PaperlayerView exact revision on arXiv

Source-linked AI summary

TreeSeeker: Tree-Structured Trial, Error, and Return in Deep Search

Zhuofan Shi, Mingzhe Ma, Lu Wang, Fangkai Yang, Pu Zhao, Yiming Guan, Youling Huang, Wei Zhang, Qingwei Lin, Dongmei Zhang, Saravan Rajmohan

arXiv:2606.11662v1cs.AI

TL;DR

Deep search agents must decide when to continue a promising direction, explore alternatives, or return from failed paths. TreeSeeker uses branch-and-return search with textual UCB control, outperforming evaluated open-source baselines across three deep-search benchmarks.

  • Problem

    Deep search requires deciding whether to continue a useful direction, try a new one, or return from a failed path as the search horizon grows.

  • Method

    TreeSeeker organizes sub-goal search as tree-structured branch-and-return exploration, with TreeSearch selecting exploit, explore, or prune operations using value, uncertainty, and risk.

  • Results

    56.3 on XBench-DS, 47.0 on BrowseComp, and 43.0 on BrowseComp-ZH gave TreeSeeker the best performance among evaluated open-source baselines.

  • Takeaways & Limitations

    Explicit branch-and-return control is a valuable complement to stronger reasoning and tool execution in long-horizon deep search.

  • Takeaways & Limitations

    Evaluation is limited to text-based deep-search benchmarks and does not cover multimodal settings because TreeSeeker lacks multimodal tool integration.

Abstract

from arXiv · show

Deep search requires agents to answer complex questions through multi-step web search, browsing, evidence comparison, and synthesis. A central challenge is deciding how to search when several directions look plausible but only some will later lead to reliable evidence. If an agent greedily follows the current best-looking direction, it may keep extending a weak continuation. If it explores without discipline, it may waste budget on disconnected trials. We propose TreeSeeker, an inference-time framework for controlled trial-and-error in deep search. TreeSeeker organizes search as branch-and-return search over tree-structured states, where each branch is a tentative direction for a sub-goal. At each round, TreeSearch reads all sub-goal trees, identifies active goals, and uses textual UCB signals of value, uncertainty, and risk to select among exploiting a promising branch, exploring an uncertain alternative, or pruning an unproductive continuation and returning to an earlier branch point. TreeMem supports this control loop by keeping evidence, uncertainty, conflicts, progress, and failure cues attached to the branches that produced them, so trial outcomes can guide later decisions. Experiments on XBench-DeepSearch, BrowseComp, and BrowseComp-ZH show that TreeSeeker consistently outperforms strong open-source baselines, suggesting that explicit branch-and-return control complements stronger reasoning and tool execution.

1 Introduction

Deep search requires multi-step planning, browsing, evidence inspection, conflict resolution, and synthesis, making controlled trial-and-error essential under limited budgets. TreeSeeker addresses this challenge with branch-and-return search, textual UCB control, and branch-linked memory, outperforming evaluated open-source baselines across three benchmarks.

  • Motivation: Deep search combines subgoal planning, querying, browsing, evidence inspection, conflict resolution, and synthesis across long-horizon interactions.As the search horizon grows, deciding when to continue or change direction becomes a central challenge.
  • Motivation: Greedy continuation can extend weak directions, while undisciplined alternatives waste budget; effective search must test uncertainty and return from failures.Early directions may later produce weak, conflicting, or incomplete evidence.
  • Method: TreeSeeker organizes each sub-goal as a tree of search-direction branches and selects one operation for every dependency-ready active goal in a single pass.Branches can represent queries, source families, or hypotheses, while branch-and-return operations support continuing, exploring, pruning, and returning.
  • Results: 56.3 on XBench-DS, 47.0 on BrowseComp, and 43.0 on BrowseComp-ZH were achieved by TreeSeeker, the best among evaluated open-source baselines.On XBench-DS, removing textual UCB signals reduced performance by 4.3 points, while disabling branch-and-return operations reduced it by 8.3 points.
  • Method: TreeSearch applies operation-level textual UCB using value, uncertainty, and risk, while TreeMem attaches evidence, conflicts, progress, and failure cues to their originating branches.These components let prior trial outcomes guide later search decisions.

2 Related Work

