acceptodds
Under review as a conference paper at ICLR 2027

BranchMem: Branch-Structured Memory for Long-Horizon Search Agents

Abstract

Long-horizon search agents accumulate evidence across retrieval rounds, form in- termediate judgments, and use earlier findings to guide subsequent actions. As the interaction history grows beyond a single context window, memory must preserve a state that remains useful for future decisions. An executed search trajectory can support several unresolved candidate interpretations, each with its own in- termediate judgments. We introduce BranchMem, a branch-structured memory framework that maintains each task-relevant candidate interpretation as a persis- tent branch. New observations can extend a branch or revise its local judgments; subsequent decisions read the candidate branches and their associated evidence to reassess unresolved interpretations. We evaluated BranchMem on all 221 Memo- ryArena Search task groups.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM Agents, Agent Memory, Long-Horizon Search

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_hyxeOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

BranchMem stores each task-relevant interpretation of a long-horizon search as a persistent branch, including a candidate, local natural-language judgments, source identifiers, and revision records. The same search model proposes optional updates at stage boundaries. Later decisions read a bounded view of history, sources, and up to three branches, allowing temporarily weaker candidates to remain associated with their supporting evidence when delayed clues arrive. On all 221 MemoryArena Search groups, BranchMem achieves 71.49% final success and 59.23% progress, outperforming the strongest listed baseline while using the fewest tokens. Component ablations further show that removing branches, retaining only one candidate, or dropping revision fields reduces both success and progress.

Critical strengths
  • The representation is well aligned with the failure mode motivating the paper. Keeping alternative candidate-specific evidence chains, rather than only salient facts or a compressed trajectory, is a reasonable design for delayed-evidence search. The ablations consistently support the usefulness of candidate branches, multiple candidates, and revision fields.

  • The evaluation is reasonably broad within the chosen setting. The paper evaluates all 221 MemoryArena Search groups under a shared actor, retrieval environment, and tool budget. The trace-level analysis also provides concrete evidence that retained candidates and source references are used in later search stages.

Critical weaknesses
  • The experiments do not directly compare BranchMem with the closest structural alternatives. Table 1 provides a broad comparison with several memory and retrieval systems, but these baselines do not all directly test persistent, candidate-specific evidence chains. ReTree is particularly relevant because the paper itself describes it as maintaining source-linked claims and repairing affected state after contradictory evidence, yet it is not included in the main comparison. In addition, although the paper states that the actor, retrieval environment, task collection, and search budget are shared across baselines, it provides limited detail on how each published method was adapted to the local search harness. This makes it difficult to assess whether the observed gain is primarily due to the proposed representation or partly due to implementation differences.

  • The evaluation does not directly isolate the failure mode that BranchMem is designed to address. The main motivation of BranchMem is that a temporarily weaker candidate may become correct after delayed evidence arrives, and therefore multiple candidate-specific evidence chains should remain available for later revision. However, the experiments mainly report aggregate success and progress scores over the full MemoryArena Search collection. The paper provides only a small number of qualitative traces, while only 39 lifecycle-state changes are observed across 29 groups.

Questions for authors
  1. Could the authors clarify whether ReTree was considered or evaluated under the same actor, retrieval environment, and task collection? Given its source-linked revision mechanism, a comparison or discussion of the practical differences would help clarify the contribution of BranchMem.

  2. Could the authors provide more detail on how the published baselines were adapted to the local search harness and how implementation fidelity was checked? It would also be helpful to report per-task paired outcomes for the strongest baselines, and repeated runs where feasible, to better assess the stability of the reported improvements.

1 comment

We thank the reviewer for their suggestions regarding baseline comparisons, implementation details, and mechanism analysis. We have added experiments with ReTree and clarify below the baseline adaptations and the interpretation of the trace statistics.

W1 / Q1: Direct comparison with ReTree.

Following the reviewer’s suggestion, we additionally evaluated ReTree:

MethodSuccess rate SR (%)Progress score PS (%)Tokens/group (k)
ReTree67.4252.491815.40
BranchMem71.4959.23812.59

ReTree is the strongest baseline in the expanded comparison. Across all 221 task groups, BranchMem correctly answers 158 final questions, compared with 149 for ReTree. BranchMem achieves a 4.07-percentage-point higher success rate and a 6.74-percentage-point higher progress score, while consuming approximately 55.24% fewer tokens on average. This direct comparison extends the original evaluation to a structurally related method.

The two methods also differ in emphasis. ReTree focuses on backtracking and repairing affected state when new evidence contradicts existing claims, whereas BranchMem emphasizes the persistent maintenance of coexisting candidate interpretations within the same search history.

