💻 computer science

A Multi-Agent Framework for Diagnosis and Plan Repair in Knowledge Graph Question Answering

This paper proposes TRACE, a multi-agent framework that enhances Knowledge Graph Question Answering by dynamically diagnosing and repairing LLM reasoning plans through targeted evidence retrieval and verification, thereby mitigating hallucinations and improving accuracy over existing static approaches.

Original authors: Xiaohong Yu, Shunzhi Wang, Jun Wu, Jijun Zhu

Published 2026-10-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xiaohong Yu, Shunzhi Wang, Jun Wu, Jijun Zhu

Original paper licensed under CC BY 4.0 (https://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

In the rapidly evolving world of artificial intelligence, computers have learned to read, write, and reason with a fluency that once seemed impossible. These systems, known as large language models, can answer complex questions by drawing on the vast amount of text they have studied. However, this strength is also a weakness. Because these models rely on what they have memorized, they can sometimes invent facts or confidently state things that are simply untrue, a problem researchers call hallucination. To fix this, scientists have begun connecting these models to knowledge graphs, which are structured databases of facts that act like a reliable map of the world. While this combination helps, current methods often follow a rigid path: they generate a plan, look up facts, and move forward. If the plan contains a mistake early on, the system often fails to notice, continuing down the wrong path until the final answer is wrong. The challenge has been creating a system that can not only look up facts but also stop, check its work, and correct itself when the evidence doesn't match its expectations.

A team of researchers has addressed this challenge with a new framework called TRACE, designed to make artificial intelligence more reliable when answering complex questions. Instead of letting the computer race through a series of steps, TRACE breaks the process into a careful loop of planning, checking, and fixing. The system begins by asking the large language model to create a structured plan, essentially a step-by-step sketch of how it intends to find the answer. This plan is then handed to a specialized agent that goes to the knowledge graph to find evidence for each specific step. A third agent acts as a strict auditor, comparing the model's predicted observations against the actual facts retrieved from the database. If the facts align, the system moves forward. If they do not, the system triggers a repair mechanism that diagnoses exactly what went wrong and adjusts the plan accordingly.

The researchers tested this approach on three different sets of difficult questions that require connecting multiple pieces of information. They found that TRACE consistently outperformed other methods that rely on agents to interact with knowledge graphs. When using a powerful model known as GPT-4, the new framework achieved an exact match score of 80.0 percent, meaning it got the right answer 80 percent of the time, compared to 78.0 percent for the next best method. More importantly, the system showed a significant improvement in the quality of its partial answers, with a score of 66.8 compared to 48.8 for the competitor. This suggests that even when the system does not get the perfect answer, it is much closer to the truth than previous methods. The study also showed that this approach works well with smaller, less powerful models, helping them avoid the common trap of making up facts.

What makes TRACE distinct is how it handles errors. In traditional systems, if a model makes a mistake in the first step of a reasoning chain, that error often spreads, leading to a completely wrong conclusion. TRACE prevents this by treating the knowledge graph as a checkpoint at every single step. If the system tries to say that a famous painter died in a specific city, but the database shows he died in a different one, the system stops immediately. It does not just ignore the conflict; it activates a repair strategy. Depending on the type of error, the system might simply swap out the wrong fact for the correct one, roll back to a previous step to try a different path, or break the question down into smaller, more manageable parts to ensure no constraints are missed. This process is guided by a scoring system that evaluates which repair strategy offers the most reliable path forward, ensuring that the final answer is grounded in verified evidence rather than guesswork.

The researchers also looked at the cost of running this more careful system. Because the process involves checking and potentially repairing the plan, one might expect it to use significantly more computing power. However, the study found that TRACE actually uses fewer words, or tokens, to reach an answer compared to other advanced methods. While it makes a slightly higher number of calls to the model than one competitor, the total volume of text processed is lower, making the system more efficient overall. This efficiency gain comes from the system's ability to stop early when it detects a dead end, rather than wasting resources following a flawed path to its conclusion. The results suggest that by building in a mechanism for self-correction and verification, artificial intelligence can become not only smarter but also more efficient and trustworthy in its reasoning.

Technical Summary: TRACE – A Multi-Agent Framework for Diagnosis and Plan Repair in Knowledge Graph Question Answering

1. Problem Statement

Large Language Models (LLMs) have demonstrated significant capabilities in complex reasoning but remain prone to factual hallucinations and errors stemming from incomplete parametric knowledge, particularly in knowledge-intensive tasks. While Knowledge Graphs (KGs) offer structured, trustworthy external knowledge to mitigate these issues, existing KG-enhanced LLM frameworks suffer from critical limitations:

Static Integration: Current methods often rely on rigid, static integration mechanisms that cannot dynamically adjust reasoning processes based on evolving contexts or newly retrieved evidence.
Error Propagation: Without dynamic verification, errors in early reasoning steps (e.g., incorrect entity selection or path drift) propagate through the chain, leading to incorrect final answers.
Lack of Diagnostic Mechanisms: Existing approaches, including retrieval-only and plan-based methods, typically fail to explicitly verify the semantic consistency between retrieved evidence and the current reasoning goal. Once a critical path is pruned or an initial plan is biased, the system lacks the mechanism to recover or correct the trajectory.

2. Methodology: The TRACE Framework

The paper proposes TRACE (Targeted Repair through Agent Collaboration and KG Evidence), a multi-agent framework designed to unify plan generation, KG retrieval, stepwise diagnosis, and plan repair into a closed-loop reasoning process. The framework operates through four key components:

2.1 Initial Plan Generation

Before interacting with the KG, an LLM (Plan Agent) generates a structured initial reasoning plan ( $S$ ) decomposing the query into a sequence of executable steps ( $s_t$ ). Each step includes a thought ( $T_t$ ), an action ( $A_t$ ), and a predicted observation ( $\hat{O}_t$ ). This plan serves as a "reasoning sketch" that exposes the LLM's internal assumptions, making them available for verification.

2.2 KG Retrieval with Plan

A Retrieve Agent uses the current plan step as a soft retrieval condition to navigate the KG. Instead of unguided expansion, it ranks candidate relations based on semantic relevance to the query and the current step, retrieving relevant triples ( $O_t$ ) to serve as factual evidence.

2.3 Stepwise KG Diagnosis

A Diagnostic Agent evaluates the reliability of each reasoning step before proceeding. It employs a dual-verifier architecture:

LLM-based Verifier: Analyzes the consistency between the model's predicted observation ( $\hat{O}_t$ ) and the retrieved KG triples ( $O_t$ ).
NLI Verifier: A lightweight Natural Language Inference model checks for contradictions between the prediction and the evidence.
If the verification signal indicates inconsistency ( $V=1$ ), the system triggers the repair module rather than allowing the error to propagate.

2.4 Stepwise Plan Repair

Upon detecting an inconsistency, TRACE does not regenerate the entire path. Instead, a Diagnosis-Guided Plan Repair Router identifies the error type and selects an adaptive repair strategy from five options:

Evidence Replacement: Swaps unsupported local facts with KG-grounded evidence.
Evidence Expansion: Retrieves additional context when current evidence is insufficient.
Step Rollback: Reverts to a reliable previous state and reconstructs the path if the reasoning has drifted from the intent.
Constraint Decomposition: Breaks down complex questions into sub-constraints that must be individually verified.
Answer Verification Repair: Validates the final candidate answer against accumulated constraints.

2.5 Multi-Perspective Reward Mechanism

To ensure the quality of repaired plans, a KG-Grounded Repair Score ( $\nu_t$ ) evaluates the new plan based on:

Trace Coherence: Logical flow of the revised reasoning.
KG Grounding: Factual support from retrieved triples.
Constraint Coverage: Adherence to the original question's constraints.
Answer Confidence: Stability of the final answer.
Efficiency: Penalizing overly long or redundant reasoning.
Only plans with sufficient scores are accepted for subsequent reasoning steps.

3. Key Contributions

The authors highlight three primary contributions:

Unified Closed-Loop Framework: TRACE integrates plan generation, retrieval, diagnosis, and repair into a single collaborative multi-agent system, moving beyond static retrieval or fixed planning.
KG-Feedback-Driven Diagnosis: The framework introduces a mechanism to inspect intermediate reasoning steps in real-time, using KG evidence to align and repair plans dynamically rather than relying solely on the LLM's parametric knowledge.
Adaptive Repair and Evaluation: The system utilizes a multi-view reward mechanism to evaluate repaired paths, ensuring that the selected reasoning trajectory balances factual accuracy, constraint satisfaction, and efficiency.

4. Experimental Results

The framework was evaluated on three benchmark datasets: ComplexWebQuestions (CWQ), WebQSP, and WebQuestions, using three LLM backbones: Qwen2.5-7B, GPT-3.5, and GPT-4.

Performance Gains: TRACE consistently outperformed agent-based baselines (ToG and PoG) across all models and datasets.
- Under GPT-4, TRACE achieved an average Exact Match (EM) of 80.0 and F1 of 66.8, compared to PoG's 78.0/48.8.
- Under Qwen2.5-7B, TRACE improved the average F1 from 34.0 (PoG) to 52.1 and EM from 50.2 to 59.8.
Comparison with Fine-Tuned Methods: Despite not using task-specific supervised fine-tuning, TRACE achieved competitive results against fine-tuned KG-RAG methods (e.g., RoG, GNN-RAG), suggesting that effective use of KG feedback during inference is a potent alternative to parameter tuning.
Efficiency Analysis: A cost analysis using GPT-4o-mini revealed that TRACE reduced token consumption significantly compared to ToG (up to 39.3% on WebQSP) and PoG (35.7% on WebQSP), though it required a marginal increase in API calls compared to PoG. This indicates a trade-off where TRACE achieves higher accuracy and lower token usage per question through more efficient, targeted reasoning.

5. Significance and Claims

The paper claims that the significance of TRACE lies in its ability to treat KG feedback not merely as external context for answer generation, but as a process-level diagnostic signal. By continuously verifying intermediate states and dynamically repairing reasoning paths, TRACE addresses the core limitations of hallucination and error propagation in LLM reasoning.

The authors emphasize that their approach demonstrates that evidence-guided diagnosis and plan repair can significantly enhance the reliability of KG-enhanced LLMs without requiring extensive retraining. The framework provides a robust mechanism for LLMs to self-correct when their internal knowledge conflicts with structured external evidence, thereby improving both the accuracy and the interpretability of complex reasoning tasks.