CAGE: Certified Authorization under Typed-Return Uncertainty for Tool-Using Agents
Blaise Delattre, Cong Wang, Yang Cao
- Digest date
- 2026-08-03
- Submitted
- 2026-07-31
- arXiv ID
- 2607.29190
Summary
CAGE certifies whether a tool-agent action stays authorized over a declared neighborhood of plausible correctly-bound tool returns (admissible binding faults plus bounded numerical drift), proving that certifying categorical and numerical channels separately fails to compose — safe-looking perturbations on each channel alone can jointly become unsafe. It provides exact certification when policy is executable and Lipschitz/randomized-smoothing certification otherwise.
Abstract
Tool-using LLM agents act on typed tool returns, records pairing provenance and categorical fields with numerical values. Runtime permission gates generally authorize the observed return and action, leaving the decision unprotected against small errors in how the return was bound to its source. We ask whether a candidate action stays authorized over a declared neighborhood of plausible correctly bound returns: one admissible binding fault plus bounded numerical drift. We prove that certifying the categorical and numerical channels separately does not compose: perturbations that are safe on each channel alone can jointly turn the same action unsafe. CAGE certifies this joint neighborhood directly, enumerating the discrete branches exactly and certifying the continuous perturbation within each branch. Across synthetic, policy-as-code, regulatory, and real-transaction settings, CAGE removes the in-budget false allows that accurate pointwise gates admit, while keeping a useful fraction of decisions autonomous. When the policy is executable, CAGE-Exact certifies the policy itself; otherwise CAGE-Lip and CAGE-RS certify a learned gate under an explicit, measured fidelity assumption.