🤖 AI

Exploit More, Explore Smarter for Budget-Constrained Agentic Search

This paper introduces ExTS, a novel tree-search policy that optimizes budget-constrained agentic search by treating expansion as a value-of-information decision through discriminative reward shaping, stochastic virtual children, and quality-conditioned branching, achieving consistent performance improvements across diverse tasks compared to standard methods.

Original authors: Haoyang Fang, Bernie Wang

Published 2026-08-26

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Haoyang Fang, Bernie Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the rapidly evolving world of artificial intelligence, a new class of systems has emerged that does not just answer questions but actively searches for solutions. These "agentic" systems act like digital explorers, proposing ideas, testing them, and refining their best guesses over and over again. Whether they are writing computer code, designing chemical compounds, or solving complex logic puzzles, these agents rely on a cycle of generation and validation. They create a candidate solution, run it through a test to see how well it works, and then use that feedback to create a better version. However, this process is expensive. Every time the system generates a new idea or runs a test, it consumes a limited resource: a computational budget. In many real-world scenarios, this budget is tight, allowing for only a few dozen or a few hundred attempts before the system must stop. The central challenge for researchers is how to spend this limited budget wisely. If the system wastes its attempts on dead ends, it fails to find the best possible solution. If it is too cautious, it might miss a breakthrough that lies just a few steps further down a promising path.

For years, the standard method for navigating these search trees has been a strategy borrowed from game-playing algorithms, which balances two competing instincts: exploration and exploitation. Exploration means trying out new, untested paths to see if they hold promise, while exploitation means digging deeper into paths that have already shown good results. The traditional approach treats every new branch of the search tree with a certain amount of curiosity, often expanding all available options before committing to any single one. This works well when there is plenty of time and money to explore everything. But in the high-stakes, budget-constrained world of modern AI agents, this "try everything" approach often fails. It spreads the limited resources too thinly across a wide, shallow tree, leaving the most promising ideas underdeveloped. The system ends up with a broad map of many mediocre solutions rather than a deep understanding of a few excellent ones.

To solve this, researchers at Amazon AGI have introduced a new search policy called ExTS. Instead of blindly expanding every branch, this new method treats the decision to create a new branch as a calculated investment. It asks a critical question before spending any budget: is the potential value of creating a new path worth the cost? The system does this by looking at the history of its own successes and failures. If a particular line of reasoning has produced many failed attempts, the system learns to stop expanding that path and instead focuses its energy on deepening the lines that are already working. It effectively filters out the noise, ignoring the dead ends that would have consumed valuable resources in older systems.

The researchers tested this approach across four very different fields: optimizing instructions for language models, generating computer code, deducing the structure of molecules from spectral data, and designing automated workflows. In each case, they gave the new system the same tight budget that previous methods had to work with. The results were consistent. By being smarter about where to spend its money, the new system consistently found better solutions than the specialized methods designed for each specific task. For example, in the task of optimizing prompts for question-answering, the new method improved accuracy by more than ten percent compared to the previous best approach. In code generation, it solved significantly more difficult problems, finding solutions that the older methods missed. Even in the highly technical field of molecular structure elucidation, where the system had to figure out the shape of a molecule from its spectral signature, the new method achieved higher accuracy with the same number of attempts.

A key insight behind this success is that the new system does not just look at the score of a single attempt; it looks at the pattern of scores. In many of these tasks, the difference between a good solution and a great one is subtle, and the scores can be clustered very closely together. The old methods struggled to tell the difference, treating all options as roughly equal. The new system uses a technique to amplify these small differences, allowing it to distinguish between a slightly better path and a truly excellent one. It also uses a "virtual child" concept to simulate what might happen if it were to create a new branch. By sampling from the history of what has worked before, it can estimate the value of a new path without actually spending the budget to build it. If the simulation suggests the new path is unlikely to be fruitful, the system skips it entirely and goes deeper into the proven path.

The researchers also discovered that not all search problems are the same. Some tasks are prone to frequent failures, where most attempts result in errors, while others are more stable. Some tasks have scores that shift wildly as new discoveries are made, while others remain steady. The new system is flexible enough to adapt to these different landscapes. By running a small, preliminary test to understand the nature of the problem, the system can adjust its strategy slightly to match the specific challenges of the task. This adaptability allows it to perform well across a wide variety of domains without needing a completely new design for each one.

The study demonstrates that the way an AI agent spends its computational budget is just as important as the intelligence it possesses. By redesigning the search process to be more selective and more aware of the quality of its own progress, the system can achieve significantly better results with the same amount of effort. This approach offers a practical guide for building more efficient AI agents that can solve complex problems without requiring endless computing power. The findings suggest that in the future, the most effective AI systems will not necessarily be the ones that try the most things, but the ones that know exactly which things are worth trying.

Technical Summary: Exploit More, Explore Smarter for Budget-Constrained Agentic Search

Problem Definition

The paper addresses budget-constrained agentic search, a regime where Large Language Model (LLM) agents must iteratively propose and refine candidates (e.g., prompts, code, molecular structures) under a strict evaluation budget. In these scenarios, validation is expensive, generation requires multiple model calls, or both. The total budget is often limited to tens or hundreds of calls.

The authors identify that standard Monte Carlo Tree Search (MCTS), specifically the Upper Confidence Bound applied to Trees (UCT) policy, performs poorly in this regime due to three structural limitations:

Exploration-bonus dominance: At low visit counts, the exploration term dominates, causing the algorithm to treat unpromising nodes as equally attractive as promising ones.
Forced full expansion: Standard MCTS forces the expansion of all siblings before deepening a promising chain, wasting budget on unpromising branches.
Score-agnostic branching: Expansion decisions are independent of node quality; the algorithm does not gate branching based on whether a node's score justifies the cost.

