Efficient and Sound Probabilistic Verification for AI Agents

Researchers introduce a probabilistic verification framework for AI agents that enforces security policies when systems contain uncertainty or imperfect predictors. Using distributionally robust optimization, the approach computes sound upper bounds on policy violations without requiring independence assumptions, demonstrating improvements over existing methods for terminal and tool-calling agents.

This research addresses a critical gap in AI security: how to enforce formal policies when deployed systems contain probabilistic components. Real-world AI agents frequently rely on imperfect classifiers—such as PII detectors or content filters with inherent failure rates—yet existing formal verification methods assume deterministic behavior. The paper's innovation lies in abandoning unrealistic independence assumptions and instead using distributionally robust optimization to provide worst-case guarantees, ensuring security bounds hold regardless of how predicates correlate.

The problem emerges from the tension between practicality and rigor. As AI agents access external tools and process sensitive information, security policies must account for genuine uncertainty in classification, delegation decisions, and state transitions. Previous approaches either oversimplify by assuming independence or lack computational efficiency. This work bridges that gap by computing provable upper bounds on violation probabilities while maintaining acceptable utility metrics.

For the AI agent ecosystem, this framework enables more rigorous security auditing and compliance verification. Development teams building agent systems can now enforce formal policies with mathematical certainty about failure modes, even when underlying components are probabilistic. The demonstrated improvements on standard benchmarks suggest the approach scales practically.

The significance extends to regulated applications where AI agents handle sensitive data or make consequential decisions. Organizations face pressure to demonstrate not just that policies exist, but that they actually constrain behavior under realistic conditions. This work provides the technical foundation for that assurance. Future adoption may influence how AI systems undergo security certification and how developers reason about policy enforcement in production environments.

• →Introduces probabilistic verification framework eliminating unrealistic independence assumptions for AI agent security policies.
• →Uses distributionally robust optimization to compute provable upper bounds on policy violation probabilities.
• →Demonstrates improved security-utility trade-offs compared to prior methods on terminal and tool-calling agent benchmarks.
• →Enables formal security guarantees for AI systems with imperfect classifiers and probabilistic state transitions.
• →Addresses practical gap between formal verification and real-world AI deployments with uncertainty.