Related deep-search agents largely follow a single evolving trajectory, while context-management methods reconstruct or compress history into one state. TreeSeeker instead preserves semantic branches and applies textual value, uncertainty, and risk signals to decide which branches to deepen, explore, prune, or revisit.

  • ReAct and subsequent systems strengthen a sequential reason-act-observe trajectory through workspace reconstruction, improved web reasoning, and longer-horizon interaction scaling.
  • Summarization and workspace-reconstruction methods address context bottlenecks but organize research history as a single evolving state.Examples include ReSum, IterResearch, MemAgent, and AgentFold.
  • TreeSeeker attaches summarized evidence to persistent semantic branches, preserving which attempts helped or failed and which alternatives remain worth pursuing.This branch-structured memory contrasts with mixing tentative directions into a flat context or reconstructed workspace.
  • Unlike tree-search methods over discrete actions with scalar rewards or retrieval scores, deep search compares partially synthesized evidence states containing conflicts, unresolved constraints, and failure cues.The cited methods include LATS, Plan-MCTS, and ExACT.
  • TreeSeeker extends UCB intuition with textual estimates of branch value, residual uncertainty, and search risk, coupled to pruning and return to earlier branch points.Its setting is open-ended web-search branches whose hypotheses are embedded in semantic evidence states.

3 Method

TreeSeeker structures deep search as branch-and-return over sub-goal search trees. TreeSearch selects operations for active goals, while TreeMem preserves branch-local evidence and failure-aware state to support comparison, continuation, exploration, pruning, and recovery.

  • Tree-structured search state: TreeSeeker decomposes a root question into sub-goals, each represented by a search tree whose branches encode candidate queries, sources, or hypotheses.TreeMem stores the goal state and current result candidates at each sub-goal’s root, with first-level nodes representing candidate solving paths.
  • TreeSearch controller: TreeSearch reads all sub-goal trees, identifies dependency-ready unresolved goals, and emits one EXPLORE, EXPLOIT, or PRUNE operation for each active goal.The operation is the TreeSearch decision, whereas the action is the tool action used to execute it.
  • TreeMem memory: TreeMem maintains compact branch-local records of evidence, uncertainty, conflicts, progress, and failure cues so TreeSearch can compare directions and recognize useful or failed attempts.Separating records by search direction supports decisions to explore, exploit, or prune.
  • Branch-and-return loop: After tool execution or pruning, TreeMem updates active branch states, enabling the agent to continue useful paths, test alternatives, and recover from unhelpful ones.This update loop turns trial-and-error into branch-and-return search.
  • Textual UCB: TreeSearch applies textual UCB at the operation level, comparing EXPLOIT, EXPLORE, and PRUNE instead of ranking every path-action pair in a large combinatorial space.This control principle avoids both greedily extending the current best-looking branch and undisciplined exploration.

TreeMem𝑻𝒊

TreeMem stores structured branch states that preserve evidence, uncertainty, progress, failure cues, and recent tool traces for TreeSearch. This enables textual-UCB control over EXPLORE, EXPLOIT, and PRUNE operations, including risk-aware return to earlier branch points.

  • Each TreeMem node stores evidence, uncertainty, progress, and failure cues, while deeper nodes retain recent tool calls and returned observations.
  • TreeMem summarizes long-term history into goal and branch states, retains only recent raw interactions, and compresses pruned continuations into failure cues.This structured memory lets TreeSearch compare branches without replaying the full interaction history.
  • At each round, TreeSearch selects dependency-ready unresolved goals, assigns one operation per active tree, and updates selected trees independently while others remain unchanged.EXPLORE and EXPLOIT execute branch-tagged tool actions whose observations are written back to TreeMem; PRUNE records a failure cue.
  • Textual UCB compares EXPLOIT, EXPLORE, and PRUNE using ordinal signals for value, uncertainty, and risk over semantically rich branch states.Value measures expected progress, uncertainty measures expected information gain, and risk measures the chance of committing budget to a misleading continuation.
  • EXPLORE opens an uncertain alternative, EXPLOIT extends a promising branch, and PRUNE stops a weak continuation while returning to an earlier branch point.PRUNE preserves a compact failure cue and keeps the return point available for later revision.

4 Experiments

