TreeFlex: Agents Navigating Their Own Search Trees

Dongzhuo Li; Fangzhou Cheng; Weiwei Li; Kevin Han; Haixu Ma; Zhongchang Sun; Ruiyi Li; Serena Li

cs.AIOct 14, 2026

TreeFlex: Agents Navigating Their Own Search Trees

Authors: Dongzhuo Li, Fangzhou Cheng, Weiwei Li, Kevin Han, Haixu Ma, Zhongchang Sun, Ruiyi Li, Serena Li,

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

B

B_{1}

, and

A_{2}

are newer, it calls navigate to resume

A_{1}

with a new instruction. Bottom: the harness restores only the path

r\!\rightarrow\!A\!\rightarrow\!A_{1}

and its saved state for Execution, so the other branches stay out of its context. Execution proposes

P

, 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 $\mathcal{D}$	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

E_{j}

and, in

E_{6}

, proposes

P

. The proposal

P

receives the terminal score

R_{i}

. (b) Reflection forms one causal block (

R

), and each Execution segment forms its own (

E_{j}

). Colored spans are the model’s own outputs, which are trained, and gray spans are masked context. Instruction

I_{j}

is trained as a Reflection output in

R

and appears only as context in

E_{j}

(dotted). Card

S_{j}

is trained as an Execution output in

E_{j}

and appears only as context when it returns to

R

. 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

K

searches for a task receives one score. Its group-relative advantage

\hat{A}_{i}

applies to every generated token of search

i

, and a process penalty

Q

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

\lambda

				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@

k

gap. Curves use the 32k Qwen3-4B RL models and eight samples for each of 150 questions. (a) Pass@

k

. (b) Majority-vote accuracy over normalized answers against retrieval calls (searches plus reads), averaged over all

k

-sample subsets with ties broken at random. Voting never uses correctness labels. We omit

k=2

because it gives the same result as

k=1

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
FoldAgent	FoldGRPO	43.3	57.8	49	6.4
FoldAgent , step-wise delegation prompt	none	49.5	63.0	132	21.9
FoldAgent , step-wise delegation prompt	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	$\lambda$	Pen.	Val.	Mean@8	Pass@8	Branched	Root nav.	Ancestor nav.	Internal fork
rollout (main)	0	no	38.0	48.8	66.0	53 $\rightarrow$ 59	19 $\rightarrow$ 23	5 $\rightarrow$ 2	19 $\rightarrow$ 18
block	0	no	34.9	48.4	65.3	38 $\rightarrow$ 66	17 $\rightarrow$ 19	3 $\rightarrow$ 10	12 $\rightarrow$ 32
rollout	0.3	no	35.4	45.3	66.0	40 $\rightarrow$ 51	13 $\rightarrow$ 9	5 $\rightarrow$ 5	16 $\rightarrow$ 26
token	0.3	no	40.1	47.7	66.0	50 $\rightarrow$ 63	20 $\rightarrow$ 19	4 $\rightarrow$ 0	19 $\rightarrow$ 12
token	0	no	33.9	46.7	65.3	49 $\rightarrow$ 83	17 $\rightarrow$ 33	5 $\rightarrow$ 1	18 $\rightarrow$ 24

Table 4: Branching varies widely across variants while test accuracy stays within a few points. Loss is the aggregation of Equation ( 3 ),

\lambda

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	$\Delta$	Returns
base model	–	22.3	51.1	64.4	–	43.0
token mean	20	26.7	52.1	67.4	$+1.0$	24.7
rollout mean	25	28.7	54.9	68.0	$+3.8$	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;

\Delta

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 $\times$ GPUs per machine	$2\times 8$
Optimization
Training steps	50

Appendix

Table 6: Configuration of the reported BrowseComp-Plus runs. A value that spans all columns applies to every run. Sampling rows are temperature / top-

p

/ top-

k

/ min-

p

. 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	$+7.33$	[3.50, 11.25]
	vs. FoldAgent	$+6.00$	[1.67, 10.42]
Pass@8	vs. flat ReAct	$+10.00$	[4.00, 16.00]
	vs. FoldAgent	$+10.67$	[4.67, 16.67]
Vote@8	vs. flat ReAct vote@8	$+9.08$	[3.36, 14.97]
	vs. FoldAgent vote@8	$+4.64$	[ $-0.83$ , 10.33]

Appendix

Table 7: Paired differences on BrowseComp-Plus. Bold marks intervals that exclude zero.

