PaperlayerView exact revision on arXiv

Source-linked AI summary

ResidualAuth: What Authorization State Must Language Agents Preserve under Revocable Delegation?

Moonwon Choi, Seokho Jeong, Seunggeun Lee

arXiv:2609.08062v1cs.AIcs.CR

TL;DR

Tool-using agents may need authorization information about grant provenance, not merely current reachability, to answer future revocation queries. ResidualAuth formalizes the required residual state, proves its complexity, and tests whether interfaces and models preserve it. Authenticated query reads and hard effect mediation succeed in their respective roles, while bounded model-written memory rarely maintains every required distinction.

  • Problem

    Current permissions and all-pairs reachability may be identical even when the same direct-edge revocation requires opposite future authorization decisions.

  • Method

    ResidualAuth defines future-equivalent histories by all valid future continuations, derives residual-state complexity laws, and compiles the separations into controlled paired-agent episodes and diagnostics.

  • Results

    Authenticated reads achieved 15–16/16 pair-complete accuracy across four models, while fixed 256-token summaries achieved 0–2/16 and sham reads 0/16.

  • Takeaways & Limitations

    Required authorization state, usable decision information, online state maintenance, and effect mediation are distinct design questions.

  • Takeaways & Limitations

    The empirical scope uses 16 matched pairs per model, 128 held-out pairs per online-memory cell, and prespecified continuations rather than every formal string continuation.

Abstract

from arXiv · show

Tool-using language agents can delegate and revoke permissions while acting through external services. We show that two authorization histories can have identical current permissions and identical all-pairs reachability yet require opposite decisions after the same direct-edge revocation. We formalize the information needed to preserve such distinctions as a residual authorization state. We prove that exponentially many future-distinct states can share one fixed transitive closure, and give exact or tight asymptotic bounds on the state required by an exact monitor as delegation redundancy varies. ResidualAuth compiles these constructions into paired language-agent episodes. Across four open-weight models, a fixed 256-token summary solved 0-2/16 pairs, sham reads solved 0/16, and authenticated current-query reads solved 15-16/16. In a separate held-out online-memory diagnostic, exact ledger serializations fit all 128 four-coordinate pairs at both 768 and 1,024 tokens. At either cap, factually supported model-written memories sufficient for every prespecified continuation solved at most 1/128 pairs per model. A hard gate reduced eight observed unauthorized effects to zero without changing the preceding attempts. These results distinguish required authorization state, usable decision information, online state maintenance, and effect mediation.

1 INTRODUCTION

Tool-using agents must preserve more than current reachability because identical present permissions can diverge after the same direct-edge revocation. ResidualAuth formalizes future-sufficient state and evaluates whether agents can access and use it.

  • Motivation: Identical current reachability can yield opposite decisions after the same revocation when direct permission provenance differs.In the example, revoking o →m removes u’s authorization in one history but not the other.
  • Motivation: Current authorized sets and transitive closures omit which direct grants support reachability after named revocations.Future authorization depends on the direct grants that created current reachability.
  • Residual authorization state: Future-equivalent histories agree on every possible sequence of grants, revocations, and protected uses.A future-sufficient representation determines the resulting equivalence class.
  • Contributions: ResidualAuth characterizes exact future-distinct states, their redundancy–memory relationship, and whether language agents can use the required distinctions.The evaluation compares bounded summaries, sham and authenticated reads, and execution controls.
  • Scope: The formal lower bounds concern exact finite-state summaries under stated semantics, not literal token or neural-activation requirements.The paper does not propose a general-purpose production revocation protocol.

2 RESIDUAL AUTHORIZATION MODEL

