Exploit More, Explore Smarter for Budget-Constrained Agentic Search

Haoyang Fang; Bernie Wang

cs.AIAug 24, 2026

Exploit More, Explore Smarter for Budget-Constrained Agentic Search

Authors: Haoyang Fang, Bernie Wang

Organizations: Amazon AGI

Abstract

Budget-constrained agentic search arises when an LLM agent must refine candidates under a small evaluation budget, because validation is expensive, generation requires multiple model calls, or both. In this regime, standard MCTS allocates budget poorly: exploration bonuses dominate at low visit counts, unpromising siblings are expanded before promising chains can deepen, and branching is independent of node quality. We introduce ExTS, a tree-search policy that treats expansion itself as a value-of-information decision. ExTS combines three mechanisms: discriminative reward shaping to separate candidates under narrow score distributions, a stochastic virtual child that estimates the value of creating a new branch from the parent's reward history, and quality-conditioned branching that expands only when a node's score justifies the budget cost. Across prompt optimization, code generation, molecular structure elucidation, and agentic workflow optimization, ExTS is competitive with or improves over task-specific tree-search baselines, with an average relative gain of +5.5% using a single fixed configuration. We further introduce pilot-run diagnostics that characterize what makes budget-constrained agentic search problems structurally different from one another, providing both understanding of the problem space and practical guidance for adaptation.

Figures & tables

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.

Dataset	$\hat{\sigma}_{\mathcal{A}}$	$\hat{\sigma}_{f}$	$\kappa$	$\rho$
HotpotQA	.30 $\pm$ .05	.30 $\pm$ .09	.11 $\pm$ .03	.74 $\pm$ .04
HoVeR	.20 $\pm$ .06	.29 $\pm$ .01	.16 $\pm$ .11	.82 $\pm$ .01
LiveCodeBench	.32 $\pm$ .01	.23 $\pm$ .01	.14 $\pm$ .13	.57 $\pm$ .05
K-MSE	.09 $\pm$ .00	.18 $\pm$ .00	.05 $\pm$ .00	$<$ .01
DROP	.04 $\pm$ .03	.23 $\pm$ .03	.02 $\pm$ .01	.03 $\pm$ .03

Table 1: Pilot-run diagnostics (mean

\pm

std, 3 seeds).

\hat{\sigma}_{\mathcal{A}}

: refinement variance;

\hat{\sigma}_{f}

: score spread;

\kappa

: score drift;

\rho

: failure rate.

Method	HotpotQA	HoVeR
Baseline	41.44 $\pm$ 1.25	36.11 $\pm$ 0.79
GRPO †	43.33	38.67
MIPROv2 †	55.33	47.33
GEPA (Pareto)	58.55 $\pm$ 5.32	50.33 $\pm$ 2.45
ExTS	64.89 $\pm$ 0.83	50.45 $\pm$ 2.18
ExTS ∗	66.00 $\pm$ 0.98	51.67 $\pm$ 0.98

Table 2: Prompt optimization: test accuracy (%) over 3 seeds. † Results from Agrawal et al. (2025) . ∗ Pilot-adapted (Section 5.2 ).

Figure 2: LiveCodeBench pass@1 (%) over 3 seeds.

Method	ACC (%)	Morgan	MACCS	RDK
CoT	79.8 $\pm$ 0.2	.887 $\pm$ .002	.942 $\pm$ .001	.904 $\pm$ .001
K-MSE	89.8 $\pm$ 0.4	.952 $\pm$ .002	.976 $\pm$ .001	.962 $\pm$ .003
ExTS	91.0 $\pm$ 0.6	.952 $\pm$ .004	.972 $\pm$ .005	.960 $\pm$ .004
ExTS ∗	91.2 $\pm$ 0.4	.954 $\pm$ .004	.973 $\pm$ .003	.959 $\pm$ .004

Table 3: K-MSE molecular elucidation (Claude Sonnet 4.6, 216 molecules, 16 rollouts, 3 seeds). ACC (exact match) is the primary metric; fingerprint similarities are listed for reference. ∗ Pilot-adapted (Section 5.2 ).

