mlsanityData to 7 Oct 2026

Certified Speculative Execution for Untrusted AI Agents

arXiv 2606.31023 ↗First posted 30 Jun 2026cs.CR cs.LGcited by 1

On the map: LLM agents and tool use → Agent threats, guardrails and governance

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.

Key facts. Cited by 1 paper in the map (data through 7 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.

Builds on

20 of 31 references.

References · 20

  1. 2022Fast Inference from Transformers via Speculative Decodingcited by 1,615
  2. 2023Accelerating Large Language Model Decoding with Speculative Samplingcited by 975
  3. 2024Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Headscited by 821
  4. 2017Selective Classification for Deep Neural Networkscited by 799
  5. 2021A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantificationcited by 777
  6. 2016Distribution-Free Predictive Inference For Regressioncited by 657
  7. 2024EAGLE: Speculative Sampling Requires Rethinking Feature Uncertaintycited by 564
  8. 2018AI safety via debatecited by 384
  9. 2020Consistent Estimators for Learning to Defer to an Expertcited by 262
  10. 2016Control Barrier Function Based Quadratic Programs for Safety Critical Systemscited by 261
  11. 2017Predict Responsibly: Improving Fairness and Accuracy by Learning to Defercited by 228
  12. 2023AI Control: Improving Safety Despite Intentional Subversioncited by 207
8 more
  1. 2018Differentiable MPC for End-to-end Planning and Controlcited by 178
  2. 2018A predictive safety filter for learning-based control of constrained nonlinear dynamical systemscited by 91
  3. 2021Safe Reinforcement Learning Using Advantage-Based Interventioncited by 45
  4. 2025Speculative Actions: A Lossless Framework for Faster Agentic Systemscited by 20
  5. 2023Approximate non-linear model predictive control with safety-augmented neural networkscited by 9
  6. 2022Predictive safety filter using system level synthesiscited by 6
  7. 2025Learning to Partially Defer for Sequencescited by 4
  8. 2024Neural Control and Certificate Repair via Runtime Monitoringcited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026More Rejective, Not More Discriminative: The Unit of Verification in Pre-Execution LLM Oversightcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Engineering Reliable Commit Gates for Agentic AI: Cost-Aware Verification Portfolios under Common-Mode Data Failures
  2. 2026Trust Is Not a Score: Runtime Assurance Contracts for High-Risk AI Agents
  3. 2026Certified by Abstention: Distribution-Free Guarantees for Chain-of-Thought Verifiers at Small Calibration Budgets
  4. 2026Sovereign Assurance Boundary: Certificate-Bound Admission for Agentic Infrastructure
  5. 2026Beyond Uniform Token-Level Trust Region in LLM Reinforcement Learning
  6. 2026Finite-Sample Probabilistic Safety Certification for AI-Based Grid-Edge Coordination
  7. 2026CAGE: Certified Authorization under Typed-Return Uncertainty for Tool-Using Agents
  8. 2026Conformal Certification of Reasoning Trace Prefixes