Self-Correcting Long-Horizon Search Agents via Tree-Structured Memory

ReTree is a self-correcting tree-structured memory mechanism for LLM-based search agents. It constructs a bounded per-step reasoning context while preserving source-linked evidence. ReTree models search as an evidence tree whose nodes store bounded summaries, evidence, and revision histories. When newly retrieved evidence contradicts an earlier claim, ReTree traces back to the node where the claim was introduced, replaces outdated evidence, regenerates summaries, prunes affected branches, and resumes search. Source-grounded evidence provenance supports reliable conflict localization and keeps final claims traceable to retrieved passages.

Experiments on four public question-answering and search benchmarks (Bamboogle, HotpotQA, 2WikiMultiHopQA, and FRAMES) show that ReTree consistently outperforms Full-Trajectory ReAct, improving answer accuracy by up to 25.6 percentage points (pp); the average maximum per-step reasoning context of Full-Trajectory ReAct is 1.27–1.51× that of ReTree. These results establish ReTree as an effective self-correcting memory abstraction for long-horizon search.

The paper formalizes retrieval-induced error cascades as a structural state-repair problem with three joint requirements: bounded per-step reasoning context, claim-to-source provenance, and dependent-state invalidation. ReTree couples bounded summary-plus-evidence context construction with stable evidence identifiers and contradiction-triggered backtracking, summary regeneration, and subtree pruning. It implements passage-level source binding that survives memory revision, allowing answer claims to be resolved to current evidence objects and raw retrieved passages.

Across 2,149 questions drawn from four public benchmarks, ReTree improves judge accuracy over Full-Trajectory ReAct by 8.3–25.6 points; the average maximum per-step reasoning context of Full-Trajectory ReAct is 1.27–1.51× that of ReTree. ReTree also improves accuracy over FlatUpdate on every dataset and exceeds ReportMemory, the strongest aggregate baseline, by 3.0 points overall. On a large-scale FRAMES attribution diagnostic, ReTree also attains higher citation precision and recall than both the full-trajectory and report-style baselines.

Improvements to AI systems:

1. Implement self-correcting memory with provenance tracking – The AI system can maintain a tree-structured memory where each node stores a bounded summary, source-linked evidence, and a revision history. When new information contradicts an existing claim, the system traces back to the originating node, replaces outdated evidence, regenerates the summary, prunes dependent branches, and resumes reasoning. This enables the system to handle long-horizon tasks (e.g., multi-hop research, complex troubleshooting) without context overflow or error propagation.

2. Add contradiction-triggered backtracking and subtree pruning – The system can automatically detect contradictions between newly retrieved evidence and previously stored claims, then invalidate only the affected dependent states rather than restarting or blindly appending. This reduces cascading errors and improves accuracy in dynamic information environments (e.g., live fact-checking, evolving news analysis).

3. Enforce bounded per-step reasoning context – The system can cap the amount of context used at each reasoning step by storing compressed summaries plus evidence identifiers, rather than full trajectories. This allows the system to operate on devices with limited memory or to process longer sequences without hitting token limits, while maintaining performance comparable to full-context models.

4. Provide claim-to-source provenance resolution – The system can bind every final answer claim to a stable evidence identifier and a raw retrieved passage, even after memory revisions. This makes the system’s outputs fully traceable and auditable, enabling citation generation, fact-checking, and user verification in applications like legal research, medical diagnosis support, or academic writing assistance.

5. Implement stable evidence identifiers that survive memory updates – The system can keep source references consistent across revisions, so when a summary is regenerated or a branch is pruned, the underlying evidence links remain valid. This allows the system to maintain trustworthiness in iterative reasoning tasks, such as iterative code debugging or sequential scientific literature review.

6. Use structural state-repair for retrieval-induced error cascades – The system can formalize its memory management as a repair problem with three joint requirements: bounded context, provenance, and dependent-state invalidation. This enables the system to proactively prevent error accumulation in multi-step retrieval tasks, improving robustness in open-domain question answering, conversational search, and autonomous research agents.

What the improved AI system can do:

• Answer multi-hop questions with higher accuracy (up to +25.6 percentage points) than standard full-trajectory reasoning agents, while using 27–51% less peak per-step context.

• Self-correct its reasoning when new evidence contradicts prior assumptions, without losing traceability of its final answers to specific source passages.

• Operate in memory-constrained environments (e.g., mobile assistants, edge devices) while maintaining state-of-the-art performance on long-horizon search tasks.

• Generate citations and evidence trails for every claim, even after iterative updates to its internal knowledge, making it suitable for high-stakes domains requiring verifiability.

• Prune irrelevant or outdated branches of reasoning automatically, reducing noise and improving focus in complex, multi-source information gathering.