W2 / Q2: Baseline adaptation and implementation details.

The baseline results reported in our paper come from evaluations within the local search framework, rather than being taken directly from the original papers.

In the revision, we will provide the memory writing, reading, and updating rules actually used for each method, along with configurations, prompts, and modifications required to interface with the local search tools. We will distinguish the original mechanisms from the local adaptations so that readers can examine how each implementation corresponds to its original design. For the newly added ReTree baseline, we will also specify the implementation of source linking, conflict handling, and state repair, as well as the scope of token accounting.

W3: Candidate reassessment and lifecycle statistics.

The 39 lifecycle-state changes reported in the paper count only explicit state-label changes for the same candidate across different reads; they do not capture all candidate-information updates or subsequent uses. A candidate can retain the same state while accumulating new judgments, sources, and task-relation information. The model can also use retained candidates to adjust queries or final answers without changing their lifecycle labels. This count therefore does not directly measure how frequently candidates are reassessed when delayed evidence arrives.

Reviewer_qqVmOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes BranchMem, a candidate-centric memory framework for long-horizon search agents. It maintains competing hypotheses with associated judgments, evidence references, and revision histories across search stages. The framework supports incremental memory updates and jointly presents retained candidate information to guide subsequent search decisions. On 221 MemoryArena Search task groups, BranchMem achieves a 71.49% final success rate, outperforming MAGE (64.25%) while reducing token consumption. Component ablations suggest benefits from candidate retention, multiple hypotheses, and explicit revision records.

Critical strengths
  1. The framework provides a coherent way to maintain competing hypotheses, associated evidence, and revision histories across search stages.
  2. Table 1 demonstrates a 7.24 percentage points improvement over MAGE while reducing token consumption by approximately 50%. Furthermore, the ablation studies presented in Table 2 provide supporting evidence for these results.
Critical weaknesses
  1. Limited technical novelty over existing memory frameworks. The main components of BranchMem, including multiple hypothesis tracking, evidence-grounded judgments, incremental updates, and revision-aware memory, have already been explored in related work such as BeliefMem[1], ReTree[2], and MAGE[3]. The primary distinction appears to be organizing related judgments and evidence into candidate-centric branches. While this is a reasonable design, the technical contribution seems relatively incremental compared with existing structured-memory approaches. The paper does not sufficiently establish what fundamentally new capability this representation introduces.
  2. Insufficient validation of the distinctive mechanism. Although the overall results are promising, the ablations in Table 2 do not distinguish the benefits of the proposed branch representation from those of organizing equivalent information in a simpler structured memory. Furthermore, Figure 1 illustrates potential cross-hypothesis evidence mixing, but the experiments do not systematically demonstrate that BranchMem reduces this specific failure mode relative to existing methods. The evaluation is also limited to a single actor model and benchmark, without reported repeated-run results or paired significance analysis. Consequently, the experiments demonstrate system-level effectiveness but provide insufficient evidence for the distinctive value of the proposed representation.

[1] Liao J, Wang Q, Zhu J, et al. Belief Memory: Agent Memory Under Partial Observability[J]. arXiv preprint arXiv:2605.05583, 2026. [2] Yang A, Guo Q, Huang Z, et al. Self-Correcting Long-Horizon Search Agents via Tree-Structured Memory[J]. arXiv preprint arXiv:2608.10676, 2026. [3] Chen Y, Lai H, Feng Y, et al. Beyond Semantic Organization: Memory as Execution State Management for Long-Horizon Agents[J]. arXiv preprint arXiv:2606.06090, 2026.

Questions for authors
  1. What is the fundamental technical distinction between BranchMem and existing multi-hypothesis or structured-memory approaches, particularly BeliefMem? Beyond the organization of candidate records, what new capability does BranchMem introduce?
  2. Provide an information- and budget-matched comparison against a simpler structured-memory baseline, or quantitative evidence that BranchMem specifically reduces cross-hypothesis evidence mixing.
1 comment

We thank the reviewer for their comments. We would like to clarify that BranchMem’s contribution primarily lies in the persistent representation of candidate interpretations and how they are updated. BranchMem maintains each candidate interpretation as a persistent collection of judgments. For example, when two candidate papers are associated with different authors and research findings, preserving these facts alone is insufficient; their membership in the corresponding candidate interpretations must also be retained.

This emphasis differs from those of related approaches: BeliefMem focuses on alternative conclusions and their evidential support, ReTree on evidence dependencies and repair, and MAGE on execution state management. BranchMem emphasizes the membership of judgments within coexisting candidate interpretations derived from the same executed search history, and the maintenance of that membership across stages.

