💬 NLP

Reasoning Graphs: Deterministic Agent Accuracy through Evidence-Centric Chain-of-Thought Feedback

This paper introduces "reasoning graphs," a novel structure that persists evidence-centric chain-of-thought feedback across queries to enable self-improving, deterministic agent accuracy without retraining, thereby significantly reducing variance in multi-hop question answering.

Original authors: Matthew Penaroza

Published 2026-04-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matthew Penaroza

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 are hiring a brilliant but slightly forgetful detective to solve a series of mysteries. Every time you give them a new case, they start from zero. They read the clues, make a guess, and then—poof!—they forget everything they just learned. If you give them a similar case the next day, they have to re-read the same clues and re-figure out the same logic, often making the same mistakes or getting lucky with a different answer.

This is exactly how current AI agents (like advanced chatbots) work today. They are smart, but they don't "remember" their past reasoning.

This paper introduces a solution called Reasoning Graphs. Think of it as giving your detective a giant, living notebook that never forgets, organized in a very specific way.

Here is the breakdown using simple analogies:

1. The Problem: The "Reset Button"

Currently, every time an AI answers a question, it treats the evidence (the facts it finds) as if it's seeing them for the first time.

The Analogy: Imagine a chef who cooks a great meal, but every time a customer orders the same dish, the chef throws away the recipe and the notes on what went wrong, then tries to cook it from scratch again. Sometimes they get it right; sometimes they burn it. It's unpredictable.

2. The Solution: The "Evidence-Centric Notebook"

The authors propose two special structures (graphs) that act as this notebook.

A. The Reasoning Graph (The "Clue Diary")

Instead of just remembering "I solved a murder case yesterday," this graph remembers "I looked at this specific piece of paper (evidence) and decided it was fake."

How it works:
- Every time the AI looks at a specific fact (like a Wikipedia paragraph), it writes down: "I used this," or "I rejected this because it was about the wrong movie."
- The Magic Trick: When the AI sees that same fact again in a new case, it doesn't start from scratch. It opens the notebook, looks at that specific fact, and sees a history: "Hey, 14 times in the past, smart detectives rejected this fact because it was a red herring."
- The Result: The AI gets smarter at spotting bad clues without needing to be retrained. It's like a detective who instantly recognizes a known liar because they've seen them before.

B. The Retrieval Graph (The "Trash Can")

This is the second part of the system. It helps the AI decide what not to look at in the future.

How it works:
- If the notebook shows that a specific fact is always rejected by the AI (even if the AI got the final answer right), the system marks that fact as "trash" for that type of question.
- The Analogy: Imagine a detective who keeps getting distracted by a specific newspaper article that has nothing to do with the case. After a few tries, the detective puts that newspaper in a "Do Not Read" bin. Now, when a new case comes in, they don't even waste time looking at that newspaper.
- The Result: The AI works faster and cheaper because it stops wasting time on useless information.

3. Why This is a Big Deal

The paper highlights three superpowers this system gives the AI:

Consistency (Deterministic Accuracy):
- Before: The AI might solve a puzzle correctly on Monday, fail on Tuesday, and guess randomly on Wednesday, even if the puzzle is the same.
- After: Because the AI consults its "Clue Diary," it makes the same correct decision every time it sees the same evidence. It becomes reliable.
No "Schooling" Required:
- Usually, to make an AI smarter, you have to feed it thousands of new examples and retrain its brain (which costs a lot of money and time).
- Here: The AI's "brain" (the base model) stays exactly the same. It just gets a better notebook. The improvement comes from how it uses the context, not from changing its internal code.
Full Transparency (Auditability):
- If the AI makes a mistake, you can trace its steps backward through the graph. You can see exactly which clue it looked at, what it thought about it, and why it made a decision. It's like having a video replay of the detective's entire thought process.

4. The "Cold Start" Reality

The paper admits a small catch: When the system is brand new (the "Cold Start"), the notebook is empty. The AI has to reason from scratch just like before.

The Analogy: It's like a new detective arriving at the station. They have no files yet. But as soon as they solve a few cases and fill the files, the system "warms up" and starts getting incredibly efficient.

Summary

This paper proposes a way to make AI agents learn from their specific experiences with facts rather than just general patterns. By building a permanent, structured memory of how they judged every single piece of evidence, the AI becomes:

More accurate (it stops making the same mistakes).
More consistent (it acts the same way every time).
More efficient (it stops looking at useless clues).

It's the difference between a student who forgets the lesson after every test and a student who keeps a detailed study guide, learning from every single question they've ever answered.

1. Problem Statement

Current Language Model (LM) agents operate in a stateless loop: for every query, they retrieve evidence, reason over it, and produce an answer. Once the task is complete, the Chain of Thought (CoT)—the specific evaluation of why evidence was used or rejected—is discarded. This leads to two critical issues:

Low Accuracy: Agents repeatedly re-evaluate the same evidence items from scratch, failing to leverage prior correct evaluations.
High Variance: Identical queries can yield different results (success or failure) unpredictably because the agent lacks constraints from past experiences. Recent studies show that inconsistent agent behavior correlates strongly with task failure.

