# How Should a Prompt Optimizer Spend a Tight Budget? BudgetAPO with Noise-Adaptive Evaluation

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 43 references that are in the map.
- First posted on arXiv 5 Oct 2026.

## Builds on (most cited first, 11 of 11)

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [DSPy: Compiling Declarative Language Model Calls into Self-Improving Pipelines](https://mlsanity.com/paper/2310.03714/) (2023)
- [GLM-5: from Vibe Coding to Agentic Engineering](https://mlsanity.com/paper/2602.15763/) (2026)
- [Promptbreeder: Self-Referential Self-Improvement Via Prompt Evolution](https://mlsanity.com/paper/2309.16797/) (2023)
- [tinyBenchmarks: evaluating LLMs with fewer examples](https://mlsanity.com/paper/2402.14992/) (2024)
- [Gemma 4 Technical Report](https://mlsanity.com/paper/2607.02770/) (2026)
- [Generalizing Verifiable Instruction Following](https://mlsanity.com/paper/2507.02833/) (2025)
- [CAPO: Cost-Aware Prompt Optimization](https://mlsanity.com/paper/2504.16005/) (2025)
- [More Is Not Always Better: Cross-Component Interference in LLM Agent Scaffolding](https://mlsanity.com/paper/2605.05716/) (2026)
- [Instruction Stacking Collapse: A Benchmark and the Capability-Dependent Value of Prompt Compilation](https://mlsanity.com/paper/2608.02639/) (2026)

## Abstract (arXiv)

Automatic prompt optimization (APO) has been widely employed to adapt large language models without updating their weights, yielding promising results. However, existing methods such as GEPA and OPRO assume hundreds to thousands of subject-model calls, far more than is practical behind paid, rate-limited APIs. Under tight budgets they fail in two ways: multi-stage pipelines can exhaust the budget and return the seed prompt unchanged, while single-stage methods compare candidates on fixed-size minibatches, regardless of each task's noise. As a remedy, we introduce BudgetAPO, a single-stage optimizer for the tight-budget regime. BudgetAPO incorporates (1) a noise-adaptive rule that sizes the evaluation slice to each task's noise, measured by a short probe; (2) a fixed slice that turns every accept/reject decision into a paired comparison; and (3) a reflective operator that rewrites reasoning strategy and output format jointly. Extensive results across seven benchmarks and five subject models demonstrate that BudgetAPO ranks first on every subject and beats every baseline under Holm-corrected paired tests, while returning the seed in 13% of runs at 250 calls against 86% for GEPA. On GPT-OSS-20B, GEPA needs 5 times as many calls to match method's 100-call score.