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

A dominant paradigm in deep-search agent design is the sequential reason-act-observe loop, exemplified by ReAct (Yao et al., 2023), where the agent maintains a single evolving trajectory of plans, tool calls, and observations. IterResearch (Chen et al., 2026a), WebSailor (Li et al., 2025a), WebDancer (Wu et al., 2025), and WebtThinker (Li et al., 2025c) strengthen this paradigm through workspace reconstruction, improved web reasoning, or long-horizon training and interaction scaling. Flash-Searcher (Qin et al., 2026) and ParallelResearch (Nie et al., 2026) further introduce DAG-structured subgoals and parallel execution to improve throughput and coverage. Search More, Think Less (Chen et al., 2026c) takes a complementary direction by replacing deep per-step reasoning with wider evidence acquisition to improve efficiency and generalization. However, these systems still do not provide evidence-driven control for reallocating budget across alternative paths within a goal.

This limitation matters under early-stage uncertainty, a single-path or fixed-schedule agent may continue building on weak evidence rather than redirecting budget based on what has been learned mid-search. TreeSeeker differs by treating each candidate path as a persistent semantic branch state and using TreeSearch to decide which branch to deepen, explore, or prune based on accumulated evidence and failure signals.

Long-horizon agents also face a context bottleneck, motivating summarization and workspace-reconstruction methods. ReSum (Wu et al., 2026) periodically compresses exploration history, IterResearch (Chen et al., 2026a) reconstructs an evolving workspace across research rounds, MemAgent (Yu et al., 2026) rebuilds task state on demand, and AgentFold (Ye et al., 2025) condenses and reorganizes search history to prevent context overload.

These methods address the context bottleneck effectively, but they organize history as a single evolving state. When multiple tentative search directions are mixed into a flat context or a single reconstructed workspace, it becomes difficult to distinguish which attempt was useful, which failed, and which alternative branches remain worth pursuing. TreeSeeker uses a different role for summarization: rather than compressing history into one state, TreeMem keeps summarized evidence attached to the branch that produced it. The resulting branch-local states are not memory devices for continued single-path reasoning, but decision objects that TreeSearch can compare, deepen, or prune.

The explore–exploit tradeoff formalized by UCB (Auer et al., 2002) provides a principled basis for allocating effort among competing alternatives under uncertainty. In the language agent setting, tree-search methods have applied this intuition to reasoning and planning: Language Agent Tree Search (LATS) (Zhou et al., 2024) unifies reasoning, acting, and planning in an MCTS-style framework, and follow-up works such as Plan-MCTS (Zhang et al., 2026b), ExACT (Yu et al., 2025), and uncertainty-aware web-agent frameworks (Zhang et al., 2026a) apply tree-based exploration to web navigation or interactive decision settings. In retrieval-augmented generation, MCTS-RAG (Hu et al., 2025) structures retrieval as tree search, Air-RAG (Feng et al., 2025) interleaves retrieval with reasoning via expansion and simulation, and ReARTeR (Sun et al., 2025) uses MCTS-guided process rewards for preference optimization.

These methods operate over well-defined action spaces such as query reformulations, document selections, or reasoning steps, where branch quality can be estimated with scalar rollout rewards or retrieval scores. Deep search presents a different challenge: the objects being compared are partially synthesized semantic evidence states, not discrete actions, and quality signals include partial answers, source conflicts, unresolved constraints, and failure cues rather than numeric rewards. TreeSeeker extends the UCB intuition to this setting through a textual scoring rule that estimates branch value, residual uncertainty, and search risk from semantic branch states, and couples it with a return mechanism that prunes unproductive continuations and redirects search to earlier branch points. This is broadly related to test-time hypothesis exploration in inductive reasoning (Chen et al., 2026b), but our setting differs in that hypotheses are embedded in open-ended web-search branches whose evidence must be actively gathered and revised.