TreeSeeker is evaluated on three deep-search benchmarks against open-source and proprietary systems, using gpt-5.2 as the default backbone and an additional shared gpt-4.1 setting. It achieves the strongest reported performance, with ablations and operation frequencies showing contributions from textual UCB, branch-and-return control, and TreeMem’s leaf trace.

  • Benchmarks: TreeSeeker is evaluated on XBench-DeepSearch, BrowseComp, and BrowseComp-ZH, including 100-instance sampled test subsets for each BrowseComp benchmark.The benchmarks cover long-horizon web search, compositional browsing, and Chinese-language browsing.
  • Main results: 56.3 on XBench-DS; TreeSeeker surpasses Flash-Searcher, IterResearch, and Tongyi-DeepSearch by 5.6, 12.3, and 11.3 points, respectively.It also reaches 47.0 on BrowseComp and 43.0 on BrowseComp-ZH, ranking first among evaluated open-source baselines.
  • Main results: 1.7, 2.0, and 2.6 points; under a shared gpt-4.1 backend, TreeSeeker remains ahead of Flash-Searcher across the three benchmarks.The default backbone is gpt-5.2, with both systems additionally evaluated using gpt-4.1 under the same search and browsing tools.
  • Search dynamics: Around action step 8, TreeSeeker’s cumulative success trajectory diverges from Flash-Searcher and remains consistently higher through the growth region and near the budget limit.The reported curves use shared XBench-DS queries and per-step means over three runs with min–max envelopes; the difference is attributed to evidence-driven branch selection.
  • Ablations: −8.3; disabling EXPLORE and PRUNE causes the largest XBench-DS drop, from 56.3 to 48.0, while removing Textual UCB and the retained leaf trace yields 52.0 and 51.3.The ablations show complementary contributions from textual UCB scoring, branch-and-return operations, and TreeMem’s retained latest raw leaf trace.
  • Branch operations: 51.39% vs. 43.45%; with textual UCB, EXPLOIT and EXPLORE remain relatively balanced while PRUNE occurs in 5.17% of operations.Without textual UCB, EXPLORE rises to 61.08%, alongside fewer EXPLOIT and PRUNE decisions.

5 Conclusion

TreeSeeker structures deep search as branch-and-return search over tree-structured states, maintaining multiple tentative directions and allocating budget across them. Experiments on XBench-DeepSearch, BrowseComp, and BrowseComp-ZH show consistent gains over strong open-source baselines.

  • 5 Conclusion: TreeSeeker structures deep search as branch-and-return search over tree-structured states.It treats multiple tentative search directions as explicit decision objects and repeatedly allocates budget across them.
  • 5 Conclusion: TreeSeeker consistently outperforms strong open-source baselines on XBench-DeepSearch, BrowseComp, and BrowseComp-ZH.The results suggest that explicit branch-and-return control complements stronger reasoning and tool execution in long-horizon deep search.

Limitations

TreeSeeker is limited by its text-only evaluation scope, added inference overhead, and dependence on potentially unreliable web evidence. These constraints leave multimodal extension, deployment efficiency, and high-stakes verification as important considerations.

  • Scope: TreeSeeker is evaluated only on text-based deep search benchmarks and does not integrate multimodal tools for image or video understanding.Extending the framework to multimodal evidence sources is left for future work.
  • Efficiency: Branch-and-return control adds inference cost through controller decisions and periodic branch-local memory summaries.This overhead may concern latency- or budget-sensitive deployments, despite remaining below Flash-Searcher in total tokens and tool calls.
  • Evidence reliability: TreeSeeker depends on web search and browsing results that may be noisy, incomplete, outdated, or biased.TreeSearch and TreeMem improve evidence comparison and pruning but cannot guarantee source reliability or fully resolve conflicts; high-stakes outputs require trusted-source checks or expert review.

A TreeSeeker Inference Procedure and Implementation Details

