Normalization is Enough: An Improved Algorithm for Online Group-wise Conformal Prediction

We study adversarial online conformal prediction with the goal of achieving group-wise coverage guarantees while producing small, informative conformal prediction sets. We propose Normalized-GCACI, a new algorithm that modifies the standard group-conditional approach through a single structural change: the prediction threshold is normalized by the number of active groups rather than summed over them. Despite its simplicity, this normalization stabilizes the threshold scale, directly tightens prediction sets, and crucially enables a new analysis that yields a strictly tighter group-wise coverage bound than prior work and extends the known single-group guarantee to the general multi-group setting. Extensive experiments on a non-stationary linear regression benchmark show that Normalized-GCACI tracks the target coverage more closely than existing baselines while producing substantially smaller prediction sets, and targeted ablations confirm that the gain is specifically attributable to the normalization rather than to parameter regularization or step-size decay. Finally, we instantiate our framework on post-retrieval filtering for retrieval-augmented generation (RAG): by constructing conformal prediction sets over candidate documents, our method substantially reduces the number of retained documents while preserving high recall of the relevant evidence, improving retrieval efficiency without sacrificing the quality of downstream generation.