Grounding LLM Reasoning under Incomplete Graph Evidence
2026-06-29 • Computation and Language
Computation and Language
AI summaryⓘ
The authors explore how large language models (LLMs) can use incomplete knowledge graphs to help with reasoning. They explain that because these graphs often lack complete information, it's impossible to always perfectly distinguish true paths from false ones just based on what’s observed. They propose a way to gently guide the model’s reasoning by balancing the knowledge graph evidence with the language model’s own predictions, allowing some flexibility rather than strict rules. Their approach also helps understand how different systems like GraphRAG or knowledge graph question answering manage this balance.
Large Language ModelsKnowledge GraphsOpen-World IncompletenessGraphRAGKGQASoft GroundingKL RegularizationConstrained DecodingFaithful GenerationEntity Anchors
Authors
Jiaqi Li, Fanghui Song
Abstract
Knowledge graphs can guide large language models (LLMs) reasoning, but the graph seen by a system is usually a retrieved, linked, temporally scoped, and incomplete evidence state rather than a complete account of truth. We develop a theoretical perspective on grounding observable LLM trajectories under such incomplete graph evidence.The evidence state induces entity anchors, typed relation residuals, path energies, and support regions, while the language model supplies a prior over candidate trajectories. We show that, under open-world incompleteness, no hard rule based only on the observed state can both reject every false unsupported trajectory and retain every true-but-unobserved one.We then characterize soft grounding as a KL-regularized deformation of the LLM prior: finite slack preserves support for unsupported but non-contradicted trajectories, whereas hard conditioning appears as an infinite-penalty limit.The framework also yields stability bounds under evidence perturbations and clarifies the constraint regimes appropriate for GraphRAG, KGQA, graph agents, constrained decoding, and faithful generation. The claims are evidence-relative: KG compatibility is treated as declared support, not factual truth.