When can Optimally Trained Transformers Achieve Near-Lossless Token Prediction for non-Markovian Data?
Abstract
There exists little mathematical theory explaining why Transformer architectures are empirically successful even for non-Markovian data. To this end, this paper studies next-token prediction via stochastic optimal control theoretically trained Transformers for such sources, where we consider either stationary and ergodic non-Markovian sources or those which are hidden Markov models of some finite order (possibly non-stationary). In either case, we first obtain error bounds via finite models with finite window approximations. For stationary ergodic sources, the resulting error is bounded by an entropy gap; for Nth order Markovian sources, it decays at an exponential rate α⌊ M/N⌋, where M is the window length and α is determined by filter stability (and the Dobrushin coefficients of the transition and measurement kernels). We then construct a Transformer of depth M+1, one head per layer, realizing the truncated filter, and we optimally train it with stochastic control developed in earlier work, which rigorously returns a near optimal Transformer. In particular, we show that for a non-Markovian source, either under stationarity and ergodicity for general models or under filter stability for hidden Markov models, an optimally trained Transformer has arbitrarily small performance error with increasing context length, data, and approximation refinement. Numerical studies accompany the theory.
Related
- Adversarially Trained Linear Transformers Are Optimal Robust In-Context Learners for Gaussian Mixtures
- An equality condition for the Dobrushin bound on attention rollout and how often it holds in trained transformers
- Information-Theoretic Analysis of Next-Token Prediction under Markovian Data
- One-Layer Transformers Provably Learn In-Context K-Nearest Neighbor Prediction with Chain-of-Thought
- Optimally large cuts in both directions
BibTeX
@misc{akman2026when,
title = {{When can Optimally Trained Transformers Achieve Near-Lossless Token Prediction for non-Markovian Data?}},
author = {Kağan Akman and Jake Feldman Starosta and Naci Saldi and Serdar Yüksel},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41038},
eprint = {2610.41038},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41038},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - When can Optimally Trained Transformers Achieve Near-Lossless Token Prediction for non-Markovian Data?
AU - Kağan Akman
AU - Jake Feldman Starosta
AU - Naci Saldi
AU - Serdar Yüksel
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.41038
UR - https://arxiv.org/abs/2610.41038
AB - There exists little mathematical theory explaining why Transformer architectures are empirically successful even for non-Markovian data. To this end, this paper studies next-token prediction via stochastic optimal control theoretically trained Transformers for such sources, where we consider either stationary and ergodic non-Markovian sources or those which are hidden Markov models of some finite order (possibly non-stationary). In either case, we first obtain error bounds via finite models with finite window approximations. For stationary ergodic sources, the resulting error is bounded by an entropy gap; for Nth order Markovian sources, it decays at an exponential rate α^⌊ M/N⌋, where M is the window length and α is determined by filter stability (and the Dobrushin coefficients of the transition and measurement kernels). We then construct a Transformer of depth M+1, one head per layer, realizing the truncated filter, and we optimally train it with stochastic control developed in earlier work, which rigorously returns a near optimal Transformer. In particular, we show that for a non-Markovian source, either under stationarity and ergodicity for general models or under filter stability for hidden Markov models, an optimally trained Transformer has arbitrarily small performance error with increasing context length, data, and approximation refinement. Numerical studies accompany the theory.
ER -