PaperlayerView exact revision on arXiv

Source-linked AI summary

VERA: Authority-Preserving Edge Revocation for Federated AI-Agent Workflows

Lifei Liu, Haoran Yu, Xiaochong Jiang

arXiv:2608.30091v1cs.AI

TL;DR

Agent runtimes need revocation semantics that identify exactly which authorities disappear when one delegation edge is withdrawn, without disabling independently authorized agents. VERA provides a signed, verifier-checkable edge-revocation contract and evaluates it on framework traces, where it exposes tree over-revocation and deployer-scoped under-revocation. The paper reports exact target proofs and baseline failures while validating the contract across controlled LangGraph workflows and portable artifacts.

  • Problem

    Existing agent revocation APIs resemble token or subtree invalidation and do not specify the exact authority loss from withdrawing one delegation in federated, multi-parent workflows.

  • Method

    VERA defines a signed-DAG revocation contract whose verifier checks the target reach(G) \ reach(G \ {e}) from signed delegation and revocation evidence.

  • Results

    500/500 target proofs and 500/500 authorized revocations were accepted, while 500/500 unauthorized signers and 260/260 omission attacks were rejected; tree and deployer-scoped baselines remained unsafe or incomplete.

  • Takeaways & Limitations

    The contract preserves alternate-parent authority while identifying descendants that lose all authority, providing a reference target for federated agent revocation APIs.

  • Takeaways & Limitations

    VERA assumes disjunctive authority and does not solve propagation freshness, transparency-log anchoring, Byzantine conflicting evidence, production-scale traces, or propagation.

Abstract

from arXiv · show

Modern agent frameworks compose planners, tool agents, remote services, and shared specialists into runtime delegation graphs, but their revocation APIs still resemble token or subtree invalidation. When one delegation is withdrawn, the runtime must know which agents lose authority while independently authorized agents keep working. We study this authority consistency problem and introduce VERA (Verifiable Edge Revocation for Agents), a verifier-checkable revocation contract and API emitted by agent-runtime adapters as signed evidence. Under disjunctive authority, revoking edge e invalidates exactly T_intent(e,G) = reach(G) \ reach(G \ {e}), the agents whose every authorizing root path used e. Used as a contract, this target exposes two runtime failures: tree cascades over-revoke shared agents, while deployer-scoped cascades under-revoke cross-domain descendants. In a LangGraph framework-replt cells repeated 20 times yield 500compiled-framework traces and 2,000 valid signed delegation decisions; 13/25 cells contain runtime multi-parsharing and 8/25 contain cross-deployer shies 500/500 target proofs, preserves all320 alternate-parent shared-agent cases that tree cascade revokes, and rejects unauthorized signers and omission attacks. Baseline replay over 1,9that holder/node and tree-style targetscannot express this behavior. We further validate schema portability on A2A, AutoGen, and CrewAI artifacts: nine traces, including five executable Cregned delegation events that pass schema and signature checks.

I. INTRODUCTION

The paper frames agent revocation as an authority-consistency problem in federated, multi-parent workflows. VERA makes the semantic target explicit so shared agents retain independent authority while cross-domain descendants lose withdrawn authority.

  • Multi-principal frameworks compose planners, tools, remote specialists, and shared agents across process and organizational boundaries, creating a need for authenticated and auditable delegated authority.
  • Tree cascades over-revoke shared agents with alternate parent paths, while deployer-scoped cascades under-revoke descendants in other domains.
  • Under disjunctive authority, revoking edge e invalidates exactly nodes whose every authorizing root path uses e.The target is T_intent(e,G) = reach(G) \ reach(G \ {e}).
  • VERA defines a signed-DAG contract and API that names delegation edges and lets relying parties verify authority-preserving targets without re-querying a central authorization service.
  • The prototype is a middleware contract for existing orchestrators and does not build Byzantine propagation, transparency logs, or a production platform.

A. From Chains to Multi-Parent DAGs

Agent delegation is modeled as a signed execution-evidence DAG because runtimes create multi-parent, cross-organizational relationships that credential-oriented mechanisms do not precisely revoke. The paper uses graph reachability to define authority loss while signatures make the result locally enforceable.

  • Agent runtimes create multi-parent relationships such as shared specialists and cross-deployer tasks, which are modeled as directed acyclic graphs.The multi-parent case is characterized by |parents(v)| > 1.
  • Adjacent mechanisms authenticate credentials, identities, or endpoints but do not define exact authority loss from revoking one edge in a multi-parent agent DAG.
  • In the illustrated over-revocation case, revoking A →C leaves C authorized through B →C, but a tree cascade revokes C and D.
  • A SIGNED-DAG contains agent nodes, directed delegation edges, deployer signatures, deployer labels, and public keys, with each edge representing parent-to-child authority delegation.
  • The execution-evidence DAG represents retries and recurring workflows as successive invocation events or epochs so each signed replay view remains acyclic.
  • Signatures authenticate graph evidence and let relying parties check authority and revocation locally without contacting a central authority.

