PaperlayerView exact revision on arXiv

Source-linked AI summary

Traverse: Learning When to Remember, Reset, and Redirect for Long-Horizon Web Search

Jingyuan Ma, Lynx Aster, He Zhang, Siyao Song, Weijie Yuan, Zhe Zhang, Kai Jia, Zhifang Sui

arXiv:2609.37082v2cs.CL

TL;DR

Long-horizon search agents can accumulate misleading context that makes early mistakes persist, while existing context-management methods leave answer correctness checking relatively overlooked. Traverse combines rubric-guided search, agent-managed memory, and independent verification, and trains memory behavior by optimizing only the final segment after context management. The authors report 72.83 on BrowseComp for Traverse-35B and performance across search tasks, including transfer to financial and e-commerce search.

  • Problem

    Long-horizon search agents can accumulate noisy or misleading evidence that perpetuates early errors, while prior context-management methods largely focus on maintaining search state rather than checking answer correctness.

    Source: §1 · p. 1

  • Method

    Traverse combines Rubric–Answer–Verify search with agent-triggered memory tools and an RL strategy that optimizes only the final segment after context management.

    Source: §1 · p. 2, §2.2 · p. 3

  • Results

    72.83 on BrowseComp; Traverse-35B outperforms comparable open-source systems and reports competitive performance across search benchmarks with transfer to financial and e-commerce tasks.

    Source: §1 · p. 2, §4.2 · pp. 6–7, §6 · p. 10

  • Takeaways & Limitations

    Ablations validate agent-controlled context compression and final-segment-only RL, and report that agent-controlled compression outperforms automatic compaction.

    Source: §1 · p. 2, §4.3 · p. 9, §6 · p. 10

Abstract

from arXiv · show

Long-horizon information-seeking agents often accumulate noisy or misleading context, causing early mistakes to persist and making recovery increasingly difficult. We introduce an autonomous search harness in which the agent manages its own search process through three states: Rubric, Answer, and Verify. The agent first defines criteria for a valid answer, searches under these criteria, and then independently verifies the result before deciding whether to terminate or continue searching. It is further equipped with a Seal Memory tool that enables active context management. Training this behavior with reinforcement learning, however, can induce Seal Collapse, resulting in unstable training and preventing the agent from reliably learning when and how to use its memory tools. We solve this with a simple strategy that trains only the final segment after context management. Our 35B model achieves 72.83 on BrowseComp, outperforming comparable open-source systems, and consistently improves over the base model across BrowseComp-ZH, xbench, DeepSearchQA, WideSearch, financial investigation, and product search. Ablations show that autonomous compression outperforms automatic compaction and validate our RL design.

1 INTRODUCTION

Long-horizon search agents can accumulate misleading context that perpetuates early errors, while existing context-management work has largely emphasized maintaining search state rather than checking answer correctness. Traverse combines rubric-guided search, agent-managed memory, and independent verification, with a final-segment-only RL strategy to address Seal Collapse.

1 INTRODUCTION

  • Long-horizon search accumulates noisy or misleading evidence that can bias later decisions, repeat unproductive paths, and make recovery increasingly difficult.Prior context-management approaches summarize histories or reconstruct research state, but the paper identifies answer verification as an overlooked capability.Source: §1 · pp. 1–2
  • Traverse lets agents define answer criteria, search under them, manage context with Seal Memory, and independently verify whether to stop or resume searching.The paper reports Seal Collapse under all-segment RL and proposes optimizing only the final segment after context management.Source: §1 · p. 2
  • 72.83 on BrowseComp; Traverse-35B outperforms comparable open-source systems and reports gains across search benchmarks and transfer to finance and e-commerce tasks.The paper also reports improvements over the base model on BrowseComp-ZH and WideSearch.Source: §1 · p. 2

2 METHOD

Traverse structures long-horizon search as an iterative Rubric–Answer–Verify process and gives the agent control over context compression and answer verification. The agent may reset context to preserve useful information, then verify against the rubric and resume evidence-seeking if needed.

2.1 OVERVIEW

  • The overview combines rubric-guided exploration, autonomous context management, and self-verification in an iterative search workflow.The agent constructs criteria before searching, then evaluates whether to answer or continue after verification.Source: §2.1 · pp. 2–3, Figure 1 · p. 3

2.2 SELF-CONTEXT MANAGEMENT

  • Seal Memory lets the agent choose when to compress context and what information to preserve, while Read Memory retrieves finer-grained stored details.The agent is informed of token usage after tool calls, and compaction resets context for the next segment.Source: §2.2 · p. 3

