Batch Universal Prediction via Conditional Additive Smoothing

Marco Bondaschi, Michael GastpararXiv 2026 · arXiv

TL;DR

This paper introduces batch regret, a new theoretical framework for universal prediction that models how a predictor improves after observing a batch of training data. By analyzing simple additive smoothing (add-$\beta$) estimators, the authors characterize the optimal "bias" needed for in-distribution learning and prove a conditional version of the classic regret-capacity theorem.

What Problem Does This Paper Address?

In classical universal prediction, we typically study how a model learns from a single, increasingly long sequence. However, modern machine learning—especially the training of Large Language Models (LLMs)—looks different: a model is trained on a massive batch of independent sequences and then evaluated on a fresh, unseen test sequence from the same distribution.

The authors identify a gap in information theory: we lack a formal measure of "regret" (the excess loss over an optimal predictor that knows the true distribution) for this batch-training setting. They propose batch regret to bridge this gap, providing a mathematical playground to study how "in-context" or "in-distribution" learning efficiency scales with the amount of available training data.

Methods

The researchers employ several key theoretical tools:

  • Conditional Regret-Capacity Theorem: They prove that the minimax batch regret is equal to the maximal conditional mutual information between the source's parameters and the test sequence, given the training batch.
  • Conditional Add-$\beta$ Estimators: They adapt the classic additive smoothing technique (adding a small constant $\beta$ to observed counts) to the batch setting. Unlike standard estimators, these must integrate information from both the static training batch and the evolving test sequence.
  • Poisson Analysis: To understand how these estimators behave when data is sparse (e.g., when a token has a very low probability), they extend the "Poisson regime" analysis originally developed by Krichevsky.
  • Rényi Generalization: The work extends beyond standard logarithmic loss to Rényi divergence, linking batch regret to Sibson’s $\alpha$-mutual information.

Datasets

As a theoretical information theory paper, no real-world datasets were used. Instead, the authors rigorously analyze two fundamental data-generating models:

  1. Binary Memoryless (Bernoulli) Sources: Where bits are generated independently with a fixed probability.
  2. First-Order Binary Markov Sources: Where the probability of the next bit depends on the current state.

Key Insights and Ideas

  • The Importance of the "Poisson Regime": The paper shows that the most challenging parameters to predict are those very close to the boundaries (0 or 1). In these regions, the regret is dominated by a "boundary-layer" effect.
  • Optimal Bias is Dynamic: For memoryless sources, the optimal smoothing parameter $\beta$ isn't a single universal constant; it depends on the size of the training batch $n$. As $n$ grows, this optimal $\beta$ converges to the famous Krichevsky value of $\approx 0.509$.
  • Markov Sources and Initial States: A surprising "aha moment" is that in the batch setting, the initial state distribution of a Markov source becomes a first-order effect. Because the training batch consists of many independent sequences, the model gets many "looks" at how sequences start, making the assumption about the initial law (known, free, or stationary) critical to the total regret.
  • Upper-Envelope Structure: The overall performance of an add-$\beta$ estimator is determined by the maximum of three different regimes: the interior of the parameter space, the exact endpoints, and the Poisson "boundary layer."

![Fig.

  1. The Poisson layer function $G_\beta$ shows how regret behavior changes near the parameter boundaries for different smoothing values.](/figures/art_e415278d9554461b94630560c6942f31)

Key Results

  • Minimax Lower Bound: For Bernoulli sources, the best possible batch regret scales as $\frac{1}{2} \log(1 + 1/n)$. This provides a fundamental limit on how much any predictor can improve given $n$ training sequences.
  • Add-$\beta$ Optimality: The authors find the specific $\beta_n^*$ that minimizes the worst-case regret for a fixed batch size $n$.
  • Markov Regret Coefficients: They characterize the leading coefficients for Markov sources. For example, if the initial state is a "free" parameter, it adds an extra $1/(2n)$ to the regret compared to when the initial state is known.

![Fig.

  1. The full-simplex coefficient $C_\beta$ is formed by the upper envelope of different regret regimes. The intersection point identifies the optimal smoothing parameter.](/figures/art_f78e6859b2744b3baea134db748b86fb)

Limitations and Future Work

The current work is restricted to binary alphabets and relatively simple source models (memoryless and first-order Markov). While these are foundational, real-world data (like natural language) has massive alphabets and much more complex, long-range dependencies.

The authors suggest that future research could:

  • Extend these results to larger, non-binary alphabets.
  • Analyze higher-order Markov models or more complex parametric classes.
  • Apply this "batch regret" framework to more sophisticated architectures, such as Transformers, to see if they can achieve these theoretical optimality limits in practice.

Summary updated

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.
BibTeX
@misc{bondaschi2026batch,
  author = {Marco Bondaschi and Michael Gastpar},
  title = {{Batch Universal Prediction via Conditional Additive Smoothing}},
  year = {2026},
  eprint = {2610.41859},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41859},
}

Loading related content...

Figure