pith. sign in

arxiv: 2606.31023 · v1 · pith:WGILQKMUnew · submitted 2026-06-30 · 💻 cs.CR · cs.LG

Certified Speculative Execution for Untrusted AI Agents

Chenyu Zhou , Qiliang Jiang , Shuning Wu , Xu Zhou This is my paper

Pith reviewed 2026-07-01 05:54 UTC · model grok-4.3

classification 💻 cs.CR cs.LG
keywords speculative executionconformal predictionconstrained optimizationAI safetyunit commitmentcertified decision makingLLM agents
0
0 comments X

The pith

A contract uses a trusted verifier and calibrated boundary to let untrusted AI proposals run on hard-constrained decisions while keeping exact safety and near-oracle regret.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents Certificate-Gated Prefix Acceptance as a contract that accepts the longest low-cost prefix from any proposal source as long as it stays inside a per-segment regret budget set by conformal calibration. A trusted verifier rejects every constraint violation exactly, and the solver handles only the remaining suffix. This structure is shown to force zero applied violations from sources that violate constraints in 98 percent of direct uses, including adversarial drafters and multiple frozen LLMs. On a unit-commitment problem the same contract converts an 8B LLM into a 2.96 times wall-clock speedup at 2.1 percent regret while the regret stays statistically indistinguishable from the stepwise oracle.

Core claim

CGPA closes the gap between trusted solvers and untrusted AI drafts by rejecting violating transitions exactly, gating the longest feasible prefix inside a conformally calibrated regret budget, and deferring the rest to the solver, so that safety, regret, and speed are decoupled by construction; the resulting system produces zero applied violations from every tested proposal source and reduces mean regret three orders of magnitude below unguarded acceptance while delivering up to 2.96 times per-episode speedup on deployment-scale instances.

What carries the argument

Certificate-Gated Prefix Acceptance (CGPA), a contract that pairs an exact trusted verifier for constraint violations with a conformally calibrated value boundary that accepts the longest low-cost prefix inside a per-segment regret budget and defers the suffix to the solver.

If this is right

  • Every untrusted source, including adversarial drafters and LLMs that violate constraints 98 percent of the time in direct rollout, produces zero applied violations under the contract.
  • A certificate-aware learned boundary drives mean regret three orders of magnitude below unguarded acceptance and statistically indistinguishable from the stepwise oracle.
  • Under calendar shift a learned proposal source overtakes the oracle on 15 of 18 held-out days.
  • On a deployment-scale unit-commitment instance the contract converts a frozen 8B LLM into a 2.96 times per-episode wall-clock speedup at 2.1 percent regret, exceeding both the domain heuristic and a safe receding-horizon baseline.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same contract structure could be applied to other hard-constrained sequential problems such as job-shop scheduling or power-grid control where fast but unreliable proposals are available.
  • If the conformal calibration is repeated periodically on recent data, the regret budget could adapt to slow distribution drift without changing the safety guarantee.
  • The decoupling of safety from source quality suggests that stronger proposal sources will automatically produce larger speedups at the same regret target.

Load-bearing premise

The conformal calibration of the value boundary produces a valid per-segment regret bound that continues to hold for the proposal distribution and constraint set present at deployment time.

What would settle it

A test set drawn from the same distribution used for conformal calibration on which the observed per-segment regret exceeds the calibrated bound would falsify the central claim.

Figures

Figures reproduced from arXiv: 2606.31023 by Chenyu Zhou, Qiliang Jiang, Shuning Wu, Xu Zhou.

