Paper deep dive
Exact-Solution Volume and Length Generalization in Transformers
Yijia Jessica Zhu, David Chiang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/13/2026, 4:04:24 AM
Summary
This paper introduces Normalized Exact-Solution Volume (NESV) to analyze the length generalization capabilities of single-layer transformers. By deriving asymptotic bounds for NESV across four tasks (First, Majority, Index, Parity), the authors demonstrate that faster decay in solution volume correlates with poorer length generalization. Specifically, the Index task exhibits a volume decay of $\Theta(n^{-3})$, leading to poor extrapolation. The authors propose a structural modification to the transformer model (normalized positional model) that eliminates a quadratic error term, improving the NESV bound to $\Theta(n^{-1})$ and increasing empirical accuracy at 10x training length from 60% to 85%.
Entities (8)
Relation Signals (7)
Majority Task → hasnesvbound → Theta(1/(n log n))
confidence 98% · MAJORITY (Theta(1/(n log n)))
Index Task → hasnesvbound → Theta(n^-3)
confidence 98% · Under the positional model A_pos, the NESV for Index is Theta(n^-3)
First Task → hasnesvbound → Theta(1)
confidence 98% · FIRST (Theta(1))
Parity Task → hasnesvbound → 0
confidence 98% · PARITY (0)
Normalized Positional Model → improvesnesvboundfor → Index Task
confidence 95% · The NESV improves from Theta(n^-3) to Theta(n^-1)... empirically achieving 85% accuracy... compared with the 60% accuracy of the original model.
Normalized Exact-Solution Volume → measures → Length Generalization Difficulty
confidence 95% · the faster the exact-solution volume decays with input length, the harder it is to length-generalize on that task.
Transformer → usedfor → Index Task
confidence 90% · We study a transformer model that would structurally eliminate one of the terms... for Index
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Research on transformer expressivity shows whether a transformer is capable of solving a given task, but gives little indication of whether the solution, if learned, is generalizable to longer input lengths. We study this question through normalized exact-solution volume (NESV): the fraction of a bounded parameter region that achieves an exact solution on every input of length $n$. For fixed-width, single-layer transformers with $\log n$-scaled attention, we establish asymptotic bounds on NESV for four tasks: FIRST ($\Theta(1)$), MAJORITY ($\Theta(1/(n\log n))$), INDEX ($\Theta(1/n^3)$), and PARITY ($0$). These results are consistent with previous empirical results: the faster the exact-solution volume decays with input length, the harder it is to length-generalize on that task. Looking deeper into INDEX, our volume analysis reveals two error sources that grow with $n$. Consequently, we study a transformer model that would structurally eliminate one of the terms, theoretically improving the NESV bound to $\Theta(n^{-1})$, and empirically achieving 85% accuracy when tested at $10\times$ the training length, compared with the 60% accuracy of the original model. We conclude that volume analysis may be a useful approach to identify concrete sources of length sensitivity and thus provide insights into task-specific model refinements.
Tags
Links
- Source: https://arxiv.org/abs/2610.07676v1
- Canonical: https://arxiv.org/abs/2610.07676v1
Trouble viewing inline? Open PDF directly →
Full Text
99,448 characters extracted from source content.
Expand or collapse full text
Exact-Solution Volume and Length Generalization in Transformers Yijia Jessica Zhu David Chiang Affiliation: University of Notre Dame Email: yzhu26,dchiang@nd.edu Abstract Research on transformer expressivity shows whether a transformer is capable of solving a given task, but gives little indication of whether the solution, if learned, is generalizable to longer input lengths. We study this question through normalized exact-solution volume (NESV): the fraction of a bounded parameter region that achieves an exact solution on every input of length n. For fixed-width, single-layer transformers with logn n-scaled attention, we establish asymptotic bounds on NESV for four tasks: First (Θ(1) (1)), Majority (Θ(1/(nlogn)) (1/(n n))), Index (Θ(1/n3) (1/n^3)), and Parity (00). These results are consistent with previous empirical results: the faster the exact-solution volume decays with input length, the harder it is to length-generalize on that task. Looking deeper into Index, our volume analysis reveals two error sources that grow with n. Consequently, we study a transformer model that would structurally eliminate one of the terms, theoretically improving the NESV bound to Θ(n−1) (n^-1), and empirically achieving 85% accuracy when tested at 10×10× the training length, compared with the 60% accuracy of the original model. We conclude that volume analysis may be a useful approach to identify concrete sources of length sensitivity and thus provide insights into task-specific model refinements. 1 Introduction Theoretical work on the expressivity of transformers (cf. the survey by Strobl et al., 2024) can be seen as a prelude to the study of learnability by transformers, since the existence of a transformer and parameters that solve a given problem is a prerequisite for a transformer to learn to solve the problem. But the existence of a single point in parameter space does not tell us much about whether that point is actually learnable. In this paper, following Kover et al. (2026), we ask a more difficult question: given that a problem is solvable by a transformer with some parameters, how large is the set of successful parameters? While Kover et al. (2026) arrived at somewhat pessimistic conclusions, we look at single-layer transformers with logn n-scaling and find that, the volume of the set of successful parameters, as a function of the sequence length n, provides a way to quantify the difficulty of length-generalization in various problems. The drive for looking beyond expressivity is also visible in experiments on simple sequence tasks. Chiang and Cholak (2022) construct exact transformers for First (whether the first symbol is a 1) and Parity (whether the number of 1’s is odd), but report that standard training fails on Parity, and that First does not necessarily extrapolate to longer inputs without logn n-scaling. Hahn and Rofin (2024) report that fitted Parity solutions become much sharper as input length grows than fitted solutions for First and Majority (whether there are more 1’s than 0’s). Thus, tasks that are all expressible can behave differently under training and length extrapolation. Such findings motivate examining the geometry of the parameter sets that implement a task. In related work on loss landscapes, Chiang et al. (2023) argue that the geometry and volume of low-loss regions can explain part of neural-network generalization without relying entirely on the implicit bias of gradient descent. We study a related exact-solution quantity at each finite input length. For a fixed task and architecture, we restrict the trainable parameters to a bounded region and measure the fraction that correctly solves the task on every input of length n. We call this quantity the normalized exact-solution volume (NESV). Its dependence on n describes how the full set of exact solutions changes as the computation is required to handle longer inputs. With uniform sampling over the bounded parameter region, this is the probability of sampling an exact solution. Comparing this baseline with empirical training results can help distinguish the effects of initialization and optimization from the nature of the task and the selected transformer model in terms of learnability. We consider four binary classification tasks on binary strings. First returns the first input symbol, whereas Index returns the symbol at a position specified by one of the input tokens. Majority returns whether more than half of input symbols are 1’s, whereas Parity returns whether the number of 1’s is odd. We refer to the first pair as positional tasks, and the second pair as counting tasks. We conduct our analyses on the simplest models suited to solve the corresponding problems. In all cases, we only consider single-layer transformers. For the positional tasks, we use a model with positional encoding (j, j2j^2) where the Query and Key maps only depend on token positions and the Value map only depends on the tokens themselves (following the form of the construction of Bhattamishra et al. (2024)). For the counting tasks, the positions of the tokens are irrelevant, so we primarily use a model without positional encoding. We also examined a model with sinusoidal positional encoding (sin(j) (j), cos(j) (j)). See Table 1 for a summary of the asymptotic bounds obtained with respect to input length n. Under the positional model posA_pos, the NESV for Index is Θ(n−3) (n^-3), while First has constant NESV. The sinusoidal model sinA_sin has volume 00 for both. Under the position-free model genA_gen, the NESV for Majority is Θ(1/(nlogn)) (1/(n n)). Under the sinusoidal model sinA_sin, the NESV for Majority is instead Θ(1/(n3logn)) (1/(n^3 n)). Parity has a zero NESV whenever n>h+1n>h+1 for both models, h being the width of the transformer. This is a direct consequence of the standard one-dimensional capacity of shallow ReLU networks (Arora et al., 2018) in the finite-length setting, and is consistent with the broader result that no one-layer, one-head transformer computes Parity across all lengths (Kozachinskiy et al., 2026b). We train those tasks under the same protocol. The empirical results are in line with our NESV analysis: the task-model pair whose NESV shrinks faster as n grows shows worse length generalization. The only counterexample was that, under the general sinusoidal model, MAJORITY trains as well as under the position-free model genA_gen, although the former’s volume shrinks faster with n. Table 1: NESV bounds and mean accuracy at 10×10× the maximum training length for the four tasks. The models genA_gen, sinA_sin, and posA_pos are described in Section 2.2, while normA_norm is described in Section 4.2. Task Model Positional (posA_pos) General (genA_gen) Sinusoidal (sinA_sin) Normalized (normA_norm) NESV Acc. (%) NESV Acc. (%) NESV Acc. (%) NESV Acc. (%) First Θ(1) (1) 100.0 00 51.12 00 55.06 Θ(1) (1) 100.0 Majority — 92.7 Θ((nlogn)−1) ((n n)^-1) 82.6 Θ((n3logn)−1) ((n^3 n)^-1) 87.5 — 92.7 Index Θ(n−3) (n^-3) 59.6 00 51.9 00 50.2 Θ(n−1) (n^-1) 85.1 Parity 00 — 00 — 00 — 00 — Among the tasks we examine, Index demonstrates particularly bad length generalization (60% average accuracy at ten times training length) despite being expressible (Kozachinskiy et al., 2026a). Our NESV analysis reveals the underlying mechanisms. Exact retrieval of a designated position k requires that position to receive enough attention, so its attention score must remain within a constant of the maximum attention score. Expressing the difference in attention scores between neighboring positions as a function of k reveals two key error components, one proportional to k2k^2 and another proportional to k, which are the sources of failing length generalization. Guided by this analysis, we modify the model so that the error term proportional to k2k^2 no longer grows with input length. This is called the normalized positional model. The NESV improves from Θ(n−3) (n^-3) to Θ(n−1) (n^-1). In our experiments, the modified model also generalizes substantially better on Index, achieving an average accuracy of 85% percent at ten times the training length. Taken together, the results show that expressivity alone can conceal qualitatively different parameter-space behavior. Volume analysis, on the other hand, may offer another useful tool to further identify the computational constraints responsible for learning behaviors and offer insight for task-specific model refinements. 2 Setup In this section, we describe the tasks to be analyzed and the transformers to be used in the analysis. 2.1 Tasks and exact-solution volume For n≥1n≥ 1, write [n]=1,…,n[n]=\1,…,n\ and let w=(w1,…,wn)∈0,1nw=(w_1,…,w_n)∈\0,1\^n. We study Firstn(w) First_n(w) =w1 =w_1 Indexn(w,k) Index_n(w,k) =wk,k∈[n], =w_k, k∈[n], Majorityn(w) Majority_n(w) =∑j=1nwj≥n+12for odd n, =1 \ _j=1^nw_j≥ n+12 \ odd n, Parityn(w) Parity_n(w) =(∑j=1nwj)mod2. = ( _j=1^nw_j ) 2. For Index, the n tokens w1,…,wnw_1,…,w_n, which we call data tokens, are followed by a single token, which we call the index token, encoding k. We refer to this as right-hand sequence Indexing. For the other tasks, there is an index token for consistency’s sake, but it is fixed. Definition 1 (Normalized exact-solution volume, NESV). For a task T and transformer model A, let SnT,S_n^T,A be the parameters for which the output is strictly correct on every length-n input, and on every index k. For a fixed parameter bound B>0B>0, define VBT,(n)=λD(SnT,∩[−B,B]D)(2B)D.V_B^T,A(n)= _D_A (S_n^T,A∩[-B,B]^D_A )(2B)^D_A. (1) Equivalently, (1) is the probability of obtaining a correct solution when each scalar parameter is sampled independently and uniformly from [−B,B][-B,B]. Unless stated otherwise, B and the hidden width of the FFNN, h, are fixed as n grows. Throughout, log denotes the natural logarithm; ‖⋅‖2\| ·\|_2 and ‖⋅‖∞\| ·\|_∞ denote the Euclidean and maximum-coordinate norms. Throughout, c,C>0c,C>0 and the constants implicit in the subscripted asymptotic notation such as ΘB,h _B,h may depend on B and h, but never on n; c, C may change from line to line. 2.2 Transformer Models We consider only single-layer transformers. Let xjx_j denote the j-th data token and let z denote the index token. The query, key, and value maps have the form Q(x)=WQx+bQ,K(x)=WKx+bK,V(x)=WVx+bV.Q(x)=W_Qx+b_Q,K(x)=W_Kx+b_K,V(x)=W_Vx+b_V. Writing q=Q(z),kj=K(xj),vj=V(xj)q=Q(z),k_j=K(x_j),v_j=V(x_j), the attention output is αj=exp((logn)q⊤kj)∑i=1nexp((logn)q⊤ki),A=∑j=1nαjuj. _j= \! (( n)q k_j ) _i=1^n \! (( n)q k_i ), A= _j=1^n _ju_j. (2) The logn n factor was proposed by Chiang and Cholak (2022) and Nakanishi (2025) and has been used in practice in Qwen (Bai et al., 2023). Chen et al. (2026) provide additional theoretical justification for this choice. In this paper, this choice is natural since we study positional tasks such as Index, where attention must continue to select a particular position as the number of competing positions grows with the input length. We omit the 1/d1/ d factor in conventional logn n scaling because d is constant in n and does not affect the asymptotic bounds in n. The self-attention is followed by a feed-forward network (FFNN) classifier with hidden width h: y=W2ReLU(W1A+b1)+b2∈ℝ2,y=W_2ReLU(W_1A+b_1)+b_2 ^2, (3) where W1∈ℝh×2,b1∈ℝh,W2∈ℝ2×h,b2∈ℝ2W_1 ^h× 2,b_1 ^h,W_2 ^2× h,b_2 ^2. The two coordinates of y are indexed by the labels 0,1\0,1\, and the predicted label is y^=argmaxc∈0,1(y)c y= *argmax_c∈\0,1\(y)_c. When the input needs to be explicit, we write A(w,k)A(w,k) and y(w,k)y(w,k). We do not use residual connections or layer normalization. Adding them could alter the size and geometry of the exact-solution set; we leave this extension for future work. In this paper, we consider four models. We describe three of them here; the fourth, normA_norm, we leave for Section 4.2. In the general model gen(h)A_gen(h), the data tokens are xj=ewj∈ℝ2x_j=e_w_j ^2, and the index token is z=02z=0_2. The maps Q,K,V:ℝ2→ℝ2Q,K,V:R^2 ^2 are unrestricted affine maps, so q=Q(02)q=Q(0_2), kj=K(ewj)k_j=K(e_w_j), and vj=V(ewj)v_j=V(e_w_j). So gen(h)A_gen(h) has Dcount=5h+20D_count=5h+20 trainable scalar parameters. We also examined a model, sin(h)A_sin(h), with a sinusoidal positional encoding (sin(j) (j), cos(j) (j)). For the positional tasks, we use the positional model pos(h)A_pos(h). The data token at position j and the index token encoding k are xjpos=[ewjjj2]∈ℝ4,zkpos=[02k0]∈ℝ4x_j^pos= bmatrixe_w_j\\ j\\ j^2 bmatrix ^4, z_k^pos= bmatrix0_2\\ k\\ 0 bmatrix ^4 (where 020_2 is the two-dimensional zero vector). For First, the index is fixed at k=1k=1. For Index, the index k∈[n]k∈[n] is supplied as part of the input. Because j and j2j^2 grow without bound in the input length, allowing them to propagate through the network would like lead to instability; positional-encoding choices are known to strongly affect length extrapolation (Kazemnejad et al., 2023). Accordingly, we constrain the model to have the form of the index-lookup construction of Bhattamishra et al. (2024): WQpos W_Q^pos =[02×2a02], = bmatrix0_2× 2&a&0_2 bmatrix, bQpos b_Q^pos =b, =b, WKpos W_K^pos =[02×2rs], = bmatrix0_2× 2&r&s bmatrix, bKpos b_K^pos =cK, =c_K, WVpos W_V^pos =[CV02×2], = bmatrixC_V&0_2× 2 bmatrix, bVpos b_V^pos =bV, =b_V, where a,b,r,s,cK,bV∈ℝ2,CV∈ℝ2×2a,b,r,s,c_K,b_V ^2,C_V ^2× 2 (and 02×20_2× 2 is the 2×22× 2 zero matrix). This model has Dpos=5h+18D_pos=5h+18 trainable scalar parameters. 3 NESV bounds and length generalization We first establish the volume bounds for the four tasks and then compare such results with those of length-generalization experiments. 3.1 Main result Theorem 1 (NESV bounds). Fix B>0B>0 and h≥2h≥ 2. As n→∞n→∞, VBFirst,pos(h)(n) V_B First,A_pos(h)(n) =ΘB,h(1) = _B,h(1) (4) VBIndex,pos(h)(n) V_B Index,A_pos(h)(n) =ΘB,h(n−3) = _B,h(n^-3) (5) VBMajority,gen(h)(n) V_B Majority,A_gen(h)(n) =ΘB,h((nlogn)−1) = _B,h ((n n)^-1 ) n odd (6) VBParity,gen(h)(n) V_B Parity,A_gen(h)(n) =0 =0 n>h+1. n>h+1. (7) Proof sketch. For First, one can choose parameters such that the attention score decreases quadratically away from position one. A fixed neighborhood of these parameters preserves that decrease, and the resulting concentration of attention lets the classifier return the first symbol for all sufficiently large lengths. The neighborhood does not shrink with n, thus ensuring a constant NESV bound. However, the same argument cannot be used for Index, because the attention score must peak at j=kj=k for every possible k, and small errors that are harmless at one position can be amplified at another. We examine the two relevant error sources in Section 4. In the position-free model genA_gen, a word is represented only by its number of 1’s. For Majority, the output changes only once, between counts (n−1)/2(n-1)/2 and (n+1)/2(n+1)/2. These counts differ by just one, so the interval that separates them narrows as n increases. Consequently, placing the decision boundary between them requires increasingly precise parameter choice. For Parity, by contrast, every increment in the count must flip the output. A fixed number of hidden ReLU units cannot provide arbitrarily many flips in output. The upper bound of zero, meaning that Parity is not solvable by the class of transformers considered here, is consistent with previous theoretical results (Kozachinskiy et al., 2026b) and experiments (Chiang and Cholak, 2022; Hahn and Rofin, 2024). The complete proofs of the four bounds, including the technical details omitted from the Index proof sketch in Section 4.1, are given in Appendix A. ∎ For detailed results related to the sinusoidal model sinA_sin, see Appendix C. 3.2 Experiment To compare these bounds with empirical results, we train the First, Index, and Majority models with hidden width h=8h=8. We use 20 random seeds per task and draw a fresh batch at each update, sampling its length uniformly from 1,…,N1,…,N; for Majority, we use only odd lengths. The main results use N=51N=51. Checkpoints are selected using validation data at length N, without inspecting longer inputs, and tested on random examples at lengths up to 511. Additional experiments on N=11,21,31,41N=11,21,31,41, which give similar results, are in Appendix D. Table 1 shows that First remains accurate at the longest test length (under posA_pos), Majority retains substantial accuracy (under genA_gen), and Index falls much closer to chance (under posA_pos). These observations agree with the ranking of the three volume bounds. We found the results of Index particularly interesting. Despite the task being expressible and learnable on lengths up to 51, it showed poor length generalization, much worse than that of Majority. We take a closer look at this task in the next section. 4 The Index task We first revisit the volume argument from the previous section, to identify the parameter combinations responsible for the n-dependent decay. We then modify the model to control one of these combinations structurally and compare the resulting theoretical and empirical behavior. 4.1 Length-sensitive components of the attention score Recall that, in the positional model pos(h)A_pos(h), q=ak+b,kj=rj+sj2+cK,uj=CVewj+bV.q=ak+b,k_j=rj+sj^2+c_K,u_j=C_Ve_w_j+b_V. The attention score is gj=q⊤kj=(ak+b)⊤(rj+sj2+cK).g_j=q k_j=(ak+b) (rj+sj^2+c_K). (8) We compare the scores at position k and position k+Δk+ . The expansion will produce the following quantities used repeatedly in later proofs, so we introduce some notations for future convenience. χ=a⊤sℓ=2b⊤s+a⊤rδ=b⊤sϕ=b⊤r.χ=a s =2b s+a r δ=b s φ=b r. (9) Now consider position k+Δ∈[n]k+ ∈[n]. The score gap of this position is gk+Δ−gk g_k+ -g_k =Δ(2χk2+ℓk+ϕ)⏟Clin(k)+Δ2(χk+δ)⏟Cquad(k). = (2χ k^2+ k+φ )_C_lin(k)+ ^2 (χ k+δ )_C_quad(k). (10) We want this gap to be negative. The coefficient Cquad(k)C_quad(k) controls the curvature of the score around the indexed position, while Clin(k)C_lin(k) measures its first-order drift and therefore whether the score remains centered at j=kj=k; we want it to be zero. Because χ and ℓ are multiplied by k and k2k^2, small errors in these parameter combinations can be amplified at large k (i.e., at large n). 4.1.1 Sketch of lower bound See Section A.2.1 for the full proof of the lower bound. Let η=minB/16,1/16η= \B/16,1/16\ and consider the solution (which we call the center): a0=(2η,0),b0=(0,−η),r0=(η,0),s0=(0,η).a^0=(2η,0), b^0=(0,-η), r^0=(η,0), s^0=(0,η). (11) We want to find a region around the center that still solves the problem. The volume of this region will serve as our lower bound. At this center, χ=ℓ=ϕ=0χ= =φ=0, δ=−η2δ=-η^2, and the score gap is gk+Δ−gk=−η2Δ2.g_k+ -g_k=-η^2 ^2. (12) In a sufficiently small neighborhood of the center, we may restrict |χ|≤cn−2,|ℓ|≤cn−1,|χ|≤ cn^-2, | |≤ cn^-1, (13) while allowing a, b, r2r_2, and s2s_2 (the second coordinates of r and s, resp.) to vary over fixed-width intervals independent of n. Every parameter choice in this region then satisfies gk+Δ−gk≤−η24Δ2g_k+ -g_k≤- η^24 ^2 for every k∈[n]k∈[n] and every nonzero Δ such that k+Δ∈[n]k+ ∈[n]. Under the logn n attention scale, the total attention outside the indexed position then tends to zero as n→∞n→∞ uniformly in k. Hence, for all sufficiently large n, the indexed position receives at least a fixed fraction of the total attention, uniformly over all inputs and indexes. We may then restrict (CV,bV)(C_V,b_V) and (W1,b1,W2,b2)(W_1,b_1,W_2,b_2) to fixed-size neighborhoods, independent of n, such that, for some constant c0>0c_0>0 independent of n, ywk(w,k)−y1−wk(w,k)≥c0y_w_k(w,k)-y_1-w_k(w,k)≥ c_0 for every input (w,k)(w,k). To produce a exact solution, only the width of the interval χ and ℓ need to depend on n. Therefore the constructed set of exact solutions has normalized volume Ω(n−2)⋅Ω(n−1)=Ω(n−3). (n^-2)· (n^-1)= (n^-3). (14) 4.1.2 Sketch of upper bound See Section A.2.2 for the full proof of the upper bound. For each indexed position k, compare a constant word with a word that differs from it only at position k. These two inputs must be assigned different labels. We consider two cases. Let m=ywk(w,k)−y1−wk(w,k)m=y_w_k(w,k)-y_1-w_k(w,k). In any correct solution, we will have m>0m>0, but if m≤n−5m≤ n^-5, we call the solution small-margin; otherwise, we call it large-margin. Take any one of the inequalities ywk(w,k)>y1−wk(w,k)y_w_k(w,k)>y_1-w_k(w,k); there are 4n4n such inequalities in total. Fix arbitrary values of a,b,r,s,cK,CV,bV,W1,b1,W2a,b,r,s,c_K,C_V,b_V,W_1,b_1,W_2, and b2,1−wkb_2,1-w_k. As b2,wkb_2,w_k varies, the margin of the inequality varies with slope one. To satisfy 0<ywk(w,k)−y1−wk(w,k)≤n−50<y_w_k(w,k)-y_1-w_k(w,k)≤ n^-5, b2,wkb_2,w_k needs to lie in an interval of length n−5n^-5. Thus the set of small-margin solutions has normalized volume at most 4n⋅n−5/(2B)=O(n−4)4n· n^-5/(2B)=O(n^-4). For every large-margin solution, changing only the symbol at position k from τ to σ≠τσ≠τ must change the predicted label from τ to σ. By the definition of a large-margin solution, for each of the two words w in this comparison, ywk(w,k)−y1−wk(w,k)>n−5y_w_k(w,k)-y_1-w_k(w,k)>n^-5. Since the yσ(w,k)−yτ(w,k)y_σ(w,k)-y_τ(w,k), viewed as a function of the attention output A(w,k)A(w,k) is Lipschitz, this is impossible if the attention assigned to position k is too small. Hence the indexed position receives at least an inverse polynomial amount of attention. The softmax formula in (2) then implies that gkg_k lies within a constant of the maximum score. Comparing it with the two neighboring scores in (10) gives Cquad(k)+|Clin(k)|≤M0,C_quad(k)+|C_lin(k)|≤ M_0, where M0M_0 is independent of n. Since every coordinate of a,b,sa,b,s lies in [−B,B][-B,B], both χ=a⊤sχ=a s and δ=b⊤sδ=b s are bounded independently of n. Hence, for k≤nk≤ n, |Cquad(k)|=|χk+δ|=O(n)|C_quad(k)|=|χ k+δ|=O(n), and thus |Clin(k)|≤M0+|Cquad(k)|=O(n).|C_lin(k)|≤ M_0+|C_quad(k)|=O(n). Let M=⌊n/4⌋M= n/4 . Since Clin(k)=2χk2+ℓk+ϕC_lin(k)=2χ k^2+ k+φ, we have Clin(3M)−2Clin(2M)+Clin(M)=4χM2C_lin(3M)-2C_lin(2M)+C_lin(M)=4χ M^2. Because each term on the left is O(n)O(n) and M=Θ(n)M= (n), this gives |χ|=O(n−1)|χ|=O(n^-1). Moreover, Clin(2M)−Clin(M)=6χM2+ℓMC_lin(2M)-C_lin(M)=6χ M^2+ M. Using |χ|=O(n−1)|χ|=O(n^-1) in this identity gives |ℓ|=O(1)| |=O(1). Repeating the same argument gives |χ|=O(n−2),|ℓ|=O(n−1).|χ|=O(n^-2), | |=O(n^-1). (15) We used the fact Pr(|a⊤s|≤ε1,|2b⊤s+a⊤r|≤ε2)=OB(ε1ε2) (|a s|≤ _1,\ |2b s+a r|≤ _2 )=O_B( _1 _2) (16) whenever 0<ε1≤ε20< _1≤ _2 are sufficiently small (for detailed proof see Section A.2.2, Lemma 3). Apply this fact to (15) and adding the O(n−4)O(n^-4) small-margin volume would gives the upper bound O(n−3)O(n^-3). 4.1.3 Experimental analysis We next check whether χ=a⊤s and ℓ=2b⊤s+a⊤rχ=a s and =2b s+a r identified by the volume proof track the behavior of trained models. In (10), χ controls the error term whose effect grows quadratically with k, while ℓ controls the error term whose effect grows linearly with k. For a model trained up to maximum length N, we therefore consider the quantities N2|χ|N^2|χ| and N|ℓ|N| |, allowing models trained at different maximum lengths to be comparable. Across the 100 positional models trained at five maximum lengths, smaller values of both quantities are associated with higher mean accuracy on unseen lengths; see Fig. 1. Ranking the models separately within each maximum training length gives correlations of −0.655-0.655 for N2|χ|N^2|χ| and −0.516-0.516 for N|ℓ|N| |. Both have p<10−3p<10^-3 under permutation tests that preserve the five training-length groups. The training and evaluation protocol is given in Sections D.2 and D.3, and the coefficient analysis is detailed in Section D.4. Figure 1: Scale-normalized drift coefficients and mean OOD accuracy for trained positional Index models. Markers indicate the maximum training length N. The above analysis suggests a direct architectural change: instead of relying on training to place two free coefficients inside shrinking intervals, control one of the length-growing error terms through the model itself. 4.2 The Normalized Model We introduce a modified positional model, denoted norm(h)A_norm(h). It uses the same input vectors, value map, ReLU classifier, and trainable positional parameters a,b,r,s,cKa,b,r,s,c_K as pos(h)A_pos(h). We split the computation of the attention score into two channels: a linear channel that does not depend on the j2j^2 coordinate of the keys’ positional encoding, and a quadratic channel that depends only on the j2j^2 coordinate. In the quadratic channel, we modify the queries as follows. Define the fixed smooth map F(v)=v1+‖v‖22(v∈ℝ2).F(v)= v 1+\|v\|_2^2 (v ^2). (17) The linear and quadratic positional channels are qlin=ak+b,qquad=b+F(ak),kjlin=rj+cK,kjquad=sj2.q^lin=ak+b, q^quad=b+F(ak), k_j^lin=rj+c_K, k_j^quad=sj^2. (18) Thus the linear channel uses the full query ak+bak+b, whereas the quadratic channel applies F to the index-dependent contribution akak. The attention score is gjnorm g_j^norm =(qlin)⊤kjlin+(qquad)⊤kjquad = (q^lin ) k_j^lin+ (q^quad ) k_j^quad =(ak+b)⊤(rj+cK)+(b+F(ak))⊤sj2. =(ak+b) (rj+c_K)+ (b+F(ak) ) sj^2. (19) The attention weights are obtained by applying the same logn n-scaled softmax to (19); the values and the one-hidden-layer ReLU classifier are unchanged. The normalization introduces no new trainable parameters, so norm(h)A_norm(h) has the same parameter dimension and uses the same B as pos(h)A_pos(h). This modification could be applied to a general transformer by excluding j2j^2 from the position encoding at position j but adding an additional term f(qi,kj)j2f(q_i,k_j)j^2 directly into the attention score, with f being a scalar-valued function whose output remains bounded. We leave exploration of this more general setting for future work. The map F is approximately the identity near the origin, but its output has norm strictly smaller than one. Consequently, the component of the query that depends on k and is multiplied with j2j^2 no longer grows linearly with k. To make this precise, suppose first that a≠0a≠ 0 and write a^=a/‖a‖2 a=a/\|a\|_2. Retaining δ and ϕφ from (9), define χ^:=a^⊤s,ℓ^:=ℓ+2χ^,εχ(k):=(F(ak)−a^)⊤s. χ:= a s, := +2 χ, _χ(k):= (F(ak)- a ) s. (20) Then the modified quadratic and linear coefficients are Cquadnorm(k) C_quad^norm(k) =χ^+δ+εχ(k), = χ+δ+ _χ(k), (21) Clinnorm(k) C_lin^norm(k) =ℓ^k+ϕ+2kεχ(k). = k+φ+2k _χ(k). Thus, gk+Δnorm−gknorm=ΔClinnorm(k)+Δ2Cquadnorm(k).g_k+ ^norm-g_k^norm= C_lin^norm(k)+ ^2C_quad^norm(k). (22) Moreover, |εχ(k)|≤‖s‖22k2‖a‖22,|2kεχ(k)|≤‖s‖2k‖a‖22.| _χ(k)|≤ \|s\|_22k^2\|a\|_2^2, |2k _χ(k)|≤ \|s\|_2k\|a\|_2^2. (23) Thus the k2k^2 drift in (10) is replaced by a linear term and a bounded error 2kεχ(k)=O(k−1)2k _χ(k)=O(k^-1). Only the coefficient ℓ remains to be confined to an interval of width O(n−1)O(n^-1). Theorem 2 (NESV of Index under norm(h)A_norm(h)). For B>0B>0 and h≥2h≥ 2. VBIndex,norm(h)(n)=ΘB,h(n−1).V_B Index,A_norm(h)(n)= _B,h(n^-1). (24) Proof. The proof follows the same strategy as that of the Index bounds for the positional model in Section 4.1. The full proof is given in Appendix B. ∎ Compared with the original positional model, selective normalization removes one shrinking direction from the volume calculation. In pos(h)A_pos(h), the two effective constraints have widths n−2n^-2 and n−1n^-1; in norm(h)A_norm(h), the saturation of the quadratic query channel leaves only the n−1n^-1 constraint. The improvement from Θ(n−3) (n^-3) to Θ(n−1) (n^-1) therefore follows from the same score-level mechanism identified by the original proof. 4.3 Length-generalization experiments We train pos(h)A_pos(h) and norm(h)A_norm(h) under the same protocol, using paired seeds, the same training batches, and identical initial values for all parameters shared by the two models. The main comparison uses classifier width h=8h=8, maximum training length N=51N=51, and 20 seeds. As shown in Fig. 2, the original model degrades rapidly beyond the training range, whereas the selectively normalized model retains substantially higher accuracy. At length 511, approximately ten times the maximum training length, mean accuracy increases from 60%60\% for pos(h)A_pos(h) to approximately 85%85\% for norm(h)A_norm(h). Experiments with maximum training lengths N∈11,21,31,41N∈\11,21,31,41\ show similar results and are reported in Section D.5. Figure 2: Length generalization on Index for the positional and norm(h)A_norm(h) models trained up to N=51N=51. Shading shows 95%95\% bootstrap confidence intervals. Taken together, the coefficient analysis and the architectural intervention give two complementary forms of evidence. The original volume proof identifies the parameter combinations whose effects grow with the index k, and those combinations are associated with the behavior of trained models. Selectively normalizing the quadratic query channel removes the faster-growing contribution, enlarges the exact-solution volume from Θ(n−3) (n^-3) to Θ(n−1) (n^-1), and improves extrapolation in the model for which the volume calculation is carried out. 5 Related Work The Index task has been studied many times before. Bhattamishra et al. (2024) give an efficient one-layer construction in which the data appear before the indexed Index, as in our right-hand Index task. This differs from left-hand Indexing, where the Index appears before the data and the answer is produced later (Kozachinskiy et al., 2025; Kozachinskiy et al., 2026a). One-layer constructions for related right-hand function-evaluation problems are also studied by Strobl et al. (2025). A line of work related to our normalized model normA_norm controls attention by normalizing query–key interactions. QKNorm ℓ2 _2-normalizes complete query and key vectors and learns the attention scale (Henry et al., 2020), while scaled cosine attention likewise removes dependence on their magnitudes (Liu et al., 2022). Separately, approaches to length extrapolation often modify the positional contribution to attention, for example by adding distance-dependent score biases (Press et al., 2022) or by designing relative position encoding to improve attention resolution beyond the training lengths (Sun et al., 2023). Our norm(h)A_norm(h), on the other hand, does not normalize the full query or key vectors, nor the quadratic positional coordinate j2j^2. Instead, it applies a fixed smooth bounded map to the index-dependent query component in the quadratic positional channel. Another related line of work studies which functions occupy large or stable regions of transformer parameter space. Hahn and Rofin (2024) connect Boolean sensitivity to transformer norms and perturbation behavior, while Kover et al. (2026) study the parameter-space geometry of transformers computing Boolean functions. Empirical work on simplicity bias likewise suggests that the parameter-to-function map favors some Boolean functions over others (Bhattamishra et al., 2023). Our volume measure tracks how volume changes with sequence length, rather than assigning a single complexity or sensitivity measure to the target task. For Index, such analysis not only shows that the volume decreases with longer input lengths, but also isolates the sources of such shrinkage. 6 Discussion and Limitations Initialization and optimization Parameter-space volume depends on the distribution placed on the parameters. Equation 1 assumes a uniform distribution over a box of size 2B2B in the raw coordinates. But initialization and optimization can concentrate strongly on particular parts of parameter space, so differences in exact-solution volume might not translate exactly into differences in accuracy. Tightening the correspondence would therefore require combining the present analysis with the distributions over parameters induced by initialization and optimization. Depth Our theoretical results concern fixed-width, one-layer, one-head transformers. This restriction can matter qualitatively. Bhattamishra et al. (2024) show examples where two-layer transformers of logarithmic size solve problems for which one-layer transformers require linear size. The parameter constraints governing length generalization may therefore change substantially with depth, and extending the volume analysis to deeper transformers is an important next step. 7 Conclusion Parameter-space volume is useful not only for measuring how exact solutions change with input length, but also for revealing why they change. On the Index task, our volume analysis isolates the length-sensitive components, suggesting a modification to the model itself that improves length extrapolation. This suggests a broader use of volume analysis as a diagnostic for transformer model refinement, especially task-specific ones. Reproducibility Statement The baseline architectures, parameter prior, and strict-correctness criterion are defined in Section 2. The norm(h)A_norm(h) architecture is defined in Section 4.2, and the fixed-sinusoidal Majority model is defined in Section C.1. The complete volume arguments, experimental protocol, checkpoint-selection rule, evaluation-bank construction, and supplementary results are presented in the appendix. AI Use Statement In this work, we used generative AI tools to aid literature exploration, assist in the writing of proofs (prose editing, LaTeX preparation, proofreading), create or modify scientific figures, and edit code (for experiments). We have not used generative AI tools to develop theoretical models or conceptual frameworks, formulate mathematical claims, provide critical ingredients for proving mathematical claims, propose or refine hypotheses, design or provide feedback on research methodology or experiments, or assist with translation. We have reviewed all AI-assisted work and take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI. References Arora et al. (2018) R. Arora, A. Basu, P. Mianjy, and A. Mukherjee Understanding deep neural networks with rectified linear units. In Proceedings of the International Conference on Learning Representations (ICLR), External Links: Link Cited by: §1. Bai et al. (2023) J. Bai, S. Bai, Y. Chu, Z. Cui, K. Dang, X. Deng, Y. Fan, W. Ge, Y. Han, F. Huang, B. Hui, L. Ji, M. Li, J. Lin, R. Lin, D. Liu, G. Liu, C. Lu, K. Lu, J. Ma, R. Men, X. Ren, X. Ren, C. Tan, S. Tan, J. Tu, P. Wang, S. Wang, W. Wang, S. Wu, B. Xu, J. Xu, A. Yang, H. Yang, J. Yang, S. Yang, Y. Yao, B. Yu, H. Yuan, Z. Yuan, J. Zhang, X. Zhang, Y. Zhang, Z. Zhang, C. Zhou, J. Zhou, X. Zhou, and T. Zhu Qwen technical report. External Links: 2309.16609, Link Cited by: §2.2. Bhattamishra et al. (2024) S. Bhattamishra, M. Hahn, P. Blunsom, and V. Kanade Separations in the representational capabilities of transformers and recurrent architectures. In Advances in Neural Information Processing Systems, Vol. 37. External Links: Document Cited by: §1, §2.2, §5, §6. Bhattamishra et al. (2023) S. Bhattamishra, A. Patel, V. Kanade, and P. Blunsom Simplicity bias in transformers and their ability to learn sparse Boolean functions. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics, p. 5767–5791. External Links: Document Cited by: §5. Chen et al. (2026) S. Chen, Z. Lin, Y. Polyanskiy, and P. Rigollet Critical attention scaling in long-context transformers. In Proceedings of the International Conference on Learning Representations (ICLR), External Links: Link Cited by: §2.2. Chiang and Cholak (2022) D. Chiang and P. Cholak Overcoming a theoretical limitation of self-attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics, p. 7654–7664. External Links: Document Cited by: §1, §2.2, §3.1. Chiang et al. (2023) P. Chiang, R. Ni, D. Y. Miller, A. Bansal, J. Geiping, M. Goldblum, and T. Goldstein Loss landscapes are all you need: neural network generalization can be explained without the implicit bias of gradient descent. In Proceedings of the International Conference on Learning Representations (ICLR), External Links: Link Cited by: §1. Hahn and Rofin (2024) M. Hahn and M. Rofin Why are sensitive functions hard for transformers?. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics, p. 14973–15008. External Links: Document Cited by: §1, §3.1, §5. Henry et al. (2020) A. Henry, P. R. Dachapally, S. S. Pawar, and Y. Chen Query-key normalization for transformers. In Findings of the Association for Computational Linguistics: EMNLP 2020, p. 4246–4253. External Links: Document Cited by: §5. Kazemnejad et al. (2023) A. Kazemnejad, I. Padhi, K. Natesan Ramamurthy, P. Das, and S. Reddy The impact of positional encoding on length generalization in transformers. In Advances in Neural Information Processing Systems, Vol. 36, p. 24892–24928. External Links: Link Cited by: §2.2. Kover et al. (2026) B. Kover, A. Butoi, A. Svete, M. Hahn, and R. Cotterell Understanding the parameter space geometry of transformers encoding boolean functions. In Proceedings of the International Conference on Machine Learning (ICML), External Links: Link Cited by: §1, §5. Kozachinskiy et al. (2026a) A. Kozachinskiy, V. Opazo, and F. Urrutia Indexing: the beginning and the end. External Links: Link Cited by: §1, §5. Kozachinskiy et al. (2026b) A. Kozachinskiy, T. Steifer, and P. Walega Parity, sensitivity, and transformers. External Links: Link Cited by: §1, §3.1. Kozachinskiy et al. (2025) A. Kozachinskiy, F. Urrutia, H. Orellana, T. Steifer, G. Pizarro, M. Fuentes, F. Meza Vasquez, C. Buc Calderon, and C. Rojas Strassen attention, split VC dimension and compositionality in transformers. In Advances in Neural Information Processing Systems, Vol. 38, p. 10718–10749. External Links: Document Cited by: §5. Liu et al. (2022) Z. Liu, H. Hu, Y. Lin, Z. Yao, Z. Xie, Y. Wei, J. Ning, Y. Cao, Z. Zhang, L. Dong, F. Wei, and B. Guo Swin Transformer V2: scaling up capacity and resolution. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), p. 12009–12019. External Links: Document Cited by: §5. Nakanishi (2025) K. M. Nakanishi Scalable-softmax is superior for attention. External Links: 2501.19399, Link Cited by: §2.2. Press et al. (2022) O. Press, N. A. Smith, and M. Lewis Train short, test long: attention with linear biases enables input length extrapolation. In Proceedings of the International Conference on Learning Representations (ICLR), External Links: Link Cited by: §5. Strobl et al. (2025) L. Strobl, D. Angluin, and R. Frank Concise one-layer transformers can do function evaluation (sometimes). External Links: Link Cited by: §5. Strobl et al. (2024) L. Strobl, W. Merrill, G. Weiss, D. Chiang, and D. Angluin What formal languages can transformers express? A survey. Transactions of the Association for Computational Linguistics 12, p. 543–561. External Links: Document Cited by: §1. Sun et al. (2023) Y. Sun, L. Dong, B. Patra, S. Ma, S. Huang, A. Benhaim, V. Chaudhary, X. Song, and F. Wei A length-extrapolatable transformer. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 14590–14604. External Links: Document Cited by: §5. Appendix A Proofs of the Baseline NESV Bounds This appendix proves the four baseline bounds in Theorem 1. A.1 First The lower bound constructs fixed neighborhoods of parameters independent of input length that gives exact solutions to the task. The upper bound follows from symmetry between the two labels. Proof of the First bound in Theorem 1. Choose η=minB/16,1/16η= \B/16,1/16\ and set a0=(2η,0),b0=(0,−η),r0=(η,0),s0=(0,η),a^0=(2η,0), b^0=(0,-η), r^0=(η,0), s^0=(0,η), (25) with cK0=bV0=0c_K^0=b_V^0=0 and CV0=ηI2C_V^0=η I_2. We call this set of (a0,b0,r0,s0)(a^0,b^0,r^0,s^0) the center. Put qF:=a+bq_F:=a+b, ℓ^1:=qF⊤r _1:=q_F r, ℓ^2:=qF⊤s. _2:=q_F s. At the center, ℓ^10=2η2 _1^0=2η^2 and ℓ^20=−η2 _2^0=-η^2. By continuity, there is a fixed positive-volume neighborhood of (a,b,r,s)(a,b,r,s) on which |ℓ^1−2η2|≤η28,|ℓ^2+η2|≤η28.| _1-2η^2|≤ η^28, | _2+η^2|≤ η^28. (26) For j=1+Δj=1+ with Δ≥1 ≥ 1, the key bias cancels and g(1)−g(1+Δ) g(1)-g(1+ ) =Δ[(−ℓ^1−2ℓ^2)+(−ℓ^2)Δ] = [(- _1-2 _2)+(- _2) ] ≥η22Δ2. ≥ η^22 ^2. (27) Consequently, throughout this fixed positional-parameter neighborhood, 1−α1≤∑Δ=1∞n−(η2/2)Δ2⟶0.1- _1≤ _ =1^∞n^-(η^2/2) ^2 0. (28) Restrict (CV,bV)(C_V,b_V) to a fixed neighborhood on which ‖CVeσ+bV−ηeσ‖∞≤η16(σ∈0,1).\|C_Ve_σ+b_V-η e_σ\|_∞≤ η16 (σ∈\0,1\). (29) For all sufficiently large n, (28) gives α1≥7/8 _1≥ 7/8. If y⋆=w1y =w_1 and y¯⋆=1−y⋆ y =1-y , the total attention masses on the two symbols satisfy py⋆−py¯⋆≥34.p_y -p_ y ≥ 34. (30) Convexity of the value perturbation in (29) therefore gives Ay⋆−Ay¯⋆≥η(py⋆−py¯⋆)−η8≥5η8.A_y -A_ y ≥η (p_y -p_ y )- η8≥ 5η8. (31) Choose W10,b10,W20,b20W_1^0,b_1^0,W_2^0,b_2^0 as follows. Take the first two rows of W10W_1^0 to be ηe0⊤η e_0 and ηe1⊤η e_1 , with both corresponding biases equal to η2η^2. Set every remaining row of W10W_1^0 to zero and its bias to −η-η. In W20W_2^0, give output row zero coefficient η on hidden unit zero and output row one coefficient η on hidden unit one, with all other entries zero; set b20=0b_2^0=0. The first two hidden units are active throughout a sufficiently small neighborhood of (29), whereas the remaining units are inactive, and y0−y1=η2(A0−A1).y_0-y_1=η^2(A_0-A_1). (32) Thus (31) gives a correct-logit margin of at least that y0−y1≥y_0-y_1≥ 5η3/85η^3/8 at the center. Allow cKc_K to vary over a sufficiently small fixed neighborhood of 00. This does not affect the attention weights, since qF⊤cKq_F c_K is added to every attention score. Together with the fixed neighborhoods chosen above for (a,b,r,s)(a,b,r,s), (CV,bV)(C_V,b_V), and (W1,b1,W2,b2)(W_1,b_1,W_2,b_2), this gives a set of normalized volume cF>0c_F>0, independent of n. For the upper bound, swap the two rows of W2W_2 and the two entries of b2b_2, leaving every other coordinate unchanged. This is a measure-preserving involution of the raw parameter cube. It maps the exact solutions of First to the exact solutions of the complementary task w↦1−w1w 1-w_1. The two exact-solution sets are disjoint, so each occupies at most one half of the cube. In particular, the NESV is O(1)O(1). ∎ A.2 Index We use the notation from Section 4.1. Thus the attention score at position j is gj=(ak+b)⊤(rj+sj2+cK),g_j=(ak+b) (rj+sj^2+c_K), (33) and χ=a⊤s,ℓ=2b⊤s+a⊤r,δ=b⊤s,ϕ=b⊤r.χ=a s, =2b s+a r, δ=b s, φ=b r. (34) For k+Δ∈[n]k+ ∈[n], the score gap at position k+Δk+ is gk+Δ−gk=ΔClin(k)+Δ2Cquad(k),g_k+ -g_k= C_lin(k)+ ^2C_quad(k), (35) where Clin(k)=2χk2+ℓk+ϕ,Cquad(k)=χk+δ.C_lin(k)=2χ k^2+ k+φ, C_quad(k)=χ k+δ. (36) A.2.1 Lower bound Choose η=minB/16,1/16η= \B/16,1/16\ and consider the solution (which we call the center): a0=(2η,0),b0=(0,−η),r0=(η,0),s0=(0,η).a^0=(2η,0), b^0=(0,-η), r^0=(η,0), s^0=(0,η). (37) At this point, χ=ℓ=ϕ=0,δ=−η2,χ= =φ=0, δ=-η^2, (38) and hence gk−gj=η2(j−k)2.g_k-g_j=η^2(j-k)^2. (39) To obtain a positive-volume family around this point, consider the local coordinate map Ψ(a,b,r,s)=(χ,ℓ,a1,a2,b1,b2,r2,s2). (a,b,r,s)=(χ, ,a_1,a_2,b_1,b_2,r_2,s_2). (40) We call (a,b,r,s)(a,b,r,s) the untransformed coordinates and (χ,ℓ,a1,a2,b1,b2,r2,s2)(χ, ,a_1,a_2,b_1,b_2,r_2,s_2) the transformed coordinates. For fixed (a,b,r2,s2)(a,b,r_2,s_2), the Jacobian of (s1,r1)↦(χ,ℓ)(s_1,r_1) (χ, ) is [a102b1a1],det=a12. bmatrixa_1&0\\ 2b_1&a_1 bmatrix, =a_1^2. (41) The determinant is nonzero at (37). The inverse function theorem therefore gives a fixed neighborhood on which Ψ is one-to-one and the Jacobians of Ψ and Ψ−1 ^-1 are bounded. Hence there are constants c,C>0c,C>0, independent of n, such that every measurable set E in the transformed-coordinate neighborhood satisfies cvol(E)≤vol(Ψ−1(E))≤Cvol(E).cvol(E) \! ( ^-1(E) )≤ Cvol(E). Restrict |χ|≤η264n2,|ℓ|≤η264n,|χ|≤ η^264n^2, | |≤ η^264n, (42) while restricting the remaining transformed coordinates to fixed-width intervals independent of n sufficiently close to the center that δ≤−3η24,|ϕ|≤η216.δ≤- 3η^24, |φ|≤ η^216. (43) For every k≤nk≤ n, these conditions imply Cquad(k)≤−η22,|Clin(k)|≤η24.C_quad(k)≤- η^22, |C_lin(k)|≤ η^24. (44) Indeed, the contribution of χkχ k to Cquad(k)C_quad(k) is at most η2/64η^2/64, and the three contributions to Clin(k)C_lin(k) are bounded by 2η2/642η^2/64, η2/64η^2/64, and η2/16η^2/16, respectively. Therefore, for every nonzero integer Δ with k+Δ∈[n]k+ ∈[n], gk−gk+Δ g_k-g_k+ =−ΔClin(k)−Δ2Cquad(k) =- C_lin(k)- ^2C_quad(k) ≥η24Δ2. ≥ η^24 ^2. (45) Under the logn n attention scale, the total attention outside the indexed position is consequently at most 2∑d=1∞n−(η2/4)d2,2 _d=1^∞n^-(η^2/4)d^2, (46) which tends to zero as n→∞n→∞ uniformly in the index k and over all positional parameters (a,b,r,s)(a,b,r,s) in the local neighborhood above satisfying (42) and (43). Set CV0=ηI2C_V^0=η I_2, bV0=0b_V^0=0, and take the parameter values W10=[ηI20(h−2)×2],b10=(η2,η2,−η,…,−η)⊤,W_1^0= bmatrixη I_2\\ 0_(h-2)× 2 bmatrix, b_1^0=(η^2,η^2,-η,…,-η) , W20=[ηI202×(h−2)],b20=0.W_2^0= bmatrixη I_2&0_2×(h-2) bmatrix, b_2^0=0. For all sufficiently large n, (46) makes the indexed position receive at least 3/43/4 of the total attention. If wk=σw_k=σ, the σ coordinate of the attention output exceeds the other coordinate by at least η/2η/2, even if every other token has symbol 1−σ1-σ. With the chosen parameters, the first two hidden units are active and, for c∈0,1c∈\0,1\, the c-th unit outputs ηAc+η2η A_c+η^2. The corresponding row of W2W_2 multiplies this quantity by η, so yc=η2Ac+η3y_c=η^2A_c+η^3. The common term η3η^3 cancels between the two logits, and therefore yσ−y1−σ=η2(Aσ−A1−σ)≥η32y_σ-y_1-σ=η^2 (A_σ-A_1-σ )≥ η^32. This margin is uniform over all inputs and indexes, so there exists fixed neighborhoods independent of n of CV,bV,W1,b1,W2,b2C_V,b_V,W_1,b_1,W_2,b_2 that produce exact solutions. The key bias cKc_K may also vary over a fixed neighborhood because it cancels from the attention weights. The two intervals in (42) contribute normalized widths of orders n−2n^-2 and n−1n^-1, whereas all other coordinates vary over intervals of width independent of n. Therefore VBIndex,pos(h)(n)=ΩB,h(n−3).V_B Index,A_pos(h)(n)= _B,h(n^-3). (47) A.2.2 Upper bound For each indexed position k, compare a constant word with a word that differs from it only at position k. These two inputs must be assigned different labels. We consider two cases. Let m=ywk(w,k)−y1−wk(w,k)m=y_w_k(w,k)-y_1-w_k(w,k). In any correct solution, we will have m>0m>0, but if m≤n−5m≤ n^-5, we call the solution small-margin; otherwise, we call it large-margin. Take any one of the inequalities ywk(w,k)>y1−wk(w,k)y_w_k(w,k)>y_1-w_k(w,k); there are 4n4n such inequalities in total. Fix arbitrary values of a,b,r,s,cK,CV,bV,W1,b1,W2a,b,r,s,c_K,C_V,b_V,W_1,b_1,W_2, and b2,1−wkb_2,1-w_k. As b2,wkb_2,w_k varies, the margin of the inequality varies with slope one. To satisfy 0<ywk(w,k)−y1−wk(w,k)≤n−50<y_w_k(w,k)-y_1-w_k(w,k)≤ n^-5, b2,wkb_2,w_k needs to lie in an interval of length n−5n^-5. Thus the set of small-margin solutions has normalized volume at most 4n⋅n−5/(2B)=O(n−4)4n· n^-5/(2B)=O(n^-4). For every large-margin solution, changing only the symbol at position k from τ to σ≠τσ≠τ must change the predicted label from τ to σ. By the definition of a large-margin solution, for each of the two words w in this comparison, ywk(w,k)−y1−wk(w,k)>n−5y_w_k(w,k)-y_1-w_k(w,k)>n^-5. Since the yσ(w,k)−yτ(w,k)y_σ(w,k)-y_τ(w,k), viewed as a function of the attention output A(w,k)A(w,k) is Lipschitz, this is impossible if the attention assigned to position k is too small. To see this, let w be the constant-τ word and let w′w be the word obtained by changing only position k to σ. Because the query and key maps read only positional coordinates, the two words have the same attention weights. Their attention outputs therefore satisfy A(w′,k)−A(w,k)=αkCV(eσ−eτ),A(w ,k)-A(w,k)= _kC_V(e_σ-e_τ), (48) so ‖A(w′,k)−A(w,k)‖∞≤2Bαk.\|A(w ,k)-A(w,k)\|_∞≤ 2B _k. (49) Moreover, ReLU is 11-Lipschitz, each row of W1W_1 has ℓ1 _1-norm at most 2B2B, and the difference between rows σ and τ of W2W_2 has ℓ1 _1-norm at most 2hB2hB. Hence |(yσ(w′,k)−yτ(w′,k))−(yσ(w,k)−yτ(w,k))| | (y_σ(w ,k)-y_τ(w ,k) )- (y_σ(w,k)-y_τ(w,k) ) | ≤4hB2‖A(w′,k)−A(w,k)‖∞≤8hB3αk. 50.00008pt≤ 4hB^2\|A(w ,k)-A(w,k)\|_∞≤ 8hB^3 _k. (50) The first difference is greater than n−5n^-5 and the second is less than −n−5-n^-5, so αk≥n−54hB3. _k≥ n^-54hB^3. (51) Hence the indexed position receives at least an inverse polynomial amount of attention. The softmax formula in (2) then implies that gkg_k lies within a constant of the maximum score. Indeed, n−54hB3≤αk=ngk∑j=1nngj≤ngk−maxjgj, n^-54hB^3≤ _k= n^g_k _j=1^nn^g_j≤ n^g_k- _jg_j, (52) and therefore maxjgj−gk≤5+log(4hB3)logn≤M0 _jg_j-g_k≤ 5+ (4hB^3) n≤ M_0 (53) for all sufficiently large n, where M0M_0 is independent of n. For every interior index 2≤k≤n−12≤ k≤ n-1, comparing gkg_k with the two neighboring scores in (10) gives gk+1−gk=Clin(k)+Cquad(k)≤M0g_k+1-g_k=C_lin(k)+C_quad(k)≤ M_0 (54) and gk−1−gk=−Clin(k)+Cquad(k)≤M0.g_k-1-g_k=-C_lin(k)+C_quad(k)≤ M_0. (55) Thus Cquad(k)+|Clin(k)|≤M0,C_quad(k)+|C_lin(k)|≤ M_0, (56) where M0M_0 is independent of n. Since every coordinate of a,b,sa,b,s lies in [−B,B][-B,B], both χ=a⊤sχ=a s and δ=b⊤sδ=b s are bounded independently of n. Hence, for k≤nk≤ n, |Cquad(k)|=|χk+δ|=O(n)|C_quad(k)|=|χ k+δ|=O(n), and thus |Clin(k)|≤M0+|Cquad(k)|=O(n).|C_lin(k)|≤ M_0+|C_quad(k)|=O(n). Let M=⌊n/4⌋M= n/4 . Since Clin(k)=2χk2+ℓk+ϕC_lin(k)=2χ k^2+ k+φ, we have Clin(3M)−2Clin(2M)+Clin(M)=4χM2C_lin(3M)-2C_lin(2M)+C_lin(M)=4χ M^2. Because each term on the left is O(n)O(n) and M=Θ(n)M= (n), this gives |χ|=O(n−1)|χ|=O(n^-1). Moreover, Clin(2M)−Clin(M)=6χM2+ℓMC_lin(2M)-C_lin(M)=6χ M^2+ M. Using |χ|=O(n−1)|χ|=O(n^-1) in this identity gives |ℓ|=O(1)| |=O(1). These preliminary bounds make |Cquad(k)|=|χk+δ|=O(1)|C_quad(k)|=|χ k+δ|=O(1) (57) uniformly for k≤nk≤ n. Equation (56) then gives |Clin(k)|=O(1)|C_lin(k)|=O(1). Repeating the same argument, now using these improved bounds, gives |χ|=O(n−2),|ℓ|=O(n−1).|χ|=O(n^-2), | |=O(n^-1). (58) We used the fact Pr(|a⊤s|≤ε1,|2b⊤s+a⊤r|≤ε2)=OB(ε1ε2) (|a s|≤ _1,\ |2b s+a r|≤ _2 )=O_B( _1 _2) whenever 0<ε1≤ε20< _1≤ _2 are sufficiently small. Lemma 3 (Joint two-slab estimate). Let a,b,r,sa,b,r,s be independent and uniform on [−B,B]2[-B,B]^2. There are constants Cslab,εB>0C_slab, _B>0, depending only on B, such that, whenever 0<ε1≤ε2≤εB0< _1≤ _2≤ _B, Pr(|a⊤s|≤ε1,|2b⊤s+a⊤r|≤ε2)≤Cslabε1ε2. \! (|a s|≤ _1,\ |2b s+a r|≤ _2 )≤ C_slab _1 _2. (59) Proof. Scaling changes only the constant, so take B=1B=1. Fix (a,s)(a,s), and set ϱ=(‖a‖22+‖s‖22)1/2. =(\|a\|_2^2+\|s\|_2^2)^1/2. (60) The second constraint defines a slab in (b,r)(b,r) with normal vector (2s,a)(2s,a). One coordinate of this vector has magnitude at least a constant multiple of ϱ , so, after fixing the other three coordinates, the allowed fraction of the remaining coordinate is at most Cmin1,ε2ϱ.C \1, _2 \. (61) To estimate the first constraint at fixed radius ϱ . Write a=ϱcosϑa^,s=ϱsinϑs^,0≤ϑ≤π2,a= \, a, s= \, s, 0≤ ≤ π2, (62) where a^,s^∈1 a, s ^1. If φ is the angle between a a and s s, then |a⊤s|=ϱ2sinϑcosϑ|cosφ|.|a s|= ^2 \,| |. (63) For fixed ϑ , the fraction of angle φ satisfying the first constraint is at most Cmin1,ε1ϱ2sinϑcosϑ.C \1, _1 ^2 \. (64) The angular density contains the factor sinϑcosϑ , therefore integrating over ϑ bounds the angular fraction by Cmin1,ε1ϱ2.C \1, _1 ^2 \. (65) because when t≤1t≤ 1, ∫0π/2minsinϑcosϑ,tϑ=O(t) _0^π/2 \ ,t\\,d =O(t). The radial volume element for (a,s)∈ℝ4(a,s) ^4is proportional to ϱ3dϱ ^3d . Enlarging the cube to a fixed ball and combining (61) and (65), the required probability is at most a constant times ∫0R0ϱ3min1,ε1ϱ2min1,ε2ϱϱ. _0^R_0 ^3 \1, _1 ^2 \ \1, _2 \d . (66) Assume 0<ε1≤ε2≤10< _1≤ _2≤ 1. If ε2≤ε1 _2≤ _1, split the integral at ε2 _2 and ε1 _1 to obtain I I ≤∫0ε2ϱ3ϱ+ε2∫ε2ε1ϱ2ϱ+ε1ε2∫ε1R0ϱ ≤ _0 _2 ^3\,d + _2 _ _2 _1 ^2\,d + _1 _2 _ _1^R_0d ≤Cε1ε2. ≤ C _1 _2. (67) If ε1≤ε2 _1≤ _2, split instead at ε1 _1 and ε2 _2. Rescaling restores B and proves the lemma. ∎ Applying the above lemma to (58), the large-margin solutions have normalized volume O(n−3)O(n^-3): the entries of a,b,r,sa,b,r,s are independent parameter coordinates, and all remaining coordinates integrate out. Adding the O(n−4)O(n^-4) small-margin volume gives VBIndex,pos(h)(n)=OB,h(n−3).V_B Index,A_pos(h)(n)=O_B,h(n^-3). (68) Together with (47), this proves the Index claim in Theorem 1. A.3 Majority In the position-free model genA_gen, every input with the same number of ones produces the same attention output. The proof therefore reduces Majority to a one-dimensional sequence indexed by the count and measures how much of the parameter space places the decision boundary between the two central counts. Let t=∑j=1nwj,vb=V(eb),q=Q(02),t= _j=1^nw_j, v_b=V(e_b), q=Q(0_2), (69) and define the query–key score contrast X=q⊤WK(e1−e0),Γ=exp((logn)X).X=q W_K(e_1-e_0), = (( n)X). (70) All zero tokens share one score and all one tokens share another, so the total attention mass on the one tokens and the attention output are exactly ρt=tΓn−t+tΓ,At=v0+ρt(v1−v0). _t= t n-t+t , A_t=v_0+ _t(v_1-v_0). (71) Thus the 2n2^n inputs reduce to n+1n+1 possible count levels. Throughout this subsection, write n=2m+1n=2m+1. For an attention scale β>0β>0 and a score contrast x, let Δρn,β(x)=ρm+1−ρm, _n,β(x)= _m+1- _m, (72) where Γ=eβx =e^β x. The counts m and m+1m+1 are the two adjacent levels at which the majority label changes. Lemma 4 (Central attention gap). For Γ=eβx =e^β x, Δρn,β(x) _n,β(x) =neβx(m+1+meβx)(m+(m+1)eβx) = ne^β x(m+1+me^β x)(m+(m+1)e^β x) (73) =n2+(n2−1)sinh2(βx/2). = nn^2+(n^2-1) ^2(β x/2). (74) Moreover, 0<Δρn,β(x)≤1n,∫ℝΔρn,β(x)x=4artanh(1/n)β.0< _n,β(x)≤ 1n, _R _n,β(x)\,dx= 4artanh(1/n)β. (75) Proof. Substitute t=m,m+1t=m,m+1 into (71) and subtract to obtain (73). Dividing its denominator by eβxe^β x and using n=2m+1n=2m+1 gives (74). The maximum is attained at x=0x=0. For the integral, set z=tanh(βx/2)z= (β x/2). Then dx=2dzβ(1−z2),Δρn,β(x)=n(1−z2)n2−z2.dx= 2\,dzβ(1-z^2), _n,β(x)= n(1-z^2)n^2-z^2. (76) Therefore ∫ℝΔρn,β(x)x=2nβ∫−11dzn2−z2=4artanh(1/n)β. _R _n,β(x)\,dx= 2nβ _-1^1 dzn^2-z^2= 4artanh(1/n)β. (77) ∎ For fixed values of all parameters except b2,1b_2,1, exact correctness requires b2,1b_2,1 to place the decision threshold between the two central count levels. Define the bias-free logit difference H(z)=(e1−e0)⊤W2ReLU(W1z+b1).H(z)=(e_1-e_0) W_2ReLU(W_1z+b_1). (78) Lemma 5 (Output-bias fiber). Condition on every raw parameter except b2,1b_2,1. The set of values of b2,1b_2,1 that can extend the conditioned coordinates to an exact Majority solution has length at most 8hB3Δρn,β(X).8hB^3 _n,β(X). (79) Proof. Correctness on the count-m and count-(m+1)(m+1) levels requires H(Am)+b2,1−b2,0 H(A_m)+b_2,1-b_2,0 <0, <0, (80) H(Am+1)+b2,1−b2,0 H(A_m+1)+b_2,1-b_2,0 >0. >0. (81) Thus b2,1b_2,1 must lie in (b2,0−H(Am+1),b2,0−H(Am)), (b_2,0-H(A_m+1),\ b_2,0-H(A_m) ), (82) whose length is H(Am+1)−H(Am)H(A_m+1)-H(A_m) when this difference is positive. ReLU is 11-Lipschitz, each row of W1W_1 has ℓ1 _1-norm at most 2B2B, and the difference between the two rows of W2W_2 has ℓ1 _1-norm at most 2hB2hB. Hence H is 4hB24hB^2-Lipschitz in ℓ∞ _∞. Moreover, Am+1−Am=Δρn,logn(X)(v1−v0)A_m+1-A_m= _n, n(X)(v_1-v_0), so ‖Am+1−Am‖∞≤2BΔρn,β(X).\|A_m+1-A_m\|_∞≤ 2B _n,β(X). (83) Multiplying the two bounds proves the claim. ∎ To average the fiber length over the query and key parameters, we use a uniform density bound for X. Lemma 6 (Density of the score contrast). Under the uniform raw-cube measure, the random variable X=q⊤WK(e1−e0)X=q W_K(e_1-e_0) has a density fXf_X satisfying ‖fX‖∞≤B−2.\|f_X\|_∞≤ B^-2. (84) Proof. Write ΔK=WK(e1−e0) _K=W_K(e_1-e_0). Each coordinate of ΔK _K is the difference of two independent uniform variables and has triangular density bounded by (2B)−1(2B)^-1. Conditional on qagg≠0q_agg≠ 0, choose a coordinate with magnitude ‖qagg‖∞\|q_agg\|_∞ and condition on the other coordinate of ΔK _K. Scaling gives ‖fX|qagg‖∞≤12B‖qagg‖∞.\|f_X q_agg\|_∞≤ 12B\|q_agg\|_∞. (85) Since qagg=Q(0)=bQq_agg=Q(0)=b_Q is uniform on [−B,B]2[-B,B]^2, [‖qagg‖∞−1]=2B.E [\|q_agg\|_∞^-1 ]= 2B. (86) Averaging proves the result. ∎ By Fubini’s theorem and Lemmas 4, 5 and 6, VBMajority,gen(h)(n) V_B Majority,A_gen(h)(n) ≤4hB2[Δρn,logn(X)] ≤ 4hB^2\,E [ _n, n(X) ] ≤4hB2‖fX‖∞∫ℝΔρn,logn(x)x ≤ 4hB^2\|f_X\|_∞ _R _n, n(x)\,dx ≤16hartanh(1/n)logn. ≤ 16hartanh(1/n) n. (87) Since artanh(1/n)≤n/(n2−1)artanh(1/n)≤ n/(n^2-1), this is Oh((nlogn)−1)O_h((n n)^-1). For the matching lower bound, we need a positive mass of score contrasts on which the central gap is of order 1/n1/n and a fixed-volume set of the remaining parameters that turns this gap into a correct bias interval. Lemma 7 (Lower contrast mass). There is a constant cX=cX(B)>0c_X=c_X(B)>0 such that, for all sufficiently large n, Pr(|X|≤1logn)≥cXlogn. \! (|X|≤ 1 n )≥ c_X n. (88) Proof. Write ΔK=WK(e1−e0) _K=W_K(e_1-e_0) and qagg=(q1,q2)q_agg=(q_1,q_2). Restrict to q1∈[B/2,B],|q2|≤B/4,|ΔK,2|≤B/2.q_1∈[B/2,B], |q_2|≤ B/4, | _K,2|≤ B/2. (89) These independent events have probabilities at least 1/41/4, 1/41/4, and 3/83/8. Conditional on them, the inequality |q1ΔK,1+q2ΔK,2|≤ε|q_1 _K,1+q_2 _K,2|≤ (90) asks that ΔK,1 _K,1 lie in an interval of length at least 2ε/B2 /B, centered in [−B/4,B/4][-B/4,B/4]. If ε≤B2/8 ≤ B^2/8, the interval lies in [−B/2,B/2][-B/2,B/2], where the triangular density of ΔK,1 _K,1 is at least 3/(8B)3/(8B). Hence Pr(|X|≤ε)≥9ε512B2. (|X|≤ )≥ 9 512B^2. (91) Taking ε=1/logn =1/ n proves the lemma. ∎ Lemma 8 (Positive-volume monotone decoder family). There are constants cΩ,κ>0c_ ,κ>0 and a set of values of (WV,bV,W1,b1,W2,b2,0)(W_V,b_V,W_1,b_1,W_2,b_2,0) of normalized volume at least cΩc_ such that the bias-free logit difference along v0+p(v1−v0)v_0+p(v_1-v_0) is affine with derivative at least κ for all p∈[0,1]p∈[0,1]. For every parameter choice in this set, b2,1b_2,1 may vary over an interval of length at least κ(ρm+1−ρm)κ( _m+1- _m) (92) while preserving exact Majority correctness. Proof. Let eV=(1,0)⊤e_V=(1,0) and choose WV,bVW_V,b_V so that v0=0,v1=ηeV.v_0=0, v_1=η e_V. (93) Give one hidden unit first-layer row ηeV⊤η e_V and bias η, make every other hidden unit strictly inactive, and set the difference between output rows on the active hidden unit to η. Set the other output-row differences and b2,0b_2,0 to zero. Along the value segment, define ψ(p)=H(v0+p(v1−v0)).ψ(p)=H(v_0+p(v_1-v_0)). (94) For these parameter values, ψ(p)=η2+η3p.ψ(p)=η^2+η^3p. (95) The active pre-activation lies in [η,η+η2][η,η+η^2], while every other pre-activation equals −η-η. A fixed open raw-coordinate box around these parameter values therefore preserves the activation pattern, keeps ψ affine with derivative at least η3/2η^3/2, and keeps b2,0−ψb_2,0-ψ inside (−B,B)(-B,B). Take κ=η3/2κ=η^3/2 and let cΩc_ be the normalized volume of this box. For parameters in the box, the interval (b2,0−ψ(ρm+1),b2,0−ψ(ρm)) (b_2,0-ψ( _m+1),\ b_2,0-ψ( _m) ) (96) has length at least κ(ρm+1−ρm)κ( _m+1- _m) and lies in the raw bias range. Since both ρt _t and ψ are increasing, every t≤mt≤ m gives a negative logit difference and every t≥m+1t≥ m+1 gives a positive one. Thus all count levels are classified correctly. ∎ On the event in (88), |lognX|≤1| n\,X|≤ 1, so (74) gives ρm+1−ρm≥1n(1+sinh2(1/2))=Ω(n−1) _m+1- _m≥ 1n (1+ ^2(1/2) )= (n^-1). Restrict the (WV,bV,W1,b1,W2,b2,0)(W_V,b_V,W_1,b_1,W_2,b_2,0) to the set in Lemma 8. The remaining bias interval then has normalized length Ω(1/n) (1/n). Multiplying this length by the Ω(1/logn) (1/ n) contrast event and the fixed parameter box volume gives VBMajority,gen(h)(n)≥c−nlogn.V_B Majority,A_gen(h)(n)≥ c_-n n. (97) Together with (87), this proves the Majority claim in Theorem 1. A.4 Parity For Parity, the count reduction in (71) gives a sequence of points along the value segment on which the required label flips. The proof compares the resulting number of sign changes with the number of activation changes available to a one-hidden-layer ReLU classifier. If v0≠v1v_0≠ v_1, then 0=ρ0<ρ1<⋯<ρn=1.0= _0< _1<·s< _n=1. (98) Since every count-t attention output has the form At=v0+ρt(v1−v0),A_t=v_0+ _t(v_1-v_0), all such outputs lie on the line segment joining v0v_0 and v1v_1. Parameterize this segment by A(p)=v0+p(v1−v0)A(p)=v_0+p(v_1-v_0), p∈[0,1]p∈[0,1] and define the difference between the two output logits along it by f(p)=(e1−e0)⊤[W2ReLU(W1A(p)+b1)+b2].f(p)=(e_1-e_0) [W_2ReLU(W_1A(p)+b_1)+b_2 ]. (99) This is a continuous piecewise-affine function of p, and each hidden preactivation can change sign at most once. Proof of the Parity bound in Theorem 1. If v0=v1v_0=v_1, every count level has the same attention output, so exact parity is impossible. Otherwise, exact parity makes f(ρt)f( _t) alternate in sign. By continuity, for each t=0,…,n−1t=0,…,n-1, choose a zero zt∈(ρt,ρt+1)z_t∈( _t, _t+1). For each t=1,…,n−1t=1,…,n-1, the interval (zt−1,zt)(z_t-1,z_t) contains ρt _t, where f is nonzero. If no hidden pre-activation changed sign in this interval, the activation pattern would be fixed and f would be affine there. An affine function that vanishes at both endpoints is identically zero, contradicting f(ρt)≠0f( _t)≠ 0. Hence each of the n−1n-1 disjoint intervals (zt−1,zt)(z_t-1,z_t) contains a point at which a hidden ReLU pre-activation changes sign. Since each hidden pre-activation changes sign at most once, this requires h≥n−1h≥ n-1. Therefore the exact-solution set is empty whenever n>h+1n>h+1. ∎ Appendix B Proof of the norm(h)A_norm(h) Index Bound This appendix proves Theorem 2. Recall the fixed map F(v)=v1+‖v‖22F(v)= v 1+\|v\|_2^2 (100) and the norm(h)A_norm(h) positional score gjnorm=(ak+b)⊤(rj+cK)+(b+F(ak))⊤sj2.g_j^norm=(ak+b) (rj+c_K)+ (b+F(ak) ) sj^2. (101) χ^=a^⊤s,ℓ^=ℓ+2χ^,εχ(k)=(F(ak)−a^)⊤s, χ= a s, = +2 χ, _χ(k)= (F(ak)- a ) s, (102) with δ=b⊤sδ=b s and ϕ=b⊤rφ=b r as in (9). Then, Cquadnorm(k)=χ^+δ+εχ(k),Clinnorm(k)=ℓ^k+ϕ+2kεχ(k),C_quad^norm(k)= χ+δ+ _χ(k), C_lin^norm(k)= k+φ+2k _χ(k), (103) Whenever k+Δ∈[n]k+ ∈[n], gk+Δnorm−gknorm=ΔClinnorm(k)+Δ2Cquadnorm(k).g_k+ ^norm-g_k^norm= C_lin^norm(k)+ ^2C_quad^norm(k). (104) Since F(ak)F(ak) is collinear with a, F(ak)=λa(k)a^,λa(k)=k‖a‖21+k2‖a‖22.F(ak)= _a(k) a, _a(k)= k\|a\|_2 1+k^2\|a\|_2^2. (105) Moreover, 0≤1−λa(k)≤12k2‖a‖22,|2kεχ(k)|≤‖s‖2k‖a‖22.0≤ 1- _a(k)≤ 12k^2\|a\|_2^2, |2k _χ(k)|≤ \|s\|_2k\|a\|_2^2. (106) B.1 Lower bound Use the same positional center as in (37). At this point, a^0=(1,0) a^0=(1,0) is orthogonal to s0=(0,η)s^0=(0,η), and hence ℓ^=ϕ=0,Qa0(k)=−η2(k≥1). =φ=0, Q_a^0(k)=-η^2 (k≥ 1). (107) Thus Cquadnorm(k)=−η2,Clinnorm(k)=0,C_quad^norm(k)=-η^2, C_lin^norm(k)=0, (108) and therefore, gknorm−gjnorm=η2(j−k)2.g_k^norm-g_j^norm=η^2(j-k)^2. (109) Work in a fixed neighborhood of this center on which a1>ηa_1>η. The map a↦a^a a is smooth there. Replace the raw coordinate r1r_1 by ℓ , keeping (a,b,r2,s)(a,b,r_2,s) as the other coordinates. Since ∂ℓ^∂r1=a1, ∂ ∂ r_1=a_1, (110) the corresponding coordinate change is locally invertible, with Jacobian and inverse Jacobian bounded on a sufficiently small fixed neighborhood. Thus boxes in these transformed coordinates and their preimages in the original coordinates have volumes within fixed multiplicative constants, independent of n. Shrink the fixed intervals for the other transformed coordinates so that throughout the neighborhood ‖a‖2≥η,b⊤s≤−7η28,|a^⊤s|≤minη28,η416,|ϕ|≤η216.\|a\|_2≥η, b s≤- 7η^28, | a s|≤ \ η^28, η^416 \, |φ|≤ η^216. (111) By (105), for every k≥1k≥ 1, Cquadnorm(k)=δ+λa(k)χ^≤−3η24.C_quad^norm(k)=δ+ _a(k) χ≤- 3η^24. (112) Furthermore, (106) and (111) give |2kεχ(k)|≤|a^⊤s|‖a‖22≤η216(k≥1).|2k _χ(k)|≤ | a s|\|a\|_2^2≤ η^216 (k≥ 1). (113) Here we used that 2kεχ(k)=2k(λa(k)−1)a^⊤s2k _χ(k)=2k( _a(k)-1) a s. Now restrict the only shrinking transformed coordinate by |ℓ^|≤η216n.| |≤ η^216n. (114) For every k≤nk≤ n, equations (111), (113), and (114) imply |ℓ^k+ϕ+2kεχ(k)|≤3η216.| k+φ+2k _χ(k)|≤ 3η^216. (115) Therefore, for every nonzero integer Δ with k+Δ∈[n]k+ ∈[n], gknorm−gk+Δnorm g_k^norm-g_k+ ^norm ≥3η24Δ2−3η216|Δ| ≥ 3η^24 ^2- 3η^216| | ≥η22Δ2. ≥ η^22 ^2. (116) Under the logn n attention scale, the total attention outside position k is at most 2∑d=1∞n−(η2/2)d2,2 _d=1^∞n^-(η^2/2)d^2, (117) which tends to zero uniformly in k and in the parameters in the neighborhood above. Thus the same fixed neighborhoods of CV,bV,W1,b1,W2,b2C_V,b_V,W_1,b_1,W_2,b_2 used in the baseline Index lower bound preserve a positive logit difference for the correct label, and cKc_K may vary over a fixed neighborhood because it cancels from the attention weights. The transformed coordinate ℓ varies over an interval of width Θ(n−1) (n^-1), whereas a,b,r2,s,cK,CV,bV,W1,b1,W2,b2a,b,r_2,s,c_K,C_V,b_V,W_1,b_1,W_2,b_2 vary over fixed-width intervals. Boundedness of the local Jacobian then gives VBIndex,norm(h)(n)=ΩB,h(n−1).V_B Index,A_norm(h)(n)= _B,h(n^-1). (118) B.2 Upper bound Use the same 4n4n inequalities ywk(w,k)>y1−wk(w,k)y_w_k(w,k)>y_1-w_k(w,k) as in the original Index upper bound. The same output-bias argument shows that exact solutions for which one of these margins lies in (0,n−5](0,n^-5] have normalized volume OB(n−4)O_B(n^-4). For every remaining exact solution, the indexed position receives at least c0n−5c_0n^-5 attention in each constant-word/single-change comparison. Hence its score lies within a constant M0M_0 of the maximum score, uniformly in n. Comparing the indexed position with its two neighbors in (104) gives Cquadnorm(k)+|Clinnorm(k)|≤M0(2≤k≤n−1).C_quad^norm(k)+|C_lin^norm(k)|≤ M_0 (2≤ k≤ n-1). (119) Since ‖F(ak)‖2<1\|F(ak)\|_2<1 and the parameters are bounded, there exists a constant C0=C0(B)C_0=C_0(B) such that |Cquadnorm(k)|=|(b+F(ak))⊤s|≤C0(a,b,s∈[−B,B]2,k≥1).|C_quad^norm(k)|=| (b+F(ak) ) s|≤ C_0 (a,b,s∈[-B,B]^2,\ k≥ 1). (120) It follows from (119) that |ℓ^k+ϕ+2kεχ(k)|≤M1(2≤k≤n−1)| k+φ+2k _χ(k)|≤ M_1 (2≤ k≤ n-1) (121) for another constant M1=M1(B,h)M_1=M_1(B,h). Split the raw parameter cube according to whether ∥a∥2≤n−1/2.\|a\|_2≤ n^-1/2. (122) Because a consists of two independent raw coordinates, the normalized volume of this part is at most the area of a radius-n−1/2n^-1/2 disk divided by (2B)2(2B)^2, and hence is OB(n−1)O_B(n^-1). On its complement, take k0=⌊n/2⌋k_0= n/2 . For all sufficiently large n, k0k_0 is interior and k0≥n/3k_0≥ n/3. By (106), |2kεχ(k0)|≤‖s‖2k0‖a‖22=OB(1)|2k _χ(k_0)|≤ \|s\|_2k_0\|a\|_2^2=O_B(1) (123) because ∥a∥2>n−1/2\|a\|_2>n^-1/2. Boundedness also gives |ϕ|=OB(1)|φ|=O_B(1). Equation (121) at k0k_0 therefore forces |ℓ^|≤Cn| |≤ Cn (124) for C=C(B,h)C=C(B,h). Conditional on (a,b,s)(a,b,s), ℓ^=a⊤r+(2b⊤s+2a^⊤s), =a r+ (2b s+2 a s ), (125) so (124) defines a slab in the independent variable r with normal a. Choose a coordinate i with |ai|≥‖a‖2/2|a_i|≥\|a\|_2/ 2 and fix the other coordinate of r. The allowed values of rir_i lie in an interval of length at most C/(n‖a‖2)C/(n\|a\|_2), up to a constant depending only on B and h. Thus the normalized volume is at most CBmin1,1n‖a‖2.C_B \1, 1n\|a\|_2 \. (126) Enlarging the square for a to a fixed-radius disk and integrating in polar coordinates on the complement of (122) gives ∫a∈[−B,B]2∥a∥2>n−1/2CBn‖a‖2a _ subarrayca∈[-B,B]^2\\ \|a\|_2>n^-1/2 subarray C_Bn\|a\|_2\,da ≤CB′n∫n−1/22Bdϱ ≤ C_B n _n^-1/2 2Bd =OB(n−1). =O_B(n^-1). (127) All remaining raw coordinates integrate out. Adding the O(n−1)O(n^-1) small-a region and the O(n−4)O(n^-4) small-margin region gives VBIndex,norm(h)(n)=OB,h(n−1).V_B Index,A_norm(h)(n)=O_B,h(n^-1). (128) Together with (118), this proves Theorem 2. Appendix C Fixed Sinusoidal Encoding on Majority This appendix analyzes the fixed-frequency sinusoidal Majority model used in the discussion. C.1 Model and matched bound Let n=2m+1n=2m+1 be odd, let pj=(sinj,cosj)⊤p_j=( j, j) , and define xjsin=[ewjpj]∈ℝ4,zsin=04.x_j = bmatrixe_w_j\\ p_j bmatrix ^4, z =0_4. (129) The frequency is fixed at one and is not a trainable coordinate. The query, key, and value maps are unrestricted affine maps from ℝ4R^4 to ℝ2R^2, the attention multiplier is βn=logn _n= n, and the output is the same width-h one-hidden-layer ReLU classifier as in Section 2. We denote this architecture by sin(h)A_sin(h). All scalar parameters are bounded in [−B,B][-B,B]. Theorem 9 (Fixed-sinusoidal Majority volume). For every fixed B>0B>0 and h≥2h≥ 2, VBMajority,sin,gen(h)(n)=Θ(1n3logn).V_B Majority,A_sin,gen(h)(n)= ( 1n^3 n). (130) Write the columns of WKW_K and WVW_V as WK=[k0k1ksinkcos],WV=[v0v1vsinvcos],W_K=[k_0\ k_1\ k_ \ k_ ], W_V=[v_0\ v_1\ v_ \ v_ ], (131) and define q q =bQ, =b_Q, λ λ =βnq⊤(k1−k0), = _nq (k_1-k_0), Γ =eλ, =e^λ, a a =βn[q⊤ksinq⊤kcos], = _n bmatrixq k_ \\ q k_ bmatrix, Pj P_j =ea⊤pj, =e^a p_j, T T =∑j=1nPj, = _j=1^nP_j, vb v_b =vb+bV(b∈0,1), =v_b+b_V (b∈\0,1\), CV C_V =[vsinvcos], =[v_ \ v_ ], μ μ =1T∑j=1nPjpj. = 1T _j=1^nP_jp_j. (132) The common key-bias and symbol-zero score contributions cancel, so the attention weights are αj(w)=PjΓwj∑i=1nPiΓwi. _j(w)= P_j ^w_j _i=1^nP_i ^w_i. (133) For t∈[0,1]nt∈[0,1]^n, introduce the algebraic extensions (t) D(t) =T+(Γ−1)∑jPjtj, =T+( -1) _jP_jt_j, (134) (t) N(t) =∑jPj(v0+CVpj)+∑jtjPj[Γv1−v0+(Γ−1)CVpj]. = _jP_j(v_0+C_Vp_j)+ _jt_jP_j [ v_1-v_0+( -1)C_Vp_j ]. (135) Then (t)>0 D(t)>0 on the cube and A(w)=(w)/(w)A(w)= N(w)/ D(w) on binary inputs. C.2 The necessary positional compensation Let di=(W2)1i−(W2)0id_i=(W_2)_1i-(W_2)_0i and b=b2,1−b2,0b=b_2,1-b_2,0. After multiplying the logit difference by the positive denominator (t) D(t), the resulting function is continuous and piecewise affine in t. For an activation pattern σ⊆[h]σ [h], define ℓσ _σ =∑i∈σdi(W1)i,:⊤, = _i∈σd_i(W_1)_i,: , cσ c_σ =b+∑i∈σdib1,i, =b+ _i∈σd_ib_1,i, δσ _σ =ℓσ⊤(v1−v0), = _σ (v_1-v_0), ξσ _σ =CV⊤ℓσ, =C_V _σ, (136) and cσ∗=−ℓσ⊤v0+Γv11+Γ−ξσ⊤μ.c_σ^*=- _σ v_0+ v_11+ - _σ μ. (137) Lemma 10 (Positional compensation). Outside a set of raw-cube measure zero, every exact solution at a sufficiently large odd length has an activation pattern σ⊆[h]σ [h] such that δσ≠0 _σ≠ 0 and ‖a+sinhλδσξσ‖2≤Cn, \|a+ λ _σ _σ \|_2≤ Cn, (138) while |cσ−cσ∗|≤C|δσ|nΓ(1+Γ)2.|c_σ-c_σ^*|≤ C| _σ|n (1+ )^2. (139) The constants are uniform over the bounded raw parameter cube, including when q and δσ _σ are arbitrarily small but nonzero. Proof. Exclude first the finite union of sets on which one of the affine pieces defined below vanishes at t=0t=0; each is null by slicing along b2,1b_2,1. On activation pattern σ, the denominator-scaled logit difference is an affine function Lσ(t)=Lσ(0)+∑jℓ^σ,jtjL_σ(t)=L_σ(0)+ _j _σ,jt_j, where ℓ^σ,j=Pj(κσ+νσ⊤pj),κσ=ℓσ⊤(Γv1−v0)+(Γ−1)cσ,νσ=(Γ−1)ξσ. _σ,j=P_j( _σ+ _σ p_j), _σ= _σ ( v_1-v_0)+( -1)c_σ, _σ=( -1) _σ. (140) Fix t∈[0,1]nt∈[0,1]^n with ∑jtj=n/2 _jt_j=n/2. Preserving ∑jtj _jt_j, ∑jPjtj _jP_jt_j, ∑jPjsinjtj _jP_j j\,t_j, and ∑jPjcosjtj _jP_j j\,t_j, one can move to a point with at most four fractional coordinates. Rounding those coordinates to words with respectively m and m+1m+1 ones and using exact correctness forces a zero of one affine piece within four coordinate changes. Applying this to the centrally symmetric convex body generated by Pj(1,pj)∈ℝ3P_j(1,p_j) ^3 and using the elementary convex-body slab bound yields, for some σ, ∑j=1n|ℓ^σ,j−med(ℓ^σ,1,…,ℓ^σ,n)|≤ChMσ,|Lσ(12)|≤ChMσ, _j=1^n | _σ,j-med( _σ,1,…, _σ,n) |≤ C_hM_σ, |L_σ\! ( 121 ) |≤ C_hM_σ, (141) where Mσ=maxj|ℓ^σ,j|M_σ= _j| _σ,j|. The fixed phases jmod2πj 2π are equidistributed because |∑j=1neikj|=Ok(1)| _j=1^ne^ikj|=O_k(1) for each fixed nonzero integer k. Applied to the sequence ea⊤pj(κσ+νσ⊤pj)e^a p_j( _σ+ _σ p_j), the first inequality in (141) first bounds ‖a‖2\|a\|_2, then a compactness argument forces a and νσ/κσ _σ/ _σ to approach zero, and finally the first two discrete Fourier modes of the second-order Taylor expansion give κσ≠0,Mσ≍|κσ|,‖a‖22≤Cn,‖a+νσκσ‖2≤Cn. _σ≠ 0, M_σ | _σ|, \|a\|_2^2≤ Cn, \|a+ _σ _σ \|_2≤ Cn. (142) To return to the raw parameters, put ec=cσ−cσ∗e_c=c_σ-c_σ^* and τ=2Γδσ/(1+Γ)τ=2 _σ/(1+ ). Direct substitution gives Lσ(12)=(1+Γ)T2ec,κσ=τ−νσ⊤μ+(Γ−1)ec.L_σ\! ( 121 )= (1+ )T2e_c, _σ=τ- _σ μ+( -1)e_c. (143) Since T≍nT n, (141) and (142) imply |ec|≤C|κσ|/((1+Γ)n)|e_c|≤ C| _σ|/((1+ )n) and |κσ−τ|≤Cn−1/2|κσ|| _σ-τ|≤ Cn^-1/2| _σ|. Hence δσ≠0 _σ≠ 0, |τ|≍|κσ||τ| | _σ|, and ‖νσ/τ−νσ/κσ‖2≤C/n\| _σ/τ- _σ/ _σ\|_2≤ C/n. Using νσ/τ=(sinhλ/δσ)ξσ _σ/τ=( λ/ _σ) _σ proves (138), and the bound on ece_c proves (139). ∎ C.3 Volume integration Proof of Theorem 9. For the upper bound, fix one of the finitely many activation patterns σ and condition on q, the two symbol key columns, and all value and classifier coordinates except b2,1b_2,1, leaving the two positional key columns unconditioned. Each coordinate of (138) restricts one independent positional key column to a slab whose conditional normalized width is at most CBmin1,1nβn‖q‖∞.C_B \1, 1n _n\|q\|_∞ \. (144) The two columns use disjoint raw coordinates. After they are fixed, (139) restricts b2,1b_2,1 to an interval of normalized length OB,h(1/n)O_B,h(1/n). Summing over σ and integrating t=‖q‖∞t=\|q\|_∞, whose density under the uniform square measure is proportional to t, gives VBMajority,sin,gen(h)(n) V_B Majority,A_sin,gen(h)(n) ≤CB,hn∫0Btmin1,1nβnt2t ≤ C_B,hn _0^Bt \1, 1n _nt \^2dt ≤CB,h(1+log(nβn))n3βn2=OB,h(1n3logn). ≤ C_B,h(1+ (n _n))n^3 _n^2=O_B,h\! ( 1n^3 n ). (145) For the lower bound, restrict the value and classifier coordinates to a fixed positive-volume open box on which the bias-free logit difference has the form ℓ⊤A+cH A+c_H for every attainable attention output, with constants 0<δ−≤δ:=ℓ⊤(v1−v0)≤δ+0< _-≤δ:= (v_1-v_0)≤ _+ and ξ=CV⊤ℓξ=C_V satisfying ‖ξ‖2/δ≤1/100\|ξ\|_2/δ≤ 1/100. Such a box is obtained from an interior center with v0=0v_0=0, v1=η(1,0)⊤v_1=η(1,0) , CV=0C_V=0, and one uniformly active hidden unit. Set A∗=v0+Γv11+Γ+CVμ,b2,1∗=b2,0−cH−ℓ⊤A∗.A^*= v_0+ v_11+ +C_Vμ, b_2,1^*=b_2,0-c_H- A^*. (146) At this centered bias, the exact logit difference is (y(w))1−(y(w))0=∑j(wj−1/2)ℓ^j(w),ℓ^j=Pj[2Γδ1+Γ+(Γ−1)ξ⊤(pj−μ)].(y(w))_1-(y(w))_0= _j(w_j-1/2) _j D(w), _j=P_j [ 2 δ1+ +( -1)ξ (p_j-μ) ]. (147) If |λ|≤c1n−1/2|λ|≤ c_1n^-1/2 and ‖a+(sinhλ/δ)ξ‖2≤c2/n\|a+( λ/δ)ξ\|_2≤ c_2/n, a uniform first-order expansion of (147) gives ℓ^j/τ=F0+O(1/n) _j/τ=F_0+O(1/n) with τ=2Γδ/(1+Γ)τ=2 δ/(1+ ) and F0≥3/4F_0≥ 3/4. Therefore the numerator has the Majority sign and magnitude bounded below by a positive constant, while (w)=O(n) D(w)=O(n); an interval |b2,1−b2,1∗|<c3/n|b_2,1-b_2,1^*|<c_3/n preserves strict correctness on every input. It remains to measure a full-dimensional set satisfying these conditions. Restrict the query bias to q1>0,|q2|≤q1/4,r:=βnq1∈[Ln,cn].q_1>0, |q_2|≤ q_1/4, r:= _nq_1∈ [ Ln, c n ]. (148) For sufficiently small c, the symbol key columns may vary over their full raw squares while |λ|≤c1n−1/2|λ|≤ c_1n^-1/2. Conditional on these choices and on the decoder box, the two coordinates of the compensation condition restrict one entry of each positional key column to an interval of length Θ(1/(nr)) (1/(nr)); fixed-width restrictions on the other entries keep these intervals inside the raw cube. Their joint normalized mass is therefore ΩB,h(1/(n2r2)) _B,h(1/(n^2r^2)), and the admissible output-bias interval contributes ΩB,h(1/n) _B,h(1/n). Since the query-cone measure after integrating q2q_2 is a constant multiple of rdr/βn2r\,dr/ _n^2, VBMajority,sin,gen(h)(n) V_B Majority,A_sin,gen(h)(n) ≥cB,hn3βn2∫L/nc/ndr ≥ c_B,hn^3 _n^2 _L/n^c/ n drr ≥cB,h′n3logn. ≥ c _B,hn^3 n. (149) Every restricted raw coordinate varies over an interval of positive width and every unrestricted coordinate integrates out, so this is a full-dimensional lower bound. Together with (145), it proves the theorem. ∎ Appendix D Experimental Details and Selected Additional Results This appendix specifies the experimental protocol used for the main-text comparisons and reports the additional results referenced in the discussion of sinusoidal positional encoding. D.1 Reported models and benchmark provenance The baseline positional implementation is the model pos(h)A_pos(h) from Section 2, with quadratic positional coordinates (j,j2)(j,j^2), and the selectively normalized implementation is norm(h)A_norm(h) from Section 4.2. For the baseline Majority experiment, we use the unrestricted affine NoPE implementation of gen(h)A_gen(h). The additional sinusoidal Majority control is the fixed-frequency general model sin(h)A_sin(h) defined in Section C.1. We use the same 2020 seeds, 20002000–20192019, at each maximum training length N∈11,21,31,41,51.N∈\11,21,31,41,51\. (150) Training and qualification did not have access to the test banks, and every newly trained checkpoint was selected and frozen before its test evaluation. D.2 Training, selection, and initialization Training uses Adam with learning rate 3×10−43× 10^-4, β1=0.9 _1=0.9, β2=0.999 _2=0.999, numerical stabilizer 10−810^-8, no weight decay, batch size 256256, and gradient-norm clipping at one. Each update uses a fresh batch of independent uniformly random bits. For Index, the index k is sampled uniformly from the positions in the sampled sequence. For First and Index, one data length is sampled uniformly from 1,…,N\1,…,N\ per batch. For Majority, the sampled length is uniform over the odd integers in that range. Computation uses float64. At data length L, attention scores are multiplied by logL L, without an additional 1/d1/ d factor. Every run is trained for at most 30,00030,000 updates and is validated every 500500 updates on a fixed bank of 1,0001,000 examples at length N. Training stops after three consecutive perfect validations. The selected checkpoint maximizes validation accuracy; ties are resolved first by lower cross-entropy and then by the earlier update. No input longer than N is used in checkpoint selection. For the pos(h)A_pos(h) and norm(h)A_norm(h) models, the vectors a,r,s,b,cKa,r,s,b,c_K are initialized from centered normal distributions with standard deviations 0.1/N0.1/N, 0.1/N0.1/N, 0.1/N20.1/N^2, 0.10.1, 0.10.1, respectively. Other parameters use Xavier-uniform initialization and their biases are zero. pos(h)A_pos(h)/norm(h)A_norm(h) pairs use identical initial tensors and the same training streams. For genA_gen and sinA_sin, content query/key blocks and the bounded sinusoidal positional blocks use Xavier-uniform initialization, while shared value, bias, and classifier blocks are copied from the paired posA_pos seed. D.3 Evaluation banks, metrics, and uncertainty For a maximum training length N, the common test grid is N,2N+1,3N,5N,8N+1,10N+1.N, 2N+1, 3N, 5N, 8N+1, 10N+1. (151) At each test length, all seeds and model variants for the same task use the same saved bank of 1,0001,000 examples. For First, the first bit is exactly balanced and the remaining bits are random. For Majority, 500500 random strings are paired with their complements. For Index, each of 500500 random string–query pairs is paired with the complemented string and the same query. Test accuracy is the fraction correct on one saved bank. The longest-test statistic is the mean across the 2020 seeds at L=10N+1L=10N+1. For coefficient analyses and other OOD summaries, the seed-level mean OOD accuracy is the equal-weight mean across the five test lengths strictly greater than N. Confidence intervals are pointwise percentile 95%95\% intervals. D.4 Coefficient analysis The coefficient analysis uses the 100100 selected Index checkpoints on posA_pos: 2020 seeds at each of the five values of N in (150). For each checkpoint, we compute χ=a⊤s,ℓ=2b⊤s+a⊤rχ=a s, =2b s+a r (152) directly from the learned parameters. To avoid treating differences among the five training maxima as evidence for a coefficient association, we rank each coefficient magnitude and the seed-level mean OOD accuracy separately within each value of N, and then pool the within-N ranks. The resulting correlations are −0.655-0.655 for N2|χ|N^2|χ| and −0.516-0.516 for N|ℓ|N| |. The two-sided permutation test uses 10,00010,000 permutations and shuffles ranks only within the same value of N; both tests give p<10−3p<10^-3. D.5 Selected results across maximum training lengths Table 2 reports the longest-test results. Each entry is the mean percentage accuracy across 2020 seeds, followed by its pointwise 95%95\% seed-bootstrap interval. Table 2: Accuracy at the longest tested length L=10N+1L=10N+1. Entries are percentages, with pointwise 95%95\% seed-bootstrap intervals in parentheses. N L First (posA_pos) Majority (genA_gen) Index (posA_pos) Index (normA_norm) 11 111 100.0 (100.0–100.0) 83.8 (78.0–89.4) 57.2 (55.9–58.6) 63.4 (62.7–64.1) 21 211 100.0 (100.0–100.0) 91.3 (86.2–95.3) 55.2 (54.1–56.5) 74.1 (68.8–79.9) 31 311 100.0 (100.0–100.0) 87.1 (82.6–91.5) 59.2 (58.3–60.0) 90.6 (85.6–95.4) 41 411 100.0 (100.0–100.0) 88.5 (84.2–92.2) 55.1 (54.5–55.8) 84.4 (78.1–90.6) 51 511 100.0 (100.0–100.0) 82.6 (77.6–87.5) 59.6 (58.6–60.6) 85.1 (80.2–90.1) D.6 Sinusoidal positional encoding on Majority Relevant results on the performance of sinA_sin compared to genA_gen on Majority is displayed in Table 3. Table 3: Mean OOD accuracy on Majority for genA_gen and sinA_sin general models. Entries are percentages, averaged equally over the five test lengths above N, with 95%95\% confidence intervals in parentheses. N NoPE General Sinusoidal General 11 91.6 (88.1–95.0) 95.3 (93.6–96.8) 21 95.1 (91.8–97.6) 93.8 (91.5–95.9) 31 92.9 (90.0–95.6) 91.2 (88.2–94.0) 41 93.4 (90.6–95.8) 91.5 (88.7–94.1) 51 89.8 (86.2–92.9) 92.9 (90.0–95.6) D.7 Sanity checks for norm(h)A_norm(h) on other tasks We also compared pos(h)A_pos(h) to norm(h)A_norm(h) on First and Majority. For First, both positional models achieve 100%100\% mean accuracy at L=10N+1L=10N+1 for every N in (150). For our setup of Majority, posA_pos and normA_norm are equivalent, hence producing same results for every seed.