A Measure-Theoretic Analysis of Reasoning in Transformers: Structural Generalization and Approximation Limits

Abstract

Scaling laws for reasoning in large language models (LLMs) are well documented, but little theory explains their out-of-distribution (OOD) generalization. We formalize reasoning with optimal transport: each search trajectory is mapped to twelve structural coordinates, such as tree depth and backtracking rate, and dataset shift is measured by the Wasserstein-1 distance. Kantorovich duality bounds the OOD risk through this distance, the architecture's Lipschitz constant and approximation limits. First, under absolute positional encoding (APE), shifting part of a trajectory to later positions almost surely changes the attention scores within that part; if this misroutes exact-match search, the Lipschitz constant and risk are $\Omega (1)$. Shift-invariant encodings such as rotary position embedding (RoPE) leave the scores unchanged and bound the error. Second, we map backtracking to a Dyck-$k$ language and, under an implicit-depth assumption, derive a risk floor for search trees deeper than a multiple of the number of layers. Enough layers remove this floor; more width only shrinks a separate Barron-space approximation term. Experiments with 54 trained Transformers on combinatorial search (Countdown) support these bounds. Appendix experiments measure structural shifts in public agent, embodied and robot trajectories, shift all position indices of 33 public language models, and split deeply nested tasks into separate model calls.

arXiv commentAccepted at NeurIPS 2026. v2: camera-ready version. 54 pages (10-page main text), 6 figures, 3 tables. Code and results: https://github.com/Yyuzrah/AMTA4R