The model represents each right as a directed graph of direct grants and defines authorization through reachability. Exact monitoring is characterized by residual equivalence over valid action histories.

  • Authorization histories: Each right uses a directed graph whose edge i →j means principal i directly granted that right to j.The root is authorized by convention; other principals are authorized exactly when reachable.
  • Action semantics: Histories contain grant, revoke, and use actions, with validity and graph updates governed by idempotent administrative semantics.Duplicate grants and absent-edge revocations are valid no-ops in the main semantics.
  • Assumptions: The model assumes independent rights, coordinate locality, and joint reachability across one-right states.Strict variants with invalid duplicate grants or absent-edge revocations are treated separately.
  • Residual state: Two histories are future-equivalent when they have the same residual set of valid future action sequences.A representation is future-sufficient when equal representations imply equal residuals.
  • Exact monitoring: An exact deterministic online monitor requires exactly Nres states, and zero-error randomized monitoring requires at least Nres states.The result uses an absorbing dead state under the paper’s acceptor convention.

3 FUTURE-SUFFICIENT STATE UNDER REVOCATION

Revocation makes current reachability insufficient: exponentially many future-distinct authorization states can share one transitive closure. Required memory increases with delegation redundancy, while explicit information limits impose approximate-monitoring error bounds.

  • Exponential separation: 2^(N(N−1)/2) residual states can share one fixed transitive closure for one right under persistent or cascading delegation.With r independent rights, the construction yields a product bound across rights.
  • Construction: A fixed closure can contain every subset of forward shortcuts because adding them leaves the chain’s transitive closure unchanged.A tailored revocation sequence tests each shortcut independently.
  • Monitoring consequence: Exact encodings must distinguish states that react differently to a future named revocation, even without storing a literal adjacency matrix.Closure-only representations therefore lose exponentially many distinctions.
  • Redundancy–memory law: Without revocation memory is linear in N, one-parent policies add a logarithmic factor, and dense redundant support gives a quadratic state exponent.One-parent policies reduce memory by restricting redundant failover behavior.
  • Approximate monitoring: Retaining at most half of shattered information yields an error floor of h2^-1(1/2) ≈0.11, while b = 0 gives 1/2.Additional computation from the retained information and an independent probe cannot evade the same lower bound.

4 THE RESIDUALAUTH BENCHMARK

ResidualAuth converts formal same-now/different-next separations into audited executable episodes and separates decision information from effect control. Its benchmark uses graph–ledger checks, trusted query evidence, and a hard execution gate.

  • Benchmark design: Each benchmark pair has the same checkpoint reachability and later revocation but different direct provenance and opposite terminal labels.The benchmark tests whether theory-identified distinctions are usable under different interfaces.
  • Ledger validation: The concrete-ledger bridge projects grant identities and parent lineages into abstract effective edges and maps concrete events to abstract actions.Its assumptions include well-founded selected-parent lineage and no hidden alternate support.
  • Fresh query evidence: A current path witness is insufficient for arbitrary post-update queries, while path-or-cut certificates are sound and complete for one fixed query against a trusted post-update graph.The false-accept bounds are min{1, Nδ} for paths and min{1, N^2δ} for cuts.
  • Information and enforcement: Authenticated reads expose the correct decision information, whereas sham reads do not; a hard gateway separately prevents unauthorized committed effects.The interfaces therefore probe decision information and effect mediation as distinct layers.
  • Online state maintenance: The online-memory audit treats exact ledger serialization as a representational ceiling and requires model-written memories to be factually supported and correct for every prespecified continuation.Table 2 reports pair-complete results out of 128.

5 EXPERIMENTAL SETUP

The study evaluates four open-weight models under controlled authorization-observation, state-maintenance, and execution conditions, using matched paired episodes and a separate held-out audit.

  • Controlled interface study: Four open-weight models are evaluated at pinned revisions in matched four-coordinate conditions containing 16 pairs per condition.The models are Qwen3.6-35B-A3B, Gemma-4-26B-A4B-it, Ministral-3-14B-Instruct-2512, and Mistral-Small-4-119B-2603.
  • Controlled interface study: The controlled interface study compares a deterministic 256-token event summary, a content-matched sham tool, and authenticated query access.
  • Online state-maintenance audit: The held-out online audit tests stateless maintenance using only model-written memory and the next eight public typed-DSL events.It contains 1,024 evaluation pairs disjoint from 32 calibration pairs.
  • Experimental controls: Token caps are interface constraints rather than measurements of the information quantities in the information-theoretic theorem.All runs use temperature zero, one seeded pass per episode, and pinned model revisions.

