Skip to content
conftrace_
2026 EMNLP EMNLP 2026

Per-Step Conformal Calibration Does Not Transfer to Agent Trajectories

AbstractConformal prediction supplies finite-sample coverage guarantees for individual language-model responses. We show that per-step conformal calibration need not preserve this guarantee along a multi-step agent trajectory: at a nominal miscoverage level of 10%, per-step split conformal delivers 83.5% trajectory score-threshold miscoverage on a fifteen-step web-navigation agent, and we prove lower bounds in three regimes of agent dynamics: i.i.d. resampling, memoryless covariate shift, and state-dependent Markov transitions. The i.i.d. regime alone accounts for the bulk of the empirical gap; the third regime, novel to this work, gives, to our knowledge, the first separation of the trajectory union event from i.i.d. resampling under marginal-stationary, non-trivial Markov dynamics, a setting in which prior marginal-drift analyses are silent. The separation persists under exact score stationarity and, for non-degenerate score laws, holds at any calibration sample size up to an O(T/sqrt(n)) finite-sample slack. A polynomial alpha-spending schedule restores end-to-end coverage to within 1.1 points of nominal across five agentic-NLP benchmarks and, by direct substitution, lifts process-reward-model step verifiers – which on their own miscover trajectories at 31.5-62.5% – to 9.6-10.6%, near the nominal target.

More from EMNLP 2026

All EMNLP 2026 papers →