PaperlayerView exact revision on arXiv

Source-linked AI summary

Exploit More, Explore Smarter for Budget-Constrained Agentic Search

Haoyang Fang, Bernie Wang

arXiv:2608.23848v1cs.AIcs.LG

TL;DR

Budget-constrained agentic search gives standard MCTS too little budget for effective refinement. ExTS makes selection and expansion quality-aware, and across four domains it is competitive with or improves over task-specific baselines using one fixed configuration, with gains concentrated in high-failure-rate and moderate-difficulty regimes.

  • Problem

    Budget-constrained agentic search limits agents to tens or hundreds of evaluations, while standard MCTS can produce flat, wide trees that fail to develop deep refinement chains.

  • Method

    ExTS jointly redesigns selection and expansion using reward shaping, a virtual-child value-of-information heuristic, and quality-conditioned branching.

  • Results

    +5.5% average relative gain across prompt optimization, code generation, molecular structure elucidation, and agentic workflow optimization using one fixed configuration.

  • Takeaways & Limitations

    Pilot-run diagnostics characterize structural differences among agentic search problems and provide practical guidance for adaptation.

  • Takeaways & Limitations

    The diagnostics are conditioned on the model, scorer, and budget, so their transferability across model families is untested.

Abstract

from arXiv · show

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.

1 Introduction

Budget-constrained agentic search uses only tens or hundreds of calls, making both candidate selection and expansion consequential. ExTS addresses this regime with value-of-information expansion, discriminative scoring, and quality-conditioned branching, improving or matching task-specific methods across four domains.

  • Motivation: Budget-constrained agentic search limits systems to tens or hundreds of generation and validation calls across diverse applications.The regime includes prompt optimization, code generation, tool-augmented reasoning, and multi-step planning.
  • Motivation: Standard MCTS wastes tight budgets through low-visit exploration dominance, forced expansion of unpromising siblings, and ungated branching.These limitations spread search across shallow, low-value structures.
  • ExTS: ExTS makes expansion a value-of-information decision using a virtual child sampled from parent reward history and quality-conditioned branching gated by reshaped score.Its discriminative reward shaping separates candidates under narrow score distributions, while virtual expansion competes directly with deepening.
  • Results: +10.8% on HotpotQA, +11.7% on LiveCodeBench hard, +1.3% on K-MSE, +3.5% on DROP, and +0.2% on HoVeR were achieved by ExTS with one fixed configuration across four domains.The reported domains are prompt optimization, code generation, molecular structure elucidation, and agentic workflow optimization.

2 Preliminaries

Validation-heavy search is formalized as budgeted stochastic refinement over candidates, with pilot-run diagnostics describing task landscapes. Standard UCT is poorly matched to this regime because compressed rewards and small budgets undermine its assumptions, motivating ExTS’s redesign of related MCTS mechanisms.

  • Search formulation: Validation-heavy search uses a candidate set S, stochastic refinement operator A, validation function f, and total evaluation budget B to maximize f(x) over a search tree.The tree is rooted at an initial candidate x0, and validation may return a score or failure ⊥.
  • Pilot-run diagnostics: Four pilot-run diagnostics characterize validation-heavy search landscapes, guide hyperparameter choices, and explain why no single search configuration dominates universally.They are computed from a pilot tree generated by running the baseline search method for each dataset.
  • Limitations of standard MCTS: UCT’s exploration bonus can dominate when reward shaping compresses the effective exploitation range, making nodes appear equally promising.Its default C = 2 is calibrated for rewards in [0, 1].
  • Limitations of standard MCTS: Budgets of tens to hundreds of evaluations fall far below UCT’s asymptotic convergence regime, producing flat, wide trees.This is the second assumption violation identified for validation-heavy search.
  • Classical MCTS extensions: Progressive widening, FPU, and PUCT do not transfer directly because they are respectively score-agnostic, fixed for unvisited actions, or dependent on a learned prior.ExTS redesigns these mechanisms, including stochastic virtual-child FPU and prior-free PUCT-style decay.

3 Methodology