Existing solutions often focus on the "harness" (frameworks wrapping the search) or target specific task types with custom algorithms (e.g., Thompson sampling for code, Pareto-frontier selection for prompts), lacking a unified policy that adapts to diverse agentic problems.

Methodology: ExTS

The authors introduce ExTS (Exploit More, Explore Smarter), a tree-search policy that jointly redesigns node selection and expansion decisions. ExTS treats expansion itself as a Value-of-Information (VOI) decision. It operates through three core mechanisms:

1. Discriminative Reward Shaping

To address the issue of raw validation scores clustering in narrow ranges (making nodes appear equally attractive), ExTS applies a non-linear shaping function $\phi$ to rewards.

Mechanism: It uses a temperature-controlled convex function $\phi(r) = \frac{e^{\hat{r}/T} - 1}{e^{1/T} - 1}$ (where $T < 1$ ) to compress low scores and amplify high scores.
Success-Rate Weighting: It incorporates a success-rate weight $(n^+_v / n_v)^\alpha$ to discount nodes whose subtrees produce mostly invalid outputs (failures).
Result: This creates effective selection signals even when raw scores are tightly clustered, allowing the algorithm to distinguish between candidates.

2. VOI Estimation via the Virtual Child

ExTS reframes expansion as a decision between deepening an existing chain or creating a new branch.

Mechanism: At any internal node, ExTS computes a virtual child score. This virtual child represents the expected value of creating a new branch.
Sampling: The virtual child's score is estimated by sampling $k$ scores from the parent's reward history (including the parent's own score) and applying the shaping function. The number of samples $k$ is proportional to the "fair-share" visit count, capturing finite-sample uncertainty.
Decision: The algorithm compares the score of the best real child against the virtual child. If the virtual child's score is higher, the algorithm selects the current node for expansion (creating a new branch); otherwise, it recurses into the best real child. This allows the search to deepen promising chains without fully expanding unpromising siblings first.

3. Quality-Conditioned Branching

ExTS restricts expansion based on node quality to prevent budget waste.

Expansion Gate: Non-root nodes are only permitted to expand if their validation score exceeds a $\tau$ -quantile of the population scores. Below-threshold nodes can still be visited and updated but cannot spawn new children.
Quality-Gated Progressive Widening: The maximum branching factor grows with visit count (progressive widening) only for nodes whose quality justifies the cost (i.e., those above a higher quantile $\gamma$ ). Low-scoring nodes remain capped at a small initial branching factor $M_0$ .

Key Contributions

Unified Policy: ExTS provides a single, fixed configuration that is competitive with or improves upon task-specific baselines across four diverse domains: prompt optimization, code generation, molecular structure elucidation, and agentic workflow optimization.
Structural Redesign: Unlike prior work that merely tunes exploration constants, ExTS introduces structural mechanisms (virtual children, quality gating) to decide where and when to expand, rather than just how much to explore.
Pilot-Run Diagnostics: The authors introduce four diagnostics ( $\hat{\sigma}_A$ , $\hat{\sigma}_f$ , $\kappa$ , $\rho$ ) to characterize the search landscape of a task. These metrics explain why different tasks respond to different configurations and offer practical guidance for adapting hyperparameters (e.g., adjusting temperature $T$ for low-drift tasks or the success exponent $\alpha$ for high-failure tasks).

Results

ExTS was evaluated across four domains with a single fixed configuration, and an adapted version ( $ExTS^*$ ) that adjusts 1-2 hyperparameters based on pilot diagnostics.

Prompt Optimization (HotpotQA, HoVeR): ExTS improved over the GEPA Pareto baseline by +10.8% on HotpotQA (with 6.4 $\times$ lower variance) and matched performance on HoVeR. The adapted $ExTS^*$ further improved HotpotQA to 66.00%.
Code Generation (LiveCodeBench): On the "hard" split, ExTS achieved 19.1% pass@1, outperforming AB-MCTS-A (17.1%) and Standard MCTS (18.1%). The fixed configuration achieved 46.2% overall pass@1, while the adapted version ( $ExTS^*$ ) reached 47.4%.
Molecular Structure Elucidation (K-MSE): ExTS improved exact-match accuracy by +1.3% over the K-MSE baseline (91.0% vs 89.8%).
Agentic Workflow Optimization (DROP): ExTS achieved Pareto dominance with a mean accuracy of 90.96% (lowest variance and cost) compared to CoT and AFlow baselines. The adapted version ( $ExTS^*$ ) further improved the mean accuracy to 91.54%.
Budget Scaling: ExTS demonstrates more efficient budget-to-performance conversion, particularly on hard instances where iterative refinement is critical. It overtakes standard MCTS at low budgets (e.g., $B \approx 8$ ) and maintains a widening gap as budget increases.

Significance and Claims

The paper claims that ExTS represents a shift from tuning exploration constants to structural redesign of the search policy. The authors argue that in budget-constrained regimes, the decision of whether to expand is as consequential as which child to visit.

Generalizability: A single fixed configuration works across structurally distinct domains, suggesting that the mechanisms of reward shaping, virtual child estimation, and quality gating address fundamental limitations of MCTS in validation-heavy search.
Adaptability: The pilot-run diagnostics provide a practical framework for understanding the "shape" of agentic search problems, explaining why no single configuration dominates universally and offering a path for lightweight adaptation.
Efficiency: By gating expansion on quality and framing it as a VOI decision, ExTS redirects budget from breadth-first exploration to selective refinement, achieving superior performance with the same or lower computational cost.

The authors note limitations, including the reliance on a single model per domain due to API costs and the fact that pilot diagnostics describe the landscape as seen by a specific configuration rather than intrinsic domain properties. However, they demonstrate that even without pilot adaptation, ExTS outperforms or matches specialized baselines.