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

• URL: http://arxiv.org/abs/2608.10676v1
• Date: Tue, 11 Aug 2026 08:56:42 GMT
• Title: Self-Correcting Long-Horizon Search Agents via Tree-Structured Memory
• Abstract summary: We propose ReTree, a self-correcting tree-structured memory mechanism for search agents.<n>ReTree constructs a bounded per-step reasoning context while preserving source-linked evidence.<n>Experiments on four public question-answering and search benchmarks show that ReTree consistently outperforms Full-Trajectory ReAct.
• Score: 20.351040137738398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large language model (LLM)-based search agents answer questions through multi-step interactions with external environments. However, providing complete execution trajectories to the LLM causes unbounded context growth and introduces noise. Existing compression methods reduce context at the cost of important details and often replace erroneous facts without repairing downstream reasoning derived from them. To address this problem, we propose ReTree, a self-correcting tree-structured memory mechanism for search agents. ReTree constructs a bounded per-step reasoning context while preserving source-linked evidence. It 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 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\times$ that of ReTree. These results establish ReTree as an effective self-correcting memory abstraction for long-horizon search.

Related papers

• TreeSeeker: Tree-Structured Trial, Error, and Return in Deep Search [43.554579524244495]
  TreeSeeker is an inference-time framework for controlled trial-and-error in deep search.<n>It organizes search as branch-and-return search over tree-structured states, where each branch is a tentative direction for a sub-goal.<n>TreeSeeker consistently outperforms strong open-source baselines.
  arXiv  Detail & Related papers  (2026-06-10T05:10:19Z)
• PruneRAG: Confidence-Guided Query Decomposition Trees for Efficient Retrieval-Augmented Generation [19.832367438725306]
  PruneRAG builds a structured query decomposition tree to perform stable and efficient reasoning.<n>We define the Evidence Forgetting Rate as a metric to quantify cases where golden evidence is retrieved but not correctly used.
  arXiv  Detail & Related papers  (2026-01-16T06:38:17Z)
• ToM: Leveraging Tree-oriented MapReduce for Long-Context Reasoning in Large Language Models [107.86069298500855]
  ToM is a novel Tree-oriented MapReduce framework for long-context reasoning.<n>We show that ToM significantly outperforms existing divide-and-conquer frameworks and retrieval-augmented generation methods.
  arXiv  Detail & Related papers  (2025-11-01T10:43:58Z)
• TreeRare: Syntax Tree-Guided Retrieval and Reasoning for Knowledge-Intensive Question Answering [10.597526246308938]
  Iterative and adaptive retrieval has been shown to be a promising approach to resolve complex, knowledge-intensive questions.<n>We propose TreeRare, a framework that utilizes syntax trees to guide information retrieval and reasoning for question answering.<n>TreeRare achieves substantial improvements over existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-05-31T01:07:50Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>We identify two key challenges contributing to this inefficiency: $textitover-exploration$ due to redundant states with semantically equivalent content, and $textitunder-exploration$ caused by high variance in verifier scoring.<n>We propose FETCH, a flexible, plug-and-play system compatible with various tree search algorithms.
  arXiv  Detail & Related papers  (2025-02-16T16:12:01Z)
• ReTreever: Tree-based Coarse-to-Fine Representations for Retrieval [64.44265315244579]
  We propose a tree-based method for organizing and representing reference documents at various granular levels.<n>Our method, called ReTreever, jointly learns a routing function per internal node of a binary tree such that query and reference documents are assigned to similar tree branches.<n>Our evaluations show that ReTreever generally preserves full representation accuracy.
  arXiv  Detail & Related papers  (2025-02-11T21:35:13Z)
• Tree of Reviews: A Tree-based Dynamic Iterative Retrieval Framework for Multi-hop Question Answering [0.18849131083278733]
  We propose a dynamic retrieval framework called Tree of Reviews (ToR) for multi-hop question answering. ToR achieves state-of-the-art performance in both retrieval and response generation.
  arXiv  Detail & Related papers  (2024-04-22T09:25:05Z)
• Probabilistic Tree-of-thought Reasoning for Answering Knowledge-intensive Complex Questions [93.40614719648386]
  Large language models (LLMs) are capable of answering knowledge-intensive complex questions with chain-of-thought (CoT) reasoning. Recent works turn to retrieving external knowledge to augment CoT reasoning. We propose a novel approach: Probabilistic Tree-of-thought Reasoning (ProbTree)
  arXiv  Detail & Related papers  (2023-11-23T12:52:37Z)
• Tree Prompting: Efficient Task Adaptation without Fine-Tuning [112.71020326388029]
  Tree Prompting builds a decision tree of prompts, linking multiple LM calls together to solve a task. Experiments on classification datasets show that Tree Prompting improves accuracy over competing methods and is competitive with fine-tuning.
  arXiv  Detail & Related papers  (2023-10-21T15:18:22Z)
• Entailment Tree Explanations via Iterative Retrieval-Generation Reasoner [56.08919422452905]
  We propose an architecture called Iterative Retrieval-Generation Reasoner (IRGR) Our model is able to explain a given hypothesis by systematically generating a step-by-step explanation from textual premises. We outperform existing benchmarks on premise retrieval and entailment tree generation, with around 300% gain in overall correctness.
  arXiv  Detail & Related papers  (2022-05-18T21:52:11Z)

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.