ExTS treats selection and expansion as reward-distribution-conditional decisions, combining discriminative reward shaping, virtual-child value-of-information estimation, and quality-conditioned branching. Its search loop retains standard MCTS operations while allowing expansion at internal nodes when creating a new branch is estimated to be more valuable than deepening the best existing child.

  • Overall design: ExTS conditions selection and expansion on observed reward distributions at both local subtree and global tree scopes, rather than relying on a single scalar-weighted exploration term.The complete loop follows standard MCTS: select, expand, validate, and backpropagate.
  • Reward shaping and selection: ExTS combines shaped rewards with success-rate weighting so narrow raw validation-score distributions can distinguish candidates while discounting mostly invalid subtrees.The shaping function uses global normalization and a temperature-controlled nonlinearity; for T < 1, it amplifies high scores.
  • Expansion as value of information: A stochastic virtual child makes expansion a first-class decision at every expandable internal node by competing with real children during selection.Its reward estimate samples from the parent’s reward pool, with finite-sample variance encouraging expansion when evidence is thin; expansion occurs when its score exceeds the best real child’s.
  • Quality-conditioned branching: Quality-conditioned branching permits expansion above a τ-quantile gate and increases the branching cap only for nodes above a stronger γ-quantile quality threshold.Defaults are γ = 0.75 and τ = 0.25; low-scoring nodes remain capped at M0, while every leaf receives an initial expansion attempt before gating applies.

4 Evaluation

ExTS is evaluated across four domains under equal per-task budgets, using one fixed configuration alongside tuned baselines and modest pilot-adapted variants. It improves or matches task-specific methods across prompt optimization, code generation, molecular elucidation, and workflow optimization, with gains attributed to deeper refinement and quality-aware allocation.

  • Evaluation design: All methods share each task’s evaluation budget, while ExTS uses one fixed configuration and baselines use fully tuned domain-specific configurations.Pilot-adapted ExTS∗ variants adjust one or two hyperparameters using pilot-run diagnostics.
  • Prompt optimization: ExTS reaches 64.89% on HotpotQA versus 58.55% for GEPA (Pareto), while ExTS∗ reaches 66.00%; on HoVeR, ExTS reaches 50.45% versus 50.33%.The HotpotQA improvement is +10.8% with 6.4× lower variance; ExTS∗ uses α = 2.0, while HoVeR’s result is +0.2% within noise.
  • Code generation: 19.1% hard-split pass@1 for ExTS exceeds 17.1% for AB-MCTS-A and 18.1% for StandardMCTS, while overall ExTS reaches 46.2%.The gains come from deeper refinement of promising candidates; ExTS∗ reaches 47.4% overall.
  • Molecular elucidation: ExTS improves molecular ACC by +1.3% over K-MSE’s MCTSr in a near-zero-failure, stationary-score domain.Its gains come from exploitation shaping and a virtual child directing budget toward molecules benefiting from iterative refinement, despite an embedding-similarity reward gap.
  • Workflow optimization: On DROP workflow optimization, ExTS is Pareto-dominant, achieving the best accuracy, lowest variance, and lowest cost through productive moderate-depth nodes and quality gates.CoT incurs rising context cost from deep chains, whereas AFlow reduces cost but sacrifices robustness through stateless selection.

5 Understanding ExTS

ExTS’s gains cannot be reproduced by tuning standard MCTS alone because its redesign addresses flat rewards, expansion control, and score-agnostic branching. Diagnostics and ablations show that task structure determines effective settings, while selective refinement converts budget into stronger performance, especially on harder search problems.

  • Why standard MCTS tuning is insufficient: Standard MCTS reaches only 44.3–45.6% on LiveCodeBench across C=1.0–2.0, versus 46.2% for ExTS.A single exploration-exploitation scalar cannot address flat rewards, forced full expansion, or score-agnostic branching.
  • Diagnostic-guided adaptation: Coarse diagnostic-guided adaptation yields ExTS∗ variants that outperform all task-specific baselines despite non-exhaustive tuning.High experiment cost prevents exhaustive grid search, so the reported configurations may not be optimal.
  • Diagnostic-guided adaptation: 91.2% ACC (+0.2 pp), 91.54 F1 (+0.58 pp), and 47.4% (+1.2 pp) result from softened temperature settings across K-MSE, DROP, and LiveCodeBench.Softening T or τ to 0.5 hedges against tightly clustered scores and can also help when validation signals are inherently noisy.
  • Diagnostic-guided adaptation: 51.67% (+1.22 pp, 2.2× lower variance) follows from UCT with τgate=0 on high-drift HoVeR, while α=2.0 gives 66.00% (+1.11 pp) on high-failure HotpotQA.HoVeR has κ=0.16; HotpotQA has ρ=0.74, and reducing α to 1.0 causes −7.78 pp with 6.8× higher variance.
  • Component ablations: On HotpotQA, removing the failure penalty costs −7.78 pp, removing the virtual child costs −3.22 pp, and removing gated widening costs −2.34 pp.The virtual-child ablation restores wide-tree behavior, while gated widening restricts expansion to nodes whose quality justifies the budget cost.
  • Selective refinement and budget scaling: ExTS produces shallower leaves but deeper best nodes on non-trivial K-MSE cases, yielding +2.9 pp ACC and concentrating gains where refinement matters.ExTS has leaf depth 3.73 versus 4.43 for MCTSr, best-node depth 1.09 versus 1.03, and ACC 80.1% versus 77.2%.

