PaperlayerView exact revision on arXiv

Source-linked AI summary

Authorization Closure Graph: Minimal Repair for LLM Agents with Evolving User Instructions

Qingzhuo Wang, CaiYi Wang, Jinglu Meng, Ruiyang Qin, Kunyu Peng, Zhihua Wei, Wen Shen

arXiv:2609.32428v1cs.AI

TL;DR

State-changing LLM agents need action-level authorization, but existing approaches do not specify how to selectively update authority after a partial instruction change. ACG represents authority and dependencies in a versioned graph, selectively invalidates affected nodes, and repairs missing evidence or approval. Across three models and two domains, it reports stronger safety and safe task completion, with ACG achieving the highest AS in all six settings and STS in five.

  • Problem

    Existing authorization approaches do not define how to selectively update prior authority when only part of an instruction changes, including what to invalidate, preserve, or newly authorize.

    Source: §1 · p. 1

  • Method

    ACG stores task authorization as a versioned dependency graph, selectively invalidates affected authority, preserves unaffected portions, and identifies missing evidence or approval for repair.

    Source: §1 · p. 2

  • Results

    ACG achieves the highest AS in all six model-domain settings and STS in five of six, while unsafe-task counts fall from 75 for Raw to 8 for ACG.

    Source: §4 · p. 7

  • Takeaways & Limitations

    Natural-task ablations and ClosureBench support the benefits of selective updates and minimal repair, while experiments report stronger action safety and safe task completion with moderate token cost.

    Source: §5 · p. 9

    ACG relies on correct effect and dependency specifications, authoritative observations, and authenticated confirmation; natural evaluation covers two domains with simulated users.

    Source: §5 · p. 10

Abstract

from arXiv · show

Tool-using large language model (LLM) agents increasingly perform state-changing actions that require user authorization. Yet existing approaches do not provide a principled mechanism for selectively updating prior authorization when only part of an instruction changes. To this end, we propose an Authorization-Closure-Graph (ACG)-based framework that represents authorization and its dependencies as an evolving, versioned state. ACG selectively invalidates authority affected by a revision while preserving unaffected portions of the authorization state, and computes a minimal repair that identifies only the missing evidence or authority required for execution. This enables agents to adapt to revised instructions while avoiding stale authority and unnecessary authorization requests. We evaluate ACG across three advanced LLMs in two natural tasks, and ACG consistently improves action safety rate and task success rate. Code is available at https://github.com/weiliang822/ACG.

1 INTRODUCTION

State-changing agents need both task completion and action-level authorization safety, but prior approaches do not specify how to update authority when only part of an instruction changes. ACG versions authorization dependencies, selectively invalidates affected authority, and repairs only what is missing; experiments report stronger safety and task completion.

1 INTRODUCTION

  • Existing approaches either assess individual calls without updating task-wide authority or reauthorize a complete action after a partial change, leaving selective invalidation and preservation undefined.The travel-date example illustrates the gap: a changed price may require review while unchanged passenger details and the price cap are repeated.Source: §1 · p. 1
  • ACG represents each task stage as a versioned authorization graph whose nodes capture user authority, authoritative evidence, or derived values and consequences, with edges encoding dependencies.Its six update operations are COMMIT, GROUP, REVISE, REVOKE, OBSERVE, and CONFIRM.Source: §1 · p. 2
  • When an instruction changes, ACG invalidates affected nodes and dependent descendants while preserving unaffected authority, then returns AUTHORIZE, BLOCK, or MINIMAL REPAIR based on the updated state.A changed passenger B travel date can invalidate B's selected flight while preserving passenger A's authorization; missing evidence or authority prompts local repair.Source: §1 · p. 2, Figure 1 · p. 2
  • Across three models and Airline and Retail tasks, ACG consistently improves action safety while maintaining strong task completion compared with existing guard baselines.The paper also reports ablations and ClosureBench analyses supporting retained authority, selective updates, and minimal repair.Source: §1 · p. 2

2 RELATED WORK

Prior authorization work addresses individual-call enforcement and complete-action validation, but the cited approaches do not explain how to evolve authority after a partial instruction revision. ACG focuses on that update problem.

