Certified Speculative Execution for Untrusted AI Agents

• URL: http://arxiv.org/abs/2606.31023v1
• Date: Tue, 30 Jun 2026 01:45:56 GMT
• Title: Certified Speculative Execution for Untrusted AI Agents
• Abstract summary: Certificate-Gated Prefix Acceptance (CGPA) is a speculative-execution contract for untrusted AI agents.<n>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 (1.79x) and a safe receding-horizon baseline (1.07x)
• Score: 5.864346468963738
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Repeated-Game Security for Restaking-Based Verifiable Inference [2.9661360665913574]
  This paper shows that a one-round slashing condition can overstate security when inference is supplied repeatedly under the same stake.<n>We propose a deployable mechanism combining history-dependent challenges, reputation-weighted slashing, and stake vesting.
  arXiv  Detail & Related papers  (2026-08-10T03:03:56Z)
• Survive or Collapse: The Asymmetric Roles of Data Gating and Reward Grounding in Self-Play RL [76.45061154544568]
  Self-play reinforcement learning trains language models on their own generated tasks, co-evolving a proposer and solver without human labels.<n>Recent systems report strong reasoning gains, but collapse and instability are widely observed and poorly understood.<n>We argue instead that self-play stability is governed by two distinct levers: a data-level gate that decides which proposer-generated tasks enter the training pool, and the reward signal that updates the policy on tasks already admitted.
  arXiv  Detail & Related papers  (2026-05-21T09:19:23Z)
• AITH: A Post-Quantum Continuous Delegation Protocol for Human-AI Trust Establishment [9.198471344145092]
  We present AITH (AI Trust Handshake), a post-quantum continuous delegation protocol.<n>AITH introduces: (1) a Continuous Delegation Certificate signed once with ML-DSA-87 (FIPS 204, NIST Level 5), replacing per-operation signing with sub-microsecond boundary checks at 4.7M ops/sec; (2) a six-check Boundary Engine enforcing hard constraints, rate limits, and escalation triggers with zero cryptographic overhead on the critical path; and (3) a push-based Revocation Protocol propagating invalidation within one second.
  arXiv  Detail & Related papers  (2026-04-09T01:30:28Z)
• SELFDOUBT: Uncertainty Quantification for Reasoning LLMs via the Hedge-to-Verify Ratio [0.038379177968040606]
  We propose SELFDOUBT, a single-pass uncertainty framework for reasoning language models.<n>Our key signal, the Hedge-to-Verify Ratio (HVR), detects whether a reasoning trace contains uncertainty markers and, if so, whether they are offset by explicit selfchecking behavior.<n> SELFDOUBT operates on a single observed reasoning trajectory, making it suitable for latency- and cost-constrained deployment over any proprietary API.
  arXiv  Detail & Related papers  (2026-04-07T19:19:29Z)
• Improving Search Agent with One Line of Code [68.58667107354253]
  Tool-based Agentic Reinforcement Learning (TARL) has emerged as a promising paradigm for training search agents to interact with external tools.<n>We propose textbfSearch textbfAgent textbfPolicy textbfOptimization (textbfSAPO), which stabilizes training via a conditional token-level KL constraint.
  arXiv  Detail & Related papers  (2026-03-10T04:07:39Z)
• Information Fidelity in Tool-Using LLM Agents: A Martingale Analysis of the Model Context Protocol [69.11739400975445]
  We introduce the first theoretical framework for analyzing error accumulation in Model Context Protocol (MCP) agents.<n>We show that cumulative distortion exhibits linear growth and high-probability deviations bounded by $O(sqrtT)$.<n>Key findings include: semantic weighting reduces distortion by 80%, and periodic re-grounding approximately every 9 steps suffices for error control.
  arXiv  Detail & Related papers  (2026-02-10T21:08:53Z)
• Agentic Uncertainty Quantification [76.94013626702183]
  We propose a unified Dual-Process Agentic UQ (AUQ) framework that transforms verbalized uncertainty into active, bi-directional control signals.<n>Our architecture comprises two complementary mechanisms: System 1 (Uncertainty-Aware Memory, UAM), which implicitly propagates verbalized confidence and semantic explanations to prevent blind decision-making; and System 2 (Uncertainty-Aware Reflection, UAR), which utilizes these explanations as rational cues to trigger targeted inference-time resolution only when necessary.
  arXiv  Detail & Related papers  (2026-01-22T07:16:26Z)
• Trajectory Guard -- A Lightweight, Sequence-Aware Model for Real-Time Anomaly Detection in Agentic AI [0.0]
  Trajectory Guard is a Siamese Recurrent Autoencoder with a hybrid loss function that jointly learns task-trajectory alignment via contrastive learning and sequential validity via reconstruction.<n>At 32 ms latency, our approach runs 17$-27times$ faster than LLM Judge baselines, enabling real-time safety verification in production deployments.
  arXiv  Detail & Related papers  (2026-01-02T00:27:11Z)
• LEC: Linear Expectation Constraints for False-Discovery Control in Selective Prediction and Routing Systems [95.35293543918762]
  Large language models (LLMs) often generate unreliable answers, while uncertainty methods fail to fully distinguish correct from incorrect predictions.<n>We address this issue through the lens of false discovery rate (FDR) control, ensuring that among all accepted predictions, the proportion of errors does not exceed a target risk level.<n>We propose LEC, which reinterprets selective prediction as a constrained decision problem by enforcing a Linear Expectation Constraint.
  arXiv  Detail & Related papers  (2025-12-01T11:27:09Z)
• Safe and Compliant Cross-Market Trade Execution via Constrained RL and Zero-Knowledge Audits [0.5586191108738564]
  We present a cross-market algorithmic trading system that balances execution quality with rigorous compliance enforcement.<n>The architecture comprises a high-level planner, a reinforcement learning execution agent, and an independent compliance agent.<n>We report effects at the 95% confidence level using paired t-tests and examine tail risk via CVaR.
  arXiv  Detail & Related papers  (2025-10-06T15:52:12Z)
• Core Safety Values for Provably Corrigible Agents [2.6451153531057985]
  We introduce the first implementable framework for corrigibility, with provable guarantees in multi-step, partially observed environments.<n>Our framework replaces a single reward with five *structurally separate* utility heads.<n>For open-ended settings where adversaries can modify the agent, we prove that deciding whether an arbitrary post-hack agent will ever violate corrigibility is undecidable.
  arXiv  Detail & Related papers  (2025-07-28T16:19:25Z)
• Certified Robustness Under Bounded Levenshtein Distance [55.54271307451233]
  We propose the first method for computing the Lipschitz constant of convolutional classifiers with respect to the Levenshtein distance.<n>Our method, LipsLev, is able to obtain $38.80$% and $13.93$% verified accuracy at distance $1$ and $2$ respectively.
  arXiv  Detail & Related papers  (2025-01-23T13:58:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.