Exploit More, Explore Smarter for Budget-Constrained Agentic Search

# Exploit More, Explore Smarter for Budget-Constrained Agentic Search
Source: [https://arxiv.org/html/2608.23848](https://arxiv.org/html/2608.23848)
###### 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 introduceExTS, 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\.## 1Introduction

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](https://arxiv.org/html/2608.23848#bib.bib8);[Opsahl\-Ong et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib9)\), code generation\([Zhang et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib22);[Inoue et al\., 2026](https://arxiv.org/html/2608.23848#bib.bib17)\), tool\-augmented reasoning\([Yao et al\., 2022](https://arxiv.org/html/2608.23848#bib.bib20);[Schick et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib21)\), multi\-step planning\([Yao et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib10);[Besta et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib23)\), 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](https://arxiv.org/html/2608.23848#bib.bib11);[Madaan et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib3);[Zhou et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib12);[Qi et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib35);[Antoniades et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib36);[Zhang et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib33);[Hao et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib37);[Liu et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib1);[Li et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib34);[Fang et al\., 2026a](https://arxiv.org/html/2608.23848#bib.bib2)\)\. These systems retain linear search or standard UCT for selection and expansion \(Appendix[A](https://arxiv.org/html/2608.23848#A1)\), leaving substantial room for improvement in how budget is allocated within the tree\. On the search algorithm side, AB\-MCTS\([Inoue et al\., 2026](https://arxiv.org/html/2608.23848#bib.bib17)\)replaces UCT with Thompson sampling, GEPA\([Agrawal et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib8)\)uses Pareto\-frontier selection, and AFlow\([Zhang et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib31)\)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 introduceExTS111Code will be released at[https://github\.com/amazon\-science/ExTS](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](https://arxiv.org/html/2608.23848#S3.SS1)\) that produces effective selection signals when raw scores cluster narrowly; avirtual child heuristic\(Section[3\.2](https://arxiv.org/html/2608.23848#S3.SS2)\) that estimates expansion value by sampling from the parent’s reward history, making expansion a value\-of\-information \(VOI\) decision competing directly with deepening; andquality\-conditioned branching\(Section[3\.3](https://arxiv.org/html/2608.23848#S3.SS3)\) that restricts expansion to nodes whose score justifies the budget cost\. These mechanisms are inspired by classical MCTS ideas \(progressive widening\([Coulom, 2007](https://arxiv.org/html/2608.23848#bib.bib5)\), first\-play urgency\([Gelly and Wang, 2006](https://arxiv.org/html/2608.23848#bib.bib29)\), PUCT\([Rosin, 2011](https://arxiv.org/html/2608.23848#bib.bib25)\)\) and improve upon each for budget\-constrained agentic search \(Section[5\.3](https://arxiv.org/html/2608.23848#S5.SS3)\)\.

With a single fixed configuration across prompt optimization\([Yang et al\., 2018](https://arxiv.org/html/2608.23848#bib.bib14);[Jiang et al\., 2020](https://arxiv.org/html/2608.23848#bib.bib15)\), code generation\([Jain et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib16)\), molecular structure elucidation\([Zhuang et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib4)\), and agentic workflow optimization\([Dua et al\., 2019](https://arxiv.org/html/2608.23848#bib.bib32)\), 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 ortwohyperparameters based on pilot\-run diagnostics\. We additionally report diagnostics linking landscape structure to hyperparameter sensitivity, component ablations, budget\-scaling and tree\-shape analysis\.

## 2Preliminaries

### 2\.1Validation\-Heavy Search

We formalize validation\-heavy search as a tuple\(𝒮,𝒜,f,B\)\(\\mathcal\{S\},\\mathcal\{A\},f,B\)where𝒮\\mathcal\{S\}is the set of candidate solutions \(e\.g\., prompts, code, or plans\),𝒜:𝒮→𝒮\\mathcal\{A\}:\\mathcal\{S\}\\rightarrow\\mathcal\{S\}is a stochastic refinement operator powered by an LLM,f:𝒮→ℝ∪\{⊥\}f:\\mathcal\{S\}\\rightarrow\\mathbb\{R\}\\cup\\\{\\bot\\\}is a validation function that returns a score or failure, andBBis the total evaluation budget\. The search builds a tree𝒯\\mathcal\{T\}rooted at an initial candidatex0x\_\{0\}and the goal isarg⁡maxx∈𝒯​f​\(x\)\\arg\\max\_\{x\\in\\mathcal\{T\}\}f\(x\)within budgetBB\.

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](https://arxiv.org/html/2608.23848#A3)\)\. 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*σ^𝒜\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}is the normalized standard deviation offfacross independent refinements with the same input, quantifying the stochasticity of the LLM refinement operator\. The*normalized score deviation*σ^f\\hat\{\\sigma\}\_\{f\}is the standard deviation offfacross all successfully validated candidates in the completed tree, normalized to\[0,1\]\[0,1\]\. The*score drift*κ\\kappais 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*ρ\\rhois the fraction of refinement attempts whereffreturns⊥\\bot\. Table[1](https://arxiv.org/html/2608.23848#S2.T1)characterizes the datasets we study along these axes\.

Table 1:Pilot\-run diagnostics \(mean±\\pmstd, 3 seeds\)\.σ^𝒜\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}: refinement variance;σ^f\\hat\{\\sigma\}\_\{f\}: score spread;κ\\kappa: score drift;ρ\\rho: failure rate\.
### 2\.2Standard MCTS and Its Limitations

In standard MCTS, the UCT policy\([Kocsis and Szepesvári, 2006](https://arxiv.org/html/2608.23848#bib.bib6)\)selects childccof nodevvby maximizing

UCTstd​\(c\)=Rcnc\+C​ln⁡nvnc\\text\{UCT\}\_\{\\text\{std\}\}\(c\)=\\frac\{R\_\{c\}\}\{n\_\{c\}\}\+C\\sqrt\{\\frac\{\\ln n\_\{v\}\}\{n\_\{c\}\}\}\(1\)whereRc/ncR\_\{c\}/n\_\{c\}is the average reward,ncn\_\{c\}andnvn\_\{v\}are visit counts, andCCcontrols exploration\. The theoretical defaultC=2C=\\sqrt\{2\}is calibrated for rewards in\[0,1\]\[0,1\]with sufficient budget for convergence\([Browne et al\., 2012](https://arxiv.org/html/2608.23848#bib.bib7)\)\.

Two assumptions underlying UCT are violated in validation\-heavy search\. First, reward shaping \(Section[3\.1](https://arxiv.org/html/2608.23848#S3.SS1)\) 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](https://arxiv.org/html/2608.23848#bib.bib24);[Browne et al\., 2012](https://arxiv.org/html/2608.23848#bib.bib7);[Kocsis and Szepesvári, 2006](https://arxiv.org/html/2608.23848#bib.bib6)\)\. Together, these violations produce flat, wide trees that fail to develop deep refinement chains\. The PUCT exploration term \(Section[3\.1](https://arxiv.org/html/2608.23848#S3.SS1)\) 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](https://arxiv.org/html/2608.23848#S5.SS3)\)\. Progressive widening\([Coulom, 2007](https://arxiv.org/html/2608.23848#bib.bib5);[Chaslot et al\., 2008](https://arxiv.org/html/2608.23848#bib.bib30)\)ties branching to visit count but is score\-agnostic\. First\-play urgency \(FPU\)\([Gelly and Wang, 2006](https://arxiv.org/html/2608.23848#bib.bib29)\)assigns a fixed value to unvisited actions but cannot adapt to non\-stationary score distributions\. PUCT\([Rosin, 2011](https://arxiv.org/html/2608.23848#bib.bib25);[Silver et al\., 2017](https://arxiv.org/html/2608.23848#bib.bib26)\)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\.

## 3Methodology

*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](https://arxiv.org/html/2608.23848#S5.SS1)\)\. 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 nodevvstores a candidatexv∈𝒮x\_\{v\}\\in\\mathcal\{S\}and maintains:nvn\_\{v\}\(total visits\),nv\+n\_\{v\}^\{\+\}\(successful visits\),ℛv\\mathcal\{R\}\_\{v\}\(reward observations from successful expansions invv’s subtree\), andsv=f⁡\(xv\)s\_\{v\}=f\(x\_\{v\}\)\(validation score\)\. The reward poolℛv\\mathcal\{R\}\_\{v\}implements mean backup: ExUCT\(v\)\(v\)estimates the refinement productivity of expanding belowvv, not the quality ofvv’s own candidate\. Figure[1](https://arxiv.org/html/2608.23848#S0.F1)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](https://arxiv.org/html/2608.23848#alg2)\(Appendix[B](https://arxiv.org/html/2608.23848#A2)\)\.

### 3\.1Discriminative 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 nodevv\(nv\>0n\_\{v\}\>0\) as:

ExUCT​\(v\)\\displaystyle\\text\{ExUCT\}\(v\)=\(nv\+nv\)α⋅φ⁡\(ri\)¯\\displaystyle=\\left\(\\frac\{n\_\{v\}^\{\+\}\}\{n\_\{v\}\}\\right\)^\{\\alpha\}\\\!\\cdot\\\!\\overline\{\\varphi\(r\_\{i\}\)\}\+explore​\(npar⁡\(v\),nv\)\\displaystyle\\quad\+\\text\{explore\}\(n\_\{\\mathrm\{par\}\(v\)\},\\;n\_\{v\}\)\(2\)The exploitation term combines two signals: the shaped rewardsφ⁡\(ri\)¯\\overline\{\\varphi\(r\_\{i\}\)\}, which separate candidates when raw scores cluster narrowly, and a success\-rate weight\(nv\+/nv\)α\(n\_\{v\}^\{\+\}/n\_\{v\}\)^\{\\alpha\}, which discounts nodes whose subtrees produce mostly invalid outputs \(α\\alphacontrols failure discounting\)\. The shaping functionφ\\varphimaps raw scores through*global*normalization and a temperature\-controlled nonlinearity:

φ⁡\(r\)=er^/T−1e1/T−1,r^=r−sminsmax−smin,\\varphi\(r\)=\\frac\{e^\{\\,\\hat\{r\}/T\}\-1\}\{e^\{1/T\}\-1\},\\quad\\hat\{r\}=\\frac\{r\-s\_\{\\min\}\}\{s\_\{\\max\}\-s\_\{\\min\}\},\(3\)φ⁡\(ri\)¯=1\|ℛv\|​∑ri∈ℛvφ⁡\(ri\)\.\\overline\{\\varphi\(r\_\{i\}\)\}=\\frac\{1\}\{\|\\mathcal\{R\}\_\{v\}\|\}\\sum\_\{r\_\{i\}\\in\\mathcal\{R\}\_\{v\}\}\\varphi\(r\_\{i\}\)\.\(4\)ForT<1T<1,φ\\varphiis 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\. TheUCTvariant decays logarithmically:

exploreUCT​\(npar,nv\)=C​ln⁡nparnv,\\text\{explore\}\_\{\\text\{UCT\}\}\(n\_\{\\text\{par\}\},n\_\{v\}\)=C\\sqrt\{\\frac\{\\ln n\_\{\\text\{par\}\}\}\{n\_\{v\}\}\},\(5\)while thePUCT\-stylevariant decays linearly, providing faster convergence toward exploitation under tight budgets:

explorePUCT​\(npar,nv\)=C⋅npar1\+nv\.\\text\{explore\}\_\{\\text\{PUCT\}\}\(n\_\{\\text\{par\}\},n\_\{v\}\)=C\\cdot\\frac\{\\sqrt\{n\_\{\\text\{par\}\}\}\}\{1\+n\_\{v\}\}\.\(6\)Unlike standard PUCT\([Rosin, 2011](https://arxiv.org/html/2608.23848#bib.bib25);[Silver et al\., 2017](https://arxiv.org/html/2608.23848#bib.bib26)\), which incorporates a learned policy priorP⁡\(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 withC=1\.0C\\\!=\\\!1\.0; we evaluate the UCT variant \(C=2C\\\!=\\\!\\sqrt\{2\}\) as an ablation in Section[5\.3](https://arxiv.org/html/2608.23848#S5.SS3)\.

### 3\.2VOI 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 nodevvwithmmexisting children, ifvvcan 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\_\{\\text\{fair\}\}=\\max\\\!\\left\(1,\\;\{\\color\[rgb\]\{0,0,0\}\\frac\{\\textstyle\\sum\_\{c\\in\\mathrm\{children\}\(v\)\}n\_\{c\}\}\{m\}\}\\right\)\.\(7\)We then samplek=max⁡\(1,⌊nfair⋅nv\+/nv⌋\)k=\\max\(1,\\lfloor n\_\{\\text\{fair\}\}\\cdot n\_\{v\}^\{\+\}/n\_\{v\}\\rfloor\)scores with replacement from the parent’s reward poolℛv∪\{sv\}\\mathcal\{R\}\_\{v\}\\cup\\\{s\_\{v\}\\\}and compute the estimated shaped meanφ⁡\(r~\)¯\\overline\{\\varphi\(\\tilde\{r\}\)\}\. The virtual child score mirrors Equation[2](https://arxiv.org/html/2608.23848#S3.Ex1):

ExUCTvirt=\(nv\+nv\)α⋅φ⁡\(r~\)¯\+explore​\(nv,nfair\)\.\\text\{ExUCT\}\_\{\\text\{virt\}\}=\\Bigl\(\\frac\{n\_\{v\}^\{\+\}\}\{n\_\{v\}\}\\Bigr\)^\{\\\!\\alpha\}\\\!\\cdot\\,\\overline\{\\varphi\(\\tilde\{r\}\)\}\\;\+\\;\\text\{explore\}\(n\_\{v\},n\_\{\\text\{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\.

Letc∗=arg⁡maxcj​ExUCT​\(cj\)c^\{\*\}=\\arg\\max\_\{c\_\{j\}\}\\text\{ExUCT\}\(c\_\{j\}\)be the best real child\. IfExUCTvirtual\>ExUCT​\(c∗\)\\text\{ExUCT\}\_\{\\text\{virtual\}\}\>\\text\{ExUCT\}\(c^\{\*\}\), the node is selected for expansion; otherwise selection recurses intoc∗c^\{\*\}\.Appendix[I](https://arxiv.org/html/2608.23848#A9)works through this comparison on a real run\.

### 3\.3Quality\-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τ\\tau\-quantile of the population:

sv≥Qτ​\(\{su:u∈𝒯\}\)\.s\_\{v\}\\geq Q\_\{\\tau\}\\bigl\(\\\{s\_\{u\}:u\\in\\mathcal\{T\}\\\}\\bigr\)\.\(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](https://arxiv.org/html/2608.23848#bib.bib5);[Chaslot et al\., 2008](https://arxiv.org/html/2608.23848#bib.bib30)\)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\}\+\\bigl\\lfloor\\log\_\{b\}\\\!\\tfrac\{n\_\{v\}\}\{n\_\{0\}\}\\bigr\\rfloor\\cdot\\mathbbm\{1\}\\bigl\[s\_\{v\}\\geq Q\_\{\\gamma\}\\lor v=v\_\{\\text\{root\}\}\\bigr\],\(10\)whereM0M\_\{0\}is the initial maximum children,bbis the widening base,n0n\_\{0\}is the visit threshold before widening begins, andQγQ\_\{\\gamma\}is theγ\\gamma\-quantile of node scores\. Typicallyγ≫τ\\gamma\\gg\\tau\(defaults:γ=0\.75\\gamma=0\.75,τ=0\.25\\tau=0\.25\), reflecting that widening is a stronger commitment than a single expansion\. Low\-scoring nodes remain capped atM0M\_\{0\}\.

Algorithm 1ExUCT\-Select: Selection with Virtual Child0:Node

vv
1:if

vvis a leafthen

2:return

vv
3:endif

4:

can\_expand←\|children​\(v\)\|<M⁡\(v\)\\text\{can\\\_expand\}\\leftarrow\|\\text\{children\}\(v\)\|<M\(v\)
5:if

v≠rootv\\neq\\text\{root\}and can\_expandthen

6:can\_expand

←sv≥Qτ​\(\{su:u∈𝒯\}\)\\leftarrow s\_\{v\}\\geq Q\_\{\\tau\}\(\\\{s\_\{u\}:u\\in\\mathcal\{T\}\\\}\)
7:endif

8:

c∗←arg⁡maxc∈children​\(v\)​ExUCT​\(c\)c^\{\*\}\\leftarrow\\arg\\max\_\{c\\in\\text\{children\}\(v\)\}\\text\{ExUCT\}\(c\)
9:ifcan\_expandthen

10:

m←\|children​\(v\)\|m\\leftarrow\|\\text\{children\}\(v\)\|
11:

nfair←max⁡\(1,∑cnc/m\)n\_\{\\text\{fair\}\}\\leftarrow\\max\\bigl\(1,\\;\{\\color\[rgb\]\{0,0,0\}\\sum\_\{c\}n\_\{c\}/m\}\\bigr\)
12:

k←max⁡\(1,⌊nfair⋅nv\+/nv⌋\)k\\leftarrow\\max\(1,\\lfloor n\_\{\\text\{fair\}\}\\cdot n\_\{v\}^\{\+\}/n\_\{v\}\\rfloor\)
13:Sample

r~1,…,r~k∼ℛv∪\{sv\}\\tilde\{r\}\_\{1\},\\ldots,\\tilde\{r\}\_\{k\}\\sim\\mathcal\{R\}\_\{v\}\\cup\\\{s\_\{v\}\\\}with replacement

14:

q←\(nv\+/nv\)α⋅1k∑iφ\(r~i\)q\\leftarrow\(n\_\{v\}^\{\+\}/n\_\{v\}\)^\{\\alpha\}\\cdot\\frac\{1\}\{k\}\\sum\_\{i\}\\varphi\(\\tilde\{r\}\_\{i\}\)
15:

ExUCTvirtual←q\+explore​\(nv,nfair\)\\text\{ExUCT\}\_\{\\text\{virtual\}\}\\leftarrow q\+\\text\{explore\}\(n\_\{v\},n\_\{\\text\{fair\}\}\)
16:if

ExUCTvirtual\>ExUCT​\(c∗\)\\text\{ExUCT\}\_\{\\text\{virtual\}\}\>\\text\{ExUCT\}\(c^\{\*\}\)then

17:return

vvexpand here

18:endif

19:endif

20:returnExUCT\-Select\(

c∗c^\{\*\}\)

#### Gate semantics\.

The expansion gate \(Algorithm[1](https://arxiv.org/html/2608.23848#alg1), 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\.

## 4Evaluation

We evaluate ExTS across four domains spanning diverse failure rates, score variances, and drift levels \(Table[1](https://arxiv.org/html/2608.23848#S2.T1)\)\. All methods share the same evaluation budgetBBper task\. ExTS uses a single fixed configuration across all domains \(Table[10](https://arxiv.org/html/2608.23848#A2.T10)\); 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](https://arxiv.org/html/2608.23848#A4)\.

### 4\.1Prompt Optimization

Table 2:Prompt optimization: test accuracy \(%\) over 3 seeds\.†Results from[Agrawal et al\. \(2025\)](https://arxiv.org/html/2608.23848#bib.bib8)\.∗Pilot\-adapted \(Section[5\.2](https://arxiv.org/html/2608.23848#S5.SS2)\)\.We integrate ExTS into the GEPA framework\([Agrawal et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib8)\)for optimizing DSPy\([Khattab et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib13)\)instructions on HotpotQA\([Yang et al\., 2018](https://arxiv.org/html/2608.23848#bib.bib14)\)and HoVeR\([Jiang et al\., 2020](https://arxiv.org/html/2608.23848#bib.bib15)\)\(300 test examples, 3 seeds, Qwen3\-8B\)\. This domain has the highest failure rate \(ρ=0\.74\\rho=0\.74–0\.820\.82\) among our tasks\.

Table[2](https://arxiv.org/html/2608.23848#S4.T2)shows that ExTS improves over GEPA Pareto by\+\+10\.8% on HotpotQA with6\.4×6\.4\\timeslower variance\. The pilot\-adapted ExTS∗further improves to 66\.00% by increasing the success\-rate exponent toα=2\.0\\alpha\\\!=\\\!2\.0, which sharpens node selection in this high\-failure\-rate domain \(ρ=0\.74\\rho=0\.74; Section[5\.2](https://arxiv.org/html/2608.23848#S5.SS2)\)\. On HoVeR, ExTS performs on par with GEPA Pareto \(\+\+0\.2%, within noise\)\. HoVeR exhibits the highest score drift \(κ=0\.16\\kappa=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](https://arxiv.org/html/2608.23848#S5.SS2)\)\.

### 4\.2Code Generation

Figure 2:LiveCodeBench pass@1 \(%\) over 3 seeds\.We integrate ExTS into the TreeQuest framework\([Inoue et al\., 2026](https://arxiv.org/html/2608.23848#bib.bib17)\)on LiveCodeBench\([Jain et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib16)\)\(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](https://arxiv.org/html/2608.23848#S4.F2)\)\.

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\.3Molecular 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](https://arxiv.org/html/2608.23848#S5.SS2)\)\.We apply ExTS to K\-MSE\([Zhuang et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib4)\), 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](https://arxiv.org/html/2608.23848#S4.T3)\)\. 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\.4Agentic Workflow Optimization

Table 4:Workflow optimization on DROP \(F1×\\times100, 3 seeds\)\.∗Pilot\-adapted \(Section[5\.2](https://arxiv.org/html/2608.23848#S5.SS2)\)\.We evaluate ExTS on DROP\([Dua et al\., 2019](https://arxiv.org/html/2608.23848#bib.bib32)\)within the AFlow framework\([Zhang et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib31)\), 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](https://arxiv.org/html/2608.23848#S4.T4)\)\. 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\.

## 5Understanding ExTS

### 5\.1The Exploration Constant Is Not Enough

A natural question is whether simply tuning the exploration constantCCin standard MCTS could replicate ExTS’s gains\. On LiveCodeBench \(Figure[2](https://arxiv.org/html/2608.23848#S4.F2)\), sweepingCCfrom 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\. LoweringCCshifts budget toward exploitation but still expands unpromising nodes unconditionally; raisingCCbroadens 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\.2Pilot\-Run Findings

We examine how pilot\-run diagnostics \(Table[1](https://arxiv.org/html/2608.23848#S2.T1)\) 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](https://arxiv.org/html/2608.23848#S4.T2),[3](https://arxiv.org/html/2608.23848#S4.T3),[4](https://arxiv.org/html/2608.23848#S4.T4)and Figure[2](https://arxiv.org/html/2608.23848#S4.F2)\)\.Appendix[G](https://arxiv.org/html/2608.23848#A7)condenses these findings into a compact diagnostic guide \(Table[13](https://arxiv.org/html/2608.23848#A7.T13)\)\.Three patterns emerge\.

#### Lowσ^𝒜\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}/lowκ\\kappaor unstable validation→\\rightarrowsoftenTT\.

When refinement variance and drift are both low, scores cluster tightly and aggressive exploitation \(lowTT\) over\-commits to gaps that may not predict test improvement\. RelaxingTTto 0\.5 hedges against this\. On K\-MSE \(σ^𝒜=0\.09\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}\\\!=\\\!0\.09,κ=0\.05\\kappa\\\!=\\\!0\.05\),T=0\.5T\\\!=\\\!0\.5yields 91\.2% ACC \(\+\+0\.2 pp; Table[3](https://arxiv.org/html/2608.23848#S4.T3)\)\. On DROP \(σ^𝒜=0\.04\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}\\\!=\\\!0\.04,κ=0\.02\\kappa\\\!=\\\!0\.02\), raisingτ=0\.5\\tau\\\!=\\\!0\.5withM0=4M\_\{0\}\\\!=\\\!4yields 91\.54 F1 \(\+\+0\.58 pp; Table[4](https://arxiv.org/html/2608.23848#S4.T4)\)\. LiveCodeBench \(σ^𝒜=0\.32\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}\\\!=\\\!0\.32,κ=0\.14\\kappa\\\!=\\\!0\.14\) does not exhibit this signature, yet also benefits fromT=0\.5T\\\!=\\\!0\.5\(47\.4%,\+\+1\.2 pp; Figure[2](https://arxiv.org/html/2608.23848#S4.F2)\) 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, moderateTT\-softening improves performance when the validation scorer is a weak proxy for the true metric\.

#### High score drift \(κ\\kappa\)→\\rightarrowearly exploration\.

Highκ\\kappameans 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\\tau\_\{\\text\{gate\}\}\\\!=\\\!0\) avoids blocking potentially good parents based on transiently low scores\. On HoVeR \(κ=0\.16\\kappa=0\.16, highest\), switching to UCT withτgate=0\\tau\_\{\\text\{gate\}\}\\\!=\\\!0yields 51\.67% \(\+\+1\.22 pp,2\.2×2\.2\\timeslower variance; Table[2](https://arxiv.org/html/2608.23848#S4.T2)\)\. Conversely, HotpotQA \(κ=0\.11\\kappa=0\.11\) strongly prefers PUCT \(\+\+6\.45 pp over UCT; Table[7](https://arxiv.org/html/2608.23848#S5.T7)\), where fast decay concentrates budget on chains whose rankings are stable enough to trust\.

#### High failure rate \(ρ\\rho\)→\\rightarrowsensitive toα\\alpha\.

Intuitively, when most expansions fail, the success\-rate exponentα\\alphabecomes critical for separating productive nodes from unproductive ones\. We verify this on HotpotQA \(ρ=0\.74\\rho=0\.74\): settingα=2\.0\\alpha\\\!=\\\!2\.0yields 66\.00% \(\+\+1\.11 pp; Table[2](https://arxiv.org/html/2608.23848#S4.T2)\), while reducingα\\alphato 1\.0 causes−\-7\.78 pp with6\.8×6\.8\\timeshigher variance \(Table[5](https://arxiv.org/html/2608.23848#S5.T5)\)\. In low\-failure tasks,α\\alphahas negligible effect\.

### 5\.3Ablation Studies

We isolate each design choice via leave\-one\-out ablation on HotpotQA \(highρ\\rho, highκ\\kappa\)\. LiveCodeBench ablations are in Table[12](https://arxiv.org/html/2608.23848#A6.T12)\(Appendix[F](https://arxiv.org/html/2608.23848#A6)\)\.

Table 5:Leave\-one\-out ablation on HotpotQA \(3 seeds\)\. LiveCodeBench ablations in Table[12](https://arxiv.org/html/2608.23848#A6.T12)\.Table[5](https://arxiv.org/html/2608.23848#S5.T5)confirms that all components contribute\. Failure penalty has the largest impact \(−\-7\.78 pp\), followed by the virtual child \(−\-3\.22 pp\); without the latter, the algorithm reverts to wide\-tree behavior\. Gated progressive widening contributes−\-2\.34 pp by restricting expansion to nodes whose quality justifies the budget cost\.

#### Classical mechanisms do not transfer directly\.

Table[6](https://arxiv.org/html/2608.23848#S5.T6)replaces ExTS components with their classical counterparts: fixed FPU\([Gelly and Wang, 2006](https://arxiv.org/html/2608.23848#bib.bib29)\)instead of the virtual child, and score\-agnostic progressive widening\([Coulom, 2007](https://arxiv.org/html/2608.23848#bib.bib5)\)instead of quality\-gated widening\. On DROP, both FPU constants underperform ExTS \(−\-2\.0 pp and−\-1\.6 pp\), and the gap between FPU=0\.5\\,\{=\}\\,0\.5and FPU=0\.8\\,\{=\}\\,0\.8\(\+\+0\.4 pp\) illustrates a fundamental limitation: fixed FPU is sensitive to the constant’s value, which interacts with explorationCC, shaping temperatureTT, 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\)\.
#### Exploration type: PUCT vs\. UCT\.

Table[7](https://arxiv.org/html/2608.23848#S5.T7)compares the default PUCT \(linear decay\) against UCT \(logarithmic decay\)\. HotpotQA strongly prefers PUCT \(\+\+6\.45 pp\), where fast decay concentrates budget on proven chains\. HoVeR prefers UCT \(\+\+0\.88 pp\), where sustained exploration buffers against score drift\. This task\-dependent sensitivity motivates the diagnostic analysis in Section[5\.2](https://arxiv.org/html/2608.23848#S5.SS2)\.

Table 7:Exploration type ablation: PUCT \(default\) vs\. UCT, 3 seeds\.

### 5\.4Tree\-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](https://arxiv.org/html/2608.23848#A5.SS0.SSS0.Px1)\.

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\.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 pp ACC on the non\-trivial subset \(80\.1% vs\. 77\.2%\), where the overall\+\+1\.2 pp 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\.5Budget\-Scaling Behavior

We measure performance as a function of evaluation budgetBBacross LiveCodeBench, HotpotQA, and K\-MSE \(setup details in Appendix[E](https://arxiv.org/html/2608.23848#A5.SS0.SSS0.Px2)\)\.

Figure 3:Budget\-scaling behavior across three domains, averaged over 3 seeds \(±1​σ\\pm 1\\sigmabands\)\. 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](https://arxiv.org/html/2608.23848#S5.F3)shows that ExTS converts budget into performance more efficiently across all domains\. On LiveCodeBench, ExTS trails atB=1B\{=\}1\(all methods reduce to a single sample\) but overtakes Standard MCTS atB≈8B\{\\approx\}8and reaches 46\.2% vs\. 45\.6% \(Standard\) and 45\.4% \(AB\-MCTS\) atB=128B\{=\}128; on hard problems the gap widens to19\.1% vs\. 17\.1% \(AB\-MCTS\)\. On HotpotQA, ExTS reaches 64\.9% atB=70B\{=\}70versus 58\.0% for GEPA Pareto with tighter confidence intervals\. On K\-MSE, ExTS leads fromB=1B\{=\}1onward and maintains a growing gap \(72\.5 vs\. 71\.8 atB=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\.5pp fromB=1B\{=\}1toB=32B\{=\}32vs\.\+3\.7\+3\.7pp for MCTS\) confirms that the advantage concentrates where search depth matters most\.

## 6Conclusion

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](https://arxiv.org/html/2608.23848#A8)\)\.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

- Agrawalet 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](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p3.1),[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px3.p1.1.1),[§D\.1](https://arxiv.org/html/2608.23848#A4.SS1.p1.1),[§D\.1](https://arxiv.org/html/2608.23848#A4.SS1.p3.1),[§1](https://arxiv.org/html/2608.23848#S1.p1.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1),[§4\.1](https://arxiv.org/html/2608.23848#S4.SS1.p1.1),[Table 2](https://arxiv.org/html/2608.23848#S4.T2)\.
- Antoniadeset al\.\(2025\)A\. Antoniades, A\. Örwall, K\. Zhang, Y\. Xie, A\. Goyal, and W\. WangSWE\-search: enhancing software agents with monte carlo tree search and iterative refinement\.External Links:2410\.20285,[Link](https://arxiv.org/abs/2410.20285)Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1)\.
- Bestaet 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\.InProceedings of the AAAI conference on artificial intelligence,Vol\.38,pp\. 17682–17690\.Cited by:[§1](https://arxiv.org/html/2608.23848#S1.p1.1)\.
- Brownet al\.\(2024\)B\. Brown, J\. Juravsky, R\. Ehrlich, R\. Clark, Q\. V\. Le, C\. Ré, and A\. MirhoseiniLarge language monkeys: scaling inference compute with repeated sampling\.External Links:2407\.21787,[Link](https://arxiv.org/abs/2407.21787)Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px2.p1.1)\.
- Browneet 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\. ColtonA survey of monte carlo tree search methods\.IEEE Transactions on Computational Intelligence and AI in games4\(1\),pp\. 1–43\.Cited by:[§2\.2](https://arxiv.org/html/2608.23848#S2.SS2.p1.2),[§2\.2](https://arxiv.org/html/2608.23848#S2.SS2.p2.1)\.
- Chaslotet al\.\(2008\)G\. M\. J\. Chaslot, M\. H\. Winands, H\. J\. v\. d\. Herik, J\. W\. Uiterwijk, and B\. BouzyProgressive strategies for monte\-carlo tree search\.New Mathematics and Natural Computation4\(03\),pp\. 343–357\.Cited by:[§2\.2](https://arxiv.org/html/2608.23848#S2.SS2.SSS0.Px1.p1.1),[§3\.3](https://arxiv.org/html/2608.23848#S3.SS3.SSS0.Px2.p1.1)\.
- Coulom \(2007\)R\. CoulomComputing “elo ratings” of move patterns in the game of go\.ICGA journal30\(4\),pp\. 198–208\.Cited by:[§1](https://arxiv.org/html/2608.23848#S1.p3.1),[§2\.2](https://arxiv.org/html/2608.23848#S2.SS2.SSS0.Px1.p1.1),[§3\.3](https://arxiv.org/html/2608.23848#S3.SS3.SSS0.Px2.p1.1),[§5\.3](https://arxiv.org/html/2608.23848#S5.SS3.SSS0.Px1.p1.1)\.
- Duaet al\.\(2019\)D\. Dua, Y\. Wang, P\. Dasigi, G\. Stanovsky, S\. Singh, and M\. GardnerDROP: a reading comprehension benchmark requiring discrete reasoning over paragraphs\.InProceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 \(Long and Short Papers\),pp\. 2368–2378\.Cited by:[§D\.4](https://arxiv.org/html/2608.23848#A4.SS4.p1.1),[§1](https://arxiv.org/html/2608.23848#S1.p4.1),[§4\.4](https://arxiv.org/html/2608.23848#S4.SS4.p1.1)\.
- Fanget 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 Systems38,pp\. 69001–69070\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1)\.
- Fanget 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](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1)\.
- Gaiet al\.\(2026\)J\. Gai, S\. Zhang, K\. Bostrom, J\. Huang, V\. Patil, H\. Fang, B\. Wang, H\. Rangwala, and G\. KarypisOptimizing 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](https://arxiv.org/html/2608.23848#A8.T14.2),[Table 14](https://arxiv.org/html/2608.23848#A8.T14.3),[Appendix H](https://arxiv.org/html/2608.23848#A8.p1.1.1)\.
- Gelly and Wang \(2006\)S\. Gelly and Y\. WangExploration exploitation in go: uct for monte\-carlo go\.InNIPS: Neural Information Processing Systems Conference On\-line trading of Exploration and Exploitation Workshop,Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p4.1.1),[§1](https://arxiv.org/html/2608.23848#S1.p3.1),[§2\.2](https://arxiv.org/html/2608.23848#S2.SS2.SSS0.Px1.p1.1),[§5\.3](https://arxiv.org/html/2608.23848#S5.SS3.SSS0.Px1.p1.1)\.
- Guoet al\.\(2024\)K\. Guo, B\. Nan, Y\. Zhou, T\. Guo, Z\. Guo, M\. Surve, Z\. Liang, N\. V\. Chawla, O\. Wiest, and X\. ZhangCan llms solve molecule puzzles? a multimodal benchmark for molecular structure elucidation\.InAdvances in Neural Information Processing Systems,A\. Globerson, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. Tomczak, and C\. Zhang \(Eds\.\),Vol\.37,pp\. 134721–134746\.External Links:[Document](https://dx.doi.org/10.52202/079017-4281),[Link](https://proceedings.neurips.cc/paper_files/paper/2024/file/f2b9e8e7a36d43ddfd3d55113d56b1e0-Paper-Datasets_and_Benchmarks_Track.pdf)Cited by:[§D\.3](https://arxiv.org/html/2608.23848#A4.SS3.p1.1)\.
- Haoet al\.\(2023\)S\. Hao, Y\. Gu, H\. Ma, J\. J\. Hong, Z\. Wang, D\. Z\. Wang, and Z\. HuReasoning with language model is planning with world model\.External Links:2305\.14992,[Link](https://arxiv.org/abs/2305.14992)Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1)\.
- Heet al\.\(2026\)Z\. He, H\. Lin, B\. Han, W\. Zhu, H\. Fang, B\. Wang, X\. Zhu, R\. Li, and M\. ReimherrReSkill: reconciling skill creation with policy optimization in agentic rl\.arXiv preprint arXiv:2606\.01619\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px4.p1.1.1)\.
- Inoueet al\.\(2026\)Y\. Inoue, K\. Misaki, Y\. Imajuku, S\. Kuroki, T\. Nakamura, and T\. AkibaWider or deeper? scaling llm inference\-time compute with adaptive branching tree search\.Advances in Neural Information Processing Systems38,pp\. 35448–35484\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p3.1),[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p4.1.1),[§D\.2](https://arxiv.org/html/2608.23848#A4.SS2.p1.1),[§D\.2](https://arxiv.org/html/2608.23848#A4.SS2.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p1.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1),[§4\.2](https://arxiv.org/html/2608.23848#S4.SS2.p1.1)\.
- Jainet al\.\(2024\)N\. Jain, K\. Han, A\. Gu, W\. Li, F\. Yan, T\. Zhang, S\. Wang, A\. Solar\-Lezama, K\. Sen, and I\. StoicaLiveCodeBench: holistic and contamination free evaluation of large language models for code\.External Links:2403\.07974,[Link](https://arxiv.org/abs/2403.07974)Cited by:[§D\.2](https://arxiv.org/html/2608.23848#A4.SS2.p1.1),[§1](https://arxiv.org/html/2608.23848#S1.p4.1),[§4\.2](https://arxiv.org/html/2608.23848#S4.SS2.p1.1)\.
- Jianget al\.\(2020\)Y\. Jiang, S\. Bordia, Z\. Zhong, C\. Dognin, M\. Singh, and M\. BansalHoVer: a dataset for many\-hop fact extraction and claim verification\.InFindings of the Association for Computational Linguistics: EMNLP 2020,pp\. 3441–3460\.Cited by:[§D\.1](https://arxiv.org/html/2608.23848#A4.SS1.p1.1),[§1](https://arxiv.org/html/2608.23848#S1.p4.1),[§4\.1](https://arxiv.org/html/2608.23848#S4.SS1.p1.1)\.
- Khattabet 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](https://arxiv.org/html/2608.23848#A4.SS1.p1.1),[§4\.1](https://arxiv.org/html/2608.23848#S4.SS1.p1.1)\.
- Kocsis and Szepesvári \(2006\)L\. Kocsis and C\. SzepesváriBandit based monte\-carlo planning\.InEuropean conference on machine learning,pp\. 282–293\.Cited by:[§2\.2](https://arxiv.org/html/2608.23848#S2.SS2.p1.1),[§2\.2](https://arxiv.org/html/2608.23848#S2.SS2.p2.1)\.
- Kwonet al\.\(2023\)W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. E\. Gonzalez, H\. Zhang, and I\. StoicaEfficient memory management for large language model serving with pagedattention\.External Links:2309\.06180,[Link](https://arxiv.org/abs/2309.06180)Cited by:[§D\.1](https://arxiv.org/html/2608.23848#A4.SS1.p1.1)\.
- Langeet al\.\(2026\)R\. Lange, Y\. Imajuku, and E\. CetinShinkaevolve: towards open\-ended and sample\-efficient program evolution\.InInternational Conference on Learning Representations,Vol\.2026,pp\. 74026–74078\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px3.p1.1.1)\.
- Liet al\.\(2025\)D\. Li, S\. Cao, C\. Cao, X\. Li, S\. Tan, K\. Keutzer, J\. Xing, J\. E\. Gonzalez, and I\. StoicaS\*: test time scaling for code generation\.External Links:2502\.14382,[Link](https://arxiv.org/abs/2502.14382)Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1)\.
- Liet al\.\(2018\)L\. Li, K\. Jamieson, G\. DeSalvo, A\. Rostamizadeh, and A\. TalwalkarHyperband: a novel bandit\-based approach to hyperparameter optimization\.External Links:1603\.06560,[Link](https://arxiv.org/abs/1603.06560)Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px2.p1.1)\.
- Liet al\.\(2026\)Y\. Li, W\. Deng, J\. Li, and X\. LiSpend less, reason better: budget\-aware value tree search for llm agents\.External Links:2603\.12634,[Link](https://arxiv.org/abs/2603.12634)Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p3.1)\.
- Liuet 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](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px3.p1.1.1)\.
- Liuet 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](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1)\.
- Madaanet 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 systems36,pp\. 46534–46594\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1)\.
- Opsahl\-Onget al\.\(2024\)K\. Opsahl\-Ong, M\. J\. Ryan, J\. Purtell, D\. Broman, C\. Potts, M\. Zaharia, and O\. KhattabOptimizing instructions and demonstrations for multi\-stage language model programs\.InProceedings of the 2024 Conference on Empirical Methods in Natural Language Processing,pp\. 9340–9366\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2608.23848#S1.p1.1)\.
- Qiet al\.\(2024\)Z\. Qi, M\. Ma, J\. Xu, L\. L\. Zhang, F\. Yang, and M\. YangMutual reasoning makes smaller llms stronger problem\-solvers\.External Links:2408\.06195,[Link](https://arxiv.org/abs/2408.06195)Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1)\.
- Rosin \(2011\)C\. D\. RosinMulti\-armed bandits with episode context\.Annals of Mathematics and Artificial Intelligence61\(3\),pp\. 203–230\.Cited by:[§1](https://arxiv.org/html/2608.23848#S1.p3.1),[§2\.2](https://arxiv.org/html/2608.23848#S2.SS2.SSS0.Px1.p1.1),[§3\.1](https://arxiv.org/html/2608.23848#S3.SS1.p2.3)\.
- Santhanamet al\.\(2022\)K\. Santhanam, O\. Khattab, J\. Saad\-Falcon, C\. Potts, and M\. ZahariaColbertv2: effective and efficient retrieval via lightweight late interaction\.InProceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,pp\. 3715–3734\.Cited by:[§D\.1](https://arxiv.org/html/2608.23848#A4.SS1.p1.1)\.
- Schicket al\.\(2023\)T\. Schick, J\. Dwivedi\-Yu, R\. Dessì, R\. Raileanu, M\. Lomeli, E\. Hambro, L\. Zettlemoyer, N\. Cancedda, and T\. ScialomToolformer: language models can teach themselves to use tools\.Advances in neural information processing systems36,pp\. 68539–68551\.Cited by:[§1](https://arxiv.org/html/2608.23848#S1.p1.1)\.
- Shinnet al\.\(2023\)N\. Shinn, F\. Cassano, A\. Gopinath, K\. Narasimhan, and S\. YaoReflexion: language agents with verbal reinforcement learning\.Advances in neural information processing systems36,pp\. 8634–8652\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1),[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px5.p1.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1)\.
- Silveret 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\.nature529\(7587\),pp\. 484–489\.Cited by:[§2\.2](https://arxiv.org/html/2608.23848#S2.SS2.p2.1)\.
- Silveret 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](https://arxiv.org/html/2608.23848#S2.SS2.SSS0.Px1.p1.1),[§3\.1](https://arxiv.org/html/2608.23848#S3.SS1.p2.3)\.
- Snellet al\.\(2024\)C\. Snell, J\. Lee, K\. Xu, and A\. KumarScaling llm test\-time compute optimally can be more effective than scaling model parameters\.External Links:2408\.03314,[Link](https://arxiv.org/abs/2408.03314)Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px2.p1.1)\.
- Wanget al\.\(2024\)X\. Wang, C\. Li, Z\. Wang, F\. Bai, H\. Luo, J\. Zhang, N\. Jojic, E\. Xing, and Z\. HuPromptagent: strategic planning with language models enables expert\-level prompt optimization\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 23967–24001\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1)\.
- Weiet al\.\(2023\)J\. Wei, X\. Wang, D\. Schuurmans, M\. Bosma, B\. Ichter, F\. Xia, E\. Chi, Q\. Le, and D\. ZhouChain\-of\-thought prompting elicits reasoning in large language models\.External Links:2201\.11903,[Link](https://arxiv.org/abs/2201.11903)Cited by:[§D\.3](https://arxiv.org/html/2608.23848#A4.SS3.p2.1)\.
- Yanget 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](https://arxiv.org/html/2608.23848#A4.SS1.p1.1)\.
- Yanget al\.\(2024\)C\. Yang, X\. Wang, Y\. Lu, H\. Liu, Q\. V\. Le, D\. Zhou, and X\. ChenLarge language models as optimizers\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 12028–12068\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px4.p1.1)\.
- Yanget al\.\(2018\)Z\. Yang, P\. Qi, S\. Zhang, Y\. Bengio, W\. Cohen, R\. Salakhutdinov, and C\. D\. ManningHotpotQA: a dataset for diverse, explainable multi\-hop question answering\.InProceedings of the 2018 conference on empirical methods in natural language processing,pp\. 2369–2380\.Cited by:[§D\.1](https://arxiv.org/html/2608.23848#A4.SS1.p1.1),[§1](https://arxiv.org/html/2608.23848#S1.p4.1),[§4\.1](https://arxiv.org/html/2608.23848#S4.SS1.p1.1)\.
- Yaoet al\.\(2023\)S\. Yao, D\. Yu, J\. Zhao, I\. Shafran, T\. Griffiths, Y\. Cao, and K\. NarasimhanTree of thoughts: deliberate problem solving with large language models\.Advances in neural information processing systems36,pp\. 11809–11822\.Cited by:[§1](https://arxiv.org/html/2608.23848#S1.p1.1)\.
- Yaoet al\.\(2022\)S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. Narasimhan, and Y\. CaoReact: synergizing reasoning and acting in language models\.arXiv preprint arXiv:2210\.03629\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px5.p1.1),[§1](https://arxiv.org/html/2608.23848#S1.p1.1)\.
- Zhanget 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\. ZhouLLaMA\-berry: pairwise optimization for o1\-like olympiad\-level mathematical reasoning\.External Links:2410\.02884,[Link](https://arxiv.org/abs/2410.02884)Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1)\.
- Zhanget 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\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 34040–34077\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p3.1),[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px6.p1.1),[1st item](https://arxiv.org/html/2608.23848#A4.I1.i1.p1.1),[§D\.4](https://arxiv.org/html/2608.23848#A4.SS4.p1.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1),[§4\.4](https://arxiv.org/html/2608.23848#S4.SS4.p1.1)\.
- Zhanget al\.\(2023\)S\. Zhang, Z\. Chen, Y\. Shen, M\. Ding, J\. B\. Tenenbaum, and C\. GanPlanning with large language models for code generation\.arXiv preprint arXiv:2303\.05510\.Cited by:[§1](https://arxiv.org/html/2608.23848#S1.p1.1)\.
- Zhouet al\.\(2023\)A\. Zhou, K\. Yan, M\. Shlapentokh\-Rothman, H\. Wang, and Y\. WangLanguage agent tree search unifies reasoning acting and planning in language models\.arXiv preprint arXiv:2310\.04406\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px1.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p2.1)\.
- Zhuanget al\.\(2025\)X\. Zhuang, B\. Wu, J\. Cui, K\. Feng, X\. Li, H\. Xing, K\. Ding, Q\. Zhang, and H\. ChenBoosting llm’s molecular structure elucidation with knowledge enhanced tree search reasoning\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),pp\. 22561–22576\.Cited by:[Appendix A](https://arxiv.org/html/2608.23848#A1.SS0.SSS0.Px7.p1.1),[§D\.3](https://arxiv.org/html/2608.23848#A4.SS3.p1.1),[§D\.3](https://arxiv.org/html/2608.23848#A4.SS3.p2.1),[§1](https://arxiv.org/html/2608.23848#S1.p4.1),[§4\.3](https://arxiv.org/html/2608.23848#S4.SS3.p1.1)\.

###### Contents

1. [1Introduction](https://arxiv.org/html/2608.23848#S1)
2. [2Preliminaries](https://arxiv.org/html/2608.23848#S2)1. [2\.1Validation\-Heavy Search](https://arxiv.org/html/2608.23848#S2.SS1) 2. [2\.2Standard MCTS and Its Limitations](https://arxiv.org/html/2608.23848#S2.SS2)
3. [3Methodology](https://arxiv.org/html/2608.23848#S3)1. [3\.1Discriminative Reward Shaping](https://arxiv.org/html/2608.23848#S3.SS1) 2. [3\.2VOI Estimation via the Virtual Child](https://arxiv.org/html/2608.23848#S3.SS2) 3. [3\.3Quality\-Conditioned Branching](https://arxiv.org/html/2608.23848#S3.SS3)
4. [4Evaluation](https://arxiv.org/html/2608.23848#S4)1. [4\.1Prompt Optimization](https://arxiv.org/html/2608.23848#S4.SS1) 2. [4\.2Code Generation](https://arxiv.org/html/2608.23848#S4.SS2) 3. [4\.3Molecular Structure Elucidation](https://arxiv.org/html/2608.23848#S4.SS3) 4. [4\.4Agentic Workflow Optimization](https://arxiv.org/html/2608.23848#S4.SS4)
5. [5Understanding ExTS](https://arxiv.org/html/2608.23848#S5)1. [5\.1The Exploration Constant Is Not Enough](https://arxiv.org/html/2608.23848#S5.SS1) 2. [5\.2Pilot\-Run Findings](https://arxiv.org/html/2608.23848#S5.SS2) 3. [5\.3Ablation Studies](https://arxiv.org/html/2608.23848#S5.SS3) 4. [5\.4Tree\-Shape Diagnostics](https://arxiv.org/html/2608.23848#S5.SS4) 5. [5\.5Budget\-Scaling Behavior](https://arxiv.org/html/2608.23848#S5.SS5)
6. [6Conclusion](https://arxiv.org/html/2608.23848#S6)
7. [References](https://arxiv.org/html/2608.23848#bib)
8. [ARelated Work](https://arxiv.org/html/2608.23848#A1)
9. [BDefault Configuration and Complete Algorithm](https://arxiv.org/html/2608.23848#A2)
10. [CFormal Definitions of Pilot\-Run Diagnostics](https://arxiv.org/html/2608.23848#A3)
11. [DDetailed Experimental Setup](https://arxiv.org/html/2608.23848#A4)1. [D\.1Prompt Optimization](https://arxiv.org/html/2608.23848#A4.SS1) 2. [D\.2Code Generation](https://arxiv.org/html/2608.23848#A4.SS2) 3. [D\.3Molecular Structure Elucidation](https://arxiv.org/html/2608.23848#A4.SS3) 4. [D\.4Agentic Workflow Optimization](https://arxiv.org/html/2608.23848#A4.SS4)
12. [EAnalysis Setup Details](https://arxiv.org/html/2608.23848#A5)
13. [FMore Ablations on LiveCodeBench](https://arxiv.org/html/2608.23848#A6)
14. [GCompact Diagnostic Guide](https://arxiv.org/html/2608.23848#A7)
15. [HFurther Evaluation on an Additional Domain: GPU Kernel Optimization](https://arxiv.org/html/2608.23848#A8)
16. [IWorked Example: The Virtual Child](https://arxiv.org/html/2608.23848#A9)
17. [JEthical Considerations and Broader Impact](https://arxiv.org/html/2608.23848#A10)
18. [KArtifact Documentation](https://arxiv.org/html/2608.23848#A11)
19. [LUse of AI Assistants](https://arxiv.org/html/2608.23848#A12)

## Appendix ARelated 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](https://arxiv.org/html/2608.23848#bib.bib11);[Madaan et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib3);[Fang et al\., 2026a](https://arxiv.org/html/2608.23848#bib.bib2);[Fang et al\., 2026b](https://arxiv.org/html/2608.23848#bib.bib47)\)\. LATS\([Zhou et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib12)\)integrates MCTS with LLM value functions and self\-reflection but does not modify the tree policy\. rStar\([Qi et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib35)\)defines rich reasoning actions with mutual verification between two SLMs\. RAP\([Hao et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib37)\)repurposes the LLM as a world model within standard MCTS\. SWE\-Search\([Antoniades et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib36)\)introduces a multi\-agent evaluation framework with a hybrid value function for software engineering tasks\. PromptAgent\([Wang et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib28)\)frames prompt optimization as MCTS\-style strategic planning with error feedback\. LLaMA\-Berry\([Zhang et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib33)\)replaces raw value estimates with pairwise preference aggregation for mathematical reasoning but retains standard UCT selection\. S\*\([Li et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib34)\)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](https://arxiv.org/html/2608.23848#bib.bib1)\)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](https://arxiv.org/html/2608.23848#bib.bib17)\)replaces UCT with Thompson sampling for code generation\. GEPA\([Agrawal et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib8)\)uses Pareto\-frontier selection over scored candidates for prompt optimization\. AFlow\([Zhang et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib31)\)applies score\-weighted random sampling from recent rounds for workflow optimization\. BAVT\([Li et al\., 2026](https://arxiv.org/html/2608.23848#bib.bib38)\)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](https://arxiv.org/html/2608.23848#bib.bib29)\)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](https://arxiv.org/html/2608.23848#bib.bib17)\)\(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](https://arxiv.org/html/2608.23848#A1.T9)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\)](https://arxiv.org/html/2608.23848#bib.bib39)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\-NNsampling\([Brown et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib41)\)generatesNNindependent 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](https://arxiv.org/html/2608.23848#bib.bib40)\)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\)\.
#### Evolutionary search for LLM systems\.

ShinkaEvolve\([Lange et al\., 2026](https://arxiv.org/html/2608.23848#bib.bib45)\)and EvoX\([Liu et al\., 2026](https://arxiv.org/html/2608.23848#bib.bib46)\)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](https://arxiv.org/html/2608.23848#bib.bib8)\), 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×\\timeslower 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\.

#### Promptand Skilloptimization\.

OPRO\([Yang et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib27)\)uses LLMs as optimizers over scored solution histories\. MIPROv2\([Opsahl\-Ong et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib9)\)applies Bayesian surrogate optimization to DSPy instruction tuning\.For skill optimization, ReSkill\([He et al\., 2026](https://arxiv.org/html/2608.23848#bib.bib49)\)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](https://arxiv.org/html/2608.23848#bib.bib11)\)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](https://arxiv.org/html/2608.23848#bib.bib20)\)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](https://arxiv.org/html/2608.23848#bib.bib31)\)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](https://arxiv.org/html/2608.23848#S4.SS4)\.

#### Molecular structure elucidation\.

K\-MSE\([Zhuang et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib4)\)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 BDefault Configuration and Complete Algorithm

Algorithm[2](https://arxiv.org/html/2608.23848#alg2)gives the complete ExTS search loop and Table[10](https://arxiv.org/html/2608.23848#A2.T10)lists the default hyperparameters used across all experiments\.

Algorithm 2ExTS: Complete Search Loop0:

x0x\_\{0\}, refinement operator

𝒜\\mathcal\{A\}, validator

ff, budget

BB
1:Initialize tree

𝒯\\mathcal\{T\}with root

v0v\_\{0\},

xv0←x0x\_\{v\_\{0\}\}\\leftarrow x\_\{0\},

sv0←f⁡\(x0\)s\_\{v\_\{0\}\}\\leftarrow f\(x\_\{0\}\)
2:whilebudget

BBnot exhausteddo

3:

v←ExUCT\-Select​\(v0\)v\\leftarrow\\textsc\{ExUCT\-Select\}\(v\_\{0\}\)Alg\.[1](https://arxiv.org/html/2608.23848#alg1)

4:

x′←𝒜⁡\(xv\)x^\{\\prime\}\\leftarrow\\mathcal\{A\}\(x\_\{v\}\)LLM refinement

5:

r←f⁡\(x′\)r\\leftarrow f\(x^\{\\prime\}\)
6:if

r=⊥r=\\botthen

7:Backprop\-Failure\(

vv\);continue

8:endif

9:Create child

uu:

xu←x′x\_\{u\}\\leftarrow x^\{\\prime\},

su←rs\_\{u\}\\leftarrow r
10:

children⁡\(v\)←children⁡\(v\)∪\{u\}\\mathrm\{children\}\(v\)\\leftarrow\\mathrm\{children\}\(v\)\\cup\\\{u\\\}
11:Backprop\-Success\(

vv,

rr\)

12:endwhile

13:return

arg⁡maxv∈𝒯⁡sv\\arg\\max\_\{v\\in\\mathcal\{T\}\}s\_\{v\}

Table 10:ExTS default configuration, fixed across all experiments\.
## Appendix CFormal Definitions of Pilot\-Run Diagnostics

Section[2\.1](https://arxiv.org/html/2608.23848#S2.SS1)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𝒯\\mathcal\{T\}built during a pilot run of budgetBB\.Table[11](https://arxiv.org/html/2608.23848#A3.T11)summarizes the notation used throughout\.

Table 11:Notation used in formal property definitions\.#### Definition 1: Failure rate \(ρ\\rho\)\.

The fraction of expansion attempts that do not produce a successfully validated candidate:

ρ=nv0−nv0\\rho\\;=\\;\\frac\{n\_\{v\_\{0\}\}^\{\-\}\}\{n\_\{v\_\{0\}\}\}\(11\)wherev0v\_\{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 andnv0−n\_\{v\_\{0\}\}^\{\-\}equals the total failures\. An attempt counts as failed ifffreturns⊥\\bot\(e\.g\., syntax error, runtime error, timeout, or a domain\-specific rejection criterion\)\. By construction,ρ∈\[0,1\]\\rho\\in\[0,1\]\. Domains withρ\>0\.5\\rho\>0\.5spend more than half their budget on failed attempts, making failure\-aware mechanisms \(dual backpropagation, success\-rate weighting\) essential\.

#### Definition 2: Normalized score deviation \(σ^f\\hat\{\\sigma\}\_\{f\}\)\.

The spread of validation scores across all successfully evaluated candidates, normalized by the observed range:

σ^f=1smax−smin​1\|S\+\|−1​∑v∈S\+\(sv−s¯\)2\\hat\{\\sigma\}\_\{f\}\\;=\\;\\frac\{1\}\{s\_\{\\max\}\-s\_\{\\min\}\}\\sqrt\{\\frac\{1\}\{\|S^\{\+\}\|\-1\}\\sum\_\{v\\in S^\{\+\}\}\(s\_\{v\}\-\\bar\{s\}\)^\{2\}\}\(12\)wheres¯=1\|S\+\|​∑v∈S\+sv\\bar\{s\}=\\frac\{1\}\{\|S^\{\+\}\|\}\\sum\_\{v\\in S^\{\+\}\}s\_\{v\}\. Ifsmax=smins\_\{\\max\}=s\_\{\\min\}or\|S\+\|<2\|S^\{\+\}\|<2, we defineσ^f=0\\hat\{\\sigma\}\_\{f\}=0\. Low values indicate a flat score landscape where exploitation shaping must work harder to differentiate candidates\.

#### Definition 3: Score drift \(κ\\kappa\)\.

Score drift quantifies the non\-stationarity of normalized node scores as the tree grows\. At each iterationtta new node with scoresnews\_\{\\mathrm\{new\}\}is added\. Letsmints\_\{\\min\}^\{t\}andsmaxts\_\{\\max\}^\{t\}denote the running minimum and maximum scores among all nodes at iterationtt\. Let𝒯Δ=\{t:smint≠smint−1​or​smaxt≠smaxt−1\}\\mathcal\{T\}\_\{\\Delta\}=\\\{t:s\_\{\\min\}^\{t\}\\neq s\_\{\\min\}^\{t\-1\}\\text\{ or \}s\_\{\\max\}^\{t\}\\neq s\_\{\\max\}^\{t\-1\}\\\}be iterations where the normalization bounds change\. The normalized score of nodevvat timettiss^vt=\(sv−smint\)/\(smaxt−smint\)\\hat\{s\}\_\{v\}^\{t\}=\(s\_\{v\}\-s\_\{\\min\}^\{t\}\)/\(s\_\{\\max\}^\{t\}\-s\_\{\\min\}^\{t\}\)\. Then:

κ=1\|𝒯Δ\|​∑t∈𝒯Δ1\|Vt\|​∑v∈Vt\|s^vt−s^vt−1\|\\kappa\\;=\\;\\frac\{1\}\{\|\\mathcal\{T\}\_\{\\Delta\}\|\}\\sum\_\{t\\in\\mathcal\{T\}\_\{\\Delta\}\}\\frac\{1\}\{\|V\_\{t\}\|\}\\sum\_\{v\\in V\_\{t\}\}\\bigl\|\\hat\{s\}\_\{v\}^\{t\}\-\\hat\{s\}\_\{v\}^\{t\-1\}\\bigr\|\(13\)whereVtV\_\{t\}is the set of nodes existing before iterationtt\(excluding the newly added node\)\. If\|𝒯Δ\|=0\|\\mathcal\{T\}\_\{\\Delta\}\|=0or the score range is zero, we defineκ=0\\kappa=0\. Highκ\\kappaindicates that newly discovered candidates frequently shift the normalization bounds, changing the relative exploitation values of existing candidates\.

#### Definition 4: Refinement variance \(σ^𝒜\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}\)\.

The refinement variance measures the stochasticity of the refinement operator𝒜\\mathcal\{A\}when applied to the same parent state\. For each internal nodev∈I⁡\(𝒯\)v\\in I\(\\mathcal\{T\}\)with at least two successfully validated children, letCv\+=\{c∈children⁡\(v\):sc​is defined\}C\_\{v\}^\{\+\}=\\\{c\\in\\mathrm\{children\}\(v\):s\_\{c\}\\text\{ is defined\}\\\}andf¯v=1\|Cv\+\|​∑c∈Cv\+sc\\bar\{f\}\_\{v\}=\\frac\{1\}\{\|C\_\{v\}^\{\+\}\|\}\\sum\_\{c\\in C\_\{v\}^\{\+\}\}s\_\{c\}\. The per\-node refinement variance is:

σ𝒜,v2=1\|Cv\+\|−1​∑c∈Cv\+\(sc−f¯v\)2\\sigma^\{2\}\_\{\\mathcal\{A\},v\}\\;=\\;\\frac\{1\}\{\|C\_\{v\}^\{\+\}\|\-1\}\\sum\_\{c\\in C\_\{v\}^\{\+\}\}\(s\_\{c\}\-\\bar\{f\}\_\{v\}\)^\{2\}\(14\)LetI2=\{v∈I⁡\(𝒯\):\|Cv\+\|≥2\}I\_\{2\}=\\\{v\\in I\(\\mathcal\{T\}\):\|C\_\{v\}^\{\+\}\|\\geq 2\\\}\. The global refinement variance is:

σ^𝒜=1smax−smin​1\|I2\|​∑v∈I2σ𝒜,v2\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}\\;=\\;\\frac\{1\}\{s\_\{\\max\}\-s\_\{\\min\}\}\\sqrt\{\\frac\{1\}\{\|I\_\{2\}\|\}\\sum\_\{v\\in I\_\{2\}\}\\sigma^\{2\}\_\{\\mathcal\{A\},v\}\}\(15\)

#### Distinction fromσ^f\\hat\{\\sigma\}\_\{f\}\.

σ^f\\hat\{\\sigma\}\_\{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,σ^𝒜\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}isolates the variance attributable to the LLM’s sampling stochasticity by conditioning on the parent\. A domain may have lowσ^f\\hat\{\\sigma\}\_\{f\}\(flat overall landscape\) but highσ^𝒜\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}\(diverse candidates from any single parent\), or vice versa\. Highσ^𝒜\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}indicates that re\-sampling from the same node is productive, providing implicit exploration; lowσ^𝒜\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}indicates refinements are largely deterministic and explicit exploration via higherCCis needed\.

#### Computation details for Table[1](https://arxiv.org/html/2608.23848#S2.T1)\.

All properties are computed from pilot trees built by running the baseline method for each dataset with budgetBB, averaged across 3 seeds \(\{0,42,1024\}\\\{0,42,1024\\\}\)\.

*ρ\\rho:*We readnv0n\_\{v\_\{0\}\}andnv0\+n\_\{v\_\{0\}\}^\{\+\}directly from the root node’s backpropagated statistics stored in the pilot tree\.

*σ^f\\hat\{\\sigma\}\_\{f\}:*We collect the scoresvs\_\{v\}of every nodev∈S\+v\\in S^\{\+\}in the pilot tree and compute the sample standard deviation divided bysmax−smins\_\{\\max\}\-s\_\{\\min\}\. For K\-MSE, which runs 216 independent molecule searches per seed, we pool all node scores across molecules before computing a singleσ^f\\hat\{\\sigma\}\_\{f\}per seed\.

*κ\\kappa:*We replay the tree construction in node\-creation order, trackingsmints\_\{\\min\}^\{t\}andsmaxts\_\{\\max\}^\{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\.

*σ^𝒜\\hat\{\\sigma\}\_\{\\mathcal\{A\}\}:*We estimate refinement variance from sibling scores in the pilot tree: for each internal nodevvwith\|Cv\+\|≥2\|C\_\{v\}^\{\+\}\|\\geq 2successfully validated children, we computeσ𝒜,v2\\sigma^\{2\}\_\{\\mathcal\{A\},v\}from the children’s scores and aggregate via Equation[15](https://arxiv.org/html/2608.23848#A3.E15)\. This treats siblings as approximate samples from𝒜⁡\(xv\)\\mathcal\{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 runK=10K\\\!=\\\!10i\.i\.d\. refinements from a fixed parent state for 5 representative problems and aggregate\.

## Appendix DDetailed Experimental Setup

### D\.1Prompt Optimization

We evaluate ExTS within the GEPA prompt optimization framework\([Agrawal et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib8)\), which optimizes natural\-language instructions in DSPy programs\([Khattab et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib13)\)\. We use two multi\-hop reasoning benchmarks: HotpotQA\([Yang et al\., 2018](https://arxiv.org/html/2608.23848#bib.bib14)\), a question answering task with a 4\-predictor DSPy program and ColBERTv2 retrieval\([Santhanam et al\., 2022](https://arxiv.org/html/2608.23848#bib.bib19)\)over 5\.2M Wikipedia abstracts, and HoVeR\([Jiang et al\., 2020](https://arxiv.org/html/2608.23848#bib.bib15)\), 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](https://arxiv.org/html/2608.23848#bib.bib18)\)via vLLM\([Kwon et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib42)\)\(TP=4, temperature 0\.6, top\-pp0\.95, thinking enabled\)\.

In the ExTS formulation, the candidate set𝒮\\mathcal\{S\}consists of DSPy instruction configurations\. The refinement operator𝒜\\mathcal\{A\}is an LLM instruction proposer conditioned on failure feedback\. The validatorffevaluates on the full train and validation set, returning⊥\\botif the new score does not exceed the parent’s\. Score stationarityκ\\kappais 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](https://arxiv.org/html/2608.23848#bib.bib8)\)\), ExTS default \(Table[10](https://arxiv.org/html/2608.23848#A2.T10)\), and per\-dataset ExTS∗\(HotpotQA:α=2\.0\\alpha\\\!=\\\!2\.0; HoVeR: UCT exploration,τ=0\\tau\\\!=\\\!0\), with the optimization budget matched across methods\.

### D\.2Code Generation

We evaluate ExTS within the TreeQuest framework\([Inoue et al\., 2026](https://arxiv.org/html/2608.23848#bib.bib17)\)on LiveCodeBench\([Jain et al\., 2024](https://arxiv.org/html/2608.23848#bib.bib16)\), 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,𝒮\\mathcal\{S\}consists of code solutions,𝒜\\mathcal\{A\}is an LLM code editor conditioned on test failure traces, andffis the full public test suite execution \(returning⊥\\boton syntax errors or compilation failures\)\. Score stationarityκ\\kappais low because existing solution scores do not change\. We compare StandardMCTS \(UCT withC=2C\\\!=\\\!\\sqrt\{2\}, samples per action of 5\), AB\-MCTS\-A \(Thompson sampling with Gaussian conjugate prior\([Inoue et al\., 2026](https://arxiv.org/html/2608.23848#bib.bib17)\)\), and ExTS default \(Table[10](https://arxiv.org/html/2608.23848#A2.T10)\)\. ExTS∗setsT=0\.5T\\\!=\\\!0\.5\.

### D\.3Molecular Structure Elucidation

We evaluate ExTS on the K\-MSE molecular structure elucidation task\([Zhuang et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib4)\), 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](https://arxiv.org/html/2608.23848#bib.bib44)\), 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,𝒮\\mathcal\{S\}consists of SMILES strings,𝒜\\mathcal\{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,ggchecks chemical validity via RDKit, andffis 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](https://arxiv.org/html/2608.23848#bib.bib4)\)and chain\-of\-thought prompting\([Wei et al\., 2023](https://arxiv.org/html/2608.23848#bib.bib43), CoT;\), using 16 rollouts per molecule and 3 seeds \(\{0,42,1024\}\\\{0,42,1024\\\}\)\. ExTS uses the default configuration \(Table[10](https://arxiv.org/html/2608.23848#A2.T10)\)\. ExTS∗setsT=0\.5T\\\!=\\\!0\.5\.

### D\.4Agentic Workflow Optimization

We evaluate ExTS within the AFlow framework\([Zhang et al\., 2025](https://arxiv.org/html/2608.23848#bib.bib31)\)on the DROP reading comprehension benchmark\([Dua et al\., 2019](https://arxiv.org/html/2608.23848#bib.bib32)\)\. 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𝒮\\mathcal\{S\}consists of these workflow programs\. The refinement operator𝒜\\mathcal\{A\}is an optimizer LLM \(Claude Sonnet 4\.5\) that proposes mutations to the workflow graph conditioned on execution logs and past experience\. The validatorffexecutes 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\\rho\\approx 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](https://arxiv.org/html/2608.23848#bib.bib31)\): 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](https://arxiv.org/html/2608.23848#A2.T10)\)\. ExTS∗setsτ=0\.5\\tau\\\!=\\\!0\.5,M0=4M\_\{0\}\\\!=\\\!4\.

Budget is 20 search rounds per seed, with seeds\{0,42,1024\}\\\{0,42,1024\\\}\.

## Appendix EAnalysis Setup Details

#### Tree\-shape diagnostics \(Section[5\.4](https://arxiv.org/html/2608.23848#S5.SS4)\)\.

We compare MCTSr \(binary expansion, no gating\) against ExTS at two branching caps:M0=2M\_\{0\}\\\!=\\\!2\(matching MCTSr’s effective branching\) andM0=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\{\\sim\}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](https://arxiv.org/html/2608.23848#S5.SS5)\)\.

On LiveCodeBench we run Standard MCTS, AB\-MCTS, and ExTS withB=128B\{=\}128\(182 problems, 3 seeds\) and extract pass@1 at each intermediate budget from the cumulative score trajectory: a problem is solved at budgetbbif its best public\-test solution within the firstbbevaluations 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 FMore Ablations on LiveCodeBench

Table[12](https://arxiv.org/html/2608.23848#A6.T12)isolates two components on LiveCodeBench\. Removing gated progressive widening costs−\-1\.3 pp overall and−\-1\.6 pp 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 pp overall and−\-2\.0 pp 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\)\.
## Appendix GCompact Diagnostic Guide

Table[13](https://arxiv.org/html/2608.23848#A7.T13)condenses the pilot\-run findings of Section[5\.2](https://arxiv.org/html/2608.23848#S5.SS2)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 \(typically0\.20\.2–1\.21\.2pp\)\. 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](https://arxiv.org/html/2608.23848#S2.SS1)\), 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](https://arxiv.org/html/2608.23848#S5.SS2)\.The default configuration, used when no pilot is run, is PUCT withC=1\.0C\\\!=\\\!1\.0,α=2\\alpha\\\!=\\\!\\sqrt\{2\},T=0\.3T\\\!=\\\!0\.3,M0=3M\_\{0\}\\\!=\\\!3, andτ=0\.25\\tau\\\!=\\\!0\.25\(Table[10](https://arxiv.org/html/2608.23848#A2.T10)\)\.

## Appendix HFurther 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](https://arxiv.org/html/2608.23848#A2.T10)\), with no tuning and no diagnostics, we follow the setup of[Gai et al\. \(2026\)](https://arxiv.org/html/2608.23848#bib.bib48), 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 from4\.15×4\.15\\timesto4\.36×4\.36\\times, the median speedup from3\.09×3\.09\\timesto3\.81×3\.81\\times, and the per\-category speedups across all three difficulty levels \(Table[14](https://arxiv.org/html/2608.23848#A8.T14)\)\. We note that the original speed validation of[Gai et al\. \(2026\)](https://arxiv.org/html/2608.23848#bib.bib48)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](https://arxiv.org/html/2608.23848#A2.T10)\) with no tuning or diagnostics\. All values are speedup factors \(×\\times\); L1, L2, and L3 are the difficulty levels \(categories\) defined by[Gai et al\. \(2026\)](https://arxiv.org/html/2608.23848#bib.bib48)\. 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\)](https://arxiv.org/html/2608.23848#bib.bib48)\.
## Appendix IWorked 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](https://arxiv.org/html/2608.23848#S3.E7)and[8](https://arxiv.org/html/2608.23848#S3.E8)and Algorithm[1](https://arxiv.org/html/2608.23848#alg1)\. We reconstruct the iteration where the run’s best candidate \(score68\.6768\.67\) is created: at iteration 104 the search descendsroot→v1→v3→v7\\text\{root\}\\rightarrow v\_\{1\}\\rightarrow v\_\{3\}\\rightarrow v\_\{7\}and expands the leafv7v\_\{7\}\. At that point the global score range is\[50\.33,65\.0\]\[50\.33,65\.0\]\(68\.6768\.67does not yet exist, being the child about to be created\) and the defaults apply \(T=0\.3T\\\!=\\\!0\.3,α=2\\alpha\\\!=\\\!\\sqrt\{2\},C=1\.0C\\\!=\\\!1\.0, PUCT with parent exponent0\.50\.5\)\. We show the virtual\-child comparison at the pivotal nodev1v\_\{1\}, which hasnv=28n\_\{v\}\\\!=\\\!28visits,nv\+=4n\_\{v\}^\{\+\}\\\!=\\\!4successful visits \(success rate0\.1430\.143\), scoresv=52\.33s\_\{v\}\\\!=\\\!52\.33, and a single childv3v\_\{3\}\(n=24n\\\!=\\\!24,n\+=3n^\{\+\}\\\!=\\\!3, score55\.3355\.33, rewards\{62\.33,60\.67,65\.0\}\\\{62\.33,60\.67,65\.0\\\}\)\.

#### Best real child\.

The rewards ofv3v\_\{3\}normalize and shape \(Eq\.[3](https://arxiv.org/html/2608.23848#S3.E3)\) to\{0\.528,0\.351,1\.000\}\\\{0\.528,0\.351,1\.000\\\}with mean0\.6260\.626; its success rate3/=0\.1253/24\\\!=\\\!0\.125gives\(0\.125\)2=0\.053\(0\.125\)^\{\\sqrt\{2\}\}\\\!=\\\!0\.053, so the exploitation term is0\.053⋅=0\.0330\.053\\cdot 0\.626\\\!=\\\!0\.033\. With PUCT explorationC⋅nv/\(1\+nchild\)=28/\(1\+24\)=0\.212C\\cdot\\sqrt\{n\_\{v\}\}/\(1\+n\_\{\\text\{child\}\}\)\\\!=\\\!\\sqrt\{28\}/\(1\+24\)\\\!=\\\!0\.212, the total isExUCT​\(v3\)=0\.245\\text\{ExUCT\}\(v\_\{3\}\)\\\!=\\\!0\.245\.

#### Virtual child\.

The fair\-share visit count \(Eq\.[7](https://arxiv.org/html/2608.23848#S3.E7)\) isnfair=24/=24n\_\{\\text\{fair\}\}\\\!=\\\!24/1\\\!=\\\!24and the sample size isk=round⁡\(nfair⋅nv\+/nv\)=round⁡\(24⋅0\.143\)=3k\\\!=\\\!\\operatorname\{round\}\(n\_\{\\text\{fair\}\}\\cdot n\_\{v\}^\{\+\}/n\_\{v\}\)\\\!=\\\!\\operatorname\{round\}\(24\\cdot 0\.143\)\\\!=\\\!3\. The virtual child drawsk=3k\\\!=\\\!3scores from the parent’s pool \(reward history plussvs\_\{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 is28/\(1\+24\)=0\.212\\sqrt\{28\}/\(1\+24\)\\\!=\\\!0\.212, so in expectation it scores\(0\.143\)2⋅0\.396\+=0\.237\(0\.143\)^\{\\sqrt\{2\}\}\\cdot 0\.396\+0\.212\\\!=\\\!0\.237, just below the best real child at0\.2450\.245\.

#### Decision and interpretation\.

The comparison is close,0\.2370\.237versus0\.2450\.245, and turns on the shaped sample: widening wins only when the mean of the three draws exceeds about0\.520\.52, which requires repeatedly drawing the two high pool entries \(0\.5280\.528and1\.0001\.000\)\. Enumerating all draws, this happens with probability0\.2560\.256, so ExTS deepens intov3v\_\{3\}about three quarters of the time, and the descent continues throughv3v\_\{3\}to the leafv7v\_\{7\}whose expansion produces the global best of68\.6768\.67\. The virtual child’s exploration bonus, computed at the honest fair\-share countnfair=24n\_\{\\text\{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 \(virtual0\.3720\.372versus best real0\.3810\.381\), while atv3v\_\{3\}itself widening is gated off \(it is at the branching capM0=3M\_\{0\}\\\!=\\\!3and below the widening visit threshold\), so the search simply deepens intov3v\_\{3\}’s least\-visited childv7v\_\{7\}\.

## Appendix JEthical 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 KArtifact Documentation

Table[15](https://arxiv.org/html/2608.23848#A11.T15)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\.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 LUse of AI Assistants

We used AI assistants to refine the grammar of the paper’s text\.