Technical Summary: CAGE (Certified Authorization under Typed-Return Uncertainty)

1. Problem Statement

The paper addresses a critical vulnerability in Tool-Using Large Language Model (LLM) Agents. While deployed agent harnesses increasingly employ runtime permission gates to authorize tool calls, these gates typically evaluate the observed tool return and the proposed action at a single point in time. They fail to account for residual binding uncertainty: the possibility that the validated record observed by the agent ($\tilde{z}$) differs from the "correctly bound" return ($z^\star$) due to minor assembly faults (e.g., stale provenance tags, schema mismatches, or race conditions) and bounded numerical drift.

The core problem is that an action may appear safe under the observed record and even under separate checks for discrete (categorical) and continuous (numerical) perturbations, yet become unsafe when these perturbations occur jointly. The authors term this the joint-gap attack. Existing defenses, which often focus on sanitizing untrusted text or evaluating pointwise actions, leave the decision boundary unprotected against these specific semantic uncertainties.

2. Methodology: CAGE

The authors propose CAGE (Certified Authorization Gate for Execution), a runtime monitor that shifts the object of authorization from the observed point $(\tilde{z}, a)$ to a joint neighborhood $B_{d,\epsilon}(\tilde{z})$. An action $a$ is authorized only if it remains safe for every plausible correctly bound return within this neighborhood.

The Joint Neighborhood

The neighborhood is defined by two budgets:

• Discrete Budget ($d$): Allows for up to $d$ admissible binding faults (e.g., a single provenance swap or policy pack confusion).
• Continuous Budget ($\epsilon$): Allows for bounded $\ell_2$ drift in numerical fields (e.g., risk scores, amounts) after standard validation.

The Non-Composition Theorem

A central theoretical contribution is the proof that separate certification of channels does not compose.

• Theorem 1: A safety predicate may be safe under all continuous perturbations of the original discrete state and safe under all discrete swaps of the original continuous value, yet unsafe under a combined discrete swap and continuous shift.
• Implication: Marginal certificates (checking text and numbers separately) are unsound. The defense must certify the Cartesian product of the discrete and continuous perturbations.

The CAGE Algorithm

CAGE operates by exact enumeration of the discrete neighborhood followed by sound certification of the continuous branch:

1. Enumerate: Compute the finite set of discrete neighbors $N_d(s) = \{s' : D_{disc}(s, s') \le d\}$.
2. Certify Branches: For each discrete neighbor $s'$, certify that the action is safe for all continuous perturbations $x'$ within the $\epsilon$-ball.
3. Decision: Allow the action only if every branch passes its continuous certification test.

The Assumption Ladder (Backends)

CAGE supports different backends depending on the nature of the policy (executable vs. learned):

• CAGE-Exact (Rung 1): Used when the policy is an executable predicate (e.g., affine constraints in Rego or decision tables). It performs exact mathematical verification of constraints over the $\epsilon$-ball. This is policy-certified.
• CAGE-Lip (Rung 2): Used for learned gates (implicit policies). It employs a 1-Lipschitz neural network architecture. It certifies the gate's decision based on the Lipschitz margin ($h_\theta > L_{cert}\epsilon$). This is gate-certified and sound under a measured gate-policy fidelity assumption.
• CAGE-RS (Rung 3): Used for black-box gates. It applies Randomized Smoothing to provide probabilistic guarantees over the continuous ball. This is also gate-certified.

3. Key Contributions

1. Formalization of Robust Authorization: The paper formalizes post-tool-return authorization as a decision under bounded semantic uncertainty, proving that return-dependent safety requires inspecting the realized return (Proposition 1).
2. Non-Composition Proof: The authors prove that marginal certificates for categorical and numerical channels do not imply safety over their joint product, identifying the existence of "joint-gap witnesses" (Theorem 1).
3. Certified Monitor with Assumption Ladder: CAGE provides a unified framework that enumerates the discrete space exactly and certifies the continuous space using a hierarchy of backends (Exact, Lipschitz, Smoothing), ensuring a soundness floor even for learned gates.
4. Measured Safety Case: The work provides a rigorous safety case calibrated on injected faults, demonstrating that CAGE removes in-budget false allows while retaining useful autonomy.

4. Experimental Results

The evaluation spans synthetic settings, policy-as-code (Open Policy Agent, GoRules), regulatory frameworks (PSD2/AML), and real transaction data (IEEE-CIS).

• Existence of Joint-Gap Witnesses: The study confirms that joint-gap witnesses exist in every setting, occurring at natural frequencies of 3.5% to 12%.
• Soundness: Across all settings, CAGE achieves a Certified False Allow (CFA) rate of 0. In contrast, pointwise gates and marginal composition baselines admit these unsafe witnesses at high rates (often 100% of the witness set).
• Autonomy: Despite the strict safety guarantees, CAGE retains significant autonomy:
  • CAGE-Exact autonomously clears 22–34% of robust-safe decisions in policy-as-code settings and 57% in natural traffic.
  • Learned backends (Lip/RS) retain 6.5–37% autonomy depending on the strictness of the operating point.
• End-to-End Validation: In live system tests (Kubernetes, MCP write paths, AML engines), CAGE successfully blocked unsafe side effects (e.g., unauthorized deployments, over-quota writes) that were admitted by un-gated or pointwise-gated agents.
• Adaptive Attacks: CAGE remains sound against adaptive adversaries who know the policy and budget, whereas learned point gates suffer high false-allow rates (up to 98% in some synthetic attacks).

5. Significance and Claims

The paper claims that CAGE provides a calibrated authorization mechanism for decisions where safety depends on uncertain typed returns. Its significance lies in:

• Closing the Logical Gap: It is the first system to formally certify the joint neighborhood of typed returns, addressing a vulnerability that pointwise and marginal defenses miss.
• Practical Deployability: By offering an "assumption ladder," it bridges the gap between theoretically perfect executable policies and practical learned gates, providing formal guarantees even in the latter case under explicit fidelity conditions.
• Operational Realism: The work explicitly separates the formal guarantee from operational preconditions (e.g., freshness of data, integrity of the constructor). It quantifies the "residual risk" when these preconditions fail (e.g., if data staleness exceeds the declared budget), rather than claiming absolute immunity.

The authors are modest about external validity claims: they demonstrate the existence, realizability, and mechanism of joint-gap attacks in deployed-style pipelines but do not claim to have measured the prevalence of these specific faults in all real-world agentic systems. They conclude that CAGE is a necessary runtime control wherever typed-return uncertainty can be measured and enforced.