# Certified Speculative Execution for Untrusted AI Agents

arXiv: https://arxiv.org/abs/2606.31023 · HTML: https://mlsanity.com/paper/2606.31023/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Agent threats, guardrails and governance, one of 16 directions in LLM agents and tool use.
- Builds on 20 of its 31 references that are in the map.
- First posted on arXiv 30 Jun 2026.

## Placed in

- LLM agents and tool use / [Agent threats, guardrails and governance](https://mlsanity.com/agents/agent-threats-guardrails-and-governance/)

## Builds on (most cited first, 20 of 20)

- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [AI safety via debate](https://mlsanity.com/paper/1805.00899/) (2018)
- [Control Barrier Function Based Quadratic Programs for Safety Critical Systems](https://mlsanity.com/paper/1609.06408/) (2016)
- [Consistent Estimators for Learning to Defer to an Expert](https://mlsanity.com/paper/2006.01862/) (2020)
- [Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer](https://mlsanity.com/paper/1711.06664/) (2017)
- [AI Control: Improving Safety Despite Intentional Subversion](https://mlsanity.com/paper/2312.06942/) (2023)
- [Differentiable MPC for End-to-end Planning and Control](https://mlsanity.com/paper/1810.13400/) (2018)
- [A predictive safety filter for learning-based control of constrained nonlinear dynamical systems](https://mlsanity.com/paper/1812.05506/) (2018)
- [Safe Reinforcement Learning Using Advantage-Based Intervention](https://mlsanity.com/paper/2106.09110/) (2021)
- [Speculative Actions: A Lossless Framework for Faster Agentic Systems](https://mlsanity.com/paper/2510.04371/) (2025)
- [Approximate non-linear model predictive control with safety-augmented neural networks](https://mlsanity.com/paper/2304.09575/) (2023)
- [Predictive safety filter using system level synthesis](https://mlsanity.com/paper/2212.02111/) (2022)
- [Learning to Partially Defer for Sequences](https://mlsanity.com/paper/2502.01459/) (2025)
- [Neural Control and Certificate Repair via Runtime Monitoring](https://mlsanity.com/paper/2412.12996/) (2024)

## Built on by (most cited first, 1 of 1)

- [More Rejective, Not More Discriminative: The Unit of Verification in Pre-Execution LLM Oversight](https://mlsanity.com/paper/2608.23941/) (2026)

## Abstract (arXiv)

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.