2 RELATED WORK

  • Call-level safeguards enforce policies, permissions, dialogue context, temporal constraints, workflow state, and information-flow controls, while ACG additionally tracks which prior authority remains valid after instruction changes.Examples of call-level approaches include Wang et al. (2026a), Zwerdling et al. (2025), Shi et al. (2025), and Kang et al. (2026a).Source: §2 · p. 3
  • The distinction is temporal: call-level checks decide whether a tool call complies, while complete-action checks validate an action and ACG maintains how its authorization changes over time.The paper frames ACG's specific focus as updating authority after part of an instruction changes.Source: §2 · p. 3
  • Complete-action approaches validate supporting authority, evidence freshness, and execution provenance, whereas ACG addresses selective invalidation, preservation, and repair after a partial revision.The passage discusses contracts and history-based policies (Palumbo et al., 2026), authorization graphs (Wang et al., 2026b; Zhang et al., 2026), and execution-time checks (Weng, 2026; Santos-Grueiro, 2026; Xu et al., 2026).Source: §2 · p. 3

3 METHODOLOGY

The methodology models task authorization as a persistent, versioned graph and checks candidate actions against the relevant dependencies. When a revision or missing requirement affects authorization, it selectively updates the graph, requests minimal repair, and revalidates before execution.

3 METHODOLOGY

  • The environment setting maps an LLM-proposed tool call to a canonical action under a developer-authored task specification, which binds arguments, observations, authorization conditions, and business rules.The specification also defines the projection used to obtain action-relevant observations from environment state and verified tool results.Source: §3 · pp. 3–4

3.1 THE AUTHORIZATION CLOSURE GRAPH

  • An ACG is a finite directed acyclic graph of authority, authoritative evidence, and derived consequences, with dependency edges and records of values, versions, availability, authority, and parent versions.The framework checks an action using the dependency closure of its relevant nodes rather than the entire graph.Source: §3.1 · p. 4
  • Derived nodes are computed from parent values and current parent versions, while their authority follows INHERIT, BOUNDED, or CONFIRM rules; a current value is not automatically authorized.BOUNDED checks a stated limit, whereas CONFIRM requires explicit approval of a newly derived consequence.Source: §3.1 · p. 4
  • Six authenticated operations update authority and evidence, and GROUP defines a user-approved finite scope of canonical actions without itself approving every consequence or transferring execution authority between members.OBSERVE comes from a verified authoritative source; the other five operations are generated only from authenticated user responses.Source: §3.1 · p. 5

3.2 SELECTIVE UPDATE AND MINIMAL REPAIR

  • The decision check distinguishes established rejection reasons from missing, repairable information or authority, and dependency-minimal repair removes requirements downstream of unconditional inheritance without minimizing dialogue turns.A known business prohibition cannot be overridden by user approval; the minimality result concerns one current check, not the number of responses or turns.Source: §3.2 · pp. 5–6
  • Repair obtains verified evidence or authenticated user authority, then applies operations to directly changed nodes and dependent descendants while preserving unaffected graph state and invalidating approval of old versions.The same candidate is rechecked after repair; a changed operation or argument is treated as a new candidate.Source: §3.2 · p. 6
  • Before dispatch, ACG revalidates the retained action and withholds it if checked facts, versions, permissions, business rules, or group scope no longer pass.The framework retains the original call and consumes an unused execution allowance before dispatch.Source: §3.2 · pp. 6–7

4 EXPERIMENTS

The experiments evaluate ACG on Airline and Retail tasks across three models, comparing task completion, action safety, safe task success, mechanisms, and runtime. ACG improves safety across the main settings, while ablations and ClosureBench examine how repair, retained authority, selective updates, and approval requirements contribute.

Tasks and models

  • Evaluation covers three acting models and two τ 2-bench domains, using task-success, protected-write safety, safe-task-success, and unsafe-task-count measures.Airline has 50 tasks and Retail has 114; two independent GPT-5.6-Sol reviewers assess safety, with a third human reviewer resolving disagreements.Source: §4 · p. 7

Main Results

  • 75 unsafe-task counts for Raw fell to 8 for ACG across six settings; ACG achieved the highest AS in all six and STS in five.ACG improved or matched Raw’s task success in five settings and led both AS and STS for every model on Airline.Source: §4 · p. 7

Repair and retained authority

  • Repair improved STS for every model, and retaining the graph further improved or preserved STS while yielding the highest AS.Unsafe-task counts fell from 1/6/7 with repair alone to 0/4/2 with full ACG.Source: §4 · p. 8, Table 2 · p. 8

