# Budget-Aware LLM Discovery via Cost-Calibrated Frontier Utility

arXiv: https://arxiv.org/abs/2607.26828 · HTML: https://mlsanity.com/paper/2607.26828/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 46 references that are in the map.
- First posted on arXiv 29 Jul 2026.

## Builds on (most cited first, 30 of 32)

- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning](https://mlsanity.com/paper/2507.19457/) (2025)
- [Automated Design of Agentic Systems](https://mlsanity.com/paper/2408.08435/) (2024)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model](https://mlsanity.com/paper/2401.02051/) (2024)
- [Token-Budget-Aware LLM Reasoning](https://mlsanity.com/paper/2412.18547/) (2024)
- [ShinkaEvolve: Towards Open-Ended And Sample-Efficient Program Evolution](https://mlsanity.com/paper/2509.19349/) (2025)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [LLM-SR: Scientific Equation Discovery via Programming with Large Language Models](https://mlsanity.com/paper/2404.18400/) (2024)
- [Learning to Discover at Test Time](https://mlsanity.com/paper/2601.16175/) (2026)
- [LLaMEA: A Large Language Model Evolutionary Algorithm for Automatically Generating Metaheuristics](https://mlsanity.com/paper/2405.20132/) (2024)
- [AdaEvolve: Adaptive LLM Driven Zeroth-Order Optimization](https://mlsanity.com/paper/2602.20133/) (2026)
- [EvoX: Meta-Evolution for Automated Discovery](https://mlsanity.com/paper/2602.23413/) (2026)
- [CORAL: Towards Autonomous Multi-Agent Evolution for Open-Ended Discovery](https://mlsanity.com/paper/2604.01658/) (2026)
- [SelfBudgeter: Adaptive Token Allocation for Efficient LLM Reasoning](https://mlsanity.com/paper/2505.11274/) (2025)
- [Budget-Aware Tool Use Enables Effective Agent Scaling](https://mlsanity.com/paper/2511.17006/) (2025)
- [Evolving Code with A Large Language Model](https://mlsanity.com/paper/2401.07102/) (2024)
- [Reasoning on a Budget: A Survey of Adaptive and Controllable Test-Time Compute in LLMs](https://mlsanity.com/paper/2507.02076/) (2025)
- [BudgetThinker: Empowering Budget-aware LLM Reasoning with Control Tokens](https://mlsanity.com/paper/2508.17196/) (2025)
- [DeltaEvolve: Accelerating Scientific Discovery through Momentum-Driven Evolution](https://mlsanity.com/paper/2602.02919/) (2026)
- [Structured Scaling of AI Discovery Across Diverse Scientific Domains](https://mlsanity.com/paper/2604.19341/) (2026)
- [AgentTTS: Large Language Model Agent for Test-time Compute-optimal Scaling Strategy in Complex Tasks](https://mlsanity.com/paper/2508.00890/) (2025)
- [Inference-Time Budget Control for LLM Search Agents](https://mlsanity.com/paper/2605.05701/) (2026)
- [The Art of Scaling Test-Time Compute for Large Language Models](https://mlsanity.com/paper/2512.02008/) (2025)
- [BAMAS: Structuring Budget-Aware Multi-Agent Systems](https://mlsanity.com/paper/2511.21572/) (2025)
- [Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs](https://mlsanity.com/paper/2602.09574/) (2026)
- [PACEvolve++: Improving Test-time Learning for Evolutionary Search Agents](https://mlsanity.com/paper/2605.07039/) (2026)

## Abstract (arXiv)

Large language models increasingly support scientific and algorithmic discovery through inference-time search over evaluated candidates. Existing adaptive discovery controllers assign credit based only on score progress, even though prompt length, retries, and guidance calls cause search actions to incur different token costs. Under a fixed search budget, the controller must decide which frontier to develop and whether its gain justifies the realized cost before the budget is exhausted. We prove that, in the worst case, cost-blind control can forfeit all but a vanishing fraction of attainable quality as frontier count and cost heterogeneity grow. To address this limitation, we introduce CostAda, an adaptive controller built on cost-calibrated frontier utility. By valuing progress relative to realized action cost and conditioning credit on the remaining budget, CostAda coordinates local exploration intensity, frontier allocation, and budgeted tactic intervention. Realized action cost and remaining budget therefore shape the search rather than serving only as accounting variables or a stopping rule. Across eight benchmarks with GLM-5 and GPT-5.4, CostAda reaches the strongest baseline's full-budget quality with at most half the budget on thirteen of sixteen benchmark--backbone pairs and achieves the strongest final quality on all sixteen pairs.