Fault-Tolerant Budget Conservation in Distributed Multi-Agent Delegation

Genliang Zhu; Chu Wang

cs.AISep 29, 2026

Fault-Tolerant Budget Conservation in Distributed Multi-Agent Delegation

Authors: Genliang Zhu, Chu Wang

Organizations: Accentrust, Vancouver, Canada · Georgia Institute of Technology, Atlanta, Georgia, USA · University of Illinois Urbana-Champaign, Urbana, Illinois, USA

Abstract

Resource limits are becoming an authorization boundary for AI agents that delegate work across concurrent and failure-prone workers. Parent-child allocation constraints, affine objects, and distributed escrow do not by themselves prevent overspend when replies are lost, effects complete after timeout, messages repeat, branches partition, or DAG joins alias one lineage. We formalize fault-tolerant budget conservation for distributed multi-agent delegation. Budgets are quantized resource vectors represented by exclusive escrow credits that move through a delegation DAG. Before dispatch, a branch converts credit into an operation reservation bound to lineage, epoch, normalized effect, maximum charge, receiver, and idempotency key. It persists a signed dispatch permit with quarantine; the gateway verifies that permit before first acceptance. Uncertain effects remain charged until authenticated settlement, a fenced authoritative no-effect proof, or permanent retirement. We prove ownership partition, ledger and effect conservation, descendant non-amplification, at-most-once settlement, late-completion safety, and partition confinement under explicit mediation, durability, authentication, normalization, and gateway assumptions. An indistinguishability result shows that partition-local availability requires exclusive preallocation. Bounded TLA+ checking, an independent JavaScript explorer, and crash-injected two-process SQLite experiments exercise the declared scope and detect timeout-refund and historical-certificate-validation mutants. The mechanism preserves the issued budget bound across the evaluated crash, retry, duplicate, partition, join, and late-completion schedules.

Figures & tables

Panel of Figure 1 — Figure 1. Parent/child allocation conservation does not prevent a timeout-refund/late-completion double spend. The safe trace keeps the reservation charged while the external outcome is indeterminate. Color is redundant with labels and arrow meaning. Two horizontal traces compare unsafe and safe handling of a lost effect response. The unsafe red trace refunds on timeout, lets another worker spend, and later observes the first effect, exceeding the root budget. The safe green and amber trace keeps the right reserved and reconciles an authenticated receipt or no-effect proof before committing or returning it.

Work	Consumable vector	Recursive / DAG delegation	Crash + partition	External-effect settlement	Primary contribution	Boundary relative to this paper
Agent Contracts	Yes	Recursive hierarchy	No fault semantics evaluated	Between-action monitor	Resource-bounded contract + allocation law	No duplicate/late-effect/fencing model
Token Budgets	Cost scalar/object	Fan-out ownership	In-process focus	Estimator-based cap	Incident catalog + affine Rust case study	No durable cross-protocol recovery
CapLease	Consumable authorization state	Delegation	Crash/retry recovery	Idempotent receiver contract	Durable authorization-state protocol	No partitioned vector-credit DAG join/effect-coverage theorem
EpochX	Task credits / bounties	Recursive delegation	No reported crash/partition proof	Lock + acceptance settlement	Agent marketplace and asset economy	No prefix ownership/effect-uncertainty invariant
AIP / AAT	Reusable scopes	Signed chains	Offline verification	Invocation + completion binding	Identity and monotone scope attenuation	No exclusive consumable ownership
MPAC	Not central	Multi-principal graph	Optimistic conflicts	Operation state	General agent coordination	No resource invariant

Table 1. Closest work is complementary. The contribution is not any individual primitive, but a fault-aware composition that keeps exclusive delegated rights and external-effect obligations coupled.

Panel of Figure 2 — Figure 2. Reference architecture and declared trust boundary. The untrusted agent may propose and retry; only the trusted branch store can move budget state. Protected external effects pass through a gateway whose authenticated outcome drives idempotent settlement. The independent verifier is a read-only evidence consumer outside the safety TCB. A three-tier architecture. A root issuer sends a grant and budget to a delegation controller and branch store beside an untrusted agent. Reserved dispatch flows to an effect gateway and external receiver. A terminal-evidence authority and reconciler feed authoritative outcomes back to the branch store. An independent verifier outside the boundary receives the diagrammed read-only evidence export and verifies trace/conservation records. A dashed boundary identifies only the trusted enforcement components.