B. Revocation Log

The revocation log records signed edge withdrawals over time, and path validity requires every edge on a root-to-node path to be authenticated and unrevoked. Disjunctive authority keeps a node active when at least one valid parent path survives.

  • The revocation log R contains edge identifiers paired with revocation times.
  • An edge is revoked at time t when the log contains the same edge with a revocation time no later than t.
  • R_t is the set of edges revoked by time t.
  • A root-to-node path is valid only when every edge is authenticated and unrevoked at the evaluation time.
  • Under disjunctive authority, independent parent delegations are alternatives, so a node remains active if one valid root-to-node path survives.

D. Threat Model and Trust Assumptions

VERA defines revocation over an authenticated, observed delegation graph and requires edge-specific, multi-parent-preserving, cross-domain-complete targets. Its verifier checks exactness locally for the observed revocation prefix, while propagation freshness and several trust-boundary threats remain outside scope.

  • Trust boundary: The guarantee is limited to the observed authenticated graph and does not solve propagation freshness, transparency-log anchoring, conflicting Byzantine-deployer evidence, or confidentiality beyond measured disclosure.Unobserved revocations remain a propagation-layer concern.
  • Contract requirements: VERA targets withdrawn delegation edges rather than whole credentials, principals, or subtrees, preserving alternate authorizing paths and covering cross-deployer descendants.These requirements correspond to edge-level targeting, multi-parent preservation, and cross-domain completeness.
  • Semantic target: Under disjunctive authority, Tintent(e, G) = reach(G) \ reach(G \ {e}) identifies nodes that lose every authorizing path when edge e is removed.The target is authority-preserving because descendants with alternate paths remain authorized.
  • Semantic target: The target can be computed in O(|V| + |E|) time using forward reachability on G and G \ {e}, with dominator structures supporting many queries.The computation serves as the correctness oracle for the signed target language.
  • Verifier model: A relying party can verify the target without an online authorization query when it authenticates edges and revocations and checks survivor paths, complete in-edge commitments, and the partition of reachable nodes.The proposition guarantees exactness for the authenticated graph view and observed revocation prefix.

C. Approximation Mechanisms

The paper compares exact edge targeting with coarser propagation mechanisms by the nodes each revocation request invalidates. Tree cascades can over-revoke shared descendants, while deployer-scoped cascades can under-revoke across administrative boundaries.

  • Exact target: The exact edge target computes Tintent(e, G) and serves as the reference for all baseline comparisons.It evaluates the authority lost specifically when one delegation edge is removed.
  • Tree cascade: Tree cascade revokes an edge’s child and all forward descendants, over-revoking DAG descendants that retain an alternate root path.The mechanism is exact on trees but not generally on multi-parent delegation graphs.
  • Deployer-scoped cascade: Deployer-scoped cascade traverses only nodes visible to the initiating deployer and can miss cross-domain descendants whose authority depends on the revoked edge.This models revocation administered within one administrative domain.
  • Coarse revocation: Node or deployer revocation invalidates all authority held by a node or domain, making these mechanisms suitable for compromise response but coarse for removing one delegation relationship.Their target is broader than an edge-specific withdrawal.
  • Segment revocation: Segment revocation targets content-addressed output segments rather than delegation authority and is therefore not evaluated as an edge-revocation substitute.It remains a distinct output-binding primitive.

D. Error Metrics

The paper distinguishes over-revocation from under-revocation and defines batch-aware semantic targets for evaluating revocation mechanisms. In multi-parent graphs, independently processing or unioning single-edge targets can fail to capture the true batch target.

  • Over-revocation removes legitimate agents, whereas under-revocation leaves agents active after they should lose authority.
  • Revocation APIs that process events independently are not generally correct for multi-parent DAGs.
  • T_intent(R, G) = reach(G) \ reach(G \ R) defines the nodes that become unreachable after removing a revoked edge set.
  • Removing both parent edges can disconnect a node even when removing either edge alone does not, so the batch target is not the union of single-edge targets.
  • A system can under-revoke simultaneous revocations by unioning independently computed single-edge targets, despite each single-edge target being exact.

V. MEASUREMENT METHODOLOGY

The measurement pipeline normalizes framework events into signed delegation DAGs and replays them under exact and baseline target languages. It combines agent-native traces with topology stress tests, batch-revocation tests, portability artifacts, and a static corpus.

  • Framework events are normalized into signed delegation DAGs and replayed under exact and baseline target languages.
  • The evaluation combines deterministic witnesses, random and scale-free DAGs, batch-revocation tests, executed LangGraph traces, portability artifacts, and a static LangGraph corpus.
  • E16 is the primary agent-native evidence, while mined and non-agent DAGs provide supporting topology evidence rather than direct revocation traffic.

