Source-linked AI summary
Token Budgets: An Empirical Catalog of 63 LLM-Agent Budget-Overrun Incidents, with an Affine-Typed Rust Mitigation as a Case Study
Sajjad Khan
TL;DR
The paper catalogs recurring LLM-agent budget-overrun failures and evaluates an affine Rust budget as a mitigation for concurrency-related integrity hazards. The approach reports zero cap violations and zero false refusals in a temperature-stratified live-API test, while its main distinction is compile-time non-bypassability rather than better outcomes than correctly written runtime monitors.
Problem
LLM-agent budget overruns recur in production, while concurrency-related integrity properties such as preventing double-spending are not reliably enforced by existing type systems.
Method
The paper combines a catalog of 63 confirmed incidents and 47 supplementary structural entries with an affine Rust budget that makes cloning, double-spending, and post-delegation use compile errors.
Results
Zero cap violations and zero false refusals were reported in a temperature-stratified live-API test with N = 160, while the approach matched correctly written runtime monitors at 0 overshoot.
Takeaways & Limitations
The affine layer's supported value is non-bypassability under operator error in multi-agent delegation, rather than a stronger cost guarantee or better outcome than disciplined runtime monitoring.
Takeaways & Limitations
The experiment is a constructed reproduction at one parameter setting, and the catalog establishes recurrence of the structural class rather than deployment prevalence or an incidence rate.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
LLM-agent budget overruns recur across production systems, while existing safeguards operate at runtime and can detect overspending only after calls commit. The paper catalogs these failures and evaluates affine Rust ownership as a narrowly targeted mitigation for non-bypassable budget integrity.
- Empirical motivation: 63 confirmed incidents across 21 sub-projects and 18 ecosystems are organized into eight mechanism clusters, alongside 47 supplementary structural entries.The catalog covers 2023–2026 and includes quoted maintainer or user evidence where available.
- Empirical motivation: Existing safeguards—including alerts, circuit breakers, and network payment enforcement—remain runtime mechanisms that detect or reject spending only after requests are initiated.These mechanisms provide second-line defenses but do not prevent the API call from committing before detection.
- Affine mitigation: The type-level contribution targets concurrency integrity rather than a stronger cost guarantee: the borrow checker prevents aliasing, double-spend, and use-after-split in typed source code.Binary-level cap-soundness remains unestablished, and the runtime cap depends on estimator assumption A1.
- Affine mitigation: The Rust Budget API applies affine ownership so cloning, double-spending, and use-after-delegation become compile errors, while dollar-cap arithmetic remains runtime and estimator-dependent.The crate uses no unsafe code, and its core affine path avoids Arc<Mutex<_>>.
- Scope: The approach is positioned for new Rust agents requiring multi-provider cumulative-session caps, not as a universal mechanism across deployment contexts.The paper explicitly presents the affine discipline as one mechanism among several and notes that existing Python deployments require re-implementation.
- Scope: Reasoning models fall outside the stated estimator guarantee because hidden reasoning tokens are not bounded by max_output_tokens and require provider-side controls or deployment-specific calibration.Initial reasoning-token calibrations may be off by an order of magnitude before tuning.
2 MOTIVATION: A FAILURE CATALOG
The catalog uses a failure-confirming public-GitHub sampling frame to document recurring budget-primitive failures across LLM-agent projects, while distinguishing descriptive corpus composition from incidence claims. Its exploratory taxonomy and independent replication provide evidence of recurring mechanisms, but sampling and coding limitations constrain interpretation.
- 2.1 Methodology: Primary-catalog coding achieved Cohen’s κ = 0.837 on N = 113, while confirmed-subset agreement reached κ = 0.943 on n = 79.The feature-request/bug boundary remains the weakest coding seam, with κfr = 0.727.
- 2.1 Methodology: The sample is biased toward popular open-source frameworks and public GitHub artifacts, while closed-source platforms and internal-only incidents are under-represented.Candidate sourcing also shifted from LLM-assisted keyword expansion to direct human keyword skimming during construction.
- 2.3 Baseline replication: The independent cohort reproduced the primary mechanism clusters, and the keyword filter caught 61/63 qualifying rows (97% catch rate).These results support recurrence and sustained demand for budget-discipline primitives, not an incidence estimate.
- 2.4 Catalog composition: 63 confirmed production failures comprise 57.3% of the 110-row corpus, alongside 28 maintainer-acknowledged gaps and 14 feature requests.The confirmed-failure count is convention-sensitive relative to feature requests; strong claims rely on the union of case types.
- 2.4 Catalog composition: The catalog documents a budget-primitive-missing condition across 21 sub-projects, not 110 distinct paying-customer overrun incidents.The corpus does not support prevalence claims such as the percentage of deployments that overrun.
- 2.5 Catalog: Eight architectural clusters organize the 110 retained rows, led by M-retry-loop (27 rows / 12 frameworks) and M-cost-observability (22 / 9).Other clusters include context amplification, storage amplification, missing budget primitives, delegation fanout, silently dropped provider options, and multimodal cost amplification.
- 2.5 Catalog: The eight-cluster partition is exploratory: blind second-rater agreement was Cohen’s κ = 0.44, with stronger agreement for cost-observability and multimodal mechanisms.The taxonomy structures discussion of failure modes but is not treated as validated or as grounds for exact per-cluster claims.
- 2.6 Patterns: Reactive fixes can be rapid, but no catalog case shows an overrun prevented before the user paid for the request.Examples include same-day fixes and a fastest resolution one day after filing.
3 THE MITIGATION: AN AFFINE BU D G E T (CASE STUDY)
The mitigation separates a runtime dollar cap from an affine type layer that makes budget bookkeeping non-bypassable in typed Rust source. It targets concurrency and delegation errors while preserving explicit estimator and provider assumptions.
- Scope of the mitigation: The runtime cap bounds in-program spend across all eight incident clusters, while affine ownership makes cap bookkeeping non-bypassable in typed source.The type system structurally fixes the missing-budget-primitive cluster and prevents aliasing, double-spending, and use-after-delegation mistakes across the remaining clusters.
- Scope of the mitigation: The type-level claim targets correctly intended runtime checks that race or are bypassed under concurrency, rather than replacing runtime cost arithmetic.The M-delegation-fanout shape is the motivating case: the borrow checker rejects the racy pattern at compile time.
- Affine Budget design: Budget is a non-Clone, non-Copy Rust value whose self-consuming operations enforce ownership during spending, splitting, merging, and delegation.Budget::new is gated by BudgetMint; spend returns a remainder and receipt, split returns child budgets, and merge consumes both arguments.
- Reservation and cap bound: Before each API call, a provider-stratified estimator reserves an upper bound through checked_sub and refuses calls that would exceed the cap.The conditional bound depends on estimator soundness, provider-respected output caps, truthful charge reporting, rate stability, and related assumptions.
- Reservation and cap bound: Successful calls reconcile reservations against provider-reported charges and refund over-reservation, while failed calls forfeit their receipts.The reconciliation path depends on the charge-truthfulness assumption A7.
- Limitations: Binary-level cap soundness remains open because the paper establishes integrity only for well-typed Rust source, not compiled execution.The evaluation observes zero cap violations, but this is not presented as a proof that compilation and scheduling preserve the source-level properties.
4 EVALUATION
The evaluation tests compile-time integrity, cap-respecting behavior, and the affine discipline’s distinguishing value under multi-agent operator error. Across forgetful-operator trials, runtime alternatives can be safe when correctly implemented, while the Rust approach mechanically rejects the racy pattern.
- Statistical conventions: The evaluation’s empirical interpretation accounts for near-deterministic T = 0 replicas by emphasizing cross-temperature independent runs and conservative per-cell reading.The statistical conventions distinguish per-run Wilson intervals from configuration-level effective sample size.
- Multi-runtime evaluation: Across provider comparisons, Rust refuses cap-violating calls before the network request and records maximum overshoot of 0 uc.A correctly configured runtime-cost layer shares the cap-respecting outcome but checks after calls return.
- What the type system adds: Runtime lock discipline reaches 0/30, but the affine conditions achieve the same outcome without requiring operators to write that discipline correctly.The racy pattern is rejected by the borrow checker, making non-bypassability the distinguishing property rather than cap-respecting outcome alone.
- Compile-time integrity: Three Rust translations of the racy delegation pattern fail to compile with expected rustc diagnostics.The tests cover shared-budget reuse, cloning, and parent reuse after splitting.
- Cap regimes: The approach admits all three children when the cap fits the allocation and refuses pre-flight when no admissible allocation fits.Conditions C and D both remain cap-respecting, with D using a cap sized for three children.
5 RELATED WORK
The paper positions Token Budgets as a compile-time affine-integrity layer complementary to runtime and transport controls, transferring established resource-typing ideas to LLM dollar cost.
- Comparison with Agent Contracts: The approach differs from Agent Contracts by enforcing budget non-cloning, non-double-spending, and non-reuse after delegation through Rust’s type system.Agent Contracts provides runtime inter-agent contract monitoring; the two can be deployed together.
- Novelty boundary: The runtime pre-call reservation pattern is established in tokencap, LiteLLM, and Semantic Kernel; the contribution is its affine compile-time integrity layer for LLM cost.The paper explicitly separates novelty in the type-system transfer from novelty in runtime estimation.
- Empirical distinction: The forgetful-operator experiment reports 30/30 overshoot for a racy Python delegation pattern versus 0/30 for three disciplined alternatives, while Rust rejects the race at compile time.This isolates compile-time integrity from the cap-respecting outcome achievable through correct runtime discipline.
- Adjacent literatures: The paper situates the approach among substructural typing, capability authority, gas metering, cloud governance, and transport-level payment controls.These literatures provide related resource, authority, reservation, and quota mechanisms rather than an identical LLM-cost solution.
- Layered cost enforcement: Token Budgets complements runtime and transport mechanisms by enforcing in-process integrity before external resources are consumed.Runtime guards and network wallets remain useful for different failure modes.
6 DISCUSSION AND LIMITATIONS
The discussion bounds the approach to specific trust, language, workload, deployment, and empirical settings, while showing that provider under-reporting can invalidate client-side cap guarantees.
- Language scope: Python-only deployments require runtime mitigations or a production-grade static-analysis plugin because compile-time enforcement depends on Rust affine ownership.The current Mypy plugin is identified as a proof of concept.
- Catalog scope: The catalog establishes recurrence in sampled projects, not ecosystem prevalence, because denominator-based telemetry was unavailable.The paper identifies prevalence measurement as a separate open empirical need.
- Taxonomy validity: Taxonomy reliability is uneven: headline agreement is κ = 0.44 across 110 rows, with overlapping boundaries among several mechanisms.Cost-observability and multimodal-cost-amplification are more reliable than the remaining category boundaries.
- Provider accounting: Provider under-reporting causes 666/1,000 sessions to overshoot at k = 2 and 1,000/1,000 at k = 5 and k = 10.At k = 1, all 1,000 sessions respect the cap; reconciliation every three calls reduces but does not eliminate overshoot at k = 5.
- Workload scope: The empirical workload evaluation is limited to three retry-loop patterns and does not establish behavior for RAG, tree-of-thoughts, multimodal, or long-context workloads.The mechanism is described as workload-independent in principle, but the empirical claim remains narrower.
- Deployment scope: The approach is single-process and requires distributed reservation services for multi-tenant deployments spanning replicas.The proposed extension involves authoritative per-session reservations and typed RPC-acquired leases.
- Model scope: Reasoning-model hidden tokens fall outside Proposition 1 because providers bill tokens not bounded by max_output_tokens.The proposed response is defense in depth using provider-side reasoning controls.
7 FUTURE WORK
Future work targets formal refinement, tighter estimation, distributed deployment, operator evidence, and a different programming-languages framing.
- Formal assurance: Binary-level refinement remains an unattempted proof obligation: future work would establish that the compiled binary preserves source-level properties.The paper does not rely on this stronger claim.
- Estimation: A DP-composition-style estimator could potentially reduce AdaptiveEstimator over-reservation toward tokenizer-direct performance without per-spend latency.The paper treats adapting DP mathematics to LLM cost as research work rather than a parameter adjustment.
- Distributed deployment: Production multi-tenant reservation requires implementation and evaluation of replicated leases, partial-failure semantics, and hot-key partitioning.The current work only sketches a Saga-style reservation service.
- Operational evidence: Operator interviews or deployment data are needed to test whether real practitioners prefer the capital-efficiency trade-off of affine budgeting.The current decision matrix presents this trade-off parametrically.
- Research framing: A programming-languages-centered revision would foreground the affine type system and binary-level refinement rather than the present empirical-software-engineering framing.The paper treats that framing as a distinct future paper, not an internal open question.
8 CONCLUSION
The paper catalogs recurring LLM-agent budget overruns and evaluates affine Rust ownership as a targeted mitigation for in-process integrity failures.
- Empirical contribution: 63 confirmed incidents and 47 supplementary entries are organized into eight architectural mechanism clusters, with the type-level discipline most directly addressing M-budget-primitive-missing.The other seven clusters primarily benefit from runtime cap arithmetic conditional on estimator soundness.
- Mitigation: The affine API makes cloning, double-spending, and use after delegation compile-time errors within the Rust trust boundary.Runtime checked subtraction separately enforces the dollar cap.
- Interpretation: The head-to-head comparison reports that runtime-monitored alternatives can reach the same cap-respecting outcome, making the layers complementary rather than competing.The distinction is the integrity layer supporting refusal, not the cap-respecting result alone.
- Scope: The paper presents the crate as one mitigation for new Rust agents, while leaving cap-respecting behavior of the running Tokio binary open.Its formal and empirical scope does not extend to a binary-level guarantee.
DATA AVAILABILITY
The paper provides a complete replication package across six repositories and identifies aggregate-budget primitives as a type-level design target in the catalog evidence.
- The replication package spans six repositories, including the main library, catalog data, formal mechanisations, inter-rater materials, and experimental harnesses.
- M-budget-primitive-missing covers 12 cases across 6 frameworks where first-class declarative aggregate-budget primitives are absent or broken.
A.1 Type-system specification
The affine Budget type uses owned, non-copyable values and consuming operations to reject duplication, double-spending, and post-delegation use at compile time. Rust ownership also supports safe asynchronous delegation without synchronization primitives, while cap-respecting accounting still depends on a conservative estimator.
- Budget representation: Budget represents a finite quota measured in integer unit-cost values, with 1 uc = 10^-5 USD, and is non-Clone, non-Copy, with value-consuming methods.A 540 uc cap corresponds to $0.0054 of provider spend; the source names the field micro_cents.
- Budget representation: The API exposes constructors, availability queries, spending, splitting, merging, and consumption through owned Budget values.
- Compile-time properties: Three compile-time properties reject cloning, double-spending, and use-after-split through Rust errors E0599 and E0382.Cloning lacks a clone method; consuming spend or split moves the original binding, preventing later reuse.
- Scope of guarantees: Rust’s prohibition on returning references to local Budgets is an inherited borrow-checker rule, not a property specific to the affine design.
- Scope of guarantees: Cap-respecting accounting additionally requires a conservative cost estimator, because the affine properties constrain resource ownership and accounting integrity rather than estimator correctness.
- Delegation: The delegation example splits a parent budget, moves the child into tokio::spawn, runs parent work concurrently, and merges the worker’s unspent remainder.The borrow checker accepts the ownership transfers and rejects out-of-protocol use; errors propagate through Result and ?.
- Affine versus linear ownership: The affine discipline permits discarded resources on error paths, unlike a linear discipline that would require every Budget value to be consumed exactly once.
APPENDIX B SPECIFICATION CROSS-CHECKS (SUMMARY)
The specification is cross-checked with formal and concurrency tools, but these checks do not constitute a binary-level proof and do not compose multiplicatively.
- TLA+, TLC, Verus, randomized stress testing, and bounded Loom model-checking cross-check the abstract specification and exercise concurrency.
- Binary-level cap soundness remains unproved, and the tool results are not evidence that assurance composes multiplicatively across methods.
APPENDIX C PROOF OF PROPOSITION 1
The proof establishes the cap bound by combining unique ownership, non-increasing ledger state, exact reservation deductions, and conservative estimator assumptions.
- Proof scope: The appendix characterizes Proposition 1 as integer bookkeeping under stated assumptions rather than a deep system property.
- Ledger bound: The proof derives ∑i∈S ri = B0 − L(σfinal) ≤ B0 from unique ownership, non-increasing ledger state, and checked arithmetic.
- Estimator bound: The inequality ∑i∈S ci ≤ ∑i∈S ri follows from pointwise conservative input and output-token reservation assumptions.Input UTF-8 length and the max-output-token bound support conservative reservations at the provider’s per-token rates.
- Estimator bound: Matching operator-supplied rates to provider charges preserves the reservation relationship, while refund assumptions maintain ledger conservation after confirmation.
RESULTS
The appendix compares structural and cost-aware budget mitigations using a deterministic mock model and three live providers, documenting how each runtime is instantiated for the head-to-head.
- Appendix scope: The appendix provides the full setup, results table, mechanism analysis, and reproducibility notes for the head-to-head summarized in §4.2.
- Experimental setup: The comparison includes LangGraph, CrewAI, and AutoGen structural counters, plus runtime-cost and Rust budget mechanisms.Structural parameters use commonly cited defaults for budget-mitigation discussion, while the harness tests a deterministic mock chat model and three live providers.
- Experimental setup: The harness fixes the cap at B0 = 540uc (≈$0.0054) and per-step token-count growth at g = 60.The setup evaluates OpenAI gpt-4o-mini, Anthropic claude-haiku-4-5, and Groq llama-3.3-70b-versatile.
D.0.2 Results
Table 8 reports mean spend, cap percentage, and outcome codes across N = 10 cohorts, with mock-model coverage limited because CrewAI and AutoGen require real providers.
- Table 8 results: N = 10 cohorts are averaged for each runtime-provider cell in Table 8.The table reports mean spend in micro-cents and percentage of the configured cap.
- Table 8 results: CrewAI and AutoGen are omitted from the Mock column because they require a real provider.Their wrappers record an explicit skip outcome rather than running against a stub LLM.
D.0.3 Mechanism interpretation
The mechanism comparison separates estimator under-reservation and model reliability from protection behavior, with compile-time and pre-call runtime checks avoiding the post-hoc overshoot pattern.
- Mechanism interpretation: 168% on Anthropic and 153% on Groq show the Python simulator’s coarse estimator under-reserving on tool-augmented prompts.The Rust implementation uses the full UTF-8-serialized request body and refuses every cap-violating call before the network.
- Mechanism interpretation: Structural counters bound call count rather than dollars, while runtime-cost guards check after calls and can admit one overshooting call.Token Budgets lifts the check before the call, combining type-system rejection with a runtime refusal before spending.
- Mechanism interpretation: 0/10 CrewAI-on-Groq runs completed because malformed Llama-3.3-70B tool-call JSON exhausted CrewAI’s internal retry loop before max_iter triggered.This model-level reliability issue is distinct from the structural-counter mechanism discussed in the comparison.
D.0.5 Threats to validity and reproducibility
The validity discussion distinguishes the cap-respecting Rust result from the Python simulation, documents model-specific Groq failures, and reports the reproducibility artifact and table design.
- Threats to validity and reproducibility: The cap-respecting claim rests on the Rust implementation, while the Python simulator is included only for harness homogeneity despite 168%/153% under-reservation.The Python simulator’s coarse estimator violates assumption A1 on tool-augmented prompts.
- Threats to validity and reproducibility: 1/10 LangGraph and 10/10 CrewAI errors on Groq reflect Llama-3.3-70B tool-call reliability rather than the budget mechanism alone.A more reliable Groq model would remove this confound, according to the passage.
- Threats to validity and reproducibility: The artifact includes harnesses, per-cell CSVs, and the driver script, with total live-sweep cost ∼$0.18.
- Threats to validity and reproducibility: Table 8 uses bootstrap 95% CIs from 104 resamples, and most cells have <5 uc CI width at temperature = 0.The CrewAI-Anthropic cell is the principal exception.