6 Conclusion

ExTS is a quality-aware tree-search policy for budget-constrained LLM agent search that jointly redesigns selection and expansion. Across four diverse domains, it is competitive with or improves over task-specific baselines using one fixed configuration.

  • Core contribution: ExTS jointly redesigns selection and expansion for budget-constrained LLM agent search.It replaces flat UCT selection and unconditional expansion with quality-aware decisions.
  • Core contribution: ExTS shapes rewards for narrow score distributions, frames expansion as a value-of-information decision, and gates branching on node quality.
  • Empirical scope: Across four diverse domains, ExTS is competitive with or improves over task-specific baselines using a single fixed configuration.

Limitations · I Worked Example: The Virtual Child

The paper limits its empirical scope by using one model per domain and leaving model-scale effects and cross-family diagnostic transferability untested. Its pilot diagnostics characterize landscapes only for the specific model, scorer, and budget configuration used.

  • Limitations: The study uses a single model per domain because tree search incurs substantial API costs.Each experiment requires hundreds of LLM calls per task instance across multiple seeds.
  • Limitations: Model scale effects on the search landscape are not studied.The limitation follows from the single-model-per-domain design.
  • Limitations: Pilot-run diagnostics are conditioned on the model, scorer, and budget.They therefore describe the landscape as seen by that configuration rather than intrinsic domain properties.
  • Limitations: Transferability of the diagnostics across model families remains untested.The paper does not establish whether configuration-specific landscape descriptions generalize across model families.
  • Limitations: The diagnostic approach requires a pilot tree.The supplied passage introduces this requirement but is truncated before specifying further details.
  • Limitations: The paper attributes its restricted model coverage to the substantial API costs of tree search.The cost arises because experiments require hundreds of LLM calls per task instance across multiple seeds.

A Related Work · B Default Configuration and Complete Algorithm · C Formal Definitions of Pilot-Run Diagnostics

The paper positions ExTS as a reward-aware search-policy redesign for budget-constrained agentic search, contrasting it with LLM-specific harnesses and task-specific allocation methods. It also specifies a fixed default search configuration and formalizes four pilot-run diagnostics covering failures, score spread and drift, and refinement stochasticity.

  • A Related Work: Unlike many LLM search systems that retain vanilla UCT or use linear refinement, ExTS redesigns both selection and expansion across structurally distinct domains.The paper contrasts ExTS with harness-focused methods, linear chains, and systems such as LATS that add LLM components without modifying the tree policy.
  • A Related Work: ExTS differs from prior allocation methods by exploiting parent-child refinement structure rather than treating candidates as independent or targeting one task type.The paper contrasts it with AB-MCTS, GEPA, AFlow, sequential halving, Hyperband, and evolutionary optimizers operating at larger budgets or in different search families.
  • A Related Work: ExTS makes exploration and exploitation reward-aware by using observed validation rewards to control expansion value and branching width.Its virtual child estimates the value of creating a new branch from the parent’s reward history, rather than using fixed urgency or visit-count-only widening.
  • A Related Work: ExTS is presented as a drop-in search component for prompt, skill, workflow, molecular, linear, or greedy systems, with direct comparisons in workflow and molecular settings.The K-MSE evaluation keeps its scorer and knowledge base unchanged to isolate selection and expansion, while AFlow is directly compared as a workflow-search baseline.
  • B Default Configuration and Complete Algorithm: The complete ExTS loop is given in Algorithm 2, while Table 10 specifies the default hyperparameters fixed across all experiments.The loop operates until budget B is exhausted and includes separate backpropagation paths for failure and successful validation.
  • C Formal Definitions of Pilot-Run Diagnostics: The pilot-run framework defines four measurable diagnostics from a search tree T constructed with budget B.These diagnostics are failure rate ρ, normalized score deviation σ̂_f, score drift κ, and refinement variance σ̂_A.
  • C Formal Definitions of Pilot-Run Diagnostics: Failure rate ρ is the fraction of expansion attempts that fail validation, with failed outcomes including syntax errors, runtime errors, timeouts, or domain-specific rejection.By construction, ρ ∈ [0, 1], and ρ > 0.5 means more than half the budget is spent on failed attempts.
  • C Formal Definitions of Pilot-Run Diagnostics: Normalized score deviation σ̂_f measures score spread, score drift κ measures changes in normalized values as bounds evolve, and refinement variance σ̂_A isolates sibling-score stochasticity.Low σ̂_f indicates a flat landscape, high κ indicates frequent shifts from newly discovered candidates, and high σ̂_A makes resampling productive whereas low σ̂_A favors explicit exploration.

