cs.AIOct 14, 2026
SaveTreeFlex: Agents Navigating Their Own Search Trees
Organizations: Meta AI
Abstract
A ReAct-style agent accumulates observations, intermediate results, and failed attempts in a single context. As this context grows, stale and off-path information consumes its limited capacity and obscures relevant evidence, making focused reasoning increasingly difficult. We introduce TreeFlex, a framework in which the agent's own policy decides where to search. The agent records each intermediate state, with a short summary, as a node in a search tree maintained by the harness. The policy is a single language model that acts in two roles. In the Reflection role, it has a global view of the tree through these summaries and picks a node to resume, together with an instruction. In the Execution role, the harness restores the path that led to that node, and the model carries out the instruction with the usual task tools until it saves a new node or proposes a solution, which Reflection then approves or sends back to another node. Through these choices, the policy decides whether to deepen the current line, branch from or revisit an earlier state, verify a proposal, or stop, without a fixed traversal order or a score for each node. We train navigation, task actions, checkpointing, and proposal review jointly with a tree-aware adaptation of GRPO, using task-level outcome rewards augmented by process rewards. After small-scale RL of a 4B model, with the same active-context limit for all methods, TreeFlex reaches 48.8% accuracy on a challenging deep-research benchmark, versus 41.5% for flat ReAct and 42.8% for FoldAgent, and its Pass@8 is about ten points higher than either. On SWE-bench Verified, with all three systems trained with RL from the same 9B model, TreeFlex resolves 54.9% of tasks, versus 43.3% for FoldAgent and 45.2% for its step-wise variant.
Figures & tables
Figure 1: One TreeFlex search. Left: the search tree, numbered in creation order. Top: Reflection sees the task and a short card for every node. Although , , and are newer, it calls navigate to resume with a new instruction. Bottom: the harness restores only the path and its saved state for Execution, so the other branches stay out of its context. Execution proposes , and Reflection then approves it. Both roles use the same model. In deep research, the restored path consists of cards and the saved state is empty. In SWE, the restored path is the raw context along the path, and the saved state is a repository snapshot.
| Tool | Role | What it does |
| navigate(node, instruction) | Reflection | Choose a node to resume and write an instruction for the next segment. Creates no node. |
| Domain tools | Execution | Work on the task, such as retrieving documents or editing and testing code. |
| checkpoint(summary) | Execution | Save the current state as a new child of the node where the segment started, with summary as its card, and return the card to Reflection. |
| commit(solution) | Execution | Save the current state as a new child of the node where the segment started, holding a proposed final solution for Reflection to review. |
| approve_commit(node) | Reflection | Accept the proposed solution at node unchanged, which ends the search. |
Table 1: Tree tools of Reflection and Execution. Deep research calls commit with an answer and an explanation. SWE exposes it as OpenHands’ finish(message) , which proposes the current repository state.
Figure 2: Tree-aware GRPO on one search. (a) The search from Figure 1 . In Reflection, the policy picks each node to resume. In Execution, it saves one checkpoint per segment and, in , proposes . The proposal receives the terminal score . (b) Reflection forms one causal block ( ), and each Execution segment forms its own ( ). Colored spans are the model’s own outputs, which are trained, and gray spans are masked context. Instruction is trained as a Reflection output in and appears only as context in (dotted). Card is trained as an Execution output in and appears only as context when it returns to . The blocks follow the deep-research setting, in which Execution sees the cards along its path and only its own instruction. (c) Each of the searches for a task receives one score. Its group-relative advantage applies to every generated token of search , and a process penalty applies only to the turn it concerns. The objective uses a token, block, or rollout mean and can mix in a role mean with weight .
| Quality (%) | Usage per rollout | |||||||
| Model | Method | Ctx. | Br./nav. | Mean@8 | Pass@8 | Gen. tokens | Searches | Reads |
| Qwen3-30B (base) | Flat ReAct | 32k | 0 | 42.6 | 55.3 | 584 | 3.1 | 3.7 |
| FoldAgent | 32k | 10 | 46.1 | 66.7 | 3,212 | 8.7 | 11.5 | |
| TreeFlex | 32k | 10 | 48.3 | 62.7 | 4,833 | 14.3 | 20.6 | |
| Qwen3-4B (base) | Flat ReAct | 32k | 0 | 36.2 | 56.0 | 1,082 | 2.4 | 2.3 |
| FoldAgent | 32k | 10 | 33.1 | 54.0 | 2,553 | 5.7 | 12.3 | |
Table 2: TreeFlex gives the highest mean accuracy under matched context limits. Each cell aggregates eight samples for each of 150 questions. Mean@8 is the accuracy averaged over the eight samples, and Pass@8 counts a question as solved if any sample is correct. Usage values are means per rollout. Generated tokens exclude retrieved observations, and reads count get_document and open_page calls. Ctx. is the active-context limit after the initial prompt, and Br./nav. is the maximum number of branches ( FoldAgent ) or navigations ( TreeFlex ). The flat ReAct row with a 254k limit is a diagnostic outside the matched comparison.
Figure 3: Eight samples of a baseline do not close the Pass@ gap. Curves use the 32k Qwen3-4B RL models and eight samples for each of 150 questions. (a) Pass@ . (b) Majority-vote accuracy over normalized answers against retrieval calls (searches plus reads), averaged over all -sample subsets with ties broken at random. Voting never uses correctness labels. We omit because it gives the same result as .
Figure 4: TreeFlex leads in every difficulty bin. Bars show mean accuracy over eight samples per question; error bars are 95% question-bootstrap intervals. Difficulty follows the independent-reference rule of Sun et al. (2026) .
| Resolved (%) | Usage per rollout | ||||
| System | RL | Mean@3 | Pass@3 | Turns | Minutes |
| FoldAgent | none | 31.7 | 44.0 | 34 | 5.0 |
| FoldGRPO | 43.3 | 57.8 | 49 | 6.4 | |
| FoldAgent , step-wise delegation prompt | none | 49.5 | 63.0 | 132 | 21.9 |
| FoldGRPO | 45.2 | 58.2 | 96 | 10.0 | |
| TreeFlex | none | 51.1 | 64.4 | 98 | 24.8 |
Table 3: TreeFlex resolves the most SWE-bench Verified tasks, before and after RL. Each row uses Qwen3.5-9B with a 32k active-context limit and at most ten branches or navigations, and aggregates three rollouts for each of 500 tasks. Mean@3 is the resolve rate averaged over the three rollouts, and Pass@3 counts a task as resolved if any rollout resolves it. RL models are selected among steps 5, 10, 15, 20, and 25 by Mean@3 on 100 SWE-Gym validation tasks. Turns and minutes are means per rollout.
| Accuracy (%) | Tree behavior during training (%) | ||||||||
| Loss | Pen. | Val. | Mean@8 | Pass@8 | Branched | Root nav. | Ancestor nav. | Internal fork | |
| rollout (main) | 0 | no | 38.0 | 48.8 | 66.0 | 53 59 | 19 23 | 5 2 | 19 18 |
| block | 0 | no | 34.9 | 48.4 | 65.3 | 38 66 | 17 19 | 3 10 | 12 32 |
| rollout | 0.3 | no | 35.4 | 45.3 | 66.0 | 40 51 | 13 9 | 5 5 | 16 26 |
| token | 0.3 | no | 40.1 | 47.7 | 66.0 | 50 63 | 20 19 | 4 0 | 19 12 |
| token | 0 | no | 33.9 | 46.7 | 65.3 | 49 83 | 17 33 | 5 1 | 18 24 |
Table 4: Branching varies widely across variants while test accuracy stays within a few points. Loss is the aggregation of Equation ( 3 ), the role weight, and Pen. the finalization penalty. Val. is Mean@3 on the 64 validation questions at the step selected for each run, and Mean@8 and Pass@8 are test results at that step. Tree behavior compares the first and last ten training steps, using 160 inspected rollouts from each. Branched is the share of rollouts in which some node has more than one child. Root and Ancestor nav. are the shares of navigations that target the root or an earlier ancestor. Internal fork is the share of rollouts in which a node other than the root has more than one child.
| Run | Step | Val. | Mean@3 | Pass@3 | Returns | |
| base model | – | 22.3 | 51.1 | 64.4 | – | 43.0 |
| token mean | 20 | 26.7 | 52.1 | 67.4 | 24.7 | |
| rollout mean | 25 | 28.7 | 54.9 | 68.0 | 12.2 |
Table 5: On SWE, the rollout mean improves over the base model and the token mean does not. Both RL runs train on the 250-task union and use the step among 5, 10, 15, 20, and 25 with the highest validation Mean@3 (Val.). Test values aggregate three rollouts for each of 500 SWE-bench Verified tasks; is the change from the base model. Returns is the share of test rollouts that return to the root or an earlier node.
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
| Setting | TreeFlex | FoldAgent | Flat ReAct (32k) | Flat ReAct (254k) |
| Model and data | ||||
| Base model | Qwen3-4B-Instruct-2507 | |||
| Train / validation / test questions | 616 / 64 / 150 | |||
| Machines GPUs per machine | ||||
| Optimization | ||||
| Training steps | 50 | |||
Table 6: Configuration of the reported BrowseComp-Plus runs. A value that spans all columns applies to every run. Sampling rows are temperature / top- / top- / min- . Context values are in tokens.
Figure 5: TreeFlex leads on validation throughout training. Curves show unsmoothed Mean@3 on the fixed 64-question validation split every five steps. Stars mark the steps selected for test evaluation. The plot does not show test accuracy.
| Metric | Comparison | Difference | 95% interval |
| Mean@8 | vs. flat ReAct | [3.50, 11.25] | |
| vs. FoldAgent | [1.67, 10.42] | ||
| Pass@8 | vs. flat ReAct | [4.00, 16.00] | |
| vs. FoldAgent | [4.67, 16.67] | ||
| Vote@8 | vs. flat ReAct vote@8 | [3.36, 14.97] | |
| vs. FoldAgent vote@8 | [ , 10.33] |
Table 7: Paired differences on BrowseComp-Plus. Bold marks intervals that exclude zero.
| Comparison | Difference | 95% interval |
| TreeFlex vs. FoldAgent , base models | [16.20, 22.73] | |
| TreeFlex vs. FoldAgent step-wise, base models | [ , 4.00] | |
| TreeFlex RL vs. FoldAgent RL | [9.00, 14.27] | |
| TreeFlex RL vs. FoldAgent step-wise RL | [7.07, 12.40] | |
| TreeFlex RL vs. its base model | [1.40, 6.27] | |
| FoldAgent RL vs. its base model | [9.00, 14.40] |
Table 8: Paired differences on SWE-bench Verified (Mean@3). Bold marks intervals that exclude zero.
| System | RL | Resolved | Submitted and resolved | Submitted |
| FoldAgent | none | 31.7 | 3.7 | 3.9 |
| FoldGRPO | 43.3 | 13.4 | 17.4 | |
| FoldAgent , step-wise delegation prompt | none | 49.5 | 31.5 | 42.3 |
| FoldGRPO | 45.2 | 40.8 | 69.5 | |
| TreeFlex | none | 51.1 | 50.1 | 86.1 |
| tree-aware GRPO | 54.9 | 53.6 | 90.1 |
Table 9: Most of the tasks TreeFlex resolves are solutions the policy submitted. Resolved is the Mean@3 of Table 3 . Submitted and resolved counts a rollout only if the policy submitted the graded solution. Submitted is the share of rollouts that end with finish or an approved proposal.
| Search queries | Distinct opened documents | Evidence read | |||||
| Method | Per rollout | Distinct, across 8 | Repeated | Per rollout | Distinct, across 8 | Per rollout | Across 8 |
| Flat ReAct | 3.4 | 21.3 | 21% | 2.0 | 5.3 | 19% | 34% |
| FoldAgent | 9.3 | 68.0 | 10% | 2.7 | 8.7 | 26% | 48% |
| TreeFlex | 20.7 | 153.2 | 6% | 5.2 | 16.0 | 34% | 59% |
Table 10: Repeated flat sampling revisits the same evidence. “Per rollout” averages over the eight samples of a question. “Across 8” pools the eight samples. Repeated is the share of a question’s queries that duplicate another of its queries. Evidence read is the share of a question’s annotated evidence documents that were opened.
Figure 6: TreeFlex restarts from root and then returns to an older node. Badges mark Reflection’s choices, and the dashed arrow shows the return from to . Node starts a new branch from the root and finds no rival song. Node then resolves the remaining date conflict, and Reflection approves the answer.