Towards Budget-Aware Agents: Can LLM Agents Know What They Will Spend?

RLxF @ ICML 2026 · OpenReview

TL;DR

This paper introduces budget awareness as a distinct capability for LLM agents, formalizing it through "progressive interval estimation"—the ability of an agent to predict, mid-execution, how much resource (tokens, time, or money) remains to complete a task. The authors find that being a "smart" agent doesn't make you a good accountant: task performance is largely decoupled from budget estimation, and models are systematically over-optimistic about their own efficiency.

What Problem Does This Paper Address?

As LLM agents move from simple chat interfaces to long-horizon autonomous workers (coding assistants, supply-chain managers, web navigators), they consume significant resources. Currently, we track these costs "post-hoc"—we see the bill after the agent finishes (or fails).

The gap is that agents lack self-awareness regarding their own resource consumption. An agent that doesn't know it’s about to blow its budget can't decide to abort a hopeless task, request more resources, or pivot to a cheaper strategy. Existing research usually treats token count as a secondary metric rather than a signal the agent should monitor internally.

Methods

The authors propose a new framework called Progressive Interval Estimation. Instead of asking for a single point estimate at the start of a task, they require the agent to provide a confidence-aware range (an interval) at every turn of the execution.

To evaluate this without the estimation process itself interfering with the task, they use a Rollout-Replay protocol:

  1. Rollout: An agent completes a task without any budget constraints. The full trajectory and costs are logged.
  2. Replay: The same agent is fed prefixes of that trajectory and asked: "Given this progress, how much more will you spend to finish? Or is it now impossible?"

The researchers decomposed budget awareness into three sub-capabilities:

  • Feasibility Prediction: Can the agent tell if it will succeed within the remaining budget?
  • Early Failure Detection: Can it flag a "doomed" trajectory before the budget is actually exhausted?
  • Interval Calibration: Is the predicted cost range accurate and tight?

They tested five frontier models (including GPT-5.2, Claude 4.7, and Gemini 3.1) and even trained a Qwen-7B model using Supervised Fine-Tuning (SFT) and Reinforcement Learning (RL) to see if this "accounting" skill is trainable.

Datasets

The study evaluates agents across four diverse environments:

  • Internal Budgets (Tokens):
    • Sokoban: A classic planning/puzzle task.
  • Search-R1: A multi-hop information retrieval task.
  • SWE-bench: Real-world GitHub issue resolution (coding).
  • External Budgets (Money, Time, Inventory):
    • Warehouse: A newly introduced supply-chain environment curated from real enterprise data. Agents must manage three coupled constraints: cumulative cost (USD), time (weeks), and warehouse occupancy.

Key Insights and Ideas

  • The Decoupling Effect: This is the most striking finding. Task success correlates only weakly ($r \approx 0.35$) with budget awareness. A model like Claude Opus might be the best at solving coding problems, but Claude Sonnet might be better at predicting how many tokens it will take to do so. Budget awareness is a "metacognitive" skill distinct from raw problem-solving.
  • Systematic Optimism: Models are "born optimists." Across all 20 model-environment pairs, models underestimated remaining costs far more often than they overestimated them. They tend to realize a task is "impossible" only in the final 20% of the execution—long after most of the budget has been wasted.
  • Calibration vs. Reasoning: The authors found that knowing if a task is finishable (feasibility) is a calibration problem—it can be fixed easily with SFT. However, providing a precise interval of cost is a reasoning problem that remains difficult even after specialized training.
  • Actionable Signals: Even though current models are flawed, their internal "hunches" about failure are already useful. Implementing a simple early-stop policy based on the agent's own "impossible" flags saved 28–64% of tokens on failed runs with only a tiny hit to the overall success rate.

Key Results

  • Training Gains: For the Qwen-7B model, SFT alone raised feasibility prediction accuracy from a dismal 25.5% to roughly 90%.
  • RL Fragility: Reinforcement Learning (using GRPO) improved interval coverage to 47%, but it required an SFT "warm-start." RL from scratch caused the model's estimation capabilities to collapse.
  • Model Rankings: No single model dominated. For example, on Search-R1, Opus had the highest success rate (75.8%), but Sonnet provided significantly better interval estimates (36.5% hit rate vs. 23.1% for Opus).

Limitations and Future Work

  • Offline vs. Online: The "Rollout-Replay" method is an offline evaluation. In the real world, agents need to estimate budget while thinking, which introduces a "cost of thinking" recursion that this paper explicitly avoids to keep the metrics clean.
  • Optimism Bias: While the paper identifies the bias, it doesn't fully solve it. Even trained models still skew toward underestimating costs.
  • Generalization: The training was performed primarily on Sokoban; whether "budget reasoning" learned in one domain transfers to others (e.g., from puzzles to coding) remains an open question.

The authors conclude that budget should be treated not just as a metric for accounting, but as a control signal that agents can—and should—use to manage themselves.

Summary updated

Abstract

Foundation-model agents are deployed with growing resource constraints like token, money, and time budgets, yet it remains unclear whether they know how much budget they will spend. We call this capability budget awareness and formalize it as progressive interval estimation: mid-execution, whether the agent can provide an interval on how much budget remains needed and whether the task is still finishable. We score this with a rollout-replay protocol that re-queries the same agent on every prefix of an unconstrained rollout, and decompose estimation into three sub-capabilities: feasibility prediction, early failure detection, and interval calibration. We evaluate five frontier models on four environments spanning internal budgets (token consumption on Sokoban, Search-R1, and SWE-bench) and external budgets (cost, time, and warehouse occupancy in a supply-chain environment curated from real enterprise data); we further train Qwen-7B budget estimators with SFT and RL on Sokoban, and deploy their predictions through a simple early-stop policy. Across these axes, we find budget awareness: (1) decouples from task performance, (2) fails in structured ways, and (3) is already actionable and trainable as a control signal that resource-limited agents currently lack.
BibTeX
@inproceedings{2026towards,
  title = {{Towards Budget-Aware Agents: Can LLM Agents Know What They Will Spend?}},
  booktitle = {RLxF @ ICML},
  year = {2026},
  url = {https://openreview.net/forum?id=aYzLDRQsgO},
}
Figure