ResidualAuth: What Authorization State Must Language Agents Preserve under Revocable Delegation?
Moonwon Choi, Seokho Jeong, Seunggeun Lee
cs.AI · cs.CR
Quick verdict
Strong residual-state theory plus a well-controlled agent benchmark; key caveat: headline cells use 16 pairs and the read arm is oracle-like.
Summary
The paper asks what authorization state a tool-using language agent must preserve so future grant/revoke/use decisions stay correct under revocable delegation. Using a Myhill–Nerode-style residual equivalence over delegation histories, the authors prove one transitive-closure fiber contains at least 2^(N(N−1)/2) future-distinct states (Theorem 1), derive a redundancy–memory law (Θ(rn) without revocation, Θ(rn log n) one-parent, Θ(rnΔ log(en/Δ)) Δ-capped, Θ(rn²) persistent/cascading; Theorem 2), and give a Fano-type error floor for bounded-information summaries (Theorem 3). These constructions are compiled into ResidualAuth: matched counterfactual episodes with identical current reachability but opposite post-revocation labels, graded by symbolic replay rather than LLM judges. Across four open-weight models, 256-token summaries solved 0–2/16 pairs, sham reads 0/16, and authenticated current-query reads 15–16/16. A stricter online-memory audit found exact ledgers fit all 128 four-coordinate pairs at 768/1,024 tokens while strict model-written memories solved at most 1/128; no prespecified maintenance contrast survived Holm correction. A hard gateway cut unauthorized effects from eight to zero without altering decisions. Main limitations: headline cells use only 16 pairs per model, the read arm is an oracle-like upper bound, and scope is confined to a synthetic binary direct-edge model.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 3
● low 1
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- Under edge-addressable revocation, two histories with identical current permissions and identical transitive closure can require opposite decisions, and one closure fiber contains at least 2^(N(N−1)/2) residual states per right (Theorem 1).
- Exact monitor memory follows a redundancy–memory law: Θ(rn) without revocation, Θ(rn log n) for one-parent policies, Θ(rnΔ log(en/Δ)) under a Δ-parent cap, and Θ(rn²) under persistent/cascading semantics (Theorem 2).
- With a 256-token summary, four open-weight models solve 0–2/16 counterfactual pairs while authenticated current-query reads solve 15–16/16 and sham reads 0/16.
- Exact ledger serializations fit all 128 four-coordinate pairs at 768 and 1,024 tokens, but strict factually-supported model-written memories solve at most 1/128, showing representational fit without online maintenance.
- A hard execution gateway eliminates all observed unauthorized effects (8→0, plus a 192→0 stress suite) without changing the preceding proposals, separating decision quality from effect containment.
Strengths
Verified theory-to-benchmark pipeline
Exact state counts are cross-checked by exhaustive small-instance enumeration (Appendix M.1: persistent quotient 3/17/513 at N=1/2/3, matching 2^(rN²)+1), the ledger-to-graph refinement (Prop. 2) was audited on all 192 pairs and 12,032 prefixes, and release is fail-closed behind reference-solver, pair-integrity, temporal, split and hash gates (Fig. 3).
Cheat-resistant endpoint and symbolic grading
Pair-complete accuracy makes constant allow/deny policies score 0/16 and independent guesses ~25%; an exact symbolic grader replaces LLM judges and separates proposal, attempt, committed effect, and utility (Fig. 4), which is what makes the enforcement result interpretable.
Prespecified, corrected statistics with honest nulls
Clean four-way decomposition of the problem
Explicit scope honesty
Weaknesses
Tiny confirmatory denominators
Oracle-like decisive intervention
Floor/ceiling precludes dose-response
Endpoint-sensitivity of the memory headline
Narrow formal scope, thin frontier evidence
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
ResidualAuth (arXiv 2609.08062, SNU) is a theory-plus-benchmark paper on authorization state for tool-using language agents under revocable delegation. Central claim: current permissions — even full all-pairs reachability — are not a future-sufficient state when revocation is edge-addressable; the required information is a "residual authorization state" defined by a Myhill–Nerode quotient over delegation histories (§2, Prop. 1). Three formal results: Theorem 1 proves ≥2^(N(N−1)/2) future-distinct residual states inside one transitive-closure fiber per right; Theorem 2 gives exact counts (2^(rN)+1 monotone, 2^(rN²)+1 persistent, R_n^r+1 cascading with R_n = 2^(N²)(1±O(N²2^−N))) and Θ(rNΔ log(eN/Δ)) under a Δ-parent cap; Theorem 3 gives a Fano-type error floor for summaries under an explicit information bottleneck. Empirics test whether four open-weight models preserve and use these distinctions, and what a hard execution gate adds. Scope is explicitly narrow: initially-empty binary direct-edge graphs, one right governing use and delegation (§8 Scope).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is ResidualAuth?
It is a research paper plus benchmark showing that an agent's current permissions — even full pairwise reachability — are not enough information for future authorization decisions when permissions can be delegated and later revoked by naming a specific grant. It formalizes the required information as a 'residual authorization state' and tests whether language agents can preserve and use it.
Why can't an agent just remember current permissions?
Because after a revocation, whether someone keeps access depends on which specific direct grant survived. Two histories can look identical today yet need opposite answers tomorrow; the paper proves exponentially many such future-distinct histories share one identical transitive closure, so a snapshot provably discards needed information.
How well did language models do on the benchmark?
With a fixed 256-token summary of events, four open-weight models solved 0–2 of 16 counterfactual pairs; a fake (content-matched) tool solved 0/16; an authenticated read that returns the trusted decision solved 15–16/16. In a stricter online-memory test, exact ledger state fit the token budget for all 128 pairs, but model-written memories passed at most 1/128 under strict grading.
Is code or data available for ResidualAuth?
The paper's reproducibility statement says an accompanying code package contains the episode generator, exact model-memory executor, lineage and pair-integrity verifiers, pinned model/analysis manifests, complete prompts and tool schemas, and figure source data; episodes are synthetic, so no private data is involved.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- The provided text is a sampled excerpt: three marked '[...sampling gap...]' regions skip part of the §5 empirical narrative, portions of Appendices E–H (e.g., E.3, H.1.3 onward), Appendix K.6–K.8, and the tail of the references plus Appendix A; judgments about those regions rest on the visible surrounding text only.
- All figures, tables, and numbers cited in this review were verified present in the provided excerpt; no claim of missing content is made beyond the sampling gaps noted above.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.