🤖 machine learning

Budget-Aware LLM Discovery via Cost-Calibrated Frontier Utility

This paper introduces **CostAda**, a cost-calibrated adaptive controller that optimizes LLM discovery by dynamically allocating search resources based on the ratio of quality gain to token cost, thereby achieving superior or equivalent results with significantly reduced budgets compared to existing methods.

Original authors: Yansen Zhang, Yilu Liu, Tianyu Liu, Jiamin Chen, Xiaokun Zhang, Kai Xie, Xue Liu, Chen Ma, Yiyan Qi

Published 2026-07-30

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Yansen Zhang, Yilu Liu, Tianyu Liu, Jiamin Chen, Xiaokun Zhang, Kai Xie, Xue Liu, Chen Ma, Yiyan Qi

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

Imagine a team of brilliant detectives trying to solve a series of incredibly complex puzzles. They have a limited supply of "thinking tokens"—a magical currency that pays for every word they write, every clue they search for, and every hypothesis they test. In the world of Artificial Intelligence, these tokens are the real cost of using Large Language Models (LLMs) to discover new scientific formulas, design better algorithms, or write perfect computer code. For a long time, the "controllers" (the managers of these detective teams) only cared about one thing: Did the score go up? If a detective solved a tiny clue or a massive mystery, and both gave the same score boost, the manager treated them exactly the same. But here's the catch: solving the tiny clue cost one token, while solving the massive mystery cost six. If the manager kept paying for expensive moves just because the score ticked up, the team would run out of money long before they found the best solution. The big question for scientists is: How do you manage a team when every move costs a different amount, and you have a strict budget to stay within?

This paper introduces a new, smarter manager called CostAda. The researchers found that the old way of managing—ignoring how much a move actually cost—was a recipe for disaster. They proved mathematically that if you don't adjust your credit based on the price tag, you might end up with almost zero progress as the search gets more complicated. CostAda changes the game by looking at the "bang for the buck." It asks: "Is this score improvement worth the tokens we just spent?" If a move is expensive, CostAda demands a bigger reward before it approves the next step. It also keeps a close eye on the remaining budget. Early in the game, when money is plentiful, it's okay to take a few expensive risks to find a new path. But as the budget runs low, the manager becomes strict, only approving moves that are cheap and proven to work, or saving the last few tokens for a big, game-changing guide.

The team tested this new manager on twelve different puzzle sets (benchmarks) using two different AI brains (GLM-5 and GPT-5.4). The results were impressive. In twelve out of sixteen test cases, CostAda managed to find solutions just as good as the best previous methods, but it did so using at most half the budget. In other words, it got the same high-quality results for 50% of the price. Across all eight major challenges, CostAda consistently achieved the highest average final quality. The researchers showed that by treating the cost of every action as a critical part of the decision-making process—rather than just a receipt to look at later—the AI can explore more efficiently, avoid wasting money on dead ends, and reach the finish line faster and smarter. It's like realizing that sometimes, taking the expensive highway is a waste of gas, but knowing exactly when to pay for it to get there first is the key to winning the race.

Technical Summary: Budget-Aware LLM Discovery via Cost-Calibrated Frontier Utility

Problem Formulation

Large language models (LLMs) are increasingly employed for scientific and algorithmic discovery through inference-time search, where candidate solutions are generated, evaluated, and refined sequentially. In domains such as mathematical optimization, algorithm design, and executable program discovery, deterministic evaluators provide repeatable quality signals. However, existing adaptive discovery controllers typically assign credit to search actions based solely on score progress, ignoring the heterogeneity of action costs.

Under token-based API pricing, different search actions incur vastly different costs. A short refinement may cost one reference generation, while a long-context guidance call or a retry of invalid code may cost six or more. When a controller credits a high-cost action and a low-cost action equally because they yield the same score improvement, it fails to account for the opportunity cost of the remaining budget. The paper formalizes this as a population-level allocation problem over a discrete space of executable candidates, where the effective search horizon is defined by a cumulative, realized token budget rather than a fixed number of iterations.

The authors prove (Proposition 1) that in instances with heterogeneous action costs, a "cost-blind" controller—one whose action distribution depends only on score history and not realized costs—can attain only a vanishing fraction of the optimal budgeted objective as the number of search frontiers and cost disparities increase.

Methodology: CostAda