2.3 DEEP RESEARCH STATE MACHINE

  • The Rubric state defines answer criteria, Answer gathers web evidence under them, and Verify independently checks the candidate and either passes it or redirects search.The agent can return to Answer with verifier feedback and unmet criteria, repeating the cycle until it submits an answer.Source: §2.3 · p. 4

3 MODEL TRAINING

Traverse trains search behavior from curated teacher trajectories and uses turn-level masks to exclude undesirable supervision without discarding valid recovery behavior. For RL, it addresses noisy credit assignment and segment-induced trajectory reweighting by optimizing only the final segment after context compaction.

3.1 SUPERVISED FINE-TUNING

  • Teacher trajectories are filtered for tool-call and behavioral errors, with turn-level masks excluding undesirable assistant turns while retaining valid supervision for recovery.The training questions are synthesized from knowledge graphs and verified for solvability before teacher trajectories are collected.Source: §3.1 · pp. 4–5

3.2 SEAL GUIDED REINFORCEMENT LEARNING

  • Broadcasting a trajectory’s final reward across all segments weakens credit assignment and implicitly changes trajectory weights when compaction fragments a trajectory.A trajectory split into K segments contributes K samples, changing the objective’s normalization relative to uncompacted trajectories.Source: §3.2 · p. 5
  • Final-segment-only RL addresses noisy credit assignment and trajectory reweighting caused by broadcasting trajectory-level rewards across fragmented segments.The method optimizes only the final segment; this also couples the decision to continue searching through compaction with the decision to answer.Source: §3.2 · pp. 5–6
  • Final segments receive a less noisy learning signal because they are temporally closest to the trajectory-level reward.When a segment ends, the agent must answer or invoke Seal Memory; context overflow makes that segment final and failure is penalized.Source: §3.2 · pp. 5–6

4 EXPERIMENTS

Traverse-35B performs competitively across the search benchmarks and improves on financial and e-commerce evaluations. Ablations support final-segment RL and agent-controlled context compaction over the tested alternatives.

4.1 EXPERIMENT SETUP

  • Experiments use Qwen3.5-35B-A3B; RL is applied only to the Answer state, with Discard-All enabled for BrowseComp when context is exhausted.The context-reset fallback is described as orthogonal to Seal Memory and combinable with agent-triggered compression.Source: §4.1 · p. 6
  • Evaluation covers five search benchmarks—BrowseComp, BrowseComp-ZH, WideSearch, xbench, and DeepSearchQA—and generalization on GAIA, FinSearchComp, and ShoppingComp.The five search benchmarks cover deep information seeking, multilingual search, breadth-oriented retrieval, and multi-step evidence collection and synthesis.Source: §4.1 · p. 6

4.2 MAIN RESULTS

  • 72.83 on BrowseComp makes Traverse-35B comparable to FORT-Searcher; it trails slightly on BrowseComp-ZH and xbench, but leads search-specialized models on DeepSearchQA and WideSearch.Table 1 reports the five benchmark results.Source: §4.2 · p. 6, Table 1 · p. 7
  • 18.45 percentage points in GAIA accuracy, 19.70 points in FinSearchComp accuracy, and 0.1331 in ShoppingComp SoP are gains over the base model.The authors report gains on financial and e-commerce evaluations beyond the training distribution.Source: Table 2 · p. 7, §4.2 · p. 7

4.3 ABLATION STUDIES

  • 65.2 BC185 Avg@3 for final-segment RL exceeds SFT (60.4), standard all-segment RL (51.7), and 1/K_i-weighted all-segment RL (57.8).On WideSearch, final-segment RL scores 49.7/71.1 Row-F1/Item-F1, versus 46.3/66.2 for standard and 40.1/59.5 for weighted all-segment RL.Source: §4.3 · p. 7, Figure 2 · p. 8
  • Final-segment RL maintains stable accuracy, Seal usage, and search behavior, while standard all-segment RL collapses and weighted training shows degradation and repeated loops.The weighted variant's accuracy degrades around step 20; Seal usage surges around steps 25–30 alongside increasingly early Seal calls and repeated Search/LinkSummary loops.Source: §4.3 · pp. 7–8, Figure 3 · p. 8
  • RL improves BC185 by 4.8 points and WideSearch by 6.0 Row F1 and 7.9 Item F1, while requiring fewer search turns than SFT.These comparisons evaluate RL against SFT.Source: §4.3 · p. 8
  • Active Seal improves BC185 Avg@3 by 10.28 points over Auto Compaction, with consistent Pass@3 and Maj@3 gains.Median first Seal occurs at 67 turns and 67.5K tokens, versus 217 turns and 231.4K tokens for Auto Compaction; the table defines first-operation medians over trajectories containing a memory operation.Source: §4.3 · pp. 8–9, Table 3 · p. 9