Empirically, BranchMem achieves a success rate of 71.49% across all 221 task groups, outperforming MAGE and BeliefMem by 7.24 and 11.31 percentage points, respectively. Restricting memory to a single candidate reduces success by 6.78 percentage points, while removing revision fields reduces it by 4.52 percentage points. These results support the practical value of candidate retention and revision.

Reviewer_oJY5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper introduces a branch-structured memory framework designed for long-horizon search agents that must accumulate and evaluate evidence over multiple retrieval rounds. The proposed solution groups task-relevant candidates, local judgments, and source references into persistent candidate branches that can be incrementally updated and revised as new evidence arrives. Experimental study shows that a strong final success rate was achieved while consuming significantly fewer tokens than baseline approaches.

Critical strengths

The decoupled local judgments and revision histories sounds an interesting design. BranchMem decouples raw source observations from task-level candidate interpretations. It enables incremental, candidate-level status updates and preserves revision records without corrupting or overwriting shared execution histories or valid underlying source facts. The performance and token savings seem encouraging, which on MAGE improves task progress, while using fewer tokens. The methods use the same agent model, retrieval environment, and tool budgets. Token counts include memory updates and later memory reads, not just answer generation. The authors provide thorough experimental backing, including stage-level trace analysis and systematic component ablations

Critical weaknesses

The proposed design architecture imposes fixed settings and item caps, e.g., candidate text capped, task relations, etc., In complex domains requiring highly intricate reasoning chains or lengthy citations, these fixed limits could constrain expressive quality. In the evaluation, the system keeps the three most recently inserted candidates, so an older candidate can be removed even after an update. No stress test shows what happens when capacity is reached or useful candidates are removed. Higher success on longer task groups is not compared with baselines The related-work section describes candidate beliefs, source tracking, and updates in BeliefMem and ReTree. Removing candidates or revision fields changes the information available, not just how it is grouped. A stronger test would compare branches with a flat memory containing exactly the same information, or change only which candidate a claim belongs to. There is some concern about the reproducibility of the experimental study, mainly because of the lacking baseline models’ settings and prompts, such as the judge prompt and grading examples for the answer judge in the experiments. In Figure 3, the performance scales positively with search depth, that is, the BranchMem achieves 64.56% SR on short tasks, 71.11% on medium tasks, and 82.69% on long-horizon tasks This demonstrates that persistent candidate branches become increasingly advantageous as interaction depth expands, which is worth a bit more explanation. Intuitively, the success compared to baseline could be like that, but not the absolute success rate.

Questions for authors

n/a

2 comments

We thank the reviewer for pointing out the potential limitations of a fixed candidate capacity. We conducted additional experiments with maximum candidate capacities of 5 and 10, comparing them with the single-candidate and default three-candidate configurations reported in the paper:

Maximum candidatesSuccess rate SR (%)Progress score PS (%)Tokens/group (k)
164.7149.56896.00
3 (default)71.4959.23812.59
571.9563.79915.22
1071.9557.911159.36

Increasing the capacity from 3 to 5 improves the progress score by 4.56 percentage points and increases the number of successfully completed tasks from 158/221 to 159/221, while increasing average token consumption by approximately 12.63%. Further increasing the capacity to 10 leaves the final success rate unchanged, reduces the progress score, and increases token consumption by approximately 42.67% relative to the default configuration. Thus, the default capacity is not optimal across all metrics, but a larger capacity both retains potentially useful early candidates and increases the burden of reasoning over outdated or less relevant candidates.

We thank the reviewer for suggesting baseline comparisons across task lengths. Using the same grouping as Figure 3, we report the results for the MAGE baseline and the related method BeliefMem:

Method≤6 stages (79 groups) SR (%)7–8 stages (90 groups) SR (%)≥9 stages (52 groups) SR (%)
MAGE59.4965.5669.23
BeliefMem65.8247.7873.08
BranchMem64.5671.1182.69

BranchMem outperforms MAGE by 5.07, 5.55, and 13.46 percentage points on short, medium, and long task groups, respectively, showing a larger relative gain on long task groups in this evaluation. Compared with BeliefMem, BranchMem scores 1.26 percentage points lower on short task groups but 23.33 and 9.61 percentage points higher on medium and long task groups, respectively. These results support the effectiveness of BranchMem on medium and long task groups.

Longer task groups can provide more intermediate clues and opportunities to verify candidates, helping the agent resolve uncertainty before the final question. Retaining and integrating this accumulated evidence can therefore make the final answer easier to identify.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.