💬 NLP

Improving Factuality in LLMs via Inference-Time Knowledge Graph Construction

This paper proposes a novel framework that improves the factual accuracy of Large Language Models by dynamically constructing and refining structured knowledge graphs during inference, which integrates internal model knowledge with external retrieval to overcome the limitations of unstructured text-based approaches.

Original authors: Shanglin Wu, Lihui Liu, Jinho D. Choi, Kai Shu

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shanglin Wu, Lihui Liu, Jinho D. Choi, Kai Shu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, well-read librarian (the Large Language Model, or LLM). This librarian has read millions of books and can tell you almost anything. However, like any human, they have a limit to what they can remember perfectly. Sometimes, they might mix up two similar stories, forget a specific detail, or confidently make up a fact that sounds right but isn't. This is what researchers call "hallucination."

To fix this, the authors of this paper propose a new way for the librarian to work, which they call "Inference-Time Knowledge Graph Construction."

Here is how their method works, broken down into simple steps using an analogy of building a map to find a hidden treasure.

The Problem: The "Unstructured" Search

Usually, when you ask the librarian a tricky question, they might try to answer by just thinking hard (like a "Chain of Thought"). Or, they might look up some text on the internet and read through it.

The Issue: Reading a long, messy paragraph of text is like trying to find a specific street in a city by reading a novel about the city. It's easy to get lost, miss a turn, or get distracted by irrelevant details. The librarian might grab the wrong fact because the information wasn't organized.

The Solution: Building a "Map" (The Knowledge Graph)

Instead of just reading text, the authors teach the librarian to draw a map (a Knowledge Graph) while they are answering the question. This map connects dots (facts) with lines (relationships).

Here is their 4-step process:

1. Drawing the Seed Map (Initialization)

When you ask a question (e.g., "What play was Bernstein's Symphonic Dances based on?"), the librarian first looks at their own memory and draws a small, rough sketch.

They write down: Dag Achatz → transcribed → Symphonic Dances → is from → West Side Story.
The Problem: The librarian's internal memory might be incomplete. They might stop at West Side Story and think, "That's the answer!" But actually, West Side Story itself was based on something else. The map is missing a piece.

2. Expanding the Map (Internal Expansion)

The librarian looks at their sketch and asks, "What else do I know about these dots?" They try to add more lines to the map using their own brainpower.

They might add: West Side Story → composed by → Leonard Bernstein.
The Issue: Even with this expansion, the librarian might still be missing the crucial link that connects West Side Story back to the original play, Romeo and Juliet. Their internal memory has a gap.

3. Consulting the "City Guide" (External Retrieval)

This is the magic step. The librarian realizes, "I'm not sure if I have the full picture." So, they pause and consult a trusted, external City Guide (like Wikipedia or Google Search).

They look up West Side Story in the guide.
The guide says: "West Side Story was inspired by Romeo and Juliet."
The librarian takes this new, verified fact and adds it to their map: West Side Story → inspired by → Romeo and Juliet.
The Benefit: If the librarian had made a mistake earlier (e.g., thinking the music was from a different year), the City Guide helps them correct the map, not just add to it.

4. Finding the Treasure (Answering on the Graph)

Now, with a complete, corrected map that connects Dag Achatz all the way to Romeo and Juliet, the librarian traces the path on the map. Because the path is clear and verified by the City Guide, they can confidently say: "The answer is Romeo and Juliet."

Why is this better?

The paper claims this method is superior for three main reasons:

Structure over Chaos: Instead of wading through a flood of unstructured text, the librarian works with a structured map. This makes it harder to get distracted by irrelevant information.
Self-Correction: The librarian doesn't just trust their own memory. They use the external guide to fix mistakes in their own map. If the librarian thinks "A leads to B," but the guide says "A leads to C," the librarian updates the map.
Small Librarians can do Big Jobs: The experiments showed that even smaller, less powerful "librarians" (smaller AI models) could perform just as well as giant ones if they used this map-building method. The external guide levels the playing field.

The Results

The authors tested this on three different types of trivia challenges.

The Outcome: Their method consistently got more correct answers than the standard ways of asking the AI.
The "Recall" Boost: They found that by using the external guide, the "map" they built contained the correct facts much more often (a huge jump in "recall," or finding the right facts) compared to just relying on the AI's memory.

The Catch (Limitations)

The authors are honest about the flaws:

Garbage In, Garbage Out: If the librarian draws the initial part of the map wrong, and the external guide doesn't catch it, the final answer will still be wrong.
Not Perfect: There is still a gap between having the right facts on the map and actually picking the right answer. The system isn't 100% perfect yet.

Summary