5 RELATED WORK

The related work situates TRAVERSE among autonomous web-search agents and outcome-based reinforcement learning for search. It identifies long-horizon context and credit-assignment challenges that motivate its final-segment training approach.

5.1 WEB SEARCH AGENTS

  • TRAVERSE organizes search into RUBRIC, ANSWER, and VERIFY states for criteria formulation, evidence seeking, and answer revision based on verification.The framework is presented alongside prior agents that use query reformulation, webpage navigation, evidence aggregation, and answer synthesis.Source: §5.1 · p. 9

5.2 REINFORCEMENT LEARNING FOR LONG-HORIZON SEARCH AGENTS

  • Prior context methods summarize interaction histories or reconstruct evolving research states, while broader long-horizon work explores active memory curation and context folding.The passage frames these methods as primarily maintaining a useful search state.Source: §5.1 · p. 9, §5.2 · p. 9
  • Outcome-based reinforcement learning can teach search behavior without intermediate reasoning annotations, but long-horizon search adds context-budget and ambiguous-credit-assignment challenges.Earlier searches may include irrelevant retrievals, eliminated candidates, and abandoned directions.Source: §5.2 · p. 9
  • TRAVERSE uses autonomous SEAL MEMORY operations to set segment boundaries and applies the terminal learning signal only to the final segment.Earlier evidence remains available through sealed memory, while uncertain exploratory segments receive no direct gradient.Source: §5.2 · p. 9

6 CONCLUSION

TRAVERSE combines a RUBRIC–ANSWER–VERIFY search process with agent-controlled context management. Its training recipe supports strong BrowseComp performance and competitive results across other search settings.

6 CONCLUSION

  • TRAVERSE structures research through RUBRIC, ANSWER, and VERIFY states and lets the agent choose when to compress context and what information to preserve.Its Seal Memory Tool supports agent-managed context boundaries.Source: §6 · pp. 9–10
  • 72.83 on BrowseComp is achieved by TRAVERSE-35B, which also remains competitive across multilingual, broad-retrieval, and evidence-synthesis benchmarks and transfers to financial and e-commerce search.The conclusion reports that ablations show improved performance from final-segment training and that agent-triggered sealing outperforms fixed-threshold automatic compaction.Source: §6 · p. 10
  • The training recipe combines masked supervised fine-tuning on teacher trajectories with reinforcement learning that optimizes only the final segment after context compaction.The conclusion says this design avoids noisy credit assignment and trajectory reweighting associated with all-segment training, preventing observed Seal Collapse.Source: §6 · p. 10

A SEARCH TASK SYNTHESIS

The task-synthesis pipeline builds search questions by expanding knowledge-graph seed tasks with web evidence, controlling their complexity and clue specificity, and filtering for validity and difficulty.

A SEARCH TASK SYNTHESIS

  • The synthesis pipeline has four stages: seed-task initialization, structured formalization, Web-grounded expansion, and quality filtering.Its design is formalization-driven and inspired by WebShaper (Tao et al., 2025).Source: A SEARCH TASK SYNTHESIS · p. 16
  • Seed tasks begin with a target entity sampled from a knowledge graph and factual relations used to construct a simple question with a known answer.The target can be the entity or one of its attributes; remaining facts become initial constraints.Source: A SEARCH TASK SYNTHESIS · p. 16
  • The formal representation records the target, supporting relations, intermediate entities, and constraints, and seed tasks are retained only when the feasible answer set is the target alone.Each knowledge projection contains candidate entities satisfying its corresponding constraint.Source: A SEARCH TASK SYNTHESIS · p. 16
  • Layer-wise expansion replaces an expandable leaf constant with a variable constrained by a subproblem whose answer is that constant, requiring additional search while preserving the original target.Repeated expansion yields chained and branching structures with intermediate results needed for the final answer.Source: A SEARCH TASK SYNTHESIS · p. 16
  • Web-grounded expansion combines knowledge-graph relations with retrieved facts, prioritizes independent support, removes duplicate statements, and links facts to entities to reduce entity-matching errors.Descriptive web text can also supply new expansion anchors after candidate entities are extracted and linked.Source: A SEARCH TASK SYNTHESIS · p. 16
  • Task complexity varies through expansion depth, relation-chain length, branches, constraints, and composition patterns including chained retrieval, comparison, and temporal reasoning.Clue specificity is separately varied through truthful transformations such as converting exact dates to ranges or entity names to type-level descriptions.Source: A SEARCH TASK SYNTHESIS · pp. 16–17
  • Generated questions preserve factual constraints, mask the target, and include reference answers, formal representations, supporting relations, provenance, and transformation metadata.The natural-language question is verbalized from the expanded formal representation.Source: A SEARCH TASK SYNTHESIS · p. 17
  • Filtering checks structural consistency, web-evidence quality and entity correspondence, approximate answer uniqueness against alternatives, and empirical difficulty before tasks enter trajectory collection.Tool-free-solvable questions are removed, and attempt-based success estimates exclude consistently trivial or effectively unsolvable tasks to form a difficulty-balanced training set.Source: A SEARCH TASK SYNTHESIS · p. 17