D Detailed Experimental Setup … D.4 Agentic Workflow Optimization

The experimental setup evaluates ExTS across prompt optimization, code generation, molecular structure elucidation, and agentic workflow optimization. Each task instantiates ExTS with task-specific candidate spaces, refinement operators, validators, benchmarks, and comparison strategies.

  • D.1 Prompt Optimization: Prompt optimization uses GEPA on HotpotQA and HoVeR, evaluating 300-example test sets with accuracy (%) across seeds {0, 42, 1024}.Experiments use Qwen3-8B via vLLM with TP=4, temperature 0.6, top-p 0.95, and thinking enabled.
  • D.1 Prompt Optimization: The prompt-optimization comparison matches budgets across Baseline, GEPA Pareto, ExTS default, and per-dataset ExTS∗ conditions.ExTS∗ uses α = 2.0 for HotpotQA and UCT exploration with τ = 0 for HoVeR.
  • D.2 Code Generation: Code generation evaluates ExTS on 182 LiveCodeBench v6 problems using public tests for search reward and private tests for pass@1.The problems comprise 45 easy, 55 medium, and 82 hard instances, with a budget of 128 steps per problem and seeds {0, 42, 1024}.
  • D.2 Code Generation: The code-generation baselines are StandardMCTS, AB-MCTS-A, and ExTS default, with ExTS∗ setting T = 0.5.StandardMCTS uses UCT with C = 2 and five samples per action; AB-MCTS-A uses Thompson sampling with a Gaussian conjugate prior.
  • D.3 Molecular Structure Elucidation: Molecular structure elucidation evaluates 216 MolPuzzle molecules using Morgan fingerprint Tanimoto similarity (FTS) and exact-match accuracy (ACC).Each example includes IR, carbon-13 and proton NMR spectra, and a molecular formula; ACC canonicalizes SMILES with RDKit.
  • D.3 Molecular Structure Elucidation: For molecular elucidation, ExTS revises SMILES using spectral critiques and retrieved substructures, validates chemical validity with RDKit, and compares against K-MSE’s original MCTSr.The scorer computes cosine similarity between predicted-molecule and target-spectrum embeddings scaled to [0, 100].
  • D.4 Agentic Workflow Optimization: Agentic workflow optimization uses AFlow on DROP, where Python workflow graphs are mutated from execution logs and past experience and validated on 200 problems.The executor is Claude Haiku 4.5, while the optimizer is Claude Sonnet 4.5; the test benchmark contains 800 problems scored by token-level F1.
  • D.4 Agentic Workflow Optimization: AFlow, linear CoT, and ExTS share the optimizer, executor, validation protocol, and test evaluation over 20 search rounds per seed.AFlow samples score-weighted random parents, CoT extends the deepest node without branching, and ExTS uses its default configuration; ExTS∗ sets τ = 0.5 and M0 = 4.

E Analysis Setup Details