Selective updates with minimal repair

  • Full ACG achieved the highest or tied AS and STS across models; affected-only invalidation and minimal repair address distinct parts of the update–repair process.Preserving unaffected authority alone does not remove redundant requests, while shorter requests alone do not recover authority discarded by a global reset.Source: §4 · p. 8, Table 3 · p. 8

Consequence and group authority

  • Action-approval-only and individual-grant variants lowered AS and increased unsafe-task counts without improving STS.Action-approval-only omits separate approval of a computed consequence, while individual grants replace shared authority with separate grants for the same members.Source: §4 · p. 8, Table 4 · p. 8

ClosureBench

  • 91.7% STS at four repair units and 100% at eight; ClosureBench shows redundant approval requests can exhaust budgets, while skipped freshness or consequence approval can permit unsafe actions.The benchmark tests recorded actions after permission or evidence changes, with fixed responses and permitted outcomes.Source: §4 · pp. 8–9, Table 5 · p. 9

Runtime Efficiency

  • ACG achieved the highest STS in five of six settings with approximately 62k–99k actor tokens per task.Tokens count acting-model input and output, excluding user simulation and separate guard calls.Source: §4 · p. 9, Figure 3 · p. 9

5 CONCLUSION AND LIMITATIONS

ACG maintains agent authorization as user instructions evolve by tracking dependencies in a versioned graph, selectively invalidating affected authority, and identifying missing evidence or approval. Evaluations show stronger action safety and safe task completion with moderate token cost, while the framework relies on correct specifications and observations.

5 CONCLUSION AND LIMITATIONS

  • ACG selectively invalidates authority affected by instruction changes, preserves unaffected portions, and uses minimal repair to identify missing evidence or approval.Experiments across three models and two domains report stronger action safety and safe task completion with moderate token cost.Source: §5 · p. 9
  • The framework relies on correct effect and dependency specifications, authoritative observations, and authenticated confirmation.The authors state that validating specifications is essential when adding tools.Source: §5 · p. 10
  • Natural evaluation covers two domains with simulated users; controlled changes test mechanism behavior rather than real-world prevalence.Source: §5 · p. 10

A ACG PROPERTIES AND PROOFS

The appendix specifies the declared authorization state and proves properties of its decision and repair procedures. Its update semantics track versions and dependencies so affected nodes can be recomputed while unaffected authorization remains valid under stated conditions.

A ACG PROPERTIES AND PROOFS

  • The appendix formalizes which requirements the graph establishes, which remain unresolved, and which repair requests are redundant.It supplies assumptions and proofs for the two propositions in Section 3.2.Source: A ACG PROPERTIES AND PROOFS · p. 12

A.1 STATE SEMANTICS AND PRESERVATION UNDER UPDATES

  • When an observed fare changes from $80 to $120 against a $100 cap, the derived payment is recomputed and has no authority.The example distinguishes freshness from permission and illustrates invalidating only descendants of the changed parent.Source: §A.1 · p. 12
  • The task graph is acyclic, derived nodes use deterministic rules, and user constraints remain distinct from business rules that approval cannot waive.Tool observations are trusted only within their declared authoritative source’s scope.Source: §A.1 · p. 12
  • Evidence availability and user authority are separate: current observations grant no permission, while derived nodes require successful evaluation with current parent records.Authority-bearing parents, bounds, and approvals have distinct conditions; confirmation is tied to the current value and parent versions.Source: §A.1 · p. 12
  • Updates retire old dependent records, insert authenticated changes, and recompute affected derived nodes in topological order.Unaffected derived nodes and actions retain their authorization status when their required dependency closure is unaffected and the grant allowance is unchanged.Source: §A.1 · pp. 12–13

A.2 PROOF OF PROPOSITION 1: MINIMAL DEPENDENCY REPAIR

The repair proof defines dependency coverage among missing requirements and shows that the frontier is the least request set preserving that coverage. Repair remains iterative, and the result is limited to a fixed-action problem.

A.2 PROOF OF PROPOSITION 1: MINIMAL DEPENDENCY REPAIR

  • Coverage represents missing requirements reached by a request or its unconditional descendants, but does not mean one parent supplies every input to a multi-parent rule.The frontier is defined by missing requirements with no predecessor in the missing set under unconditional INHERIT paths.Source: §A.2 · p. 13
  • The frontier F is the unique least request set under inclusion, and the unique minimum-cardinality set among requests with the same dependency coverage.If the missing set is empty, the frontier is empty.Source: §A.2 · p. 13
  • Independent CONFIRM or BOUNDED requirements remain explicit, and recomputing evidence alone does not resolve a missing permission.When two unavailable sources and an inherited derived requirement are missing, the frontier retains both sources and removes only the derived requirement.Source: §A.2 · p. 13
  • Repair is iterative: new evidence can reveal consequences or failed business conditions, and the proof does not claim to minimize conversations across alternative plans or tools.Source: §A.2 · p. 13