B QUALITATIVE ANALYSIS OF AUTONOMOUS CONTEXT RECOVERY

The qualitative cases show the agent using Seal Memory to recover from unproductive searches by preserving useful evidence and failed hypotheses, then redirecting its search in refreshed context.

B QUALITATIVE ANALYSIS OF AUTONOMOUS CONTEXT RECOVERY

  • Table 4 presents two representative trajectories in which the model invokes Seal Memory without an external compaction trigger, preserves useful search state, and changes strategy in refreshed context.Source: B QUALITATIVE ANALYSIS OF AUTONOMOUS… · p. 17, Table 4 · p. 18
  • In the Polish-officer case, the model stores verified facts and rejected candidates with exclusion reasons, then uses those dead ends as constraints to identify Hipolit Łossowski.The correct birth year returned is 1881.Source: B QUALITATIVE ANALYSIS OF AUTONOMOUS… · p. 18
  • In the baseball-player case, the model records that a current-roster assumption failed, expands to former Rakuten players, corrects an entity-type error, and identifies Hiroaki Yamamoto.It also verifies the disputed weight condition after the reset.Source: B QUALITATIVE ANALYSIS OF AUTONOMOUS… · p. 18
  • The cases illustrate recovery beyond periodic compression: the model recognizes an unproductive state, creates a semantic boundary, preserves evidence and failed hypotheses, and redirects its search.The passage says a controlled comparison with automatic compaction provides complementary quantitative evidence for this recovery behavior.Source: B QUALITATIVE ANALYSIS OF AUTONOMOUS… · p. 18

C REWARD SHAPING AND CONTEXT-BUDGET RANDOMIZATION

The reward design combines answer correctness with resource, action, and efficiency signals. Context budgets vary across rollout groups while remaining matched within each group, encouraging the agent to choose when to seal based on progress and remaining budget.

C REWARD SHAPING AND CONTEXT-BUDGET RANDOMIZATION

  • Answer correctness is the primary trajectory-level signal, supplemented by resource penalties and action-local signals on the final segment.Both positive and negative group-relative advantages are retained; when correctness rewards are identical, ordinary auxiliary advantages are suppressed while resource penalties and deterministic constraints remain active.Source: C REWARD SHAPING AND CONTEXT-BUDGET… · pp. 18–19
  • Turn penalties begin in the final 5% of the turn budget, while context penalties rise near the active segment’s budget limit.Generation terminates at the hard context limit.Source: C REWARD SHAPING AND CONTEXT-BUDGET… · pp. 18–19
  • Format errors incur penalties on the assistant turn that produces them, and deterministic action violations cap token-level advantages.Violations include fabricated tool names or arguments, repeated identical searches, and sealing when the answer is already ready.Source: C REWARD SHAPING AND CONTEXT-BUDGET… · p. 19
  • Among correct trajectories for the same question, more efficient tool use earns a width-aware bonus assigned to turns that issue parallel calls.Efficiency is ranked by tool-use cost.Source: C REWARD SHAPING AND CONTEXT-BUDGET… · p. 19
  • Context budgets vary independently across rollout groups but remain shared within each question’s group, discouraging a fixed context-length trigger for sealing.After a seal, the new segment starts from the task specification and sealed memory under the same group budget.Source: C REWARD SHAPING AND CONTEXT-BUDGET… · p. 19

D BROWSECOMP-LITE: A LIGHTWEIGHT EVALUATION SUBSET

The authors construct BROWSECOMP-LITE-185 to make model development and ablations less costly than evaluating the full BrowseComp benchmark. Its size is calibrated against historical full-set results and checked against specified deviation tolerances.