The analysis evaluates ExTS against tree-search baselines under controlled model and component settings, then examines budget-scaling behavior across LiveCodeBench and HotpotQA. Tree-shape diagnostics distinguish trivial from non-trivial molecular problems, while budget experiments track cumulative performance as evaluations increase.

  • Tree-shape diagnostics: Tree-shape diagnostics compare MCTSr with ExTS at branching caps M0 = 2 and M0 = 3 under shared evaluation components.MCTSr uses binary expansion without gating, while all methods share the same scorer, retriever, and Claude Sonnet 4.6 LLM.
  • Tree-shape diagnostics: 124/216 molecular problems are trivial, while 92/216 are non-trivial based on whether any method improves beyond the root.Trivial problems have the best node at depth 0 for all methods and seeds; non-trivial problems have at least one improvement beyond the root.
  • Budget-scaling behavior: Budget-scaling experiments track cumulative performance across increasing evaluation budgets on LiveCodeBench and HotpotQA.LiveCodeBench uses B=128 across 182 problems and 3 seeds, measuring pass@1 from cumulative score trajectories; HotpotQA compares ExTS and GEPA over 78 search iterations and 3 seeds.

F More Ablations on LiveCodeBench · G Compact Diagnostic Guide

LiveCodeBench ablations show that quality-conditioned branching and root exclusion materially affect budget allocation, especially on hard problems. A compact diagnostic guide links four landscape properties to hyperparameter adjustments and specifies a default configuration when no pilot run is available.

  • F More Ablations on LiveCodeBench: −1.3 pp overall and −1.6 pp on hard problems result from removing gated progressive widening on LiveCodeBench.The ablation attributes these losses to budget waste on unpromising subtrees when quality-conditioned branching is removed.
  • F More Ablations on LiveCodeBench: −1.0 pp overall and −2.0 pp on hard problems result from removing root exclusion, with notably higher variance.Allowing the score gate to block root expansion can starve the tree of initial diversity when early candidates score poorly.
  • F More Ablations on LiveCodeBench: Table 12 reports a leave-one-out ablation on LiveCodeBench using pass@1 % across 3 seeds.This setup contextualizes the reported component-removal effects.
  • G Compact Diagnostic Guide: The diagnostic guide characterizes agentic search landscapes along failure rate, score spread, drift, and refinement variance.It presents these four diagnostics as both an analytic study of structural differences and a deployment aid.
  • G Compact Diagnostic Guide: Each diagnostic axis maps to a concrete hyperparameter adjustment for adapting agentic search.The guide condenses the pilot-run findings of Section 5.2 into a compact practical framework.
  • G Compact Diagnostic Guide: When no pilot is run, the default configuration uses PUCT with C = 1.0, α = 2, T = 0.3, M0 = 3, and τ = 0.25.The configuration is identified as the default in Table 10.

H Further Evaluation on an Additional Domain: GPU Kernel Optimization … K Artifact Documentation

ExTS generalizes to GPU kernel optimization, improving optimized MCTS across reported speedup metrics under a fixed, untuned configuration. A worked example illustrates virtual-child selection, while the paper discusses broader-impact limits and documents artifact use.

  • H Further Evaluation on an Additional Domain: GPU Kernel Optimization: ExTS was evaluated beyond the four main domains using Gai et al.’s setup and original settings, with MCTS (optimized) as the comparison baseline.The evaluation covered 40 tasks and used a single run because of the domain’s substantial compute cost.
  • H Further Evaluation on an Additional Domain: GPU Kernel Optimization: 4.36× geometric-mean speedup versus 4.15× for MCTS (optimized) on 40 GPU-kernel tasks, with ExTS improving every reported metric.The single-run evaluation used Claude Opus 4.6, one NVIDIA A100 40GB GPU per task, and ExTS’s fixed default configuration without tuning or diagnostics.
  • I Worked Example: The Virtual Child: 0.237 versus 0.245: the virtual child’s ExUCT score is just below the best real child at pivotal node v1.The worked example reconstructs iteration 104, where the search descends root → v1 → v3 → v7 and expands v7.
  • I Worked Example: The Virtual Child: 0.256: widening wins only when three sampled shaped rewards exceed the relevant threshold, so ExTS deepens into v3 about three quarters of the time.That descent continues to leaf v7, whose expansion produces the global best score of 68.67.
  • J Ethical Considerations and Broader Impact: ExTS could potentially accelerate harmful agent-based systems, but the method only reallocates evaluation budget and does not add capabilities beyond existing LLM agents.The experiments use publicly available benchmarks and models accessed through standard APIs.
  • K Artifact Documentation: Frameworks serve as search harnesses, datasets and benchmarks are used for evaluation, and models are accessed through supported APIs or inference engines.The artifact documentation records licenses and whether usage is consistent with intended purpose.
Loading 2608.23848v1…