6 RESULTS

Results separate decision information, online state maintenance, and effect mediation: authenticated reads improve paired decisions, strict model-written memories rarely suffice, and hard execution blocks unauthorized effects.

  • Information access: Authenticated reads achieved 15–16/16 pair-complete decisions across models, versus 0–2/16 for 256-token summaries and 0/16 for sham reads.The read-versus-summary and read-versus-sham contrasts remained significant after Holm correction.
  • Online state maintenance: Exact ledger serializations solved all 128 four-coordinate pairs at both 768 and 1,024 tokens, while strict model-written memories solved at most 1/128.The relaxed endpoint was reported only as a diagnostic and reached 3, 0, 12, and 64/128 pairs at B = 1024 across models.
  • Diagnostic boundary: The terminal diagnostic requires latest fresh-ID regrant provenance but does not require correct expiry or cascading-deletion semantics.Those operations were measured only through intermediate trajectory fidelity, where performance was also poor.
  • Complete-history diagnostics: Full-history results were heterogeneous, ranging from 10–32/32 pairs in one bounded-memory study to 22/24 and 19/24 in a terminal-only realism suite.These results were retained as diagnostics rather than a universal context-length claim.
  • Effect mediation: Hard execution reduced committed unauthorized effects from eight to zero while leaving the eight unauthorized attempts unchanged.Pair-complete decision accuracy remained zero in both advisory and hard conditions.

7 RELATED WORK

Related work spans delegated authorization, agent memory and authorization benchmarks, provenance-aware runtime enforcement, and state-complexity analysis, while ResidualAuth targets future-equivalent authorization histories.

  • Delegation and revocation: Prior authorization work formalizes delegated authority, revocation propagation, and agent-specific delegation metadata or scoped policy extensions.
  • Authorization and memory benchmarks: Authorization and memory benchmarks test privilege selection, contextual access control, forgetting, and whether memory consolidation preserves source authority.
  • Provenance and enforcement: Runtime-enforcement systems separate trusted control flow, least-privilege tool policies, per-call authorization, and argument-level provenance.
  • State complexity and evaluation: ResidualAuth applies Myhill–Nerode equivalence to authorization histories rather than current reachability, and uses matched counterfactual pairs to separate retained state, fresh information, and effect mediation.The paper does not claim that its lower bound arises from natural language or that it is a general memory benchmark.

8 DISCUSSION AND LIMITATIONS

The discussion distinguishes preserving provenance, restricting delegation, externalizing queries, and mediating effects, while limiting the claims to the stated formal semantics and empirical settings.

  • Interpretive framework: The paper separates required authorization distinctions, usable decision information, online state maintenance, and post-decision effect mediation.
  • Design choices: Systems can preserve future-relevant provenance, restrict redundancy through lineage or parent caps, or externalize a specific query through authenticated evidence.These choices are not equivalent: preservation supports arbitrary future queries, restriction changes policy expressivity, and externalization answers a specific query.
  • Formal scope: The formal lower bounds assume an initially empty binary direct-edge model with one right governing use and further delegation.Real systems may include separate privileges, negative permissions, groups, thresholds, attributes, wildcard scope, or privilege lattices.
  • Theoretical limits: The information theorem requires an explicit finite-message or mutual-information premise, so token-budget curves are not themselves such a premise.The paper also does not prove a lifting theorem from arbitrary natural-language conversations to the formal action language.
  • Empirical limits: Empirical claims are bounded by small matched-pair cells, non-comparable tokenizer caps, prespecified coordinate continuations, and limited evidence for general online-maintenance attribution.Only Gemma at eight coordinates passed the computation gate, and no prespecified online-maintenance contrast survived Holm correction.

