Technical Summary: Certified Speculative Execution for Untrusted AI Agents

1. Problem Statement

Modern AI systems, including learned policies and frozen Large Language Models (LLMs), can generate sequences of decisions (drafts) at low computational cost. However, deploying these "untrusted" agents in hard-constrained sequential decision systems (e.g., energy management, unit commitment) presents a fundamental dilemma:

• Direct Execution: Acting on AI drafts directly forfeits safety guarantees. For instance, a frozen 12B-parameter LLM proposed constraint-violating actions in 98% of episodes in battery management tasks.
• Stepwise Delegation: Invoking a trusted, expensive solver (e.g., LP/MILP optimizer) at every step ensures safety but forfeits the speed and efficiency AI offers, as the solver remains on the critical path.

Existing approaches, such as speculative decoding in LLMs, verify tokens against probability distributions but do not address hard feasibility constraints or decision quality (regret) in control settings. There is a need for a layer that utilizes untrusted AI drafts for speed while maintaining strict safety and auditable performance guarantees.

2. Methodology: Certificate-Gated Prefix Acceptance (CGPA)

The paper proposes Certificate-Gated Prefix Acceptance (CGPA), a certified speculative-execution contract designed to decouple safety, regret, and speed. The system consists of a thin trusted core and an untrusted proposal source.

2.1 System Architecture

The CGPA controller is a tuple $(D, \text{Verify}, \hat{V}, \pi_F)$:

1. Untrusted Proposal Source ($D$): Can be any rule-based, learned, or LLM-based agent. It proposes a length-$K$ action prefix $u_{0:K-1}$.
2. Trusted Verifier: Simulates the proposed prefix against the system dynamics and hard constraints. It rejects any transition that violates feasibility.
3. Trusted Value Boundary ($\hat{V}$): A lightweight, learned value function (e.g., a five-quantile MLP) that estimates the cost-to-go. It acts as a "value guard" to ensure the accepted prefix is not only safe but also economically viable.
4. Trusted Oracle ($\pi_F$): A fallback solver (e.g., MILP) that provides a safe repair action if the proposal is rejected.

2.2 The Accept/Defer Mechanism

At each state $s_t$, the system executes the following logic:

• The source $D$ proposes $K$ actions.
• The Verifier checks feasibility. If any step is unsafe, the prefix is truncated to the last safe state.
• The Value Guard selects the longest verified-safe prefix $k$ satisfying:
  $$g(s_t, u_{0:k-1}) + \hat{V}(s_{t+k}) \leq \hat{V}(s_t) + \tau |\hat{V}(s_t)|$$
  where $g$ is the realized prefix cost and $\tau$ is a tolerance parameter.
• Commitment: If $k > 0$, the system commits the entire $k$-step prefix. If $k=0$, it defers to the oracle for a single step.

2.3 Theoretical Guarantees

The paper establishes that CGPA provides two structural invariants regardless of the proposal source $D$:

1. Applied Safety (Proposition 1): Every executed transition is feasible. Safety depends only on the trusted verifier and oracle, not on the proposal source.
2. Regret Certificate (Certificate 2): The system bounds the excess cost (regret) relative to the stepwise oracle. The regret bound is:
   $$J_{CGPA} - J_F \leq \sum_{i \in A} \tau_i |V(s_i)| + (2 + \tau_{\max})\epsilon |A| + \sum_{j \in R} \rho_j$$
   Crucially, the boundary error $\epsilon$ is charged once per accepted segment, not per step. This allows the system to amortize the cost of the expensive oracle over multiple steps.

2.4 Conformal Calibration

To handle the uncertainty in the learned value boundary $\hat{V}$, the authors employ split-conformal calibration. They train a quantile-regression model to output a central band and tail levels. The error bound $\epsilon(s)$ is derived from the spread of these quantiles ($\hat{V}_{0.9} - \hat{V}_{0.1}$) and calibrated on held-out data. This ensures the regret certificate holds with high probability (e.g., 95% confidence) even under distribution shifts.

3. Key Contributions

1. A Certified Speculative Execution Contract: CGPA is the first framework to adapt speculative execution principles to hard-constrained control, separating the "intelligence" (untrusted source) from the "guarantees" (trusted core).
2. Structural Decoupling: The paper proves that safety and regret can be decoupled. Safety is owned by the verifier, while regret is managed by a learnable, calibrated value boundary.
3. Conformal Calibration for Control: The integration of conformal prediction into the value boundary allows for a measured, rather than assumed, error bound $\epsilon$, providing a forward-looking regret guarantee.
4. Robustness to Adversarial Sources: The framework is designed to handle arbitrary proposal sources, including adversarial agents and heterogeneous LLMs, without compromising safety.

4. Experimental Results

The authors evaluated CGPA across three domains: Battery Energy Management (EMS), CityLearn (HVAC), and Unit Commitment (UC).

4.1 Safety and Zero Violations

• Adversarial & LLM Sources: When tested against adversarial drafters and six heterogeneous frozen LLMs (including Gemma-4-12B, which violated constraints in 98% of direct rollouts), CGPA achieved zero applied violations.
• White-Box Adversaries: Even against white-box adaptive adversaries with full knowledge of the verifier and dynamics, CGPA maintained zero violations by deferring to the oracle, absorbing the attack as reduced amortization (lower call reduction) rather than safety breaches.

4.2 Regret Reduction

• Learned Boundaries: Using a conformally calibrated learned boundary reduced mean regret by three orders of magnitude compared to unguarded acceptance (e.g., from 0.445 to 0.0002 in EMS).
• Oracle Proximity: The mean regret of CGPA was within sampling noise of the stepwise oracle (95% CI spanning zero), effectively matching the performance of the expensive solver while skipping most calls.
• Distribution Shift: Under calendar shifts (CityLearn), a learned proposal source outperformed the stepwise oracle on 15 of 18 held-out days, demonstrating that the system can leverage superior untrusted sources to beat the baseline.

4.3 Speed and Amortization

• Wall-Clock Speedup: On a deployment-scale Unit Commitment instance (48-step horizon, MILP oracle), CGPA using a frozen Qwen3-8B LLM achieved a 2.96× per-episode wall-clock speedup at 2.1% regret.
• Comparison: This outperformed domain heuristics (1.79×) and safe receding-horizon baselines (1.07×).
• Scalability: The speedup scales with the cost of the oracle. As the per-call oracle cost increased, CGPA's speedup grew (up to 2.67×), whereas event-triggered and move-blocking controllers remained near 1.0×.

5. Significance and Claims

The paper claims that CGPA provides a generalizable, certified layer for deploying untrusted AI in safety-critical systems. Its significance lies in:

• Enabling Untrusted AI: It allows the use of powerful, heterogeneous, and potentially flawed AI models (including LLMs) without sacrificing hard safety guarantees.
• Performance without Compromise: It achieves speedups by skipping expensive solver calls while maintaining regret levels comparable to the optimal stepwise solver.
• Robustness: The guarantees are structural and do not depend on the quality of the proposal source; the system degrades gracefully (by calling the oracle more often) rather than failing catastrophically.
• Practical Deployment: The framework has been validated on real-world scale problems (Unit Commitment) and demonstrates that "the more capable the untrusted source, the faster the certified system," provided the safety core remains intact.

The authors emphasize that this is a certified approach where safety is never queried from the untrusted source, and regret is bounded by a measurable, conformally calibrated certificate.