Comparison	Difference	95% interval
TreeFlex vs. FoldAgent , base models	$+19.47$	[16.20, 22.73]
TreeFlex vs. FoldAgent step-wise, base models	$+1.60$	[ $-0.73$ , 4.00]
TreeFlex RL vs. FoldAgent RL	$+11.60$	[9.00, 14.27]
TreeFlex RL vs. FoldAgent step-wise RL	$+9.73$	[7.07, 12.40]
TreeFlex RL vs. its base model	$+3.80$	[1.40, 6.27]
FoldAgent RL vs. its base model	$+11.67$	[9.00, 14.40]

Appendix

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
FoldAgent	FoldGRPO	43.3	13.4	17.4
FoldAgent , step-wise delegation prompt	none	49.5	31.5	42.3
FoldAgent , step-wise delegation prompt	FoldGRPO	45.2	40.8	69.5
TreeFlex	none	51.1	50.1	86.1
TreeFlex	tree-aware GRPO	54.9	53.6	90.1

Appendix

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%

Appendix

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

n_{2}

n_{1}

. Node

n_{2}

starts a new branch from the root and finds no rival song. Node

n_{3}

then resolves the remaining date conflict, and Reflection approves the answer.

Memory Management for LLM Agents

See all 58 papers

Aug 11, 2026

Self-Correcting Long-Horizon Search Agents via Tree-Structured Memory

Large language model (LLM)-based search agents answer questions through multi-step interactions with external environments. However, providing complete execution trajectories to the LLM causes unbounded context growth and introduces noise. Existing compression methods reduce context at the cost of important details and often replace erroneous facts without repairing downstream reasoning derived from them. To address this problem, we propose ReTree, a self-correcting tree-structured memory mechanism for search agents. ReTree constructs a bounded per-step reasoning context while preserving source-linked evidence. It models search as an evidence tree whose nodes store bounded summaries, evidence, and revision histories. When newly retrieved evidence contradicts an earlier claim, ReTree traces back to the node where the claim was introduced, replaces outdated evidence, regenerates summaries, prunes affected branches, and resumes search. Source-grounded evidence provenance supports reliable conflict localization and keeps final claims traceable to retrieved passages. Experiments on four public question-answering and search benchmarks show that ReTree consistently outperforms Full-Trajectory ReAct, improving answer accuracy by up to 25.6 percentage points (pp); the average maximum per-step reasoning context of Full-Trajectory ReAct is

1.27

1.51\times

that of ReTree. These results establish ReTree as an effective self-correcting memory abstraction for long-horizon search.

Aijun Yang, Qianxue Guo, Ziyi Huang +3

Shanghai Jiao Tong University

Agentic Search LLM Agent Memory Long-Horizon LLM Agents

Ask PDF

Jun 10, 2026

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

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.

Zhuofan Shi, Mingzhe Ma, Lu Wang +8

1Microsoft · 2East China Normal University

Inference-Time Search Exploration-Exploitation Tradeoff Tree Search Uncertainty-Aware Exploration

Ask PDF

Oct 4, 2026

LexiHorizon: Stabilizing Reinforcement Learning for Long-Horizon Deep Search

Deep search agents tackle complex knowledge tasks through iterative retrieval, multi-hop reasoning, and evidence synthesis across multiple sources. Existing approaches typically assume relatively stable retrieval systems and operate over short-horizon tool interaction. However, when retrieval is sensitive to query formulation, even a semantically appropriate query may fail to surface critical evidence because of mismatched entity names, aliases, or keyword combinations. Recovering from such failures requires repeated query reformulation and longer interaction trajectories. This setting poses a distinct training challenge, as the policy must sustain long-horizon query exploration while managing an expanding volume of retrieved content. We propose LexiHorizon, a framework for training search agents over long horizons that expands the trajectory context budget, manages accumulated retrieval content using a window over recent tool observations while preserving the reasoning history, and introduces an outcome-gated search-effort reward that provides a bounded bonus for tool invocations to trajectories with nonzero answer reward. Experiments on XBench, WebWalkerQA, and BrowseComp-ZH show that the resulting 9B model consistently outperforms both its base model and MiroThinker-1.7-mini, with maximum absolute gains of 8.7 and 23.8 percentage points, respectively. These results suggest that combining an extended context budget with reasoning-preserving context management benefits long-horizon deep search agents.

Zhiqing Nong, Liang Wen, Chao-Hsuan Liu

Long-Horizon Agent Evaluation RL for IR Long-Horizon LLM Agents Memory-Augmented Language Model Agents

Ask PDF

Abstract

Memory Management for LLM Agents

Explore similar work

Self-Correcting Long-Horizon Search Agents via Tree-Structured Memory

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

LexiHorizon: Stabilizing Reinforcement Learning for Long-Horizon Deep Search