Fault or attack	Naive failure	Required mechanism	Safe consequence
Concurrent fan-out	Two children copy one remainder	Exclusive atomic split with stable operation ID	Inputs consumed once; duplicate is a stutter
Multi-parent join	Shared ancestor counted twice	Disjoint lineage test and atomic input consumption	Alias rejected; distinct inputs may merge
Duplicate dispatch	Effect executes twice	Canonical effect key at fenced gateway	Replay returns same outcome
Response loss	Timeout interpreted as failure	Durable obligation and indeterminate state	Credit stays reserved
Crash after effect	Ledger misses consumption	Authenticated receipt query and idempotent settlement	Recovery moves reservation once
Stale worker	Old owner spends reclaimed credit	Monotone epoch and gateway fence	Old generation rejected

Table 2. Failure semantics. Safety may reduce availability or strand budget; the protocol reports that cost rather than hiding it as successful execution.

Reason	Meaning	Required response
INSUFFICIENT_LOCAL_ESCROW	Branch lacks exclusive rights	Coordinate transfer or refuse; never read a stale global total
LINEAGE_ALIAS	Join inputs overlap	Reject and audit
STALE_CREDIT_EPOCH	Message targets an old generation	Return prior outcome or reject; do not execute
OPERATION_BINDING_MISMATCH	Replay changed effect/vector/receiver	Reject as conflicting replay
TERMINAL_EVIDENCE_BINDING_MISMATCH	Success receipt or no-effect certificate does not prove this operation	Retain reservation and investigate
EFFECT_INDETERMINATE	Dispatch may have crossed boundary	Keep quarantined; query or forfeit

Table 3. Stable decisions make conservative failure observable. None of the uncertain cases is silently converted into available budget.

Result	Required assumptions / premises	Failure if omitted	Not concluded
Ownership partition and exact conservation	Authenticated unique roots/credits (Assumption 1 ); atomic durable moves ( 2 ); singleton-source guards and stable decision keys ( 3 )	Forged issuance, torn moves, or copied inputs can duplicate or lose atoms	Fair allocation, low stranding, or timely completion
Semantic and descendant non-amplification	Root/lineage authenticity; exclusive transfer; label attenuation and credit-cut accounting	A numeric balance may remain bounded while purpose, audience, or ancestry widens	Correctness of the policy classifier or optimal task decomposition
At-most-once settlement	Atomic terminal-decision key; immutable operation binding; sound tagged terminal evidence; receiver-scoped gateway idempotency	Duplicate or conflicting evidence can move the same reservation twice, or one transport retry can create multiple logical outcomes	Exactly-once delivery or honesty of an arbitrary third-party receiver
Effect coverage and external exposure bound	Authenticated binding, atomic durable ownership, and stable decisions ( 1 – 3 ); persist-before-exposure; sound normalization ( 4 ); enforced maximum-charge contract ( 6 ); fenced queryable gateway ( 5 ); complete non-equivocating terminal evidence ( 7 ); complete mediation ( 9 )	An effect can bypass its obligation, alias another effect identity, or be refunded on a false result	Coverage of covert, direct-credential, or otherwise unmediated effects
Late-completion safety and reclaim	Durable $\mathsf{R}\!\rightarrow\!\mathsf{Q}$ cut; gateway-visible monotone epoch; authoritative success/no-effect result	Timeout refund or store-only fencing permits old and new generations to use one right	Rollback of an irreversible effect or eventual recovery of stranded rights
Partition confinement	Exclusive preallocation before the cut; no unfenced cross-cut acceptance	Disconnected branches may spend the same cached remainder	Availability after local escrow is exhausted

Table 4. Assumption–conclusion boundary for the safety results. Ledger integrity alone does not establish external-effect conservation; the latter requires normalization, complete mediation, and a terminal-evidence-producing fenced gateway. A four-column table maps each theorem family to its required assumptions, the failure enabled when an assumption is omitted, and claims that the theorem explicitly does not make.