Figure 1
Figure 1. Figure 1: The certified prefix-acceptance operator (Definition 1). An untrusted source drafts a [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Amortization is structural: counterfactually scal [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The manuscript introduces Certificate-Gated Prefix Acceptance (CGPA) as a certified speculative-execution contract for untrusted AI agents in hard-constrained sequential decision systems. A trusted verifier rejects constraint-violating transitions, a conformally calibrated value boundary gates the longest low-cost prefix within a per-segment regret budget, and the remainder defers to a solver. The contract is claimed to drive all untrusted sources (adversarial drafters and six heterogeneous frozen LLMs) to zero applied violations, reduce mean regret by three orders of magnitude to within sampling noise of the stepwise oracle, and deliver up to 2.96x wall-clock speedup on a deployment-scale unit-commitment instance while preserving the guarantees.

Significance. If the conformal calibration produces a valid per-segment regret bound under the actual deployment mixture of proposal sources, the work would provide a principled mechanism to safely accelerate constrained optimization with untrusted AI without forfeiting feasibility or regret control. The reported ability to turn high-violation LLMs into certified fast solvers and the outperformance under calendar shift would be notable for practical deployment.

major comments (2)
  1. [Abstract] Abstract: the central claim that the conformally calibrated value boundary produces a valid per-segment regret bound (driving regret 'within sampling noise of the oracle' and 'three orders of magnitude below unguarded acceptance') is load-bearing for the certified interpretation, yet the abstract supplies no information on whether the calibration set matches the heterogeneous test-time mixture (six LLMs with violation rates differing sharply, up to 98% for the 12B model, plus adversarial drafters) or satisfies the exchangeability assumption required for conformal prediction coverage to transfer.
  2. [Abstract] Abstract: the reported empirical outcomes (zero violations, 95% CI spanning zero, 2.1% regret at 2.96x speedup, learned source overtaking oracle on 15/18 held-out days) cannot be verified because the abstract provides no details on experimental protocol, calibration-set construction, data splits, exact conformal procedure, or statistical tests; this directly affects soundness of the numerical claims.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed comments on the abstract. The concerns about calibration-set construction and experimental transparency are well-taken; we will revise the abstract to include concise statements addressing both points without altering its length substantially.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the conformally calibrated value boundary produces a valid per-segment regret bound (driving regret 'within sampling noise of the oracle' and 'three orders of magnitude below unguarded acceptance') is load-bearing for the certified interpretation, yet the abstract supplies no information on whether the calibration set matches the heterogeneous test-time mixture (six LLMs with violation rates differing sharply, up to 98% for the 12B model, plus adversarial drafters) or satisfies the exchangeability assumption required for conformal prediction coverage to transfer.

    Authors: We agree the abstract should make this explicit. The calibration set is constructed from a held-out sample drawn under the identical mixture of the six LLMs and adversarial drafters used at test time, preserving exchangeability within each source and yielding the reported marginal coverage. We will add one sentence to the abstract stating that the conformal boundary is calibrated on a representative mixture matching the deployment distribution. revision: yes

  2. Referee: [Abstract] Abstract: the reported empirical outcomes (zero violations, 95% CI spanning zero, 2.1% regret at 2.96x speedup, learned source overtaking oracle on 15/18 held-out days) cannot be verified because the abstract provides no details on experimental protocol, calibration-set construction, data splits, exact conformal procedure, or statistical tests; this directly affects soundness of the numerical claims.

    Authors: The full protocol, splits, conformal procedure, and statistical tests appear in Sections 4–5 and the appendix. To improve standalone verifiability of the abstract, we will insert a brief clause noting the use of a held-out calibration set, calendar-shift evaluation on 18 days, and 95% CIs computed via bootstrap. We believe this addresses the concern while respecting abstract length constraints. revision: yes

Circularity Check

0 steps flagged

No circularity: conformal calibration is external standard method; regret results are empirical

full rationale

The paper's central mechanism (CGPA contract with conformally calibrated value boundary) relies on conformal prediction, a standard external statistical technique that supplies coverage guarantees under exchangeability assumptions independent of the present work. The reported regret reductions (three orders of magnitude, within sampling noise of oracle) are presented as measured outcomes on held-out data and deployment instances, not as quantities forced by the calibration procedure itself. No equations or steps reduce a claimed prediction to a fitted input by construction, nor does any load-bearing premise collapse to a self-citation chain. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The approach rests on a trusted verifier that correctly detects violations and on conformal calibration producing valid regret bounds; the regret budget is a tunable parameter whose value affects the speed-regret tradeoff.

free parameters (1)
  • per-segment regret budget
    Tunable allowance that determines how long a prefix may be accepted before deferring to the solver; its value is chosen to balance speed and cost.
axioms (1)
  • domain assumption A trusted verifier exists that exactly identifies all constraint-violating transitions
    Invoked in the description of the CGPA contract to guarantee that rejected transitions are never applied.
invented entities (1)
  • Certificate-Gated Prefix Acceptance (CGPA) no independent evidence
    purpose: To provide a certified speculative-execution contract that decouples safety, regret, and speed
    New mechanism introduced by the paper; no independent evidence supplied outside the described experiments.

pith-pipeline@v0.9.1-grok · 5822 in / 1565 out tokens · 30264 ms · 2026-07-01T05:54:15.115196+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 9 canonical work pages · 5 internal anchors

  1. [1]

    Proceedings of the 40th International Conference on Machine Learning , pages =

    Fast Inference from Transformers via Speculative Decoding , author =. Proceedings of the 40th International Conference on Machine Learning , pages =. 2023 , editor =

    2023

  2. [2]

    Accelerating Large Language Model Decoding with Speculative Sampling

    Accelerating Large Language Model Decoding with Speculative Sampling , author =. arXiv preprint arXiv:2302.01318 , year =

    work page internal anchor Pith review Pith/arXiv arXiv

  3. [3]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume =

    Safe Reinforcement Learning via Shielding , author =. Proceedings of the AAAI Conference on Artificial Intelligence , volume =. 2018 , doi =

    2018

  4. [4]

    IEEE Transactions on Automatic Control , volume =

    Event-Triggered Real-Time Scheduling of Stabilizing Control Tasks , author =. IEEE Transactions on Automatic Control , volume =. 2007 , doi =

    2007

  5. [5]

    Automatica , volume =

    Least-Restrictive Move-Blocking Model Predictive Control , author =. Automatica , volume =. 2010 , doi =

    2010

  6. [6]

    Automatica , volume =

    Optimal Move Blocking Strategies for Model Predictive Control , author =. Automatica , volume =. 2015 , doi =

    2015

  7. [7]

    Journal of Heuristics , volume =

    Rollout Algorithms for Combinatorial Optimization , author =. Journal of Heuristics , volume =. 1997 , doi =

    1997

  8. [8]

    Automatica , volume =

    A Predictive Safety Filter for Learning-Based Control of Constrained Nonlinear Dynamical Systems , author =. Automatica , volume =. 2021 , doi =

    2021

  9. [9]

    Proceedings of The 5th Annual Learning for Dynamics and Control Conference , pages =

    Predictive Safety Filter Using System Level Synthesis , author =. Proceedings of The 5th Annual Learning for Dynamics and Control Conference , pages =. 2023 , editor =

    2023

  10. [10]

    IEEE Transactions on Automatic Control , volume =

    Control Barrier Function Based Quadratic Programs for Safety Critical Systems , author =. IEEE Transactions on Automatic Control , volume =. 2017 , doi =

    2017

  11. [11]

    Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads

    Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads , author =. arXiv preprint arXiv:2401.10774 , year =

    work page internal anchor Pith review Pith/arXiv arXiv

  12. [12]

    EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty

    EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty , author =. arXiv preprint arXiv:2401.15077 , year =

    work page internal anchor Pith review Pith/arXiv arXiv

  13. [13]

    Safe Exploration in Continuous Action Spaces

    Safe Exploration in Continuous Action Spaces , author =. arXiv preprint arXiv:1801.08757 , year =

    work page internal anchor Pith review Pith/arXiv arXiv

  14. [14]

    Advances in Neural Information Processing Systems , volume =

    Safe Model-Based Reinforcement Learning with Stability Guarantees , author =. Advances in Neural Information Processing Systems , volume =. 2017 , url =

    2017

  15. [15]

    arXiv preprint arXiv:1807.06096 , year =

    Safe Reinforcement Learning via Probabilistic Shields , author =. arXiv preprint arXiv:1807.06096 , year =

    work page arXiv

  16. [16]

    Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems , pages =

    Shielding Atari Games with Bounded Prescience , author =. Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems , pages =. 2021 , publisher =

    2021

  17. [17]

    Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , year =

    A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning , author =. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics , year =

  18. [18]

    IEEE Transactions on Power Systems , volume =

    Zimmerman, Ray Daniel and Murillo-S. IEEE Transactions on Power Systems , volume =. 2011 , doi =

    2011

  19. [19]

    2012 , publisher =

    Individual Household Electric Power Consumption Data Set , author =. 2012 , publisher =

    2012

  20. [20]

    Proceedings of the 6th ACM International Conference on Systems for Energy-Efficient Buildings, Cities, and Transportation (BuildSys) , pages =

    V. Proceedings of the 6th ACM International Conference on Systems for Energy-Efficient Buildings, Cities, and Transportation (BuildSys) , pages =. 2019 , doi =

    2019

  21. [21]

    SIAM Journal on Control and Optimization , volume =

    Real-Time Iteration Scheme for Nonlinear Optimization in Optimal Feedback Control , author =. SIAM Journal on Control and Optimization , volume =. 2002 , doi =

    2002

  22. [22]

    Zico , booktitle =

    Amos, Brandon and Rodriguez, Ivan Dario Jimenez and Sacks, Jacob and Boots, Byron and Kolter, J. Zico , booktitle =. Differentiable. 2018 , url =

    2018

  23. [23]

    Advances in Neural Information Processing Systems , volume =

    Deep Reinforcement Learning at the Edge of the Statistical Precipice , author =. Advances in Neural Information Processing Systems , volume =

  24. [24]

    Proceedings of the AAAI Conference on Artificial Intelligence , year =

    Neural Control and Certificate Repair via Runtime Monitoring , author =. Proceedings of the AAAI Conference on Artificial Intelligence , year =

  25. [25]

    Econometrica , volume =

    Regression Quantiles , author =. Econometrica , volume =

  26. [26]

    Algorithmic Learning in a Random World , author =

  27. [27]

    Journal of the American Statistical Association , volume =

    Distribution-Free Predictive Inference for Regression , author =. Journal of the American Statistical Association , volume =

  28. [28]

    Journal of Open Research Software , volume =

    Brown, Tom and H. Journal of Open Research Software , volume =

  29. [29]

    International Conference on Machine Learning (ICML) , year =

    Safe Reinforcement Learning Using Advantage-Based Intervention , author =. International Conference on Machine Learning (ICML) , year =

  30. [30]

    , journal =

    Willems, Jan C. , journal =. Dissipative Dynamical Systems Part

  31. [31]

    International Conference on Machine Learning (ICML) , year =

    Consistent Estimators for Learning to Defer to an Expert , author =. International Conference on Machine Learning (ICML) , year =

  32. [32]

    Advances in Neural Information Processing Systems (NeurIPS) , year =

    Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer , author =. Advances in Neural Information Processing Systems (NeurIPS) , year =

  33. [33]

    Advances in Neural Information Processing Systems (NeurIPS) , year =

    Selective Classification for Deep Neural Networks , author =. Advances in Neural Information Processing Systems (NeurIPS) , year =

  34. [34]

    Foundations and Trends in Machine Learning , volume =

    A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification , author =. Foundations and Trends in Machine Learning , volume =

  35. [35]

    International Conference on Learning Representations (ICLR) , year =

    Conformal Risk Control , author =. International Conference on Learning Representations (ICLR) , year =

  36. [36]

    arXiv preprint arXiv:2304.09575 , year =

    Approximate Non-Linear Model Predictive Control with Safety-Augmented Neural Networks , author =. arXiv preprint arXiv:2304.09575 , year =

    work page arXiv

  37. [37]

    arXiv preprint arXiv:2502.01459 , year =

    Learning to Partially Defer for Sequences , author =. arXiv preprint arXiv:2502.01459 , year =

    work page arXiv

  38. [38]

    International Conference on Learning Representations (ICLR) , year =

    Speculative Actions: A Lossless Framework for Faster Agentic Systems , author =. International Conference on Learning Representations (ICLR) , year =

  39. [39]

    Proceedings of the AAAI Conference on Artificial Intelligence , year =

    Safe Reinforcement Learning via Formal Methods: Toward Safe Control Through Proof and Learning , author =. Proceedings of the AAAI Conference on Artificial Intelligence , year =

  40. [40]

    Conformal Policy Control

    Conformal Policy Control , author =. arXiv preprint arXiv:2603.02196 , year =

    work page internal anchor Pith review Pith/arXiv arXiv

  41. [41]

    The Annals of Statistics , volume =

    Conformal Prediction Beyond Exchangeability , author =. The Annals of Statistics , volume =

  42. [42]

    Greenblatt, Ryan and Shlegeris, Buck and Sachan, Kshitij and Roger, Fabien , booktitle =

  43. [43]

    Weak-to-strong generalization: Eliciting strong capabilities with weak supervision.arXiv preprint arXiv:2312.09390,

    Weak-to-Strong Generalization: Eliciting Strong Capabilities With Weak Supervision , author =. arXiv preprint arXiv:2312.09390 , year =

    work page arXiv

  44. [44]

    Irving, Geoffrey and Christiano, Paul and Amodei, Dario , journal =