Efficient and Reliable Probabilistic Verification for AI Agents

The researchers propose an efficient and reliable probabilistic verification framework for enforcing safety policies for AI agents operating in complex digital environments. Existing runtime monitoring methods based on formal languages such as Datalog support only deterministic policies, whereas in practice components such as declassifiers or personally identifiable information (PII) detectors carry some failure probability on each invocation and are difficult to satisfy the independence assumptions required by prior probabilistic reasoning work. The new framework is based on distributionally robust optimization and can still compute a reliable upper bound on the policy violation probability when correlations may exist among predicates. The authors state that on standard benchmarks for terminal and tool-calling agents, the method outperforms existing techniques, improving the safety-utility trade-off while guaranteeing a strict upper bound on violation probability.