We present TreeSeeker, an inference-time framework that organizes deep search as branch-and-return search. As shown in Figure 1, given a root question, TreeSeeker first decomposes it into sub-goals, since complex tasks often require resolving multiple pieces of evidence before synthesizing the final answer. Each sub-goal is associated with a search tree. The first-level branches are candidate paths for solving the sub-goal, such as different queries, sources, or hypotheses, while deeper nodes record the actions and observations produced along each path. Instead of following one linear search trajectory, TreeSeeker keeps these possible directions separated in the trees. The agent can continue a useful branch, try an uncertain alternative, or prune an unhelpful continuation and return to an earlier branch point for revision. In this way, trial-and-error is not repeated independent runs, but a structured process over search branches.

TreeSeeker has two components.  TreeSearch decides how the search should move through the trees. At each decision round, it first reads all sub-goal trees in one shot, identifies dependency-ready unresolved goals, and outputs one operation for each active goal in a single pass. Here, operation denotes the TreeSearch decision (Explore/Exploit/Prune). Action denotes the tool action used to execute the selected operation.  TreeMem stores compact, failure-aware records for each branch, including evidence, uncertainty, conflicts, progress, and failure cues. By keeping different search directions separated, these records allow TreeSearch to compare branches, identify useful or failed attempts, and decide whether to explore, exploit, or prune.

Figure 1 shows the overall loop. TreeSearch reads the current TreeMem states and outputs one decision for each active sub-goal tree (Explore/Exploit/Prune). After tool execution or pruning, TreeMem updates the corresponding active branch states. This loop lets the agent compare search directions, continue useful ones, test alternatives, and recover from unhelpful paths.

Together, TreeMem and TreeSearch turn trial-and-error into branch-and-return search. We use  Textual UCB because trial-and-error needs an explicit control principle. It should not greedily follow the current best-looking branch. It should also not explore alternatives without discipline. A literal path-level UCB formulation would score every path-action pair per sub-goal. That creates a large combinatorial space and turns deep-search control into fine-grained path ranking. We therefore decide at the operation level. For each dependency-ready sub-goal, TreeSearch compares Exploit/Explore/Prune as budget-allocation choices and then grounds the selected operation on concrete path target(s). This preserves the explore and exploit logic, allocates budget across exploit/explore/return in a principled way, and avoids exhaustive path-action enumeration.

TreeSearch realizes branch-and-return search as an explicit inference-time control loop. At each decision round, TreeSearch reads all sub-goal trees, selects dependency-ready unresolved goals, assigns one operation to each selected tree in a single pass, and updates active trees accordingly. For each selected goal, the decision can be Explore, Exploit, or Prune. This lets the controller advance multiple sub-goals in parallel while keeping each tree update explicit and local.

At decision round $r$, TreeSearch first reads all sub-goal trees in one shot.

It then constructs an actionable frontier over trees that are ready to search but not solved yet.

Here, $\mathrm{View}(\mathcal{T}_{i})$ is a compact view of tree $\mathcal{T}_{i}$, including its active branches and their current states. Let $\mathcal{S}_{r}$ be the indices of trees in $\mathcal{F}_{r}$. TreeSearch then outputs one decision for every tree in $\mathcal{S}_{r}$ in a single pass. Trees outside $\mathcal{S}_{r}$ are not executed in the current round and remain unchanged.

After TreeSearch outputs the decision set $\mathcal{D}_{r}=\{(\mathcal{T}_{i},b_{i},d_{i})\}_{i\in\mathcal{S}_{r}}$, each active tree ($i\in\mathcal{S}_{r}$) is updated independently in the current round. For Explore and Exploit, the selected branch is passed to the action generator, which executes branch-tagged tool actions. The resulting observation is written back to the corresponding branch in TreeMem. For Prune, TreeMem records a failure cue and preserves the earlier branch point for future revision.

The update for each selected tree is written as

where $o_{i}$ is either the returned observation or the pruning signal. Trees outside $\mathcal{S}_{r}$ remain unchanged. The updated collection of trees is then used in the next decision round.

Together, these operations implement structured trial-and-error, where Explore creates trials, Exploit deepens useful trials, and Prune returns from failed ones.