Existing memory mechanisms (e.g., Reflexion or ReasoningBank) address this by storing distilled strategies or self-reflections indexed by query similarity or recency. However, these approaches are query-centric, meaning they retrieve general strategies rather than specific insights about the evidence items currently being examined. Consequently, the feedback is often disconnected from the specific context the agent is processing.

2. Methodology

The authors propose a dual-graph architecture that persists the agent's reasoning as structured graph edges, enabling evidence-centric feedback. The system operates without retraining the base model; all improvements come from context engineering via graph traversal.

A. Reasoning Graph ( $G_R$ )

This is the core contribution. It persists the agent's per-evidence chain of thought as directed edges connecting agents to evidence items.

Structure: Nodes represent Agents, Decisions, and Evidence Items. Edges represent "Decided" (outcome, confidence) and "Evaluated" (step, verdict, reasoning).
Backward Traversal (Evidence-Centric Feedback): When a new query arrives, the system does not search for similar past queries. Instead, for every evidence item in the current candidate set, it traverses incoming edges from all past runs.
- It aggregates evaluations specifically for that evidence item.
- It filters for correct outcomes only to avoid reinforcing errors.
- It constructs an Evidence Profile containing the verdict distribution (e.g., "rejected 90% of the time"), top reasoning patterns, and a reliability score.
- This profile is injected into the agent's prompt alongside the raw evidence.
Forward Traversal (Auditability): Allows reconstructing the full chain of thought for any past decision for debugging and analysis.

B. Retrieval Graph ( $G_P$ )

A complementary structure that optimizes the retrieval pipeline.

Structure: Connects Decision nodes to Evidence items via "Retrieved via" edges, capturing metadata (rank, similarity score).
Pipeline Planner: Analyzes rejection rates for specific evidence items within a query type. If an item is consistently rejected across past runs (even if the final answer was correct), the planner excludes it from future candidate sets.
Effect: This "tightens the candidate funnel," reducing the number of irrelevant passages the agent must process, thereby lowering token costs and noise.

C. The Feedback Loop

Retrieve: The Pipeline Planner (using $G_P$ ) filters the candidate set.
Reason: The Agent receives the filtered set + Evidence Profiles (from $G_R$ ).
Act & Observe: The agent produces an answer and receives an outcome signal (correct/incorrect).
Update: New edges are written atomically to both graphs.
Result: Over successive runs, accuracy converges, and variance collapses as the agent relies on verified historical signals rather than reasoning from scratch.

3. Key Contributions

Reasoning Graphs: A novel graph structure that shifts memory retrieval from "query similarity" to "evidence identity." It enables the system to ask, "How has this specific passage been judged before?" rather than "What strategies worked on similar questions?"
Retrieval Graphs: A mechanism for self-optimizing the retrieval pipeline by excluding consistently unhelpful evidence items.
Deterministic Accuracy: The system achieves deterministic behavior (identical verdicts on the same evidence across runs) without retraining. The base model remains frozen; improvements are purely structural.
Evaluation Protocol: A proposed Sequential Cluster Protocol designed to measure accuracy convergence and variance collapse over time, addressing the limitations of standard i.i.d. benchmarks.

4. Results & Expected Outcomes

Note: As the paper presents a framework and protocol rather than finalized experimental results, the "results" section describes the hypothesized outcomes and theoretical guarantees.

Accuracy Convergence: Task accuracy is expected to be non-decreasing over successive runs as evidence profiles become richer and the candidate funnel tightens.
Variance Collapse: Decision consistency is expected to increase as the agent aligns its verdicts with the majority signal in the evidence profiles.
Cost Efficiency: While injecting profiles adds tokens, the exclusion of entire passages via the retrieval graph is expected to result in a net decrease in inference cost over time.
Ablation Hypotheses: The paper hypothesizes that the full system will outperform:
- Vanilla RAG (no memory).
- Reflexion (recency-based memory).
- ReasoningBank (query-similarity memory).
- A "Query-Centric" variant of the graph (proving the superiority of evidence-centric traversal).

5. Significance

Retraining-Free Improvement: The system achieves significant performance gains without fine-tuning or gradient updates, making it applicable to any frozen foundation model.
Full Auditability: Every decision is traceable through the graph, enabling systematic failure diagnosis and safety auditing, which is crucial for enterprise deployment.
Scalability: The approach scales with corpus size; as retrieval noise increases with larger corpora, the evidence-centric feedback provides a stable, pre-verified signal that compensates for noise.
Cross-Model Transfer: Evidence profiles are model-agnostic. A graph accumulated by a high-capability model can be used to boost the performance of a smaller, cheaper model.

6. Limitations & Future Work

Cold Start: The system performs at baseline levels until the graph accumulates sufficient edges for a specific query type.
Error Reinforcement: If the outcome signal is noisy or biased, the system could reinforce incorrect patterns (mitigated by the "correct-outcome filter").
Identity vs. Semantics: The system relies on exact passage deduplication (content hash). It cannot currently merge profiles for semantically equivalent but textually different passages.
Distribution Shift: The system does not currently adapt to shifts in query types over time.

In conclusion, Reasoning Graphs represent a paradigm shift from query-based memory to evidence-based memory, offering a path toward deterministic, auditable, and self-improving AI agents through structural context engineering.