Panel of Figure 3 — Figure 3. Per-right lifecycle. A timeout can trigger reconciliation but never changes ownership. Only an authenticated settlement or a fenced proof of non-execution releases a quarantined right. A success receipt canonically partitions $X_{o}$ : $D_{o}$ commits, while $X_{o}\setminus D_{o}$ moves to the separate decision-bound $\mathsf{ReturnTarget}$ box. A fenced no-effect proof moves all $X_{o}$ to that box along a distinct dashed path. Separate source, current-owner, and return-target boxes prevent the three ownership roles from being visually conflated. Eight colored boxes distinguish source Available, Transit, current-owner Available, Reserved, Quarantined, return-target Available, Committed, and Forfeited states. Transit either returns to the source after a cancel decision or moves to the current owner after an accept decision. Solid arrows show reserve, expose, success settlement, and retirement. The two success arrows split the footprint: the actual subset moves to Committed and the remainder moves to the return-target Available box. A separate dashed curve sends the whole quarantined footprint to that box after a fenced no-effect proof. A dashed self-loop on Forfeited says late evidence annotates without changing ownership. A red curved arrow from Quarantined to current-owner Available is labeled timeout refund forbidden.

Record	Immutable identity/binding	Mutable state	Uniqueness or integrity rule
root_grant	root, issuer, resource schema, issued vector, label digest	status, current policy version, installed fence epochs	issuer signature; one issued vector per root generation
credit	root, logical slot/reissue-chain ID, credit ID, parent credit ID, generation, epoch, issuer, credit authority/owner, source-label digest, lineage and rights commitments	available ranges, lifecycle, current marker	immutable predecessor identity; at most one current generation per logical slot/reissue chain; disjoint split siblings may be current concurrently, but live ranges never overlap
transfer	root, transfer ID, source generation, destination, ranges, label	sealed / accepted / rejected / fenced	unique $(root,transfer\_id)$ ; terminal decision immutable
operation	root, logical slot, operation ID, source lineage/rights commitments, epoch, effect digest, receiver, key, $\beta_{o}$ , maximum vector, source/operation labels, witness, selector schema version	reserved/quarantined/terminal phase; write-once return target and $H(D_{o}),H(X_{o}\setminus D_{o})$ inside the terminal decision	unique $(root,operation\_id)$ ; immutable replay, partition, and return binding
gateway_effect	$iid$ , key, $\beta_{o}$ , receiver, effect digest, acceptance sequence	accepted/effect/terminal outcome	one immutable acceptance binding and at most one instance per key
terminal_evidence	evidence ID, tagged variant, $\beta_{o}$ , root/slot/operation binding, authority/signature; success adds $iid$ , acceptance sequence, and actual vector; no-effect adds fence epoch	verification result and application time	unique evidence ID and one compatible terminal variant per operation

Table 5. Logical durable records. A cryptographic audit chain detects post-hoc modification but does not replace atomic ownership transitions.

Transition	Local work	Coordination
Reserve / settle	$O(d)$	one local durable transaction
Split	$O(d+\ell)$	one local durable transaction
Cross-store transfer	$O(d+\ell)$	source seal + destination accept
Join	$O(pd+p\ell)$	one authority over all consumed inputs
Reconcile	$O(d)$ per operation	gateway query; reclaim additionally needs fence + non-acceptance proof
Audit replay	$O(d)$ per transition	none on enforcement path

Table 6. Asymptotic costs for compressed footprints. Cryptographic verification adds work proportional to the chosen signature and commitment formats.

Fault injection point	Ambiguity created	Required safe state	Bug exposed if weakened
After reserve commit, before dispatchable	No exposure possible by durable evidence	$\mathsf{R}$ , then verified abort	leaked reservation or unsafe send without outbox
After quarantine commit, before send	Send may not have happened	$\mathsf{Q}$ until gateway proof	utilization loss if safe; double spend if blindly refunded
After gateway effect, before reply	Effect exists, response absent	$\mathsf{Q}$ , then receipt settlement	timeout-refund/late-effect overspend
After receipt arrival, before ledger commit	Receipt can replay	same settlement applied once	duplicate charge or duplicate remainder
During sealed transfer	Source debited, destination unknown	$\mathsf{T}$ until accept/exclusion	both-side ownership after retry
During epoch advance	Old worker may retain credentials	old gateway requests fenced	stale-generation spend after reclaim

