ZEBRA: Zero-shot Budgeted Resource Allocation for LLM Orchestration

• URL: http://arxiv.org/abs/2605.20485v1
• Date: Tue, 19 May 2026 20:50:05 GMT
• Title: ZEBRA: Zero-shot Budgeted Resource Allocation for LLM Orchestration
• Abstract summary: We propose ZEBRA, a framework that reduces multi-phase budget allocation to a continuous nonlinear knapsack problem.<n>On a $150$-task APPS coding benchmark, both ZEBRA variants outperform LLM-direct on every aggregate metric.<n>We show that lightweight algorithmic guidance at inference time can improve the economic behavior of autonomous multi-agent systems.
• Score: 8.226365534099399
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.3$pp, 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.

Related papers

• One Policy, Any Budget: Internalizing Budget-Aware Search via Reinforcement Learning [41.55260785497756]
  We propose AnySearch, a framework that enables a single policy to perform budget-aware search under any budget constraint.<n>In the first phase, we train the agent with explicit budget state injection and structured reasoning prompts.<n>In the second phase, the scaffold is removed and the agent learns to operate autonomously under adaptively sampled budget constraints.
  arXiv  Detail & Related papers  (2026-09-01T07:12:32Z)
• Learning When to Act: Communication-Efficient Reinforcement Learning via Run-Time Assurance [0.27998963147546146]
  We show that a single policy can learn control inputs and communication-efficient timing decisions under a pointwise Lyapunov safety shield.<n>A run-time assurance layer overrides the policy via a one-step-ahead Lyapunov prediction and a precomputed LQR backup.<n>A 12-state 3D quadrotor case study extends the framework to higher-dimensional systems where classical STC is intractable.
  arXiv  Detail & Related papers  (2026-05-11T23:55:15Z)
• Compute Where it Counts: Self Optimizing Language Models [10.058821474955177]
  We study dynamic budget allocation for autoregressive decoding.<n>We train the policy with group-relative policy optimization on teacher-forced episodes.<n>Our reward trades off language-model quality against soft penalties that encourage episode-average budget usage.
  arXiv  Detail & Related papers  (2026-05-11T17:27:15Z)
• Adaptive Test-Time Compute Allocation for Reasoning LLMs via Constrained Policy Optimization [18.737087162461563]
  Test-time compute scaling has become a powerful lever for improving large language model performance.<n>Yet deploying these techniques under finite inference budgets requires a decision that current systems largely ignore.<n>We formalize this as a constrained optimization problem (maximize expected accuracy subject to an average compute budget) and solve it with a two-stage Solve-then-Learn pipeline.
  arXiv  Detail & Related papers  (2026-04-16T10:39:22Z)
• $\nabla$-Reasoner: LLM Reasoning via Test-Time Gradient Descent in Latent Space [71.23672814629448]
  $nabla$-Reasoner is an iterative generation framework that integrates differentiable optimization over token logits into the decoding loop.<n>$nabla$-Reasoner achieves over 20% accuracy improvement on a challenging mathematical reasoning benchmark.
  arXiv  Detail & Related papers  (2026-03-05T08:42:54Z)
• Pay for Hints, Not Answers: LLM Shepherding for Cost-Efficient Inference [7.865726406769634]
  Small Language Models (SLMs) offer dramatic cost savings yet lag substantially in accuracy.<n>We introduce LLM Shepherding, a framework that requests only a short prefix (a hint) from the LLM and provides it to SLM.<n>Shepherding generalizes both routing and cascading, and it achieves lower cost under oracle decision-making.
  arXiv  Detail & Related papers  (2026-01-29T18:52:54Z)
• Phase Transition for Budgeted Multi-Agent Synergy [41.486076708302456]
  Multi-agent systems can improve reliability, yet under a fixed inference budget they often help, saturate, or even collapse.<n>We develop a minimal and calibratable theory that predicts these regimes from three binding constraints of modern agent stacks.
  arXiv  Detail & Related papers  (2026-01-24T05:32:50Z)
• Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharing [52.124267908936396]
  The model is composed of $M$ arms and $K$ plays.<n>Each arm has a number of capacities, and each unit of capacity is associated with a reward function.<n>When multiple plays compete for the arm capacity, the arm capacity is allocated in a larger priority weight first manner.
  arXiv  Detail & Related papers  (2025-12-25T11:19:09Z)
• Controlling Performance and Budget of a Centralized Multi-agent LLM System with Reinforcement Learning [53.57360296655208]
  Large language models (LLMs) exhibit complementary strengths across domains and come with varying inference costs.<n>Existing approaches rely on decentralized frameworks, which invoke multiple LLMs for every input and thus lead to substantial and uncontrolled inference costs.<n>We introduce a centralized multi-LLM framework, where a controller LLM selectively coordinates a pool of expert models in a cost-efficient and cost-controllable manner.
  arXiv  Detail & Related papers  (2025-11-04T17:35:17Z)
• FedSVD: Adaptive Orthogonalization for Private Federated Learning with LoRA [68.44043212834204]
  Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in learning (FL)<n>Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in learning (FL)
  arXiv  Detail & Related papers  (2025-05-19T07:32:56Z)
• Not All Rollouts are Useful: Down-Sampling Rollouts in LLM Reinforcement Learning [55.15106182268834]
  Reinforcement learning with verifiable rewards (RLVR) has emerged as the leading approach for enhancing reasoning capabilities in large language models.<n>It faces a fundamental compute and memory asymmetry: rollout generation is embarrassingly parallel and memory-light, whereas policy updates are communication-heavy and memory-intensive.<n>We introduce PODS (Policy Optimization with Down-Sampling), which decouples rollout generation from policy updates by training only on a strategically selected subset of rollouts.
  arXiv  Detail & Related papers  (2025-04-18T17:49:55Z)
• Online Apprenticeship Learning [58.45089581278177]
  In Apprenticeship Learning (AL), we are given a Markov Decision Process (MDP) without access to the cost function. The goal is to find a policy that matches the expert's performance on some predefined set of cost functions. We show that the OAL problem can be effectively solved by combining two mirror descent based no-regret algorithms.
  arXiv  Detail & Related papers  (2021-02-13T12:57:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.