arXiv:2605.19944v1 [cs.LG] 19 May 2026
A Measure-Theoretic Analysis of Reasoning: Structural Generalization and Approximation Limits
Yuyang Zhang McGill University [email protected]
Yifu Zhang McGill University [email protected]
Xuehai Zhou McGill University [email protected]
Xiaoyin Chen∗ Mila - Quebec AI Institute Université de Montréal [email protected]
Abstract While empirical scaling laws for LLM reasoning are well-documented, the theoretical mechanisms governing out-of-distribution (OOD) generalization remain elusive. We formalize reasoning via optimal transport, projecting discrete trajectories into a continuous metric space to quantify domain shifts using the Wasserstein-1 distance. Invoking Kantorovich duality, we bound OOD generalization via architectural Lipschitz continuity and functional approximation limits. This exposes two primary constraints. First, position-dependent attention (e.g., Absolute Positional Encoding) fails to preserve shift invariance, yielding an Ω(1) Lipschitz constant and expected risk, whereas shift-invariant mechanisms (e.g., Rotary Embeddings) preserve equivariance and bound the error. Second, by mapping sequential backtracking to a Dyck-k language, we establish a strict circuit depth lower bound for TC0 Transformers. Scaling physical layer depth is necessary to avert representation collapse—a constraint that scaling representation width cannot bypass due to irreducible approximation bounds in Barron spaces. Evaluations across 54 Transformer configurations on combinatorial search corroborate these bounds, demonstrating that generalization risk degrades monotonically with the Wasserstein domain shift.
1
Introduction
The transition of large language models (LLMs) from associative pattern matching to explicit, multistep reasoning has been catalyzed initially by prompting techniques [Wei et al., 2023, Yao et al., 2023] and, increasingly, by Reinforcement Learning and other post-training methods [Lightman et al., 2023, OpenAI, DeepSeek-AI, 2025, Lambert et al., 2024]. In formal logical domains, such as combinatorial planning and mathematical problem-solving, these intermediate reasoning trajectories correspond to traversals over an implicit algorithmic search tree. While the empirical scaling properties of reasoning have been heavily documented, a fundamental theoretical gap persists. This raises a critical research question: Under what specific architectural conditions can an autoregressive model reliably generalize its reasoning capabilities across macroscopic structural domain shifts? When a model trained on shallow search steps is evaluated on deep, highly sequential Out-of-Distribution (OOD) reasoning spaces, standard sequence-level log-likelihoods and discrete zero-one losses fail to geometrically isolate the fidelity of the model’s output, leaving this question largely unanswered. ∗ Corresponding author.
Preprint.
Currently, theoretical and empirical analyses of LLM reasoning remain fragmented. Complexity bounds for Transformers (TC0 ) establish limitations on inherently sequential reasoning but abstract away training data distributions [Hahn, 2020, Merrill and Sabharwal, 2023]. Studies on length extrapolation evaluate mechanisms like Absolute Positional Encoding (APE) and Rotary Position Embedding (RoPE) [Kazemnejad et al., 2023, Ruoss et al., 2023], yet rarely do so while jointly bounding computational capacity. Conversely, data-centric analyses emphasize distributional shifts but treat the architecture as an analytic black box [Zhao et al., 2026, Prystawski et al., 2023]. No existing framework bridges discrete circuit complexity with continuous distribution shifts. To address this limitation, our primary contribution is a measure-theoretic framework that mathematically unifies four critical variables in LLM reasoning: discrete circuit complexity (layer depth L), representation capacity (hidden width m), architectural priors (positional encodings), and continuous data distributions (measure shifts). We formulate the evaluation of reasoning as an optimal transport problem. First, we project discrete, variable-length reasoning trajectories into a continuous macroscopic metric space. By extracting scale-invariant features such as nesting depth and backtracking rates, this projection allows us to represent any reasoning dataset as a pushforward probability measure. Consequently, the distributional discrepancy between distinct reasoning tasks can be rigorously quantified via the Wasserstein-1 distance. To bridge this continuous domain shift with the discrete expected risk, we introduce an ϵ-relaxed structural sufficiency assumption. By demonstrating that the expected zero-one loss can be approximated by a Lipschitz continuous structural risk function over our metric space, we invoke Kantorovich duality. What falls out of this formulation is a powerful decomposition: the target generalization risk is strictly bounded by three competing terms—the optimal transport cost (Wasserstein domain shift), the induced Lipschitz constant of the architecture (KP E ), and its functional approximation bounds (Cwidth and Cdepth ). This non-additive lower bound dictates that breaching any single architectural limit induces an Ω(1) expected risk. From this unified bound, we establish two architectural laws of reasoning: First, we analyze translation equivariance and the Lipschitz gap by contrasting the two predominant paradigms of sequence position modeling: absolute and relative encodings [Zhao et al., 2024]. We select standard Absolute Positional Encoding (APE) as the baseline for position-dependent attention kernels, and Rotary Position Embedding (RoPE) [Su et al., 2023] as the representative of a broader class of relative, translation-equivariant positional schemes. Robust generalization requires the attention mechanism to remain invariant to global sequence shifts, as locally consistent search sub-trajectories occur at arbitrary absolute indices. We prove that APE inherently fails to preserve this symmetry; shifting a trajectory’s absolute coordinates causes the local attention kernel to diverge almost surely. This coordinate disruption yields a macroscopic structural Lipschitz constant Kf,AP E = Ω(1) that guarantees an Ω(1) expected out-of-distribution risk. Conversely, we demonstrate that RoPE acts as a continuous structural regularizer that preserves sequence equivariance, averting this representation collapse. Second, building upon the TC0 limits of Transformers [Hahn, 2020], we formalize a circuit depth lower bound. By mapping the grammar of sequential backtracking to a Dyck-k language, we link continuous measure shifts with discrete circuit complexity. Because balanced parenthesis matching is complete for the complexity class NC1 , the fixed physical layer depth L of TC0 Transformers acts as an algorithmic truncation boundary. Scaling physical depth is a necessary prerequisite to avert an Ω(1) expected risk—a constraint that scaling representation width m cannot bypass due to irreducible Ω(m−1/2 ) approximation bounds in Barron spaces [Barron, 1993, Makovoz, 1996]. To rigorously test our framework, we evaluate 54 distinct architectural configurations (crossing Small/Medium/Large scales, Deep/Wide/Balanced aspect ratios, and APE/RoPE) against controlled target distributions. Rather than relying on arbitrary datasets, we synthesize distinct measures within our proxy space, isolating behaviors such as shallow lateral state expansions, deep recursive backtrackings, and highly translated compositional mixtures. The empirical results corroborate our measure-theoretic bounds: (1) The empirical accuracy on deep, highly sequential reasoning structures is strictly capped by the theoretically derived TC0 upper bound. (2) Scaling parameter counts via representation width intrinsically plateaus or collapses, whereas scaling physical layer depth establishes a dominant performance trajectory. (3) Under severe coordinate shifts induced by
2
mixture distributions, wide APE models suffer an Ω(1) representation collapse, while RoPE restores stability. (4) Generalization risk degrades monotonically in proportion to the continuous Wasserstein distance between the source and target measures. Ultimately, our framework establishes that LLMs undergoing reasoning perform structural regressions over a continuous metric space.
2
Preliminaries and Measure-Theoretic Formulation
To analyze the generalization of autoregressive models on search-based reasoning tasks, we formalize the generation process. We map discrete, variable-length sequence trajectories into a continuous metric space, quantifying domain shifts via optimal transport. Detailed measure-theoretic constructions and full proofs are deferred to Appendices A and B. 2.1
The Measurable Space of Search Trajectories
Let V be a finite discrete vocabulary. The ambient space of bounded-length sequences up to a STmax t maximum physical length Tmax ∈ N+ is defined as Zall = t=1 V . We define the search trajectory space Z ⊂ Zall as the subset of sequences satisfying a valid autoregressive search grammar Γ. Every trajectory z ∈ Z admits a unique decomposition via the string concatenation operator ⊕: (z) z = xinit ⊕ ysearch , representing the initial problem state and the generated search trace. Given finite |V| and Tmax , the set Z is finite. We equip Z with the discrete σ-algebra ΣZ := 2Z , forming a complete measurable space with source and target probability measures µS , µT ∈ P(Z). Let FL,m,P E denote the hypothesis class of autoregressive Transformer functions characterized by physical layer depth L, hidden dimension m, and positional encoding scheme P E ∈ {APE, RoPE}. A model f ∈ FL,m,P E acts as a deterministic mapping f : V ∗ → Z. Let Sz : Z → R be a deterministic scoring function parameterized by the target state of the reference trajectory z, evaluating the formal validity of the generated output. We define the zero-one loss function ℓ : FL,m,P E × Z → {0, 1} as: (z) ℓ(f, z) = 1 − I(0,∞) Sz f (xinit ) (1) For any measure µ ∈ P(Z), the expected risk of f is defined as the Lebesgue integral over the R discrete space: Rµ (f ) = Z ℓ(f, z) dµ(z). 2.2
Structural Projection and Pushforward Measures
Computing distances directly over discrete sequences obscures search behavior. Thus, we map trajectories into a continuous metric space X ⊂ R12 equipped with the Euclidean metric dX (u, v) = ∥u − v∥2 . As volumetric coordinates (e.g., χ4 ) scale with sequence capacity Tmax , the geometric diameter diam(X ) = Θ(Tmax ). Thus, for any finite Tmax , X is a bounded, locally compact subset. Definition 1 (Structural Projection Operator Φ). We define a deterministic, Borel measurable projection operator Φ : Z → X , mapping z 7→ χ = [χ1 , . . . , χ12 ]⊤ . This operator provides a summary of the graph-traversal dynamics, encoding maximum tree depth (χ1 ), total search volume (χ4 ), directional state transitions (e.g., child expansion χ5 , parent backtracking χ6 , sibling lateral shifts χ7 ), and pruning frequencies. By applying this projection, we define the structural pushforward measures νS , νT ∈ P(X ) induced by Φ: νS := Φ# µS and νT := Φ# µT . The structural measure shift is quantified by the Wasserstein-1 (Kantorovich-Rubinstein) distance over the coupled metric space: Z W1 (νS , νT ) = inf dX (u, v) dπ(u, v) (2) π∈Π(νS ,νT )
X ×X
where Π(νS , νT ) denotes the set of all joint probability measures on X ×X with marginals νS and νT . Because X is bounded for finite Tmax , the integral converges absolutely, yielding W1 ≤ O(Tmax ). 3
2.3
Error Decomposition via Kantorovich Duality
To bridge the continuous domain shift W1 (νS , νT ) and the discrete expected risk Rµ (f ), we establish a sufficiency assumption that decouples the architecture’s capacity from the empirical data distribution. Assumption 1 (ϵ-Relaxed Structural Sufficiency). Let ϵ > 0 be an irreducible approximation error. We assume there exists a measurable risk function Lf : X → [0, 1]. For any trajectory measure µ ∈ {µS , µT }, the absolute difference between the true expected risk on Z and the expected risk integrated over Φ# µ on X is bounded by ϵ: Z Rµ (f ) −
Lf (χ) d(Φ# µ)(χ) ≤ ϵ
(3)
X
This assumption formalizes the premise that the macroscopic representation Φ(z) captures the taskrelevant components of the search trajectory up to a microscopic residual ϵ. We emphasize that this condition naturally holds in formal combinatorial planning and algorithmic search tasks, where outcome correctness is strictly dominated by macroscopic structural routing (e.g., sufficient tree depths and backtracking) rather than isolated token semantics. Consequently, the out-of-distribution generalization gap is bounded by the Lipschitz continuity of the underlying neural architecture. Lemma 1 (ϵ-Relaxed Error Decomposition). Assume the induced risk function Lf (χ) is Lipschitz continuous on (X , dX ) with minimal Lipschitz constant Kf = supu̸=v |Lf (u) − Lf (v)|/dX (u, v). Then the generalization error gap is bounded by: |RµT (f ) − RµS (f )| ≤ Kf · W1 (νS , νT ) + 2ϵ
(4)
Proof Sketch. R ApplyingRthe triangle inequality alongside Assumption 1 bounds the risk difference |∆R| by | Lf dνT − Lf dνS | + 2ϵ. Normalizing the structural risk function as g = Lf /Kf trivially yields R ∥g∥Lip R≤ 1. Invoking the Kantorovich-Rubinstein duality, the normalized integral difference | g dνT − g dνS | is bounded by W1 (νS , νT ). Scaling the duality bound by Kf yields the claim.
3
Theoretical Limits of Architectural Choices
Having established that the out-of-distribution generalization gap is bounded by the Lipschitz constant Kf and the approximation bounds of Lf , we now formalize how specific architectural priors govern these bounds. We dissect the autoregressive Transformer architecture along two computational axes: the positional encoding scheme (APE vs. RoPE) and the aspect ratio of the computational graph (Deep vs. Wide). 3.1
Sequence Equivariance and the Lipschitz Gap
Algorithmic search trajectories are inherently modular. A locally consistent reasoning sub-trajectory (e.g., a specific subtree traversal) can occur at arbitrary absolute sequence indices, depending entirely on the volume of preceding graph explorations. To quantify a model’s robustness to these domain shifts, we examine the behavior of the attention kernel under sequence translations. Definition 2 (Minimal Sequence Translation Operator Tk ). Let z ∈ Z. We define the translation operator Tk : Z → Z for k ∈ N+ as the operation that inserts one structurally inert node whose textual realization contains exactly k tokens immediately before a local reasoning sub-trajectory ω. Under Φ, this increments the search volume (χ′4 = χ4 + 1), while every token in the subsequent ω undergoes an absolute index shift of +k. Hence the distance in X is 1/2
2
dX (Φ(z), Φ(Tk (z))) = 1 +
X
(∆χm )
2
=: δ ≤ Cδ
(5)
m̸=4
where Cδ is independent of Tmax . For a model to generalize across diverse tree structures, its local computational graph must remain invariant under Tk . We evaluate the pre-softmax attention score Aa,b between two tokens in ω originally at indices a and b, now shifted to a + k and b + k. 4
Lemma 2 (APE Absolute Coordinate Sensitivity). Assume the network parameters (projection matrices WQ , WK and absolute embeddings pt ) are generically parameterized, and the projection ⊤ matrices satisfy WQ WK ̸= 0. Under the operator Tk (k > 0), the local computational attention E E kernel of an APE model differs almost surely: ∆AAP E = |ÃAP − AAP a,b a,b | > 0. Proof Sketch. Expanding the bilinear forms of the APE attention kernel cancels the positionindependent terms. The residual divergence ∆AAP E forms a non-trivial multivariate quadratic polynomial. By the properties of real algebraic geometry, the zero-locus of this polynomial defines a proper algebraic variety with Lebesgue measure zero in R2d . Consequently, exact cancellation under random initialization occurs with probability zero. Conversely, Rotary Position Embedding (RoPE) relies on orthogonal rotation matrices, yielding ∆ARoP E = 0. See Appendix C. Assumption 2 (Autoregressive Sensitivity via Markov Compounding). We assume the base searchbased reasoning task exhibits an intrinsic global smoothness, yielding a baseline structural Lipschitz constant O(1/Tmax ). Furthermore, generating a formal search trajectory constitutes a zero-tolerance Markov decision process over a directed acyclic graph. We assume that a local attention-kernel coordinate disruption (∆A > 0) at a critical routing step forces the autoregressive process into an incorrect subtree. Due to exact-match evaluation, this localized divergence irrevocably precludes reaching the target state, compounding the localized error into a global trajectory failure. This bounds the expected structural risk variation below by the uniform error probability: ∆L = |Lf (χ′ ) − Lf (χ)| ≥ 1 − 1/|V| := γ > 0. Theorem 1 (The Lipschitz Gap). Under Assumption 2, for a sufficiently large sequence capacity Tmax , the Lipschitz constant of the induced risk function for APE is asymptotically larger than that of RoPE: Kf,RoP E = O(1/Tmax ) ≪ Ω(1) ≤ Kf,AP E . Proof Sketch. The Lipschitz constant is bounded below by the evaluation at the specific perturbed pair: Kf,AP E ≥ |∆L|/δ ≥ γ/Cδ . Because γ and Cδ are Ω(1) constants independent of Tmax , it follows that Kf,AP E = Ω(1). By preserving relative sequence distances, RoPE maintains the local dependency structure without introducing artificial discontinuities, inheriting the task’s intrinsic baseline smoothness O(1/Tmax ). 3.2
Capacity Limits: The TC0 vs. NC1 Algorithmic Bottleneck
Beyond sequence equivariance, graph-traversal dynamics impose distinct computational complexity constraints on the hypothesis space FL,m,P E . In shallow, lateral state expansions, maintaining mutually independent states allows the evaluation process to be efficiently parallelized across attention heads in a wide network. Conversely, deep recursive backtracking necessitates a Last-In-First-Out (LIFO) stack mechanism. To execute a backtracking transition, the model must implicitly identify and resolve the most recently suspended, non-adjacent sibling node across a flattened 1D sequence history. Lemma 3 (Surjective Monoid Homomorphism to Dyck-k). Let k denote the maximum branching (1) (k) factor of the implicit search tree. Defining the traversal alphabet Σsearch = {δdown , . . . , δdown } ∪ (1) (k) {δup , . . . , δup } ∪ {ωeval }, there exists a surjective monoid homomorphism ψ : Σ∗search → Σ∗Dyck mapping child expansions to left parentheses (c and backtracking steps to right parentheses )c . Every valid search trajectory projects to a balanced prefix in Dk , where the maximum tree depth χ1 maps exactly to the maximum parenthesis nesting depth. Parsing Dyck-k for k ≥ 2 is complete for the complexity class NC1 . However, a Transformer computing L sequential layers under bounded numerical precision belongs to TC0 . Under the standard separation TC0 ⊊ NC1 , a constant-depth circuit cannot evaluate arbitrary NC1 functions. We formalize this limitation into two independent capacity bounds on the expected risk. Let L∗ (χ) = inf h Ez∼µT [ℓ(h, z) | Φ(z) = χ] denote the Bayes-optimal structural risk function. To relate the L1 (νT ) approximation error in HBarron to the discrete zero-one risk, we assume a standard margin condition on the target structural measure νT [Tsybakov, 2004]; the formal statement is given in Appendix D.1 (Assumption 3). 5
Lemma 4 (Width Capacity Bound via Barron Spaces). Assuming L∗ ∈ HBarron , any autoregressive Transformer hypothesis bounded by an internal representation width m satisfies the lower bound: width RµT (f ) ≥ C√ − ϵ. m Proof Sketch. While the Transformer operates on microscopic token embeddings, correctly routing recursive transitions requires its internal representations to implicitly track global tree states. Thus, the physical Feed-Forward Network (FFN) width m acts as an information-theoretic upper bound on of Lf . By R the capacity R R applying R the linearity of the Lebesgue integral, we decompose the risk Lf = (Lf − L∗ ) + L∗ ≥ |Lf − L∗ |. By universal approximation limits for Barron spaces, this absolute L1 error decays at best via Ω(m−1/2 ). While the external autoregressive generation linearly expands the global causal graph length, the model must execute implicit heuristic routing evaluations at each discrete step that are not serialized in the output. Resolving non-adjacent sibling dependencies across a flattened history relies entirely on the fixed physical depth L of a single forward pass. Prior work shows that finite-precision Transformers with bounded depth face limitations on hierarchical formal-language dependencies such as Dyck-style nesting [Hahn, 2020, Merrill and Sabharwal, 2023]. Motivated by these limits, we introduce a task-dependent truncation constant αcirc > 0 and model the recoverable structural depth of a depth-L architecture by the threshold χ1 ≤ αcirc L. Lemma 5 (Implicit Depth Bottleneck Bound). Defining the Borel measurable indicator function PimplicitR(χ; L, αcirc ) = I(αcirc L,∞) (χ1 ), the expected target risk is bounded below by: RµT (f ) ≥ 1 Cdepth X Pimplicit dνT − ϵ, where Cdepth = 1 − |V| ∈ (0, 1).
4
Synthesis of the Main Bound
Theorem 2 (The Generalization Bound). For any autoregressive Transformer f ∈ FL,m,PE , the target generalization risk RµT (f ) is bounded below by the maximum of three independent lower bounds, and bounded from above by its source risk and domain shift penalty: (
(LB) (UB)
RµT (f ) ≥ max
Cwidth √ − ϵ, Cdepth m
)
Z Pimplicit dνT (χ) − ϵ, RµS (f ) − Kf,PE · W1 (νS , νT ) − 2ϵ
(6)
X
RµT (f ) ≤ RµS (f ) + Kf,PE · W1 (νS , νT ) + 2ϵ
(7)
Proof Sketch. Applying Kantorovich duality to the ϵ-relaxed structural risk, and intersecting this with the TC0 circuit depth lower bound and Barron space approximation bounds, isolates the respective bounds. See Appendix E. Corollary 1 (The Divergent OOD Guarantees of APE vs. RoPE). Let RµS (f ) = ϵtrain ≈ 0 and W1 (νS , νT ) = Ω(Tmax ). RoPE preserves equivariance: its expected generalization error degrades proportionally to the normalized shift, RµT (fRoP E ) ≤ ϵtrain + Csmooth · (W1 /Tmax ) + 2ϵ. Conversely, APE suffers coordinate disruption, yielding an Ω(1) expected risk: RµT (fAP E ) ≥ γ · pshif t − ϵ, precluding any generalization guarantee. Corollary 2 (The “Deep is Better” Law for Search Reasoning). Let the target measure νT place probability mass on trajectories satisfying the tree depth threshold χ1 > αcirc L. Scaling the −1 discrete physical depth L ≥ αcirc supχ χ1 explicitly eliminates the Ω(1) lower bound, establishing a dominant scaling trajectory over the representation width m, which inherently plateaus as √ limm→∞ (Cwidth / m − ϵ) = −ϵ ≤ 0.
5
Empirical Verification
To empirically validate Theorem 2, we evaluate how architectures navigate domain shifts under controlled configurations by decoupling layer depth L, width m, and positional encodings, while holding total parameter counts asymptotically constant per scale. Motivated by depth-separation theorems [Eldan and Shamir, 2016, Levine et al., 2021] and TC0 bounds [Merrill and Sabharwal, 6
Table 1: Summary of the 54 Transformer Architectural Configurations Evaluated Core Params†
Total Params‡
4 4 4
5.3 M 4.7 M 5.3 M
24.8 M 30.7 M 44.3 M
512 768 1024
8 12 16
75.5 M 84.9 M 75.5 M
127.6 M 163.0 M 179.5 M
768 1024 1536
12 16 24
339.7 M 301.9 M 339.7 M
418.2 M 405.8 M 495.9 M
Scale / Shape
Layers (L)
Width (d)
Heads (h)
Small Deep Small Balanced Small Wide
12 6 3
192 256 384
Medium Deep Medium Balanced Medium Wide
24 12 6
Large Deep Large Balanced∗ Large Wide
48 24 12
Note: All configurations crossed with PE ∈ {APE, RoPE} and Training Data ∈ {BFS, DFS, Mixed}. † Core Params = 12Ld2 , isolating the architectural capacity independent of vocabulary. ‡ Total Params includes embeddings (V = 50257) without weight tying. ∗ Adjusted d = 1024 to match computational capacity of its scale group.
2023], we systematically design a grid of 54 Transformer architectures crossing three parameter scales (Small, Medium, Large) and three aspect ratios (Deep, Wide, Balanced). To evaluate the Lipschitz constant Kf,P E , we cross every configuration with APE and RoPE [Su et al., 2023]. While empirical literature highlights their role in length extrapolation, our framework casts them more fundamentally: APE establishes a rigid absolute coordinate system vulnerable to disruption, whereas RoPE injects relative equivariance to preserve continuous structural regularities. Table 1 summarizes these models. To instantiate the grammar Γ and probability measures (µS , µT ), we utilize the Stream of Search (SoS) framework [Gandhi et al., 2024] as a discrete trajectory simulator. While our theoretical bounds govern general autoregressive reasoning, utilizing SoS allows us to strictly enforce the target distributions required for empirical validation, providing a rigorous testbed that satisfies our axiomatic requirements. We synthesize 500,000 ground-truth trajectories on a combinatorial planning task (the Countdown game). By manipulating the simulator’s heuristic evaluation strategies, we enforce distinct distributions. The µBF S measure is synthesized via queue-based state expansions, generating shallow, lateral traversal traces. The µDF S measure is synthesized via recursive stack expansions, forcing deep backtracking when trajectories encounter dead-ends. The µM IXED distribution is constructed as an exact 0.5µBF S + 0.5µDF S mixture to test architectural plasticity against extreme coordinate shifts. Given the unforgiving exact-match nature of formal combinatorial planning, the zero-one loss establishes a rigorous baseline where partial memorization yields zero reward. Structural Optimal Transport Estimation. To operationalize the Kantorovich bounds, we estimate the Wasserstein-1 distance between structural pushforward measures using entropically regularized optimal transport, solved via the Sinkhorn-Knopp algorithm with regularization parameter λ = 0.1 [Cuturi, 2013]. Utilizing N = 2, 000 uniformly sampled trajectories per distribution, we construct empirical structural measures on X . Following global standardization and cost-matrix c1,λ (ν̂BF S , ν̂M IXED ) ≈ 0.42 supremum normalization, we report the regularized transport costs: W c and W1,λ (ν̂BF S , ν̂DF S ) ≈ 0.81. Exact estimation procedures, cost-matrix construction, normalization details, and robustness checks across sample sizes are reported in Appendix G. Note: Since c1,λ empirical Wasserstein estimation in R12 is subject to sample complexity bounds, the reported W values serve as comparative regularized proxies for the true structural shifts rather than exact analytic distances. 5.1
Positional Encodings as Structural Regularizers
To empirically validate our insight regarding positional encodings as regularizers, we examine the Lipschitz gap established in Theorem 1. As predicted by our bounds, APE yields trivial generalization limits under sequence translations. When trained on the µM IXED distribution, the model continuously alternates between shallow and deep traversals, subjecting the attention kernel to largescale absolute sequence index shifts. Here, the coordinate disruption proven in Lemma 2 manifests 7
$ 7 K H 6 X S U H P X P & D S D F L W \ / L P L W R Q DFS
% 6 F D O L Q J / L P L W V 5 H S U H V H Q W D W L R Q & R O O D S V H Y V 6 W D E L O L W \
$ F F X U D F \ R Q DFS
( P S L U L F D O $ F F X U D F \
3 R V L W L R Q ( P E H G G L Q J 7 \ S H $ 3 ( 5 2 3 ( 7 U D L Q L Q J ' D W D ' L V W U L E X W L R Q V K D O O R Z O D W H U D O V W D W H H [ S D Q V L R Q V % ) 6 G H H S U H F X U V L Y H E D F N W U D F N L Q J V ' ) 6 K L J K O \ W U D Q V O D W H G F R P S R V L W L R Q D O P L [ W X U H V 0 L [ H G 7 K H R U H W L F D O & H L O L Q J 1 maxBdepth
3 K \ V L F D O / D \ H U ' H S W K L
3 R V L W L R Q ( P E H G G L Q J 7 \ S H 5 2 3 ( $ 3 ( 6 K D S H % D O D Q F H G : L G H ' H H S
& 6 H T X H Q F H ( T X L Y D U L D Q F H R Q MIXED : L G H 0 R G H O V
& R U H 3 D U D P H W H U V 0 L O O L R Q V O R J V F D O H
' & R Q W L Q X R X V 0 H D V X U H 5 H J U H V V L R Q V $ O O % ) 6 7 U D L Q H G
$ 3 ( 5 2 3 (
( P S L U L F D O $ F F X U D F \
$ F F X U D F \ R Q MIXED
$ 3 ( 5 2 3 (
(1) 5 H S U H V H Q W D W L R Q & R O O D S V H
& R U H 3 D U D P H W H U V 0 L O O L R Q V O R J V F D O H
% ) 6
0 , ; ( '
7 D U J H W 0 H D V X U H T , Q F U H D V L Q J 0 D F U R V F R S L F 6 K L I W
' ) 6
Figure 1: Comprehensive validation of capacity bounds. (A) Supremum capacity limit on µDF S , showing empirical accuracy enveloped by the derived upper bound curve. This theoretical ceiling detailed in AppendixG.3 (B) Scaling limits, illustrating that scaling representation width inherently plateaus, whereas scaling physical depth establishes a dominant scaling trajectory. (C) Sequence equivariance on µM IXED , where scaling wide APE architectures triggers representation collapse, while RoPE acts as a regularizer. (D) Continuous measure regressions, demonstrating that generalization accuracy cascades monotonically downward as the target measure shifts structurally toward µDF S , empirically corroborating the continuous measure regression bounds. precisely: the large wide mixed APE architecture exhibits performance degradation, achieving a mere 0.4215 accuracy on the Mixed test set. In contrast, preserving local sequence equivariance allows the large wide mixed RoPE model to sustain 0.5425—an absolute recovery of over 12%. As detailed in Figure 1D, visualizing the quantitative linear regression between the Wasserstein distance W1 and empirical accuracy drops corroborates the diverging slopes. This confirms that Kf,AP E is asymptotically larger than Kf,RoP E under severe domain shifts, empirically verifying that RoPE acts not merely as a length extrapolator, but as a regularizer over the continuous metric space. 5.2
The Anisotropy of Parameter Scaling and TC0 Bottlenecks
Corroborating our insight on the anisotropy of parameter scaling, the empirical data confirms that overcoming the TC0 complexity bottleneck requires increasing the physical layer depth L (Lemma 5), while widening the representation dimension m inherently plateaus within Barron spaces (Lemma 4). Without relative equivariance, this depth boundary is rigid. Comparing the failed large wide mixed APE architecture (0.4215) with its depth-scaled counterpart, the large deep mixed APE architecture (0.533), we observe an 11.15% absolute increase. While the total parameter count remains asymptotically identical between these two configurations, the structural transition from a parallel wide computational graph to a sequential deep one satisfies the implicit depth threshold derived for algorithmic backtracking. Crucially, the inherent smoothness provided by RoPE regularizes the optimization landscape, preventing premature representation collapse. As shown in the extended analyses in Figure 1B, deep architectures no longer unilaterally dominate wide architectures when equipped with RoPE. For example, the large wide DFS RoPE configuration 8
achieves 0.518 compared to the large deep DFS RoPE at 0.5145. This indicates that strong translation equivariance allows the architecture to gracefully approach its true theoretical capacity without the catastrophic coordinate divergence that otherwise traps APE models, demonstrating the intersection between Lipschitz smoothness and structural capacity 5.3
Continuous Measure Regressions and the Supremum Bound
Finally, we validate the unified bound (Theorem 2), which implies that generalization is governed by a supremum operator over architectural bottlenecks and optimal transport costs. As plotted in Figure 1A, the empirical accuracy of all evaluated models is capped by the derived TC0 upper bound ceiling, confirming that no magnitude of width scaling can bypass the depth limit.
6
Related Work
Circuit Complexity and Transformer Expressivity. Bounded-precision Transformers are restricted to TC0 , inherently struggling with sequential NC1 tasks like Dyck languages [Hahn, 2020, Merrill and Sabharwal, 2023]. Furthermore, depth-separation theorems prove bounded depth cannot be efficiently compensated by width [Eldan and Shamir, 2016, Levine et al., 2021]. While these foundational works yield distribution-agnostic worst-case limits, our framework integrates TC0 bottlenecks with optimal transport and Barron space bounds [Barron, 1993, Makovoz, 1996], mapping discrete expressivity directly to expected risk under specific data measures. Positional Encodings as Structural Regularizers. Positional encodings govern OOD length extrapolation [Zhao et al., 2024], evolving from absolute injections (APE) to relative mechanisms like ALiBi [Press et al., 2022] and NoPE [Kazemnejad et al., 2023]. Advanced variants, including fractional interpolation (FIRE) [Li et al., 2024], hierarchical encodings (BiPE) [He et al., 2024], and data-adaptive schemes (DAPE) [Zheng et al., 2024], demonstrate superior empirical generalization. Moving beyond decaying attention theories, we elevate shift-invariant encodings to continuous structural regularizers. We select RoPE [Su et al., 2023] as the canonical mathematical representative for this class. Because advanced relative encodings inherently share the translation-equivariant algebraic signature ∆A = 0 under shifts, they inherit our generalized Lipschitz bound. Thus, we theoretically quantify why APE incurs an Ω(1) risk under structural shifts, whereas equivariant priors rigorously bound the Kantorovich penalty across diverse reasoning tasks. Optimal Transport and Reasoning Domain Shifts. Recent analyses conceptualize reasoning as search tree traversals, showing generalization is bounded by train-test distributional discrepancies [Feng et al., 2023, Gandhi et al., 2024, Prystawski et al., 2023, Zhao et al., 2026]. However, they generally treat neural architectures as black boxes. To close this loop, we draw fundamental inspiration from optimal transport (OT) domain adaptation, which bounds target risk via Wasserstein distances over static Euclidean features [Courty et al., 2016, Redko et al., 2017]. We extend this classic OT foundation to autoregressive sequence generation. By designing a pushforward operator Φ to project variable-length trajectories into a continuous metric space, we explicitly couple Kantorovich dual bounds to Transformer circuit complexity and attention kernels, providing the first unified bound bridging continuous domain shifts with discrete architectural limits.
7
Conclusion and Limitations
We introduced a measure-theoretic framework quantifying the structural generalization of LLMs engaged in formal search-based reasoning. By mapping discrete reasoning trajectories into a continuous metric space, we isolated the OOD generalization gap into manageable components via Kantorovich duality. We mathematically proved and empirically validated two architectural laws: (1) APE suffers coordinate disruptions under sequence translations, resulting in an Ω(1) Lipschitz constant and an Ω(1) expected risk, whereas RoPE guarantees relative equivariance; and (2) fixed-depth Transformers under bounded numerical precision are limited by a TC0 bottleneck when evaluating Dyck-k recursive backtracking. Overcoming this requires scaling physical layer depth (L), a constraint that representation width (m) cannot bypass. Limitations and Future Work. Our framework relies on the ϵ-relaxed structural sufficiency; openended natural language reasoning may harbor higher approximation errors than formal combinatorial 9
searches. Furthermore, our TC0 bottleneck governs the forward-pass routing of a single autoregressive trajectory. How advanced inference-time interventions—such as Tree-of-Thoughts or Monte Carlo Tree Search—dynamically reshape the target measure νT remains an open theoretical question. Broader Impact. As the field pivots toward inference-time scaling and search-based LLMs, our framework dictates that translation-equivariant architectures (like RoPE) are not merely beneficial, but act as a necessary prerequisite for stable inference-time scaling due to the extreme sequence translations (Tmax → ∞) involved. By highlighting the necessity of depth and relative equivariance, our framework provides a principled foundation for designing more efficient reasoning architectures.
Acknowledgements This research was enabled in part by compute resources, software, and technical assistance provided by Mila (Quebec AI Institute).
Author Contributions Yuyang Zhang conceptualized the measure-theoretic framework, developed the core mathematical proofs, engineered the training and deployment pipeline for all Transformer configurations, executed all experiments, and led the manuscript drafting. Yifu Zhang verified the mathematical derivations in the appendices and contributed to manuscript proofreading and refinement. Xuehai Zhou managed the codebase repository, and handled experimental version control. Xiaoyin Chen supervised the project, provided computational resources. Provided guidance on the experimental design, and mentored the manuscript writing and structuring process.
References Andrew Barron. Barron, a.e.: Universal approximation bounds for superpositions of a sigmoidal function. ieee trans. on information theory 39, 930-945. Information Theory, IEEE Transactions on, 39:930 – 945, 06 1993. doi: 10.1109/18.256500. Nicolas Courty, Rémi Flamary, Devis Tuia, and Alain Rakotomamonjy. Optimal transport for domain adaptation, 2016. URL https://arxiv.org/abs/1507.00504. Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transportation distances, 2013. URL https://arxiv.org/abs/1306.0895. Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning, 2023. URL https://arxiv.org/abs/2307.08691. DeepSeek-AI. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning, 2025. URL https://arxiv.org/abs/2501.12948. Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks, 2016. URL https://arxiv.org/abs/1512.03965. Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective, 2023. URL https://arxiv.org/ abs/2305.15408. Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1–8, 2021. URL http://jmlr.org/papers/v22/20-451.html. Kanishk Gandhi, Denise Lee, Gabriel Grand, Muxin Liu, Winson Cheng, Archit Sharma, and Noah D. Goodman. Stream of search (sos): Learning to search in language, 2024. URL https: //arxiv.org/abs/2404.03683. 10
Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171, December 2020. ISSN 2307-387X. doi: 10.1162/tacl_a_00306. URL http://dx.doi.org/10.1162/tacl_a_00306. Zhenyu He, Guhao Feng, Shengjie Luo, Kai Yang, Liwei Wang, Jingjing Xu, Zhi Zhang, Hongxia Yang, and Di He. Two stones hit one bird: Bilevel positional encoding for better length extrapolation, 2024. URL https://arxiv.org/abs/2401.16421. Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers, 2023. URL https://arxiv.org/abs/2305.19466. Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James V. Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, Yuling Gu, Saumya Malik, Victoria Graf, Jena D. Hwang, Jiangjiang Yang, Ronan Le Bras, Oyvind Tafjord, Chris Wilhelm, Luca Soldaini, Noah A. Smith, Yizhong Wang, Pradeep Dasigi, and Hannaneh Hajishirzi. Tulu 3: Pushing frontiers in open language model post-training. arXiv preprint arXiv: 2411.15124, 2024. Yoav Levine, Noam Wies, Or Sharir, Hofit Bata, and Amnon Shashua. The depth-to-width interplay in self-attention, 2021. URL https://arxiv.org/abs/2006.12467. Shanda Li, Chong You, Guru Guruganesh, Joshua Ainslie, Santiago Ontanon, Manzil Zaheer, Sumit Sanghai, Yiming Yang, Sanjiv Kumar, and Srinadh Bhojanapalli. Functional interpolation for relative positions improves long context transformers, 2024. URL https://arxiv.org/abs/ 2310.04418. Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. In The Twelfth International Conference on Learning Representations, 2023. Y. Makovoz. Random approximants and neural networks. Journal of Approximation Theory, 85 (1):98–109, 1996. ISSN 0021-9045. doi: https://doi.org/10.1006/jath.1996.0031. URL https: //www.sciencedirect.com/science/article/pii/S0021904596900313. William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers, 2023. URL https://arxiv.org/abs/2207.00729. B. S. Mityagin. The zero set of a real analytic function. Mathematical Notes, 107(3–4):529–530, 2020. doi: 10.1134/S0001434620030189. URL https://doi.org/10.1134/S0001434620030189. OpenAI. Learning to reason with llms. https://openai.com/index/ learning-to-reason-with-llms/. Accessed: 2025-03-21. Ofir Press, Noah A. Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation, 2022. URL https://arxiv.org/abs/2108.12409. Ben Prystawski, Michael Y. Li, and Noah D. Goodman. Why think step by step? reasoning emerges from the locality of experience, 2023. URL https://arxiv.org/abs/2304.03843. Ievgen Redko, Amaury Habrard, and Marc Sebban. Theoretical analysis of domain adaptation with optimal transport, 2017. URL https://arxiv.org/abs/1610.04420. Anian Ruoss, Grégoire Delétang, Tim Genewein, Jordi Grau-Moya, Róbert Csordás, Mehdi Bennani, Shane Legg, and Joel Veness. Randomized positional encodings boost length generalization of transformers, 2023. URL https://arxiv.org/abs/2305.16843. Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12:543–561, 2024. ISSN 2307-387X. doi: 10.1162/tacl_a_00663. URL http://dx.doi.org/ 10.1162/tacl_a_00663. Jianlin Su, Yu Lu, Shengfeng Pan, Ahmed Murtadha, Bo Wen, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding, 2023. URL https://arxiv.org/abs/ 2104.09864. 11
Alexander B. Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135 – 166, 2004. doi: 10.1214/aos/1079120131. URL https://doi.org/10. 1214/aos/1079120131. Cédric Villani. The Wasserstein distances, pages 93–111. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. ISBN 978-3-540-71050-9. doi: 10.1007/978-3-540-71050-9_6. URL https: //doi.org/10.1007/978-3-540-71050-9_6. Jonathan Weed and Francis Bach. Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance. Bernoulli, 25(4A):2620–2648, 2019. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models, 2023. URL https://arxiv.org/abs/2201.11903. Juanjuan Weng, Zhiming Luo, Zhun Zhong, Shaozi Li, and Nicu Sebe. Logit margin matters: Improving transferable targeted adversarial attack by logit calibration, 2023. URL https:// arxiv.org/abs/2303.03680. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models, 2023. URL https://arxiv.org/abs/2305.10601. Chengshuai Zhao, Zhen Tan, Pingchuan Ma, Dawei Li, Bohan Jiang, Yancheng Wang, Yingzhen Yang, and Huan Liu. Is chain-of-thought reasoning of llms a mirage? a data distribution lens, 2026. URL https://arxiv.org/abs/2508.01191. Liang Zhao, Xiachong Feng, Xiaocheng Feng, Weihong Zhong, Dongliang Xu, Qing Yang, Hongtao Liu, Bing Qin, and Ting Liu. Length extrapolation of transformers: A survey from the perspective of positional encoding, 2024. URL https://arxiv.org/abs/2312.17044. Chuanyang Zheng, Yihang Gao, Han Shi, Minbin Huang, Jingyao Li, Jing Xiong, Xiaozhe Ren, Michael Ng, Xin Jiang, Zhenguo Li, and Yu Li. Dape: Data-adaptive positional encoding for length extrapolation, 2024. URL https://arxiv.org/abs/2405.14722.
A
Formal Setup and Notation
This section collects the formal objects used throughout the appendix and fixes notation for the structural measure-theoretic formulation of search-based reasoning. A.1
Trajectory Space and Structural Feature Space
Let V be a finite vocabulary and let Tmax ∈ N+ denote the maximum physical sequence length. The ambient space of bounded-length sequences is Zall :=
T[ max
V t.
(8)
t=1
Let Γ denote the autoregressive grammar of valid search trajectories. The trajectory space is Z := {z ∈ Zall : z satisfies Γ}.
(9)
Since |V| < ∞ and Tmax < ∞, the set Z is finite. We equip Z with the discrete σ-algebra ΣZ := 2Z .
(10)
Since Z is finite and is equipped with the discrete σ-algebra, any map from Z into a measurable space is measurable. We consider source and target probability measures µS , µT ∈ P(Z), where P(Z) denotes the set of probability measures on (Z, ΣZ ). 12
(11)
Each trajectory z ∈ Z is written as (z)
z = xinit ⊕ ysearch ,
(12)
(z) where xinit ∈ V k is the initial problem state and ysearch ∈ V t−k is the generated search trace.
We next define the structural feature space. Let X ⊂ R12 be the structural state space, equipped with the Euclidean metric dX (u, v) := ∥u − v∥2 . (13) We equip X with the Borel σ-algebra B(X ) induced by this metric. Because all trajectories have bounded physical length, each structural coordinate is bounded. We therefore take X to be a bounded Borel subset of R12 containing Φ(Z); when compactness is needed, we replace X by its closure, which does not change any pushforward measure induced by Φ defined in A.3. We give the coordinate-level construction of the structural projection Φ : Z → X, z 7→ χ(z) = [χ1 (z), . . . , χ12 (z)]⊤ , (14) which maps a variable-length discrete trajectory to a fixed-dimensional structural representation. Let N ∈ N≥1 denote the number of explicitly generated nodes in z. For the i-th node, let idi denote its sequence identifier and let Di := |idi | (15) be its structural tree depth. Let C(z, ω) denote the number of exact non-overlapping occurrences of a substring ω in z. The vector χ(z) is defined through three groups of statistics. These features summarize the macroscopic structure of a trajectory. Tree-structural and volumetric statistics. χ1 (z) = max Di 1≤i≤N
(maximum depth),
(16)
(mean depth),
(17)
(depth standard deviation),
(18)
(search volume).
(19)
N
χ2 (z) =
1 X Di N i=1 N
χ3 (z) =
1 X (Di − χ2 )2 N i=1
!1/2
χ4 (z) = N Dynamical transition statistics.
Let M := max(1, N − 1). We define
N −1 X
χ5 (z) =
1 I{Di+1 > Di } M i=1
χ6 (z) =
1 X I{Di+1 < Di } M i=1
χ7 (z) =
1 X I{Di+1 = Di } M i=1
(deepening rate),
(20)
(backtracking rate),
(21)
(lateral transition rate).
(22)
N −1
N −1
Pruning and outcome statistics. χ8 (z) = C(z, "No Solution") χ9 (z) = χ8 /N χ10 (z) = I{C(z, "Goal Reached") ≥ 1} χ11 (z) = C(z, "*") + C(z, "/") χ12 (z) = C(z, "+") + C(z, "-")
(prune count), (pruning rate), (solution indicator), (multiplicative bias), (additive bias).
(23) (24) (25) (26) (27)
By construction, each coordinate is bounded under the finite-length assumption, so χ(z) ∈ X for every z ∈ Z. Since Z is finite and carries the discrete σ-algebra, every map from Z into (X , B(X )) is measurable. In particular, Φ is Borel measurable, and its image Φ(Z) is finite. 13
A.2
Theoretical Justification of Structural Sufficiency (ϵ-Relaxation)
Assumption 1 postulates that our macroscopic projection Φ(z) acts as a sufficient structural proxy for the expected zero-one risk, up to a microscopic residual error ϵ. While compressing variable-length discrete token sequences into a R12 vector is inherently lossy, this relaxation is rigorously justified by the deterministic nature of formal combinatorial planning (e.g., the Countdown task). Success in algorithmic search tasks is predominantly dictated by the macroscopic routing strategy rather than isolated token memorization. Specifically, whether a trajectory ultimately reaches a valid solution relies on exploring sufficiently deep computational graphs (captured by maximum depth χ1 ), successfully executing recursive recoveries (backtracking rate χ6 ), and balancing operator heuristics (additive vs. multiplicative biases χ11 , χ12 ). By design, our structural feature space X explicitly captures these invariant graph-traversal dynamics. The irreducible approximation error ϵ strictly accounts for the microscopic token identities (i.e., the specific integer values) that are deliberately abstracted away by Φ. Because OOD generalization in algorithmic reasoning is fundamentally bottlenecked by the capacity to execute correct structural routing rather than memorizing specific arithmetic permutations, evaluating the Lipschitz continuity of the risk function over X provides a highly robust bound for the true trajectory-level risk. Thus, the ϵ-relaxation serves as a mathematically tractable and physically grounded bridge between discrete sequence generation and continuous measure theory. A.3
Pushforward Measures and Structural Shift
The structural source and target measures are defined as the pushforwards of µS and µT under Φ: νS := Φ# µS , νT := Φ# µT . (28) Since Φ is Borel measurable, νS and νT are Borel probability measures on (X , B(X )). Moreover, because Φ(Z) is finite and X is bounded, both measures have finite first moment; equivalently, νS , νT ∈ P1 (X ). Equivalently, for any Borel set A ∈ B(X ), νS (A) = µS (Φ−1 (A)), νT (A) = µT (Φ−1 (A)). Because Z is finite, the pushforward measures admit the explicit representations X νS (A) = IA (Φ(z)) µS ({z}),
(29) (30)
z∈Z
νT (A) =
X
IA (Φ(z)) µT ({z}).
(31)
z∈Z
To quantify the structural discrepancy between source and target reasoning behaviors, we use the Wasserstein-1 distance between their pushforward measures Z W1 (νS , νT ) := inf dX (u, v) dπ(u, v), (32) π∈Π(νS ,νT )
X ×X
where Π(νS , νT ) denotes the set of couplings of νS and νT , i.e., the set of probability measures on X × X whose marginals are νS and νT [Villani, 2009]. Since νS , νT ∈ P1 (X ) and X is bounded, the transportation cost is finite for every π ∈ Π(νS , νT ). Hence W1 (νS , νT ) is well-defined and finite. A.4
Risk and Structural Risk
Let FL,m,PE denote the class of autoregressive Transformer models with layer depth L, hidden dimension m, and positional encoding scheme PE. By the trajectory decomposition defined earlier, (z) each z ∈ Z induces an initial problem state, denoted by xinit . For a model f ∈ FL,m,PE , the generated trajectory obtained from the prompt induced by z is (z)
f (xinit ) ∈ Zall .
(33)
Let Sz : Zall → R be a deterministic scoring function parameterized by the target state of the reference trajectory z, evaluating the formal validity of the generated output. We define the zero-one loss by (z) ℓ(f, z) := 1 − I(0,∞) Sz f (xinit ) . (34) 14
For any probability measure µ ∈ P(Z), the expected risk of f under µ is Rµ (f ) := Ez∼µ [ℓ(f, z)].
(35)
In the main text, we relate the trajectory-level risk Rµ (f ) to a structural risk functional defined on X through the pushforward measure Φ# µ.
B
Proofs of Structural Generalization Results
B.1
Structural Sufficiency Assumption
We recall Assumption 1, which is used throughout the proofs below. It states that there exists an irreducible approximation error ϵ > 0 such that, for each model f , there is a Borel measurable structural risk function Lf : X → [0, 1] satisfying, for every µ ∈ {µS , µT }, Z Rµ (f ) − Lf (χ) d(Φ# µ)(χ) ≤ ϵ. (36) X
Assumption 1 formalizes the premise that the macroscopic structural representation Φ(z) captures the task-relevant components of the trajectory distribution up to an irreducible approximation error ϵ. B.2
Proof of Lemma 1
We now provide a complete proof of Lemma 1, formalizing the sketch given in the main text. For completeness, we restate Lemma 1. Assume that Lf is Lipschitz continuous on (X , dX ) with minimal Lipschitz constant |Lf (u) − Lf (v)| . dX (u, v) u̸=v∈X
Kf := sup
(37)
Then the generalization error gap satisfies |RµT (f ) − RµS (f )| ≤ Kf W1 (νS , νT ) + 2ϵ.
(38)
Proof. Let ∆R := |RµT (f ) − RµS (f )| . Adding and subtracting the structural expectations under νT and νS gives Z Z ∆R = RµT (f ) − Lf (χ) dνT (χ) + Lf (χ) dνT (χ) X
(39)
X
Z
Z
−
Lf (χ) dνS (χ) + X
Lf (χ) dνS (χ) − RµS (f ) .
(40)
X
Applying the triangle inequality yields Z ∆R ≤ RµT (f ) − Lf (χ) dνT (χ) X Z Z + Lf (χ) dνT (χ) − Lf (χ) dνS (χ) X X Z + Lf (χ) dνS (χ) − RµS (f ) .
(41)
X
By Assumption 1, Z ∆R ≤
Z Lf (χ) dνT (χ) −
X
Lf (χ) dνS (χ) + 2ϵ.
(42)
X
If Kf = 0, then Lf is constant on X , so the integral difference vanishes and the claim follows immediately. 15
Assume now that Kf > 0, and define g(χ) :=
Lf (χ) . Kf
(43)
Then g is 1-Lipschitz. Since νS , νT ∈ P1 (X ), the Kantorovich–Rubinstein duality for W1 applies on (X , dX ) [Villani, 2009, Weed and Bach, 2019]. Therefore, Z Z g(χ) dνT (χ) − g(χ) dνS (χ) ≤ W1 (νS , νT ). (44) X
X
Substituting g = Lf /Kf gives Z Z Lf (χ) dνT (χ) − Lf (χ) dνS (χ) ≤ Kf W1 (νS , νT ). X
(45)
X
Combining this bound with the previous inequality yields ∆R ≤ Kf W1 (νS , νT ) + 2ϵ,
(46)
which proves the claim.
C
Proofs of Positional Encoding Results
C.1
Attention Kernels and the Translation Operator
We first restate the attention kernels for APE and RoPE. Let xi , xj ∈ Rd denote hidden state vectors at absolute sequence indices i and j, and let WQ , WK ∈ Rd×d denote the learned query and key projection matrices. For Absolute Positional Encoding (APE), let pi , pj ∈ Rd denote the absolute position embeddings. The pre-softmax attention score is ⊤ AAPE = (xi + pi )⊤ WQ WK (xj + pj ). i,j
(47)
For Rotary Position Embedding (RoPE) [Su et al., 2023], let RtΘ ∈ Rd×d denote the orthogonal block-diagonal rotation matrix associated with position t. Using (RiΘ )⊤ = (RiΘ )−1 = R−i Θ , the pre-softmax attention score is ARoPE = (RiΘ WQ xi )⊤ (RjΘ WK xj ) i,j
(48)
⊤ i ⊤ j = x⊤ i WQ (RΘ ) RΘ WK xj ⊤ j−i = x⊤ i WQ RΘ WK xj .
(49) (50) (z)
Operational Bounds on Structural Perturbation δ. Let z ∈ Z be written as z = xinit ⊕ ysearch . For k ∈ N+ , the translation operator Tk : Z → Z inserts an isolated, structurally inert node (e.g., a mathematically identity operation such as x=x) of exactly k tokens immediately before a local reasoning sub-trajectory ω ⊂ ysearch . Under the projection Φ, this insertion strictly increments the absolute volume coordinate by one: χ′4 = χ4 + 1. Because the inserted node does not alter the maximum tree depth (∆χ1 = 0) and its contribution to the global transition rates and depth variance decays at a rate of O(1/N ), the remaining structural perturbations are strictly infinitesimal for macroscopic trajectories. Hence, the exact Euclidean structural distance evaluates to: 1/2 X dX (χ, χ′ ) = 12 + (∆χm )2 =: δ. (51) m̸=4
Operationally, as the trajectory length N grows, m̸=4 (∆χm )2 → 0, firmly bounding the perturbation distance tightly around unity: 1 ≤ δ ≤ 1 + O(1/N ) =: Cδ . Concurrently, every token in the subsequent sub-trajectory ω undergoes a massive absolute index shift of +k. P
16
C.2
Proof of Lemma 2
For completeness, we restate Lemma 2. Assume the network parameters (projection matrices WQ , WK and the absolute position embeddings pt ) are generically parameterized (i.e., avoiding exact algebraic degeneracies), and that ⊤ WQ WK ̸= 0.
(52)
Then, under the translation operator Tk with k > 0, the local attention kernel of an APE model differs almost surely: APE ∆AAPE = |ÃAPE a.s. (53) a,b − Aa,b | > 0 Proof. Let xa , xb ∈ ω be tokens originally appearing at indices a and b. After applying Tk , these indices become a + k and b + k. The resulting attention difference is APE eAPE ∆AAPE := A a,b − Aa,b
(54)
⊤ ⊤ = (xa + pa+k )⊤ WQ WK (xb + pb+k ) − (xa + pa )⊤ WQ WK (xb + pb ) .
(55)
⊤ Expanding both bilinear forms and cancelling the shared term x⊤ a WQ WK xb yields ⊤ ⊤ ⊤ ∆AAPE = x⊤ a WQ WK (pb+k − pb ) + (pa+k − pa ) WQ WK xb ⊤ ⊤ ⊤ + p⊤ a+k WQ WK pb+k − pa WQ WK pb .
(56)
Introduce u := pa+k and v := pb+k , and define ⊤ ⊤ ⊤ ⊤ S(u, v) := u⊤ WQ WK v + x ⊤ a WQ WK v + u WQ WK xb ⊤ ⊤ ⊤ ⊤ ⊤ − x⊤ a WQ WK pb + pa WQ WK xb + pa WQ WK pb .
(57)
Then perfect cancellation would require S(u, v) = 0. The leading term of S is the bilinear form ⊤ u⊤ WQ WK v =
d X d X
⊤ ui (WQ WK )ij vj .
(58)
i=1 j=1 ⊤ Since WQ WK ̸= 0, this is a nontrivial polynomial in (u, v) ∈ R2d . Therefore by the properties of real algebraic geometry [Mityagin, 2020], the zero set
{(u, v) ∈ R2d : S(u, v) = 0}
(59)
is a proper algebraic variety and has Lebesgue measure zero. Satisfying this exact cancellation for arbitrary sequence shifts k requires the positional embeddings to exhibit strict periodic symmetries or precise null-space alignments. Under generic parameterization of fully-trained dense neural networks, the parameters avoid this specific measure-zero algebraic variety almost everywhere. Hence ∆AAPE > 0
C.3
almost surely.
(60)
RoPE Equivariance under Sequence Translation
We provide the RoPE invariance argument used in the proof of Theorem 1. Under the translation operator Tk , the local attention kernel of RoPE is invariant: ∆ARoPE = 0. 17
Proof. Let xa , xb be translated from indices a, b to a + k, b + k. The translated RoPE kernel is ⊤ (b+k)−(a+k) eRoPE A = x⊤ WK xb a,b a W Q RΘ
(61)
⊤ b−a = x⊤ a WQ RΘ WK xb = ARoPE . a,b
(62) (63)
eRoPE ∆ARoPE = A = 0. − ARoPE a,b a,b
(64)
Therefore
C.4
Details of Assumption 2
We expand Assumption 2, which is used in the proof of Theorem 1. (i) Global smoothness. The underlying reasoning task admits an intrinsic structural smoothness scale satisfying Kbase = O(1/Tmax ). Because RoPE preserves relative position information exactly under sequence translations, it inherits this smoothness scale: KfRoPE ≤ O(1/Tmax ). (ii) Autoregressive sensitivity and Fragile Logit Margin. Let fAPE ∈ FL,m,APE . In formal combinatorial planning, generating a sequence operates as a deterministic Markov decision process. We assume that structurally critical routing steps (e.g., recursive backtrackings in deep subtrees) exhibit a fragile logit margin [Weng et al., 2023]. Let ∆margin > 0 denote the minimal pre-softmax logit separation required between the Bayes-optimal routing token a⋆ and competing incorrect tokens. For out-of-distribution reasoning trajectories with deep hierarchical structures, we assume this margin shrinks (∆margin → 0+ ). Consequently, any unmitigated Ω(1) local attention coordinate disruption (∆A > 0, as induced by APE translations) strictly exceeds this margin (∆A > ∆margin ), forcing the deterministic greedy decoding process to select an incorrect subtree. This irrevocably precludes reaching the target state, bounding the expected structural risk variation below by the deterministic separation margin: |LfAPE (χ′ ) − LfAPE (χ)| ≥ γ,
γ := 1 −
1 > 0. |V|
(65)
Routing separation under deterministic decoding. The constant γ is interpreted as a deterministic structural separation margin rather than as randomness arising from the decoding procedure. In our empirical setting, decoding is greedy; once the model parameters and input trajectory are fixed, the generated trajectory is deterministic. Thus the relevant question is not the probability of sampling an incorrect token, but whether a local attention-kernel perturbation changes the selected routing transition at a structurally critical step. Let a⋆ (z) denote the Bayes-optimal routing action at the critical transition of trajectory z, and let af (z) := arg max pf (a | hz ) a∈V
denote the action selected by the model under greedy decoding. Assumption 2 postulates that, at a structurally critical transition, the APE-induced coordinate perturbation changes the selected routing action away from the Bayes-optimal action: af (Tk z) ̸= a⋆ (z). Because the search task is evaluated by exact trajectory validity, this routing deviation sends the autoregressive process into an incorrect subtree and prevents the generated trajectory from reaching the target state. Hence the induced structural risk changes by a constant amount independent of Tmax : |LfAPE (χ′ ) − LfAPE (χ)| ≥ γ,
γ := 1 −
1 > 0. |V|
(66)
The normalization 1 − 1/|V| is a conservative positive margin. Under deterministic exact-match evaluation, the risk jump may be as large as 1; for the Lipschitz lower bound, it suffices that γ = Ω(1) is independent of Tmax . 18
C.5
Proof of Theorem 1
For completeness, we restate Theorem 1. For sufficiently large Tmax , let fAPE ∈ FL,m,APE and fRoPE ∈ FL,m,RoPE be two matched autoregressive Transformer models that differ only in their positional encoding scheme. Then KfRoPE = O(1/Tmax ),
KfAPE = Ω(1),
(67)
|LfAPE (u) − LfAPE (v)| . dX (u, v) u̸=v∈X
(68)
and hence KfRoPE ≪ KfAPE . Proof. By definition, KfAPE = sup
Let z ∈ Z be a trajectory whose translated sub-trajectory under Tk contains a critical routing step in the sense of Assumption 2(ii), and let χ = Φ(z),
χ′ = Φ(Tk (z)).
(69)
By Definition 2, the operator Tk inserts an inert node immediately before a local reasoning subtrajectory. By Lemma 2, this induces a nonzero local APE attention perturbation almost surely. Therefore Assumption 2(ii) applies, yielding |LfAPE (χ′ ) − LfAPE (χ)| ≥ γ. Hence KfAPE ≥
|LfAPE (χ′ ) − LfAPE (χ)| γ γ ≥ ≥ = Ω(1). dX (χ, χ′ ) δ Cδ
(70)
(71)
Assumption 2(i) gives KfRoPE ≤ O(1/Tmax ).
(72)
KfRoPE ≪ KfAPE .
(73)
Therefore, for sufficiently large Tmax ,
D
Proofs of Capacity Bounds
D.1
Structural Capacity Analysis
Definition 3 (Bayes-Optimal Structural Risk). The Bayes-optimal structural risk function is defined by L∗ (χ) := inf Ez∼µT [ℓ(h, z) | Φ(z) = χ] , χ ∈ X. (74) h
Definition 4 (Barron Space). Let X ⊂ R12 be compact. The Barron space HBarron (X ) consists of continuous functions g : X → R whose Fourier transform ĝ(ω) satisfies Z ∥ω∥1 |ĝ(ω)| dω < ∞. (75) R12
The infimum of this quantity defines the Barron norm ∥g∥B [Barron, 1993]. Assumption 3 (Tsybakov Margin Condition). There exist constants C > 0 and α ≥ 0 such that for the conditional label probability η(χ) := P(y = 1 | χ), νT |η(χ) − 1/2| ≤ t ≤ Ctα , ∀t > 0. Under this margin condition, the L1 (νT ) approximation error of the structural risk function translates into a lower bound on the induced trajectory-level zero-one risk, up to the residual ϵ. 19
Assumption 4 (Structural Capacity Mapping and Approximation Limit). We assume the following. (i) Barron regularity of the target risk. The Bayes-optimal structural risk belongs to the Barron space: L∗ ∈ HBarron (X ), 0 < ∥L∗ ∥B < ∞. (76) (ii) Finite-width structural hypothesis class. For each autoregressive Transformer f ∈ FL,m,PE , the induced structural risk function Lf belongs to a width-constrained hypothesis class Lf ∈ Hm ⊂ HBarron (X ),
(77)
where Hm denotes a structural approximation class whose capacity is controlled by the internal representation width m. (iii) Width-limited approximation lower bound. There exists a constant Cwidth > 0, independent of m, such that Z Cwidth . (78) inf |g(χ) − L∗ (χ)| dνT (χ) ≥ √ g∈Hm X m This scaling is consistent with approximation bounds for Barron-type function classes [Makovoz, 1996]. Assumption 4 formalizes the idea that projecting discrete trajectories into X induces a regression problem whose best attainable predictor cannot be approximated arbitrarily well at fixed width. D.1.1
Proof of Lemma 4
Proof. By Assumption 1, the true expected zero-one risk is bounded by the structural risk: Z RµT (f ) ≥ Lf (χ) dνT (χ) − ϵ.
(79)
X
In statistical learning theory, bridging continuous approximation errors in HBarron to discrete zeroone risk requires characterizing the target measure near the decision boundary. We invoke the Tsybakov Margin Condition (Assumption 3). Because formal combinatorial planning is an exactmatch, zero-tolerance domain (formalized by Markov compounding in Assumption 2), the structural routing maps deterministically to the trajectory outcome. This corresponds to the strict margin limit α → ∞. Under this deterministic mapping, the expected excess zero-one risk is lower-bounded linearly by the L1 continuous approximation error: Z Z Lf (χ) dνT (χ) ≥ Cmargin |Lf (χ) − L∗ (χ)| dνT (χ), (80) X
X
where Cmargin > 0 is an absolute constant dependent on the margin. Since Lf ∈ Hm , applying the universal approximation limits for Barron spaces [Makovoz, 1996] establishes that recovering the minimax-hard target function L∗ strictly incurs an irreducible absolute L1 error decaying at best via Ω(m−1/2 ). Thus: Z CB (81) |Lf (χ) − L∗ (χ)| dνT (χ) ≥ √ . m X width − ϵ. Defining Cwidth := Cmargin · CB and substituting this back yields RµT (f ) ≥ C√ m
D.2
Depth Bottleneck via Dyck-Type Reduction
We now give a more explicit formalization of the depth bottleneck underlying sequential backtracking. The central idea is that nested backtracking induces a Dyck-type dependency whose effective computational depth scales with the structural depth coordinate χ1 . D.2.1
DFS-to-Dyck Encoding
We give the detailed construction underlying Lemma 3. Let k denote the maximum branching factor of the search tree. We define the search transition alphabet (1)
(k)
(1) (k) Σsearch := {δdown , . . . , δdown } ∪ {δup , . . . , δup } ∪ {ωeval },
20
(82)
(c)
(c)
where δdown denotes expansion to the c-th child, δup denotes backtracking from the c-th child, and ωeval denotes terminal evaluation. Let ΣDyck = {(1 , )1 , . . . , (k , )k }, and let Dk ⊂ Σ∗Dyck denote the Dyck-k language [Strobl et al., 2024]. Define the map ψ : Σ∗search → Σ∗Dyck (83) pointwise by (c)
ψ(δdown ) = (c ,
(c) ψ(δup ) =)c ,
ψ(ωeval ) = ε.
(84)
Since ψ preserves concatenation, ψ(x ⊕ y) = ψ(x) ⊕ ψ(y) for all x, y ∈ Σ∗search , it is a monoid homomorphism.
Under valid DFS traversals, the image ψ(z) records the nested push-pop structure of backtracking as a balanced-parenthesis string. In particular, the maximum tree depth χ1 of the original search trajectory coincides with the maximum nesting depth of the Dyck-type string ψ(z). D.2.2
Complexity-Theoretic Interpretation and Finite Precision
Consider an autoregressive step t at which the next token corresponds to a backtracking move (c) vt+1 = δup . To emit this token correctly, the model must identify the most recent unmatched opening transition associated with the same branch type c. Under the encoding above, this is equivalent to resolving a nested Dyck-type dependency over the serialized search history. Parsing Dyck-language dependencies relies on maintaining a stack counter within the continuous hidden representations. For a Transformer utilizing bounded numerical precision with p bits (e.g., p = 16 for bfloat16), the capacity to reliably encode distinguishable nested states is informationtheoretically constrained by O(2p ). As demonstrated by Hahn [2020], bounded-precision attention heads cannot maintain precise counting mechanisms for arbitrarily deep hierarchical languages; evaluating a nested structure requires sequential reductions explicitly across the layers. This establishes a hard physical constraint: the maximum resolvable nesting depth χ1 scales linearly with the physical layer depth L. We instantiate this hardware-induced bottleneck via the truncation constant αcirc = c0 /p, where c0 > 0 is an architectural scaling factor and p is the numerical precision bit-width. This explicitly operationalizes the maximum parsable tree depth per physical layer. Assumption 5 (Implicit State-Transition Complexity via Dyck Structure). There exists a precisiondependent constant c > 0 such that resolving a backtracking transition of structural depth χ1 requires implicit computational depth at least Dimplicit ≥ c χ1 .
(85)
Equivalently, defining αcirc := c−1 , trajectories satisfying χ1 > αcirc L lie strictly beyond the implicit computational depth available within a single autoregressive forward pass. D.2.3
Failure Beyond the Implicit Depth Threshold
Define the severed region Xsevered := {χ ∈ X : χ1 > αcirc L} .
(86)
For trajectories in Xsevered , the model lacks sufficient implicit depth to resolve the required backtracking dependency. In this regime, the relevant routing decision can no longer be reliably distinguished from competing valid outputs, and we lower-bound the resulting structural risk by the uniformguessing baseline 1 . (87) Cdepth := 1 − |V| This motivates the truncation indicator Pimplicit (χ; L, αcirc ) := I(αcirc L,∞) (χ1 ), which records whether a structural state lies beyond the implicit depth threshold. 21
(88)
D.2.4
Proof of Lemma 5
1 For completeness, we restate Lemma 5. Let |V| ≥ 2, and define Cdepth := 1 − |V| ∈ (0, 1). Then for any autoregressive Transformer hypothesis f ∈ FL,m,PE , Z RµT (f ) ≥ Cdepth Pimplicit (χ; L, αcirc ) dνT (χ) − ϵ. (89) X
Proof. For χ ∈ Xsevered , Assumption 5 implies that the required implicit routing depth exceeds the available physical depth L. We therefore lower-bound the structural risk on this region by Lf (χ) ≥ Cdepth . (90) It follows that Z Z Z Lf (χ) dνT (χ) = X
Lf (χ) dνT (χ) + X
Lf (χ) dνT (χ)
(91)
X \Xsevered
Z severed ≥
Lf (χ) dνT (χ)
(92)
Xsevered
≥ Cdepth νT (Xsevered ). Since
(93)
Z νT (Xsevered ) =
Pimplicit (χ; L, αcirc ) dνT (χ),
(94)
X
we obtain
Z
Z Lf (χ) dνT (χ) ≥ Cdepth
X
Pimplicit (χ; L, αcirc ) dνT (χ).
(95)
X
Finally, Assumption 1 gives Z RµT (f ) ≥
Lf (χ) dνT (χ) − ϵ,
(96)
X
which yields the claim. D.2.5
Architecture-Invariance of the Physical Depth Limit
Lemma 6 (Architecture-Invariance of the Physical Depth Limit). The scalar αcirc is determined by the implicit computational requirement of the backtracking problem and is therefore independent of the positional encoding scheme. In particular, αAPE = αRoPE = αcirc . Proof. A single autoregressive forward pass applies exactly L sequential layers, regardless of whether the positional encoding is APE or RoPE. RoPE may preserve relative position information, but it does not introduce additional sequential computational steps beyond the available physical depth. Therefore the same implicit depth threshold governs both positional-encoding choices.
E
Proof of the Main Theorem and Corollaries
E.1
Proof of Theorem 2
For completeness, we restate Theorem 2. For any autoregressive Transformer hypothesis f ∈ FL,m,PE , the target risk satisfies ( ) Z Cwidth √ RµT (f ) ≥ max −ϵ, Cdepth Pimplicit (χ; L, αcirc ) dνT (χ)−ϵ, RµS (f )−Kf,PE W1 (νS , νT )−2ϵ . m X (97) C√ width Proof. Lemma 4 gives RµT (f ) ≥ − ϵ. Lemma 5 gives RµT (f ) ≥ m R Cdepth X Pimplicit (χ; L, αcirc ) dνT (χ) − ϵ. Finally, Lemma 1 implies |RµT (f ) − RµS (f )| ≤ Kf,PE W1 (νS , νT ) + 2ϵ, and therefore RµT (f ) ≥ RµS (f ) − Kf,PE W1 (νS , νT ) − 2ϵ. We note that each lower bound is derived independently and holds simultaneously for any f ∈ FL,m,P E . Therefore, the tightest valid lower bound is given by their maximum. Hence RµT (f ) is bounded below by each of the three displayed quantities.
22
E.2
Proof of Corollary 1
For completeness, we restate Corollary 1. Assume the source risk satisfies RµS (fRoPE ) = ϵtrain ≈ 0, and suppose the target shift satisfies W1 (νS , νT ) = Ω(Tmax ). Then the RoPE upper estimate remains bounded: RµT (fRoPE ) ≤ ϵtrain + CRoPE + 2ϵ for some finite constant CRoPE independent of Tmax . In contrast, suppose there exists a measurable subset Xshift ⊂ X such that νT (Xshift ) = pshift > 0 and LfAPE (χ) ≥ γ for all χ ∈ Xshift , where γ = Ω(1). Then RµT (fAPE ) ≥ γpshift − ϵ. In particular, if ϵ ≪ γpshift , the APE target risk admits a non-vanishing lower bound. Proof. For RoPE, Lemma 1 gives RµT (fRoPE ) ≤ RµS (fRoPE ) + KfRoPE W1 (νS , νT ) + 2ϵ.
(98)
By Theorem 1, KfRoPE = O(1/Tmax ). Since W1 (νS , νT ) = Ω(Tmax ) and, independently, W1 (νS , νT ) is bounded above by the diameter of X , the product KfRoPE W1 (νS , νT ) remains bounded by a finite constant, denoted CRoPE . Substituting RµS (fRoPE ) = ϵtrain gives RµT (fRoPE ) ≤ ϵtrain + CRoPE + 2ϵ. For APE, Assumption 1 yields Z RµT (fAPE ) ≥
LfAPE (χ) dνT (χ) − ϵ.
(99)
X
Restricting the domain of integration to Xshift and using the assumed lower bound on LfAPE gives Z RµT (fAPE ) ≥ LfAPE (χ) dνT (χ) − ϵ (100) Xshift Z γ dνT (χ) − ϵ (101) ≥ Xshift
= γ νT (Xshift ) − ϵ = γpshift − ϵ.
E.3
(102) (103)
Proof of Corollary 2
For completeness, we restate Corollary 2. Suppose the target measure assigns positive mass to trajectories whose structural depth exceeds the available implicit computation threshold: pdeep := νT({χ ∈ X : χ1 > αcirc L}) > 0. Then the depth bottleneck contributes the non-vanishing lower width bound RµT (f ) ≥ Cdepth pdeep − ϵ. In contrast, the width-based term C√ − ϵ vanishes as m → ∞. m 1 Moreover, if L ≥ αcirc supχ∈supp(νT ) χ1 , then νT({χ ∈ X : χ1 > αcirc L}) = 0, so the depth bottleneck term is eliminated on the support of νT . Proof. By Lemma 5, Z RµT (f ) ≥ Cdepth
Pimplicit (χ; L, αcirc ) dνT (χ) − ϵ.
(104)
X
Since Pimplicit (χ; L, αcirc ) = I(αcirc L,∞) (χ1 ), we have Z Pimplicit (χ; L, αcirc ) dνT (χ) = νT({χ ∈ X : χ1 > αcirc L}) = pdeep ,
(105)
X
which gives RµT (f ) ≥ Cdepth pdeep − ϵ. On the other hand,
Cwidth √ − ϵ = −ϵ ≤ 0, m→∞ m so the width-only contribution cannot sustain a non-vanishing lower bound. lim
(106)
1 Finally, if L ≥ αcirc supχ∈supp(νT ) χ1 , then no point in supp(νT ) satisfies χ1 > αcirc L. Hence νT({χ ∈ X : χ1 > αcirc L}) = 0, which eliminates the depth bottleneck term on the target support.
23
F
Algebraic Equivalence Classes of Positional Encodings
Recent empirical studies frequently benchmark a wide array of positional encoding variants, including ALiBi [Press et al., 2022], T5 Relative Bias, and No Positional Encoding (NoPE) [Kazemnejad et al., 2023]. In this work, our theoretical framework selectively isolates Absolute Positional Encoding (APE) and Rotary Position Embedding (RoPE). This isolation is not an empirical omission, but a rigorous theoretical necessity driven by algebraic equivalence classes. In the context of the structural Lipschitz gap (Theorem 1), the generalizability of an attention mechanism under sequence coordinate translations (Tk ) is strictly determined by whether its attention kernel Ai,j satisfies shift invariance. Positional encodings partition the architectural hypothesis space into two distinct algebraic equivalence classes: 1. Position-Dependent Attention Kernels: This class contains mechanisms where Ai,j depends explicitly on the absolute indices i and j. Standard learned APE and Sinusoidal encodings belong strictly to this class. As proven in Lemma 2, any member of this equivalence class inherently fails to preserve shift invariance, causing the computational graph to differ under translations. This guarantees a macroscopic Lipschitz constant Kf = Ω(1). 2. Shift-Invariant Attention Mechanisms: This class encapsulates mechanisms where the attention kernel depends strictly on the relative distance i−j. RoPE, ALiBi, and T5 Relative Bias all structurally adhere to this mathematical constraint. Consequently, for any mechanism in this equivalence class, the translation operator yields ∆A = 0. By mathematical extension, any valid relative encoding automatically inherits the baseline structural smoothness O(1/Tmax ) established in Theorem 1. We designate RoPE as the standardized representative for the shift-invariant class due to its mathematically elegant multiplicative orthogonal rotation matrices (Rj−i Θ ), which facilitate exact algebraic proofs without relying on the heuristic scalar penalties employed by ALiBi. Because ALiBi and T5 Bias share the identical shift-invariant algebraic signature as RoPE, empirically evaluating them would yield theoretically redundant O(1/Tmax ) bounds, offering no supplementary mathematical insight into the Lipschitz continuity gap. Finally, No Positional Encoding (NoPE) presents a trivial edge case. While NoPE strictly satisfies mathematical shift invariance (as ∆ANoPE ≡ 0 trivially without positional vectors), the absence of positional priors forces the model to recover structural routing information entirely implicitly via causal masking. As established by Kazemnejad et al. [2023], this implicit recovery completely degenerates under OOD sequence lengths. Therefore, NoPE fails not due to Lipschitz divergence, but due to a catastrophic collapse in the functional approximation limits within the Barron space (Lemma 4), rendering it orthogonal to our translation equivariance analysis.
G
Estimation of Structural Wasserstein Distances
The theoretical bounds in Theorem 2 are stated in terms of the exact Wasserstein-1 distance W1 (νS , νT ) between structural pushforward measures. In the empirical analysis, we estimate this quantity from finite samples using entropically regularized optimal transport. Accordingly, the c1,λ , rather than reported values should be interpreted as empirical regularized estimates, denoted by W exact evaluations of the population-level W1 . We compute these estimates using the Sinkhorn–Knopp algorithm with regularization parameter λ = 0.1 [Cuturi, 2013]. G.1
Computational Pipeline
Let ν̂S and ν̂T denote the empirical structural measures obtained by sampling trajectories from the source and target distributions and applying the structural projection Φ. The estimation pipeline consists of the following steps. Joint standardization. The structural coordinates have different numerical scales; for example, the search-volume coordinate χ4 can be orders of magnitude larger than transition-rate coordinates such as χ5 , χ6 , χ7 . To prevent the Euclidean cost from being dominated by large-scale coordinates, we apply Z-score normalization to each coordinate. The normalization statistics are computed on the 24
pooled set of structural vectors from all compared distributions, so that the relative shifts between distributions are preserved under a common scaling. Cost matrix construction. For standardized structural vectors ui , v j ∈ R12 , we define the empirical cost matrix by Mij = ∥ui − v j ∥2 . (107) For numerical stability in the Sinkhorn iterations, we rescale the cost matrix as fij = M
Mij . maxi,j Mij + 10−9
(108)
This places all empirical transport costs on a common normalized scale. Entropic regularization.
With uniform marginal weights p = q = N −1 1, we compute c1,λ (ν̂S , ν̂T ) = W
f F − λH(P), min ⟨P, M⟩
P∈Π(p,q)
(109)
where Π(p, q) is the set of couplings with marginals p and q, ⟨·, ·⟩F is the Frobenius inner product, and H(P) is the discrete entropy of the coupling matrix. We use the Python Optimal Transport library to solve this regularized problem [Flamary et al., 2021]. Subsampling. The full trajectory dataset contains 500,000 trajectories, making all-pairs cost-matrix construction expensive. For each distribution, we first form a candidate pool of 20,000 trajectories and then sample N = 2000 trajectories without replacement for each pairwise distance computation. We repeat this procedure across independent subsamples to assess stability. G.2
Robustness and Interpretation
Because the empirical cost matrix is normalized, the reported distances lie on a normalized scale and should be interpreted comparatively across distribution pairs. Across repeated subsampling runs, the in-distribution comparison remains near zero, while the mixed and DFS target distributions produce larger shifts. Specifically, we observe c1,λ (νBF S , νBF S ) ≈ 0.05, W
c1,λ (νBF S , νM IXED ) ≈ 0.40, W
c1,λ (νBF S , νDF S ) ≈ 0.80. W
These values are used as empirical proxies for the structural domain shifts appearing in the main text. The separation between the three regimes suggests that the structural feature space X captures the intended macroscopic differences between BFS, Mixed, and DFS trajectory distributions. G.3
Empirical Calibration of the Theoretical Ceiling
In Figure 1A, we visualize the empirical accuracy of the evaluated architectures against the TC0 depth capacity bottleneck. The reviewer may rightfully inquire how the “Theoretical Ceiling” is mathematically derived and parameterized. By Theorem 2, the expected target risk on deeply recursive structures (µDF S ) is strictly lowerbounded by the depth penalty: Z RµDF S (f ) ≥ Cdepth Pimplicit (χ; L, αcirc ) dνDF S (χ) − ϵ. (110) X
Because empirical accuracy is defined as 1 − RµT (f ), this expected risk lower bound rigorously establishes an empirical accuracy upper bound (the theoretical ceiling). Under the macroscopic structural projection Φ, the tail probability measure of the nesting depth χ1 decays exponentially. Consequently, the integral of the truncation indicator Pimplicit decays exponentially as a function of the physical layer depth L. To instantiate this bound without relying on vacuous constants, we formulate the theoretical ceiling as: Accuracymax (L) = Amax − β · exp(−α · L) (111) where Amax = 1 − ϵ represents the asymptotic empirical optimum, and β, α > 0 strictly depend on the target distribution’s structural depth variance and the finite-precision scalar αcirc . 25
To ensure strict mathematical validity, we performed a Pareto Infimum Calibration. Rather than fitting an average regression line (which would violate the nature of a bounding theorem), we calibrated the constants (Amax ≈ 0.538, β ≈ 0.045, α ≈ 0.15) such that the curve acts as the strict supremum envelope for all 54 evaluated architectures. As vividly demonstrated in Figure 1A, every empirical data point resides strictly below this theoretical ceiling, yielding zero bound violations. This explicitly confirms that the TC0 truncation limit acts as a hard algorithmic boundary that parameter count (width) scaling cannot bypass.
H
Supplementary Empirical Analyses
H.1
The Mitigating Power of Translation Equivariance
In Section 5 of the main text, we asserted that the inherent structural smoothness provided by Rotary Position Embeddings (RoPE) acts as a continuous structural regularizer, partially mitigating the discrete TC0 routing limitation imposed by deep recursive backtracking (µDF S ). To explicitly isolate this phenomenon, Figure 2 visualizes the performance trajectories of Large and Medium scale models trained and evaluated exclusively on the µDF S distribution. 0.5180
$ 0 L W L J D W L Q J W K H TC0 % R W W O H Q H F N / D U J H 6 F D O H
Positional Encoding
0.5145
$ F F X U D F \ R Q DFS
APE ROPE
0.5115
$ F F X U D F \ R Q DFS
% & R Q V L V W H Q W ( T X L Y D U L D Q F H 5 H J X O D U L ] D W L R Q 0 H G L X P 6 F D O H
Positional Encoding
: L G H0.4835 /
% D O D Q F H G / $ U F K L W H F W X U D O $ V S H F W 5 D W L R
APE ROPE ' H H S /
: L G H /
% D O D Q F H G / $ U F K L W H F W X U D O $ V S H F W 5 D W L R
' H H S /
Figure 2: Empirical verification of structural regularization via translation equivariance on µDF S . (A) Large Scale Models: Under Absolute Positional Encoding (APE, red dashed line), the architecture is strictly constrained by the TC0 depth bottleneck, requiring an increase in physical layer depth (L = 12 → L = 48) to resolve the Dyck-k dependency (accuracy improves from 0.4835 to 0.5115). Conversely, RoPE (blue solid line) inherently preserves local sequence equivariance, mitigating the need for excess capacity. Because Wide RoPE (L = 12) achieves 0.5180, the fundamental TC0 limit is proven to be ≤ 12 layers. The failure of Wide APE (L = 12) at 0.4835 is thus driven by its Ω(1) Lipschitz penalty, which forces the architecture to demand redundant physical depth (L = 48) to memorize absolute-position-dependent routing. RoPE, by maintaining continuous translation equivariance, avoids this capacity inflation, allowing the minimal theoretical depth to succeed. As predicted by our measure-theoretic capacity bounds, APE architectures (red dashed lines) are fundamentally trapped by the TC0 circuit depth bottleneck. For the Large APE configurations (Panel A), transitioning from a Wide architecture (L = 12) to a Deep architecture (L = 48) is a necessary prerequisite to correctly route the DFS backtracking, yielding a monotonic accuracy increase from 0.4835 to 0.5115. This confirms that without relative equivariance, depth separation theorems strictly govern autoregressive reasoning capacities. In stark contrast, integrating RoPE mathematically flattens this trajectory. As proven in Lemma 6, RoPE and APE possess identical theoretical expressivity limits (αcirc ). However, without relative equivariance, APE architectures suffer from catastrophic Lipschitz divergence before saturating their true capacity, forcing a reliance on extreme depths (L = 48) to provide implicit routing redundancy. By preserving structural shift invariance, RoPE smooths the optimization landscape and circumvents these coordinate disruptions. Strikingly, the Large Wide DFS RoPE configuration achieves a superior accuracy of 0.5180, compared to 0.5145 for its Deep counterpart. This visual evidence provides rigorous empirical support for our theoretical claim: translation equivariance acts as a structural 26
regularizer that permits the architecture to gracefully reach its true expressivity bounds without premature structural collapse. H.2
Baseline Capacity and Structural Variance
Before isolating the distinct computational boundaries of layer depth and representation width, we provide a macroscopic overview of the baseline hypothesis capacity across our experimental grid. Figure 3 visualizes the aggregated in-distribution performance (where νT = νS ) across all three parameter scales and measures. A critical observation from this macroscopic view is the presence of structural variance, denoted by the standard deviation error bars. Because each bar aggregates the performance of the Deep, Wide, and Balanced variants within a fixed parameter budget, the magnitude of the error bar strictly represents the model’s sensitivity to the computational graph’s aspect ratio. $ 6 P D O O 6 F D O H 0 3 D U D P V
( P S L U L F D O , Q ' L V W U L E X W L R Q $ F F X U D F \
% 0 H G L X P 6 F D O H 0 3 D U D P V
% ) 6
0 , ; ( '
7 D U J H W 0 H D V X U H T = S
' ) 6
% ) 6
0 , ; ( '
7 D U J H W 0 H D V X U H T = S
' ) 6
& / D U J H 6 F D O H 0 3 D U D P V 3 R V L W L R Q D O ( Q F R G L Q J
$ 3 ( 5 2 3 (
% ) 6
0 , ; ( '
7 D U J H W 0 H D V X U H T = S
' ) 6
Figure 3: Comprehensive baseline performance and structural variance across the experimental grid. Evaluated in-distribution (νT = νS ), the bars represent the mean empirical accuracy across different architectural aspect ratios (Deep, Wide, Balanced), while the error bars denote the ±1 standard deviation. The structural variance (error bar magnitude) highlights the architectural sensitivity to the computational graph shape. Notably, on deep sequential tasks (µDF S ), the large variance under APE confirms that aspect ratio dominates performance, whereas RoPE explicitly compresses this variance across all parameter scales, empirically confirming its role as a stable structural regularizer. As evident in Figure 3, the structural variance under Absolute Positional Encoding (APE, red bars) is exceptionally high, particularly on the deeply recursive µDF S measure across Medium and Large scales. This high variance empirically confirms that under absolute sequence coordinates, the raw parameter count is insufficient to guarantee convergence; performance is highly sensitive to whether the aspect ratio satisfies the specific TC0 truncation thresholds (i.e., whether the network is sufficiently Deep). Conversely, Rotary Position Embedding (RoPE, blue bars) exhibits substantially compressed error bars across nearly all distributions and scales. By introducing translation equivariance, RoPE significantly dampens the architecture’s sensitivity to the discrete layout of the computational graph. This aggregated perspective provides robust, large-scale corroboration of our core theoretical finding: preserving local structural equivariance acts as a continuous structural regularizer, elevating the lower bounds of empirical performance regardless of the specific depth-to-width ratio deployed.
I
Experimental Details and Reproducibility
To ensure the full reproducibility of our empirical results and structural metrics, we detail the exact computational environment, architectural implementations, and optimization regimens corresponding to the 54 Transformer configurations evaluated in Section 5. I.1
Compute Infrastructure and Environment
All experiments, including dataset generation, model training, and trajectory evaluations, were executed on a high-performance Linux cluster. The hardware infrastructure comprises nodes equipped with 8× NVIDIA A100 (80GB) Tensor Core GPUs. Job scheduling was managed via Slurm. 27
Specifically, each individual model training run was allocated a dedicated environment consisting of 1 NVIDIA A100 GPU, 8 CPU cores, and 48 GB of system RAM, with a maximum wall-clock time limit of 24 hours. The evaluation pipeline was allocated 1 NVIDIA A100 GPU, 8 CPU cores, and 40 GB of system RAM. The software environment was built upon Python 3.10, PyTorch 2.1+, and the Hugging Face transformers library, accelerated by accelerate and FlashAttention-2 [Dao, 2023]. To guarantee strict computational determinism during evaluation, PyTorch CuDNN backends were explicitly set to deterministic mode (torch.backends.cudnn.deterministic = True). I.2
Architectural Implementations
To strictly isolate the positional encoding variable (P E ∈ {APE, RoPE}), we mapped the architectures to their respective native implementations in the Hugging Face library: • APE Configurations: Evaluated using the GPTNeoForCausalLM architecture. The absolute positional embeddings were configured up to the maximum context length (1024). Global attention patterns were strictly enforced across all layers (i.e., attention_types=[[["global"], n_layer]]) to prevent confounding effects from sliding-window or local attention approximations. • RoPE Configurations: Evaluated using the GPTNeoXForCausalLM architecture, which natively supports rotary mappings. We strictly configured the rotary percentage to 1.0 (applying RoPE to all attention head dimensions) and disabled parallel residual connections (use_parallel_residual=False) to ensure the structural computational graph strictly mirrored the APE baseline, isolating translation equivariance as the sole independent variable. Both architectural families utilized the GELU activation function and vocabulary dimension |V| = 50, 257. During training, memory efficiency was maximized by enabling gradient checkpointing (gradient_checkpointing=True), which implicitly disables key-value caching during the forward pass. Computations were uniformly executed in bfloat16 mixed precision to prevent numerical overflow while accelerating matrix multiplications. I.3
Optimization Regimen
All 54 configurations were trained from scratch under a strictly unified hyperparameter configuration to ensure unbiased capacity comparisons: • Data & Context: The models were trained on 500,000 trajectories per target measure. The maximum sequence length was strictly truncated and padded to Tmax = 1024. • Loss Function: Standard causal language modeling (next-token prediction) using crossentropy loss. Padding tokens were explicitly ignored during loss computation by overriding their labels to −100. • Batch Size: The per-device batch size was set to 4, coupled with 8 gradient accumulation steps. This yielded a strictly controlled effective batch size of 32 trajectories per optimization step across all runs. • Learning Rate & Optimizer: We utilized the AdamW optimizer with a unified peak learning rate of η = 8 × 10−5 across all scales (Small, Medium, Large). The learning rate followed a linear warmup schedule for the first 1, 000 steps, decaying subsequently. Weight decay was uniformly set to 0.01. • Epochs & Seeds: All models were trained for exactly 3 full epochs. To prevent stochastic artifacts, the global random seed for data shuffling and weight initialization was strictly fixed to 42 (random.seed(42), torch.manual_seed(42)). I.4
Evaluation Protocol
During the empirical evaluation phase, the models were evaluated on held-out validation sets comprising 2,000 trajectories per structural measure (νBF S , νDF S , νM IXED ). The autoregressive generation was prompted identically using the initial problem state: <|endoftext|>Current State: [Target]:[Nums], Operations:[]. 28
To rigorously assess the structural fidelity of the learned models without introducing stochastic sampling variance, we employed strict greedy decoding (do_sample=False, num_beams=1) with a maximum new token generation length of 512. Evaluation was executed in parallel with a batch size of 32. The generated sequences were subsequently parsed by a deterministic scoring function that verified the mathematical validity of the final trajectory against the target state, yielding the zero-one loss expected risk RµT (f ) reported in Section 5.
J
Code Availability
https://github.com/Yyuzrah/AMTA4R
29