Table 7. Required crash and concurrency cuts. Each outcome is checked after every durable prefix, not only after recovery completes.

Evidence	Declared finite scope	Generated or edges	Distinct states	Depth	Safe outcome
Settlement TLC	2 atoms, 2 actors, epochs/generations 0..1	54,477	16,592	29	exhausted; no violation
Lineage TLC	2 dimensions, 4 rights, 4 credits	23	21	8	exhausted; no violation
JavaScript graph	2 atoms, 2 actors, complete reachable graph	54,476	16,592	28	exhausted; no violation

Table 8. Completed bounded safety checks. The generated-or-edges column denotes TLC generated states for the TLA+ rows and explored transitions for JavaScript. Completion applies only to the constants shown.

Weakening	Detection	Shortest retained witness	Observed failure
Timeout refund after exposure	TLC and JavaScript	TLC depth 4; JS depths 3 and 5	unsafe reclaim; then loss of effect coverage after the accepted request completes late
Historical-certificate validation (compound)	lineage TLC	6 states	ownership uniqueness; 8 live occurrences for 4 rights (maximum multiplicity 2)

Table 9. Targeted mutant results. Witness lengths are breadth-first counterexamples in the declared finite models, not field-failure probabilities. The historical-certificate row weakens both currentness and disjointness validation.

Safe schedule	Kills	Records	Checker
W2 pre-commit rollback	1	29	pass
W2 post-commit recovery	1	23	pass
gateway-accept pre-commit rollback/retry	1	33	pass
gateway-accept post-commit dedupe	1	24	pass
effect/reply loss; W4 pre-commit	2	29	pass
W4 post-commit dedupe	1	27	pass

Table 10. Independent checks over ten concrete safe traces. Each case uses fresh branch-ledger and gateway databases.

Attack or failure	Prevented or detected by	Residual consequence	Outside the theorem
Duplicate child allocation	atomic exclusive split + stable ID	duplicate request stutters	corrupt authoritative store
Lineage alias at fan-in	disjoint rights commitment + input consumption	join rejected	unsound commitment implementation
Dispatch replay	operation binding + gateway idempotency	prior outcome returned	non-cooperating receiver
Timeout refund race	$\mathsf{Q}$ retention + reconciliation	stranded capacity	guaranteed eventual receiver response
Stale worker	gateway-visible epoch fence	old request rejected or observed	direct credentials bypassing gateway
Forged/changed receipt	signature and full binding verification	quarantine and investigation	compromised terminal-evidence authority

Table 11. Security coverage and residual risk. The protocol prefers explicit loss of utility to an unsupported conservation claim.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Domain	Meaning
$\mathcal{K}$	finite set	authenticated resource dimensions
$\mathbf{B}_{g}$	$\mathbb{N}^{\|\mathcal{K}\|}$	vector issued by root grant $g$
$U_{g}$	finite disjoint union	logical unit rights underlying $\mathbf{B}_{g}$
$X_{c},X_{o},X_{x}$	subsets of $U_{g}$	credit, operation, and transfer footprints
$\mathsf{vec}(X)$	$\mathbb{N}^{\|\mathcal{K}\|}$	per-dimension cardinality of footprint $X$
$\lambda$	authorization-label domain	root, principal, purpose, audience, effect class, expiry, and policy version

Appendix

Table 12. Notation. Logical unit sets make aliasing explicit; the runtime may use compact balance and lineage certificates.

