PaperlayerView exact revision on arXiv

Source-linked AI summary

Certified Speculative Execution for Untrusted AI Agents

Chenyu Zhou, Qiliang Jiang, Shuning Wu, Xu Zhou

arXiv:2606.31023v1cs.CRcs.LG

TL;DR

Hard-constrained decision systems lack a way to use AI drafts without giving up solver-backed feasibility or speed. CGPA gates proposed prefixes through trusted checks and a value boundary; it reports zero applied violations, regret near the stepwise oracle, and a 2.96× speedup on deployment-scale unit commitment.

  • Problem

    Untrusted learned policies and LLMs lack feasibility guarantees, while delegating every step to a trusted solver sacrifices the speed of their drafts.

    Source: §1 · p. 1

  • Method

    CGPA verifies proposed transitions, gates safe prefixes with a trusted value boundary, and defers the remainder to the oracle under a per-segment regret certificate.

    Source: §1 · p. 1, §2.5 · p. 4

  • Results

    2.96× wall-clock speedup on deployment-scale unit commitment, with zero applied violations and regret within sampling noise of the stepwise oracle.

    Source: §1 · p. 2, §5 · p. 7

  • Takeaways & Limitations

    Accepted segments skip oracle solves, and throughput grows with proposal-source capability while guarantees remain unchanged.

    Source: §1 · p. 2, §5 · p. 7

    The bounded-boundary-error guarantee assumes error at accepted-segment endpoints is at most ϵ, audited empirically over the reachable endpoints.

    Source: §2.2 · p. 2

Abstract

from arXiv · show

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.

1 Introduction

Hard-constrained systems face a trade-off: AI drafts are cheap but lack feasibility guarantees, while trusted solvers are reliable but expensive when invoked at every step. CGPA separates untrusted proposal generation from trusted guarantees, accepting verified, value-gated prefixes and deferring the rest to the oracle.

1 Introduction

  • A frozen 12B-parameter LLM proposes constraint-violating battery actions in 98% of episodes, while trusted solvers certify feasibility but are expensive at every step.Directly executing learned or LLM drafts forfeits feasibility guarantees.Source: §1 · p. 1
  • Unlike speculative decoding, which checks token drafts against a probability distribution, control drafts require separate checks for hard feasibility and decision quality (Leviathan, Kalman, and Matias 2023; Chen et al. 2023).A constraint-safe prefix can still be economically poor.Source: §1 · p. 1
  • CGPA accepts the longest proposed action prefix that passes a trusted feasibility check and value guard, then defers the remainder to the oracle.Proposal sources can be rules, learned policies, or frozen LLMs.Source: §1 · p. 1
  • The contract’s three parts are structurally necessary: feasibility must be exact, excess cost must be budgeted per accepted segment, and the estimated boundary error must be calibrated.Removing any part collapses the contract onto a weaker baseline.Source: §1 · p. 1
  • The regret certificate charges value-boundary error once per accepted segment, not per step.Safety does not query the boundary error; learning it down reduces regret, while accepted segments skip oracle solves.Source: §1 · pp. 1–2
  • Learning the value boundary down shrinks regret three orders of magnitude, while deployment-scale unit commitment reaches a 2.96× wall-clock speedup.Each accepted segment skips oracle solves.Source: §1 · pp. 1–2

2 Certified Speculative Execution

CGPA separates untrusted action proposals from trusted feasibility, value, and fallback decisions. It accepts certified prefixes, defers when needed, and charges boundary error per accepted segment.

2.1 Problem Setup

  • The reference controller calls the trusted oracle at every step but applies only the first action of each receding-horizon solve; CGPA moves it off the per-step critical path.The setup uses finite-horizon control with non-negative stage costs and hard feasibility constraints.Source: §2.1 · p. 2

2.2 The Accept/Defer Contract

  • CGPA combines an untrusted K-action drafter, trusted verifier, value boundary, and oracle, accepting the longest safe prefix meeting its guard and deferring otherwise to verified repair.The proposal source may be arbitrary; the guarantees depend on the trusted components.Source: §2.2 · p. 2

2.3 Safety Holds for Any Proposal Source

  • Every applied transition is feasible for any proposal source when the trusted oracle and exact verifier are available, independently of value-boundary error.A non-conservative surrogate cannot replace the exact feasibility gate without making safety depend on its error.Source: §2.3 · pp. 2–3, §2.2 · p. 2

