Technical Summary: Proper Scoring Rules for Agentic Uncertainty Quantification

Problem Statement

Language model agents increasingly operate through extended trajectories involving observation, reasoning, tool use, and plan revision. In these settings, uncertainty is not merely a property of the final answer but a dynamic signal evolving with the interaction history. While recent work has shifted toward generating trajectory-level uncertainty signals (e.g., stepwise calibration, propagated uncertainty), the evaluation of these signals remains flawed.

Existing evaluation metrics, such as AUROC, AUPRC, Trajectory Expected Calibration Error (T-ECE), and scalarized Trajectory Brier scores, conflate ranking usefulness with probabilistic truthfulness.

• Rank-based metrics (AUROC/AUPRC) measure discrimination but are invariant to monotone transformations of probabilities, failing to distinguish between well-calibrated probabilities and overconfident/underconfident distortions.
• Calibration metrics (T-ECE) measure binwise marginal calibration but are "resolution-blind," rewarding forecasts that are correct on average within bins even if they lack discriminative power within those bins.
• Scalarized proper scores (e.g., applying Brier loss to a collapsed trajectory summary) are strictly proper only for the collapsed scalar, not for the full prefix-conditioned probability trace.

The core problem is the lack of a strictly proper evaluator for the prefix-conditioned success-probability process ($q_t = P_\pi(Y=1 | H_t)$). Without such an evaluator, it is impossible to strictly elicit truthful probability traces from agents, which is critical for downstream interventions like deferral, reflection, or human handoff that depend on the probability scale rather than just rank.

Methodology

1. The Trajectory Proper Score (TPS)

The authors introduce the Trajectory Proper Score (TPS), a predictor-agnostic family of strictly proper scoring rules for trajectory-level uncertainty.

• Definition: TPS aggregates a strictly proper binary scoring rule ($S_{\alpha,\beta}$) over the trajectory steps, weighted by an evaluator-chosen schedule ($w_t$):
  $$TPS(F_{1:T}, Y) = \sum_{t=1}^{T} w_t S_{\alpha,\beta}(F_t, Y)$$
  where $F_t$ is the agent's reported probability of eventual success given history $H_t$, and $Y$ is the terminal outcome.
• Strict Propriety: The authors prove (Theorem 4.1) that if the underlying binary score is strictly proper and weights are positive, TPS is strictly proper for the full prefix-conditioned process. This means the expected score is uniquely maximized when the agent reports the true conditional probability $q_t$ at every step.
• Score Family: The method utilizes the beta-family of scores ($S_{\alpha,\beta}$), derived from the Schervish–Buja threshold-mixture construction. This family includes the log score (limiting case), the Brier score ($\alpha=\beta=1$), and allows for asymmetric cost shaping via parameters $\alpha$ and $\beta$.

2. Handling Censored Trajectories

In practical benchmarks, trajectories are often administratively censored (e.g., hitting a step budget) before the outcome $Y$ is observed. The paper extends TPS to these cases via conditional projection:

• Exact Reduced Score ($TPS^{cen,exact}$): By projecting the complete-data score onto the observable prefix, the authors derive an exact censored score that depends on the continuation-success probability $q_Z = P_\pi(Y=1 | H_Z)$ at the stopping point. This score is strictly proper for the observable prefix.
• Simple Censored Approximation ($TPS^{cen,simple}$): When $q_Z$ is unestimated, the authors propose a pessimistic operational approximation setting $q_Z \approx 0$. This effectively scores the censored prefix as if the failure branch occurred. The authors prove this is strictly proper for a pseudo-label target ($m_t = P_\pi(\Delta=1, Y=1 | H_t)$), which converges to the true target only if the missing success mass is zero.

3. Theoretical Limitations of Existing Metrics

The paper formally demonstrates (Theorems A and B) why common metrics fail to elicit the full trace:

• T-ECE is resolution-blind; a constant forecast equal to the bin average can achieve zero error even if it discards all within-bin variation.
• Scalarized Brier/Log Loss applied to aggregated traces (e.g., $\Phi_{last}, \Phi_{avg}, \Phi_{min}$) elicits only the collapsed scalar, not the trace. For aggregators like $\Phi_{avg}$ or $\Phi_{min}$, the truthful trace can be strictly suboptimal compared to a non-truthful trace that manipulates the aggregation to match the optimal scalar.

Key Results

1. Calibration-Invariance Gap

Experiments on Tau2-Bench reveal a significant divergence between rank-based and proper scoring metrics.

• Recalibration Effect: When verbal confidence signals were recalibrated using Platt scaling, the AUROC changed negligibly ($\Delta/SE \approx 0.3$), while the TPS (log endpoint) improved substantially ($\Delta/SE \approx 43$).
• Implication: Rank metrics failed to detect that the raw stream was severely miscalibrated (saturated near 0.9–1.0), whereas TPS correctly identified the probability-scale error. The recalibrated stream barely exceeded the base-rate reference in TPS, despite similar ranking performance.

2. Impact of Censoring

On WebShop, where 47% of trajectories were administratively censored (hitting step limits), the evaluation population changed significantly.

• Selection Bias: Complete-only evaluation discarded a structurally harder subset of trajectories (censored ones were 3x longer).
• Score Shift: Including censored trajectories via the simple censored approximation shifted the average TPS by +0.159 nats (95% CI: [+0.133, +0.188]) compared to complete-only evaluation.
• Predictor Sensitivity: The shift was positive for underconfident predictors but negative for overconfident ones (e.g., completion token probability), demonstrating that censoring-aware scoring alters the verdict based on the confidence regime.

3. Validation of Censored Extensions

• Artificial Censoring: On complete trajectories from StrategyQA, Tau2-Bench, and HotpotQA, the authors artificially censored outcomes. The closed-form decomposition of the censored score matched the directly computed difference to numerical precision, validating the theoretical derivation.
• Monte Carlo Audit: On HotpotQA, the authors estimated $q_Z$ via Monte Carlo rollouts. The exact reduced score differed materially from the simple $q_Z \approx 0$ approximation, confirming that the choice of $q_Z$ estimation impacts the final score.

Significance and Claims

The paper claims to establish a foundational framework for strictly proper evaluation of agentic uncertainty. Its significance lies in:

1. Separating Elicitation from Ranking: It demonstrates that ranking metrics (AUROC) and calibration metrics (ECE) do not strictly elicit the full probability trace required for probabilistic decision-making.
2. Operational Necessity of Proper Scores: The empirical results show that probability recalibration can drastically change the TPS verdict while leaving rank metrics unchanged. This implies that for applications relying on probability thresholds (deferral, handoff), current evaluation practices may be misleading.
3. Handling Real-World Constraints: By extending proper scoring to administratively censored trajectories, the paper provides a method to evaluate agents on benchmarks with step budgets without discarding difficult, truncated cases or mislabeling them.

The authors maintain a modest scope, noting that the framework assumes non-informative administrative censoring and targets binary terminal outcomes. They explicitly state that the work focuses on the evaluator-side propriety of uncertainty signals, distinct from the predictor-side methods used to generate them. The TPS framework is agnostic to the source of the signal (verbal confidence, token probabilities, etc.) as long as it is expressed as a prefix-conditioned success probability.