Action	Precondition	Postcondition	Replay/failure behavior
$\mathsf{Issue}$	authenticated fresh root; vector and label schema valid	all $U_{g}$ in one root $\mathsf{A}$ credit with a fresh logical slot; install matching epoch and active-generation registers	duplicate root ID rejected or returns identical issuance
$\mathsf{Split}$	current owner generation/epoch; pairwise-disjoint subsets; attenuated labels	parent loses exactly union; install every child under a pairwise-distinct fresh logical slot; close and clear the parent only if its complete responsibility is consumed	same request stutters; conflicting replay rejected
$\mathsf{Delegate}$ seal	current source; subset available; destination/label bound	same atoms $\mathsf{A}\rightarrow\mathsf{T}$ ; signed certificate/outbox durable	send retries preserve transfer ID; timeout stays $\mathsf{T}$
$\mathsf{Delegate}$ decision	valid current certificate or destination-exclusion proof; decision pending	CAS to exactly one of accepted or cancelled and logically moves the footprint to the unique destination child or back to the source; acceptance installs the child under a fresh logical slot with matching current registers	duplicate returns prior decision; competing terminal decision rejected
$\mathsf{Delegate}$ materialize	terminal transfer decision and matching footprint	durable rows materialize the logical owner already selected by the decision register; abstract stutter	crash recovery repeats the same materialization; stale source or destination rows are never authoritative
$\mathsf{Reserve}$	current credit/epoch; available footprint; valid effect and joint witness	same atoms $\mathsf{A}\rightarrow\mathsf{R}$ ; operation, obligation, outbox, audit atomically durable	duplicate identical operation stutters; changed binding rejected

Appendix

Table 13. Abstract action contract for issuance, transfer, reservation, dispatch, acceptance, and effect occurrence. Preconditions are part of the mechanism, not optional validation advice.

Action	Precondition	Postcondition	Replay/failure behavior
$\mathsf{Settle}$ success	full footprint in $\mathsf{Q}(o)$ ; valid receipt for $\iota\in\mathsf{Obs}$ , matching $\beta_{o}$ ; when the remainder is nonempty, a decision-bound return credit satisfying Equation ( 7 ); $\mathbf{0}\preceq\mathbf{d}\preceq\mathbf{u}$	version-bound $\mathsf{Take}_{\nu_{\mathsf{sel}}}(X_{o},\mathbf{d})$ $\mathsf{Q}\rightarrow\mathsf{C}$ ; complement $\mathsf{Q}\rightarrow\mathsf{A}$ ; bind $H(D_{o})$ and $H(X_{o}\setminus D_{o})$	identical receipt stutters; conflicting receipt or partition rejects
$\mathsf{Return}$	type-matched $\zeta$ : local no-dispatch precondition for $\pi_{\mathrm{local}}$ , or gateway fence plus authoritative $\pi_{\neg e}$ proof that the exact binding was never accepted and cannot occur; return target satisfies Equation ( 7 )	all operation atoms move from the branch-specific $\mathsf{R}/\mathsf{Q}\rightarrow\mathsf{A}$ ; write terminal decision and audit; the local branch also persists $\pi_{\mathrm{local}}$ and sets the dispatch gate to absorbing local-abort	timeout or local lease expiry alone has no transition
$\mathsf{Retire}$	unresolved quarantined operation and authorized administrative decision	all operation atoms $\mathsf{Q}\rightarrow\mathsf{F}$	availability never increases; $\mathsf{F}$ is absorbing
$\mathsf{Fence}$	source is current; authenticated target $\eta^{+}>\mathsf{AuthoritativeEpoch}(g,\chi_{c})=\eta_{c}$ ; gateway installation protocol satisfied	install the gateway fence, mark the old credit closing, clear its active generation, and advance the slot authority epoch without moving balance or creating a successor; old generation cannot initiate a new effect and recorded old outcomes remain queryable	old messages reject or return prior result
$\mathsf{Reissue}$	old generation closed at installed $\eta^{+}$ ; exact $\mathsf{Reusable}$ footprint uniquely available; $\mathsf{SafeA}=\mathsf{Avail}$ ; write-once key selects $(\eta^{+},c^{+})$ for normalized predecessor $(g,\chi_{c},cid,\eta_{c})$ ; target satisfies Equation ( 16 )	one transaction moves only that footprint and installs $c^{+}$ as current for the same logical slot	committed, forfeited, accepted, or unresolved atoms never move; exact replay stutters and changed target rejects
$\mathsf{TerminalRollover}$	fenced predecessor is closing; $o$ is its final nonterminal operation with a type-matched terminal-outcome witness; source and settlement authority agree; $\mathsf{SafeA}=\mathsf{Avail}$ ; both decision keys are unassigned; normalized reissue target satisfies Equations ( 17 )–( 18 )	one transaction fixes the terminal partition, moves only its return footprint plus disjoint $\mathsf{SafeA}$ to $c^{+}$ , closes $c$ , and installs $c^{+}$ , writes both keys, sets the witness-specific operation/outbox outcome, and appends its audit node; the local branch additionally sets the absorbing local-abort dispatch gate	exact replay stutters; changed evidence, partition, epoch, or successor rejects