In short, this paper suggests that instead of asking an AI to just "think" or "read a paragraph," we should ask it to build a visual map of facts, check that map against a trusted encyclopedia, fix any errors on the map, and then follow the map to the answer. This makes the AI more accurate, less likely to lie, and easier to understand.

Technical Summary: Improving Factuality in LLMs via Inference-Time Knowledge Graph Construction

Problem Statement

Large Language Models (LLMs) frequently generate factually inconsistent answers due to limitations in their parametric memory. While Retrieval-Augmented Generation (RAG) paradigms attempt to mitigate this by incorporating external knowledge at inference time, existing approaches typically treat retrieved knowledge as unstructured text. This text-only approach suffers from lower retrieval accuracy, hinders compositional reasoning, and amplifies the influence of irrelevant information, ultimately undermining the factual consistency of LLM outputs. Furthermore, methods relying on static, pre-constructed Knowledge Graphs (KGs) lack adaptability in fast-changing contexts and are difficult to scale.

Methodology

The authors propose a novel, four-stage pipeline that dynamically constructs and expands Knowledge Graphs during inference, integrating both internal LLM knowledge and external retrieved knowledge. The process is formalized as follows:

Graph Initialization: Given a question $Q$ , the LLM is prompted to extract relevant entities and relations to form a seed KG ( $G_0$ ). This captures the core focus of the question.
Graph Expansion: The seed KG is iteratively expanded in a breadth-first manner using the LLM's internal knowledge. The model selects entities from a buffer and generates new triplets (subject-relation-object) to extend the graph up to a predefined depth $D$ , resulting in an expanded KG ( $G_1$ ).
External Retrieval: To address inaccuracies or gaps in $G_1$ $G_{1}$ , the system employs an external retrieval mechanism (using Wikipedia and Google Search via BM25). The LLM selects specific entities or triplets from the graph and chooses between two actions:
- Correction: Replacing erroneous triplets with factually accurate ones found in external sources.
- Expansion: Adding new related triplets to bridge knowledge gaps.
  This iterative refinement produces a grounded KG ( $G^*$ ).
Answering on Graph: Finally, the LLM generates the answer by querying the refined KG ( $G^*$ ). The model is restricted to reasoning over the triplets present in the graph to reduce off-graph hallucinations and ensure the response is grounded in verifiable evidence chains.

Key Contributions

The paper outlines three primary contributions:

Inference-Time KG Construction: A novel method to extract triplets directly from an LLM's internal knowledge and design an iterative expansion strategy to dynamically extend KGs during inference.
Hybrid Knowledge Integration: A unified pipeline that seamlessly combines internal LLM knowledge with external knowledge bases. This hybrid approach compensates for the gaps inherent in each source, enhancing factual grounding.
Empirical Validation: Extensive evaluation on three diverse Factual QA benchmarks (Complex WebQuestions, HotpotQA, and SimpleQA) demonstrates consistent and significant improvements in answer accuracy and factual consistency across different datasets and backbone models.

Experimental Results

The method was evaluated on CWQ, HotpotQA, and SimpleQA using various backbone models (including GPT-4o, Deepseek-V3, Llama-4-Scout, and Qwen2.5).

Performance Gains: The proposed approach achieved state-of-the-art results in both internal and external knowledge settings. Under the external knowledge setting, the method showed substantial improvements, particularly on the challenging SimpleQA dataset, with accuracy gains of up to 23.0% compared to baselines.
Recall Improvements: The integration of external retrieval significantly increased the recall of ground-truth facts appearing in the reasoning process. For instance, on SimpleQA, Llama-4-Scout's recall increased from 13.0% (internal only) to 37.5% (with external retrieval).
Generalization: The method proved robust across different model scales. Notably, smaller models (e.g., Llama-4-Scout) equipped with this method could outperform or match significantly larger models (e.g., DeepSeek-V3) when external retrieval was utilized, suggesting the method effectively mitigates the limitations of internal parametric memory.
Ablation Insights: Analysis revealed a trade-off where increased reasoning complexity (more hops) leads to larger graph sizes but decreased accuracy, as the model struggles to identify the correct path among expanded candidates. However, larger models generally exhibited higher accuracy and recall, with the performance gap between models narrowing when external knowledge was introduced.

Significance

The paper posits that inference-time KG construction is a promising direction for enhancing LLM factuality in a structured, interpretable, and scalable manner. By moving beyond unstructured text retrieval, the proposed framework enables LLMs to access and integrate factual knowledge systematically. The ability to dynamically construct and refine graphs allows for real-time adaptation to knowledge gaps, offering a plug-and-play solution that improves reliability without requiring extensive manual curation or static pre-built graphs. The authors emphasize that while limitations regarding hallucination propagation and graph retrieval optimality remain, the approach offers a significant step toward more trustworthy AI in high-stakes domains.