Reasoning Graphs: Self-Improving, Deterministic RAG through Evidence-Centric Feedback

• URL: http://arxiv.org/abs/2604.07595v2
• Date: Mon, 13 Apr 2026 18:38:49 GMT
• Title: Reasoning Graphs: Self-Improving, Deterministic RAG through Evidence-Centric Feedback
• Abstract summary: Language model agents reason from scratch on every query, discarding their chain of thought after each run.<n>We introduce reasoning graphs, a graph structure that persists per-evidence chain thought as structured edges connected to evidence items they evaluate.<n>We evaluate on MuSiQue and HotpotQA using a sequential cluster protocol, a high-reuse deployment simulation, and a determinism experiment.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Language model agents reason from scratch on every query, discarding their chain of thought after each run. This produces lower accuracy and high variance, as the same query type can succeed or fail unpredictably. We introduce reasoning graphs, a graph structure that persists per-evidence chain of thought as structured edges connected to the evidence items they evaluate. Unlike prior memory mechanisms that retrieve distilled strategies by query similarity, reasoning graphs enable evidence-centric feedback: given a new candidate set, the system traverses all incoming evaluation edges for each evidence item across all prior runs, surfacing how that specific item has been judged before. We further introduce retrieval graphs, a complementary structure that feeds a pipeline planner to tighten the candidate funnel over successive runs. Together, both graphs form a self-improving feedback loop: accuracy improves systematically and verdict-level variance collapses. This requires no retraining; the base model remains frozen and all gains come from context engineering via graph traversal. We evaluate on MuSiQue and HotpotQA using a sequential cluster protocol, a high-reuse deployment simulation, and a determinism experiment. At 50%+ evidence profile coverage, our system reduces errors by 47% compared to vanilla RAG on the same questions (controlled dose-response, p < 0.0001). On 4-hop questions, accuracy improves by +11.0pp (p=0.0001). In high-reuse settings, the system achieves Pareto dominance: highest accuracy, 47% lower cost, and 46% lower latency. Evidence profiles improve verdict consistency by 7-8 percentage points (p=0.007, Wilcoxon); the full system drives all 11 hard probes to perfect consistency at both temperature 0 and 0.5 (p=0.004).

Related papers

• Same Agent, Different Answers: A Repeat-Aware Audit of Corpus-Induced Answer Churn in Retrieval-Augmented QA [0.4351760066527804]
  A retrieval-augmented QA system can return different answers after an index expansion even when its requested model identifier, prompt, retrieval policy, evidence depth, rendering, and exposed generation controls are held fixed.<n>We call the hidden phenomenon accuracy-blind answer churn and introduce the emphSnapshot Compatibility Audit, which estimates excess answer churn by subtracting same-snapshot repeat disagreement from cross-snapshot disagreement.
  arXiv  Detail & Related papers  (2026-08-24T06:40:09Z)
• Dual Spatial-Temporal Attribution: Architecture-Aligned Post-Hoc Explainability for Recurrent Graph Anomaly Detection [1.8899300124593645]
  We present X-AddGraph, a post-hoc explainability framework for anomaly detection in dynamic graphs.<n>Because the detector is frozen, detection performance is preserved exactly.<n>X-AddGraph reproduces every score identically while adding explanations where none existed.
  arXiv  Detail & Related papers  (2026-08-12T15:58:27Z)
• Analysis of Federated Aggregation under Model Poisoning and Backdoor Attacks: A Reconstructed Cross-Dataset and Cross-Architecture Benchmark [0.0]
  A 500-cell seed-1 evaluation matrix was reconstructed across five aggregation methods.<n>Execution logs were identified for 454 original runs and 36 repaired or rerun executions.<n>Krum attained the highest recorded accuracy under both sign-flipping and Gaussian configurations.
  arXiv  Detail & Related papers  (2026-08-11T20:42:56Z)
• Rethinking Self-Evolving Agent Skills: Feedback Dynamics over Multiple Rounds [43.5891705224868]
  Self-evolving skill systems promise to improve agents by turning execution feedback into persistent skill updates without changing the underlying model.<n>We present a controlled evaluation framework across five benchmarks and three models.<n>Overall, persistent skill self-evolution is better understood as sparse, validation-filtered search with model- and benchmark-dependent returns.
  arXiv  Detail & Related papers  (2026-07-31T04:02:51Z)