Appendix

Table 14. Abstract action contract for settlement, return, retirement, fencing, reissue, fused rollover, and join (continued).

Concrete event	Abstract image	Required evidence	Forbidden mapping
Root row commit	$\mathsf{Issue}$	issuer signature, fresh generation, exact vector	editing an existing issued vector
Source debit + transfer row commit	$\mathsf{Delegate}$ seal	one transaction, same compressed ranges	message send before source debit
Transfer-decision CAS	$\mathsf{AcceptTransfer}$ or $\mathsf{CancelTransfer}$ , including the one logical ownership switch	valid certificate/exclusion proof and monotone decision register	accepted and cancelled both becoming terminal
Destination/source finalization	$\mathsf{stutter}$ (materialization only)	same terminal decision and exact compressed ranges; logical ownership is read from the decision register	treating a stale row as authoritative or moving the abstract footprint a second time
Operation/outbox commit	$\mathsf{Reserve}$	atomic debit and immutable slot/effect binding	reserving after tool execution
Dispatchable marker commit	$\mathsf{Dispatch}$	durable $\mathsf{R}\rightarrow\mathsf{Q}$ before gateway exposure	network send while still only $\mathsf{R}$

Appendix

Table 15. Refinement obligations for issuance, transfer, dispatch, and gateway effects.

Concrete event	Abstract image	Required evidence	Forbidden mapping
Terminal-outcome transaction	$\mathsf{Settle}$ , $\mathsf{Return}$ , or, when fused with successor installation, $\mathsf{TerminalRollover}$	a tagged external signature or trusted durable local no-dispatch witness, $\beta_{o}$ including selector version, one terminal CAS, exact committed/remainder footprint commitments, and Equation ( 7 ) for every returned atom	treating a success receipt as no-effect evidence, choosing a noncanonical partition, applying a textual worker assertion, or widening/redirecting a remainder
Timeout / worker death	stutter + reconciliation request	no ownership change	$\mathsf{Q}\rightarrow\mathsf{A}$
Epoch installation	$\mathsf{Fence}$	monotone successor visible at every protected gateway	local-only epoch bump followed by reuse
Ordinary successor-generation transaction	$\mathsf{Reissue}$	closed-generation proof at the installed $\eta^{+}$ , exact uniquely available reusable footprint, write-once unique reissue decision, and authenticated target satisfying Equation ( 16 ); decision, current metadata, and move are atomic	copying old $\mathsf{C}/\mathsf{F}/\mathsf{T}/\mathsf{Q}$ atoms or widening/changing the successor lineage, root, or authority
Fused final-outcome/successor transaction	$\mathsf{TerminalRollover}$	Equations ( 17 )–( 18 ); canonical terminal partition and status; complete $\mathsf{SafeA}$ ; atomic terminal and normalized reissue decisions	mapping the fused commit to only $\mathsf{Settle}$ , $\mathsf{Return}$ , or $\mathsf{Reissue}$ , or copying an input atom
Audit-only append	stutter	digest of an already authoritative decision	moving rights solely because a log entry exists

Appendix

Table 16. Refinement obligations for terminal resolution, fencing, and successor installation. A trace that cannot be mapped without violating Tables 15 – 16 is outside the implementation theorem.

Claim	Analytical support	Executable support	Explicit exclusion
Ownership partition	transition induction over raw ownership relations	lineage tagged-occurrence model, legal-join witness, and compound invalid fan-in mutant; settlement model separately checks the single-location obligations	Byzantine/corrupt authoritative store
Exact six-bucket conservation	partition lemma + vector corollary	finite transition-accounting checks and runtime prefix checks	real-world value not represented by resource schema
Descendant non-amplification	cut/lineage induction	split, transfer, join, and alias schedules	task quality and fair allocation
At-most-once settlement	immutable binding + terminal CAS	duplicate and conflicting receipt cases	exactly-once network delivery
Effect-instance coverage and external exposure bound	injective gateway binding + complete-charge theorem	effect-instance log joined to operation and maximum-vector trace	unmediated paths or dishonest charge authority
Late-completion safety	$\mathsf{Q}$ retention + fence argument	effect-before-response-loss and delayed receipt cases	automatic eventual refund

