Capacity-Constrained Delayed Feedback for Online Conformal Risk Control

Bowen Wang, Osvaldo SimeonearXiv 2026 · arXiv

In the quest for "reliable" machine learning, Online Conformal Risk Control (OCRC) has emerged as a powerful tool. It allows models to output prediction sets (rather than single points) that come with rigorous, long-term guarantees on risk—for example, ensuring that a tumor segmentation mask misses no more than 10% of the actual tumor on average.

However, standard OCRC assumes a luxury rarely found in the real world: immediate and perfect feedback. In many high-stakes applications, feedback is delayed (e.g., waiting for a patient's follow-up) and tracking resources are finite (e.g., limited memory to store pending predictions). This paper introduces Capacity-Aware OCRC (CA-OCRC) to bridge this gap.

TL;DR

CA-OCRC is a new framework for maintaining statistical risk guarantees in online learning when feedback is both delayed and limited by a "tracking capacity." By using a randomized tracking policy and inverse probability weighting, it achieves the same long-term risk control as infinite-capacity systems, even with surprisingly small resource budgets.

What Problem Does This Paper Address?

The core promise of conformal methods is a mathematical guarantee: "The average loss will not exceed $\alpha$." In an online setting, the algorithm achieves this by adjusting a confidence threshold based on the losses observed in previous rounds.

The problem arises when you can't see every loss immediately. If you have a "tracking capacity" of $K$, you can only wait for the results of $K$ predictions at any given time. If feedback for round 1 is delayed by 100 days, and you only have a capacity of 10, you might have to stop tracking round 1 to make room for new predictions. Once you stop tracking a round, its feedback is lost forever. Existing OCRC methods break down here because they either assume infinite capacity or fail to account for the bias introduced by lost feedback.

Methods

The authors propose CA-OCRC, which manages the tracking budget through a randomized policy. The process within each round is illustrated in the figure below:

Fig. 1. Illustration of sequential prediction with delayed feedback under a finite tracking capacity. (a) Operations within round t:

Key components include:

  1. Randomized Tracking Policy: For every prediction, the system samples a "proxy delay." This determines how long the system is willing to wait for that specific feedback. If the real feedback doesn't arrive before the proxy delay expires, the round is "evicted" to free up capacity.
  2. Two-Level Inverse Probability Weighting (IPW): To keep the risk guarantees valid, the algorithm doesn't just treat the received feedback as a standard sample. It scales the updates to the confidence threshold by the inverse of the probability that the feedback was actually tracked and received. This mathematically compensates for the "missing" data.
  3. Optimized Proxy Distributions: The authors derive optimal distributions for these proxy delays. For arbitrary delays, a simple Bernoulli-type policy (track until the maximum possible delay with probability $p$, or not at all) works best. For stochastic delays, they provide a closed-form distribution that prioritizes tracking rounds during the windows when feedback is most likely to arrive.

Datasets

The authors evaluated CA-OCRC across four diverse domains:

  • Medical Imaging: Tumor segmentation using the PraNet model on a compilation of open-source datasets (Kvasir, CVC-300, etc.).
  • Natural Language Processing: Open-domain question answering using the Natural Questions (NQ) dataset and a DPR retriever-reader pipeline.
  • Computer Vision: Hierarchical image classification using ImageNet and a ResNet-152 backbone.
  • Wireless Communications: Beam selection tasks, simulating temporally correlated delays in a base station environment.

Key Insights and Ideas

  • The Capacity-Feedback Trade-off: There is a fundamental tension between wanting more feedback (tracking longer) and avoiding "capacity saturation" (where the buffer is full and you can't admit new rounds). CA-OCRC manages this by occasionally "sacrificing" rounds via randomization to ensure the buffer stays healthy.
  • Logarithmic Scaling Laws: One of the most surprising theoretical findings is that you don't need a massive capacity to perform well. The authors show that a capacity $K$ that scales only logarithmically with the time horizon ($K \approx \ln(T)$) is sufficient to achieve the same convergence rate as a system with infinite capacity.
  • Robustness to Correlation: Unlike simpler baselines like FIFO (First-In-First-Out), CA-OCRC remains robust even when delays are temporally correlated (e.g., a "burst" of long delays), because its randomized admission policy prevents the buffer from being permanently clogged by a single bad streak.

Key Results

  • Reliable Risk Control: In all experiments, CA-OCRC successfully converged to the target risk level $\alpha$, whereas naive baselines often overshot the risk budget when capacity was tight.
  • Efficiency: The optimized proxy delay design (which uses knowledge of the delay distribution) produced smaller, more precise prediction sets compared to the "worst-case" Bernoulli design.
  • Convergence Speed: As capacity $K$ increases, the "risk gap" (the distance from the target risk) decays at a rate of $\mathcal{O}(T^{-K/(K+1)})$. This confirms that even small increases in capacity significantly boost the speed at which the algorithm learns to control risk.

Limitations and Future Work

  • Prior Knowledge: The most efficient version of the algorithm requires knowing the distribution of feedback delays. While the authors provide a "worst-case" version that doesn't need this, it is less efficient.
  • Bounded Losses: The current theory is developed for losses bounded between 0 and 1. Extending this to unbounded losses (like squared error in regression) remains an open challenge.
  • Parameter Tuning: Future work could focus on making the algorithm "parameter-free," automatically learning the best tracking probabilities on the fly without manual tuning of the learning rate or proxy distributions.

Summary updated

Abstract

Online conformal risk control (OCRC) enables reliable uncertainty quantification in machine learning by converting model outputs into prediction sets with long-term risk guarantees. These guarantees, however, hinge on the assumption that the loss of each round is revealed immediately and losslessly. In practice, feedback may be delayed, and limited resources may prevent tracking all pending predictions, causing some feedback to be lost. To address this challenge, we develop capacity-aware OCRC (CA-OCRC), a framework that jointly determines how to allocate limited tracking feedback capacity and how to construct prediction sets. CA-OCRC is based on a randomized tracking policy that samples a proxy delay to decide whether, and for how long, feedback for the current round is tracked. CA-OCRC updates the prediction sets via inverse probability weighting, compensating for the possibility of feedback lost due to delays and limited tracking capacity. We analyze risk bounds for both arbitrary and stochastic delays, revealing a trade-off between receiving more feedback and avoiding capacity saturation. Building on these bounds, we optimize the proxy delay distribution, showing scaling laws for the tracking capacity that ensure the same long-term risk as OCRC with unlimited feedback. Experiments on medical imaging, natural language processing, computer vision, and wireless communications show the effectiveness of CA-OCRC as compared to existing OCRC mechanisms.
BibTeX
@misc{wang2026capacity,
  author = {Bowen Wang and Osvaldo Simeone},
  title = {{Capacity-Constrained Delayed Feedback for Online Conformal Risk Control}},
  year = {2026},
  eprint = {2611.17059},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.17059},
}
Figure