2.4 Regret Certificate

  • Boundary error is charged once per accepted segment, yielding an O(ϵ|A|) regret term rather than a charge for every interior step.Each segment-level charge amortizes over the oracle solves skipped when that segment spans multiple steps.Source: §2.4 · p. 3

2.5 Certificate-Aware Learning of the Value Boundary

  • A five-quantile MLP uses its median for the value guard and its spread to estimate boundary error; split-conformal calibration targets 80% and 90% coverage.Across domains, empirical coverage is 0.816–0.853 and 0.900–0.917; removing the spread penalty inflates EMS regret by 1.46× at matched call reduction.Source: §2.5 · pp. 3–4

3 Experiments

Across EMS, CityLearn, and unit commitment, the experiments vary the proposal source while keeping the certified contract fixed. CGPA combines zero applied violations with lower regret and, when oracle calls are costly, faster execution.

3.1 Setup

  • Experiments span battery EMS, CityLearn HVAC, and deployment-scale unit commitment, with the contract held fixed while proposal sources vary.EMS episodes generally use a 24-step horizon and prefix length K=4; the study varies the boundary, acceptance mechanism, proposal source, or fallback oracle in controlled frontier slices.Source: §3.1 · p. 4

3.2 The Contract Neutralizes Arbitrary Proposal Sources

  • Direct execution of adversarial drafters and larger Gemma models produced constraint violations in 98–100% of episodes, while CGPA admitted none and deferred unsafe transitions.Replacing the oracle with an end-to-end learner paid 0.503 mean regret, about 7× the same learner used as a CGPA proposal source; against a white-box adaptive adversary, CGPA deferred at every step, absorbing the attack as lost amortization rather than violations.Source: §3.2 · pp. 4–5

3.3 Learned Value Boundaries Lift the Risk–Cost Frontier

  • Certificate-aware conformal gating reduced mean regret to 0.0002, three orders below unguarded acceptance and within sampling noise of the stepwise oracle.Under calendar shift, learned proposals raised call reduction by +18.8pp, lowered mean regret by 0.055, and beat the stepwise oracle’s cost on 15 of 18 days; at fixed source and boundary, prefix acceptance reached 0.0081 mean regret versus 0.0227 for full-plan acceptance.Source: §3.3 · p. 5

3.4 One Contract, Six Heterogeneous LLM Proposal Sources

  • The same contract absorbed six frozen LLMs at zero applied violations: feasible but costly models cut regret 3.8–10.9× at 62–70% call reduction, while unsafe models’ transitions were rejected.Across a controlled source-quality sweep, call reduction rose from 24% to 90% at zero violations.Source: §3.4 · pp. 5–6

3.5 Deployment-Scale Wall-Clock Amortization

  • 2.96× per-episode mean speedup at 2.1% regret; frozen Qwen3-8B exceeded the hold drafter’s 1.79× aggregate amortization and trigger replanning’s 1.07×.It achieved 2.02× aggregate wall-clock speedup, and all 50 episodes were faster than fallback; the contract retained its zero-violation guarantee.Source: §3.5 · p. 6

4 Related Work

CGPA connects scalable oversight to sequential control with deterministic feasibility and an auditable per-segment regret price (Greenblatt et al. 2024; Burns et al. 2023; Irving, Christiano, and Amodei 2018). It adapts draft–verify–accept, learning-to-defer, conformal risk control, and safe-control ideas to certified control prefixes.

AI control and scalable oversight

  • CGPA gives the sequential-control instance of scalable oversight a deterministic feasibility guarantee and auditable per-segment regret price, rather than a monitored probability of subversion (Greenblatt et al. 2024; Burns et al. 2023; Irving, Christiano, and Amodei 2018).It separates a strong untrusted generator from a weaker trusted overseer, accepting through exact verification and a calibrated value certificate rather than a learned monitor.Source: §4 · pp. 6–7

Speculative decoding

  • CGPA changes speculative decoding’s verified object from a token distribution to hard transition safety and certified fallback-relative cost, and accepts deviations within a regret budget (Leviathan, Kalman, and Matias 2023; Chen et al. 2023; Cai et al. 2024; Li et al. 2024).Unlike lossless token acceptance or action-match execution, CGPA permits control deviations under hard feasibility.Source: §4 · p. 7

Selective prediction and learning to defer

  • CGPA makes control-prefix acceptance coverage, deferral abstention to a trusted expert, and the certificate a bound on the cost of coverage (Geifman and El-Yaniv 2017; Mozannar and Sontag 2020; Madras, Pitassi, and Zemel 2018).Unlike sequence-level token and span abstention (Rayan and Tewari 2025), it defers executed control prefixes under a hard-feasibility verifier and fallback-relative regret certificate.Source: §4 · p. 7