Appendix

Table 17. Claims are linked to distinct analytical and executable evidence. The exclusions are part of the claim, not deferred implementation details.

Explore similar work

Jun 2, 2026cs.SE

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

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.

Sajjad Khan

independent researcher; MSc in Data Science, University of the West of England, Bristol, UK

Agent Failure Analysis Multi-Agent LLM Systems LLM Agents LLM Agent Reliability

Ask PDF

Aug 26, 2026cs.IR

When Stale Constraints Go Unchecked: Budgeted Verification Failures in Inherited Agent Memory

Provenance links keep the evidence behind an inherited belief reachable; an agent with a verification budget must still choose which links to inspect. We study a consolidated memory that states a decision constraint and whose source record has since been superseded by a record that withdraws it: provenance is immutable, the current record has changed, and the memory is stale. In a controlled six-memory scenario with a budget of two records, sixteen language models rarely re-verified a constraint that read as settled: they inspected its provenance path in about one episode in five and, once the constraint had been superseded, produced stale-consistent decisions in 77.3%, 74.7% and 74.7% of episodes across a primary run, a replication and a held-out domain. Re-assigning one of the same two slots to the critical path removed most of them: +74.0, +72.7 and +61.3 points (positive in every model), +80.7 in a prospectively frozen interleaved replication with a repaired non-critical control, and +62.0 on a panel of 10 models from 9 organisations; a corrected re-run of the held-out scenario gave +73.3. The forced-critical policy uses experimenter knowledge of the critical path: it quantifies how much stale-decision risk the same budget can recover and is not a scheduler. Two further deposited experiments locate the failure and a remedy: in this store the constraint's path is selected in 17.0% of episodes at two slots and 88.7% at four of six (above uniform allocation), and at two slots a one-sentence, target-blind rule (prefer memories that state a limit on a candidate direction) moved the agent's own allocation onto the constraint's path and recovered the oracle contrast on decisions (+89.3 points) where that constraint limits the tempting action, while a content-free freshness cue did not materially redirect allocation and a content-matched control rule changed neither selection nor decisions.

Kazuki Nakayashiki

Glasp

LLM Agent Verification LLM Agent Reliability Agent Memory Management Data Provenance

Ask PDF

Jun 28, 2026cs.AI

Budgeted Act-or-Defer Multi-Agent LLM Deliberation with Local Reliability Bounds

Multi-agent deliberation among LLMs can improve reasoning, but deployment requires deciding when the current answer is reliable enough to act on and when it should be escalated to human review. We formulate this as budgeted act-or-defer decision making. At each round, the system maps the debate prefix to a low-dimensional state, computes a

k

-nearest-neighbor lower confidence bound on state-conditional correctness using calibration data, and acts only when the bound exceeds a user-specified reliability threshold. The certificate controls wrong actions through the decomposition

β= δ+ α+ \varepsilon_{\mathrm{act}}

, separating calibration failure, residual action risk, and representation gap. The guarantee is conditional, not distribution-free: it relies on a valid local bias envelope and an action-region representation-gap bound, and each assumption is paired with falsification-style diagnostics. Because the same absolute wrong-action budget has different meanings across tasks of different difficulty, we set budgets relative to each task's final-round error using training data only, and evaluate safety by normalized budget usage

\mathrm{WA}/β

. On six benchmarks against nine baselines, the method uses 9--12% of the pre-declared budget on activated datasets, reaching up to 84% automation and 96% acted-on accuracy; on stress-test datasets, it defers rather than forcing unreliable automation. Rather than relying on per-task post-hoc threshold search, the method prospectively converts a user-declared wrong-action budget into an auditable act-or-defer operating point before deployment, under explicitly stated assumptions.

Mengdie Flora Wang, Haochen Xie, Guanghui Wang +2

1AWS Generative AI Innovation Center, USA · General Motors (GM), USA

AI Agent Reliability Multi-Agent LLM Systems Selective Prediction LLM Decision-Making LLM Agent Reliability

Ask PDF