Online Conformal Prediction Beyond Feedback

Problem Formulation: Online Conformal Prediction Beyond Feedback

Uncertainty quantification is critical for deploying machine learning in safety-critical applications. Online Conformal Prediction (OCP) offers a theoretically principled framework for generating prediction sets that guarantee the true label is included with a user-specified frequency, even for non-i.i.d. data streams and black-box classifiers. However, standard OCP methods rely on a feedback loop: after issuing a prediction set, the algorithm receives feedback (either the true label or a coverage signal) to adjust future sets, compensating for past miscoverages.

This paper addresses a setting where such feedback is unavailable or prohibitive. In many safety-critical scenarios, such as latent probes for Large Language Models (LLMs), an algorithm may need to classify inputs into safety categories. If the probe abstains (queries a human or a stronger system), the label may eventually become available. However, for inputs where the probe makes a deployed decision, the label is never observed. This creates a "beyond feedback" scenario: the learner must choose between outputting a prediction set or querying the correct label, but cannot do both. Consequently, the learner never observes whether a deployed prediction set was correct, preventing the standard compensation mechanisms used in existing OCP methods.

Methodology: OCP with Queries (OCPQ)

The authors propose Online Conformal Prediction with Queries (OCPQ), a method designed for this beyond-feedback protocol. The approach proceeds in two main steps:

1. Reduction to Partial Monitoring: The problem is reduced to a finite partial monitoring game. The "arms" of the game consist of a finite set of prediction thresholds $M \subset [0, 1]$ and a separate query action.

   • Prediction Action: Selecting a threshold $m \in M$ generates a prediction set $\Gamma_C(x_t, m)$ based on a black-box classifier $C$. This action yields no observation (null feedback $\perp$) and no direct reward.
   • Query Action: Selecting the query action reveals the true label $y_t$ but produces no prediction set and yields zero reward.
   • Reward Structure: The algorithm defines an auxiliary reward function $R(m, t)$. If the true label is covered by the prediction set ($y_t \in \Gamma_C(x_t, m)$), the reward is $1 - m(1-\beta)$, where $\beta$ is a user-defined parameter controlling the trade-off between coverage and efficiency. If the label is not covered, the reward is 0. The query action always yields 0 reward. This structure incentivizes the learner to select tight thresholds (small $m$) while maintaining coverage.

2. Algorithm Design: OCPQ adapts the label-efficient exponentially weighted forecaster of Cesa-Bianchi, Lugosi, and Stoltz (2004).

   • On each round $t$, the algorithm performs a query with a fixed probability $\epsilon$.
   • If a query is made, the true label $y_t$ is observed. The algorithm then updates the cumulative reward estimates $\hat{Z}_{m,t}$ for all thresholds $m \in M$ using an inverse probability weighting scheme, effectively reconstructing the reward that would have been obtained had a prediction been made.
   • If no query is made, the algorithm samples a threshold $m_t$ from an exponentially weighted distribution based on the current estimates $\hat{Z}_{m,t}$ and outputs the corresponding prediction set. No feedback is received.

Theoretical Results

The paper establishes finite-horizon guarantees for OCPQ under an oblivious adversarial data stream of length $T$:

• Regret: The expected regret relative to the best fixed threshold in hindsight is $O(T^{2/3})$. Specifically, with $\epsilon = T^{-1/3}$ and $\eta = T^{-2/3}\sqrt{\ln|M|}$, the regret is bounded by $T^{2/3}(2\sqrt{\ln|M|} + 1)$. The authors note this rate is asymptotically optimal for this class of partial monitoring games.
• Coverage: The expected coverage rate $p_{cover}$ satisfies:
  $$E[p_{cover}] \ge \beta - O(T^{-1/3})$$
  This guarantees that the coverage approaches the user-defined target $\beta$ as $T$ increases.
• Query Rate: The algorithm queries the label on only an expected $T^{-1/3}$ fraction of rounds.
• High-Probability Bounds: The paper also derives high-probability bounds for both regret and coverage, demonstrating that the variance of the algorithm's performance is controlled and does not exhibit pathological behavior.

Empirical Results

Experiments were conducted on real-world datasets to validate the approach:

• Distribution Shift: OCPQ was tested on standard benchmarks (MNIST, CIFAR-10, CIFAR-100) where the training distribution differed from the test distribution (e.g., MNIST to USPS, or MNIST to MNIST-C). The results showed that the coverage-efficiency trade-off could be controlled via the parameter $\beta$. The empirical coverage consistently exceeded the theoretical lower bound.
• LLM Safety Monitoring: The method was applied to safety monitoring for LLM prompts using the WildGuardMix dataset, which includes both vanilla and adversarially rewritten prompts. The base classifier's accuracy dropped significantly on adversarial prompts, yet OCPQ maintained coverage above the theoretical bound while keeping prediction sets informative.
• Comparison: When compared to Adaptive Conformal Inference (ACI), which assumes full feedback, OCPQ achieved comparable coverage-efficiency frontiers despite using significantly less information (querying only ~5% of rounds).

Significance and Contributions

The paper claims the following contributions:

1. New Protocol: It formulates OCP in a "beyond feedback" setting where deployed predictions are never evaluated, a scenario common in safety-critical applications where labels are only available for abstained queries.
2. Algorithmic Reduction: It reduces this problem to a partial monitoring game and adapts label-efficient adversarial learning techniques to solve it, specifically modifying the forecaster to treat queries as distinct actions that replace, rather than follow, predictions.
3. Theoretical Guarantees: It provides finite-horizon expected regret and coverage guarantees for OCP in this setting, showing that valid uncertainty quantification is possible with only $O(T^{-1/3})$ label queries.
4. Practical Effectiveness: Experiments demonstrate that sparse supervision (random queries) is sufficient to maintain useful coverage and efficiency trade-offs, even under adversarial distribution shifts, without requiring feedback from deployed prediction sets.

The authors note that while the method is conservative (empirical coverage often exceeds the bound), this is a consequence of the weak assumptions required for the partial monitoring game formulation. Future work could explore less conservative methods or extensions to adaptive adversaries.