TreeSeeker begins by decomposing the query into dependency-linked sub-goals with alternative candidate paths, then iteratively selects and executes branch operations through a TreeSearch–TreeMem loop. Periodic state consolidation preserves evidence, uncertainty, progress, conflicts, and failure cues for termination and final answer generation.

  • Planning and TreeMem initialization: The planning agent decomposes root query q0 into sub-goals G, constructs dependency DAG DG, and proposes candidate paths Pi for each goal gi.The DAG determines dependency readiness, while candidate paths define alternative search directions.
  • Planning and TreeMem initialization: TreeMem initializes a goal-local tree per goal, representing candidate paths as major branches while separating summarized states M from recent records and retained leaf traces R.This structure attaches later decisions to goal- and branch-specific state rather than a flat history.
  • Frontier construction and textual UCB decision: At each iteration, TreeSearch builds a frontier of unresolved dependency-ready goals and binds each candidate operation—EXPLOIT, EXPLORE, or PRUNE—to concrete branch targets.The frontier combines summarized TreeMem states, the recent-record overlay, and the dependency DAG.
  • Decision execution and leaf-trace update: EXPLORE and EXPLOIT execute branch actions with web search, page crawling, or Python tools, whereas PRUNE requires no external browsing and updates the selected path’s leaf trace.Action-observation pairs enter recent records, and the latest leaf trace replaces the previous continuation anchor.
  • Periodic summary updates: H = 8 decision rounds is the summary interval, consolidating operation records into branch states containing evidence, provenance, candidate answers, constraints, progress, conflicts, and failure cues.Older unsummarized records may be compressed or removed, while each active path’s latest leaf trace is retained.
  • Termination and answer generation: The loop stops when ANSWERFOUND identifies sufficient evidence or the global step budget is exhausted, after which remaining records are summarized and the answer is generated from updated TreeMem.Final synthesis includes candidate answers, supporting evidence, confidence signals, and applicable unresolved conflict markers.

B Experimental Details

TreeSeeker is evaluated on three long-horizon, multi-source search benchmarks spanning English and Chinese web environments. The experiments compare it with open-source and proprietary systems while aligning backend models and tool interfaces where possible to isolate search-control effects.

  • Benchmarks: The evaluation uses XBench-DeepSearch, BrowseComp, and BrowseComp-ZH, covering complex multi-step search, heterogeneous evidence integration, and answer synthesis.BrowseComp and BrowseComp-ZH each use a randomly sampled 100-instance test subset due to resource constraints.
  • Benchmarks: BrowseComp-ZH extends the evaluation to Chinese web environments, testing non-English browsing, cross-page reasoning, and culturally or linguistically specific evidence aggregation.The benchmark is included to assess crosslingual and cross-cultural generalization beyond English web search.
  • Baselines: Comparisons include open-source deep-search agents, reported open-source model systems, and proprietary products such as OpenAI DeepResearch and Gemini DeepResearch.Flash-Searcher is identified as the most direct structural baseline for testing explicit branch-level control against fixed scheduling.
  • Implementation Details: For reimplemented systems, backend models and tool interfaces are kept aligned when the original design permits, making search-control frameworks the main intended source of differences.The default backend is gpt-5.2-20251211, while Tongyi DeepSearch uses its released Tongyi-A30B-A3B variant.

C Cost Analysis

TreeSeeker accepts additional controller and branch-memory costs to enable structured trial-and-error, while keeping overall cost practical. Relative to Flash-Searcher, it uses fewer tokens and tool calls while achieving higher XBench-DS performance, though it remains costlier than lighter baselines.

  • Efficiency tradeoff: TreeSearch adds a controller decision before execution, while TreeMem periodically summarizes branch-local states for comparing, continuing, or pruning directions.This additional control cost supports structured trial-and-error rather than minimizing token usage alone.
  • Efficiency tradeoff: 1415.8K total tokens and 71.92 tool calls reduce Flash-Searcher’s 1474.6K and 90.20, while XBench-DS performance rises from 50.7 to 56.3.These results indicate that TreeSeeker’s improvement does not simply come from scaling inference cost beyond existing strong systems.
  • Efficiency tradeoff: TreeSeeker remains more expensive than lighter baselines such as IterResearch and Tongyi-DeepResearch, and exceeds LATS in total tokens and tool calls.The supplied passage establishes these comparisons but does not provide the corresponding LATS values.

D Operation Decision Analysis Details

