Paper deep dive
Exploit More, Explore Smarter for Budget-Constrained Agentic Search
Haoyang Fang, Bernie Wang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/26/2026, 4:50:58 AM
Summary
The paper introduces ExTS, a tree-search policy for budget-constrained agentic search that improves upon standard MCTS by treating expansion as a value-of-information decision. ExTS employs three mechanisms: discriminative reward shaping to differentiate candidates with narrow score distributions, a stochastic virtual child to estimate the value of new branches, and quality-conditioned branching to restrict expansion to high-scoring nodes. ExTS demonstrates competitive or superior performance across prompt optimization, code generation, molecular structure elucidation, and agentic workflow optimization, achieving an average relative gain of +5.5% over task-specific baselines.
Entities (16)
Relation Signals (13)
ExTS → evaluatedon → HotpotQA
confidence 95% · Across prompt optimization... ExTS is competitive with or improves over task-specific tree-search baselines
ExTS → evaluatedon → LiveCodeBench
confidence 95% · code generation... ExTS is competitive with or improves over task-specific tree-search baselines
ExTS → improves → standard MCTS
confidence 95% · ExTS is competitive with or improves over task-specific tree-search baselines... standard MCTS allocates budget poorly
ExTS → uses → Discriminative Reward Shaping
confidence 95% · ExTS combines three mechanisms: discriminative reward shaping
ExTS → uses → Virtual Child
confidence 95% · ExTS combines three mechanisms: a stochastic virtual child
ExTS → uses → Quality-Conditioned Branching
confidence 95% · ExTS combines three mechanisms: quality-conditioned branching
Bernie Wang → affiliatedwith → Amazon AGI
confidence 90% · Bernie Wang... Affiliation: Amazon AGI
Haoyang Fang → affiliatedwith → Amazon AGI
confidence 90% · Haoyang Fang Affiliation: Amazon AGI
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Budget-constrained agentic search arises when an LLM agent must refine candidates under a small evaluation budget, because validation is expensive, generation requires multiple model calls, or both. In this regime, standard MCTS allocates budget poorly: exploration bonuses dominate at low visit counts, unpromising siblings are expanded before promising chains can deepen, and branching is independent of node quality. We introduce ExTS, a tree-search policy that treats expansion itself as a value-of-information decision. ExTS combines three mechanisms: discriminative reward shaping to separate candidates under narrow score distributions, a stochastic virtual child that estimates the value of creating a new branch from the parent's reward history, and quality-conditioned branching that expands only when a node's score justifies the budget cost. Across prompt optimization, code generation, molecular structure elucidation, and agentic workflow optimization, ExTS is competitive with or improves over task-specific tree-search baselines, with an average relative gain of +5.5% using a single fixed configuration. We further introduce pilot-run diagnostics that characterize what makes budget-constrained agentic search problems structurally different from one another, providing both understanding of the problem space and practical guidance for adaptation.
Tags
Links
- Source: https://arxiv.org/abs/2608.23848v1
- Canonical: https://arxiv.org/abs/2608.23848v1
Trouble viewing inline? Open PDF directly →
Full Text
83,275 characters extracted from source content.
Expand or collapse full text
Exploit More, Explore Smarter for Budget-Constrained Agentic Search Haoyang Fang Affiliation: Amazon AGI Email: haoyfang@amazon.com Bernie Wang11 1 Work done at Amazon. Affiliation: Amazon AGI Email: yuyawang@amazon.com Abstract Budget-constrained agentic search arises when an LLM agent must refine candidates under a small evaluation budget, because validation is expensive, generation requires multiple model calls, or both. In this regime, standard MCTS allocates budget poorly: exploration bonuses dominate at low visit counts, unpromising siblings are expanded before promising chains can deepen, and branching is independent of node quality. We introduce ExTS, a tree-search policy that treats expansion itself as a value-of-information decision. ExTS combines three mechanisms: discriminative reward shaping to separate candidates under narrow score distributions, a stochastic virtual child that estimates the value of creating a new branch from the parent’s reward history, and quality-conditioned branching that expands only when a node’s score justifies the budget cost. Across prompt optimization, code generation, molecular structure elucidation, and agentic workflow optimization, ExTS is competitive with or improves over task-specific tree-search baselines, with an average relative gain of +5.5% using a single fixed configuration. We further introduce pilot-run diagnostics that characterize what makes budget-constrained agentic search problems structurally different from one another, providing both understanding of the problem space and practical guidance for adaptation. Figure 1: Standard UCT spreads budget across a wide, shallow tree via flat rewards and obligatory expansion. ExTS instead uses virtual children that frame expansion as a value-of-information decision and quality-conditioned branching gated on the reshaped score. Radar plot: normalized gains; ExTS∗ denotes pilot-adapted configurations. 1 Introduction A growing class of AI systems rely on agentic search: an LLM iteratively proposes and refines candidates, consuming budget on both generation and validation. These systems span prompt optimization (Agrawal et al., 2025; Opsahl-Ong et al., 2024), code generation (Zhang et al., 2023; Inoue et al., 2026), tool-augmented reasoning (Yao et al., 2022; Schick et al., 2023), multi-step planning (Yao et al., 2023; Besta et al., 2024), etc. Despite their diversity, they share a common constraint: the search budget is limited to tens or hundreds of calls. We call this regime budget-constrained agentic search. Recent work on LLM search focuses predominantly on the harness: the framework wrapping the search, such as value functions, action spaces, or multi-agent evaluation (Shinn et al., 2023; Madaan et al., 2023; Zhou et al., 2023; Qi et al., 2024; Antoniades et al., 2025; Zhang et al., 2024; Hao et al., 2023; Liu et al., 2025; Li et al., 2025; Fang et al., 2026a). These systems retain linear search or standard UCT for selection and expansion (Appendix A), leaving substantial room for improvement in how budget is allocated within the tree. On the search algorithm side, AB-MCTS (Inoue et al., 2026) replaces UCT with Thompson sampling, GEPA (Agrawal et al., 2025) uses Pareto-frontier selection, and AFlow (Zhang et al., 2025) applies score-weighted random sampling, but each targets a single task type and none condition expansion on node quality or shape rewards for narrow score distributions. How to design selection and expansion policies that transfer across diverse agentic problems has received limited attention. We introduce ExTS11 1 Code will be released at https://github.com/amazon-science/ExTS. Until then, please contact us., a tree-search policy that exploits more and explores smarter by jointly redesigning both how nodes are selected and whether expansion should occur. The core insight is that under tight budgets, the decision of whether to expand is as consequential as which child to visit. Standard MCTS suffers from three structural limitations in this regime: exploration-bonus dominance at low visit counts, forced full expansion of unpromising siblings, and no quality gate on branching. ExTS addresses each through three mechanisms: discriminative reward shaping (Section 3.1) that produces effective selection signals when raw scores cluster narrowly; a virtual child heuristic (Section 3.2) that estimates expansion value by sampling from the parent’s reward history, making expansion a value-of-information (VOI) decision competing directly with deepening; and quality-conditioned branching (Section 3.3) that restricts expansion to nodes whose score justifies the budget cost. These mechanisms are inspired by classical MCTS ideas (progressive widening (Coulom, 2007), first-play urgency (Gelly and Wang, 2006), PUCT (Rosin, 2011)) and improve upon each for budget-constrained agentic search (Section 5.3). With a single fixed configuration across prompt optimization (Yang et al., 2018; Jiang et al., 2020), code generation (Jain et al., 2024), molecular structure elucidation (Zhuang et al., 2025), and agentic workflow optimization (Dua et al., 2019), ExTS is competitive with or improves over task-specific methods (+10.8% on HotpotQA, +11.7% on LiveCodeBench hard, +1.3% on K-MSE, +3.5% on DROP, and +0.2% on HoVeR). ExTS∗ further improves performance by adjusting one or two hyperparameters based on pilot-run diagnostics. We additionally report diagnostics linking landscape structure to hyperparameter sensitivity, component ablations, budget-scaling and tree-shape analysis. 2 Preliminaries 2.1 Validation-Heavy Search We formalize validation-heavy search as a tuple (,,f,B)(S,A,f,B) where S is the set of candidate solutions (e.g., prompts, code, or plans), :→A:S is a stochastic refinement operator powered by an LLM, f:→ℝ∪⊥f:S ∪\ \ is a validation function that returns a score or failure, and B is the total evaluation budget. The search builds a tree T rooted at an initial candidate x0x_0 and the goal is argmaxx∈f(x) _x f(x) within budget B. We identify four pilot-run diagnostics that characterize the search landscape of a validation-heavy task for a given model and scorer (formal definitions in Appendix C). Beyond guiding hyperparameter choices, these diagnostics characterize the axes along which agentic search problems structurally differ and help explain why no single search configuration dominates universally. These diagnostics are computed from a pilot tree built by running the baseline search method for each dataset, measuring properties of the landscape as seen by the task-native algorithm. The refinement variance σ σ_A is the normalized standard deviation of f across independent refinements with the same input, quantifying the stochasticity of the LLM refinement operator. The normalized score deviation σ^f σ_f is the standard deviation of f across all successfully validated candidates in the completed tree, normalized to [0,1][0,1]. The score drift κ is the mean absolute shift in normalized scores caused by evolving normalization bounds as new candidates are discovered; high drift indicates that the search frequently discovers candidates at the extremes of the score range. The failure rate ρ is the fraction of refinement attempts where f returns ⊥ . Table 1 characterizes the datasets we study along these axes. Table 1: Pilot-run diagnostics (mean± , 3 seeds). σ σ_A: refinement variance; σ^f σ_f: score spread; κ: score drift; ρ: failure rate. Dataset σ σ_A σ^f σ_f κ ρ HotpotQA .30±.05 .30±.09 .11±.03 .74±.04 HoVeR .20±.06 .29±.01 .16±.11 .82±.01 LiveCodeBench .32±.01 .23±.01 .14±.13 .57±.05 K-MSE .09±.00 .18±.00 .05±.00 <<.01 DROP .04±.03 .23±.03 .02±.01 .03±.03 2.2 Standard MCTS and Its Limitations In standard MCTS, the UCT policy (Kocsis and Szepesvári, 2006) selects child c of node v by maximizing UCTstd(c)=Rcnc+ClnnvncUCT_std(c)= R_cn_c+C n_vn_c (1) where Rc/ncR_c/n_c is the average reward, ncn_c and nvn_v are visit counts, and C controls exploration. The theoretical default C=2C= 2 is calibrated for rewards in [0,1][0,1] with sufficient budget for convergence (Browne et al., 2012). Two assumptions underlying UCT are violated in validation-heavy search. First, reward shaping (Section 3.1) compresses the effective exploitation range, causing the exploration bonus to dominate and making all nodes appear equally promising. Second, budgets of tens to hundreds of evaluations are far below the asymptotic regime where UCT’s convergence guarantees hold (Silver et al., 2016; Browne et al., 2012; Kocsis and Szepesvári, 2006). Together, these violations produce flat, wide trees that fail to develop deep refinement chains. The PUCT exploration term (Section 3.1) partially addresses the first issue by decaying linearly rather than logarithmically, reducing the dominance of exploration under tight budgets. Classical extensions. Three classical MCTS ideas are relevant but do not transfer directly to this regime (Section 5.3). Progressive widening (Coulom, 2007; Chaslot et al., 2008) ties branching to visit count but is score-agnostic. First-play urgency (FPU) (Gelly and Wang, 2006) assigns a fixed value to unvisited actions but cannot adapt to non-stationary score distributions. PUCT (Rosin, 2011; Silver et al., 2017) uses a learned policy prior with linear exploration decay. ExTS redesigns each: progressive widening becomes quality-conditioned, FPU becomes a stochastic virtual child sampling from the parent’s reward history, and PUCT-style decay operates without a learned prior. 3 Methodology Our intuition is that, especially under tight budgets, adding a single scalar-weighted UCT or PUCT exploration term to the reward cannot by itself capture the balance between exploration and exploitation (Section 5.1). ExTS keeps this weighted exploration term, but conditions both selection and expansion decisions on the observed reward distribution at two scopes: local (a node’s own subtree) and global (the whole search tree). Concretely, each node v stores a candidate xv∈x_v and maintains: nvn_v (total visits), nv+n_v^+ (successful visits), ℛvR_v (reward observations from successful expansions in v’s subtree), and sv=f(xv)s_v=f(x_v) (validation score). The reward pool ℛvR_v implements mean backup: ExUCT(v)(v) estimates the refinement productivity of expanding below v, not the quality of v’s own candidate. Figure 1 illustrates how the three design choices transform the search tree. The complete search loop follows standard MCTS (select, expand, validate, backpropagate) and is given in Algorithm 2 (Appendix B). 3.1 Discriminative Reward Shaping Both effective selection and meaningful expansion decisions require differentiating node quality. When raw validation scores cluster in a narrow range, as is common in validation-heavy domains, UCT’s exploitation term makes all nodes appear equally attractive: selection becomes near-random, and any VOI comparison between expanding versus deepening becomes uninformative. The ExTS selection policy addresses this by scoring each visited node v (nv>0n_v>0) as: ExUCT(v) (v) =(nv+nv)α⋅φ(ri)¯ = ( n_v^+n_v )^α\!·\! (r_i) +explore(npar(v),nv) +explore(n_par(v),\;n_v) (2) The exploitation term combines two signals: the shaped rewards φ(ri)¯ (r_i), which separate candidates when raw scores cluster narrowly, and a success-rate weight (nv+/nv)α(n_v^+/n_v)^α, which discounts nodes whose subtrees produce mostly invalid outputs (α controls failure discounting). The shaping function φ maps raw scores through global normalization and a temperature-controlled nonlinearity: φ(r)=er^/T−1e1/T−1,r^=r−sminsmax−smin, (r)= e^\, r/T-1e^1/T-1, r= r-s_ s_ -s_ , (3) φ(ri)¯=1|ℛv|∑ri∈ℛvφ(ri). (r_i)= 1|R_v| _r_i _v (r_i). (4) For T<1T<1, φ is convex, compressing low scores and amplifying high scores. This is important in validation-heavy domains where scores cluster in a narrow range and linear normalization would make most nodes appear equally attractive. The exploration term takes one of two forms. The UCT variant decays logarithmically: exploreUCT(npar,nv)=Clnnparnv,explore_UCT(n_par,n_v)=C n_parn_v, (5) while the PUCT-style variant decays linearly, providing faster convergence toward exploitation under tight budgets: explorePUCT(npar,nv)=C⋅npar1+nv.explore_PUCT(n_par,n_v)=C· n_par1+n_v. (6) Unlike standard PUCT (Rosin, 2011; Silver et al., 2017), which incorporates a learned policy prior P(a|s)P(a|s), our variant uses no prior for simplicity, because such a prior must be designed task-specifically. The default ExTS configuration uses PUCT-style exploration with C=1.0C\!=\!1.0; we evaluate the UCT variant (C=2C\!=\! 2) as an ablation in Section 5.3. 3.2 VOI Estimation via the Virtual Child The core of ExTS’s expansion-as-VOI principle is a mechanism for estimating the expected value of creating a new child at any internal node. In standard MCTS, expansion occurs only at leaf nodes, forcing the algorithm to fully expand each level before deepening. We instead make expansion a first-class decision at every internal node by introducing a virtual child that competes with real children during selection. At each internal node v with m existing children, if v can still expand (m<Mm<M), we compute a virtual child score. First, we estimate the virtual child’s fair-share visit count: nfair=max(1,∑c∈children(v)ncm).n_fair= \! (1,\; [rgb]0,0,0 _c (v)n_cm ). (7) We then sample k=max(1,⌊nfair⋅nv+/nv⌋)k= (1, n_fair· n_v^+/n_v ) scores with replacement from the parent’s reward pool ℛv∪svR_v∪\s_v\ and compute the estimated shaped mean φ(r~)¯ ( r). The virtual child score mirrors Equation 2: ExUCTvirt=(nv+nv)α⋅φ(r~)¯+explore(nv,nfair).ExUCT_virt= ( n_v^+n_v )^\!α\!·\, ( r)\;+\;explore(n_v,n_fair). (8) The stochastic sampling captures finite-sample uncertainty: fewer expected visits produce fewer samples and thus higher variance, naturally encouraging expansion when evidence is thin. Let c∗=argmaxcjExUCT(cj)c^*= _c_jExUCT(c_j) be the best real child. If ExUCTvirtual>ExUCT(c∗)ExUCT_virtual>ExUCT(c^*), the node is selected for expansion; otherwise selection recurses into c∗c^*. Appendix I works through this comparison on a real run. 3.3 Quality-Conditioned Branching ExTS conditions branching on node quality at two granularities: whether a node may expand at all, and how many children it may accumulate. Expansion gate. For non-root nodes, expansion is permitted only when the node’s validation score exceeds the τ-quantile of the population: sv≥Qτ(su:u∈).s_v≥ Q_τ (\s_u:u \ ). (9) Below-threshold nodes remain reachable and update their statistics but cannot spawn new children. The threshold adapts as the tree accumulates better candidates, becoming increasingly selective over time. Quality-gated progressive widening. Classical progressive widening (Coulom, 2007; Chaslot et al., 2008) ties branching to visit count but is score-agnostic. We condition it on node quality: the maximum branching factor grows with visit count, but only for nodes whose quality justifies it: M(v)=M0+⌊logbnvn0⌋⋅[sv≥Qγ∨v=vroot],M(v)=M_0+ _b\! n_vn_0 · 1 [s_v≥ Q_γ v=v_root ], (10) where M0M_0 is the initial maximum children, b is the widening base, n0n_0 is the visit threshold before widening begins, and QγQ_γ is the γ-quantile of node scores. Typically γ≫τγ τ (defaults: γ=0.75γ=0.75, τ=0.25τ=0.25), reflecting that widening is a stronger commitment than a single expansion. Low-scoring nodes remain capped at M0M_0. Algorithm 1 ExUCT-Select: Selection with Virtual Child 0: Node v 1: if v is a leaf then 2: return v 3: end if 4: can_expand←|children(v)|<M(v)can\_expand←|children(v)|<M(v) 5: if v≠rootv and can_expand then 6: can_expand ←sv≥Qτ(su:u∈)← s_v≥ Q_τ(\s_u:u \) 7: end if 8: c∗←argmaxc∈children(v)ExUCT(c)c^*← _c (v)ExUCT(c) 9: if can_expand then 10: m←|children(v)|m←|children(v)| 11: nfair←max(1,∑cnc/m)n_fair← (1,\; [rgb]0,0,0 _cn_c/m ) 12: k←max(1,⌊nfair⋅nv+/nv⌋)k← (1, n_fair· n_v^+/n_v ) 13: Sample r~1,…,r~k∼ℛv∪sv r_1,…, r_k _v∪\s_v\ with replacement 14: q←(nv+/nv)α⋅1k∑iφ(r~i)q←(n_v^+/n_v)^α· 1k _i ( r_i) 15: ExUCTvirtual←q+explore(nv,nfair)ExUCT_virtual← q+explore(n_v,n_fair) 16: if ExUCTvirtual>ExUCT(c∗)ExUCT_virtual>ExUCT(c^*) then 17: return v expand here 18: end if 19: end if 20: return ExUCT-Select(c∗c^*) Gate semantics. The expansion gate (Algorithm 1, line 5) applies to internal nodes deciding whether to create additional children. A leaf node returned at line 2 is selected for its first expansion regardless of score; the gate restricts further branching only after a node has at least one child and evidence of its quality. This means every node receives at least one expansion attempt before gating takes effect. 4 Evaluation We evaluate ExTS across four domains spanning diverse failure rates, score variances, and drift levels (Table 1). All methods share the same evaluation budget B per task. ExTS uses a single fixed configuration across all domains (Table 10); each baseline is the best-known method for its respective task with a fully tuned, domain-specific configuration. We additionally report ExTS∗ variants that adjust one or two hyperparameters per task based on pilot-run diagnostics, a modest adaptation that remains fair given the domain-specific tuning already present in each baseline. Full formulation details are in Appendix D. 4.1 Prompt Optimization Table 2: Prompt optimization: test accuracy (%) over 3 seeds. †Results from Agrawal et al. (2025). ∗Pilot-adapted (Section 5.2). Method HotpotQA HoVeR Baseline 41.44± 1.25 36.11± 0.79 GRPO† 43.33 38.67 MIPROv2† 55.33 47.33 GEPA (Pareto) 58.55± 5.32 50.33± 2.45 ExTS 64.89± 0.83 50.45± 2.18 ExTS∗ 66.00± 0.98 51.67± 0.98 We integrate ExTS into the GEPA framework (Agrawal et al., 2025) for optimizing DSPy (Khattab et al., 2023) instructions on HotpotQA (Yang et al., 2018) and HoVeR (Jiang et al., 2020) (300 test examples, 3 seeds, Qwen3-8B). This domain has the highest failure rate (ρ=0.74ρ=0.74–0.820.82) among our tasks. Table 2 shows that ExTS improves over GEPA Pareto by ++10.8% on HotpotQA with 6.4×6.4× lower variance. The pilot-adapted ExTS∗ further improves to 66.00% by increasing the success-rate exponent to α=2.0α\!=\!2.0, which sharpens node selection in this high-failure-rate domain (ρ=0.74ρ=0.74; Section 5.2). On HoVeR, ExTS performs on par with GEPA Pareto (++0.2%, within noise). HoVeR exhibits the highest score drift (κ=0.16κ=0.16) among our tasks, causing normalization bounds to shift frequently and re-rank nodes mid-search. The pilot-adapted ExTS∗ switches to UCT exploration with no gating, buffering against score re-ranking by maintaining sustained exploration (Section 5.2). 4.2 Code Generation Figure 2: LiveCodeBench pass@1 (%) over 3 seeds. We integrate ExTS into the TreeQuest framework (Inoue et al., 2026) on LiveCodeBench (Jain et al., 2024) (182 problems, budget 128, Claude Sonnet 4), comparing against StandardMCTS and AB-MCTS-A. All three methods achieve identical public-test success rates on easy (100%) and medium (85.8%), making those splits non-discriminative; we therefore use the hard split as our primary metric while reporting overall performance for reference (Figure 2). On the hard split, ExTS reaches 19.1% pass@1 versus 17.1% for AB-MCTS-A (++11.7%) and 18.1% for StandardMCTS (++5.5%), with the lowest cross-seed variance. The gains come from deeper refinement of promising candidates rather than broader coverage. Overall pass@1 is 46.2% (++1.3% over StandardMCTS). The pilot-adapted ExTS∗ (T=0.5T\!=\!0.5) further improves to 47.4% overall (++4.0% over StandardMCTS). 4.3 Molecular Structure Elucidation Table 3: K-MSE molecular elucidation (Claude Sonnet 4.6, 216 molecules, 16 rollouts, 3 seeds). ACC (exact match) is the primary metric; fingerprint similarities are listed for reference. ∗Pilot-adapted (Section 5.2). Method ACC (%) Morgan MACCS RDK CoT 79.8± 0.2 .887±.002 .942±.001 .904±.001 K-MSE 89.8± 0.4 .952±.002 .976±.001 .962±.003 ExTS 91.0± 0.6 .952±.004 .972±.005 .960±.004 ExTS∗ 91.2± 0.4 .954±.004 .973±.003 .959±.004 We apply ExTS to K-MSE (Zhuang et al., 2025), where an LLM deduces molecular SMILES from NMR and IR spectra (216 molecules, Claude Sonnet 4.6). This domain has near-zero failure rate and stationary scores. ExTS improves ACC by ++1.3% over K-MSE’s MCTSr (Table 3). The strong base model leaves limited headroom; gains come from exploitation shaping and the virtual child directing budget toward molecules that benefit from iterative refinement. The scorer measures embedding similarity rather than exact match, creating a reward-metric gap where structurally similar but incorrect molecules (e.g., isomers sharing NMR signatures) receive high rewards. 4.4 Agentic Workflow Optimization Table 4: Workflow optimization on DROP (F1 × 100, 3 seeds). ∗Pilot-adapted (Section 5.2). Method F1 (mean± ) Best Cost ($) CoT (linear) 89.28± 1.78 91.10 36.70 AFlow 87.89± 2.29 89.56 26.09 ExTS 90.96± 0.93 91.54 15.26 ExTS∗ 91.54± 1.92 93.76 10.43 We evaluate ExTS on DROP (Dua et al., 2019) within the AFlow framework (Zhang et al., 2025), which searches over LLM-based operator graphs (20 rounds, 3 seeds, Claude Sonnet 4.5 optimizer, Haiku 4.5 executor). The three methods differ in how they condition refinement: CoT always extends the deepest chain; AFlow conditions on a top-scoring round chosen by stochastic sampling; ExTS conditions on a tree-search-selected node. CoT achieves strong accuracy by accumulating history but incurs the highest cost as context grows linearly. AFlow reduces cost by avoiding deep chains but sacrifices robustness through stateless selection. ExTS is Pareto-dominant: tree search identifies productive nodes at moderate depths while quality gates prevent overcommitment to deep chains, achieving the best accuracy, lowest variance, and lowest cost (Table 4). We report cost only for this domain because the optimizer receives the parent workflow as context, making cost proportional to conditioning depth; in other domains (code generation, molecular elucidation), cost per iteration is fixed regardless of search depth. 5 Understanding ExTS 5.1 The Exploration Constant Is Not Enough A natural question is whether simply tuning the exploration constant C in standard MCTS could replicate ExTS’s gains. On LiveCodeBench (Figure 2), sweeping C from 1.0 to 2.0 produces only marginal differences (44.3–45.6% overall), with no configuration approaching ExTS (46.2%). The exploration-exploitation ratio is a single scalar that uniformly scales the bonus across all nodes; it cannot address flat reward signals, forced full expansion, or score-agnostic branching. Lowering C shifts budget toward exploitation but still expands unpromising nodes unconditionally; raising C broadens coverage but wastes budget on shallow siblings that never deepen. Neither direction addresses the core issue: the tree policy lacks the structural mechanisms to decide where expansion is worthwhile. ExTS’s improvement is structural: it reshapes how the tree grows, not merely how much it explores. 5.2 Pilot-Run Findings We examine how pilot-run diagnostics (Table 1) characterize the structural differences among agentic search problems and relate these differences to hyperparameter sensitivity. The high cost of agentic search experiments does not permit exhaustive grid search, so the ExTS∗ configurations below may not represent optimal settings. Nonetheless, even coarse adaptation guided by these diagnostics yields ExTS∗ variants that outperform all task-specific baselines (Tables 2, 3, 4 and Figure 2). Appendix G condenses these findings into a compact diagnostic guide (Table 13). Three patterns emerge. Low σ σ_A/low κ or unstable validation → soften T. When refinement variance and drift are both low, scores cluster tightly and aggressive exploitation (low T) over-commits to gaps that may not predict test improvement. Relaxing T to 0.5 hedges against this. On K-MSE (σ^=0.09 σ_A\!=\!0.09, κ=0.05κ\!=\!0.05), T=0.5T\!=\!0.5 yields 91.2% ACC (++0.2 p; Table 3). On DROP (σ^=0.04 σ_A\!=\!0.04, κ=0.02κ\!=\!0.02), raising τ=0.5τ\!=\!0.5 with M0=4M_0\!=\!4 yields 91.54 F1 (++0.58 p; Table 4). LiveCodeBench (σ^=0.32 σ_A\!=\!0.32, κ=0.14κ\!=\!0.14) does not exhibit this signature, yet also benefits from T=0.5T\!=\!0.5 (47.4%, ++1.2 p; Figure 2) because its validation signal is inherently sparse: a few public test cases serve as proxy for the full hidden suite, creating per-sample noise that similarly rewards softer exploitation. In all three cases, moderate T-softening improves performance when the validation scorer is a weak proxy for the true metric. High score drift (κ) → early exploration. High κ means normalization bounds shift frequently, making early shaped reward rankings unreliable. UCT’s exploration term is larger than PUCT’s when the tree is small, providing stronger early exploration before rankings stabilize. Disabling the score gate (τgate=0 _gate\!=\!0) avoids blocking potentially good parents based on transiently low scores. On HoVeR (κ=0.16κ=0.16, highest), switching to UCT with τgate=0 _gate\!=\!0 yields 51.67% (++1.22 p, 2.2×2.2× lower variance; Table 2). Conversely, HotpotQA (κ=0.11κ=0.11) strongly prefers PUCT (++6.45 p over UCT; Table 7), where fast decay concentrates budget on chains whose rankings are stable enough to trust. High failure rate (ρ) → sensitive to α. Intuitively, when most expansions fail, the success-rate exponent α becomes critical for separating productive nodes from unproductive ones. We verify this on HotpotQA (ρ=0.74ρ=0.74): setting α=2.0α\!=\!2.0 yields 66.00% (++1.11 p; Table 2), while reducing α to 1.0 causes −-7.78 p with 6.8×6.8× higher variance (Table 5). In low-failure tasks, α has negligible effect. 5.3 Ablation Studies We isolate each design choice via leave-one-out ablation on HotpotQA (high ρ, high κ). LiveCodeBench ablations are in Table 12 (Appendix F). Table 5: Leave-one-out ablation on HotpotQA (3 seeds). LiveCodeBench ablations in Table 12. Configuration Acc. Configuration Acc. ExTS (full) 64.89± 0.83 w/o Soft norm. 63.44± 2.20 w/o Virtual child 61.67± 1.96 w/o Gated expan. 63.22± 1.10 w/o Fail. penalty (α=1α\!=\!1) 57.11± 5.67 w/o Gated PW 62.55± 2.08 Table 5 confirms that all components contribute. Failure penalty has the largest impact (−-7.78 p), followed by the virtual child (−-3.22 p); without the latter, the algorithm reverts to wide-tree behavior. Gated progressive widening contributes −-2.34 p by restricting expansion to nodes whose quality justifies the budget cost. Classical mechanisms do not transfer directly. Table 6 replaces ExTS components with their classical counterparts: fixed FPU (Gelly and Wang, 2006) instead of the virtual child, and score-agnostic progressive widening (Coulom, 2007) instead of quality-gated widening. On DROP, both FPU constants underperform ExTS (−-2.0 p and −-1.6 p), and the gap between FPU= 0.5\,=\,0.5 and FPU= 0.8\,=\,0.8 (++0.4 p) illustrates a fundamental limitation: fixed FPU is sensitive to the constant’s value, which interacts with exploration C, shaping temperature T, and domain score scale. The virtual child sidesteps this coupling by sampling from observed rewards, adapting automatically as the score distribution evolves. Score-agnostic widening wastes budget expanding low-quality nodes. Table 6: Classical mechanisms vs. ExTS redesigns (3 seeds). Configuration Score DROP (F1 × 100) ExTS (virtual child) 90.96± 0.93 Fixed FPU =0.5=0.5 88.95± 0.81 Fixed FPU =0.8=0.8 89.34± 3.23 LiveCodeBench (pass@1 %) ExTS (quality-gated PW) 46.2± 0.4 Score-agnostic PW 45.0± 0.9 Exploration type: PUCT vs. UCT. Table 7 compares the default PUCT (linear decay) against UCT (logarithmic decay). HotpotQA strongly prefers PUCT (++6.45 p), where fast decay concentrates budget on proven chains. HoVeR prefers UCT (++0.88 p), where sustained exploration buffers against score drift. This task-dependent sensitivity motivates the diagnostic analysis in Section 5.2. Table 7: Exploration type ablation: PUCT (default) vs. UCT, 3 seeds. Dataset PUCT UCT HotpotQA 64.89± 0.83 58.44± 2.20 HoVeR 50.45± 2.18 51.33± 1.44 K-MSE 91.0± 0.6 89.0± 1.5 5.4 Tree-Shape Diagnostics We verify that ExTS redirects budget from breadth-first exploration into selective refinement by comparing tree shape on K-MSE (216 molecules, B=16B\!=\!16, 3 seeds), where MCTSr and ExTS differ only in tree policy. We measure mean leaf depth and depth of the best-scoring node, partitioning molecules into trivial (124/216 solved at root) and non-trivial (92/216). Full setup details are in Appendix E. Table 8: Tree-shape diagnostics on K-MSE (B=16B\!=\!16, 3 seeds). Non-trivial: 92 molecules where at least one method improves beyond the root. Method Leaf dep. Best dep. Scorer ACC (%) All tasks (n=216n\!=\!216) MCTSr 4.89±.08 0.44±.07 72.2± 0.3 89.8± 0.4 ExTSM0=2_M_0=2 5.49±.13 0.48±.05 72.5± 0.2 90.4± 0.4 ExTSM0=3_M_0=3 4.91±.14 0.47±.03 72.7± 0.1 91.0± 0.6 Non-trivial tasks (n=92n\!=\!92) MCTSr 4.43±.13 1.03±.16 69.5± 0.6 77.2± 0.9 ExTSM0=2_M_0=2 4.44±.09 1.12±.11 69.6± 0.4 78.6± 1.0 ExTSM0=3_M_0=3 3.73±.22 1.09±.06 70.1± 0.1 80.1± 1.4 On the non-trivial partition, ExTS (M0=3M_0\!=\!3) produces shallower leaf depths (3.73 vs. 4.43) while finding its best node deeper (1.09 vs. 1.03), the signature of selective refinement. This structural shift yields ++2.9 p ACC on the non-trivial subset (80.1% vs. 77.2%), where the overall ++1.2 p gain is concentrated. MCTSr distributes budget uniformly across depths; ExTS concentrates children at promising nodes and deepens only subtrees that improve, placing the best node at the depth where refinement transitions from improving to diminishing returns. 5.5 Budget-Scaling Behavior We measure performance as a function of evaluation budget B across LiveCodeBench, HotpotQA, and K-MSE (setup details in Appendix E). Figure 3: Budget-scaling behavior across three domains, averaged over 3 seeds (±1σ± 1σ bands). The x-axis is search budget. ExTS’s advantage is most pronounced on hard instances (top left) and in prompt optimization (bottom left), where iterative refinement matters most. Figure 3 shows that ExTS converts budget into performance more efficiently across all domains. On LiveCodeBench, ExTS trails at B=1B=1 (all methods reduce to a single sample) but overtakes Standard MCTS at B≈8B≈8 and reaches 46.2% vs. 45.6% (Standard) and 45.4% (AB-MCTS) at B=128B=128; on hard problems the gap widens to 19.1% vs. 17.1% (AB-MCTS). On HotpotQA, ExTS reaches 64.9% at B=70B=70 versus 58.0% for GEPA Pareto with tighter confidence intervals. On K-MSE, ExTS leads from B=1B=1 onward and maintains a growing gap (72.5 vs. 71.8 at B=13B=13). The crossover pattern reflects ExTS’s calibration overhead: progressive widening and virtual-child scoring require initial samples, but this investment pays off once quality-conditioned pruning can redirect evaluations away from unpromising subtrees. The steeper scaling on hard problems (+6.5+6.5 p from B=1B=1 to B=32B=32 vs. +3.7+3.7 p for MCTS) confirms that the advantage concentrates where search depth matters most. 6 Conclusion We introduced ExTS, a tree-search policy for budget-constrained LLM agent search that jointly redesigns both selection and expansion. Rather than applying flat UCT selection and expanding unconditionally, ExTS makes both decisions quality-aware: shaping rewards for narrow score distributions, framing expansion as a value-of-information decision, and gating branching on node quality. Across four diverse domains, ExTS is competitive with or improves over task-specific baselines using a single fixed configuration, with gains concentrated in high-failure-rate and moderate-difficulty regimes. The same fixed configuration further generalizes to an additional domain, GPU kernel optimization (Appendix H). We additionally show that pilot-run diagnostics characterize the structural differences among agentic search problems, explain why different tasks respond to different configurations, and offer practical guidance for adaptation. Limitations We use a single model per domain due to the substantial API costs of tree search (each experiment requires hundreds of LLM calls per task instance across multiple seeds) and do not study how model scale alters the search landscape; because the pilot-run diagnostics are conditioned on the model, scorer, and budget, they describe the landscape as seen by that configuration rather than intrinsic domain properties, and their transferability across model families is untested. Finally, the diagnostic approach requires a pilot tree that, in deployment on a new task, consumes budget not applied to the final search. References Agrawal et al. (2025) L. A. Agrawal, S. Tan, D. Soylu, N. Ziems, R. Khare, K. Opsahl-Ong, A. Singhvi, H. Shandilya, M. J. Ryan, M. Jiang, et al. Gepa: reflective prompt evolution can outperform reinforcement learning. arXiv preprint arXiv:2507.19457. Cited by: Appendix A, Appendix A, §D.1, §D.1, §1, §1, §4.1, Table 2. Antoniades et al. (2025) A. Antoniades, A. Örwall, K. Zhang, Y. Xie, A. Goyal, and W. Wang SWE-search: enhancing software agents with monte carlo tree search and iterative refinement. External Links: 2410.20285, Link Cited by: Appendix A, §1. Besta et al. (2024) M. Besta, N. Blach, A. Kubicek, R. Gerstenberger, M. Podstawski, L. Gianinazzi, J. Gajda, T. Lehmann, H. Niewiadomski, P. Nyczyk, et al. Graph of thoughts: solving elaborate problems with large language models. In Proceedings of the AAAI conference on artificial intelligence, Vol. 38, p. 17682–17690. Cited by: §1. Brown et al. (2024) B. Brown, J. Juravsky, R. Ehrlich, R. Clark, Q. V. Le, C. Ré, and A. Mirhoseini Large language monkeys: scaling inference compute with repeated sampling. External Links: 2407.21787, Link Cited by: Appendix A. Browne et al. (2012) C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and S. Colton A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games 4 (1), p. 1–43. Cited by: §2.2, §2.2. Chaslot et al. (2008) G. M. J. Chaslot, M. H. Winands, H. J. v. d. Herik, J. W. Uiterwijk, and B. Bouzy Progressive strategies for monte-carlo tree search. New Mathematics and Natural Computation 4 (03), p. 343–357. Cited by: §2.2, §3.3. Coulom (2007) R. Coulom Computing “elo ratings” of move patterns in the game of go. ICGA journal 30 (4), p. 198–208. Cited by: §1, §2.2, §3.3, §5.3. Dua et al. (2019) D. Dua, Y. Wang, P. Dasigi, G. Stanovsky, S. Singh, and M. Gardner DROP: a reading comprehension benchmark requiring discrete reasoning over paragraphs. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), p. 2368–2378. Cited by: §D.4, §1, §4.4. Fang et al. (2026a) H. Fang, B. Han, N. Erickson, X. Zhang, S. Zhou, A. Dagar, J. Zhang, A. C. Turkmen, T. Hu, H. Rangwala, et al. Mlzero: a multi-agent system for end-to-end machine learning automation. Advances in Neural Information Processing Systems 38, p. 69001–69070. Cited by: Appendix A, §1. Fang et al. (2026b) H. Fang, W. Zhu, B. Han, A. Zhang, Z. Pan, S. Yang, S. Zhang, J. Gai, P. Tang, C. Hu, et al. LLMZero: discovering adaptive training strategies for rl post-training via llm agents. arXiv preprint arXiv:2606.18388. Cited by: Appendix A. Gai et al. (2026) J. Gai, S. Zhang, K. Bostrom, J. Huang, V. Patil, H. Fang, B. Wang, H. Rangwala, and G. Karypis Optimizing cuda like a human: micro-profiling tools as expert surrogates for llm-based gpu kernel optimization. arXiv preprint arXiv:2606.26453. Cited by: Table 14, Table 14, Appendix H. Gelly and Wang (2006) S. Gelly and Y. Wang Exploration exploitation in go: uct for monte-carlo go. In NIPS: Neural Information Processing Systems Conference On-line trading of Exploration and Exploitation Workshop, Cited by: Appendix A, §1, §2.2, §5.3. Guo et al. (2024) K. Guo, B. Nan, Y. Zhou, T. Guo, Z. Guo, M. Surve, Z. Liang, N. V. Chawla, O. Wiest, and X. Zhang Can llms solve molecule puzzles? a multimodal benchmark for molecular structure elucidation. In Advances in Neural Information Processing Systems, A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (Eds.), Vol. 37, p. 134721–134746. External Links: Document, Link Cited by: §D.3. Hao et al. (2023) S. Hao, Y. Gu, H. Ma, J. J. Hong, Z. Wang, D. Z. Wang, and Z. Hu Reasoning with language model is planning with world model. External Links: 2305.14992, Link Cited by: Appendix A, §1. He et al. (2026) Z. He, H. Lin, B. Han, W. Zhu, H. Fang, B. Wang, X. Zhu, R. Li, and M. Reimherr ReSkill: reconciling skill creation with policy optimization in agentic rl. arXiv preprint arXiv:2606.01619. Cited by: Appendix A. Inoue et al. (2026) Y. Inoue, K. Misaki, Y. Imajuku, S. Kuroki, T. Nakamura, and T. Akiba Wider or deeper? scaling llm inference-time compute with adaptive branching tree search. Advances in Neural Information Processing Systems 38, p. 35448–35484. Cited by: Appendix A, Appendix A, §D.2, §D.2, §1, §1, §4.2. Jain et al. (2024) N. Jain, K. Han, A. Gu, W. Li, F. Yan, T. Zhang, S. Wang, A. Solar-Lezama, K. Sen, and I. Stoica LiveCodeBench: holistic and contamination free evaluation of large language models for code. External Links: 2403.07974, Link Cited by: §D.2, §1, §4.2. Jiang et al. (2020) Y. Jiang, S. Bordia, Z. Zhong, C. Dognin, M. Singh, and M. Bansal HoVer: a dataset for many-hop fact extraction and claim verification. In Findings of the Association for Computational Linguistics: EMNLP 2020, p. 3441–3460. Cited by: §D.1, §1, §4.1. Khattab et al. (2023) O. Khattab, A. Singhvi, P. Maheshwari, Z. Zhang, K. Santhanam, S. Vardhamanan, S. Haq, A. Sharma, T. T. Joshi, H. Moazam, et al. Dspy: compiling declarative language model calls into self-improving pipelines. arXiv preprint arXiv:2310.03714. Cited by: §D.1, §4.1. Kocsis and Szepesvári (2006) L. Kocsis and C. Szepesvári Bandit based monte-carlo planning. In European conference on machine learning, p. 282–293. Cited by: §2.2, §2.2. Kwon et al. (2023) W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C. H. Yu, J. E. Gonzalez, H. Zhang, and I. Stoica Efficient memory management for large language model serving with pagedattention. External Links: 2309.06180, Link Cited by: §D.1. Lange et al. (2026) R. Lange, Y. Imajuku, and E. Cetin Shinkaevolve: towards open-ended and sample-efficient program evolution. In International Conference on Learning Representations, Vol. 2026, p. 74026–74078. Cited by: Appendix A. Li et al. (2025) D. Li, S. Cao, C. Cao, X. Li, S. Tan, K. Keutzer, J. Xing, J. E. Gonzalez, and I. Stoica S*: test time scaling for code generation. External Links: 2502.14382, Link Cited by: Appendix A, §1. Li et al. (2018) L. Li, K. Jamieson, G. DeSalvo, A. Rostamizadeh, and A. Talwalkar Hyperband: a novel bandit-based approach to hyperparameter optimization. External Links: 1603.06560, Link Cited by: Appendix A. Li et al. (2026) Y. Li, W. Deng, J. Li, and X. Li Spend less, reason better: budget-aware value tree search for llm agents. External Links: 2603.12634, Link Cited by: Appendix A. Liu et al. (2026) S. Liu, S. Agarwal, M. Maheswaran, M. Cemri, Z. Li, Q. Mang, A. Naren, E. Boneh, A. Cheng, M. Z. Pan, et al. Evox: meta-evolution for automated discovery. arXiv preprint arXiv:2602.23413. Cited by: Appendix A. Liu et al. (2025) Z. Liu, Y. Cai, X. Zhu, Y. Zheng, R. Chen, Y. Wen, Y. Wang, S. Chen, et al. Ml-master: towards ai-for-ai via integration of exploration and reasoning. arXiv preprint arXiv:2506.16499. Cited by: Appendix A, §1. Madaan et al. (2023) A. Madaan, N. Tandon, P. Gupta, S. Hallinan, L. Gao, S. Wiegreffe, U. Alon, N. Dziri, S. Prabhumoye, Y. Yang, et al. Self-refine: iterative refinement with self-feedback. Advances in neural information processing systems 36, p. 46534–46594. Cited by: Appendix A, §1. Opsahl-Ong et al. (2024) K. Opsahl-Ong, M. J. Ryan, J. Purtell, D. Broman, C. Potts, M. Zaharia, and O. Khattab Optimizing instructions and demonstrations for multi-stage language model programs. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, p. 9340–9366. Cited by: Appendix A, §1. Qi et al. (2024) Z. Qi, M. Ma, J. Xu, L. L. Zhang, F. Yang, and M. Yang Mutual reasoning makes smaller llms stronger problem-solvers. External Links: 2408.06195, Link Cited by: Appendix A, §1. Rosin (2011) C. D. Rosin Multi-armed bandits with episode context. Annals of Mathematics and Artificial Intelligence 61 (3), p. 203–230. Cited by: §1, §2.2, §3.1. Santhanam et al. (2022) K. Santhanam, O. Khattab, J. Saad-Falcon, C. Potts, and M. Zaharia Colbertv2: effective and efficient retrieval via lightweight late interaction. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, p. 3715–3734. Cited by: §D.1. Schick et al. (2023) T. Schick, J. Dwivedi-Yu, R. Dessì, R. Raileanu, M. Lomeli, E. Hambro, L. Zettlemoyer, N. Cancedda, and T. Scialom Toolformer: language models can teach themselves to use tools. Advances in neural information processing systems 36, p. 68539–68551. Cited by: §1. Shinn et al. (2023) N. Shinn, F. Cassano, A. Gopinath, K. Narasimhan, and S. Yao Reflexion: language agents with verbal reinforcement learning. Advances in neural information processing systems 36, p. 8634–8652. Cited by: Appendix A, Appendix A, §1. Silver et al. (2016) D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature 529 (7587), p. 484–489. Cited by: §2.2. Silver et al. (2017) D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815. Cited by: §2.2, §3.1. Snell et al. (2024) C. Snell, J. Lee, K. Xu, and A. Kumar Scaling llm test-time compute optimally can be more effective than scaling model parameters. External Links: 2408.03314, Link Cited by: Appendix A. Wang et al. (2024) X. Wang, C. Li, Z. Wang, F. Bai, H. Luo, J. Zhang, N. Jojic, E. Xing, and Z. Hu Promptagent: strategic planning with language models enables expert-level prompt optimization. In International Conference on Learning Representations, Vol. 2024, p. 23967–24001. Cited by: Appendix A. Wei et al. (2023) J. Wei, X. Wang, D. Schuurmans, M. Bosma, B. Ichter, F. Xia, E. Chi, Q. Le, and D. Zhou Chain-of-thought prompting elicits reasoning in large language models. External Links: 2201.11903, Link Cited by: §D.3. Yang et al. (2025) A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: §D.1. Yang et al. (2024) C. Yang, X. Wang, Y. Lu, H. Liu, Q. V. Le, D. Zhou, and X. Chen Large language models as optimizers. In International Conference on Learning Representations, Vol. 2024, p. 12028–12068. Cited by: Appendix A. Yang et al. (2018) Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. Cohen, R. Salakhutdinov, and C. D. Manning HotpotQA: a dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 conference on empirical methods in natural language processing, p. 2369–2380. Cited by: §D.1, §1, §4.1. Yao et al. (2023) S. Yao, D. Yu, J. Zhao, I. Shafran, T. Griffiths, Y. Cao, and K. Narasimhan Tree of thoughts: deliberate problem solving with large language models. Advances in neural information processing systems 36, p. 11809–11822. Cited by: §1. Yao et al. (2022) S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao React: synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629. Cited by: Appendix A, §1. Zhang et al. (2024) D. Zhang, J. Wu, J. Lei, T. Che, J. Li, T. Xie, X. Huang, S. Zhang, M. Pavone, Y. Li, W. Ouyang, and D. Zhou LLaMA-berry: pairwise optimization for o1-like olympiad-level mathematical reasoning. External Links: 2410.02884, Link Cited by: Appendix A, §1. Zhang et al. (2025) J. Zhang, J. Xiang, Z. Yu, F. Teng, X. Chen, J. Chen, M. Zhuge, X. Cheng, S. Hong, J. Wang, et al. Aflow: automating agentic workflow generation. In International Conference on Learning Representations, Vol. 2025, p. 34040–34077. Cited by: Appendix A, Appendix A, 1st item, §D.4, §1, §4.4. Zhang et al. (2023) S. Zhang, Z. Chen, Y. Shen, M. Ding, J. B. Tenenbaum, and C. Gan Planning with large language models for code generation. arXiv preprint arXiv:2303.05510. Cited by: §1. Zhou et al. (2023) A. Zhou, K. Yan, M. Shlapentokh-Rothman, H. Wang, and Y. Wang Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:2310.04406. Cited by: Appendix A, §1. Zhuang et al. (2025) X. Zhuang, B. Wu, J. Cui, K. Feng, X. Li, H. Xing, K. Ding, Q. Zhang, and H. Chen Boosting llm’s molecular structure elucidation with knowledge enhanced tree search reasoning. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 22561–22576. Cited by: Appendix A, §D.3, §D.3, §1, §4.3. Contents 1 Introduction 2 Preliminaries 2.1 Validation-Heavy Search 2.2 Standard MCTS and Its Limitations 3 Methodology 3.1 Discriminative Reward Shaping 3.2 VOI Estimation via the Virtual Child 3.3 Quality-Conditioned Branching 4 Evaluation 4.1 Prompt Optimization 4.2 Code Generation 4.3 Molecular Structure Elucidation 4.4 Agentic Workflow Optimization 5 Understanding ExTS 5.1 The Exploration Constant Is Not Enough 5.2 Pilot-Run Findings 5.3 Ablation Studies 5.4 Tree-Shape Diagnostics 5.5 Budget-Scaling Behavior 6 Conclusion References A Related Work B Default Configuration and Complete Algorithm C Formal Definitions of Pilot-Run Diagnostics D Detailed Experimental Setup D.1 Prompt Optimization D.2 Code Generation D.3 Molecular Structure Elucidation D.4 Agentic Workflow Optimization E Analysis Setup Details F More Ablations on LiveCodeBench G Compact Diagnostic Guide H Further Evaluation on an Additional Domain: GPU Kernel Optimization I Worked Example: The Virtual Child J Ethical Considerations and Broader Impact K Artifact Documentation L Use of AI Assistants Appendix A Related Work Search for LLM reasoning and generation. Search strategies for LLM generation can be organized by whether their primary contribution lies in the harness (the framework surrounding the search) or the search algorithm itself (selection and expansion policies). On the harness side, many systems wrap standard MCTS with LLM-specific components while retaining vanilla UCT for selection and expansion. Some operate as linear refinement chains without tree structure (Shinn et al., 2023; Madaan et al., 2023; Fang et al., 2026a; Fang et al., 2026b). LATS (Zhou et al., 2023) integrates MCTS with LLM value functions and self-reflection but does not modify the tree policy. rStar (Qi et al., 2024) defines rich reasoning actions with mutual verification between two SLMs. RAP (Hao et al., 2023) repurposes the LLM as a world model within standard MCTS. SWE-Search (Antoniades et al., 2025) introduces a multi-agent evaluation framework with a hybrid value function for software engineering tasks. PromptAgent (Wang et al., 2024) frames prompt optimization as MCTS-style strategic planning with error feedback. LLaMA-Berry (Zhang et al., 2024) replaces raw value estimates with pairwise preference aggregation for mathematical reasoning but retains standard UCT selection. S* (Li et al., 2025) combines parallel sampling with sequential refinement and execution-grounded selection for code generation, contributing a scaling pipeline rather than a tree policy. MLMaster (Liu et al., 2025) applies vanilla UCT to data science automation. In each case, the primary innovation is the surrounding framework or evaluation mechanism; the internal selection and expansion dynamics remain standard or unmodified, representing a gap where better search policies could yield further gains. On the search algorithm side, fewer works redesign how budget is allocated across candidates. AB-MCTS (Inoue et al., 2026) replaces UCT with Thompson sampling for code generation. GEPA (Agrawal et al., 2025) uses Pareto-frontier selection over scored candidates for prompt optimization. AFlow (Zhang et al., 2025) applies score-weighted random sampling from recent rounds for workflow optimization. BAVT (Li et al., 2026) introduces budget-conditioned node selection via a power-law exponent that shifts from exploration to exploitation as budget depletes, evaluated on multi-hop QA tasks. BAVT is not open-sourced, precluding direct comparison. ExTS departs from most of these methods by making the exploration/exploitation balance reward-aware: instead of a fixed exploration constant, a reward-agnostic first-play-urgency value, or progressive widening tied to visit count alone, it lets observed validation rewards drive both the value of expansion and how wide a node may branch. Its virtual child is the clearest example: where first-play urgency (Gelly and Wang, 2006) assigns the same fixed value to every unexpanded child, the virtual child is a node-specific, data-dependent estimate resampled from the parent’s shaped-reward pool and scored at a fair-share visit count, which we treat as a value-of-information-style estimate of expansion value. Its closest relative is the adaptive branching of AB-MCTS (Inoue et al., 2026) (one of our baselines), which likewise lets a hypothetical branch compete with existing children. However, AB-MCTS-A relies on parametric Bayesian posteriors with conjugate priors, while AB-MCTS-M dynamically estimates two posterior distributions via MCMC, which can be less effective when the search budget is small; the virtual child, by contrast, is a nonparametric, prior-free bootstrap coupled with quality-gated widening. We compare against AB-MCTS-A (Gaussian), the strongest AB-MCTS variant on LiveCodeBench. Finally, whereas each of these baselines targets a single task type, ExTS redesigns both selection and expansion and holds a single fixed configuration across four structurally distinct domains, plugging into each framework’s existing search interface (GEPA, TreeQuest, K-MSE, AFlow). Table 9 summarizes this positioning against prior LLM tree-search methods. Test-time compute allocation and sampling baselines. Several lines of work study inference-time budget allocation from complementary perspectives. Snell et al. (2024) characterize when repeated sampling versus sequential revision is compute-optimal for reasoning tasks, providing scaling predictions at the problem level. ExTS addresses a different use case, agentic search with iterative refinement, but its mechanisms for efficient budget allocation could in principle be applied within test-time scaling frameworks. Best-of-N sampling (Brown et al., 2024) generates N independent candidates and returns the best. ExTS instead exploits parent-child refinement structure, achieving better efficiency when iterative improvement is productive. Sequential halving and Hyperband (Li et al., 2018) efficiently eliminate unpromising configurations but assume independent candidates. ExTS handles tree-structured refinement where parent quality predicts child quality. Table 9: Positioning of ExTS relative to prior LLM tree-search methods. “Focus” indicates whether the primary contribution is the search harness (H) or the search algorithm (A). Method Focus Selection Expansion Fail.-aware Linear H Sequential N/A No ToT H BFS/DFS Full No LATS H UCT Full No rStar H UCT Full No RAP H UCT Full No SWE-Search H UCT + hybrid value Full No LLaMA-Berry H UCT + pairwise Full No S* H Parallel + refine Pipeline No MLMaster H UCT Full No PromptAgent H UCT Full No GEPA A Pareto Stateless No AFlow A Score-weighted Random No AB-MCTS A Thompson Adaptive No BAVT A Budget-conditioned Structural No ExTS A ExUCT Gated + adaptive Yes Evolutionary search for LLM systems. ShinkaEvolve (Lange et al., 2026) and EvoX (Liu et al., 2026) are population-based evolutionary optimizers that run at a far larger budget than ExTS’s tight per-query regime (ShinkaEvolve uses roughly 150 evaluations for its headline result, whereas several of our settings run well below this, e.g., 16 rollouts on K-MSE and 20 rounds on AFlow), so they differ from ExTS in search family, budget, and search space. Even GEPA (Agrawal et al., 2025), one of our prompt-optimization baselines, is itself a Genetic-Pareto evolutionary method, yet ExTS improves over it by 10.8% on HotpotQA at 6.4× lower variance. ExTS is instead a complementary, plug-and-play tree policy whose value-of-information view of expansion is orthogonal to how candidates are generated, and matched-budget comparisons between tree and evolutionary search (and hybrids of the two) are a valuable direction for future work. Prompt and Skill optimization. OPRO (Yang et al., 2024) uses LLMs as optimizers over scored solution histories. MIPROv2 (Opsahl-Ong et al., 2024) applies Bayesian surrogate optimization to DSPy instruction tuning. For skill optimization, ReSkill (He et al., 2026) selects among candidate skills via Thompson sampling in agentic RL. ExTS can serve as a drop-in selection component within such frameworks. Self-improving agents. Reflexion (Shinn et al., 2023) uses verbal self-reflection for iterative improvement but follows a linear chain rather than a tree, missing the opportunity to explore alternative refinement paths. ReAct (Yao et al., 2022) synergizes reasoning and acting but uses greedy selection. These approaches are complementary, and ExTS could serve as the search backbone for systems that currently rely on linear or greedy strategies. Automated workflow optimization. AFlow (Zhang et al., 2025) automates agentic workflow generation by searching the space of LLM-based operator graphs. We directly compare against AFlow’s search strategy in Section 4.4. Molecular structure elucidation. K-MSE (Zhuang et al., 2025) already applies MCTS with a neural molecule-spectrum scorer to molecular structure elucidation, making it a directly relevant baseline. Our K-MSE evaluation uses the same scorer and knowledge base, isolating the effect of the selection/expansion policy. Appendix B Default Configuration and Complete Algorithm Algorithm 2 gives the complete ExTS search loop and Table 10 lists the default hyperparameters used across all experiments. Algorithm 2 ExTS: Complete Search Loop 0: x0x_0, refinement operator A, validator f, budget B 1: Initialize tree T with root v0v_0, xv0←x0x_v_0← x_0, sv0←f(x0)s_v_0← f(x_0) 2: while budget B not exhausted do 3: v←ExUCT-Select(v0)v← ExUCT-Select(v_0) Alg. 1 4: x′←(xv)x (x_v) LLM refinement 5: r←f(x′)r← f(x ) 6: if r=⊥r= then 7: Backprop-Failure(v); continue 8: end if 9: Create child u: xu←x′x_u← x , su←rs_u← r 10: children(v)←children(v)∪uchildren(v) (v)∪\u\ 11: Backprop-Success(v, r) 12: end while 13: return argmaxv∈sv _v s_v Table 10: ExTS default configuration, fixed across all experiments. Parameter Default Rationale Exploration type PUCT Linear decay for tight budgets Exploration C 1.0 Conservative; no policy prior Success-rate α 2 2 Amplified failure discounting Temperature T 0.3 Top-20% emphasis Initial children M0M_0 3 Moderate branching Widening base b 2 log2 _2 growth Widening threshold n0n_0 32 Delay widening Widening quantile γ 0.75 Top-quartile widening Score gate τ 0.25 Mild gating Appendix C Formal Definitions of Pilot-Run Diagnostics Section 2.1 introduces four measurable pilot-run diagnostics that characterize the search landscape of validation-heavy domains. We provide rigorous definitions below, expressed in terms of the search tree T built during a pilot run of budget B. Table 11 summarizes the notation used throughout. Table 11: Notation used in formal property definitions. Symbol Description T Search tree rooted at initial candidate x0x_0 V()V(T) Set of all nodes in T I()I(T) Set of internal (expanded) nodes: v∈V():|children(v)|>0\v∈ V(T):|children(v)|>0\ nvn_v Visit count of node v (incremented via backpropagation from all expansions in the subtree rooted at v) nv+n_v^+ Successful visit count (backpropagated from expansions where f(x′)≠⊥f(x )≠ ) nv−n_v^- Failed visit count: nv−=nv−nv+n_v^-=n_v-n_v^+ svs_v Validation score f(xv)f(x_v) for node v’s candidate xvx_v S+S^+ Set of successfully validated nodes: v∈V():sv is defined\v∈ V(T):s_v is defined\ smin,smaxs_ ,s_ minv∈S+sv _v∈ S^+s_v and maxv∈S+sv _v∈ S^+s_v respectively Definition 1: Failure rate (ρ). The fraction of expansion attempts that do not produce a successfully validated candidate: ρ=nv0−nv0ρ\;=\; n_v_0^-n_v_0 (11) where v0v_0 is the root. Since backpropagation increments all ancestors after each expansion, nv0n_v_0 equals the total number of expansion attempts across the tree and nv0−n_v_0^- equals the total failures. An attempt counts as failed if f returns ⊥ (e.g., syntax error, runtime error, timeout, or a domain-specific rejection criterion). By construction, ρ∈[0,1]ρ∈[0,1]. Domains with ρ>0.5ρ>0.5 spend more than half their budget on failed attempts, making failure-aware mechanisms (dual backpropagation, success-rate weighting) essential. Definition 2: Normalized score deviation (σ^f σ_f). The spread of validation scores across all successfully evaluated candidates, normalized by the observed range: σ^f=1smax−smin1|S+|−1∑v∈S+(sv−s¯)2 σ_f\;=\; 1s_ -s_ 1|S^+|-1 _v∈ S^+(s_v- s)^2 (12) where s¯=1|S+|∑v∈S+sv s= 1|S^+| _v∈ S^+s_v. If smax=smins_ =s_ or |S+|<2|S^+|<2, we define σ^f=0 σ_f=0. Low values indicate a flat score landscape where exploitation shaping must work harder to differentiate candidates. Definition 3: Score drift (κ). Score drift quantifies the non-stationarity of normalized node scores as the tree grows. At each iteration t a new node with score snews_new is added. Let smints_ ^t and smaxts_ ^t denote the running minimum and maximum scores among all nodes at iteration t. Let Δ=t:smint≠smint−1 or smaxt≠smaxt−1T_ =\t:s_ ^t≠ s_ ^t-1 or s_ ^t≠ s_ ^t-1\ be iterations where the normalization bounds change. The normalized score of node v at time t is s^vt=(sv−smint)/(smaxt−smint) s_v^t=(s_v-s_ ^t)/(s_ ^t-s_ ^t). Then: κ=1|Δ|∑t∈Δ1|Vt|∑v∈Vt|s^vt−s^vt−1|κ\;=\; 1|T_ | _t _ 1|V_t| _v∈ V_t | s_v^t- s_v^t-1 | (13) where VtV_t is the set of nodes existing before iteration t (excluding the newly added node). If |Δ|=0|T_ |=0 or the score range is zero, we define κ=0κ=0. High κ indicates that newly discovered candidates frequently shift the normalization bounds, changing the relative exploitation values of existing candidates. Definition 4: Refinement variance (σ σ_A). The refinement variance measures the stochasticity of the refinement operator A when applied to the same parent state. For each internal node v∈I()v∈ I(T) with at least two successfully validated children, let Cv+=c∈children(v):sc is definedC_v^+=\c (v):s_c is defined\ and f¯v=1|Cv+|∑c∈Cv+sc f_v= 1|C_v^+| _c∈ C_v^+s_c. The per-node refinement variance is: σ,v2=1|Cv+|−1∑c∈Cv+(sc−f¯v)2σ^2_A,v\;=\; 1|C_v^+|-1 _c∈ C_v^+(s_c- f_v)^2 (14) Let I2=v∈I():|Cv+|≥2I_2=\v∈ I(T):|C_v^+|≥ 2\. The global refinement variance is: σ^=1smax−smin1|I2|∑v∈I2σ,v2 σ_A\;=\; 1s_ -s_ 1|I_2| _v∈ I_2σ^2_A,v (15) Distinction from σ^f σ_f. σ^f σ_f measures the spread of scores across all candidates in the tree, reflecting the combined effect of different parent states, depths, and refinement histories. In contrast, σ σ_A isolates the variance attributable to the LLM’s sampling stochasticity by conditioning on the parent. A domain may have low σ^f σ_f (flat overall landscape) but high σ σ_A (diverse candidates from any single parent), or vice versa. High σ σ_A indicates that re-sampling from the same node is productive, providing implicit exploration; low σ σ_A indicates refinements are largely deterministic and explicit exploration via higher C is needed. Computation details for Table 1. All properties are computed from pilot trees built by running the baseline method for each dataset with budget B, averaged across 3 seeds (0,42,1024\0,42,1024\). ρ: We read nv0n_v_0 and nv0+n_v_0^+ directly from the root node’s backpropagated statistics stored in the pilot tree. σ^f σ_f: We collect the score svs_v of every node v∈S+v∈ S^+ in the pilot tree and compute the sample standard deviation divided by smax−smins_ -s_ . For K-MSE, which runs 216 independent molecule searches per seed, we pool all node scores across molecules before computing a single σ^f σ_f per seed. κ: We replay the tree construction in node-creation order, tracking smints_ ^t and smaxts_ ^t after each insertion. At each iteration where bounds change, we compute the mean absolute shift in normalized scores across existing nodes and average over all such events. σ σ_A: We estimate refinement variance from sibling scores in the pilot tree: for each internal node v with |Cv+|≥2|C_v^+|≥ 2 successfully validated children, we compute σ,v2σ^2_A,v from the children’s scores and aggregate via Equation 15. This treats siblings as approximate samples from (xv)A(x_v), which is valid when the tree context does not meaningfully change between sibling expansions. For LiveCodeBench, where the pilot does not save per-node tree structure, we instead run K=10K\!=\!10 i.i.d. refinements from a fixed parent state for 5 representative problems and aggregate. Appendix D Detailed Experimental Setup D.1 Prompt Optimization We evaluate ExTS within the GEPA prompt optimization framework (Agrawal et al., 2025), which optimizes natural-language instructions in DSPy programs (Khattab et al., 2023). We use two multi-hop reasoning benchmarks: HotpotQA (Yang et al., 2018), a question answering task with a 4-predictor DSPy program and ColBERTv2 retrieval (Santhanam et al., 2022) over 5.2M Wikipedia abstracts, and HoVeR (Jiang et al., 2020), a fact verification task. Both use a test set of 300 examples with accuracy (%) as the evaluation metric, and all experiments are run across seeds 0,42,1024\0,42,1024\ using Qwen3-8B (Yang et al., 2025) via vLLM (Kwon et al., 2023) (TP=4, temperature 0.6, top-p 0.95, thinking enabled). In the ExTS formulation, the candidate set S consists of DSPy instruction configurations. The refinement operator A is an LLM instruction proposer conditioned on failure feedback. The validator f evaluates on the full train and validation set, returning ⊥ if the new score does not exceed the parent’s. Score stationarity κ is high because aggregate scores shift when new programs join the Pareto frontier. We compare four conditions: Baseline (unoptimized seed program), GEPA Pareto (task-native Pareto-frontier selection (Agrawal et al., 2025)), ExTS default (Table 10), and per-dataset ExTS∗ (HotpotQA: α=2.0α\!=\!2.0; HoVeR: UCT exploration, τ=0τ\!=\!0), with the optimization budget matched across methods. D.2 Code Generation We evaluate ExTS within the TreeQuest framework (Inoue et al., 2026) on LiveCodeBench (Jain et al., 2024), which contains 182 problems from release v6 (January to April 2025) split into 45 easy, 55 medium, and 82 hard problems. Public test cases serve as the search reward signal and private test cases determine the final pass@1 metric. We use Claude Sonnet 4 with temperature 0.6, a budget of 128 steps per problem, and report results over seeds 0,42,1024\0,42,1024\. In the ExTS formulation, S consists of code solutions, A is an LLM code editor conditioned on test failure traces, and f is the full public test suite execution (returning ⊥ on syntax errors or compilation failures). Score stationarity κ is low because existing solution scores do not change. We compare StandardMCTS (UCT with C=2C\!=\! 2, samples per action of 5), AB-MCTS-A (Thompson sampling with Gaussian conjugate prior (Inoue et al., 2026)), and ExTS default (Table 10). ExTS∗ sets T=0.5T\!=\!0.5. D.3 Molecular Structure Elucidation We evaluate ExTS on the K-MSE molecular structure elucidation task (Zhuang et al., 2025), in which an LLM must deduce a molecule’s SMILES representation from infrared (IR) and nuclear magnetic resonance (NMR) spectral data together with a molecular formula. The evaluation set consists of 216 molecules from the MolPuzzle dataset (Guo et al., 2024), each paired with its IR spectrum image, carbon-13 and proton NMR spectra, and molecular formula. The primary metrics are Morgan fingerprint Tanimoto similarity (FTS) and exact-match accuracy (ACC), where ACC canonicalizes both predicted and ground-truth SMILES via RDKit before comparison. We use Claude Sonnet 4.6 with a pre-trained molecule-spectrum alignment scorer for reward computation. In the ExTS formulation, S consists of SMILES strings, A is an LLM that critiques the current prediction against spectral data and a retrieved knowledge base of 593 molecular substructures and then proposes a revised SMILES, g checks chemical validity via RDKit, and f is a neural scorer that computes cosine similarity between the predicted molecule’s embedding and the target spectrum’s embedding scaled to [0,100][0,100]. We compare ExTS against K-MSE’s original MCTSr (Zhuang et al., 2025) and chain-of-thought prompting (Wei et al., 2023, CoT;), using 16 rollouts per molecule and 3 seeds (0,42,1024\0,42,1024\). ExTS uses the default configuration (Table 10). ExTS∗ sets T=0.5T\!=\!0.5. D.4 Agentic Workflow Optimization We evaluate ExTS within the AFlow framework (Zhang et al., 2025) on the DROP reading comprehension benchmark (Dua et al., 2019). DROP consists of paragraphs with questions requiring discrete reasoning (counting, sorting, arithmetic) over text; the test set contains 800 problems scored by token-level F1. In the AFlow formulation, a “workflow” is a Python function that orchestrates one or more LLM calls (using operators such as Generate, Format, Review, Ensemble) to answer a question given a passage. The search space S consists of these workflow programs. The refinement operator A is an optimizer LLM (Claude Sonnet 4.5) that proposes mutations to the workflow graph conditioned on execution logs and past experience. The validator f executes the workflow on a validation split of 200 problems over 5 rounds and returns the mean F1 score. The failure rate is low (ρ≈0.05ρ≈ 0.05) because workflows almost always produce parseable output; failures are rare execution errors. We compare three search strategies sharing the same optimizer LLM, executor LLM (Claude Haiku 4.5), validation protocol, and test evaluation: • AFlow (Zhang et al., 2025): Score-weighted random parent sampling from recent rounds. No tree structure or visit statistics. • CoT (linear): Sequential refinement chain that always extends the deepest node. No branching or selection policy. • ExTS: Default configuration (Table 10). ExTS∗ sets τ=0.5τ\!=\!0.5, M0=4M_0\!=\!4. Budget is 20 search rounds per seed, with seeds 0,42,1024\0,42,1024\. Appendix E Analysis Setup Details Tree-shape diagnostics (Section 5.4). We compare MCTSr (binary expansion, no gating) against ExTS at two branching caps: M0=2M_0\!=\!2 (matching MCTSr’s effective branching) and M0=3M_0\!=\!3 (the default). All methods share the same scorer, retriever, and LLM (Claude Sonnet 4.6). Molecules are partitioned into trivial (best node at depth 0 for all methods in all seeds; 124/216) and non-trivial (at least one method in one seed improves beyond the root; 92/216). On the full dataset, all methods achieve similar leaf depths (∼5 5) because 57% of molecules are trivially solved and MCTS exhausts budget on already-solved problems. The non-trivial partition isolates the algorithmic difference. The scorer gap on non-trivial molecules (++0.6 over MCTSr) translates to a meaningful ACC improvement because this partition selects precisely the molecules where the scorer provides actionable signal. Budget-scaling behavior (Section 5.5). On LiveCodeBench we run Standard MCTS, AB-MCTS, and ExTS with B=128B=128 (182 problems, 3 seeds) and extract pass@1 at each intermediate budget from the cumulative score trajectory: a problem is solved at budget b if its best public-test solution within the first b evaluations also passes all held-out private tests. On HotpotQA we compare ExTS and GEPA Pareto over 78 search iterations (3 seeds), tracking cumulative best validation accuracy. On K-MSE we compare ExTS and MCTSr over 13 evaluation steps (3 seeds, 216 molecules), tracking cumulative best scorer score. Appendix F More Ablations on LiveCodeBench Table 12 isolates two components on LiveCodeBench. Removing gated progressive widening costs −-1.3 p overall and −-1.6 p on hard problems, confirming that quality-conditioned branching prevents budget waste on unpromising subtrees. Removing root exclusion (allowing the score gate to block root expansion) costs −-1.0 p overall and −-2.0 p on hard, with notably higher variance, because gating the root can starve the tree of initial diversity when early candidates score poorly. Table 12: Leave-one-out ablation on LiveCodeBench (pass@1 %, 3 seeds). Configuration All (%) Hard (%) ExTS (full) 46.2± 0.4 19.1± 1.4 w/o Gated prog. widening 44.9± 0.7 17.5± 1.4 w/o Root exclusion 45.2± 1.5 17.1± 2.5 Appendix G Compact Diagnostic Guide Table 13 condenses the pilot-run findings of Section 5.2 into a compact diagnostic guide. We intend it as both a deployment aid and an analytic contribution: the four diagnostics characterize the axes along which agentic search landscapes structurally differ (failure rate, score spread, drift, and refinement variance), and each axis maps to a concrete hyperparameter adjustment. These full-dataset diagnostics are an analytic study of why agentic search landscapes differ, not a deployment requirement: the fixed default configuration needs no pilot and already matches or beats every task-specialized baseline, while the ExTS∗ refinements adjust only one or two hyperparameters for modest gains (typically 0.20.2–1.21.2 p). When adaptation is desired, the diagnostics are cheap landscape statistics estimable from a small pilot subset, and most are collected simply by running the baseline method (Section 2.1), a run practitioners would perform anyway, so they largely reuse existing computation rather than new budget. Table 13: Compact diagnostic guide: mapping pilot-run signatures to hyperparameter adjustments, condensing Section 5.2. Diagnostic signature What it says about the task Relevant hyperparameter Evidence High failure rate ρ (e.g. >0.5>0.5) most expansions fail, so separating productive nodes is critical success exponent α HotpotQA Low ρ (e.g. <0.1<0.1) failures are rare success exponent α (little effect, keep default) K-MSE, DROP High score drift κ early rankings are unreliable as bounds re-rank nodes exploration type (use UCT) and score gate τ HoVeR Low κ rankings stabilize early, safe to commit exploration type (use PUCT) HotpotQA Low σ σ_A and low κ, or weak validator aggressive exploitation over-commits to spurious gaps shaping temperature T K-MSE, DROP, LCB The default configuration, used when no pilot is run, is PUCT with C=1.0C\!=\!1.0, α=2α\!=\! 2, T=0.3T\!=\!0.3, M0=3M_0\!=\!3, and τ=0.25τ\!=\!0.25 (Table 10). Appendix H Further Evaluation on an Additional Domain: GPU Kernel Optimization To further probe the generalizability of ExTS, we evaluate it on an additional domain beyond the four in the main text: GPU kernel optimization. Using the same fixed default configuration (Table 10), with no tuning and no diagnostics, we follow the setup of Gai et al. (2026), using Claude Opus 4.6 as the refinement model and their original configuration for all other settings, and reproduce their pipeline on 40 tasks, running each task on a single NVIDIA A100 40GB GPU, and compare against their optimized MCTS baseline, which we label MCTS (optimized). Owing to the substantial compute cost of this domain, we report results from a single run rather than the multiple runs used elsewhere in the paper. In this run, ExTS improves over MCTS (optimized) on every metric, raising the geometric-mean speedup from 4.15×4.15× to 4.36×4.36×, the median speedup from 3.09×3.09× to 3.81×3.81×, and the per-category speedups across all three difficulty levels (Table 14). We note that the original speed validation of Gai et al. (2026) contained an issue that admitted invalid (spurious) speedups; the numbers reported here are the corrected results that exclude those invalid speedups. These results indicate that ExTS’s budget-allocation mechanisms generalize to this additional domain without any domain-specific adaptation. Table 14: Further evaluation on an additional domain, GPU kernel optimization: 40 GPU-kernel tasks, each run on a single NVIDIA A100 40GB GPU, using ExTS’s fixed default configuration (Table 10) with no tuning or diagnostics. All values are speedup factors (×); L1, L2, and L3 are the difficulty levels (categories) defined by Gai et al. (2026). ExTS improves over MCTS (optimized) on every metric. Results are from a single run with Claude Opus 4.6, owing to the substantial compute cost of this domain. The reported speedups are the corrected results that exclude the invalid speedups admitted by the original validation of Gai et al. (2026). Method Geo. mean Median L1 L2 L3 MCTS (optimized) 4.15×4.15× 3.09×3.09× 3.68×3.68× 5.04×5.04× 3.69×3.69× ExTS 4.36×4.36× 3.81×3.81× 3.76×3.76× 5.25×5.25× 4.30×4.30× Appendix I Worked Example: The Virtual Child Setup. The numbers are taken from a real default-config ExTS run on HotpotQA (seed 0, Qwen3-8B) and computed exactly as in Equations 7 and 8 and Algorithm 1. We reconstruct the iteration where the run’s best candidate (score 68.6768.67) is created: at iteration 104 the search descends root→v1→v3→v7root→ v_1→ v_3→ v_7 and expands the leaf v7v_7. At that point the global score range is [50.33,65.0][50.33,65.0] (68.6768.67 does not yet exist, being the child about to be created) and the defaults apply (T=0.3T\!=\!0.3, α=2α\!=\! 2, C=1.0C\!=\!1.0, PUCT with parent exponent 0.50.5). We show the virtual-child comparison at the pivotal node v1v_1, which has nv=28n_v\!=\!28 visits, nv+=4n_v^+\!=\!4 successful visits (success rate 0.1430.143), score sv=52.33s_v\!=\!52.33, and a single child v3v_3 (n=24n\!=\!24, n+=3n^+\!=\!3, score 55.3355.33, rewards 62.33,60.67,65.0\62.33,60.67,65.0\). Best real child. The rewards of v3v_3 normalize and shape (Eq. 3) to 0.528,0.351,1.000\0.528,0.351,1.000\ with mean 0.6260.626; its success rate 3/=0.1253/24\!=\!0.125 gives (0.125)2=0.053(0.125) 2\!=\!0.053, so the exploitation term is 0.053⋅=0.0330.053· 0.626\!=\!0.033. With PUCT exploration C⋅nv/(1+nchild)=28/(1+24)=0.212C· n_v/(1+n_child)\!=\! 28/(1+24)\!=\!0.212, the total is ExUCT(v3)=0.245ExUCT(v_3)\!=\!0.245. Virtual child. The fair-share visit count (Eq. 7) is nfair=24/=24n_fair\!=\!24/1\!=\!24 and the sample size is k=round(nfair⋅nv+/nv)=round(24⋅0.143)=3k\!=\!round(n_fair· n_v^+/n_v)\!=\!round(24· 0.143)\!=\!3. The virtual child draws k=3k\!=\!3 scores from the parent’s pool (reward history plus svs_v), namely 55.33,62.33,60.67,65.0,52.33\55.33,62.33,60.67,65.0,52.33\ with shaped values 0.078,0.528,0.351,1.000,0.021\0.078,0.528,0.351,1.000,0.021\. Its exploration term is 28/(1+24)=0.212 28/(1+24)\!=\!0.212, so in expectation it scores (0.143)2⋅0.396+=0.237(0.143) 2· 0.396+0.212\!=\!0.237, just below the best real child at 0.2450.245. Decision and interpretation. The comparison is close, 0.2370.237 versus 0.2450.245, and turns on the shaped sample: widening wins only when the mean of the three draws exceeds about 0.520.52, which requires repeatedly drawing the two high pool entries (0.5280.528 and 1.0001.000). Enumerating all draws, this happens with probability 0.2560.256, so ExTS deepens into v3v_3 about three quarters of the time, and the descent continues through v3v_3 to the leaf v7v_7 whose expansion produces the global best of 68.6768.67. The virtual child’s exploration bonus, computed at the honest fair-share count nfair=24n_fair\!=\!24, does not on average overcome a maturing real child that already carries an exploitation signal, so the mechanism favors deepening the productive chain. A fixed first-play-urgency constant cannot make this comparison, as it sees neither the parent’s reward distribution nor the maturity of the existing children. The same close comparison recurs at the root (virtual 0.3720.372 versus best real 0.3810.381), while at v3v_3 itself widening is gated off (it is at the branching cap M0=3M_0\!=\!3 and below the widening visit threshold), so the search simply deepens into v3v_3’s least-visited child v7v_7. Appendix J Ethical Considerations and Broader Impact ExTS is a general-purpose tree-search policy that improves budget efficiency for LLM-based agentic search. As a search algorithm, it could in principle accelerate any agent-based system, including potentially harmful ones. However, the method itself does not introduce new capabilities beyond what existing LLM agents already possess; it only improves how evaluation budget is allocated among candidates. All experiments use publicly available benchmarks and models accessed through standard APIs. The molecular elucidation task involves deducing known structures from spectra rather than de novo generation of novel compounds. We do not foresee significant dual-use risks specific to this work beyond those inherent to general LLM agent research. Appendix K Artifact Documentation Table 15 documents the artifacts used in this work, their licenses, and whether our use is consistent with intended purpose. Table 15: Artifacts used, with licenses and intended-use consistency. Artifact Type License Consistent Use GEPA Framework MIT Yes TreeQuest Framework Apache 2.0 Yes AFlow Framework MIT Yes K-MSE Framework MIT Yes DSPy Framework MIT Yes vLLM Inference engine Apache 2.0 Yes RDKit Library BSD-3-Clause Yes ColBERTv2 Model MIT Yes Qwen3-8B Model Apache 2.0 Yes HotpotQA Dataset C BY-SA 4.0 Yes HoVeR Dataset MIT Yes DROP Dataset C BY-SA 4.0 Yes LiveCodeBench Benchmark MIT Yes MolPuzzle Dataset MIT Yes All frameworks are used as search harnesses into which we integrate ExTS, consistent with their intended purpose as research tools. Datasets and benchmarks are used for evaluation as intended by their creators. Models are accessed via their supported APIs or inference engines. Appendix L Use of AI Assistants We used AI assistants to refine the grammar of the paper’s text.