Batch Universal Prediction via Conditional Additive Smoothing
Abstract
Modern language models motivate renewed interest in universal prediction problems in which a predictor can exploit previously observed data before predicting a fresh sequence. We study an idealized version of this setting by introducing \emph{batch regret}: a conditional analogue of classical average regret in which a predictor observes a batch of n training sequences and is then evaluated on an independent test sequence generated by the same unknown source. Additive smoothing estimators, which add a bias to the observed token frequencies before predicting the next token, played a fundamental role as a simple prediction strategy with almost-optimal average regret for memoryless and Markov sources. Their equivalent under batch regret are the conditional additive smoothing estimators, which estimate the conditional distribution of the test sequence given the training batch. In this work, we study their asymptotical batch regret for binary memoryless and first-order Markov sources. For binary memoryless sources, we show how the optimal bias of the estimator, and consequently the corresponding batch regret, change as a function of the training batch size n, by extending the Poisson-based analysis of Krichevsky. For binary Markov sources with positive transitions, we characterize the leading coefficient of batch regret and its dependence on whether the initial law is known, free, or stationary. Finally, we introduce a Rényi analogue of batch regret and identify the corresponding optimal predictors as conditional α-NML estimators, thereby giving an operational interpretation to a conditional version of Sibson's α-mutual information.
Related
- Semantic Prior Smoothing for Conformal Prediction in Multiple-Choice Question Answering with API-Only Large Language Models
- Asymptotics and finite sample bounds for prediction and smoothing in Wright-Fisher hidden Markov models
- Prediction-Powered Smoothing and Validation for Disaggregated AI Evaluation
- Accurate stock movement prediction via centroid-based randomness smoothing
- Conformal Prediction and Conditional Coverage for Tabular Foundation Models
BibTeX
@misc{bondaschi2026batch,
title = {{Batch Universal Prediction via Conditional Additive Smoothing}},
author = {Marco Bondaschi and Michael Gastpar},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41859},
eprint = {2610.41859},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41859},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Batch Universal Prediction via Conditional Additive Smoothing
AU - Marco Bondaschi
AU - Michael Gastpar
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41859
UR - https://arxiv.org/abs/2610.41859
AB - Modern language models motivate renewed interest in universal prediction problems in which a predictor can exploit previously observed data before predicting a fresh sequence. We study an idealized version of this setting by introducing \emph{batch regret}: a conditional analogue of classical average regret in which a predictor observes a batch of n training sequences and is then evaluated on an independent test sequence generated by the same unknown source. Additive smoothing estimators, which add a bias to the observed token frequencies before predicting the next token, played a fundamental role as a simple prediction strategy with almost-optimal average regret for memoryless and Markov sources. Their equivalent under batch regret are the conditional additive smoothing estimators, which estimate the conditional distribution of the test sequence given the training batch. In this work, we study their asymptotical batch regret for binary memoryless and first-order Markov sources. For binary memoryless sources, we show how the optimal bias of the estimator, and consequently the corresponding batch regret, change as a function of the training batch size n, by extending the Poisson-based analysis of Krichevsky. For binary Markov sources with positive transitions, we characterize the leading coefficient of batch regret and its dependence on whether the initial law is known, free, or stationary. Finally, we introduce a Rényi analogue of batch regret and identify the corresponding optimal predictors as conditional α-NML estimators, thereby giving an operational interpretation to a conditional version of Sibson's α-mutual information.
ER -