Conformal risk control

  • CGPA’s calibrated band controls per-segment excess cost, making the certificate’s error quantity measured rather than assumed (Vovk, Gammerman, and Shafer 2005; Angelopoulos and Bates 2023; Angelopoulos et al. 2024; Prinster et al. 2026).Source: §4 · p. 7

Safe control and safe AI execution

  • Unlike safety filters that correct one action per online solve or controllers that accelerate or repair the trusted controller, CGPA admits an arbitrary source and certifies a feasible prefix’s fallback-relative regret (Alshiekh et al. 2018; Wabersich and Zeilinger 2021; Leeman et al. 2023; Ames et al. 2017; Wagener, Boots, and Cheng 2021; Fulton and Platzer 2018).Safety-augmented neural MPC falls back on infeasibility (Hose et al. 2023); other lines accelerate or repair the trusted controller (Yu, Zikelic, and Henzinger 2025; Tabuada 2007; Gondhalekar and Imura 2010; Diehl et al. 2002; Amos et al. 2018; Bertsekas, Tsitsiklis, and Wu 1997).Source: §4 · p. 7

5 Conclusion

CGPA lets adversarial drafters and six frozen LLMs operate with zero applied violations, regret within sampling noise of the stepwise oracle, and a 2.96× deployment-scale unit-commitment speedup. The appendix also reports a certificate-aware boundary loss sweep and a notation table.

5 Conclusion

  • Zero applied violations, regret within sampling noise of the stepwise oracle, and a 2.96× wall-clock speedup on deployment-scale unit commitment summarize CGPA’s results with adversarial drafters and six frozen LLMs.The conclusion describes the resulting execution layer as safe, low-regret, and oracle-amortizing, with throughput growing with untrusted-source capability while guarantees remain unchanged.Source: §5 · p. 7

A Notation

  • Table 4 collects symbols used throughout the main paper and appendix.Source: A Notation · p. 9

B Certificate-Aware Loss Sweep

C Conformal Calibration

The appendix reports conformal calibration, tolerance and proposal-source sweeps, boundary and acceptance comparisons, a real-calendar evaluation, and unit-commitment timing results. Across the reported settings, CGPA maintains zero applied violations while trading accepted-prefix amortization against regret.

C Conformal Calibration

  • At this calibration size, both domains meet their 80% and 90% targets using seed-disjoint calibration and test sets of 408 fallback-reachable rollout-state visits per domain.Source: C Conformal Calibration · p. 9

D Tolerance Frontier

  • Increasing τ selects longer accepted prefixes and higher call reduction, with zero applied violations throughout the reported sweep.Source: D Tolerance Frontier · p. 9

E Certified Execution over Untrusted Proposal Sources

  • Three to four orders of magnitude lower regret and zero applied violations under CGPA contrast with near-universal direct-execution violations by adversarial drafters and Gemma-4-12B and Gemma-4-E4B.The worst adversarial source reaches the oracle’s own cost under CGPA.Source: E Certified Execution over Untrusted… · p. 9

F EMS Value-Boundary Frontier

  • 0.0002 mean regret at a 95% CI of [−0.005, 0.006] places the conformally calibrated band gate within sampling noise of the stepwise oracle, three orders of magnitude below unguarded acceptance.The certificate-aware learned guard reaches 0.0063 mean regret at 60.4% call reduction, from 0.4450 for unguarded prefix acceptance; all have zero applied violations.Source: F EMS Value-Boundary Frontier · p. 9

G Full-Plan Neural MPC Comparison

  • 2.8× lower mean regret, from 0.0227 to 0.0081, at 86.6% call reduction distinguishes CGPA prefix acceptance from full-plan acceptance, with zero violations throughout.The comparison holds the imitation network fixed and varies the acceptance mechanism; higher τ trades regret for amortization.Source: G Full-Plan Neural MPC Comparison · p. 9

H CityLearn Real-Calendar Shift

I Oracle-Cost Amortization Sweep

  • Increasing per-call oracle cost demonstrates the structural advantage of certified multi-step acceptance over controllers that still call the oracle every step.The event-triggered controller’s plan uses per-step trusted-oracle calls, so its target-oracle call count is unreduced.Source: I Oracle-Cost Amortization Sweep · p. 9

