# Token Budgets: An Empirical Catalog of 63 LLM-Agent Budget-Overrun Incidents, with an Affine-Typed Rust Mitigation as a Case Study arXiv: https://arxiv.org/abs/2606.04056 ยท HTML: https://mlsanity.com/paper/2606.04056/ ## Key facts - Cited by 6 papers in the map (data through 14 Oct 2026). - Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use. - Builds on 16 of its 89 references that are in the map. - First posted on arXiv 2 Jun 2026. ## Placed in - LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/) ## Builds on (most cited first, 16 of 16) - [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022) - [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023) - [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023) - [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016) - [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023) - [The Rise and Potential of Large Language Model Based Agents: A Survey](https://mlsanity.com/paper/2309.07864/) (2023) - [FrugalGPT: How to Use Large Language Models While Reducing Cost and Improving Performance](https://mlsanity.com/paper/2305.05176/) (2023) - [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017) - [Optimizing Instructions and Demonstrations for Multi-Stage Language Model Programs](https://mlsanity.com/paper/2406.11695/) (2024) - [Verus: Verifying Rust Programs using Linear Ghost Types (extended version)](https://mlsanity.com/paper/2303.05491/) (2023) - [Agent Contracts: A Formal Framework for Resource-Bounded Autonomous AI Systems](https://mlsanity.com/paper/2601.08815/) (2026) - [RustHorn: CHC-based Verification for Rust Programs (full version)](https://mlsanity.com/paper/2002.09002/) (2020) - [Linear Haskell: practical linearity in a higher-order polymorphic language](https://mlsanity.com/paper/1710.09756/) (2017) - [Proving Expected Sensitivity of Probabilistic Programs with Randomized Variable-Dependent Termination Time](https://mlsanity.com/paper/1902.04744/) (2019) - [Running on Fumes--Preventing Out-of-Gas Vulnerabilities in Ethereum Smart Contracts using Static Resource Analysis](https://mlsanity.com/paper/1811.10403/) (2018) - [Raising Expectations: Automating Expected Cost Analysis with Types](https://mlsanity.com/paper/2006.14010/) (2020) ## Built on by (most cited first, 6 of 6) - [Engineering Reliable Coding Agents: Evaluating and Operating the System Around the Model](https://mlsanity.com/paper/2608.13867/) (2026) - [Spawn Freely, Act Sparingly: Progressive Risk Vesting for Recursive LLM-Agent Trees](https://mlsanity.com/paper/2609.01035/) (2026) - [Persistent Billable State: Denial-of-Wallet Attacks and Defenses in Tool-Calling LLM Agents](https://mlsanity.com/paper/2609.28585/) (2026) - [Authorization for Self-Modifying AI Agent Populations: Conserving Authority across Replacement, Forking, and Rollback](https://mlsanity.com/paper/2610.00347/) (2026) - [Fault-Tolerant Budget Conservation in Distributed Multi-Agent Delegation](https://mlsanity.com/paper/2610.00349/) (2026) - [Pollard: Governed Semantic Execution Trees for Framework-Independent AI Agent Control and Replay](https://mlsanity.com/paper/2610.16145/) (2026) ## Abstract (arXiv) LLM-agent budget overruns are a documented production failure class: a single retry loop can spend thousands of dollars before an operator notices, and the in-process integrity properties that would prevent it (no aliasing, no double-spend, no use-after-delegation of a cost-bearing value) are enforced, if at all, by ad-hoc wrappers rather than by the type system. Our central contribution is empirical: a catalog of 63 confirmed production incidents from 21 orchestration frameworks (2023-2026), each backed by a quoted GitHub issue and, where reported, a dollar loss, organized into an eight-cluster failure taxonomy (inter-rater Cohen's kappa = 0.837, N = 113), plus 47 supplementary structural entries. As one mitigation evaluated against this taxonomy, we build token-budgets, an 1,180-line Rust crate (no unsafe) that operationalizes affine ownership so that cloning, double-spending, or using a budget after delegating it are compile errors rather than runtime hazards an operator must remember to avoid. The dollar cap is runtime arithmetic under an estimator assumption; the affine layer makes that arithmetic non-bypassable. On single-agent workloads a 4-line Python counter matches the crate at 0/30 overshoot, so the distinguishing value is non-bypassability under operator error in multi-agent delegation: the delegation-fanout race documented in 11 incidents is rejected by the borrow checker at compile time, while the same pattern under asyncio overshoots 30/30 and three disciplined alternatives overshoot 0/30. Across five runtimes, three providers, and a temperature-stratified live-API test (N = 160), the approach reports zero cap violations and zero false refusals, at operational parity with concurrent work. Static over-reservation is 4-6x (2.11x adaptive). Binary-level cap-soundness on the running binary is left open.