# ZEBRA: Zero-shot Budgeted Resource Allocation for LLM Orchestration

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 33 references that are in the map.
- First posted on arXiv 19 May 2026.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023)
- [Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs](https://mlsanity.com/paper/2412.21187/) (2024)
- [Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.16419/) (2025)
- [Token-Budget-Aware LLM Reasoning](https://mlsanity.com/paper/2412.18547/) (2024)
- [Budget-Aware Tool Use Enables Effective Agent Scaling](https://mlsanity.com/paper/2511.17006/) (2025)
- [Difficulty-Aware Agentic Orchestration for Query-Specific Multi-Agent Workflows](https://mlsanity.com/paper/2509.11079/) (2025)
- [Self-Resource Allocation in Multi-Agent LLM Systems](https://mlsanity.com/paper/2504.02051/) (2025)
- [Controlling Performance and Budget of a Centralized Multi-agent LLM System with Reinforcement Learning](https://mlsanity.com/paper/2511.02755/) (2025)
- [Shapley-Coop: Credit Assignment for Emergent Cooperation in Self-Interested LLM Agents](https://mlsanity.com/paper/2506.07388/) (2025)
- [SEER : A Knapsack approach to Exemplar Selection for In-Context HybridQA](https://mlsanity.com/paper/2310.06675/) (2023)
- [Orchestrating Agents and Data for Enterprise: A Blueprint Architecture for Compound AI](https://mlsanity.com/paper/2504.08148/) (2025)
- [Hierarchical Budget Policy Optimization for Adaptive Reasoning](https://mlsanity.com/paper/2507.15844/) (2025)
- [ROI-Reasoning: Rational Optimization for Inference via Pre-Computation Meta-Cognition](https://mlsanity.com/paper/2601.03822/) (2026)
- [Budget-Constrained Agentic Large Language Models: Intention-Based Planning for Costly Tool Use](https://mlsanity.com/paper/2602.11541/) (2026)
- [BAMAS: Structuring Budget-Aware Multi-Agent Systems](https://mlsanity.com/paper/2511.21572/) (2025)
- [A Knapsack by Any Other Name: Presentation impacts LLM performance on NP-hard problems](https://mlsanity.com/paper/2502.13776/) (2025)
- [Predictive Scheduling for Efficient Inference-Time Reasoning in Large Language Models](https://mlsanity.com/paper/2602.01237/) (2026)
- [Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear Utilities](https://mlsanity.com/paper/2302.03781/) (2023)

## Built on by (most cited first, 2 of 2)

- [R3-Bench: LLMs Struggle with Resource-Rational Reasoning under Shared Budgets](https://mlsanity.com/paper/2608.16033/) (2026)
- [Scaling Inference-Time Compute with Teams of Coding Agents](https://mlsanity.com/paper/2610.17471/) (2026)

## Abstract (arXiv)

As autonomous agents increasingly execute end-to-end tasks under fixed monetary budgets, the pressing open question shifts from whether the budget is respected, to how to spend it effectively. Existing budget-aware methods typically control reasoning step-by-step within a single agent, or learn resource allocation policies via RL. None address how to split a budget across the composing phases of a multi-agent pipeline at inference time. We propose ZEBRA, a zero-shot framework that reduces multi-phase budget allocation to a continuous nonlinear knapsack problem: an LLM controller estimates per-phase utility curves, and a water-filling search on the Lagrange multiplier returns the per-phase split. Additive and multiplicative aggregations are unified under the same solver. On a 150-task APPS coding benchmark, both ZEBRA variants outperform LLM-direct (budget allocation directly by an LLM) on every aggregate metric. At a budget of α = 0.5 of the unconstrained spend, ZEBRA recovers 94.4% of unconstrained quality, versus 88.1% for LLM-direct. The advantage is statistically significant and transfers beyond coding: on a 3-phase HotpotQA pipeline, ZEBRA beats LLM-direct by 14.3pp, with allocations empirically robust to curve-estimation noise. On HotpotQA, ZEBRA arrives at a different budget split (near-balanced) compared to the APPS one (skewed towards a refinement phase), showing adaptation to the pipeline structure. More broadly, we show that lightweight algorithmic guidance at inference time can improve the economic behavior of autonomous multi-agent systems.