analiza aiqbench
This paper gives a theoretical account of why Transformers can predict tokens well on non-Markovian sources, a question that has mostly been answered empirically. It derives error bounds via finite-window approximations, with error decaying exponentially in window length for Markovian sources and bounded by an entropy gap for stationary ergodic ones, and shows that a depth-(M+1) Transformer trained with stochastic control can approach these limits. The results are asymptotic and rely on assumptions such as filter stability and Dobrushin coefficients, so readers should treat the numerical studies as illustrative rather than as evidence for practical model design.
When can Optimally Trained Transformers Achieve Near-Lossless Token Prediction for non-Markovian Data?
arXiv:2610.41038v1 Announce Type: new 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 $N$th order Markovian sources, it decays at an exponential rate $\alpha^{\lfloor M/N\rfloor}$, where $M$ is the window length and $\alpha$ 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.
Title: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 $N$th order Markovian sources, it decays at an exponential rate $\alpha^{\lfloor M/N\rfloor}$, where $M$ is the window length and $\alpha$ 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.
Machine Learning (cs.LG); Optimization and Control (math.OC); Probability (math.PR)
arXiv:2610.41038 [cs.LG]
(or arXiv:2610.41038v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.41038 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 314 cuvinte