Method	F1 (mean $\pm$ std)	Best	Cost ($)
CoT (linear)	89.28 $\pm$ 1.78	91.10	36.70
AFlow	87.89 $\pm$ 2.29	89.56	26.09
ExTS	90.96 $\pm$ 0.93	91.54	15.26
ExTS ∗	91.54 $\pm$ 1.92	93.76	10.43

Table 4: Workflow optimization on DROP (F1

\times

100, 3 seeds). ∗ Pilot-adapted (Section 5.2 ).

Configuration	Acc.	Configuration	Acc.
ExTS (full)	64.89 $\pm$ 0.83	w/o Soft norm.	63.44 $\pm$ 2.20
w/o Virtual child	61.67 $\pm$ 1.96	w/o Gated expan.	63.22 $\pm$ 1.10
w/o Fail. penalty ( $\alpha\!=\!1$ )	57.11 $\pm$ 5.67	w/o Gated PW	62.55 $\pm$ 2.08

Table 5: Leave-one-out ablation on HotpotQA (3 seeds). LiveCodeBench ablations in Table 12 .

DROP (F1 $\times$ 100)
Configuration	Score
ExTS (virtual child)	90.96 $\pm$ 0.93
Fixed FPU $=0.5$	88.95 $\pm$ 0.81
Fixed FPU $=0.8$	89.34 $\pm$ 3.23
LiveCodeBench (pass@1 %)
ExTS (quality-gated PW)	46.2 $\pm$ 0.4

Table 6: Classical mechanisms vs. ExTS redesigns (3 seeds).

Dataset	PUCT	UCT
HotpotQA	64.89 $\pm$ 0.83	58.44 $\pm$ 2.20
HoVeR	50.45 $\pm$ 2.18	51.33 $\pm$ 1.44
K-MSE	91.0 $\pm$ 0.6	89.0 $\pm$ 1.5

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

All tasks ( $n\!=\!216$ )
Method	Leaf dep.	Best dep.	Scorer	ACC (%)
MCTSr	4.89 $\pm$ .08	0.44 $\pm$ .07	72.2 $\pm$ 0.3	89.8 $\pm$ 0.4
ExTS ${}_{M_{0}=2}$	5.49 $\pm$ .13	0.48 $\pm$ .05	72.5 $\pm$ 0.2	90.4 $\pm$ 0.4
ExTS ${}_{M_{0}=3}$	4.91 $\pm$ .14	0.47 $\pm$ .03	72.7 $\pm$ 0.1	91.0 $\pm$ 0.6
Non-trivial tasks ( $n\!=\!92$ )
MCTSr	4.43 $\pm$ .13	1.03 $\pm$ .16	69.5 $\pm$ 0.6	77.2 $\pm$ 0.9

Table 8: Tree-shape diagnostics on K-MSE (

B\!=\!16

, 3 seeds). Non-trivial: 92 molecules where at least one method improves beyond the root.

Figure 3: Budget-scaling behavior across three domains, averaged over 3 seeds (

\pm 1\sigma

bands). The x-axis is search budget. ExTS’s advantage is most pronounced on hard instances (top left) and in prompt optimization (bottom left), where iterative refinement matters most.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Focus	Selection	Expansion	Fail.-aware
Linear	H	Sequential	N/A	No
ToT	H	BFS/DFS	Full	No
LATS	H	UCT	Full	No
rStar	H	UCT	Full	No
RAP	H	UCT	Full	No
SWE-Search	H	UCT + hybrid value	Full	No

Appendix

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).

Parameter	Default	Rationale
Exploration type	PUCT	Linear decay for tight budgets
Exploration $C$	1.0	Conservative; no policy prior
Success-rate $\alpha$	$\sqrt{2}$	Amplified failure discounting
Temperature $T$	0.3	Top-20% emphasis
Initial children $M_{0}$	3	Moderate branching
Widening base $b$	2	$\log_{2}$ growth

Appendix

Table 10: ExTS default configuration, fixed across all experiments.