TreeSeeker’s textual UCB balances exploitation and exploration rather than simply triggering more exploration, while also enabling sparse, risk-aware pruning of confidently unproductive branches. Without these value–uncertainty–risk signals, the controller explores more, exploits less, and broadens the search frontier instead of consolidating evidence chains.

  • Operation balance: With textual UCB, TreeSeeker keeps EXPLOIT and EXPLORE at comparable levels, continuing promising branches while opening alternatives.This balances evidence consolidation against premature commitment.
  • Operation balance: Without textual UCB, the controller explores more frequently and exploits less, broadening the search frontier instead of committing budget to existing evidence chains.The passage attributes this behavior to lacking explicit value–uncertainty–risk signals.
  • Risk-aware pruning: 5.17% PRUNE indicates sparse, risk-aware correction that redirects budget from continuations judged confidently unproductive without aggressively discarding branches.The full controller prunes more often than w/o Textual UCB, but pruning remains sparse.

E Prompts

The prompts initialize a DAG-structured plan by decomposing a root question into dependent goals with alternative execution paths, then guide TreeSearch in selecting goals, paths, and decision modes from TreeMem. They combine parallel execution of independent goals with textual UCB-style judgments over exploit, explore, backtrack, and finish actions.

  • E.1 Initial Planning: Paths are fallback alternatives: completing any one successful path completes its goal, making the remaining paths unnecessary.The output format requires every goal to list dependencies, paths, and success criteria.
  • E.1 Initial Planning: Independent goals execute in parallel, while dependent goals wait for all required outputs; dependencies are reserved for synthesis, comparison, or calculation goals that consume other goals’ results.The design minimizes dependency depth, avoids cycles, and permits parallel information gathering.
  • E.2 Textual UCB Decision: TreeSearch uses the plan, execution history, and tree-structured memory to choose which goals to advance and which paths to use.The implementation names the reset operation “backtrack,” corresponding to the main text’s PRUNE operation.
  • E.2 Textual UCB Decision: Backtracking does not invalidate a direction: it replaces prior context with a concise warning so the agent can later reselect and re-explore the path.The abandonment summary should identify prior traps without discouraging future retries.
  • E.2 Textual UCB Decision: The finished mode stops search once all goals have enough evidence to answer the original task, because further searching wastes budget and risks introducing noise.Perfect or exhaustive evidence is unnecessary when the key constraints are supported.
  • E.2 Textual UCB Decision: For each advanced goal, the controller binds candidate actions, scores value, risk, and uncertainty as low, mid, or high, then selects exactly one mode and commits its bound path.If the task is already answerable from collected evidence, the finished short-circuit takes precedence over per-goal scoring.

F Case Study

The case studies show TreeSeeker using pruning and branch return to redirect noisy searches, and exploration–exploitation control to avoid premature commitment among partial candidate matches. These controls enable targeted verification and stronger evidence chains in both tasks.

  • Case 1: Pruning Redirects a Noisy Role-Attribute Search: In Case 1, TreeSeeker prunes noisy alcoholic-role paths after they fail to produce a verifiable work–role evidence chain.Paths 3.1 and 3.3 are pruned because semantic matches remain noisy and do not verify the narrowed candidate.
  • Case 1: Pruning Redirects a Noisy Role-Attribute Search: It returns to an earlier branch point and reformulates Goal 3 as candidate-conditioned reverse verification using Li Jianyi, You Yi Zhong Du Yao, and the alcoholic-father setting.This replaces forward searches over abstract role labels with a concrete candidate–work verification query.
  • Case 1: Pruning Redirects a Noisy Role-Attribute Search: The redirected search closes the stagnant alcoholic-role constraint and correctly answers Li Jianyi without exhausting the budget on low-quality semantic paths.Goals 1 and 4 had already narrowed the candidate, enabling targeted verification.
  • Case 2: Exploration and Exploitation Avoid Premature Candidate Locking: In Case 2, TreeSeeker explores multiple folk-activity candidates before exploiting high-value evidence to verify the discriminative constraints for Nuo Opera.Exploration keeps Tunpu Dixi, Paohan Chuan, and Nuo Opera in comparison rather than committing to the first plausible match.
  • Case 2: Exploration and Exploitation Avoid Premature Candidate Locking: The resulting evidence chain combines official multi-region heritage records with semantic evidence for Spring Festival performance and exaggerated ritual-theatrical style.Nuo Opera is selected after verifying constraints that distinguish it from remaining alternatives, not from a single keyword hit.
Loading 2606.11662v1…