• Fantastic Adaptive Taxonomies and How to Use Them [100.20614173157708]
  AdaMAST converts execution traces into a compact, evidence-grounded failure taxonomy.<n>No code is hand-authored, no trace human-annotated.<n>In agent-system search, taxonomy-coded diagnoses of failed candidates outperform free-form.
  arXiv  Detail & Related papers  (2026-07-17T17:41:16Z)
• Accuracy, Stability, and Repeated-Run Reliability of Large Language Models on Deterministic Programming Tasks [0.8699677835130409]
  Run-level pass rate overstates retry-free coverage by up to 17.8 percentage points.<n>We present a repeated-run evaluation protocol with metrics for run-level accuracy, retry-free coverage, and per-problem variability.
  arXiv  Detail & Related papers  (2026-05-30T23:03:05Z)
• FineVerify: Scaling Test-Time Compute with Fine-Grained Self-Verification for Agentic Search [88.16262636915975]
  FineVerify is a fine-grained self-verification framework for agentic search.<n>It decomposes each question into checkable sub-questions, verifies sampled candidates, and selects the candidate with the highest aggregated score.<n>FineVerify consistently outperforms standard scaling baselines.
  arXiv  Detail & Related papers  (2026-05-30T10:21:20Z)
• TraceGraph: Shared Decision Landscapes for Diagnosing and Improving Agent Trajectories [61.51984029109709]
  We introduce TraceGraph, a graph-based framework that turns released multi-model agent trajectories into shared decision landscapes.<n>For each task, TraceGraph builds a graph over observable action-observation states from pooled rollouts before model identity is introduced.<n>It then overlays outcome-informed productive cores and trap regions, and summarizes each rollout with three events: Access, Trap exposure, and Repair.
  arXiv  Detail & Related papers  (2026-05-29T13:40:31Z)
• Retrieving Minimal and Sufficient Reasoning Subgraphs with Graph Foundation Models for Path-aware GraphRAG [27.22974957852695]
  Graph-based retrieval-augmented generation (GraphRAG) exploits structured knowledge to support knowledge-intensive reasoning.<n>We propose GFM-Retriever that directly responds to user queries with a subgraph, where a pre-trained Graph Foundation Model acts as a cross-domain Retriever.<n>GFM-Retriever achieves state-of-the-art performance in both retrieval quality and answer generation, while maintaining efficiency.
  arXiv  Detail & Related papers  (2026-03-07T12:39:21Z)
• SAGE: Structure Aware Graph Expansion for Retrieval of Heterogeneous Data [47.930782177987446]
  Retrieval-augmented question answering over heterogeneous corpora requires connected evidence across text, tables, and graph nodes.<n>Standard retriever-reader pipelines use flat similarity search over independently chunked text, missing multi-hop evidence chains across modalities.<n>We propose SAGE (Structure Aware Graph Expansion) framework that constructs a chunk-level graph offline using metadata-driven similarities with percentile-based pruning.<n>We instantiate the initial retriever using hybrid dense+sparse retrieval for implicit cross-modal corpora and SPARK (Structure Aware Planning Agent for Retrieval over Knowledge Graphs) an agentic retriever for explicit schema graphs.
  arXiv  Detail & Related papers  (2026-02-18T23:57:19Z)
• Breaking the Static Graph: Context-Aware Traversal for Robust Retrieval-Augmented Generation [12.71443292660797]
  We propose CatRAG, Context-Aware Traversal for robust RAG.<n>CatRAG builds on the HippoRAG 2 architecture and transforms the static KG into a query-adaptive navigation structure.<n> Experiments across four multi-hop benchmarks demonstrate that CatRAG consistently outperforms state of the art baselines.
  arXiv  Detail & Related papers  (2026-02-02T11:13:38Z)
• N2N-GQA: Noise-to-Narrative for Graph-Based Table-Text Question Answering Using LLMs [0.0]
  Multi-hop question answering over hybrid table-text data requires retrieving and reasoning across multiple evidence pieces from large corpora.<n>Standard Retrieval-Augmented Generation (RAG) pipelines process documents as flat ranked lists, causing retrieval noise to obscure reasoning chains.<n>N2N-GQA is the first zeroshot framework for open-domain hybrid table-text QA that constructs dynamic evidence graphs from noisy retrieval outputs.
  arXiv  Detail & Related papers  (2026-01-10T15:55:15Z)