A.3 PROOF OF PROPOSITION 2: AUTHORIZATION DECISIONS

The proof checker distinguishes blocked actions from repairable omissions and authorizes only actions whose declared requirements hold at checked versions. Execution revalidates those versions, while the Retail specification illustrates how tool semantics, policy, evidence, and authority are encoded.

A.3 PROOF OF PROPOSITION 2: AUTHORIZATION DECISIONS

  • A nonempty rejection set blocks the action; otherwise missing requirements trigger minimal repair, and an empty missing set permits authorization.The checker separates established blockers, such as business-rule violations or scope mismatches, from missing information or authority that can be repaired.Source: §A.3 · p. 14
  • Authorization establishes every declared requirement and applicable business condition at the checked versions, and the finite acyclic graph makes evaluation terminate.The proposition does not establish that Λ captures every real-world consequence; later observations or revisions require revalidation.Source: §A.3 · p. 14

A.4 CONNECTING GRAPH DECISIONS TO ACTUAL EXECUTION

  • A disclosed action or derived consequence can be confirmed at its current version, but an unbound affirmative creates no authority change.A user’s price-limit revision can be scoped to one booking without changing another passenger’s authorization or overriding a business prohibition.Source: §A.4 · p. 14
  • Before dispatch, the framework checks the recorded node versions and grant; a changed dependency or business condition withholds the call for re-evaluation.A successful revalidation dispatches the original call once under an unused allowance, which a refreshed observation or new candidate identifier does not replenish.Source: §A.4 · pp. 14–15
  • Race-free backend writes require conditional-update or transaction support, and revocation cannot roll back a completed operation.The checks assume serialized access to the session grant ledger.Source: §A.4 · p. 15

A.5 CONSTRUCTING THE SPECIFICATION: A RETAIL CANCELLATION

  • The developer authors Λ from tool schemas, business policy, and state-transition semantics; its declarations specify mappings, requirements, and evidence retrieval.The graph engine interprets those declarations rather than generating policy or authority rules from the agent’s conversation.Source: §A.5 · pp. 15–16
  • For the Retail cancellation example, the projected refund is a consequence requiring separate user confirmation; missing order status prompts evidence retrieval, while prohibited status blocks cancellation.The specification also scopes authority to the order and permits one execution under the approved grant.Source: §A.5 · pp. 15–16

B.1 TASKS, MODELS, AND BASELINES

The evaluation uses Airline and Retail benchmark tasks, three API-accessed models, and four enforcement conditions. All methods run on the full task inventories, with one trial per task.

B.1 TASKS, MODELS, AND BASELINES

  • All methods are evaluated on 50 Airline and 114 Retail tasks, with one trial per task because the two-reviewer protocol is costly.Airline tasks cover bookings and itinerary changes; Retail tasks include cancellation, return, exchange, and account or order updates.Source: §B.1 · p. 16
  • The acting models are DeepSeek-V4-Flash, GPT-5.6-Terra, and Gemini-3.6-Flash, accessed through model APIs with specified reasoning settings.The user simulator is a separate DeepSeek-V4-Flash instance with disabled thinking.Source: §B.1 · p. 16
  • The comparison includes Raw without an execution gate, AgentSpec protected-write checks, ToolGuard’s policy-to-code enforcement, and Progent’s dynamic privilege-policy procedure.The baseline interfaces are adapted to the benchmark without changing each method’s enforcement principle.Source: §B.1 · p. 16

B.2 METRICS AND INDEPENDENT SAFETY REVIEW

The evaluation combines benchmark success checks with write- and task-level safety assessments. An independent review protocol labels executed protected writes, while the mediator separately requests missing context and binds confirmation to an exact action.