9 CONCLUSION

ResidualAuth shows that current reachability is not future-complete under edge-addressable revocation. Practical systems can preserve provenance, restrict redundant delegation, or obtain trusted query-specific information, while effect mediation remains separate.

  • Authenticated query reads made the required authorization distinction usable in controlled episodes, whereas sham access did not.Execution-time effect mediation is a separate design layer.
  • Exact state fit within tested online-memory budgets, but factually supported model-written state almost never survived every prespecified continuation.

REPRODUCIBILITY STATEMENT

The paper provides complete proofs, documented benchmark and verification procedures, and a code package supporting reproducibility.

  • Appendices A–H provide the formal setup and complete proofs.
  • Appendices I–M document the benchmark, statistical analysis, supplementary results, and verification gates.
  • The code package contains the controlled episode generator, exact model-memory executor, verifiers, audits, and pinned model and environment details.

ETHICS STATEMENT

ResidualAuth uses synthetic authorization episodes rather than real credentials, private user records, or deployed access-control configurations. The results therefore place authorization state and effect mediation outside the language model in the studied settings.

  • ResidualAuth uses synthetic authorization episodes and no real credentials, private user records, or deployed access-control configurations.
  • The studied results do not support treating a language model as the security boundary.
  • Authorization state and effect mediation are maintained outside the model in the settings studied.

AI USE STATEMENT

The paper formalizes authorization histories, validity, residual states, and delegation semantics, then connects future-equivalent states to exact online-monitor complexity. Its formal and empirical claims are explicitly scoped by the stated semantics and evaluation conventions.

  • Validity convention: The all-prefix-validity acceptor convention counts an absorbing dead residual and differs from request-by-request service semantics.
  • Residual authorization state: The residual quotient is the exact number of distinguishable future-authorization states.
  • Actions and update rules: Tool histories contain grants, revocations, and uses, with validity determined by authorization and semantics-specific graph updates.
  • Delegation semantics: Persistent semantics keeps dormant edges, whereas cascading semantics removes edges whose source is unreachable after updates.
  • Exact monitoring: The minimum exact deterministic monitor has one state per residual class, by a Myhill–Nerode argument.
  • Scope and contribution: The formal contribution is the residual quotient and its state-complexity laws, not a new automata theorem or a general-purpose production revocation protocol.

C.3.2 PROOF

The proof shows that authorization histories with identical current reachability can remain future-distinct because direct-edge revocations expose hidden delegation structure. It constructs exponentially many such distinctions within one transitive-closure fiber and extends the argument across multiple rights and parent caps.

  • Counterexample: The current authorized set is insufficient: graphs G and H authorize {a, b}, yet the same continuation is invalid from G and valid from H.The separating continuation revokes an edge whose presence differs between the graphs, then tests authorization.
  • Same-closure separation: At least exponentially many residual classes share one fixed transitive closure under persistent or cascading redundant delegation.Optional shortcut edges vary independently while preserving the mandatory chain and total-order closure.
  • Same-closure separation: With r independent rights, coordinate-local constructions yield pairwise distinct residual classes inside one fixed transitive-closure tuple.A continuation naming only the differing right separates any two tuples.
  • Construction: Every constructed shortcut graph is reachable by granting mandatory chain edges first and selected shortcuts afterward.The chain keeps every shortcut source authorized, so the construction prefixes remain valid under both persistent and cascading semantics.
  • Parent-cap extension: For a parent cap ∆, the theorem gives universal two-sided asymptotic bounds on cascading residual state across all r rights and 1 ≤∆≤N.The stated constants are uniform over sufficiently large N, all r ≥1, and every permitted parent cap.

D.1.2 PROOF