D BROWSECOMP-LITE: A LIGHTWEIGHT EVALUATION SUBSET

  • BrowseComp has 1,266 questions; BROWSECOMP-LITE-185 is intended to approximate full-set performance while reducing evaluation cost.The subset supports more efficient model development and ablation studies.Source: D BROWSECOMP-LITE: A LIGHTWEIGHT… · p. 19
  • The subset size was calibrated by comparing candidate subsets with corresponding full-benchmark accuracies across historical evaluation runs.The candidate subset is formed from the first K questions after a fixed random permutation; calibration used five Best-of-1 and four Best-of-5 runs.Source: D BROWSECOMP-LITE: A LIGHTWEIGHT… · pp. 19–20
  • 185 questions limit observed subset-to-full-set deviation to 3 percentage points for Best-of-1 and 5 percentage points for Best-of-5.The selected subset is named BROWSECOMP-LITE-185.Source: D BROWSECOMP-LITE: A LIGHTWEIGHT… · p. 20, Table 5 · p. 20

E QUALITATIVE COMPARISON OF ACTIVE SEALING AND AUTOMATIC COMPACTION

The appendix contrasts active SEAL’s agent-recognized state transitions with context-length-triggered automatic compaction and specifies the harness’s search, summarization, and memory interfaces. The memory tools expose structured checkpoints and bounded retrieval of prior context.

E QUALITATIVE COMPARISON OF ACTIVE SEALING AND AUTOMATIC COMPACTION

  • Active SEAL can transition when the agent recognizes semantic stagnation, whereas automatic compaction responds to context length and may preserve an entrenched search branch.Figure 4’s anonymized cases illustrate multi-constraint entity joining, rare-constraint prioritization, and entity-centered redirection while omitting task-specific details.Source: Figure 4 · p. 21, E QUALITATIVE COMPARISON OF ACTIVE… · p. 22

F TOOL INTERFACES

  • The harness exposes four function-calling interfaces, while backend choices and execution policies are fixed by the experimental configuration rather than model-visible arguments.Top-level arguments are strictly validated, and runtime budget annotations are added after tool execution.Source: F TOOL INTERFACES · p. 22

F.1.1 WEB SEARCH: SEARCH AP I

  • The search interface accepts a free-form query and optional result count; the evaluator selects the backend, and successful results retain title, URL, description, and rank.The backend choice keeps the model-facing interface consistent across evaluation settings.Source: §F.1.1 · p. 22

F.1.2 PAGE SUMMARY: LINK SUM M A R Y T O O L

  • The page-summary tool reads one or more URLs conditioned on the agent’s question and returns a synthesized answer with reader status.The implementation may retry transient failures or use a reader-plus-LLM fallback transparently to the answer agent.Source: §F.1.2 · pp. 22–23

F.2.1 ACTIVE CHECKPOINT: SEAL M E M O R Y T O O L

  • Seal Memory creates a structured checkpoint for verified, conflicting, and partial facts, visited paths, dead ends, unexplored leads, and the next action.Only the next-step plan and task progress are mandatory top-level fields, so early checkpoints can remain partial.Source: §F.2.1 · pp. 23–24

F.2.2 CHECKPOINT RETRIEVAL: R E A D M E M O R Y T O O L

  • Read Memory retrieves the most recent checkpoint, returning compact structured state by default and bounded conversation history or a structured summary when requested.The model receives only the identifier of the latest checkpoint after a context transition.Source: §F.2.2 · p. 25

F.3 JUDGE MODELS AND EVALUATION PROTOCOLS

This section specifies the judge models and scoring procedures used across the evaluated benchmarks. It also describes benchmark-specific answer matching and the time-stable financial-search subset and product-search metrics.

F.3 JUDGE MODELS AND EVALUATION PROTOCOLS

  • The evaluation protocols pair benchmarks with judge models and scoring procedures, including DeepSeek-V4-Flash for BC, BC-ZH, GAIA, and xbench.DeepSearchQA and WideSearch follow their official evaluation implementations and prescribed judges and scoring procedures.Source: §F.3 · pp. 25–26, Table 6 · p. 26
  • FinSearchComp evaluation uses 391 time-stable questions, excluding 244 time-sensitive items tied to the dataset’s 2025 snapshot.For ShoppingComp, VPR measures valid product-oriented responses and SoP averages the proportion of user-requirement rubrics satisfied.Source: §F.3 · p. 26
  • BC and BC-ZH use a binary judge decision with the original question, reference answer, and model response language preserved.Answer matching allows numeric and semantic equivalence, reordered matching lists, and equivalent date formats.Source: §F.3 · p. 26
  • WideSearch outputs are parsed and normalized under benchmark rules before GPT-4.1 performs semantic primary-key alignment and grades columns requiring an LLM.The resulting score is Item-F1 under the benchmark’s official aggregation procedure.Source: §F.3 · p. 27
Loading 2609.37082v2…