A. RQ1: Witness Failures

Witnesses and stress tests show that topology and visibility assumptions produce distinct revocation failures, while batch revocation requires native edge-set semantics. The evaluation treats generated DAGs as stress tests rather than prevalence estimates.

  • Witness Failures: On the shared-subDAG witness, revoking A →C has an empty semantic target because B →C preserves reachability, while tree cascade revokes {C, D} and OverRev = 2.
  • Witness Failures: On the cross-deployer witness, revoking A →C targets {C, D}, while a deployer-d1-scoped cascade revokes only {C} and produces UnderRev = 1.
  • Witness Failures: The witnesses demonstrate deterministic consequences of topology and visibility assumptions rather than estimating failure frequency.
  • Scale-Graph Stress Tests: Tree cascade over-revokes on every sampled Barabasi–Albert revocation event, with mean collateral ranging from 5.9 nodes to 79.7 nodes across tested scales.
  • Batch Revocation: Across 39,991 sampled edge sets, unioning exact single-edge targets under-revoked the true batch target in a mean 21.25% of cases per graph.
  • Batch Revocation: In the mined LangGraph corpus, 8/33 alternate-parent pairs exhibit batch non-compositionality, supporting native batch target computation rather than unioning single-edge results.

D. RQ4: Agent-Framework Trace Replay

VERA replays executed framework traces as signed delegation DAGs against exact and baseline revocation targets, testing correctness, integrity, portability, and overhead. The replay shows that edge-target semantics preserve independently authorized agents while exposing failures in tree and deployer-scoped cascades.

  • Trace collection: 13/25 workflow cells contained runtime-observed multi-parent agents, while 8/25 contained cross-deployer sharing.These structures create the shared-authority and cross-domain cases needed to evaluate revocation targets.
  • Replay correctness: 500/500 target proofs and 500/500 authorized revocations were accepted, including 160/160 cross-deployer cases, while 500/500 unauthorized signers and 260/260 omission attacks were rejected.The replay therefore tested both target correctness and evidence integrity.
  • Replay correctness: 320/320 alternate-parent withdrawals preserved the shared agent under edge targeting, whereas tree cascade revoked it in all 320 cases.This directly tests whether revocation preserves authority through an independent parent.
  • Baseline comparison: Across 1,960 single-edge withdrawals, edge targets and complete-graph revalidation were exact in 1,960/1,960 cases, while tree and deployer-scoped baselines were exact for only 35.7% and 49.0%, respectively.Deployer-scoped cascade under-revoked all 880 cases whose semantic target crossed a deployer boundary.
  • Portability: A2A, AutoGen, and CrewAI artifacts emitted nine traces and 53/53 valid signed delegation events, while edge targets preserved 8/8 alternate-parent cases.The portability artifacts also showed deployer-scoped cascade missing 19/19 cross-domain target cases.
  • Supporting topology evidence: The mined LangGraph corpus supplied lower-bound structural evidence: among 18 acyclic graphs, tree cascade deviated on 54.9% of edges.Cyclic graphs were excluded from DAG replay and require epoch unrolling.
  • Overhead and implementation: Target computation remained linear at 0.17–2.15 ms through 2,000 nodes, while proof bundles were 64.7–69.0% of full signed bundles.The dominant cost was Ed25519 verification rather than graph traversal, and verification occurred when bundles or checkpoints were ingested.

VIII. DESIGN IMPLICATIONS

VERA's design implication is an API boundary for authority-preserving revocation rather than a replacement orchestrator. Framework adapters should expose edge identity, accepted-edge commitments, graph evidence, batch targets, and separate target correctness from delivery.

  • API boundary: Framework builders should name delegation edges, expose accepted-in-edge commitments, carry graph evidence, and support batch targets as S = reach(G) \ reach(G \ R).The design keeps revocation-target correctness distinct from propagation and delivery.

IX. LIMITATIONS

VERA fixes revocation targets under disjunctive authority, but its evidence is bounded by that policy and by controlled, non-production evaluation settings. Propagation, dynamic routing, and production-scale validation remain outside the paper’s scope.

  • The target applies only to disjunctive authority; all-parent, k-of-n, and path-scoped policies require different targets.
  • Evaluation uses real LangGraph machinery with controlled workloads, while cross-framework experiments test portability rather than prevalence.
  • The static corpus may miss dynamic routing, and production-scale traces remain open.
  • Propagation and delivery are orthogonal to VERA’s target semantics and remain outside the paper’s scope.
  • The paper positions its contribution as an executable revocation contract using a standard root-relative edge-dominance set, rather than a new dominator algorithm.
Loading 2608.30091v1…