J UC Per-Episode Speedup

  • 2.96× mean per-episode speedup, with a minimum of 1.51×, is reported for Qwen3-8B CGPA across 50 UC episodes, all with zero applied violations.The total-wall ratio is 2.02×.Source: J UC Per-Episode Speedup · p. 9

K Proposal Quality and Matched-τ Throughput

Proposal-prefix quality, rather than parameter count, tracks CGPA throughput in the reported comparisons. The appendix also describes a second unit-commitment replication, certificate-audit accounting, and the shared frozen-LLM proposal protocol.

K Proposal Quality and Matched-τ Throughput

  • Spearman ρ=1.000 links accepted-prefix length and CGPA call reduction across six LLMs, while parameter count and call reduction have ρ=−0.058.The reported throughput predictor is proposed-prefix quality, not model size.Source: K Proposal Quality and Matched-τ… · p. 9
  • At every matched τ, the frozen LLM exceeds the deterministic heuristic on mean and total-wall speedup at zero violations.A controlled EMS quality sweep also reports call reduction rising from 24% to 90% and mean regret falling from 0.031 to 0.002, with zero applied violations throughout.Source: K Proposal Quality and Matched-τ… · pp. 9–10

L UC Second-Instance Replication

  • Every episode is faster than stepwise fallback in the second UC instance, where the trusted oracle accounts for 99.99% of online time.This instance has 100 generators and a 48-step horizon, with a hold-commitment drafter and a boundary trained on the instance.Source: L UC Second-Instance Replication · p. 10

M Certificate Audit Components

N LLM Proposal Protocol

  • The frozen LLMs share a prompt template, parser, and deterministic decoding settings while keeping the verifier and fallback contract unchanged across sources.EMS prompts request JSON lists of discrete battery actions; UC prompts request JSON lists of generator-toggle index sets.Source: N LLM Proposal Protocol · p. 10

O UC Timing Breakdown

The trusted MILP oracle dominates online decision time, while drafting, verification, and boundary inference together take at most 2.04% of it.

O UC Timing Breakdown

  • At most 2.04% of per-decision time goes to drafting, verification, and boundary inference; the trusted MILP oracle dominates online time.Warm-starting the MILP with the same proposal yields only 0.91× end-to-end speedup on the n=50 UC run set because it still solves at every step.Source: O UC Timing Breakdown · p. 10
  • Table 6 calibrates the value-boundary band on 408 calibration and 408 test states, with target miscoverage levels for 80% and 90% bands.The states are seed-disjoint.Source: Table 6 · p. 11
  • The EMS and CityLearn τ frontier reports median call reduction and regret over ten seeds, alongside mean prefix length.The battery-EMS table compares Direct execution with CGPA wrapping the same proposal source in an accept/defer contract.Source: Table 7 · p. 11, Table 8 · p. 11

P Verifier-Error Robustness

Under bounded noise in the verifier’s next-state estimate, CGPA maintains zero applied violations by deferring more rather than admitting corrupted prefixes.

P Verifier-Error Robustness

  • Across the full bounded-noise range, no corrupted prefix is admitted and applied violations remain zero on the true trajectory.The EMS sweep uses n=100 and τ=0.04; the verifier screens using a noisy next-state estimate while execution follows true dynamics.Source: P Verifier-Error Robustness · p. 11
  • As verifier noise grows, the system defers more, absorbing estimation error as reduced amortization rather than reduced safety.Applied violations are measured on the true trajectory.Source: P Verifier-Error Robustness · p. 11
  • The verifier-robustness sweep corrupts next-state estimates with bounded uniform noise scaled as a fraction of the state range.The trusted proposal and fallback setting remain the basis of the reported sweep.Source: P Verifier-Error Robustness · p. 11

Q White-Box Adaptive Adversary

White-box adversaries can eliminate CGPA’s amortization or spend its regret budget, but they do not produce applied constraint violations. Under calendar shift, the learned source has lower mean regret than the forecast source across the reported day–seed runs.