Symbol	Description
$\mathcal{T}$	Search tree rooted at initial candidate $x_{0}$
$V(\mathcal{T})$	Set of all nodes in $\mathcal{T}$
$I(\mathcal{T})$	Set of internal (expanded) nodes: $\{v\in V(\mathcal{T}):\|\mathrm{children}(v)\|>0\}$
$n_{v}$	Visit count of node $v$ (incremented via backpropagation from all expansions in the subtree rooted at $v$ )
$n_{v}^{+}$	Successful visit count (backpropagated from expansions where $f(x^{\prime})\neq\bot$ )
$n_{v}^{-}$	Failed visit count: $n_{v}^{-}=n_{v}-n_{v}^{+}$

Appendix

Table 11: Notation used in formal property definitions.

Configuration	All (%)	Hard (%)
ExTS (full)	46.2 $\pm$ 0.4	19.1 $\pm$ 1.4
w/o Gated prog. widening	44.9 $\pm$ 0.7	17.5 $\pm$ 1.4
w/o Root exclusion	45.2 $\pm$ 1.5	17.1 $\pm$ 2.5

Appendix

Table 12: Leave-one-out ablation on LiveCodeBench (pass@1 %, 3 seeds).

Diagnostic signature	What it says about the task	Relevant hyperparameter	Evidence
High failure rate $\rho$ (e.g. ${>}0.5$ )	most expansions fail, so separating productive nodes is critical	success exponent $\alpha$	HotpotQA
Low $\rho$ (e.g. ${<}0.1$ )	failures are rare	success exponent $\alpha$ (little effect, keep default)	K-MSE, DROP
High score drift $\kappa$	early rankings are unreliable as bounds re-rank nodes	exploration type (use UCT) and score gate $\tau$	HoVeR
Low $\kappa$	rankings stabilize early, safe to commit	exploration type (use PUCT)	HotpotQA
Low $\hat{\sigma}_{\mathcal{A}}$ and low $\kappa$ , or weak validator	aggressive exploitation over-commits to spurious gaps	shaping temperature $T$	K-MSE, DROP, LCB

Appendix

Table 13: Compact diagnostic guide: mapping pilot-run signatures to hyperparameter adjustments, condensing Section 5.2 .

Method	Geo. mean	Median	L1	L2	L3
MCTS (optimized)	$4.15\times$	$3.09\times$	$3.68\times$	$5.04\times$	$3.69\times$
ExTS	$\mathbf{4.36\times}$	$\mathbf{3.81\times}$	$\mathbf{3.76\times}$	$\mathbf{5.25\times}$	$\mathbf{4.30\times}$

Appendix

Table 14: Further evaluation on an additional domain, GPU kernel optimization: 40 GPU-kernel tasks, each run on a single NVIDIA A100 40GB GPU, using ExTS’s fixed default configuration (Table 10 ) with no tuning or diagnostics. All values are speedup factors (

\times

); L1, L2, and L3 are the difficulty levels (categories) defined by Gai et al. (2026) . ExTS improves over MCTS (optimized) on every metric. Results are from a single run with Claude Opus 4.6, owing to the substantial compute cost of this domain. The reported speedups are the corrected results that exclude the invalid speedups admitted by the original validation of Gai et al. (2026) .

Artifact	Type	License	Consistent Use
GEPA	Framework	MIT	Yes
TreeQuest	Framework	Apache 2.0	Yes
AFlow	Framework	MIT	Yes
K-MSE	Framework	MIT	Yes
DSPy	Framework	MIT	Yes
vLLM	Inference engine	Apache 2.0	Yes

Appendix

Table 15: Artifacts used, with licenses and intended-use consistency.

Explore similar work

Mar 13, 2026

Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents

Test-time scaling has become a dominant paradigm for improving LLM agent reliability, yet current approaches treat compute as an abundant resource, allowing agents to exhaust token and tool budgets on redundant steps or dead-end trajectories. Existing budget-aware methods either require expensive fine-tuning or rely on coarse, trajectory-level heuristics that cannot intervene mid-execution. We propose the Budget-Aware Value Tree (BAVT), a training-free inference-time framework that models multi-hop reasoning as a dynamic search tree guided by step-level value estimation within a single LLM backbone. Another key innovation is a budget-conditioned node selection mechanism that uses the remaining resource ratio as a natural scaling exponent over node values, providing a principled, parameter-free transition from broad exploration to greedy exploitation as the budget depletes. To combat the well-known overconfidence of LLM self-evaluation, BAVT employs a residual value predictor that scores relative progress rather than absolute state quality, enabling reliable pruning of uninformative or redundant tool calls. We further provide a theoretical convergence guarantee, proving that BAVT reaches a terminal answer with probability at least

1-ε

under an explicit finite budget bound. Extensive evaluations on four multi-hop QA benchmarks across two model families demonstrate that BAVT consistently outperforms parallel sampling baselines. Most notably, BAVT under strict low-budget constraints surpasses baseline performance at

4\times

the resource allocation, establishing that intelligent budget management fundamentally outperforms brute-force compute scaling.

Yushu Li, Wenlong Deng, Jiajin Li +1

University of British Columbia · Vector Institute

Cost-Aware Inference Tree Search

Ask PDF

Jun 10, 2026

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

Deep search requires agents to answer complex questions through multi-step web search, browsing, evidence comparison, and synthesis. A central challenge is deciding how to search when several directions look plausible but only some will later lead to reliable evidence. If an agent greedily follows the current best-looking direction, it may keep extending a weak continuation. If it explores without discipline, it may waste budget on disconnected trials. We propose TreeSeeker, an inference-time framework for controlled trial-and-error in deep search. TreeSeeker organizes search as branch-and-return search over tree-structured states, where each branch is a tentative direction for a sub-goal. At each round, TreeSearch reads all sub-goal trees, identifies active goals, and uses textual UCB signals of value, uncertainty, and risk to select among exploiting a promising branch, exploring an uncertain alternative, or pruning an unproductive continuation and returning to an earlier branch point. TreeMem supports this control loop by keeping evidence, uncertainty, conflicts, progress, and failure cues attached to the branches that produced them, so trial outcomes can guide later decisions. Experiments on XBench-DeepSearch, BrowseComp, and BrowseComp-ZH show that TreeSeeker consistently outperforms strong open-source baselines, suggesting that explicit branch-and-return control complements stronger reasoning and tool execution.

Zhuofan Shi, Mingzhe Ma, Lu Wang +8

1Microsoft · 2East China Normal University

Inference-Time Search Exploration-Exploitation Tradeoff Tree Search

Ask PDF

Sep 1, 2026

One Policy, Any Budget: Internalizing Budget-Aware Search via Reinforcement Learning

While reinforcement learning has enabled LLM-based search agents to invoke external tools, existing methods train under fixed budgets and cannot adapt when constraints vary at deployment. We propose AnySearch, a framework that enables a single policy to perform budget-aware search under any budget constraint through a training scaffold and curriculum reinforcement learning. In the first phase, we train the agent with explicit budget state injection and structured reasoning prompts that guide efficient allocation under linearly decaying budgets. In the second phase, the scaffold is removed and the agent learns to operate autonomously under adaptively sampled budget constraints, matching inference conditions. Both phases are optimized with a composite reward that couples answer accuracy with budget efficiency through absolute and relative signals, where an adaptive weight amplifies the efficiency signal for high-accuracy queries and attenuates it for low-accuracy ones. Extensive experiments on seven general and multi-hop QA benchmarks show that our method outperforms baselines across all budget scales, generalizes to unseen constraints beyond the training range, and achieves superior tool productivity without excessive token overhead. Our code is available at https://github.com/xwsun01/AnySearch.

Xiaowei Sun, Jin Li, Yili Hong +2

College of Computer Science and Artiﬁcial Intelligence, Fudan University · College of Software Engineering, Southeast University · School of Artiﬁcial Intelligence, Shanghai Jiao Tong University

Cost-Aware Inference Constrained RL RL for LLM Agents RL for Tool Use

Ask PDF