💻 computer science

Token Budgets: An Empirical Catalog of 63 LLM-Agent Budget-Overrun Incidents, with an Affine-Typed Rust Mitigation as a Case Study

This paper presents an empirical catalog of 63 LLM-agent token budget overruns and introduces "token-budgets," a type-safe Rust crate that leverages affine ownership to enforce non-bypassable spending limits at compile time, effectively preventing delegation-related cost explosions that plague ad-hoc runtime solutions.

Original authors: Sajjad Khan

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sajjad Khan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Problem: The "Infinite Money Glitch" in AI

Imagine you hire a robot assistant to do some work for you. You give it a strict rule: "Spend no more than $10 on my credit card."

However, the robot gets confused. It gets stuck in a loop, trying to solve a problem over and over again. Because the robot doesn't have a built-in "stop button" that checks the price before it makes a call, it keeps spending. By the time you wake up the next morning, the robot hasn't just spent your $10; it has spent $10,000.

This paper calls this a "Budget Overrun." The authors found 63 real-world examples of this happening between 2023 and 2026 across many different AI frameworks. In some cases, users lost thousands of dollars because the software didn't stop the spending before it happened.

The Current Fixes: The "After-the-Fact" Alarm

Most companies currently try to fix this by putting up a "security guard" who watches the spending after the robot has already made the call.

The Analogy: Imagine you go to a store, buy 1,000 items, and then the cashier stops you at the door and says, "Whoa, that's over your limit!" You still have to pay for the items you already grabbed, or you have to run back to the shelf to put them all down.
The Paper's Point: These current fixes are too slow. They catch the mistake, but they don't prevent the damage.

The New Solution: The "Magic Wallet" (Token Budgets)

The authors built a new tool called Token Budgets (written in a programming language called Rust). Instead of a security guard watching the spending, they changed the wallet itself.

The Analogy:
Imagine you give the robot a physical wallet containing exactly $10 in cash.

No Copying: The wallet is made of a special material that cannot be photocopied. The robot cannot make 100 copies of the wallet to spend $1,000.
No Double-Spending: Once the robot takes a $1 bill out to buy something, that bill is gone. It cannot put the same bill back in its pocket and spend it again.
No Sharing: If the robot splits the wallet into two smaller wallets to give to two helpers, the original wallet disappears. The helpers can't go back to the original wallet to get more money.

In the world of computer code, this is called "Affine Ownership." It forces the computer to check the rules before the robot even leaves the house. If the robot tries to break the rules (like copying the wallet), the computer refuses to let the program run at all. It's like a bouncer at a club who checks your ID before you even enter; if you don't have it, you never get to the bar to order a drink.

What They Actually Proved

The paper makes three main claims, which they tested carefully:

The Catalog of Failures: They created a "Hall of Shame" listing 63 specific incidents where AI agents went on spending sprees. They also found 47 more cases where developers admitted, "We don't have a way to stop this yet." This proves the problem is real and happens often.
The "Magic Wallet" Works: They tested their new Rust tool against five other popular ways of managing AI costs.
- The Result: When they tried to trick the system into spending too much (by creating a race condition where two agents try to spend the same money at the same time), the other systems failed 100% of the time. The new "Magic Wallet" system failed 0 times.
- Why? Because the other systems rely on the programmer remembering to write a "lock" to prevent double-spending. If the programmer forgets, the money leaks. The new system forces the programmer to follow the rules, or the code won't even compile (it won't turn into a working program).
It's Not a Magic Bullet for Everything: The authors are very honest about the limits.
- It only works in Rust: This specific "Magic Wallet" only works if you are writing your software in the Rust programming language. It doesn't work for Python or JavaScript (though they made a Python version that acts like a normal security guard, not a magic wallet).
- It relies on the AI company: The system estimates how much a task will cost. If the AI company (like OpenAI or Anthropic) charges you more than they said they would, or hides some "thinking" costs, the system might still get confused. It trusts the bill it receives, but if the bill is wrong, the wallet might run dry.

The Bottom Line

This paper says: "AI agents are currently dangerous because they can accidentally drain your bank account. We found 63 examples of this. We built a new tool that uses strict computer rules to make it impossible for the code to accidentally copy or double-spend money. It works perfectly for preventing these specific types of mistakes, but it only works if you are using the Rust programming language and if the AI companies tell the truth about their prices."

In short: They didn't just build a better alarm system; they built a wallet that physically cannot be stolen or duplicated.

Technical Summary: Token Budgets

Problem Statement
LLM-agent budget overruns represent a documented production failure class where unbounded retry loops or delegation patterns accumulate thousands of dollars in costs before detection. Existing mitigations are predominantly runtime mechanisms (e.g., AgentGuard callbacks, LiteLLM proxy budgets) that track spend after an API call has been committed or rejected at the network layer. These approaches fail to prevent the "M-delegation-fanout" race condition, where concurrent sub-agents bypass a shared budget due to lack of atomicity or aliasing in the operator's code. Furthermore, many frameworks lack a first-class budget primitive entirely, leading to structural gaps where cost control is absent or implemented via ad-hoc wrappers.

Methodology
The paper employs a mixed-method approach combining empirical software engineering and systems implementation:

Empirical Catalog Construction: The authors constructed a catalog of 110 entries drawn from 21 LLM-agent sub-projects across 18 ecosystems (2023–2026). This includes 63 confirmed production incidents (user-reported overruns with dollar loss evidence) and 47 supplementary structural entries (maintainer-acknowledged gaps or feature requests). The catalog was validated via a two-human independent inter-rater reliability (IRR) study, achieving Cohen's $\kappa = 0.837$ on the four-class classification scheme.
Failure Taxonomy: The incidents were organized into eight exploratory architectural mechanism clusters, including M-retry-loop, M-cost-observability, M-delegation-fanout, and M-budget-primitive-missing.
Mitigation Design (Token Budgets): The authors implemented token-budgets, a 1,180-line Rust crate that operationalizes affine ownership for budget management. The core Budget type is non-cloneable and non-copyable. Key operations (spend, split, merge) consume the budget by value, enforcing via the Rust borrow checker that:
- A budget cannot be aliased.
- A budget cannot be double-spent (use-after-move).
- A budget cannot be used after being delegated (split).
- The dollar cap is enforced via runtime arithmetic (checked_sub) based on a provider-stratified estimator (e.g., byte-length for OpenAI, tool-loop aware for Anthropic).
Evaluation: The system was evaluated against five production runtimes (LangGraph, CrewAI, AutoGen, AgentGuard-style callbacks, LiteLLM) and concurrent work (Agent Contracts) across three providers. Experiments included:
- Compile-time Integrity: 9 trybuild tests verifying that racy patterns (cloning, double-spending) fail to compile.
- Forgetful-Operator Experiment: A comparison of a racy Python implementation (overshoots 30/30) against disciplined Python (locked), Rust affine, and Rust shared-mutex implementations.
- Live-API Sweeps: Temperature-stratified tests ( $T \in \{0.0, 0.3, 0.7, 1.0\}$ , $N=160$ ) and sub-floor cap tests to verify zero overshoot and zero false refusals.
- Estimator Soundness: Validation of the static and adaptive estimators against actual provider billing.

Key Contributions

Empirical Catalog: The first inter-rater-validated taxonomy of LLM-agent budget overruns, documenting 63 confirmed incidents and 47 structural gaps across 21 frameworks. This establishes the recurrence of the failure class, particularly the M-budget-primitive-missing pattern.
Affine Budget Discipline: A Rust implementation that shifts budget integrity from runtime discipline to compile-time enforcement. By treating the budget as an affine value, the system prevents aliasing and double-spending at the type level, ensuring that the "M-delegation-fanout" race condition is a compile error rather than a runtime hazard.
Operational Evaluation: A head-to-head demonstration that while runtime alternatives (properly locked counters) can achieve the same cap-respecting outcome, the affine discipline uniquely guarantees non-bypassability under operator error in multi-agent delegation. The evaluation shows the Rust implementation achieves 0/30 overshoots where racy baselines achieve 30/30.

Results

Integrity: The trybuild suite confirmed that all three classes of cap-circumvention (aliasing, double-spending, use-after-split) result in compile-time errors with specific rustc diagnostics.
Cap-Respecting Behavior: In live-API tests ( $N=160$ ), the Rust implementation recorded zero cap violations and zero false refusals. In the "Forgetful-Operator" experiment, the racy Python baseline overshot the cap 30/30 times, while the Rust affine implementation overshot 0/30 times.
Comparison with Runtime Alternatives: When operators correctly implement locking in Python or Rust, the cap-respecting outcome is identical to the affine approach. The distinguishing value of the affine type is that it makes the incorrect (racy) pattern impossible to compile, removing the burden of concurrency discipline from the operator.
Estimator Performance: The default static byte-length estimator reserves 4–6× actual cost. The AdaptiveEstimator tightens this to a median of 2.11× with negligible latency, while tokenizer-direct estimation achieves ~1.0× at the cost of ~1 second per-spend latency.
Deployment: A single production deployment on the Rig framework demonstrated the approach enforcing a hard session cap across concurrent sub-agents with zero overshoot.

Claims and Significance
The paper positions its contribution modestly as an empirical software engineering study with a specific systems case study:

Scope of Claim: The authors explicitly state they do not claim a formal proof of binary-level cap soundness (Conjecture 1 remains open). The integrity guarantees are source-level (enforced by the borrow checker on typed code). The dollar cap is a runtime arithmetic property conditional on estimator assumptions (A1) and provider truthfulness (A7).
Primary Value: The significance lies in addressing the M-budget-primitive-missing failure mode structurally. For frameworks lacking a budget primitive, a Rust re-implementation using token-budgets cannot silently regress or expose the budget only via callbacks.
Limitations: The approach is specific to Rust agent deployments (a minority of the current ecosystem). It does not solve provider-side billing misreporting, hidden reasoning tokens in reasoning models (OpenAI o-series, Anthropic extended-thinking), or multi-tenant cross-process budgeting without a distributed service.
Conclusion: The paper concludes that while runtime alternatives can achieve the same operational outcome if written correctly, the affine discipline provides a "non-bypassable" guarantee against operator error in multi-agent delegation, making it the preferred primitive for new Rust agent deployments requiring cumulative session caps. The catalog serves as evidence that these failure modes recur across the ecosystem regardless of implementation language.