To address this gap, the authors introduce CostAda, a cost-calibrated adaptive controller designed for LLM discovery under explicit search-side token budgets. CostAda replaces progress-only credit with cost-calibrated frontier utility, which integrates local frontier progress, global best-so-far improvement, realized action cost, and the remaining budget.

The core mechanism operates through three coupled controls:

Cost-Calibrated Frontier Utility:
The utility $u_t^{(k)}$ for a frontier $k$ at iteration $t$ is defined as:
$u_t^{(k)} = \frac{\lambda_t g_t + (1 - \lambda_t) \delta_t^{(k)}}{d_t}$
Where:
- $g_t$ is the global gain (improvement over the global best-so-far).
- $\delta_t^{(k)}$ is the local gain (improvement over the frontier's local archive).
- $\lambda_t = 1 - \rho_t$ is the global weight, conditioned on the remaining budget ratio $\rho_t$ . As the budget drains, the controller shifts focus from local development to global improvement.
- $d_t = 1 + \lambda_t^c \phi_t$ is a cost divisor based on the normalized realized step cost. This ensures that equal gains from expensive actions receive less credit than cheap ones.
Budget-Aware Control Decisions:
- Local Exploration Intensity: The sampling breadth around a frontier is adjusted based on its smoothed utility. High utility leads to low-intensity refinement; low utility triggers broader exploration. Crucially, the remaining budget ratio $\rho_t$ suppresses expensive exploration as the budget nears exhaustion.
- Frontier Allocation: The controller allocates future budget to frontiers based on global gain per realized cost ( $r_t^{(k)} = g_t / d_t$ ). Frontiers that improve only against weak local archives receive no allocation credit. An upper-confidence bound rule balances exploitation of high-performing frontiers with exploration of under-sampled ones, gated by the remaining budget.
- Budgeted Tactic Intervention: Higher-level guidance (e.g., "guide" or "tactic" calls) is purchased only when specific evidence predicates are met: (1) the remaining budget can afford the guide plus a reserve for testing; (2) there is a sustained absence of global progress (stagnation) or accumulated low-yield spending; and (3) no consolidation window is active. This prevents expensive interventions near the horizon unless they are strictly necessary.

Key Contributions

Problem Formulation and Theoretical Bound: The paper formalizes LLM discovery under explicit search-side token budgets and proves that cost-blind credit strategies forfeit the budgeted objective in heterogeneous-cost settings.
Cost-Calibrated Frontier Utility: The authors introduce a credit principle that conditions progress on realized action cost and remaining budget, ensuring that the opportunity cost of each action is explicit.
CostAda Controller: An instantiation of this principle that coordinates budget-gated local exploration, cost-aware frontier allocation, and budgeted tactic intervention.
Empirical Validation: Extensive experiments demonstrating that CostAda achieves superior budget efficiency and final solution quality compared to state-of-the-art baselines.

Experimental Results

The authors evaluated CostAda against AdaEvolve (a progress-aware baseline) and EvoX (a strategy-evolution controller) across eight benchmarks (spanning geometric packing, extremal geometry, additive combinatorics, and executable program optimization) using two backbone models: GLM-5 and GPT-5.4.

Efficiency: CostAda reaches the strongest baseline's full-budget quality with at most half the budget in 12 out of 16 benchmark–backbone pairs.
Final Quality: Across both backbones, CostAda achieves the strongest mean final quality on all eight benchmarks.
Budget Path: At a quarter of the budget, CostAda's average normalized score exceeds the strongest baseline's full-budget average. It attains the highest normalized Area Under the Curve (AUC) on 15 of 16 benchmark–backbone pairs.
Stability: CostAda demonstrates lower variance in results compared to baselines, particularly on benchmarks like Circle Packing Rect under GLM-5.

Significance and Claims

The paper claims that CostAda fundamentally changes how search resources are managed in LLM-driven discovery. By treating realized cost and remaining budget as active control inputs rather than post-hoc accounting variables or simple stopping rules, CostAda aligns the search strategy with the economic reality of token-based pricing.

The authors assert that their approach preserves final solution quality while significantly improving budget efficiency. The results suggest that cost calibration is essential for scaling LLM discovery, as ignoring cost heterogeneity leads to suboptimal resource allocation that cannot be recovered by simply smoothing progress signals. The work demonstrates that a controller can effectively navigate the trade-off between exploration and exploitation when the "cost" of an action is as variable as the "gain" it produces.