B.2 METRICS AND INDEPENDENT SAFETY REVIEW

  • Official task reward combines final-database-state matching with required-communication checks, and reaching the maximum step count yields zero reward.Natural-language assertions and additional LLM judging are not used for official reward in this evaluation.Source: §B.2 · p. 16
  • Action safety is write-level, trajectory safety is 1 − #U/N, and STS combines official success and safety within the same task.Blocked proposals and failed calls do not enter the executed-write denominator; AS is undefined when no writes are executed.Source: §B.2 · p. 17
  • Two GPT-5.6-Sol reviewers independently assess policy compliance and authorization adequacy for each executed protected write; disagreements go to a human adjudicator.A write is safe only when both criteria are positive; Figure 4 presents the review prompt and shared criteria.Source: §B.2 · p. 17, Figure 4 · p. 17

B.3 AGENT AND AUTHORIZATION INTERFACES

  • When a candidate lacks evidence or authorization, the agent inserts a local request; a context answer supplies information but does not itself authorize the action.If policy refutes the action, ACG blocks it; otherwise the interface presents the action and consequences requiring approval.Source: §B.3 · pp. 17–18
  • An exact confirmation approves one unchanged action for one execution; any changed action or consequence requires a new disclosure and approval.The mediator constructs the confirmation from the candidate and current observations; Figure 6 shows the two user-facing interactions.Source: §B.3 · p. 18, Figure 6 · p. 18

B.4 NATURAL ABLATIONS AND CLOSUREBENCH

The ablations vary how authorization is retained and repaired, invalidated, and confirmed, as well as how group authority is represented. The variants isolate these design choices while retaining the benchmark’s public dialogue and observations.

B.4 NATURAL ABLATIONS AND CLOSUREBENCH

  • The natural ablations use the full 50-task Airline inventory, official model APIs, and the main evaluation’s two-reviewer safety protocol.They use the decoding settings specified for the main evaluation.Source: §B.4 · p. 19
  • Check discards authorization between independent actions, Check + repair adds structured evidence or context repair, and Full ACG retains the session graph and grant ledger.All variants retain public dialogue and observations, so removing the session graph does not remove conversation history.Source: §B.4 · p. 19
  • The invalidation and repair comparison crosses all-authority versus affected-only invalidation with all-missing versus minimal-set repair.Full ACG uses affected-only invalidation and the minimal set; these choices change update or request scope, not the business rules an action must satisfy.Source: §B.4 · p. 19
  • The consequence-approval variant omits confirmation for a derived consequence such as a $152 forfeiture, while retaining confirmation of the exact booking and payment arguments.The comparison concerns approval of consequences not explicit in tool arguments; the variant retains the other stated checks and requirements.Source: §B.4 · p. 19
  • The individual-grants variant replaces the group-scope record with separate member grants while retaining batch confirmation and each member’s scope and allowance.The comparison tests how group authority is maintained, not whether the user can approve a batch in one response.Source: §B.4 · p. 19

B.5 CLOSUREBENCH CONSTRUCTION AND EVALUATION

The evaluation builds controlled authorization-change cases around recorded actions, then compares repair methods using fixed user responses and repair budgets. Two natural-task examples illustrate preserving an ineligible reservation and completing a valid multi-step change with separate approvals.

B.5 CLOSUREBENCH CONSTRUCTION AND EVALUATION

  • Cases vary across 2, 4, or 8 parallel branches, chain lengths of 1, 3, or 6, and eight authorization-change types.Changes include shared sources, multiple consequences, refusal, restored evidence, and false business conditions; some cases contain up to 48 successive updates.Source: §B.5 · p. 19
  • The benchmark spans 1,224 cases from 17 recorded proposed writes; Table 5 reports 936 cases built from thirteen actions.Four actions supply cases used to check the test setup, while original operations and arguments are retained.Source: §B.5 · pp. 19–20
  • ACG combines selective updates and minimal repair while retaining all approval checks, unlike comparison methods that reset authority, omit dependency checks, or skip consequence approvals.All methods receive the same initial state and change sequence; full repair asks for every missing requirement, including recoverable ones.Source: §B.5 · p. 20
  • Methods are tested with six repair budgets and predetermined evidence and approval responses, with outcomes scored for success, action safety, safe task success, and unsafe executions.Authorization checks run directly on the CPU without model-generated dialogue or an LLM judge.Source: §B.5 · p. 20

B.6 ILLUSTRATIVE CASES

  • The natural-task examples preserve a reservation when cancellation is ineligible and complete a valid multi-step change with separate approvals, yielding a $114 refund.The recorded comparison also shows the complete system’s policy interpretation and final action.Source: §B.6 · p. 21, Figure 7 · p. 21, Figure 8 · p. 22

Related papers

Loading 2609.32428v1…