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

AI agents are increasingly capable of complex, multi-step reasoning. However, they possess a dangerous tendency to enter runaway execution loops. A single poorly constrained retry loop or a recursive tool-use cycle can accumulate thousands of dollars in API costs. This can happen before a human operator even realizes the system has gone off the rails.

Currently, most developers manage this risk using runtime "circuit breakers." These are software wrappers that monitor spending and kill a process once a threshold is hit. However, these are often reactive. The money is often already spent by the time the breaker trips. More importantly, multi-agent systems create complexity. In these systems, a "parent" agent delegates tasks to several "child" agents. Coordinating these budgets leads to subtle concurrency bugs (errors occurring due to unpredictable timing in parallel execution). If two agents check the remaining budget simultaneously, they might both see enough funds to proceed. They can then collectively "double-spend" the remaining quota. This leads to a budget overshoot.

This paper reframes the problem from mere monitoring to in-process integrity. The authors argue that we should not rely on operators to implement perfect locking logic in Python. Instead, we should use a type system. This makes budget mismanagement a compile-time error (an error caught during the translation of code to a machine-readable format).

The fragility of runtime monitors

The authors establish the scale of the problem through an empirical catalog. They document 63 confirmed production budget-overrun incidents. These incidents come from 21 orchestration frameworks. The sample ranges from the LangChain ecosystem to specialized IDE agents. These are not theoretical edge cases. Many involve documented dollar losses and specific, reproducible failure mechanisms.

The paper categorizes these failures into eight clusters. Two are particularly salient for engineers building complex systems. The first is the "M-budget-primitive-missing" pattern. This occurs when frameworks lack a first-class way to represent and cap an aggregate budget. The second is the "M-delegation-fanout" race. In this scenario, an agent delegates work to multiple sub-agents. The lack of rigorous synchronization allows multiple workers to "claim" the same remaining budget slice at the same time.

Current mitigations exist at the software or transport layers. Middleware like LiteLLM or AgentGuard can track spend. However, as demonstrates, these are fundamentally post-hoc (occurring after the event).

They observe that a call has been made and then react. While they can stop the next call, they cannot prevent the current runaway call from committing its cost. Furthermore, structural counters are poor proxies for actual cost. These are limits on things like the number of "turns" an agent can take. As seen in, structural limits can overshoot the actual dollar cap by up to 1395%. This depends heavily on the verbosity of the model.

Enforcing integrity via affine ownership

To solve the coordination problem, the authors propose token-budgets. This is a Rust crate that leverages affine types to manage budget capabilities. In type theory, an affine type is a resource that can be used at most once. Unlike standard variables that can be copied indefinitely, an affine value is "consumed" when passed to a function.

The mechanism works through four primary operations on a Budget type: 1. Minting: Creating a new budget via a capability-gated constructor (Budget::new). 2. Spending: Consuming the current budget to perform a task and receiving a new, reduced budget in return (budget.spend(uc)). 3. Splitting: Taking a parent budget and dividing it into two distinct child budgets (budget.split(left, right)). 4. Merging: Combining two budgets back into one (Budget::merge(a, b)).

The core innovation is the "non-bypassability" provided by the Rust borrow checker. This is the tool that manages memory and resource ownership. Because the Budget type is non-copyable and non-cloneable, it is physically impossible in the typed source code to "double-spend" a budget. It is also impossible to use a budget after it has been split and delegated. If a developer tries to use a budget variable after it has been moved into a child thread, the compiler will reject the program. The authors distinguish this from "linear" types. Linear types must be used exactly once. Affine types are safer for budgets because a dropped (unused) budget only results in under-spending. This is inherently cap-safe.

Deterministic protection against operator error

The authors evaluate this approach against traditional Python-based runtime counters. Their most striking result comes from the "Forgetful-Operator" experiment. This was designed to isolate whether the type system provides value beyond what a "correct" programmer could achieve with locks.

In this experiment, the authors compared a racy Python implementation (no locks) against several disciplined alternatives. These included a correctly locked Python counter and the Rust affine implementation. As shown in, the racy implementation overshot the cap in 30 out of 30 trials. Disciplined alternatives also achieved 0/30 overshoots. However, they relied entirely on the operator implementing the locking logic perfectly.

The Rust affine approach stands apart. It transforms this requirement into a structural guarantee. The racy pattern simply fails to compile. This is a "deterministic mechanism split." The affine discipline does not necessarily change the mathematical outcome of a single-agent run. Instead, it ensures the outcome is robust against concurrency errors in multi-agent delegation.

Regarding performance, the authors report negligible per-operation overhead. It was measured at approximately 1.15 ns per operation. For the budget itself, they tested various estimation strategies. A static byte-length estimator results in a 4–6× over-reservation. This means you reserve much more than you spend to ensure safety. An AdaptiveEstimator tightens this to a 2.11× median over-reservation.

Unresolved obligations and residual risks

The paper is honest about the boundaries of its proof. Several "residual exposures" remain that the type system cannot touch.

First, the authors do not provide a formal proof of "binary-level cap-soundness." This refers to the behavior of the compiled machine code. While the source code is guaranteed to be well-behaved, they leave open "Conjecture 1." This conjecture suggests that compiler miscompilations or scheduler behaviors could theoretically allow a violation.

Second, the system is conditional on the honesty of the provider. The "Proposition 1" cap-respecting bound relies on Assumption A7. This assumes the provider's reported usage is truthful. The authors include a fault-injection study. It shows that if a provider under-reports usage by a factor of 2, the overshoot rate jumps to 66.6%. If the provider under-reports by a factor of 5, every single session overshoots. The type system ensures you do not accidentally spend more than intended. It cannot protect you from a Byzantine (malicious or unreliable) provider.

Finally, the approach struggles with new reasoning models. Models like OpenAI's o-series bill for "hidden" reasoning tokens. These are not captured by standard max_output_tokens constraints. For these models, the authors suggest using token-budgets as a "defense-in-depth" layer. It should sit behind provider-side controls rather than acting as a primary cap.

The verdict: A specialized tool for high-stakes orchestration

Is this a universal solution for LLM cost management? No. If you are running a simple, single-agent script, a basic runtime counter is sufficient. It carries less architectural overhead.

However, if you are building a professional-grade, multi-agent orchestration system in Rust, this approach is highly recommended. The paper demonstrates that the primary danger in complex workflows is not just the "math" of the budget. It is the "bookkeeping" of the budget across concurrent tasks. By moving this responsibility from the developer's memory to the compiler's logic, the token-budgets crate eliminates a class of concurrency-driven financial runaways.

For practitioners, the takeaway is clear. Use the Rust affine discipline for the internal integrity of your agentic logic. Continue to rely on provider-side controls and periodic billing reconciliation to handle external risks. These include dishonest reporting and hidden reasoning tokens. The full artifact is available at https://github.com/sajjadanwar0/token-budgets.