Search papers, labs, and topics across Lattice.
This paper introduces Certificate-Gated Prefix Acceptance (CGPA), a novel framework that enables certified speculative execution for untrusted AI agents, allowing them to leverage the speed of learned policies while maintaining safety guarantees. By implementing a trusted verifier that rejects constraint-violating transitions and using a conformally calibrated value boundary, CGPA effectively decouples safety, regret, and execution speed. The results demonstrate that CGPA can reduce mean regret significantly while achieving a 2.96x speedup in deployment-scale scenarios compared to traditional methods, even with untrusted sources that typically violate constraints.
Untrusted AI agents can now operate at unprecedented speeds while maintaining rigorous safety guarantees, achieving a 2.96x speedup with only 2.1% regret.
Hard-constrained sequential decision systems have no certified way to spend the test-time compute of modern AI: executing the multi-step drafts of a learned policy or a frozen LLM forfeits the feasibility guarantee a trusted solver provides, while invoking the solver at every step forfeits the speed the AI offers. Certificate-Gated Prefix Acceptance (CGPA) closes this gap with a certified speculative-execution contract for untrusted AI agents: a trusted verifier rejects constraint-violating transitions exactly, a conformally calibrated value boundary gates the longest low-cost prefix within a per-segment regret budget, and the rest defers to the solver, so safety, regret, and speed decouple by construction. The contract drives every untrusted proposal source - adversarial drafters and six heterogeneous frozen LLMs (including a 12B model that violates constraints in 98% of direct rollouts) - to zero applied violations; a certificate-aware learned boundary, conformally calibrated, drives mean regret three orders of magnitude below unguarded acceptance, to within sampling noise of the stepwise oracle (95% CI spanning zero), and under calendar shift a learned proposal source overtakes it on 15 of 18 held-out days. On a deployment-scale unit-commitment instance it turns a frozen 8B LLM into a 2.96x per-episode wall-clock speedup at 2.1% regret, outpacing the domain heuristic (1.79x) and a safe receding-horizon baseline (1.07x): the more capable the untrusted source, the faster the certified system, at guarantees that never change.
NUS