The main text abstracts this process as a TreeSearch–TreeMem feedback loop; the concrete inference procedure and prompt templates are provided in Appendices A and E.

Using gpt-5.2, TreeSeeker achieves 56.3 on XBench-DS, outperforming Flash-Searcher, IterResearch, and Tongyi-DeepSearch by 5.6, 12.3, and 11.3 points, respectively. On BrowseComp and BrowseComp-ZH, it reaches 47.0 and 43.0, ranking first among the evaluated open-source baselines. Under a shared gpt-4.1 backend, TreeSeeker also remains ahead of Flash-Searcher, with gains of 1.7, 2.0, and 2.6 points across the three benchmarks, suggesting that the advantage of TreeSearch–TreeMem is not tied to a single backend model. The strongest controlled comparison is with Flash-Searcher, since both systems use tree-structured search but differ in how candidate paths are controlled after intermediate evidence appears. The consistent gains over Flash-Searcher under both backbones suggest that explicitly maintaining branch states and selecting among continuation, exploration, and pruning decisions improves the effectiveness of the search process itself. Taken together, these results show that TreeSeeker generalizes well across different deep-search benchmarks, including both English and Chinese settings, and achieves the best performance among the evaluated open-source baselines. Beyond task accuracy, we also analyze the token usage and tool-call cost of each system in Appendix C.

Figure 4 shows cumulative success rate versus action steps on the XBench-DS queries shared by all runs, reported as the per-step mean over three runs with min–max envelopes.

The two methods behave similarly in the first several action steps, but their trajectories diverge around step $8$, after which TreeSeeker remains consistently ahead. The gap is visible in both the main growth region (roughly action steps $10$–$30$) and near the end of the budget, where TreeSeeker reaches a higher final cumulative success rate. We attribute this gap to evidence-driven branch selection rather than fixed-schedule path execution. Flash-Searcher executes candidate paths within a goal under a fixed DAG schedule, so later observations have limited effect on whether a path should be continued, revised, or abandoned. In contrast, TreeSeeker keeps branch-local evidence, uncertainty, conflicts, and failure cues in TreeMem, and TreeSearch compares Exploit, Explore, and Prune directly over these branch states using textual UCB signals.

To isolate the contribution of each core component, we conduct ablation experiments on the XBench-DS benchmark. We consider three ablated variants: (1) w/o Textual UCB, which removes the operation-level value, uncertainty, and risk signals from the TreeSearch decision prompt, so the controller selects operations without the textual UCB-style comparison defined in the method section; (2) w/o Explore & Prune, which disables the Explore and Prune operations, so TreeSearch retains only Exploit: it can continue existing branches, but cannot open new continuations or sibling branches, and cannot stop high-risk continuations and return to earlier branch points; (3) w/o Leaf Trace in TreeMem, which removes the retained latest raw leaf trace from TreeMem, forcing the agent to rely only on summarized goal and branch states and losing the short-term continuation anchor for each path.

Table 2 reports the results. Removing any component degrades performance, showing that textual UCB scoring, branch-and-return operations, and the TreeMem design make complementary contributions. Removing textual UCB lowers XBench-DS performance from 56.3 to 52.0 ($-$4.3), disabling Explore and Prune causes the largest drop to 48.0 ($-$8.3), and removing the retained leaf trace in TreeMem lowers performance to 51.3 ($-$5.0). These results indicate that semantic operation scoring, branch-and-return control, and structured branch memory make complementary contributions to effective long-horizon search.

Table 3 reports the empirical frequencies of branch operations on XBench-DS for both the full controller and the w/o Textual UCB ablation.

With textual UCB guidance, TreeSeeker keeps Exploit and Explore relatively balanced ($51.39\%$ vs. $43.45\%$), while using Prune sparingly ($5.17\%$). Removing textual UCB shifts the controller toward substantially more Explore decisions ($61.08\%$) and fewer Exploit and Prune decisions, suggesting that the semantic control signal helps allocate budget more effectively across deepening, branching, and correction. Detailed discussion of these tradeoffs is provided in Appendix D.