{"ID":5438562,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-03T01:40:09.565152011Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31023","arxiv_id":"2606.31023","title":"Certified Speculative Execution for Untrusted AI Agents","abstract":"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.","short_abstract":"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. Cert...","url_abs":"https://arxiv.org/abs/2606.31023","url_pdf":"https://arxiv.org/pdf/2606.31023v1","authors":"[\"Chenyu Zhou\",\"Qiliang Jiang\",\"Shuning Wu\",\"Xu Zhou\"]","published":"2026-06-30T01:45:56Z","proceeding":"cs.CR","tasks":"[\"cs.CR\",\"cs.LG\"]","methods":"[\"Large Language Model\"]","has_code":false}