• Hierarchical Sequence Iteration for Heterogeneous Question Answering [27.22775290181187]
  This paper introduces HSEQ, a unified framework that linearizes documents, tables, and knowledge graphs into a reversible hierarchical sequence.<n> Experiments on HotpotQA (text), HybridQA/TAT-QA (table+text), and MetaQA (KG) show consistent EM/F1 gains over strong single-pass, multi-hop, and agentic RAG baselines with high efficiency.
  arXiv  Detail & Related papers  (2025-10-23T12:48:18Z)
• Eigen-1: Adaptive Multi-Agent Refinement with Monitor-Based RAG for Scientific Reasoning [53.45095336430027]
  We develop a unified framework that combines implicit retrieval and structured collaboration.<n>On Humanity's Last Exam (HLE) Bio/Chem Gold, our framework achieves 48.3% accuracy.<n>Results on SuperGPQA and TRQA confirm robustness across domains.
  arXiv  Detail & Related papers  (2025-09-25T14:05:55Z)
• Beyond the Last Answer: Your Reasoning Trace Uncovers More than You Think [51.0691253204425]
  We analyze intermediate reasoning steps, termed subthoughts, to answer two questions: Does the final answer reliably represent the model's optimal conclusion?<n>Our approach involves segmenting a reasoning trace into sequential subthoughts based on linguistic cues.<n>We find that aggregating these answers by selecting the most frequent one (the mode) often yields significantly higher accuracy compared to relying solely on the answer derived from the original complete trace.
  arXiv  Detail & Related papers  (2025-04-29T12:39:07Z)
• ReCEval: Evaluating Reasoning Chains via Correctness and Informativeness [67.49087159888298]
  ReCEval is a framework that evaluates reasoning chains via two key properties: correctness and informativeness. We show that ReCEval effectively identifies various error types and yields notable improvements compared to prior methods.
  arXiv  Detail & Related papers  (2023-04-21T02:19:06Z)
• Explanation Selection Using Unlabeled Data for Chain-of-Thought Prompting [80.9896041501715]
  Explanations that have not been "tuned" for a task, such as off-the-shelf explanations written by nonexperts, may lead to mediocre performance. This paper tackles the problem of how to optimize explanation-infused prompts in a blackbox fashion.
  arXiv  Detail & Related papers  (2023-02-09T18:02:34Z)
• QuTE: decentralized multiple testing on sensor networks with false discovery rate control [93.1040521878626]
  This paper designs methods for decentralized multiple hypothesis testing on graphs equipped with provable guarantees on the false discovery rate (FDR)<n>We consider the setting where distinct agents reside on the nodes of an undirected graph, and each agent possesses p-values corresponding to one or more hypotheses local to its node.<n>Each agent must individually decide whether to reject one or more of its local hypotheses by only communicating with its neighbors, with the joint aim that the global FDR over the entire graph must be controlled at a predefined level.
  arXiv  Detail & Related papers  (2022-10-09T19:48:39Z)
• ExplaGraphs: An Explanation Graph Generation Task for Structured Commonsense Reasoning [65.15423587105472]
  We present a new generative and structured commonsense-reasoning task (and an associated dataset) of explanation graph generation for stance prediction. Specifically, given a belief and an argument, a model has to predict whether the argument supports or counters the belief and also generate a commonsense-augmented graph that serves as non-trivial, complete, and unambiguous explanation for the predicted stance. A significant 83% of our graphs contain external commonsense nodes with diverse structures and reasoning depths.
  arXiv  Detail & Related papers  (2021-04-15T17:51:36Z)
• Approximate Knowledge Graph Query Answering: From Ranking to Binary Classification [0.20999222360659608]
  Structured querying on incomplete graphs will result in incomplete sets of answers. Several algorithms for approximate structured query answering have been proposed. We argue that performing a ranking-based evaluation is not sufficient to assess methods for complex query answering.
  arXiv  Detail & Related papers  (2021-02-22T22:28:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.