Paper deep dive
Indexing: the Beginning and the End
Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study information bottlenecks in modern deep-learning architectures -- RNNs, softmax transformers, linear-attention transformers and state-space models -- through the lens of the indexing primitive. In this primitive, the input consists of $n$ bits and one integer $i$ from $1$ to $n$ called the index, and the output equals the value of the $i$-th bit. We introduce causal complexity for masked architectures. We show that architectures with low causal complexity cannot solve the indexing primitive in any constant number of layers when the index appears at the end of the input. In particular, this limitation applies to low-parameter RNNs, SSMs and masked linear-attention transformers. In contrast, small softmax transformers can solve it in one layer, while non-masked linear-attention transformers can solve it in 2, which separates them from their masked counterparts. In turn, when the index appears at the beginning, we show that small RNNs are capable of solving this task in 1 layer, while all the other architectures require 2. All our impossibility results are unconditional and apply even to models that employ infinite-precision real arithmetic. Moreover, experiments for up to $n=64$ qualitatively align with our theory: configurations with low-parameter theoretical solutions learn the indexing task easily, while configurations that do not admit such theoretical solutions struggle to learn as the sequence length grows.
Tags
Links
- Source: https://arxiv.org/abs/2607.22361v1
- Canonical: https://arxiv.org/abs/2607.22361v1
Trouble viewing inline? Open PDF directly →
Full Text
62,737 characters extracted from source content.
Expand or collapse full text
Indexing: the Beginning and the End Alexander Kozachinskiy CENIA alexander.kozachinskyi@cenia.cl Vicente Opazo CENIA vicente.opazo@cenia.cl Felipe Urrutia Pontifical Catholic University of Chile felipe.urrutia@uc.cl Abstract We study information bottlenecks in modern deep-learning architectures – RNNs, softmax transformers, linear-attention transformers and state-space models – through the lens of the indexing primitive. In this primitive, the input consists of n bits and one integer i from 11 to n called the index, and the output equals the value of the i-th bit. We introduce causal complexity for masked architectures. We show that architectures with low causal complexity cannot solve the indexing primitive in any constant number of layers when the index appears at the end of the input. In particular, this limitation applies to low-parameter RNNs, SSMs and masked linear-attention transformers. In contrast, small softmax transformers can solve it in one layer, while non-masked linear-attention transformers can solve it in 2, which separates them from their masked counterparts. In turn, when the index appears at the beginning, we show that small RNNs are capable of solving this task in 1 layer, while all the other architectures require 2. All our impossibility results are unconditional and apply even to models that employ infinite-precision real arithmetic. Moreover, experiments for up to n=64n=64 qualitatively align with our theory: configurations with low-parameter theoretical solutions learn the indexing task easily, while configurations that do not admit such theoretical solutions struggle to learn as the sequence length grows. 1 Introduction Part of the research on the expressivity of transformers (Strobl et al.,, 2024) has been revolving around their ability to compute certain fundamental primitives. These primitives are supposed to be a mathematical abstraction of some challenges that arise in processing information by transformers. The most well-studied primitive is the function composition. It has been linked to the transformers’ ability to infer implicit facts through compositional generalization (Peng et al.,, 2024; Guan et al.,, 2024). For instance, the training data may contain the birth year of a singer A and the Nobel Prize winners for each year, but not explicitly answer the question “who won the Nobel Prize in Physics in the year A was born?” Answering it requires composing a function mapping people to birth years with one mapping years to Nobel Prize winners. Mathematically, this inference is abstracted as the following task: given two functions f,g:[n]→[n]f,g [n]→[n] as lists of values, and an index i∈[n]i∈[n], compute g(f(i))g(f(i)), where [n]=1,…,n[n]=\1,…,n\. Peng et al., (2024) introduced this task and used communication complexity to show that 1-layer transformers with no(1)n^o(1) parameters and no(1)n^o(1) bits of precision cannot solve it. They further showed that such transformers require Ω(k) (k) chain-of-thought iterations for k-fold composition, i↦fk∘fk−1∘…∘f1(i).i f_k f_k-1 … f_1(i). Afterwards, Kozachinskiy et al., (2025) removed the bounded-precision assumption, proving the same impossibility for infinite-precision 1-layer transformers with no(1)n^o(1) parameters. They have also introduced the binary relation composition primitive and have conjectured that it cannot be done by O(1)O(1)-layer small transformers. At the same time, Barcelo et al., (2025) showed that k-fold composition requires exactly k chain-of-thought steps for 1-layer transformers of any size, although only under unique hard attention. In their breakthrough work, Chen et al., (2025) were able to extend this analysis to multi-layer transformers. They have shown that no(1)n^o(1)-parameter no(1)n^o(1)-precision transformers with masking require k layers to solve a variation of the k-fold function composition task, but full-attention transformers can solve it in O(logk)O( k) layers. Their technique is based on “autoregressive” communication complexity and thus requires assumptions about bits of precision. It is open to obtain lower bounds on multi-layer infinite-precision transformers, even with masking. Another primitive that arose from mechanistic interpretability is the induction heads task. Given a sequence of symbols, the goal is to predict what will go after the last symbol. One simple strategy is – take the closest previous appearance of the last symbol in the sequence and look what goes after it. It was observed empirically that this mechanism is widely used by transformer language models (Elhage et al.,, 2021; Olsson et al.,, 2022). In turn, Sanford et al., (2024) have shown that small 1-layer transformers cannot do this primitive while small 2-layer can (their notion of “small” includes the assumptions about the number of bits of precision). Recently, Strobl et al., (2025) have turned their attention to an even more basic primitive of function evaluation – given a function f:1,2,…,n→1,2,…,nf \1,2,…,n\→\1,2,…,n\ and an input i, output f(i)f(i). They have found out that even this simple task might be hard for small 1-layer transformers under some assumptions about input representation. Their result applies even to infinite-precision transformers. As we see, there is a rich literature on the analysis of these primitives for transformers. However, more modern architectures, aimed to circumvent the computational bottlenecks of transformers – like Mamba (Gu and Dao,, 2023) or linear-attention transformers (Katharopoulos et al.,, 2020) – still wait their turn. In this paper, we address this gap by studying a version of function evaluation primitive called indexing – which is essentially the function evaluation for functions that take just two values, 0 and 1. Our analysis includes standard transformers, linear-attention transformers, state-space models (SSMs), and “pre-transformer” RNNs. Albeit very simple, the indexing primitive surprisingly reveals a rich interplay between these architectures, and provides insights on how they process information in a form of rigorous mathematical results. Moreover, it allows us to obtain the first multi-layer infinite-precision lower bounds – although not for transformers, but for a class of architectures with low causal complexity – including SSMs, RNNs, and masked linear-attention transformers. We now describe our results in more detail. Our results In the indexing task, we are given n bits σ1,…,σn∈0,1 _1,…, _n∈\0,1\ and a number i∈1,2,…,ni∈\1,2,…,n\ called the index. The goal is to output σi _i. Observe that it can be seen as a function evaluation task for a function of the form σ:1,2,…,n→0,1σ \1,2,…,n\→\0,1\. We consider two versions of this task. In the left-hand indexing, the token with i is the first one while the answer has to be computed in the special end-token. In the right-hand indexing, the token with i is the last one, and the answer has to be computed in it. In both versions, there is also a token for each of the bits σ1,…,σn _1,…, _n. Our contribution is summarized as follows. • For causal architectures, or architectures with masking – those where the output in k-th position does not depend on input in the positions after k – we introduce the notion of causal complexity of a layer. Intuitively, it measures the minimal dimension to which the first k−1k-1 inputs to a layer can be compressed so that then the k-th output can be “easily” computed from this compressed representation and the k-th input. We show that no O(1)O(1) layers with no(1)n^o(1) causal complexity can solve the right-hand indexing task. We then observe that “small” (no(1)n^o(1)-parameter) masked linear-attention, Mamba and RNN layers all have no(1)n^o(1) causal complexity, deriving the corresponding limitations for these architectures. Once again, our lower bound technique applies even in the infinite-precision regime. Thus, we conclude that no O(1)O(1) small layers of these architectures, even if they use infinite-precision computations, can solve the right-hand indexing task. • In contrast, as it essentially was observed in previous works (Strobl et al.,, 2025) standard 1-layer transformers can solve the right-hand indexing task with O(1)O(1) parameters. This is explained by their high causal complexity compared to other architectures. We also show that 2-layer non-masked linear-attention transformers with O(1)O(1) parameters can solve the right-hand indexing task as well. This separates them from their masked version which cannot solve the task in any constant number of no(1)n^o(1)-parameter layers. • Finally, we observe that in the left-hand indexing task, RNNs prevail over all other architectures. While RNNs can solve it in 1 layer with O(1)O(1) parameters, neither standard attention, nor linear-attention, nor Mamba can solve it in 1 layer with no(1)n^o(1) parameters (but all of them can solve it in 2 layers with O(1)O(1) parameters, with or without masking). Our results exploit information bottlenecks in the aforementioned architectures. In the right-hand indexing task, the bits are processed before the index. Thus, at the moment when index is considered, the information we receive from the previous positions must essentially allow us to recover the whole n-bit string. But such memory capacity turns out to be bounded by the causal complexity, which is low for every masked architecture in question except transformers. In turn, in the left-hand indexing task, the indexed i is processed first, and intuitively it should be then carried over the input until we reach the i-th position. Then the bit at this position should be remembered and carried over to the end. RNNs are perfectly suitable for this task, while, for instance, SSMs, which are sometimes viewed as parallelizable alternatives to RNNs because of their linear update rule, struggle on this task – precisely, as we will show, because of that linearity. The following table summarizes our results, indicating for each architecture the minimal number of “small” layers needed to solve the left-hand and the right-hand indexing tasks. Architecture LHI RHI Full softmax 2 1 Causal softmax 2 1 Full linear-attention 2 2 Causal linear-attention 2 ω(1)ω(1) SSM 2 ω(1)ω(1) RNN 1 ω(1)ω(1) Table 1: Minimum number of no(1)n^o(1)-parameter layers required for the left-hand indexing (LHI) and the right-hand indexing (RHI). Recall that the ω(1)ω(1) notation means “is not bounded by a constant”. All our impossibility results hold even for models that use infinite-precision computations with real numbers. We achieve this via adapting the VC dimension technique of Kozachinskiy et al., (2025) beyond the transformers context. Finally, we experimentally test whether existence or absence of a low-parameter theoretical solution correlates with the ability to learn the indexing task in practice. First, we find that already at length n=64n=64 the configurations on the lower-bound side consistently fail under our fixed training protocol. Across all seeds, causal linear-attention transformers, RNNs and Mamba (all with up to 4 layers) consistently fail to learn the right-hand indexing, as well as 1-layer transformers (softmax and linear) and 1-layer Mamba – the left-hand indexing. As for the “existence results” (upper bounds), the situation seems to depend on the positional encoding. We found that polynomial positional encoding leads to the strongest agreement with our theory: among the 160 non-redundant constructive runs represented in our summary, only two failed to learn the task perfectly. 1.1 Further related work Study of the expressive power of transformers is not limited to the study of the above primitives. For instance, part of the research was dedicated to showing that these machines, equipped with the mechanism of autoregressively generating tokens, are capable of simulating any computation (Pérez et al.,, 2021; Merrill and Sabharwal,, 2024; Jiang et al.,, 2025). A significant part of the literature is devoted to obtaining limitations for computing formal languages, using methods from computational complexity and logic (Hahn,, 2020; Chiang et al.,, 2023; Yang et al.,, 2024; Sälzer et al.,, 2025). As for RNNs, long before the deep learning era it was observed that they are capable of simulating finite automata (Minsky,, 1967). Moreover, when one allows arbitrary rational weights and an unbounded number of intermediate steps after processing the input, they are capable of simulating Turing machines (Siegelmann and Sontag,, 1994). Very recently, Merrill et al., (2026) gave an example of a task, doable by a hybrid architecture (RNNs + transformers) but not by RNNs or transformers separately, under standard complexity assumptions. In turn, SSMs have been investigated from the viewpoint of their ability to overcome limitations of transformers in recurrent computations (Merrill et al.,, 2024) – as a more scalable alternative to RNNs in this matter. It was observed that this hugely depends on design choices. For instance, Mamba is not capable of performing summation over the group ℤ2Z_2 (Sarrof et al.,, 2024), while more general diagonalizable SSMs, under finite-precision assumption, are capable of performing summation over a finite group if and only if this group is solvable (Shakerinava et al.,, 2026). 2 Preliminaries 2.1 VC dimension and arithmetic complexity Definition 1. Let f:ℝn→ℝmf ^n ^m. Its arithmetic complexity, denoted by AC(f)AC(f), is the minimal t∈ℕt such that f can be computed by some algorithm in no more than t of the following operations: • the exponential function α↦eα e^α on real numbers; • the arithmetic operations +,−,×,/+,-,×,/ on real numbers; • jumps conditioned on >,=>,= comparisons of real numbers; • output a constant or a previously computed value. (If no such t exists, we set AC(f)=+∞AC(f)=+∞.) By a concept class we mean a function C:ℝn×ℝp→0,1C ^n×R^p→\0,1\. The first n coordinates form an input, and the last p coordinates form parameters. Definition 2. Let C:ℝn×ℝp→0,1C ^n×R^p→\0,1\ be a concept class. Its VC dimension, denoted by VCdim(C)VCdim(C), is the maximal natural number d such that for some x1,…,xd∈ℝnx^1,…,x^d ^n, the following holds. For every d-bit string α=α1…αd∈0,1dα= _1… _d∈\0,1\^d there exists y∈ℝpy ^p such that: C(x1,y)=α1,…,C(xd,y)=αd.C(x^1,y)= _1,…,C(x^d,y)= _d. Theorem 3 ((Anthony and Bartlett,, 2009) Theorem 8.14). Let C be a concept class with p parameters. Then VCdim(C)=O(AC(C)2⋅p2).VCdim(C)=O(AC(C)^2· p^2). 2.2 Layers and tasks We work with a notion of a layer. In general, a layer with input length n and input-output dimension d (in short, an (n,d)(n,d)-layer) is any function f:(ℝd)n→(ℝd)nf (R^d)^n→(R^d)^n. By tasks we formally mean functions T:Σ1×…×Σn→ΓT _1×…× _n→ , where Σ1,…,Σn,Γ _1,…, _n, are finite sets. Here n is the input length of a task. We imagine that the input to a task is given in a sequence of n tokens: the first token contains an element σ1∈Σ1 _1∈ _1, the second token contains an element σ2∈Σ2 _2∈ _2, and so on. The goal is to compute T(σ1…σn)T( _1… _n). We now formalize what it means that L layers f1,…,fLf_1,…,f_L solve a task T. Definition 4. Let T:Σ1×…×Σn→ΓT _1×…× _n→ be a task, and f1,…,fLf_1,…,f_L be (n,d)(n,d)-layers. We say that f1,…,fLf_1,…,f_L solve T if there exists a function p:Σ1×1∪…∪Σn×n→ℝd,p _1×\1\∪…∪ _n×\n\ ^d, (usually referred to as input-position embedding), and a matrix A∈ℝΓ×dA × d (usually referred to as output-distribution matrix) such that for any σ1…σn∈Σ1×…×Σn _1… _n∈ _1×…× _n, the following holds. Calculate x1=p(σ1,1),…,xn=p(σn,n),x_1=p( _1,1),…,x_n=p( _n,n), (y1,…,yn)=fL∘…∘f1((x1,…,xn)),(y_1,…,y_n)=f_L … f_1((x_1,…,x_n)), α=Ayn∈ℝΓ.α=Ay_n . Then, denoting γ=T(σ1…σn)γ=T( _1… _n), we have αγ>αγ′ _γ> _γ for all γ′∈Γ∖γ ∈ \γ\. Indexing task. The indexing task is the following task: given n bits σ1,…,σn∈0,1 _1,…, _n∈\0,1\ and a number i∈1,2,…,ni∈\1,2,…,n\, the goal is to output σi _i. We consider two variations – the right-hand indexing task where the input is given via n+1n+1 tokens; the last one (where the output should be computed) has i. The left-hand indexing task assumes n+2n+2 tokens, first goes the token with i, then tokens with σ1,…,σn _1,…, _n, and then a special end token. 2.3 Attention, RNNs, SSMs We define several types of layers from relevant architectures of interest. For each of them, we define the notion of size, referring to the number of learnable parameters in their MLPs (that, unless stated otherwise, are assumed to use the ReLU activation). We also take into account arithmetic complexity of some non-polynomial components of the architectures. The size always includes a term d – the dimension of the layer – and thus upper bounds the dimension. Definition 5. A causal softmax transformer (n,d)(n,d)-layer is given by 3 matrices K,Q,V∈ℝd×dK,Q,V ^d× d and an MLP :ℝd→ℝdN ^d ^d. On input (x1,…,xn)∈(ℝd)n(x_1,…,x_n)∈(R^d)^n, the following computations are performed to produce the output sequence (y1,…,yn)∈(ℝd)n(y_1,…,y_n)∈(R^d)^n. First, vℓ=Vxℓ,qℓ=Qxℓ,kℓ=Kxℓv_ =Vx_ , q_ =Qx_ , k_ =Kx_ for ℓ=1,…,n =1,…,n. Then ak=∑ℓ=1kvℓexpkℓTqk∑ℓ=1kexpkℓTqk,k=1,…,n,a_k= Σ _ =1^kv_ \k_ ^Tq_k\Σ _ =1^k \k_ ^Tq_k\, k=1,…,n, (1) and then yk=(xk+ak),k=1,…,ny_k=N(x_k+a_k), k=1,…,n In a full softmax transformer layer, the upper limits in the sums in (1) are changed from k to n. The size of the layer is 3d23d^2 plus the number of learnable parameters of N. Definition 6. A causal linear-attention (n,d)(n,d)-layer is given by 3 matrices K,Q,V∈ℝd×dK,Q,V ^d× d, a kernel function ϕ:ℝd→(0,+∞)dφ ^d→(0,+∞)^d and an MLP :ℝd→ℝdN ^d ^d. On input (x1,…,xn)∈(ℝd)n(x_1,…,x_n)∈(R^d)^n, the following computations are performed to produce the output sequence (y1,…,yn)∈(ℝd)n(y_1,…,y_n)∈(R^d)^n. First, vℓ=Vxℓ,qℓ=Qxℓ,kℓ=Kxℓv_ =Vx_ , q_ =Qx_ , k_ =Kx_ for ℓ=1,…,n =1,…,n. Then ak a_k =∑ℓ=1kvℓ⋅ϕ(kℓ)Tϕ(qk)∑ℓ=1kϕ(kℓ)Tϕ(qk),k=1,…,n, = Σ _ =1^kv_ ·φ(k_ )^Tφ(q_k)Σ _ =1^kφ(k_ )^Tφ(q_k), k=1,…,n, (2) yk y_k =(xk+ak),k=1,…,n. =N(x_k+a_k), k=1,…,n. (3) In a full linear-attention layer, the upper limit in the sums in (2) are changed from k to n. The size of the layer is 3d23d^2 plus the number of learnable parameters of N, plus the arithmetic complexity of the kernel function ϕφ. For instance, in (Katharopoulos et al.,, 2020) the following kernel function is used: ϕ:(x1,…,xd)↦(elu(x1)+1,…,elu(xd)+1),φ (x_1,…,x_d) (elu(x_1)+1,…,elu(x_d)+1), where elu(x)=x>0α(ex−1)x≤0elu(x)= casesx&x>0\\ α(e^x-1)&x≤ 0 cases for some positive constant α. This example has O(d)O(d) arithmetic complexity. Another common choice is to use ReLU instead of elu, where the arithmetic complexity is still O(d)O(d). Remark 7. For a one-layer softmax or linear-attention transformer, full and causal attention induce the same computation at the final readout token. Indeed, the answer is computed from the last token which sees all tokens in both models, and does not yet use the attention computations in these tokens. Definition 8. An SSM layer of dimension d is given by three maps A:ℝd→ℝd×d,B:ℝd→ℝd,ϕ:ℝ2d→ℝdA ^d ^d× d,B ^d ^d,φ ^2d ^d and vector h0∈ℝdh_0 ^d. On input (x1,…,xn)∈(ℝd)n(x_1,…,x_n)∈(R^d)^n the output sequence of vectors (y1,…,yn)∈(ℝd)n(y_1,…,y_n)∈(R^d)^n is computed as follows: for k=1,…,nk=1,…,n, compute hk h_k =A(xk)hk−1+B(xk), =A(x_k)h_k-1+B(x_k), (4) yk y_k =ϕ(xk,hk). =φ(x_k,h_k). (5) The size of the layer is d2+2d^2+2d plus the arithmetic complexities of A,B,ϕA,B,φ. For instance, in Mamba (Gu and Dao,, 2023), A(xt)A(x_t) is a constant d×d× d matrix, and B(xt)B(x_t) is defined as a multiplication of the vector xtx_t by another constant d×d× d matrix. Thus, these maps have O(d2)O(d^2) arithmetic complexity. In turn, ϕφ in Mamba can be seen as an MLP with the SiLU/Swish activation (Ramachandran et al.,, 2018), which can be expressed using exponentials and standard arithmetic operations. Thus, such ϕφ also has poly(d)poly(d) arithmetic complexity. Additionally, Mamba has an optional normalization layer for ϕφ using LayerNorm of Ba et al., (2016). Unfortunately, such a layer cannot be easily handled in our theoretical setting due to its use of the square root function which is not an operation permitted in Definition 1. Thus, with layernorm, we no longer have good upper bounds on the VC dimension guaranteed by Theorem 3 that we require for our proofs. One can incorporate this type of layers with the use of bounds on the VC dimension for Pfaffian activation functions due to Karpinski and Macintyre, (1997). However, the way these results are formulated requires a significant additional technical work in order to apply to our setting which we omit in the current version for simplicity. Definition 9. An RNN layer of dimension d is given by two MLPs 1,2:ℝ2d→ℝdN_1,N_2 ^2d ^d. On input (x1,…,xn)∈(ℝd)n(x_1,…,x_n)∈(R^d)^n, the output sequence of vectors (y1,…,yn)∈(ℝd)n(y_1,…,y_n)∈(R^d)^n is computed as follows: set h0=0∈ℝdh_0=0 ^d and for k=1,…,nk=1,…,n, compute hk h_k =1(xk,hk−1), =N_1(x_k,h_k-1), (6) yk y_k =2(xk,hk). =N_2(x_k,h_k). (7) The size of the layer is d plus the number of learnable parameters of 1,2N_1,N_2. 3 Right-hand Indexing and Causal Architectures Definition 10. An (n,d)(n,d)-layer f is causal if the i-th output of the layer is the function of the first i input vectors, for every i=1,…,ni=1,…,n. Definition 11. Let f be an (n,d)(n,d)-causal layer. Its causal complexity is the minimal natural number s≥ds≥ d such that for some p,t∈ℕp,t with p+t≤sp+t≤ s, the following holds. For any k=2,…,nk=2,…,n, there exist a “fingerprint” function ϕk:(ℝd)k−1→ℝp _k:(R^d)^k-1 ^p such that the k-th output vector, yky_k, on input (x1,…,xn)∈(ℝd)n(x_1,…,x_n)∈(R^d)^n, is the function of the fingerprint fk=ϕk(x1,…,xk−1)f_k= _k(x_1,…,x_k-1) and of xkx_k, and, moreover, this function (fk,xk)↦yk(f_k,x_k) y_k has arithmetic complexity at most t. Theorem 12. a) No O(1)O(1) causal layers of causal complexity no(1)n^o(1) can solve the right-hand indexing task. b) Two full linear-attention layers of O(1)O(1)-size can solve the right-hand indexing task; c) One softmax transformer layer of O(1)O(1)-size can solve the right-hand indexing task. Proof. a) Assume for contradiction that there exist L=O(1)L=O(1) causal layers f1,…,fLf_1,…,f_L of causal complexity no(1)n^o(1) that solve the right-hand indexing task (σ1,…,σn,i)↦σi.( _1,…, _n,i) _i. We employ the definition of the causal complexity with respect to the (n+1)(n+1)-st token, one with the index i. First, this input token is transformed via some input embedding into a vector xn+1(i)∈ℝdx_n+1(i) ^d. Next, the input binary word σ=σ1…σn∈0,1nσ= _1… _n∈\0,1\^n is first transformed into a sequence (x1,…,xn)(x_1,…,x_n) of input vectors in the first n tokens. Then (x1,…,xn)(x_1,…,x_n), by definition of causal complexity, can be transformed in L fingerprints of dimension p=no(1)p=n^o(1): σ↦fn+1(σ)∈ℝO(p)σ f_n+1(σ) ^O(p) such that the outputs of all L layers in the last position, including the last output yn+1Ly_n+1^L, can be computed from fn+1(σ)f_n+1(σ) and xn+1(i)x_n+1(i) in arithmetic complexity no(1)n^o(1). Then from yn+1Ly_n+1^L one can compute the answer σi _i to the indexing task through multiplying yn+1Ly_n+1^L by a 2×d2× d matrix, and computing the maximal coordinate of the resulting vector. The last part requires O(d)=no(1)O(d)=n^o(1) arithmetic complexity (recall that causal complexity upper bounds d). One can perform these computations for arbitrary real vectors fn+1∈ℝO(p)f_n+1 ^O(p) and xn+1∈ℝdx_n+1 ^d, not just from those that come as inputs to the indexing problem. That is, when we omit inputs in fn+1(σ),xn+1(i)f_n+1(σ),x_n+1(i), we no longer consider these vectors as functions of σ and i but allow them to take arbitrary values. This gives a concept class C(xn+1,fn+1)C(x_n+1,f_n+1), which, on the one hand, has arithmetic complexity, and thus VC dimension by Theorem 3, at most no(1)n^o(1), but on the other hand, has VC dimension at least n since for inputs xn+1(1),…,xn+1(n)x_n+1(1),…,x_n+1(n) we have: C(xn+1(i),fn+1(σ))=σi,i=1,…,n,C(x_n+1(i),f_n+1(σ))= _i, i=1,…,n, for every σ∈0,1nσ∈\0,1\^n. b) Using a positional encoding that assigns 0 to every position except the last one, to which it assigns a sufficiently large value, we can make the last token receive attention weight 100n2100n^2, while all other tokens receive weight 11. Since there is no masking, every token can then recover the index i from the last token up to a small additive error, say 0.010.01. Next, we can devise an output MLP of the first layer that produces 0 at positions k≠ik≠ i, while at position i it outputs a large marker together with the local bit σi _i. Indeed, one can do it by computing the absolute value |k−i′||k-i | – if it is less than 0.010.01, then k=ik=i, and if it is greater than 0.990.99, then k≠ik≠ i. Thus, the first-layer output at position i contains a large marker together with σi _i, while all other positions output 0. Repeating the same attention mechanism in the second layer gives this value to every token, including the last one. c) Imagine that the positional encoding of the k-th position contains (cosksink) pmatrix k\\ k pmatrix while the index i is embedded as (cosisini) pmatrix i\\ i pmatrix. Then we can make sure that the attention from the index position to the k-th position is of the form ⟨(cosksink),(cosisini)⟩ pmatrix k\\ k pmatrix, pmatrix i\\ i pmatrix and thus is strictly maximized at k=ik=i. Through multiplying these products by a sufficiently large constant, the softmax function will get us, up to a small error, the content of the i-th position that allows us to restore the i-th bit. ∎ We now observe that item a) of Theorem 12 applies to RNNs, SSMs and causal linear-attention layers with reasonable assumptions on their size. Proposition 13. no(1)n^o(1)-size SSM, RNN, and causal linear-attention layers have causal complexity no(1)n^o(1). Proof. Let (x1,…,xn)∈(ℝd)n(x_1,…,x_n)∈(R^d)^n be an input. For SSMs and RNNs, the fingerprint of x1,…,xk−1x_1,…,x_k-1 would be the vector hk−1h_k-1 from (4) and (6), respectively. Given this vector and xkx_k, one computes yky_k according to formulas (4–5) and (6–7). This can be performed in arithmetic complexity no(1)n^o(1). Here one uses the fact that the dimension, the number of learnable parameters of the MLPs in the equations, and the arithmetic complexity of A,B,ϕA,B,φ in case of SSMs, are bounded by no(1)n^o(1) due to the corresponding bound on the size of a layer. For causal linear-attention layer, the fingerprint of x1,…,xk−1x_1,…,x_k-1 consists of one d×d× d matrix, and one d-dimensional row, computed by: ∑ℓ=1k−1vℓϕ(kℓ)T,∑ℓ=1k−1ϕ(kℓ)T.Σ _ =1^k-1v_ φ(k_ )^T, Σ _ =1^k-1φ(k_ )^T. The output yky_k is then computed via formulas in (2–3). Complementing the computation, given two sums above, requires now just dO(1)=no(1)d^O(1)=n^o(1) arithmetic operations that come from matrix products, and also computation of ϕφ whose arithmetic complexity is bounded by no(1)n^o(1) due to the bound on the size of the layer. ∎ 4 Left-hand Indexing: RNNs prevail Theorem 14. a) One O(1)O(1)-size RNN layer can solve the left-hand indexing task. b) No 1-layer no(1)n^o(1)-size SSM, linear-attention or softmax transformer can solve the left-hand indexing task. c) Each of the following – 2 O(1)O(1)-size SSM layers, 2 O(1)O(1)-size linear-attention layers, 2 O(1)O(1)-size softmax transformer layers – can solve the left-hand indexing task. This holds regardless of whether the transformer layers are full or causal. Proof. a) The RNN stores i and one answer coordinate. At bit position k, the update MLP computes a binary marker for i=ki=k and writes σk _k to the answer coordinate only at that position. Since exactly one position is selected, the final state contains σi _i. b) We start with the lower bound for transformers (the same proof works both for linear-attention and softmax). Let the input to the indexing task be i,(σ1,…,σn)i,( _1,…, _n). There are n+2n+2 tokens, the first token with i, next n tokens with input bits, and the last end-token. Note that for both models, the computation of the attention in the last token (see (1) and (2)) can be decomposed into two parts, one determined by i and the other by the string σ=σ1…σnσ= _1… _n, more precisely: an+2=α(i)+β(σ)γ(i)+ρ(σ),a_n+2= α(i)+β(σ)γ(i)+ρ(σ), (8) where α(i),β(σ)∈ℝdα(i),β(σ) ^d, γ(i),ρ(σ)∈(0,+∞)γ(i),ρ(σ)∈(0,+∞). Consider a concept class C that treats coordinates of (α(i),γ(i))(α(i),γ(i)) as d+1d+1 input coordinates and (β(σ),ρ(σ))(β(σ),ρ(σ)) as d+1d+1 parameters, computes an+2a_n+2 as in (8), and then performs the rest of the computations in the last token, getting the output of the indexing task. More specifically, it sums up an+2a_n+2 with the vector xn+2x_n+2 – embedding of the last token, applies the output MLP N to the sum, multiplies the resulting vector by the output-distribution matrix A, and computes which output class has the largest score. On the one hand, if the size of the layer is no(1)n^o(1), then d=no(1)d=n^o(1), the number of learnable parameters in N is no(1)n^o(1), and hence the number of parameters and arithmetic complexity of C is no(1)n^o(1), together with its VC dimension by Theorem 3. On the other hand, if for contradiction such a layer solves the indexing task, then C((α(i),γ(i)),(β(σ),ρ(σ)))=σi,C ((α(i),γ(i)),(β(σ),ρ(σ)) )= _i, meaning that the VC dimension of C is at least n as, choosing distinct σ∈0,1nσ∈\0,1\^n, we can realize any Boolean function on n inputs: (α(1),γ(1)),…,(α(n),γ(n)).(α(1),γ(1)),…,(α(n),γ(n)). The structure of the argument against no(1)n^o(1)-size SSM layer, computing the left-hand indexing, is similar. Assuming for contradiction that such a layer exists, we construct a concept class C(α,β)C(α,β) with no(1)n^o(1) number of parameters and no(1)n^o(1) arithmetic complexity, satisfying: C(α(i),β(σ))=σiC(α(i),β(σ))= _i for some functions α(i),β(σ)α(i),β(σ), obtaining a contradiction since its VC dimension has to be at least n. More specifically, we let α(i)=h1α(i)=h_1 be the state after processing the first token (one with the index) in (4–5). The further evolution of the state h1h_1 happens through a composition of n+1n+1 affine functions ℝd→ℝdR^d ^d, determined by σ1,…,σn _1,…, _n. This whole composition can be given by a d×d× d matrix A(σ)A(σ) and a d-vector b(σ)b(σ). Overall, we get the following formula for the state after processing the whole input hn+2=A(σ)α(i)+b(σ).h_n+2=A(σ)α(i)+b(σ). Coordinates of β(σ)=(A(σ),b(σ))β(σ)=(A(σ),b(σ)) will be viewed as parameters, and there are d2+d=no(1)d^2+d=n^o(1) of them. Computing hn+2h_n+2 takes poly(d)=no(1)poly(d)=n^o(1) standard arithmetic operations. The output of the SSM layer is then computed by applying the output MLP ϕφ to hn+2h_n+2 and the embedding of the last token xn+2x_n+2, multiplying by the output-distribution matrix, and taking the highest-scoring output class. Again, this all takes arithmetic complexity no(1)n^o(1) if the size of the layer is no(1)n^o(1). Finally, we have C(α(i),β(σ))=σiC(α(i),β(σ))= _i since the layer is supposed to solve the indexing task. c) Transformers – both linear-attention and softmax, causal and full – essentially can mimic the solution from item b) of Theorem 12. By putting a lot of weight to the first position in the positional encoding, all subsequent tokens can obtain the value of the index i (up to a small additive error, say, 0.010.01). Since the index is in the beginning, the masking does not prevent us from doing it. Then again, the output MLP of the first layer can use this to output a large number at the i-th position, and 0 at all other positions. Finally, the second layer can now focus its attention on the i-th position, retrieving the value of the i-th bit. Since the output is computed at the last token, masking would not be a problem. A 2-layer SSM is capable of imitating this solution as well. Note that due to its linear update rule, it can in particular simply sum up the input vectors. By putting the index i to a designated coordinate for the first token, and 0 for other tokens, and summing up values in this coordinate, we get i to every position after the first layer. Then the output MLP can transform it into the value of the i-th bit at the i-th position and 0 at the rest of the positions. Summing up these MLP outputs at the second layer gives us the i-th bit. ∎ 5 Experiments The preceding sections establish asymptotic separations for indexing. We now test whether the same picture appears in finite models trained from scratch. We call configurations supported by our positive constructions constructive (✓), and configurations on the asymptotically hard side of our results stress tests (✗). Stress-test configurations may still succeed at small finite lengths, but their performance is expected to deteriorate as n grows. These experiments do not replace the lower bounds: training failure is not evidence of impossibility. The appendix provides full hyperparameters, ablations, parameter counts, runtimes, and length-shifted evaluations. The code for our experiments can be found at https://github.com/visho33/IndexRetrieval. https://github.com/visho33/IndexRetrieval. 5.1 Experimental Setup We train models on binary indexing for n∈8,16,32,64n∈\8,16,32,64\, using five random seeds per configuration and online-generated examples. We use the query-token readout for RHI and the end-token readout for LHI. We compare full and causal variants of softmax and linear attention, together with GRUs and Mamba2. All models have width 16. Attention models use two heads and feedforward width 64, and linear attention uses the ELU+1 feature map. By Remark 7, equivalent one-layer full/causal pairs are reported once. Further implementation details are provided in the supplement. Following an ablation over learned, sinusoidal, rotary, polynomial, and no positional encoding, we use polynomial positional encodings throughout the main sweep. Bit tokens encode their type and value, whereas query tokens additionally contain the features ((i−1)/n)((i-1)/n) and ((i−1)/n)2((i-1)/n)^2. Models are trained with AdamW, learning rate 10−310^-3, batch size 256, and at most 500 epochs, using 50,000 newly generated examples per epoch. A run is considered successful if its maximum held-out accuracy during training reaches 1.01.0. 5.2 Results Table 2 reports the number of successful seeds for each of the 23 distinct configurations. Constructive configurations succeed in 158/160158/160 runs overall: all 40/4040/40 runs succeed for n≤32n≤ 32, and 38/4038/40 succeed at n=64n=64. The only failures are one seed of two-layer full softmax attention and one seed of two-layer Mamba, both on LHI. Stress-test configurations display the opposite trend. Their success count decreases from 70/7570/75 at n=8n=8, to 51/7551/75 at n=16n=16, 13/7513/75 at n=32n=32, and 0/750/75 at n=64n=64. Thus, the empirical separation between the two theory-guided groups becomes increasingly sharp as the sequence length grows. For right-hand indexing, all stress-test families succeed at n=8n=8, while additional depth allows some causal linear-attention and Mamba models to remain successful at n=32n=32. Nevertheless, every causal linear-attention, GRU, and Mamba configuration fails the criterion at n=64n=64, for all tested depths. One-layer full and causal linear attention also transition from 5/55/5 successes at n≤16n≤ 16 to 0/50/5 at n≥32n≥ 32. For left-hand indexing, the breakdown occurs earlier. One-layer softmax attention fails at every tested length, whereas one-layer linear attention and Mamba succeed at n=8n=8 but fail for every seed once n≥16n≥ 16. In contrast, the constructive one-layer GRU and two-layer models succeed almost uniformly. Overall, the experiments qualitatively align with the theoretical separations while exhibiting substantial finite-size effects. Success at small n does not contradict an asymptotic lower bound, and failure under our fixed optimization protocol is not evidence of impossibility. Several unsuccessful runs at n=64n=64 also remain above chance, as detailed in the supplementary material. Task Model family L Thm. Bit string length n 8 16 32 64 RHI Softmax 1 ✓ RHI Linear 1 ✗ RHI Full linear 2 ✓ RHI Causal linear 2 ✗ RHI Causal linear 3 ✗ RHI Causal linear 4 ✗ RHI GRU 1 ✗ RHI GRU 2 ✗ RHI GRU 3 ✗ RHI GRU 4 ✗ RHI Mamba 1 ✗ RHI Mamba 2 ✗ RHI Mamba 3 ✗ RHI Mamba 4 ✗ LHI GRU 1 ✓ LHI Mamba 1 ✗ LHI Mamba 2 ✓ LHI Softmax 1 ✗ LHI Full softmax 2 ✓ LHI Causal softmax 2 ✓ LHI Linear 1 ✗ LHI Full linear 2 ✓ LHI Causal linear 2 ✓ Total successful runs ✓ 40 40 40 38 ✗ 70 51 13 0 Table 2: Successful seeds out of five by task, model, depth L, and bit-string length n. For L=1L=1, Softmax and Linear merge the equivalent full and causal variants. ✓ and ✗ denote constructive and stress-test configurations. The final rows aggregate 40 constructive and 75 stress-test runs per length. 6 Conclusion We used indexing to isolate how token order and information bottlenecks affect sequence models. Causal complexity yields precision-independent lower bounds for constant-depth RNNs, SSMs, and causal linear-attention transformers on right-hand indexing, whereas left-hand indexing gives a one-layer advantage to RNNs. Our experiments are consistent with these theoretical separations and show that their signatures are already visible at moderate input lengths. They also reveal substantial finite-size effects: success at small n does not contradict an asymptotic lower bound, and training failure is not evidence of impossibility. More broadly, our results show that even a minimal retrieval primitive can expose fundamental differences in how sequence architectures route and preserve information. Extending causal complexity to richer primitives and more general architectural components is a direction for future work. References Anthony and Bartlett, (2009) Anthony, M. and Bartlett, P. L. (2009). Neural network learning: Theoretical foundations. cambridge university press. Ba et al., (2016) Ba, J. L., Kiros, J. R., and Hinton, G. E. (2016). Layer normalization. arXiv preprint arXiv:1607.06450. Barcelo et al., (2025) Barcelo, P., Kozachinskiy, A., and Steifer, T. (2025). Ehrenfeucht-haussler rank and chain of thought. In Forty-second International Conference on Machine Learning. Chen et al., (2025) Chen, L., Peng, B., and Wu, H. (2025). Theoretical limitations of multi-layer transformer. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2631–2653. IEEE. Chiang et al., (2023) Chiang, D., Cholak, P., and Pillay, A. (2023). Tighter bounds on the expressivity of transformer encoders. In International Conference on Machine Learning, pages 5544–5562. PMLR. Elhage et al., (2021) Elhage, N., Nanda, N., Olsson, C., Henighan, T., Joseph, N., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., et al. (2021). A mathematical framework for transformer circuits. Transformer Circuits Thread, 1(1):12. Gu and Dao, (2023) Gu, A. and Dao, T. (2023). Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752. Guan et al., (2024) Guan, X., Liu, Y., Lin, H., Lu, Y., He, B., Han, X., and Sun, L. (2024). Mitigating large language model hallucinations via autonomous knowledge graph-based retrofitting. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 18126–18134. Hahn, (2020) Hahn, M. (2020). Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171. Jiang et al., (2025) Jiang, H., Hahn, M., Zetzsche, G., and Lin, A. W. (2025). Softmax transformers are turing-complete. arXiv preprint arXiv:2511.20038. Karpinski and Macintyre, (1997) Karpinski, M. and Macintyre, A. (1997). Polynomial bounds for vc dimension of sigmoidal and general pfaffian neural networks. Journal of Computer and System Sciences, 54(1):169–176. Katharopoulos et al., (2020) Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F. (2020). Transformers are rnns: Fast autoregressive transformers with linear attention. In International conference on machine learning, pages 5156–5165. PMLR. Kozachinskiy et al., (2025) Kozachinskiy, A., Urrutia, F., Orellana, H., Steifer, T., Pizarro, G., Fuentes, M., Meza Vaásquez, F., Buc Calderon, C., and Rojas, C. (2025). Strassen attention, split vc dimension and compositionality in transformers. Advances in Neural Information Processing Systems, 38:9665–9696. Merrill et al., (2026) Merrill, W., Li, Y., Romero, T., Svete, A., Costello, C., Dasigi, P., Groeneveld, D., Heineman, D., Kuehl, B., Lambert, N., et al. (2026). Olmo hybrid: From theory to practice and back. arXiv preprint arXiv:2604.03444. Merrill et al., (2024) Merrill, W., Petty, J., and Sabharwal, A. (2024). The illusion of state in state-space models. arXiv preprint arXiv:2404.08819. Merrill and Sabharwal, (2024) Merrill, W. and Sabharwal, A. (2024). The expressive power of transformers with chain of thought. In International Conference on Learning Representations, volume 2024, pages 7690–7706. Minsky, (1967) Minsky, M. (1967). Computation: Finite and Infinite Machines. Prentice-Hall. Olsson et al., (2022) Olsson, C., Elhage, N., Nanda, N., Joseph, N., DasSarma, N., Henighan, T., Mann, B., Askell, A., Bai, Y., Chen, A., et al. (2022). In-context learning and induction heads. arXiv preprint arXiv:2209.11895. Peng et al., (2024) Peng, B., Narayanan, S., and Papadimitriou, C. (2024). On limitations of the transformer architecture. In First conference on language modeling. Pérez et al., (2021) Pérez, J., Barceló, P., and Marinkovic, J. (2021). Attention is turing-complete. Journal of Machine Learning Research, 22(75):1–35. Ramachandran et al., (2018) Ramachandran, P., Zoph, B., and Le, Q. V. (2018). Searching for activation functions. In International Conference on Learning Representations. Sälzer et al., (2025) Sälzer, M., Köcher, C., Kozachinskiy, A., Zetzsche, G., and Lin, A. W. (2025). The counting power of transformers. arXiv preprint arXiv:2505.11199. Sanford et al., (2024) Sanford, C., Hsu, D., and Telgarsky, M. (2024). One-layer transformers fail to solve the induction heads task. arXiv preprint arXiv:2408.14332. Sarrof et al., (2024) Sarrof, Y., Veitsman, Y., and Hahn, M. (2024). The expressive capacity of state space models: A formal language perspective. Advances in Neural Information Processing Systems, 37:41202–41241. Shakerinava et al., (2026) Shakerinava, M., Khavari, B., Ravanbakhsh, S., and Chandar, S. (2026). The expressive limits of diagonal ssms for state-tracking. arXiv preprint arXiv:2603.01959. Siegelmann and Sontag, (1994) Siegelmann, H. T. and Sontag, E. D. (1994). Analog computation via neural networks. Theoretical Computer Science, 131(2):331–360. Strobl et al., (2025) Strobl, L., Angluin, D., and Frank, R. (2025). Concise one-layer transformers can do function evaluation (sometimes). arXiv preprint arXiv:2503.22076. Strobl et al., (2024) Strobl, L., Merrill, W., Weiss, G., Chiang, D., and Angluin, D. (2024). What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics, 12:543–561. Yang et al., (2024) Yang, A., Chiang, D., and Angluin, D. (2024). Masked hard-attention transformers recognize exactly the star-free languages. Advances in Neural Information Processing Systems, 37:10202–10235. Appendix A Further Experimental Details This supplement provides the experimental details omitted from the main paper: the full training and evaluation protocol, the positional-encoding ablation used to choose the final setup, complete held-out results for each model family, parameter counts, runtimes, and out-of-distribution evaluations. The main paper reports 23 distinct configuration classes. For one-layer attention models, the full and causal variants are theoretically equivalent at the final readout token, so they are merged there. In this supplement, we sometimes report them separately because both variants were trained independently. Whenever this affects a total, we state whether we are counting merged configuration classes or individual trained variants. All experiments use the binary indexing task defined in the main paper. Each run is evaluated once per epoch on a fixed held-out set of 2,000 examples. Training examples are generated online, with 50,000 examples per epoch. Training stops when the held-out binary cross-entropy reaches at most 10−610^-6 or after 500 epochs. A run is considered successful if its maximum held-out accuracy during training reaches 1.01.0. Since indexing has a deterministic correct answer, requiring perfect held-out accuracy gives a simple and strict empirical criterion. However, success on this finite held-out set does not prove that the trained model solves every possible input. A.1 Protocol Details Table 3 lists the final training and evaluation settings used in the main sweep. The positional-encoding alternatives considered during development are described separately in the next section. For each example, the index i is sampled uniformly from 1,…,n\1,…,n\, and the input bits are sampled independently and uniformly from 0,1\0,1\. The target is σi _i. Training examples are generated online, while the held-out set is generated once and kept fixed throughout each run. For a run with seed s, we initialize Python, NumPy, PyTorch, and the CUDA random-number generators with s. The held-out set uses seed s+10,000s+10,000, while the length-shifted sets at n/2n/2 and 2n2n use seeds s+20,000s+20,000 and s+30,000s+30,000, respectively. Softmax attention is implemented using Hugging Face BERT blocks (except rotary, which uses RoFormer). We explicitly set the model width, number of layers, number of attention heads, feed-forward width, causal or full attention mask, and zero dropout. Other internal choices follow the defaults of the installed Transformers version. GRUs use PyTorch’s n.GRU with input and hidden size 16, one direction, and zero dropout. Biases and the initial hidden state follow the PyTorch defaults. Mamba2 uses state dimension 16, head dimension 8, expansion factor 1, and convolution width 3. Caching, fused normalization, and fused cross-entropy paths are disabled. Other unspecified Mamba2 options follow the defaults of the installed flash-linear-attention version. We refer to this model family as Mamba in the result tables. Linear attention is implemented locally using pre-normalized blocks, bias-free query, key, value, and output projections, the ELU(x)+1ELU(x)+1 feature map, denominator epsilon 10−610^-6, and zero dropout. Full linear attention uses global key–value sums, whereas causal linear attention uses prefix sums. Other unspecified options follow the PyTorch defaults. Setting Value Task sizes n∈8,16,32,64n∈\8,16,32,64\ Seeds 0,1,2,3,4\0,1,2,3,4\ Training examples 50000 per epoch, drawn on demand Held-out examples 2000 fixed samples Evaluation frequency Once per epoch OOD test sizes n/2n/2 and 2n2n Success criterion Maximum held-out accuracy 1.01.0 Readout convention RHI: query token, LHI: end token Input query features (i−1)/n(i-1)/n and ((i−1)/n)2((i-1)/n)^2 Architectures Full and causal softmax attention Full and causal linear attention GRU Mamba2 Model width 16 Attention heads 2 Feed-forward width 64 Linear-attention feature map ELU(x)+1ELU(x)+1 Dropout 0 Positional encoding Polynomial Loss Binary cross-entropy with logits Optimizer AdamW Learning rate 10−310^-3 AdamW ϵε 10−810^-8 AdamW betas PyTorch default (0.9,0.999)(0.9,0.999) Weight decay 0 Batch size 256 Gradient clipping Global norm 5 Early stopping Held-out binary cross-entropy loss ≤10−6≤ 10^-6 Scheduler ReduceLROnPlateau Scheduler metric Training binary cross-entropy Scheduler factor 0.5 Scheduler patience 30 epochs Min. learning rate 10−510^-5 Mixed precision No Prediction rule sigmoid(logit)≥0.5sigmoid(logit)≥ 0.5 Max. epochs 500 Table 3: Final training and evaluation settings used in the main sweep. Experiments were run on a Slurm-managed x86_64 Linux server with kernel 6.8.0-124-generic, two AMD EPYC 9654 96-core processors, 1.5 TiB of system memory, and NVIDIA H100 GPUs with 80 GB of HBM3 memory, using driver 610.43.02. The sweep launcher requested one GPU per run. The software environment used Python 3.12.3, PyTorch 2.12.1 with CUDA 13.0, Transformers 5.12.1, flash-linear-attention 0.5.1, Triton 3.7.1, and NumPy 2.5.0. A.2 Positional-Encoding Ablation Before running the main sweep, we compared learned, sinusoidal, rotary, polynomial, and no positional encoding. This ablation uses d=16d=16, two attention heads, n∈32,64n∈\32,64\, seeds 0,1,2\0,1,2\, and the same training protocol as the main sweep. The ablation covers nine architecture–depth configurations (rotary is evaluated only for the four softmax-attention configurations): 1. RHI full and causal softmax attention with one layer 2. RHI full linear attention with two layers 3. LHI full and causal softmax and linear attention with two layers 4. a one-layer LHI GRU 5. two-layer LHI Mamba2 For polynomial positional encoding, each token position t∈0,…,L−1t∈\0,…,L-1\ is represented by (p,p2)(p,p^2), where p=t/(L−1)p=t/(L-1) and L is the training sequence length. This two-dimensional representation is projected to the model dimension using a learned bias-free linear layer. The main paper reports only the conclusion of this ablation. Table 4 presents the results by sequence length. Polynomial encoding is the only option that reaches perfect held-out accuracy in every run at n=32n=32 and in all but one run at n=64n=64. Based on these results, we use polynomial positional encoding throughout the main sweep. Encoding n Runs Successes Mean max. accuracy None 32 27 12 0.7628 None 64 27 12 0.7578 Learned 32 27 17 0.9751 Learned 64 27 8 0.8708 Sinusoidal 32 27 23 0.9969 Sinusoidal 64 27 18 0.9432 Rotary 32 12 12 1.0000 Rotary 64 12 6 0.9497 Polynomial 32 27 27 1.0000 Polynomial 64 27 26 0.9849 Table 4: Positional-encoding ablation. Rotary is included only for softmax attention. The only polynomial run that does not reach perfect held-out accuracy is L64_softmaxL2d16h2_poly_s0, with maximum held-out accuracy 0.59100.5910 after 500 epochs. All other polynomial runs in this ablation reach held-out accuracy 1.01.0. A.3 Complete Main-Sweep Accuracy Table 5 complements the success counts reported in the main paper by showing the maximum held-out accuracy reached during training. Each entry reports the mean ± standard deviation across five seeds. This makes it possible to distinguish configurations that came close to the perfect-accuracy criterion of 1.01.0 from those that remained substantially below perfect accuracy. As in the previous sections, one-layer full and causal attention models are listed separately because both variants were trained independently. Where Model family Depth Theory n=8n=8 n=16n=16 n=32n=32 n=64n=64 RHI Full softmax 1 Constructive 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 RHI Causal softmax 1 Constructive 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 RHI Full linear 1 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.78±0.010.78± 0.01 0.64±0.010.64± 0.01 RHI Full linear 2 Constructive 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 RHI Causal linear 1 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.78±0.010.78± 0.01 0.65±0.010.65± 0.01 RHI Causal linear 2 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.99±0.020.99± 0.02 0.77±0.010.77± 0.01 RHI Causal linear 3 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.99±0.010.99± 0.01 0.82±0.020.82± 0.02 RHI Causal linear 4 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.85±0.040.85± 0.04 RHI GRU 1 Stress test 1.00±0.001.00± 0.00 0.95±0.020.95± 0.02 0.77±0.020.77± 0.02 0.66±0.010.66± 0.01 RHI GRU 2 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.86±0.010.86± 0.01 0.69±0.010.69± 0.01 RHI GRU 3 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.86±0.020.86± 0.02 0.72±0.010.72± 0.01 RHI GRU 4 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.94±0.020.94± 0.02 0.74±0.010.74± 0.01 RHI Mamba 1 Stress test 1.00±0.001.00± 0.00 0.99±0.010.99± 0.01 0.77±0.070.77± 0.07 0.66±0.020.66± 0.02 RHI Mamba 2 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.91±0.040.91± 0.04 0.69±0.040.69± 0.04 RHI Mamba 3 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.97±0.030.97± 0.03 0.79±0.020.79± 0.02 RHI Mamba 4 Stress test 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.99±0.020.99± 0.02 0.80±0.040.80± 0.04 LHI GRU 1 Constructive 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 LHI Mamba 1 Stress test 1.00±0.001.00± 0.00 0.82±0.060.82± 0.06 0.65±0.040.65± 0.04 0.59±0.010.59± 0.01 LHI Mamba 2 Constructive 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.91±0.200.91± 0.20 LHI Full softmax 1 Stress test 0.76±0.150.76± 0.15 0.64±0.060.64± 0.06 0.58±0.010.58± 0.01 0.56±0.020.56± 0.02 LHI Full softmax 2 Constructive 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 0.92±0.180.92± 0.18 LHI Causal softmax 1 Stress test 0.76±0.150.76± 0.15 0.64±0.060.64± 0.06 0.58±0.010.58± 0.01 0.56±0.020.56± 0.02 LHI Causal softmax 2 Constructive 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 LHI Full linear 1 Stress test 1.00±0.001.00± 0.00 0.78±0.150.78± 0.15 0.64±0.060.64± 0.06 0.58±0.020.58± 0.02 LHI Full linear 2 Constructive 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 LHI Causal linear 1 Stress test 1.00±0.001.00± 0.00 0.77±0.140.77± 0.14 0.64±0.060.64± 0.06 0.58±0.020.58± 0.02 LHI Causal linear 2 Constructive 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 1.00±0.001.00± 0.00 Table 5: Mean and standard deviation, across five seeds, of the maximum held-out accuracy reached during training for each architecture–depth configuration. Constructive and Stress test denote the theory-guided groups defined in the main paper. A.4 Runtime and Model Scale at n=64n=64 Table 6 reports parameter counts, training length, and wall-clock runtime for the constructive families at n=64n=64. Successes are reported across five seeds. The number of parameters is fixed for each configuration, while the number of epochs and runtime measurements are reported as medians across the five runs. Training time is measured for the final training epoch, and evaluation time corresponds to one pass over the fixed held-out set of 2,000 examples using the same batch size as training. These measurements document the computational scale of the experiments under the hardware and software setup described above. Where Model L Succ. Params Med. epochs Train s/epoch Eval s/pass RHI Full softmax 1 5/5 3473 185 2.21 0.065 RHI Causal softmax 1 5/5 3473 185 2.24 0.065 RHI Full linear 2 5/5 6577 73 2.55 0.068 LHI GRU 1 5/5 1777 325 2.04 0.062 LHI Mamba 2 4/5 3261 113 9.01 0.184 LHI Full softmax 2 4/5 6753 261 2.57 0.069 LHI Causal softmax 2 5/5 6753 112 2.45 0.069 LHI Full linear 2 5/5 6577 50 3.24 0.085 LHI Causal linear 2 5/5 6577 33 2.60 0.069 Table 6: Parameter counts, training length, and runtime at n=64n=64 for the constructive families. Epoch and runtime columns report medians across five seeds. A.5 Length-Shifted Evaluation This section reports length-shifted evaluations for the constructive families. For each run, the model is evaluated on inputs with n/2n/2 and 2n2n bits using the same parameters, tokenization, and readout convention, without retraining. These evaluations do not affect whether a run is counted as successful in-distribution. At the task level, a shorter instance can always be embedded into a longer one by appending additional bits that are never queried. Thus, there is no fundamental obstacle to using the same indexing rule across different lengths. However, our models are trained at a single length, and the polynomial positional encoding uses the training sequence length as its reference scale. The learned solution may therefore rely on the positions seen during training rather than implement a length-independent indexing rule. Strong length generalization was therefore not expected, but we included this evaluation as a simple probe of whether it emerged nevertheless. As in the complete main-sweep table, one-layer full and causal attention variants are counted separately here because they were trained independently. This gives 45 possible constructive-family runs at each training length. The tables report the length-shifted accuracy from the final training epoch and include only runs whose maximum in-distribution held-out accuracy reached 1.01.0. Table 7 aggregates these results by training length, while Table 8 reports them separately for each model family at n=64n=64. Transfer across lengths is weak overall. Accuracy at n/2n/2 is above chance for models trained at the smallest length but approaches 0.50.5 as the training length increases. Accuracy at 2n2n remains near chance throughout. At training length n=64n=64, both length-shifted evaluations are close to chance for every listed family. Train n ID succ. Acc. at n/2n/2 Acc. at 2n2n 8 45 0.629±0.0910.629± 0.091 0.535±0.0260.535± 0.026 16 45 0.554±0.0420.554± 0.042 0.520±0.0180.520± 0.018 32 45 0.527±0.0230.527± 0.023 0.510±0.0110.510± 0.011 64 43 0.514±0.0140.514± 0.014 0.500±0.0070.500± 0.007 Table 7: Length-shifted accuracy for the constructive families, aggregated by training length. Results are reported as mean ± standard deviation across runs that succeeded in-distribution. Where Model L ID succ. Acc. at n/2n/2 Acc. at 2n2n RHI Full softmax 1 5/5 0.525±0.0080.525± 0.008 0.501±0.0070.501± 0.007 RHI Causal softmax 1 5/5 0.525±0.0080.525± 0.008 0.501±0.0070.501± 0.007 RHI Full linear 2 5/5 0.502±0.0050.502± 0.005 0.500±0.0080.500± 0.008 LHI GRU 1 5/5 0.510±0.0110.510± 0.011 0.497±0.0060.497± 0.006 LHI Mamba 2 4/5 0.513±0.0240.513± 0.024 0.499±0.0100.499± 0.010 LHI Full softmax 2 4/5 0.523±0.0050.523± 0.005 0.504±0.0030.504± 0.003 LHI Causal softmax 2 5/5 0.517±0.0100.517± 0.010 0.497±0.0070.497± 0.007 LHI Full linear 2 5/5 0.497±0.0120.497± 0.012 0.503±0.0110.503± 0.011 LHI Causal linear 2 5/5 0.513±0.0070.513± 0.007 0.499±0.0090.499± 0.009 Table 8: Length-shifted accuracy for the constructive families trained at n=64n=64. Results are reported as mean ± standard deviation across runs that succeeded in-distribution.