The proof constructs many reachable authorization graphs with identical transitive closure but different future behavior under revocation and isolation probes. It then derives matching state bounds, handles the Δ = 1 tree case, and shows why canonical parent-tree semantics cannot retain redundant failover behavior.

  • Same-closure constructions: Optional-shortcut graphs are reachable by valid histories and share the same total-order transitive closure.Each target retains a mandatory chain parent while selected earlier vertices may add shortcut parents.
  • Same-closure constructions: Two graphs differing on an optional edge are distinguishable by an isolation probe under idempotent semantics or by revoking that edge under strict semantics.The probe targets only the differing right or edge, separating future authorization behavior despite identical reachability.
  • State bounds: For Δ ≥ 2, the one-right estimate matches the upper bound, including the factor r from independently combining rights.The construction yields at least M^r residual tuples within one fixed transitive-closure tuple.
  • The Δ = 1 case: For Δ = 1, rooted labeled trees provide distinct residual states because revoking a parent edge either removes a subtree or leaves the target authorized.Different trees can therefore be separated by a direct-edge revocation and subsequent authorization behavior.
  • Redundant delegation: Canonical parent-tree semantics cannot preserve redundant delegation failover behavior.A graph with two incoming paths to a target has valid failover after deleting either edge, whereas every canonical state chooses one parent and fails on some continuation.
  • Residual shattering: An m-bit residual-shattering family yields at least 2^m non-dead residual classes, while identical transitive closure can still omit Θ residual bits.A fixed continuation distinguishes prefixes encoding different hidden bit vectors.

E.3.1 SPARSE-DISJUNCTION LEMMA

The sparse-disjunction results establish information lower bounds for preserving future authorization distinctions, while separating exact monitoring from model computation, certificates, and enforcement. They also delimit which claims apply to same-closure constructions and which require additional assumptions.

  • Sparse-disjunction bounds: Ω(N) targets with M_j = Θ(N) each contribute Ω(d log(N/d)) when d ≤ N/4.The construction aggregates these contributions across target blocks and rights.
  • Sparse-disjunction bounds: When d > N/4, Δ = Θ(N), and the resulting contribution is Ω(NΔlog(eN/Δ)).The direct product over rights supplies the corresponding aggregate lower bound.
  • Scope conditions: The fixed-fiber restriction is essential: same-closure conditional bounds do not follow when the conditioning closure itself varies with and reveals B.The Δ = 1 construction gives an unconditional rate–distortion bound, but not the same-closure conditional bound.
  • Information limits: Additional computation generated only from (Y, J) and independent randomness cannot overcome the same information lower bound.The statement explicitly includes chain-of-thought, reflection, and repeated self-consistency samples.
  • Decision and enforcement: Authenticated current-query reads can provide zero decision error in an existence result, whereas hard gateways constrain unauthorized effects without repairing the preceding decision.The read guarantee assumes the returned label is correctly read and followed; enforcement changes effects rather than proposals.

K.1 MODEL-MAINTAINED MEMORY VERSUS ANSWER-TIME COMPUTATION

The study separates whether authorization information is representationally available from whether models can maintain or use it. Authenticated query access and hard mediation improved outcomes, while bounded model-written memories and reasoning alone did not reliably preserve the required distinctions.

  • Model-maintained memory: At four coordinates and B = 512, exact sufficient pairs were 25/32, 25/32, 23/32, and 9/32 for Qwen, Gemma, Ministral, and Mistral Small.Model decisions on those selected pairs were correct for 25/25, 24/25, 18/23, and 3/9, respectively; these conditional rates were descriptive rather than randomized causal estimates.
  • Answer-time computation: 16/16 authenticated-read pairs were achieved by Qwen, Gemma, and Ministral, compared with 0/16 under their 256-token summaries.Mistral Small reached 15/16 with the authenticated read and 2/16 with the summary.
  • Effect mediation: Eight unauthorized effects became zero under hard execution, while the preceding advisory and hard executions each contained eight unauthorized attempts.The hard gate constrained effects without changing the number of attempts.
  • Scope: The results do not establish a general monotone budget, complexity, history-length, or serialization effect for online state maintenance.None of the 32 prespecified strict-memory contrasts survived endpoint-wise Holm correction.
Loading 2609.08062v1…