Delayed feedback meets a memory cap: CA-OCRC keeps online risk control on target with capacity growing only logarithmically in the maximum delay
Synopsis
Online conformal risk control has assumed each round's loss arrives immediately and intact, yet real systems delay feedback and can track only a limited number of pending predictions, so some feedback is lost for good. CA-OCRC designs the tracking policy and the prediction sets together: each round draws a random proxy delay, is tracked while capacity allows until its feedback arrives or the proxy delay expires, and a two-level inverse probability weighting compensates for lost feedback. Risk bounds for arbitrary and stochastic delays follow, and optimizing the proxy delay distribution shows that capacity growing only logarithmically in the maximum delay suffices to match the convergence rate of OCRC with unlimited feedback.
Interpretation
Online conformal risk control now treats the capacity for tracking feedback as a resource to allocate, rather than treating delay only as a late-arriving label. Earlier online conformal risk control and its delayed-feedback extensions implicitly tracked every pending feedback signal until arrival, i.e., unlimited tracking capacity; the intermittent variant at the other extreme tracks only the current round, i.e., unit capacity. The risk bounds show that a larger tracking probability yields more feedback but raises the tracking load and the probability of capacity saturation, a trade-off that appears in the bounds under both arbitrary and stochastic delays.
The method draws a random proxy delay for each round, and that draw decides whether the round is tracked and for how long at most. The proxy delay is a random duration drawn independently from a distribution to be designed; when capacity permits, the round is tracked until its feedback arrives or the proxy delay expires, at which point it is evicted so the slot can go to a new round. The threshold update uses two-level inverse probability weighting: one level compensates for random eviction by the proxy delay, the other for feedback whose delay exceeds the maximum proxy delay and is never received; on tumor segmentation, open-domain question answering, hierarchical image classification and beam selection, the tracking load stays below capacity.
Perspective
The demonstrated scope is four tasks: tumor segmentation, open-domain question answering, hierarchical image classification and wireless beam selection, with delays generated by an autoregressive gamma model covering both i.i.d. and temporally correlated cases; the conclusions concern the long-term average risk approaching the target level, not a per-round guarantee.
The refined risk bound under stochastic delays relies on the delays being independent and identically distributed; when delays are temporally correlated, the proxy distribution designed for the i.i.d. case is no longer covered by that theorem, and in experiments its risk drifts away from the target level as the correlation time grows.