Certified Process Verification: Trajectory-Level Risk Control for LLM Agents

Process verifiers make local decisions, but deployment failures can be compo- sitional: a trajectory is contaminated if any failure-relevant error is certified as safe. We study this mismatch between the decision unit (step) and the risk unit (trajectory). Certified Process Verification (CPV) preserves fine-grained step-level certify/flag decisions while calibrating the trajectory-level loss jointly induced by those decisions. For nonmonotone selective losses CPV uses Learn-then-Test (LTT), while monotone trajectory contamination can be calibrated with either LTT or conformal risk control (CRC), depending on the desired guaran- tee semantics. On AgentProcessBench (APB), simple trajectory-aware alterna- tives control contamination but are substantially more conservative: union-bound and independence-based length corrections certify 0.0% and 1.2% of steps, max- score trajectory aggregation certifies 6.3%, and CROP certifies 9.1%, whereas CPV LTT-HB certifies 14.6% at trajectory risk 0.051 ± 0.013 for a target of 0.1. An oracle-score decomposition raises CPV certification to 38.6%, show- ing that both finite-sample calibration and scorer quality limit efficiency. Across 120 matched independent synthetic calibration draws under the same trajectory-contamination loss, LTT-HB incurs 0/120 high-probability violations with mean risk 0.0360, while CRC attains mean risk 0.0862 under its expected-risk guaran- tee, consistent with the distinct semantics of the two procedures. Results across APB, Who&When, and DeltaBench characterize trajectory-safe process verifica- tion as a validity–utility problem in which fine-grained decisions and trajectory level risk must be jointly calibrated under a common deployment objective.