Improving next-token predictions for dependent data sequences
Next-token functional estimation
Information TheoryMachine Learning
Summary
When you see a series of related data points, predicting the very next one or its properties can be tricky if the data points depend on each other over time. The authors study a better way to estimate these 'next-step' characteristics by removing a group of points instead of just one when calculating estimates, which works better for dependent data. They prove mathematically that this method is reliable for many kinds of dependent sequences and show through examples that it works well even when older methods fail.
What this means in practice
- •For data scientists: Improve predictions of next data points in time-dependent datasets by better estimating related functionals from observed points.
- •For machine learning engineers: Enhance model evaluation metrics relying on next-token properties when training on sequences with temporal dependencies.
Tested on simulated data.
Authors
Milind Nakul, Vidya Muthukumar, Ashwin Pananjady
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.