Next-token functional estimation
Abstract
Suppose we observe the first n points of a sequence of random variables having length n+1, and wish to estimate a functional of the unobserved final point and the empirical measure of the n observed training points. Such next-token functionals include the probability that the next token is novel (also known as the surprise probability), the tail probability of the minimum distance between the next token and training points, and the test error of a classifier trained on the observed points. All of these quantities are classically estimated by the leave-one-out method, which is inconsistent under temporal dependence. We propose a leave-a-window-out estimator, which deletes a window of length τ after each index before forming the empirical measure and reduces to leave-one-out at τ= 1. Under natural assumptions, we show that the error of our estimator decays at a parametric rate for any stationary β-mixing process that also admits a Marton coupling. Our results thus cover several natural functionals on a large class of stochastic processes. We complement these upper bounds with a sharp minimax lower bound for estimating the surprise probability on mixing Markov chains. Simulations on Markov chains, moving-average processes, and autoregressive processes show that our estimator succeeds in many scenarios where leave-one-out and add-constant baselines fail.
Related
- Information-Theoretic Analysis of Next-Token Prediction under Markovian Data
- From Semantic to Token Communication: The Next Paradigm for Large-Model-Driven 6G Intelligent Connectivity
- The Fundamental Limits of Structure-Agnostic Functional Estimation
- Efficient estimation of measures of functional dependence
- Optimal Linear Functional Estimation for Proportionally High-Dimensional Linear Models
BibTeX
@misc{nakul2026nexttoken,
title = {{Next-token functional estimation}},
author = {Milind Nakul and Vidya Muthukumar and Ashwin Pananjady},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19529},
eprint = {2609.19529},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19529},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Next-token functional estimation
AU - Milind Nakul
AU - Vidya Muthukumar
AU - Ashwin Pananjady
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.19529
UR - https://arxiv.org/abs/2609.19529
AB - Suppose we observe the first n points of a sequence of random variables having length n+1, and wish to estimate a functional of the unobserved final point and the empirical measure of the n observed training points. Such next-token functionals include the probability that the next token is novel (also known as the surprise probability), the tail probability of the minimum distance between the next token and training points, and the test error of a classifier trained on the observed points. All of these quantities are classically estimated by the leave-one-out method, which is inconsistent under temporal dependence. We propose a leave-a-window-out estimator, which deletes a window of length τ after each index before forming the empirical measure and reduces to leave-one-out at τ= 1. Under natural assumptions, we show that the error of our estimator decays at a parametric rate for any stationary β-mixing process that also admits a Marton coupling. Our results thus cover several natural functionals on a large class of stochastic processes. We complement these upper bounds with a sharp minimax lower bound for estimating the surprise probability on mixing Markov chains. Simulations on Markov chains, moving-average processes, and autoregressive processes show that our estimator succeeds in many scenarios where leave-one-out and add-constant baselines fail.
ER -