Q White-Box Adaptive Adversary

  • The adversarial test setup gives each white-box attacker full knowledge of the verifier, boundary, dynamics, stage cost, and fallback, but no control over the trusted core.One attacker maximizes true violation severity; the other maximizes the realized cost of accepted prefixes.Source: Q White-Box Adaptive Adversary · p. 11
  • The violation-maximizing adversary breaches constraints in every raw episode across EMS and UC, yet CGPA admits no violating prefixes and defers at every step.Call reduction falls to zero, leaving the trusted-oracle floor; the feasibility gate does not query the attacked value boundary.Source: Q White-Box Adaptive Adversary · p. 11
  • On UC, the cost-budgeted adversary has 0.014 mean regret and 98% call reduction, versus the hold heuristic’s 0.026 and 93%.Coverage is 1.0 and paired 95% confidence intervals exclude zero; an unbounded cost-maximizer exhausts the nominal envelope at zero violations.Source: Q White-Box Adaptive Adversary · p. 11
  • At matched tolerances on UC, the Qwen3-8B drafter has higher total-wall speedup than the hold drafter in every comparison.The table caption reports n=50 per row and zero violations throughout.Source: Table 13 · p. 12
  • Across attack strengths, applied violations stay at zero; an adversary instead trades reduced amortization or paid regret against cost.A cost-maximizing adversary with feasible proposals also produces zero applied violations.Source: Q White-Box Adaptive Adversary · pp. 11–12
  • A learned white-box attacker reaches 0.570 feasible unwrapped mean regret versus 0.439 for the forecast drafter, while CGPA holds applied violations at zero.Under the frozen contract, certificate coverage is 0.99, mean/p95 regret is 0.014/0.022, and call reduction is 33%.Source: Q White-Box Adaptive Adversary · p. 12

R Out-of-Distribution Day Expansion and Win Rate Against the Stepwise Oracle

  • On 18 held-out calendar-shifted days across five learned-drafter seeds, mean regret is −0.137 for the learned source and −0.082 for the forecast source.The reported comparison comprises 90 paired day–seed runs; the in-distribution learned-guard win rate is 0.50.Source: R Out-of-Distribution Day Expansion… · p. 12

S Full Proofs

The proofs derive regret bounds by decomposing accepted and repair segments and telescoping their value terms; the non-learned-boundary comparison contrasts learned queries with unguarded proposal execution.

S Full Proofs

  • For an accepted segment, the exact guard bounds its cost by the value decrease plus a tolerance term; repair segments add nonnegative slack, which is zero under same-horizon fallback.The proof sums segment inequalities and telescopes value terms against the stepwise fallback cost.Source: S Full Proofs · p. 13
  • With an approximate boundary, each accepted segment adds at most (2 + τmax)ϵ to the bound, while repair terms and telescoping remain unchanged.The boundary error contributes (2 + τmax)ϵ|A| over accepted segments.Source: S Full Proofs · p. 13
  • Split-conformal validity at each of at most T+1 boundary states and a union bound yield a joint guarantee of at least 1 −δ.The calibration quantile uses miscoverage δ/(T+1), with endpoint-specific bands in the forward regret bound.Source: S Full Proofs · p. 13

T Non-Learned Value Boundaries and Unguarded Shields

  • The EMS comparison holds the proposal source fixed and changes only the value boundary; the unguarded shield executes verified proposals at every draft length and pays their full regret.Its executed trajectories are identical across K ∈ {1, 2, 4, 8}; the learned boundary answers per-state queries in milliseconds without online construction.Source: T Non-Learned Value Boundaries and… · p. 13

U Conceptual Positioning

CGPA resembles speculative decoding in invocation pattern and safety filters in its trusted-runtime contract, but accepts verified multi-step control prefixes from arbitrary sources under a value-boundary gate.

U Conceptual Positioning

  • CGPA accepts a verified multi-step control prefix from an arbitrary source, gated by a value boundary.Table 24 positions this contract among neighboring lines of work.Source: U Conceptual Positioning · pp. 13, 15, Table 24 · p. 15
  • Unlike speculative decoding, which verifies a draft batch against a target model, CGPA commits a value-gated control prefix.The contrast concerns the accepted object: a token-prefix distribution versus a verified control prefix.Source: U Conceptual Positioning · pp. 13, 15
  • Unlike selective prediction and learning to defer, which use single-step abstention, CGPA accepts a value-gated multi-step executed prefix.Its trusted-runtime contract also includes exact safety and a per-segment regret certificate.Source: U Conceptual Positioning · p. 15
  • Predictive safety filters and control barrier functions correct unsafe or risky actions rather than committing a value-gated future prefix.CGPA instead combines exact safety with a cheap value gate and an auditable per-segment regret certificate.Source: U Conceptual Positioning · p. 15
  • Event-triggered control can serve as a fallback or verifier, but does not amortize accepted prefixes.Source: U Conceptual Positioning · p. 15
  • Move-blocking MPC and rollout methods reuse state error rather than making a prefix-cost-bounded multi-step commitment.CGPA shifts solver use to rejection or repair.Source: U Conceptual Positioning · p. 15

Related papers

Loading 2606.31023v1…