Literature
Display
← All papers

Learning Linear Attention in Polynomial Time

Morris Yau · Ekin Akyürek · Jiayuan Mao · Joshua B. Tenenbaum · Stefanie Jegelka · Jacob Andreas

· NeurIPS 2025 ↗

Learning theory23 min text · CondensedOriginal paper ↗
Contents

At a glance

A single layer of multi-head linear attention, without softmax, is a cubic polynomial in its input. The paper learns it by linear regression in a lifted feature space, then factorizes the fitted matrix into at most d² attention heads. This removes a rank constraint by allowing more heads; it does not solve the optimization problem for an arbitrarily fixed small number of heads.

A positive-definite second-moment matrix of reduced input features certifies that empirical minimizers represent the same function, under the stated realizability or width conditions. The paper applies this to bounded-history Turing-machine simulation and tests synthetic attention, associative memory, and finite-automaton execution. The polynomial-time construction is distinct from the stochastic-gradient optimizers used in most experiments.

1 Introduction

Expressing a computation with a Transformer does not show that its parameters can be learned efficiently from examples. This paper separates three questions: finding an empirical optimum, generalizing on a data distribution, and identifying the actual function strongly enough to generalize outside that distribution.

The algebraic observation is that products of value and key-query parameters can be collected into a d²-by-d² matrix. Relaxing its rank constraint gives ordinary least squares; singular-value decomposition converts the result back into an attention model. The method concerns one unnormalized linear-attention layer, even though related architectures motivate the introduction.

The identifiability certificate asks whether the training inputs span an appropriate cubic-feature space. It is sufficient, not necessary. A zero training loss alone is weaker: different parameter sets may fit the data while computing different functions on new inputs. The certificate compares functions through their polynomial coefficients, avoiding irrelevant parameter rescalings.

Equation
ΛD=𝔼(Z,y)∈D​[𝒳⁡(Z)​𝒳​(Z)⊤].\Lambda_{D}\;=\;\mathbb{E}_{(Z,y)\in D}\!\bigl[\mathcal{X}(Z)\,\mathcal{X}(Z)^{\!\top}\bigr].
Algorithm 1 MHLA Learning via Regression
1:  Input: Data D:={(Zi,yi)}i∈[N]D\vcentcolon=\{(Z_{i},y_{i})\}_{i\in[N]} for Zi∈ℝd×niZ_{i}\in\mathbb{R}^{d\times n_{i}} and y∈ℝdy\in\mathbb{R}^{d}
2:   {𝒳i}i∈[N]:=ExtractFeature​(D)\{\mathcal{X}_{i}\}_{i\in[N]}\vcentcolon=\text{ExtractFeature}(D), generates
Equation 1
𝒳i:=[⟨z1:,z1:⟩z1​ni⟨z1:,z2:⟩z1​ni⋯⟨z1:,zd:⟩zd​ni⟨z2:,z1:⟩z1​ni⟨z2:,z2:⟩z1​ni⋯⟨z2:,zd:⟩zd​ni⋱⟨zd:,z1:⟩z1​ni⟨zd:,z2:⟩z1​ni⋯⟨zd:,zd:⟩zd​ni].\mathcal{X}_{i}\vcentcolon=\begin{bmatrix}\langle z_{1:},z_{1:}\rangle z_{1n_{i}}&\langle z_{1:},z_{2:}\rangle z_{1n_{i}}&\cdots&\langle z_{1:},z_{d:}\rangle z_{dn_{i}}\\ \langle z_{2:},z_{1:}\rangle z_{1n_{i}}&\langle z_{2:},z_{2:}\rangle z_{1n_{i}}&\cdots&\langle z_{2:},z_{d:}\rangle z_{dn_{i}}\\ \vdots&\vdots&\ddots&\vdots\\ \langle z_{d:},z_{1:}\rangle z_{1n_{i}}&\langle z_{d:},z_{2:}\rangle z_{1n_{i}}&\cdots&\langle z_{d:},z_{d:}\rangle z_{dn_{i}}\\ \end{bmatrix}~. (1)
3:  Create dataset {Xi,a}i∈[N],a∈[d]\{X_{i,a}\}_{i\in[N],a\in[d]}. Let Xi,a∈ℝd2×d2X_{i,a}\in\mathbb{R}^{d^{2}\times d^{2}} be a matrix that is comprised of 𝒳i\mathcal{X}_{i} in the a′​t​ha^{\prime}th block of dd rows and 00 everywhere else:
4:  
Equation 2
Xi,a=[0…𝒳iT…0]TX_{i,a}=\begin{bmatrix}0&\ldots&\mathcal{X}_{i}^{T}&\ldots&0\end{bmatrix}^{T} (2)
5:  Let W^∈ℝd2×d2\hat{W}\in\mathbb{R}^{d^{2}\times d^{2}} be regressor:
Equation 3
W^:=arg​minW∈ℝd2×d2∑i∈[N]∑a∈[d](⟨W,Xi,a⟩−yi,a)2\hat{W}\vcentcolon=\argmin_{W\in\mathbb{R}^{d^{2}\times d^{2}}}\sum_{i\in[N]}\sum_{a\in[d]}\left(\langle W,X_{i,a}\rangle-y_{i,a}\right)^{2} (3)
where yi,ay_{i,a} is the aa’th coordinate of yiy_{i}.
6:  Take the SVD of W^=A​BT=∑i∈[H^]Ai​BiT\hat{W}=AB^{T}=\sum_{i\in[\hat{H}]}A_{i}B_{i}^{T} where H^\hat{H} is the rank of W^\hat{W}.
7:  Vh=Fold​(Ah)V_{h}=\text{Fold}(A_{h}) and Qh=Fold​(Bh)Q_{h}=\text{Fold}(B_{h}) where Fold:ℝd2→ℝd×d\text{Fold}:\mathbb{R}^{d^{2}}\rightarrow\mathbb{R}^{d\times d} takes a vector p:=[pi​j for i∈[d] and j∈[d]]p\vcentcolon=[p_{ij}\text{ for }i\in[d]\text{ and }j\in[d]] and reshapes into a matrix P∈ℝd×dP\in\mathbb{R}^{d\times d} such that Pi​j=pi​jP_{ij}=p_{ij}.
8:  Return: {Vh,Qh}h∈[H^]\{V_{h},Q_{h}\}_{h\in[\hat{H}]}

2 Technical Overview

The model sums value transformations multiplied by unnormalized key-query interactions. The formal definition below distinguishes the full sequence output from its last column, the next-token prediction used throughout the analysis.

Definition 2.1 (Multi-Head Linear Attention) .

Let Z∈ℝd×nZ\in\mathbb{R}^{d\times n} be a matrix of input data. Let Θ={(Vh,Qh)}h∈[H]\Theta=\{(V_{h},Q_{h})\}_{h\in[H]} be a set of parameters where each Vh,Qh∈ℝd×dV_{h},Q_{h}\in\mathbb{R}^{d\times d} denotes value and key-query matrices for all heads h∈[H]h\in[H]. We say Θ∈ΩH\Theta\in\Omega_{H} where ΩH\Omega_{H} is the space of sets of HH ordered tuples of d×dd\times d matrices. We define multi-head linear attention (MHLA) to be the function MHLAΘ:ℝd×n→ℝd×n\text{MHLA}_{\Theta}:\mathbb{R}^{d\times n}\rightarrow\mathbb{R}^{d\times n},

where Y^∈ℝd×n\hat{Y}\in\mathbb{R}^{d\times n} is the output of the one layer linear attention. We will primarily be interested in the rightmost column vector output by MHLAΘ\text{MHLA}_{\Theta} (e.g., as in auto-regressive language models), which is:

where Z[:,n]Z[:,n] is the nn’th column of ZZ.

Equations 4–5
Y^=MHLAΘ​(Z)=∑h∈[H]Vh​Z​(ZT​Qh​Z),\hat{Y}=\text{MHLA}_{\Theta}(Z)=\sum\nolimits_{h\in[H]}V_{h}Z(Z^{T}Q_{h}Z)~, (4)
y^=MHLAΘ(Z)=∑h∈[H]VhZ(ZTQhZ[:,n]),\hat{y}=\text{MHLA}_{\Theta}(Z)=\sum\nolimits_{h\in[H]}V_{h}Z(Z^{T}Q_{h}Z[:,n])~, (5)

2.1 Polynomial-time learnability

Algorithm 1 constructs cubic input features, fits an unrestricted lifted matrix by least squares, and factors it into attention heads. The output uses at most d² heads and competes with any head count. The empirical optimization reduction does not require independent samples; the population-risk theorem assumes independently drawn examples.

Theorem 2.2 states runtime O(Nd⁴nₘₐₓ/ε) and sample complexity O((d⁴ + log(1/δ))/ε). These are the paper’s stated rates. Its unrestricted real-valued, squared-loss statement does not specify the boundedness, tail, or numerical-conditioning assumptions needed to interpret such a distribution-free rate. The algebraic regression reduction is clearer than those quantitative statistical and numerical claims.

Equation 7
𝒳⁡(Z):=[⟨z1:,z1:⟩z1​n⟨z1:,z2:⟩z1​n⋯⟨z1:,zd:⟩zd​n⟨z2:,z1:⟩z1​n⟨z2:,z2:⟩z1​n⋯⟨z2:,zd:⟩zd​n⋱⟨zd:,z1:⟩z1​n⟨zd:,z2:⟩z1​n⋯⟨zd:,zd:⟩zd​n].\mathcal{X}(Z)\vcentcolon=\\ \begin{bmatrix}\langle z_{1:},z_{1:}\rangle z_{1n}&\langle z_{1:},z_{2:}\rangle z_{1n}&\cdots&\langle z_{1:},z_{d:}\rangle z_{dn}\\ \langle z_{2:},z_{1:}\rangle z_{1n}&\langle z_{2:},z_{2:}\rangle z_{1n}&\cdots&\langle z_{2:},z_{d:}\rangle z_{dn}\\ \vdots&\vdots&\ddots&\vdots\\ \langle z_{d:},z_{1:}\rangle z_{1n}&\langle z_{d:},z_{2:}\rangle z_{1n}&\cdots&\langle z_{d:},z_{d:}\rangle z_{dn}\\ \end{bmatrix}~. (7)

Theorem 2.2 (Learnability of Linear Attention) .

Let DD be a dataset D={Zi,yi}i∈[N]D=\{Z_{i},y_{i}\}_{i\in[N]} drawn i.i.d. from a distribution 𝒟\mathcal{D} where each Zi∈ℝd×niZ_{i}\in\mathbb{R}^{d\times n_{i}}, yi∈ℝdy_{i}\in\mathbb{R}^{d}. The embedding dimension dd is fixed across the dataset, whereas nin_{i} can be different for each datapoint. Let nm​a​x=maxi∈[N]⁡nin_{max}=\max_{i\in[N]}n_{i} be the maximum sequence length, and let ΩH\Omega_{H} be the space of HH pairs of value and key-query matrices {(Vh,Qh)}h∈[H]\{(V_{h},Q_{h})\}_{h\in[H]} for any H∈[1,∞)H\in[1,\infty). Then there is an algorithm (Algorithm 1) that runs in time O⁡(N​d4​nm​a​x​ϵ−1)O(Nd^{4}n_{max}\epsilon^{-1}) and that, given input–output pairs {(Zi,yi)}i∈[N]\{(Z_{i},y_{i})\}_{i\in[N]}, returns Θ^={(V^h,Q^h)}h∈[H^]∈ΩH^\hat{\Theta}=\{(\hat{V}_{h},\hat{Q}_{h})\}_{h\in[\hat{H}]}\in\Omega_{\hat{H}} for H^≤d2\hat{H}\leq d^{2} such that with probability 1−δ1-\delta,

with sample complexity N=O⁡(1ϵ​(d4+log⁡(δ−1)))N=O\left(\frac{1}{\epsilon}\left(d^{4}+\log(\delta^{-1})\right)\right).

Equation 6
𝔼(Z,y)∈𝒟​[‖MHLAΘ^​(Z)−y‖2]−minΘ∈ΩH⁡𝔼(Z,y)∈𝒟​[‖MHLAΘ​(Z)−y‖2]≤ϵ\mathbb{E}_{(Z,y)\in\mathcal{D}}\left[\|\text{MHLA}_{\hat{\Theta}}(Z)-y\|^{2}\right]\\ -\min\nolimits_{\Theta\in\Omega_{H}}\mathbb{E}_{(Z,y)\in\mathcal{D}}\left[\|\text{MHLA}_{\Theta}(Z)-y\|^{2}\right]\leq\epsilon (6)

Proof Idea:

Expand each output coordinate as a linear function of the lifted matrix TΘ. For H heads that matrix has rank at most H. Replacing it by an unrestricted W yields a convex least-squares problem. Its singular vectors, scaled by singular values and reshaped into d-by-d matrices, supply the value and key-query parameters.

Every d²-by-d² matrix admits at most d² rank-one terms, so the relaxation is expressible by a sufficiently wide attention layer. This explains why adding heads can remove the representational rank restriction. It does not prove that gradient descent on the original factored parameters reaches the same solution.

Equations 8–9
ℒΘ​({(Zi,yi)}i∈[N])=1N​∑i∈[N]∑a∈[d](⟨𝒯Θ,Xi,a⟩−yi,a)2\mathcal{L}_{\Theta}(\{(Z_{i},y_{i})\}_{i\in[N]})=\frac{1}{N}\sum_{i\in[N]}\sum_{a\in[d]}(\left\langle\mathcal{T}_{\Theta},X_{i,a}\right\rangle-y_{i,a})^{2} (8)
𝒯Θ:=∑h∈[H]flatten​(Vh)​flatten​(Qh)T=∑h∈[H][Vh,00​Qh,00Vh,00​Qh,01…Vh,00​Qh,d​dVh,01​Qh,00Vh,01​Qh,01…Vh,01​Qh,d​dVh,d​d​Qh,00Vh,d​d​Qh,01…Vh,d​d​Qh,d​d]\mathcal{T}_{\Theta}\vcentcolon=\sum_{h\in[H]}\text{flatten}(V_{h})\text{flatten}(Q_{h})^{T}\\ =\sum_{h\in[H]}\begin{bmatrix}V_{h,00}Q_{h,00}&V_{h,00}Q_{h,01}&\ldots&V_{h,00}Q_{h,dd}\\ V_{h,01}Q_{h,00}&V_{h,01}Q_{h,01}&\ldots&V_{h,01}Q_{h,dd}\\ \vdots&\vdots&\vdots\\ V_{h,dd}Q_{h,00}&V_{h,dd}Q_{h,01}&\ldots&V_{h,dd}Q_{h,dd}\end{bmatrix} (9)

2.2 Identifiability

Build the second-moment matrix of the reduced cubic features H, whose dimension is d·binomial(d,2) + d². Distinct off-diagonal row pairs and diagonal squares avoid duplicate symmetric features. If its smallest eigenvalue is positive, realizable empirical minimizers share the same polynomial coefficients and therefore agree on every input.

The parameter map p groups models by functional equivalence, rather than by raw matrix distance. With at least d² heads, all coefficient vectors are representable and the full-rank condition also identifies the best-fitting function for nonrealizable labels. Small eigenvalues make approximate identification sensitive to error; Appendix A/E gives the stated bounds.

Equation 10
ΛD=𝔼⁡[ℋ⁡(Z)​ℋ​(Z)T]=1N​∑Z∈D[ℋ⁡(Z)​ℋ​(Z)T].\Lambda_{D}=\mathbb{E}[\mathcal{H}(Z)\,\mathcal{H}(Z)^{T}]=\frac{1}{N}\sum_{Z\in D}[\mathcal{H}(Z)\,\mathcal{H}(Z)^{T}]. (10)

Lemma 2.3 (Certificate of Identifiability—Informal) .

Let dataset D={(Zi,yi)}i∈[N]D=\{(Z_{i},y_{i})\}_{i\in[N]} be realizable (see Definition A.2) by an HH-head MHLA for any H≥1H\geq 1. Let ℋ\mathcal{H} be the uniform family of polynomials ℋn:ℝd×n→ℝψ\mathcal{H}_{n}:\mathbb{R}^{d\times n}\rightarrow\mathbb{R}^{\psi} for ψ:=(d2)​d+d2\psi\vcentcolon={d\choose 2}d+d^{2} defined as in Algorithm 2. For convenience we drop the subscript of nn and write ℋ⁡(Z)\mathcal{H}(Z) to mean ℋn​(Z)\mathcal{H}_{n}(Z) for Z∈ℝd×nZ\in\mathbb{R}^{d\times n}. Finally, define ΛD∈ℝψ×ψ\Lambda_{D}\in\mathbb{R}^{\psi\times\psi} to be the second moment of the data features:

Then if the eigenvalue λmin​(ΛD)>0\lambda_{\min}\left(\Lambda_{D}\right)>0, we say that MHLAΘ\text{MHLA}_{\Theta} is certifiably identifiable with respect to DD. That is, for every pair of empirical risk minimizers Θ,Θ′∈ΩH\Theta,\Theta^{\prime}\in\Omega_{H}

i.e., the two models have the same outputs on all inputs.

Equations 11–12
ΛD:=𝔼D​[ℋ⁡(Z)​ℋ​(Z)T].\Lambda_{D}\vcentcolon=\mathbb{E}_{D}\left[\mathcal{H}(Z)\mathcal{H}(Z)^{T}\right]~. (11)
MHLAΘ=MHLAΘ′\text{MHLA}_{\Theta}=\text{MHLA}_{\Theta^{\prime}} (12)

Corollary 2.4 .

There is a polynomial p:ΩH→ℝψp:\Omega_{H}\rightarrow\mathbb{R}^{\psi} such that for any pair of parameters Θ,Θ′∈ΩH\Theta,\Theta^{\prime}\in\Omega_{H} we have MHLAΘ=MHLAΘ′\text{MHLA}_{\Theta}=\text{MHLA}_{\Theta^{\prime}} if and only if p⁡(Θ)=p⁡(Θ′)p(\Theta)=p(\Theta^{\prime}).

3 Application to learning Universal Turing Machines.

An autoregressive layer can simulate a Turing machine by repeatedly emitting an explicitly encoded computation history. The construction bounds the number of states, alphabet size, input length, and simulated steps in advance; its embedding dimension and number of heads grow with those bounds.

If traces are generated by that construction and their feature-moment matrix has minimum eigenvalue above η, the proposed learning procedure recovers a simulator throughout the bounded domain. This is conditional on obtaining certifying data. It is not a procedure for learning an unbounded universal machine from arbitrary natural-language traces.

Lemma 3.1 (Learning UTM from Certifiably Identifiable Data) .

Let D={(Zi,yi)}i∈[N]D=\{(Z_{i},y_{i})\}_{i\in[N]} be a dataset satisfying yi=MHLAΘy_{i}=\text{MHLA}_{\Theta} for Θ∈ΩH\Theta\in\Omega_{H} being the expressibility parameters of Lemma B.1 for the set of TM’s/words (M,x)∈Δ⁡(𝒬^,Σ^,n^,Φ^)(M,x)\in\Delta(\hat{\mathcal{Q}},\hat{\Sigma},\hat{n},\hat{\Phi}). If DD is certifiably identifiable with λm​i​n​(ΛD)>η\lambda_{min}(\Lambda_{D})>\eta, then there is a poly​(d,N,Q^,Σ^,n^,Φ^,η−1)\text{poly}(d,N,\hat{Q},\hat{\Sigma},\hat{n},\hat{\Phi},\eta^{-1}) time algorithm that outputs a set of parameters Θ^∈Ωd2\hat{\Theta}\in\Omega_{d^{2}} such that for all TM’s MM and input words xx in Δ⁡(𝒬^,Σ^,n^,Φ^)\Delta(\hat{\mathcal{Q}},\hat{\Sigma},\hat{n},\hat{\Phi}), we have

The c⁡(t)c(t) step of the autoregressive computation history of Θ^\hat{\Theta} is equal to the tt’th step of the computation history of MM on xx.

Equation 13
CHΘ^(M,x)c⁡(t)[:−kt]=xt.\text{CH}_{\hat{\Theta}}(M,x)^{c(t)}[:-k_{t}]=x^{t}~. (13)

4 Experiments

Two synthetic studies examine implications of the theory for practical optimizers: whether more heads aid fitting, and whether the certificate predicts recovery of the ground-truth function. A separate appendix experiment studies finite-automaton execution with a conventional Transformer.

4.1 Do extra heads help optimization with SGD?

Data come from a random single-head linear-attention teacher on Gaussian sequences of length up to 100. The PDF specifies covariance scaling I/√d for teacher parameters and I/√T for inputs. Models include multi-head single-layer attention, deeper single-head attention, and a full Transformer with softmax, feedforward blocks, and layer normalization.

For d = 2 with 512 examples and d = 4 with 2,048 examples, sufficient heads approach the convex method’s numerical error floor. Adding layers or full-Transformer components gives no consistent gain on this deliberately linear-attention-generated task. Shading shows standard error over three runs. These small synthetic experiments support an optimization pattern, not a general ranking of depth and width on language tasks.

Equations𝒩⁡(0,Id)\mathcal{N}(0,\frac{I}{\sqrt{d}})𝒩⁡(0,IT)\mathcal{N}(0,\frac{I}{\sqrt{T}})
Original figure
(a) N=512,d=2N=512,d=2
Original figure
(b) N=2048,d=4N=2048,d=4
Figure 1: Performance comparison of multi-head, multi-layer linear attention models and the original Transformer model (denoted as full). We trained using SGD on synthetic data generated from a single-layer linear attention model for varying training set sizes (NN) and input dimensions (dd), number of heads mm, and number of layers nn. Results demonstrate that multi-head architectures converge faster on different input dimensions and match the performance of our algorithm 1 (convex algorithm). Increasing the number of layers or incorporating multilayer perceptrons (MLPs) and layer normalization did not yield consistent improvements. Shading indicates the standard error over three different runs.

4.2 Does certifiable identifiability predict generalization?

The associative-memory experiment varies the feature-moment eigenvalue and measures distance to the teacher in coefficient space. This connects the certificate to functional recovery rather than ordinary parameter matching.

Original figure
(a) Certificate of identifiability in form of the minimum Eigenvalue λmin​(ΛD)\lambda_{\min}(\Lambda_{D}) vs. Euclidean distance in pp feature space of parameters learned by Algorithm 1.
Original figure
(b) Distance to ground truth parameters in pp feature space for certifiably identifiable data (min eigenvalue =0.06=0.06) vs. nonidentifiable data (min eigenvalue =0=0). Here the parameters of MHLA are learned via SGD. Error bars are standard error on three different runs.
Figure 2: Impact of data distribution on the associative lookup task performance: We generated training data for an associative lookup task (Bietti et al., 2023; Cabannes et al., 2024) using mixtures of two distributions: (1) Gaussian key and value vectors, and (2) random unitary key and value vectors. By adjusting the mixture probability, we can manipulate the certificate value (minimum eigenvalue of the data covariance matrix), as unitary key–value vectors give rank-deficient “certificates”. (a) Algorithm 1: as the minimum eigenvalue increases, Algorithm 1 converges more closely to the true parameters. (b) SGD: SGD learns parameters that are equivalent to the ground truth parameters in pp feature space for certifiably identifiable data, but for unidentifiable data, they are far apart in pp feature space and therefore compute different functions.

Associative Memory

The task, following Bietti et al. and Cabannes et al., returns a weighted sum of stored values, with weights given by query–key inner products. The retained block matrices define a single-head teacher. Orthogonal keys reduce this weighted retrieval to an exact lookup; Gaussian keys generally produce a mixture.

Equations 14–15
V=[000Id×d]Q=[Id×d000].\displaystyle V=\begin{bmatrix}0&0\\ 0&I_{d\times d}\end{bmatrix}\quad Q=\begin{bmatrix}I_{d\times d}&0\\ 0&0\end{bmatrix}.
Z=[k1k2…kdqv1v2…vdζ]\displaystyle Z=\begin{bmatrix}k_{1}&k_{2}&\ldots&k_{d}&q\\ v_{1}&v_{2}&\ldots&v_{d}&\zeta\end{bmatrix} (14)
y=MHLAΘ​(Z)=[0∑j∈[d]⟨q,kj⟩​vj].\displaystyle y=\text{MHLA}_{\Theta}(Z)=\begin{bmatrix}0\\ \sum_{j\in[d]}\langle q,k_{j}\rangle v_{j}\end{bmatrix}. (15)

Mixture of distributions:

Keys and values are either Gaussian or columns of independently drawn orthogonal matrices; the query is a uniformly chosen stored key. With d = 4 and 2¹⁴ examples per source dataset, mixtures containing 95–100% orthogonal examples produce progressively weaker certificates. The paper reports full-rank Gaussian data and rank-deficient orthogonal data in this experiment.

Certifiable Identifiability for Algorithm 1 :

After Algorithm 1 fits each mixture, the authors compare its coefficient representation p with the teacher’s. Figure 2a shows smaller coefficient error as the minimum eigenvalue increases. The statistic measures how well the function is identified; it is not directly a held-out task-success rate.

Equation 16
d⁡(Θ,Θ^):=‖p⁡(Θ)−p⁡(Θ^)‖F.d(\Theta,\hat{\Theta})\vcentcolon=\|p(\Theta)-p(\hat{\Theta})\|_{F}. (16)

Certifiable Identifiability for MHLA:

For gradient-trained models with one, two, four, or eight heads, the full-rank dataset has certificate value 0.06 and the deficient dataset has value zero. Learned coefficients are close to the teacher in the former and substantially different in the latter. The theorem applies to an optimizer only insofar as it actually attains the required empirical risk.

5 Related Work

Related work separates representational expressivity, sample requirements, and the computational difficulty of fitting attention.

5.1 Formal Expressivity of Transformers

Earlier work implements circuits, logical expressions, domain-specific languages, formal-language recognizers, and Turing machines with attention. These expressivity results, including Turing completeness, do not themselves supply an efficient learner or a check that a given dataset uniquely identifies the intended computation.

5.2 Learning Transformers

Statistical bounds need not give tractable training algorithms. Earlier optimization results often fix attention parameters, assume structured data, or require favorable initialization and separability. The comparisons include multi-head overparameterization and learning under Bernoulli/Gaussian input assumptions. The present regression lifting targets a simpler unnormalized single-layer class with variable width.

6 Conclusion and Limitations

The main contribution is a concrete way to turn sufficient attention width into convex empirical optimization, together with a data-dependent certificate for functional identification. The model excludes softmax, learned nonlinear intermediate representations, and the multiple interacting layers of modern language models.

The paper proposes extensions through key-query feature maps. Their practicality depends on the size and computability of the resulting representation; the present proof should not be read as an efficient training guarantee for arbitrary learned kernels or full Transformers. Source statements and proofs are retained below, including the qualifications noted for their quantitative bounds.

Acknowledgments

The authors acknowledge NSF, AFOSR, ONR, ARO, Open Philanthropy, MIT Quest for Intelligence, the MIT–IBM Watson AI Lab, the Simons Center for the Social Brain, and an Alexander von Humboldt professorship.

Appendix A Certificate for identifiability of linear attention

Identifiability means that every empirical minimizer computes the same function on all inputs. Realizability means that some model exactly produces the observed labels. Algorithm 2 constructs distinct pair and square features; a full-rank empirical second moment makes the corresponding least-squares coefficient vector unique.

The formal results below distinguish realizable fixed-width models, sufficiently wide models with arbitrary labels, population input-noise claims, and approximate minimizers. The compact coefficient formula in Corollary A.4 should be read with Appendix E’s separate diagonal formula; doubling a diagonal term would give the wrong expansion.

The error statements are preserved as printed. Lemma A.7 defines its set using absolute squared training error, not excess error above a nonzero optimum. Its displayed conclusion uses an unsquared output norm, while the proof bounds a squared norm and omits constants when comparing two approximate fits. It supports a conditioning-dependent stability interpretation, not direct reuse of the printed bound without checking these details.

Algorithm 2 Constructing Features for Certificates of Identifiability
1:  Input: Data D:={Zi}i∈[N]D\vcentcolon=\{Z_{i}\}_{i\in[N]} for Zi∈ℝd×niZ_{i}\in\mathbb{R}^{d\times n_{i}}
2:  Output: feature vectors ℋ⁡(Zi)\mathcal{H}(Z_{i}) for i∈[N]i\in[N]
3:  for Zi∈DZ_{i}\in D do
4:   Let z1:,z2:,…zd:z_{1:},z_{2:},...z_{d:} be the rows of ZiZ_{i} and let za​bz_{ab} be the (a,b)(a,b) entry of ZiZ_{i}
5:   for sets ​{j,k}​ in Distinct Pairs of Indices in ​[d]2\text{sets }\{j,k\}\text{ in Distinct Pairs of Indices in }[d]^{2} do
6:    for ℓ∈[d]\ell\in[d] do
7:      ℋ(Zi)=ℋ(Zi)∘[⟨zj:,zk:⟩zℓ​ni]\mathcal{H}(Z_{i})=\mathcal{H}(Z_{i})\circ\left[\langle z_{j:},z_{k:}\rangle z_{\ell n_{i}}\right]
8:    end for
9:   end for
10:   for j∈[d]j\in[d] do
11:    for ℓ∈[d]\ell\in[d] do
12:      ℋ⁡(Zi)=ℋ⁡(Zi)∘[‖zj‖2​zℓ​ni]\mathcal{H}(Z_{i})=\mathcal{H}(Z_{i})\circ\left[\|z_{j}\|^{2}z_{\ell n_{i}}\right]
13:    end for
14:   end for
15:  end for
16:  Return: {ℋ⁡(Zi)}i∈[N]\{\mathcal{H}(Z_{i})\}_{i\in[N]}

Definition A.1 (Identifiability) .

Let D={(Zi,yi)}i∈[N]D=\{(Z_{i},y_{i})\}_{i\in[N]}. Let 𝒰Θ\mathcal{U}_{\Theta} denote a model class which is a uniform circuit family parameterized by parameters Θ∈Ω\Theta\in\Omega. Let ℒ\mathcal{L} be a loss function and ΩERM\Omega_{\text{ERM}} be the set of empirical risk minimizers:

We say model class 𝒰Θ\mathcal{U}_{\Theta} is identifiable with respect to the dataset DD if for all Z∈ℝd×n′Z\in\mathbb{R}^{d\times n^{\prime}}, and for all pairs of empirical risk minimizers Θ,Θ′∈ΩERM\Theta,\Theta^{\prime}\in\Omega_{\text{ERM}} we have 𝒰Θ\mathcal{U}_{\Theta} and 𝒰Θ′\mathcal{U}_{\Theta^{\prime}} compute the same function, i.e., they agree on all inputs (are the same uniform circuit family):

Equations 17–18
ΩΘ={Θ^∈Ω∣Θ^=arg​minΘ∈Ω⁡ℒ​(𝒰Θ,D)}.\Omega_{\Theta}=\{\hat{\Theta}\in\Omega\mid\hat{\Theta}=\argmin\nolimits_{\Theta\in\Omega}\mathcal{L}(\mathcal{U}_{\Theta},D)\}. (17)
𝒰Θ​(Z)=𝒰Θ′​(Z).\mathcal{U}_{\Theta}(Z)=\mathcal{U}_{\Theta^{\prime}}(Z). (18)

Definition A.2 (Realizability) .

Let Θ∈ΩH\Theta\in\Omega_{H} be an MHLA parameterization. We say a dataset D={(Zi,yi)}i∈[N]D=\{(Z_{i},y_{i})\}_{i\in[N]} is realizable by a parameterization Θ\Theta if yi=MHLAΘ​(Zi)y_{i}=\text{MHLA}_{\Theta}(Z_{i}).

Lemma A.3 (Certificate of Identifiability) .

Let dataset D={(Zi,yi)}i∈[N]D=\{(Z_{i},y_{i})\}_{i\in[N]} be a realizable dataset. Let ℋ={ℋn}n=1∞\mathcal{H}=\{\mathcal{H}_{n}\}_{n=1}^{\infty} be a family of polynomials ℋn:ℝd×n→ℝψ\mathcal{H}_{n}:\mathbb{R}^{d\times n}\rightarrow\mathbb{R}^{\psi} for ψ=(d2)​d+d2\psi={d\choose 2}d+d^{2} defined as follows. We index the entries of ℋ\mathcal{H} by taking the Kronecker product between all sets of pairs {j,k}\{j,k\} (for all j,k∈[d]j,k\in[d]) with with all ℓ∈[d]\ell\in[d]. We define ℋ​(Z){j,k}​ℓ\mathcal{H}(Z)_{\{j,k\}\ell} as in Algorithm 2 to be

Then if λm​i​n​(𝔼D​[ℋ⁡(Z)​ℋ​(Z)T])>0\lambda_{min}\left(\mathbb{E}_{D}\left[\mathcal{H}(Z)\mathcal{H}(Z)^{T}\right]\right)>0, we have that MHLAΘ\text{MHLA}_{\Theta} is identifiable with respect to DD.

Equation 19
ℋ(Z){j,k}​ℓ:=⟨zj:,zk:⟩zℓ​ni.\mathcal{H}(Z)_{\{j,k\}\ell}\vcentcolon=\langle z_{j:},z_{k:}\rangle z_{\ell n_{i}}. (19)

Corollary A.4 .

Let {pa}a∈[d]\{p_{a}\}_{a\in[d]} be a collection of polynomials such that pa​(Θ):ΩH→ℝψp_{a}(\Theta):\Omega_{H}\rightarrow\mathbb{R}^{\psi} is defined as follows. Each pa​(Θ)p_{a}(\Theta) is indexed by pairs {j,k}\{j,k\} for j,k∈[d]j,k\in[d] and ℓ∈[d]\ell\in[d] defined to be

Let the polynomial p:Ω→ℝd×ψp:\Omega\rightarrow\mathbb{R}^{d\times\psi} be p:=(p1,p2,…,pd)p\vcentcolon=(p_{1},p_{2},...,p_{d}). Then for any pair of parameters Θ,Θ′∈ΩH\Theta,\Theta^{\prime}\in\Omega_{H} we have MHLAΘ=MHLAΘ′\text{MHLA}_{\Theta}=\text{MHLA}_{\Theta^{\prime}} if and only if p⁡(Θ)=p⁡(Θ′)p(\Theta)=p(\Theta^{\prime}).

Equation 20
pa​(Θ){j,k}​ℓ=∑h∈[H](Vh,a​j​Qk​ℓ+Vh,a​k​Qj​ℓ).p_{a}(\Theta)_{\{j,k\}\ell}=\sum_{h\in[H]}\left(V_{h,aj}Q_{k\ell}+V_{h,ak}Q_{j\ell}\right)~. (20)

Lemma A.5 (Independent input noise yields identifiability) .

Let (Z,y)∼𝒟(Z,y)\sim\mathcal{D} be a realizable dataset. Let ZZ be drawn from a distribution 𝒵\mathcal{Z} where the (a,b)(a,b)-th entry of ZZ denoted by Za​bZ_{ab} is drawn i.i.d. from a distribution ν\nu over ℝ\mathbb{R} for all a∈[d]a\in[d] and b∈[n]b\in[n]. Let the second and fourth moment of ν\nu be denoted m2m_{2} and m4m_{4} respectively. Let m2>0m_{2}>0 and m4>m22m_{4}>m_{2}^{2}. Then MHLAΘ\text{MHLA}_{\Theta} for Θ∈ΩH\Theta\in\Omega_{H} is identifiable with respect to DD. That is to say, for any population risk minimizers Θ,Θ′∈ΩPRM\Theta,\Theta^{\prime}\in\Omega_{\text{PRM}}:

Equation 21
MHLAΘ=MHLAΘ′.\text{MHLA}_{\Theta}=\text{MHLA}_{\Theta^{\prime}}. (21)

Lemma A.6 (Identifiability without realizability for MHLA with arbitrarily many heads) .

Let dataset D={(Zi,yi)}i∈[N]D=\{(Z_{i},y_{i})\}_{i\in[N]} be any dataset drawn i.i.d from a distribution 𝒟\mathcal{D}. Let ℋ\mathcal{H} be defined as in Lemma A.3. Then if λmin​(𝔼D​[ℋ⁡(Z)​ℋ​(Z)T])>0\lambda_{\min}\left(\mathbb{E}_{D}[\mathcal{H}(Z)\mathcal{H}(Z)^{T}]\right)>0 then MHLAΘ\text{MHLA}_{\Theta} for Θ∈ΩH\Theta\in\Omega_{H} for any H∈[d2,∞)H\in[d^{2},\infty) is identifiable with respect to the data DD. That is,

for all pairs of empirical risk minimizers Θ,Θ′∈ΩERM\Theta,\Theta^{\prime}\in\Omega_{\text{ERM}}.

Equation 22
MHLAΘ=MHLAΘ′\text{MHLA}_{\Theta}=\text{MHLA}_{\Theta^{\prime}} (22)

Lemma A.7 (Identifiability with Error) .

Let Ωϵ−ERM\Omega_{\epsilon-\text{ERM}} be the set of ϵ\epsilon-approximate empirical risk minimizers,

Then we have for any Θ,Θ′∈Ωϵ−ERM\Theta,\Theta^{\prime}\in\Omega_{\epsilon-\text{ERM}} that for all inputs Z∈ℝd×nZ\in\mathbb{R}^{d\times n}

Equations 23–24
Ωϵ−ERM={Θ∈ΩH|𝔼(Zi,yi)∈D​[(MHLAΘ​(Zi)−yi)2]≤ϵ}.\Omega_{\epsilon-\text{ERM}}=\\ \left\{\Theta\in\Omega_{H}~\big|~\mathbb{E}_{(Z_{i},y_{i})\in D}\left[\left(\text{MHLA}_{\Theta}(Z_{i})-y_{i}\right)^{2}\right]\leq\epsilon\right\}. (23)
‖MHLAΘ​(Z)−MHLAΘ′​(Z)‖≤ϵλmin​(ΛD)​‖Z‖F6.\|\text{MHLA}_{\Theta}(Z)-\text{MHLA}_{\Theta^{\prime}}(Z)\|\leq\frac{\epsilon}{\lambda_{\min}\left(\Lambda_{D}\right)}\|Z\|_{F}^{6}. (24)

Application to learning Universal Turing Machines.

Combining the bounded simulator construction with the certificate yields agreement throughout the stated finite-size domain. The inverse certificate margin enters the runtime through the fitting precision needed for reliable token rounding.

Lemma A.8 (Learning UTM from Certifiably Identifiable Data) .

Let D={(Zi,yi)}i∈[N]D=\{(Z_{i},y_{i})\}_{i\in[N]} be a dataset satisfying yi=MHLAΘy_{i}=\text{MHLA}_{\Theta} for Θ∈ΩH\Theta\in\Omega_{H} being the expressibility parameters of Lemma B.1 for the set of TM’s/words (M,x)∈Δ⁡(𝒬^,Σ^,n^,Φ^)(M,x)\in\Delta(\hat{\mathcal{Q}},\hat{\Sigma},\hat{n},\hat{\Phi}). If DD is certifiably identifiable with λm​i​n​(ΛD)>η\lambda_{min}(\Lambda_{D})>\eta, then there is a poly​(d,N,Q^,Σ^,n^,Φ^,η−1)\text{poly}(d,N,\hat{Q},\hat{\Sigma},\hat{n},\hat{\Phi},\eta^{-1}) time algorithm that outputs a set of parameters Θ^∈Ωd2\hat{\Theta}\in\Omega_{d^{2}} such that for all TM’s MM and input words xx in Δ⁡(𝒬^,Σ^,n^,Φ^)\Delta(\hat{\mathcal{Q}},\hat{\Sigma},\hat{n},\hat{\Phi}), we have

The c⁡(t)c(t) step of the autoregressive computation history of Θ^\hat{\Theta} is equal to the tt’th step of the computation history of MM on xx.

Equation 25
CHΘ^(M,x)c⁡(t)[:−kt]=xt.\text{CH}_{\hat{\Theta}}(M,x)^{c(t)}[:-k_{t}]=x^{t}~. (25)

Appendix B Realizability of Universal Automata in MHLA

The expressivity construction encodes symbols, states, and positions with orthogonal vectors. Lookup, copy, and conditional update primitives append each successive computation-history symbol. It uses O(n̂Φ̂Σ̂) heads and embedding dimension O(n̂Φ̂Σ̂·max(Σ̂,Q̂)), with two-bit construction precision and O((n+t)t) autoregressive steps to represent t machine steps.

These resource bounds grow with the prescribed input/history limits. The construction is a bounded simulator, not a fixed finite-dimensional machine executing arbitrarily long histories without changing its encoding budget.

Lemma B.1 (UTM Expressibility) .

Let Δ⁡(𝒬^,Σ^,n^,Φ^)\Delta(\hat{\mathcal{Q}},\hat{\Sigma},\hat{n},\hat{\Phi}) be the set of Turing machines M={δ,Σ,𝒬,qs​t​a​r​t,qa​c​c​e​p​t,qr​e​j​e​c​t}M=\{\delta,\Sigma,\mathcal{Q},q_{start},q_{accept},q_{reject}\} and words x∈Σ∗x\in\Sigma^{*} with number of states, size of alphabet, size of input, and number of steps in computation history bounded by 𝒬^,Σ^,n^,Φ^\hat{\mathcal{Q}},\hat{\Sigma},\hat{n},\hat{\Phi} respectively. For any (M,x)∈Δ(M,x)\in\Delta, let {xt}t∈[Φ]\{x_{t}\}_{t\in[\Phi]} be the computation history of the UTM on (M,x)(M,x). Let the autoregressive computation history (see Definition C.2) of MHLAΘ\text{MHLA}_{\Theta} on input (M,x)(M,x) be denoted CHΘ​(M,x)={Z1,Z2,…,ZΦ}\text{CH}_{\Theta}(M,x)=\{Z^{1},Z^{2},...,Z^{\Phi}\}. Then there exists a set of parameters Θ∈ΩH\Theta\in\Omega_{H} for H=O⁡(n^​Φ^​Σ^)H=O(\hat{n}\hat{\Phi}\hat{\Sigma}) and embedding dimension d=O⁡(n^​Φ^​Σ^​max⁡(Σ^,𝒬^))d=O(\hat{n}\hat{\Phi}\hat{\Sigma}\max(\hat{\Sigma},\hat{\mathcal{Q}})), such that for all (M,x)∈Δ(M,x)\in\Delta, the TM computation history at time step tt is equivalent to the autoregressive computation history at time step c⁡(t)c(t) where c⁡(t)≤O⁡((n+t)​t)c(t)\leq O((n+t)t) i.e Zc⁡(t)[:−length(xt))]=xtZ^{c(t)}[:-\text{length}(x^{t}))]=x^{t}. Furthermore, this can be achieved with 2 bits of precision.

Appendix C Application to Learning Universal Turing Machines

Autoregressive attention appends each predicted token to its context. Computation histories record that growing sequence, and a decoding convention identifies the suffix representing a simulated tape. The definitions below make the machine description, word, state space, and runtime restriction explicit.

Training examples are intermediate histories paired with their next tokens. Lemma C.5 first invokes the regression generalization result, then rounds predictions and uses a union bound to control failure over the simulated history. This separates on-distribution trace accuracy from the stronger, certificate-dependent out-of-distribution claim. The number of independent machine/word draws must be distinguished from the dependent tokens within each trace.

Definition C.1 (Autoregressive MHLA) .

Let Z0Z^{0} be an input matrix in dimension ℝd×n\mathbb{R}^{d\times n}. We define the iterative process of Φ\Phi-step autoregressive MHLA as follows: starting from t=0t=0, let the next token yt+1∈ℝdy^{t+1}\in\mathbb{R}^{d} be:

and, for all t∈[Φ]t\in[\Phi], let Zt+1∈ℝd×(n+1)Z^{t+1}\in\mathbb{R}^{d\times(n+1)} be the concatenation:

Equations 26–27
yt+1=MHLAΘ​(Zt),y^{t+1}=\text{MHLA}_{\Theta}(Z^{t})~, (26)
Zt+1=Zt∘yt.Z^{t+1}=Z^{t}\circ y^{t}~. (27)

Definition C.2 (Autoregressive Computation History) .

We refer to CHΘ​(Z)={Zt}t∈[Φ]\text{CH}_{\Theta}(Z)=\{Z^{t}\}_{t\in[\Phi]} as the computation history of the Φ\Phi-step autoregressive MHLA. We denote the tt-th step of the computation history as CHΘt​(Z)=Zt\text{CH}_{\Theta}^{t}(Z)=Z^{t}.

Definition C.3 (Accept TM) .

Let M={δ,Σ,Γ,𝒬,qs​t​a​r​t,qa​c​c​e​p​t,qr​e​j​e​c​t}M=\{\delta,\Sigma,\Gamma,\mathcal{Q},q_{start},q_{accept},q_{reject}\} be a TM. Let x∈Σ∗x\in\Sigma^{*} be all strings in the alphabet Σ\Sigma. Then let ATMA_{\text{TM}} be the language ATM={(M,x)∣M​ accepts ​x}A_{\text{TM}}=\{(M,x)\mid M\text{ accepts }x\}.

Definition C.4 .

(Polynomially Bounded Universal Turing Machine) In general, a UTM is a recognizer for the language ATMA_{\text{TM}}. That is if xx is in ATMA_{\text{TM}}, the UTM accepts, else, the UTM rejects or does not halt. Let ATM∩PA_{\text{TM}}\cap P be the language of input pairs (M,x)(M,x) for TM MM and word x∈Σ∗x\in\Sigma^{*} such that MM decides xx in polynomial time. Here, we consider UTM to be the polynomial time decider for ATM∩PA_{\text{TM}}\cap P.

Lemma C.5 (Learning a UTM) .

Let Θ∈ΩH\Theta\in\Omega_{H} in dimension dd be the MHLA parameters in Lemma B.1. Let {Mi,xi}i∈[N]\{M_{i},x_{i}\}_{i\in[N]} be pairs of TM’s MM and words xx of maximum length nn drawn i.i.d. from a distribution 𝒟\mathcal{D}. Let Zi=Embed​(Mi,xi)Z_{i}=\text{Embed}(M_{i},x_{i}). For each TM/word pair (Mi,xi)(M_{i},x_{i}) let CHΘ​(Zi)={Zi1,Zi2,…,ZiΦ}\text{CH}_{\Theta}(Z_{i})=\{Z^{1}_{i},Z^{2}_{i},...,Z^{\Phi}_{i}\} be the Φ\Phi-step autoregressive computation history of MHLAΘ\text{MHLA}_{\Theta} on ZiZ_{i}. Let DD be the dataset D:={(CHΘ(Zi)t,yit+1}i∈[N],t∈[T]D\vcentcolon=\{(\text{CH}_{\Theta}(Z_{i})^{t},y^{t+1}_{i}\}_{i\in[N],t\in[T]} where yit+1=MHLAΘ​(Zit)y^{t+1}_{i}=\text{MHLA}_{\Theta}(Z^{t}_{i}). Then Algorithm 1 applied to input DD returns Θ^∈ΩH\hat{\Theta}\in\Omega_{H} for H≤d2H\leq d^{2} such that with probability 1−δ1-\delta

for sample complexity N=poly​(d,ϵ−1,log⁡(δ−1))N=\text{poly}(d,\epsilon^{-1},\log(\delta^{-1})). Then with probability 1−δ1-\delta over the randomness in the data, the probability over 𝒟\mathcal{D} that the Φ\Phi-step autoregressive computation history CHΘ^​(M,x)\text{CH}_{\hat{\Theta}}(M,x) and CHΘ​(M,x)\text{CH}_{\Theta}(M,x) differ is upper bounded by

Equations 28–29
𝔼(Z,y)∈𝒟​[(MHLAΘ^​(Z)−y)2]≤ϵ\mathbb{E}_{(Z,y)\in\mathcal{D}}\left[\left(\text{MHLA}_{\hat{\Theta}}(Z)-y\right)^{2}\right]\leq\epsilon (28)
Pr(M,x)∼𝒟[CHΘ^(M,x)≠CHΘ(M,x)]≤O(ϵΦ).\Pr\nolimits_{(M,x)\sim\mathcal{D}}[\text{CH}_{\hat{\Theta}}(M,x)\neq\text{CH}_{\Theta}(M,x)]\leq O(\epsilon\Phi). (29)

Appendix D Proof of the Main Theorem

Expanding the squared loss shows that each prediction is linear in the lifted parameter matrix. Least squares finds its optimum, and SVD recovers an equivalent attention layer with at most d² heads. Thus the constructive argument concerns fitting the best representable lifted predictor, regardless of whether labels are realizable.

The proof’s final inequality prints absolute training loss ≤ ε, although the preceding agnostic argument bounds loss relative to the optimum. With irreducible label error, that absolute claim does not follow. The original equation is preserved; the useful conclusion is comparison with the best fit. The population-rate step invokes classical learning theory without spelling out squared-loss boundedness or tail conditions.

Equations 30–35
ℒΘ​({(Zi,yi)}i∈[N])\displaystyle\mathcal{L}_{\Theta}(\{(Z_{i},y_{i})\}_{i\in[N]}) :=1N∑i∈[N]‖∑h∈[H]VhZi(ZiTQhZ[:,ni])−yi‖F2\displaystyle\vcentcolon=\frac{1}{N}\sum_{i\in[N]}\left\|\sum_{h\in[H]}V_{h}Z_{i}(Z_{i}^{T}Q_{h}Z[:,n_{i}])-y_{i}\right\|_{F}^{2} (30)
=1N∑i∈[N]∑a∈[d](∑h∈[H]eaTVhZi(ZiTQhZ[:,ni])−yi,a)2\displaystyle=\frac{1}{N}\sum_{i\in[N]}\sum_{a\in[d]}\left(\sum_{h\in[H]}e_{a}^{T}V_{h}Z_{i}(Z_{i}^{T}Q_{h}Z[:,n_{i}])-y_{i,a}\right)^{2} (31)
=1N​∑i∈[N]∑a∈[d](⟨𝒯Θ,Xi,a⟩−yi,a)2=\frac{1}{N}\sum_{i\in[N]}\sum_{a\in[d]}(\left\langle\mathcal{T}_{\Theta},X_{i,a}\right\rangle-y_{i,a})^{2} (32)
𝒯Θ:=∑h∈[H]flatten​(Vh)​flatten​(Qh)T=∑h∈[H][Vh,00​Qh,00Vh,00​Qh,01…Vh,00​Qh,d​dVh,01​Qh,00Vh,01​Qh,01…Vh,01​Qh,d​dVh,d​d​Qh,00Vh,d​d​Qh,01…Vh,d​d​Qh,d​d]\mathcal{T}_{\Theta}\vcentcolon=\sum_{h\in[H]}\text{flatten}(V_{h})\text{flatten}(Q_{h})^{T}=\sum_{h\in[H]}\begin{bmatrix}V_{h,00}Q_{h,00}&V_{h,00}Q_{h,01}&\ldots&V_{h,00}Q_{h,dd}\\ V_{h,01}Q_{h,00}&V_{h,01}Q_{h,01}&\ldots&V_{h,01}Q_{h,dd}\\ \vdots&\vdots&\vdots\\ V_{h,dd}Q_{h,00}&V_{h,dd}Q_{h,01}&\ldots&V_{h,dd}Q_{h,dd}\end{bmatrix} (33)
minW∈ℝd2×d2⁡ℒW​({(Zi,yi)}i∈[N]):=1N​∑i∈[N]∑a∈[d](⟨W,Xi,a⟩−yi,a)2≤minΘ∈ΩH⁡ℒΘ​({(Zi,yi)}i∈[N])+ϵ\min_{W\in\mathbb{R}^{d^{2}\times d^{2}}}\mathcal{L}_{W}(\{(Z_{i},y_{i})\}_{i\in[N]})\vcentcolon=\frac{1}{N}\sum_{i\in[N]}\sum_{a\in[d]}(\left\langle W,X_{i,a}\right\rangle-y_{i,a})^{2}\\ \leq\min_{\Theta\in\Omega_{H}}\mathcal{L}_{\Theta}(\{(Z_{i},y_{i})\}_{i\in[N]})+\epsilon (34)
ℒΘ^({(Zi,yi)}i∈[N]):=1N∑i∈[N]‖∑h∈[H^]V^hZi(ZiTQ^hZi[:,ni])−yi‖F2=1N∑i∈[N]∑a∈[d](∑h∈[H^]V^hZi(ZiTQ^hZi[:,ni])−yi,a)2≤ϵ\mathcal{L}_{\hat{\Theta}}(\{(Z_{i},y_{i})\}_{i\in[N]})\vcentcolon=\frac{1}{N}\sum_{i\in[N]}\left\|\sum_{h\in[\hat{H}]}\hat{V}_{h}Z_{i}(Z_{i}^{T}\hat{Q}_{h}Z_{i}[:,n_{i}])-y_{i}\right\|_{F}^{2}\\ =\frac{1}{N}\sum_{i\in[N]}\sum_{a\in[d]}\left(\sum_{h\in[\hat{H}]}\hat{V}_{h}Z_{i}(Z_{i}^{T}\hat{Q}_{h}Z_{i}[:,n_{i}])-y_{i,a}\right)^{2}\leq\epsilon (35)

Appendix E Proofs from Identifiability Section

The general certificate writes a model as an inner product between parameter polynomials and input features. In the realizable case, every empirical minimizer reaches zero loss; a positive-definite feature second moment gives a unique coefficient vector. Hence all minimizers agree everywhere, despite possible parameter redundancy.

For linear attention, group the symmetric off-diagonal products and handle row-square terms separately. Equations in this section give both coefficient formulas and reconstruct the output exactly. At width at least d², SVD makes the coefficient map surjective, so uniqueness of least squares no longer needs realizability.

The independent-input proof centers and normalizes features, then analyzes pair–pair, square–square, and mixed moments. Its printed moment calculations have additional subtleties: for example, overlapping indices can involve sixth moments, whereas the stated assumptions mention only second and fourth moments. The edition retains the claims and calculations rather than silently strengthening them.

Equations 38–49
MHLAΘ​(Z)|a=⟨pa​(Θ),ℋ⁡(Z)⟩\text{MHLA}_{\Theta}(Z)|_{a}=\langle p_{a}(\Theta),\mathcal{H}(Z)\rangle (38)
ℛv​(ℋ⁡(Z))=⟨v,ℋ⁡(Z)⟩\mathcal{R}_{v}(\mathcal{H}(Z))=\langle v,\mathcal{H}(Z)\rangle (39)
ΘERM:={Θ′∈Ω|Θ′=arg​minΘ∈Ω𝔼i∈[N][ℒ(MHLAΘ(Zi),yi)}]\Theta_{\text{ERM}}\vcentcolon=\{\Theta^{\prime}\in\Omega|\Theta^{\prime}=\argmin_{\Theta\in\Omega}\mathbb{E}_{i\in[N]}\left[\mathcal{L}(\text{MHLA}_{\Theta}(Z_{i}),y_{i})\}\right] (40)
vERM:={v′∈ℝψ|v′=arg​minv∈ℝψ⁡𝔼i∈[N]​[ℒ⁡(ℛv​(ℋ⁡(Zi)),yi)]}v_{\text{ERM}}\vcentcolon=\{v^{\prime}\in\mathbb{R}^{\psi}|v^{\prime}=\argmin_{v\in\mathbb{R}^{\psi}}\mathbb{E}_{i\in[N]}\left[\mathcal{L}(\mathcal{R}_{v}(\mathcal{H}(Z_{i})),y_{i})\right]\} (41)
MHLAΘ​(Z)​[a]=⟨pa​(Θ),ℋ⁡(Z)⟩\text{MHLA}_{\Theta}(Z)[a]=\langle p_{a}(\Theta),\mathcal{H}(Z)\rangle (42)
pa​(Θ){j,k},{ℓ}:=∑h∈[H](Vh,a​j​Qh,k​ℓ+Vh,a​k​Qh,j​ℓ)p_{a}(\Theta)_{\{j,k\},\{\ell\}}\vcentcolon=\sum_{h\in[H]}\left(V_{h,aj}Q_{h,k\ell}+V_{h,ak}Q_{h,j\ell}\right) (43)
pa​(Θ){j2}​{ℓ}:=∑h∈[H]Vh,a​j​Qh,j​ℓp_{a}(\Theta)_{\{j^{2}\}\{\ell\}}\vcentcolon=\sum_{h\in[H]}V_{h,aj}Q_{h,j\ell} (44)
ℋ(Z){j,k}​{ℓ}:=⟨zj:,zk:⟩zℓ​n\mathcal{H}(Z)_{\{j,k\}\{\ell\}}\vcentcolon=\langle z_{j:},z_{k:}\rangle z_{\ell n} (45)
ℋ(Z){j2}​{ℓ}:=∥zj:∥2zℓ​n\mathcal{H}(Z)_{\{j^{2}\}\{\ell\}}\vcentcolon=\|z_{j:}\|^{2}z_{\ell n} (46)
MHLAΘ​(Z)​[a]=∑{j,k}∈𝒮2d∑ℓ∈[d]pa​(Θ){j,k},{ℓ}​ℋ​(Z){j,k}​{ℓ}+∑j,ℓ∈[d]pa​(Θ){j2}​{ℓ}​ℋ​(Z){j2}​{ℓ}=⟨pa​(Θ),ℋ⁡(Z)⟩\text{MHLA}_{\Theta}(Z)[a]=\sum_{\{j,k\}\in\mathcal{S}^{d}_{2}}\sum_{\ell\in[d]}p_{a}(\Theta)_{\{j,k\},\{\ell\}}\mathcal{H}(Z)_{\{j,k\}\{\ell\}}+\sum_{j,\ell\in[d]}p_{a}(\Theta)_{\{j^{2}\}\{\ell\}}\mathcal{H}(Z)_{\{j^{2}\}\{\ell\}}\\ =\langle p_{a}(\Theta),\mathcal{H}(Z)\rangle (47)
𝔼[ℋb(Z){j,k}​{ℓ}ℋb(Z){j′,k′}​{ℓ′}]=1n𝔼[⟨zj:,zk:⟩⟨zj′:,zk′:⟩zℓ​bzℓ′​b]\mathbb{E}\left[\mathcal{H}_{b}(Z)_{\{j,k\}\{\ell\}}\mathcal{H}_{b}(Z)_{\{j^{\prime},k^{\prime}\}\{\ell^{\prime}\}}\right]=\frac{1}{n}\mathbb{E}\left[\langle z_{j:},z_{k:}\rangle\langle z_{j^{\prime}:},z_{k^{\prime}:}\rangle z_{\ell b}z_{\ell^{\prime}b}\right] (48)
𝔼[ℋb(Z){j2}​{ℓ}ℋb(Z){j′2}​{ℓ′}]=1n𝔼[(∥zj:∥2−nm2)(∥zj′:∥2−nm2)zℓ​b2]\mathbb{E}\left[\mathcal{H}_{b}(Z)_{\{j^{2}\}\{\ell\}}\mathcal{H}_{b}(Z)_{\{j^{\prime 2}\}\{\ell^{\prime}\}}\right]=\frac{1}{n}\mathbb{E}[(\|z_{j:}\|^{2}-nm_{2})(\|z_{j^{\prime}:}\|^{2}-nm_{2})z_{\ell b}^{2}] (49)

Lemma E.1 (General Certificate of Identifiability) .

Let dataset D={(Zi,yi)}i∈[N]D=\{(Z_{i},y_{i})\}_{i\in[N]} be a dataset realizable by Θ∈ΩH\Theta\in\Omega_{H}. Let p:={pa}a∈[d]p\vcentcolon=\{p_{a}\}_{a\in[d]} be a collection of polynomials pa:Ω→ℝψp_{a}:\Omega\rightarrow\mathbb{R}^{\psi} mapping the parameters Θ∈Ω\Theta\in\Omega to a feature space of fixed dimension ψ∈ℤ+\psi\in\mathbb{Z}^{+}. Let ℋ={ℋn}n=1∞\mathcal{H}=\{\mathcal{H}_{n}\}_{n=1}^{\infty} be a uniform family of polynomials such that ℋn:ℝd×n→ℝψ\mathcal{H}_{n}:\mathbb{R}^{d\times n}\rightarrow\mathbb{R}^{\psi}. Let pp and ℋ\mathcal{H} satisfy

for all Z∈ℝd×nZ\in\mathbb{R}^{d\times n} for all n∈[1,∞)n\in[1,\infty). Then if λmin​(𝔼D​[ℋ⁡(Z)​ℋ​(Z)T])>0\lambda_{\min}\left(\mathbb{E}_{D}\left[\mathcal{H}(Z)\mathcal{H}(Z)^{T}\right]\right)>0 , we have

for all empirical risk minimizers Θ,Θ′∈ΩERM\Theta,\Theta^{\prime}\in\Omega_{\text{ERM}}. That is, all empirical risk minimizers compute the same function.

Equations 36–37
MHLAΘ​(Z)​[a]=⟨pa​(Θ),ℋn​(Z)⟩\text{MHLA}_{\Theta}(Z)[a]=\langle p_{a}(\Theta),\mathcal{H}_{n}(Z)\rangle (36)
MHLAΘ=MHLAΘ′\text{MHLA}_{\Theta}=\text{MHLA}_{\Theta^{\prime}} (37)

Case 1: Pairs to Pairs, j ≠ k and j ′ ≠ k ′

The pair–pair case claims vanishing cross terms for distinct unordered row pairs and a positive diagonal proportional to m₂³. The displayed calculations express the intended block-diagonal argument; their independence and index-overlap conditions require care.

Equations 50–51
1n𝔼[⟨zj:,zk:⟩⟨zj′:,zk′:⟩zℓ​bzℓ′​b]=0\frac{1}{n}\mathbb{E}[\langle z_{j:},z_{k:}\rangle\langle z_{j^{\prime}:},z_{k^{\prime}:}\rangle z_{\ell b}z_{\ell^{\prime}b}]=0 (50)
1n𝔼[⟨zj:,zk:⟩2zℓ​b2]=m23\frac{1}{n}\mathbb{E}[\langle z_{j:},z_{k:}\rangle^{2}z_{\ell b}^{2}]=m_{2}^{3} (51)

Case 2: Singles to Singles, j = k and j ′ = k ′

The square–square case centers row norms by nm₂. The proposed diagonal factor is (m₄ − m₂²)m₂, positive under the lemma’s stated moment inequality, while different rows are treated as uncorrelated.

Equations 52–53
1n𝔼[(∥zj:∥2−nm2)(∥zj′:∥2−nm2)zℓ​b2]=0\frac{1}{n}\mathbb{E}\left[\left(\|z_{j:}\|^{2}-nm_{2}\right)\left(\|z_{j^{\prime}:}\|^{2}-nm_{2}\right)z_{\ell b}^{2}\right]=0 (52)
1n𝔼[(∥zj:∥2−nm2)2zℓ​b2]=1n((n2−n)m22+nm4−n2m22)m2=(m4−m22)m2\frac{1}{n}\mathbb{E}\left[\left(\|z_{j:}\|^{2}-nm_{2}\right)^{2}z_{\ell b}^{2}\right]=\frac{1}{n}\left((n^{2}-n)m_{2}^{2}+nm_{4}-n^{2}m_{2}^{2}\right)m_{2}=(m_{4}-m_{2}^{2})m_{2} (53)

Case 3: Singles to Pairs, j = k and j ′ ≠ k ′

The mixed case completes the proposed block decomposition. The stability proof then bounds output differences using coefficient differences, the minimum feature-moment eigenvalue, and a degree-six input-norm factor.

For two models whose squared training errors are each at most ε, their squared disagreement can generally be bounded by 4ε through the triangle inequality, rather than the proof’s unexplained ε. Lemma E.2 adds bounded label noise and bounded training inputs but supplies only a short proof sketch; its constants, concentration assumptions, and norm convention need verification before numerical use.

Equations 54–58
1n𝔼[(∥zj:∥2−nm2)⟨zj′:,zk′:⟩zℓ​b2]=0\frac{1}{n}\mathbb{E}\left[\left(\|z_{j:}\|^{2}-nm_{2}\right)\langle z_{j^{\prime}:},z_{k^{\prime}:}\rangle z_{\ell b}^{2}\right]=0 (54)
‖MHLAΘ​(Z)−MHLAΘ′​(Z)‖2=∑a∈[d](⟨pa​(Θ)−pa​(Θ′),ℋ⁡(Z)⟩)2≤∑a∈[d]‖pa​(Θ)−pa​(Θ′)‖2​‖ℋ⁡(Z)‖2≤(∑a∈[d]‖pa​(Θ)−pa​(Θ′)‖2)​‖Z‖F6≤ϵλm​i​n​(ΛD)​‖Z‖F6\|\text{MHLA}_{\Theta}(Z)-\text{MHLA}_{\Theta^{\prime}}(Z)\|^{2}=\sum_{a\in[d]}\left(\langle p_{a}(\Theta)-p_{a}(\Theta^{\prime}),\mathcal{H}(Z)\rangle\right)^{2}\\ \leq\sum_{a\in[d]}\|p_{a}(\Theta)-p_{a}(\Theta^{\prime})\|^{2}\|\mathcal{H}(Z)\|^{2}\\ \leq\left(\sum_{a\in[d]}\|p_{a}(\Theta)-p_{a}(\Theta^{\prime})\|^{2}\right)\|Z\|_{F}^{6}\\ \leq\frac{\epsilon}{\lambda_{min}\left(\Lambda_{D}\right)}\|Z\|_{F}^{6}\\ (55)
‖ℋ⁡(Z)‖2≤∑a,a′,a′′∈[d]​, ​b,b′,b′′∈[n]Za​b2​Za′​b′2​Za′′​b′′2≤‖Z‖F6\|\mathcal{H}(Z)\|^{2}\leq\sum_{a,a^{\prime},a^{\prime\prime}\in[d]\text{, }b,b^{\prime},b^{\prime\prime}\in[n]}Z_{ab}^{2}Z_{a^{\prime}b^{\prime}}^{2}Z_{a^{\prime\prime}b^{\prime\prime}}^{2}\leq\|Z\|_{F}^{6} (56)
λm​i​n​(ΛD)​∑a∈[d]‖pa​(Θ)−pa​(Θ′)‖2≤∑a∈[d](⟨pa​(Θ)−pa​(Θ′),ℋ⁡(Z)⟩)2≤ϵ\lambda_{min}(\Lambda_{D})\sum_{a\in[d]}\|p_{a}(\Theta)-p_{a}(\Theta^{\prime})\|^{2}\leq\sum_{a\in[d]}\left(\langle p_{a}(\Theta)-p_{a}(\Theta^{\prime}),\mathcal{H}(Z)\rangle\right)^{2}\leq\epsilon (57)
∑a∈[d]‖pa​(Θ)−pa​(Θ′)‖2≤ϵλm​i​n​(ΛD)\sum_{a\in[d]}\|p_{a}(\Theta)-p_{a}(\Theta^{\prime})\|^{2}\leq\frac{\epsilon}{\lambda_{min}(\Lambda_{D})} (58)

Lemma E.2 (Identifiability with Error and Noise in Realizability) .

Let D={(Zi,yi)}i∈[N]D=\{(Z_{i},y_{i})\}_{i\in[N]} be a dataset such that yi=MHLA​(Zi)+ζiy_{i}=\text{MHLA}(Z_{i})+\zeta_{i} for ζi\zeta_{i} i.i.d and bounded. Let Ωϵ−ERM\Omega_{\epsilon-\text{ERM}} be the set of ϵ\epsilon-approximate empirical risk minimizers.

Let maxi∈[N]⁡‖Zi‖F≤B\max_{i\in[N]}\|Z_{i}\|_{F}\leq B . Then we have for any Θ,Θ′∈Ωϵ−ERM\Theta,\Theta^{\prime}\in\Omega_{\epsilon-\text{ERM}} that for all inputs Z∈ℝd×nZ\in\mathbb{R}^{d\times n}

Equations 59–60
Ωϵ−ERM={Θ∈ΩH|𝔼(Zi,yi)∈D​[(MHLAΘ​(Zi)−yi)2]≤ϵ}.\Omega_{\epsilon-\text{ERM}}=\left\{\Theta\in\Omega_{H}~\big|~\mathbb{E}_{(Z_{i},y_{i})\in D}\left[\left(\text{MHLA}_{\Theta}(Z_{i})-y_{i}\right)^{2}\right]\leq\epsilon\right\}. (59)
‖MHLAΘ​(Z)−MHLAΘ′​(Z)‖≤ϵ−1N​∑i∈[N]ζi2+B2N​log⁡(δ−1)λmin​(ΛD)​‖Z‖F6.\|\text{MHLA}_{\Theta}(Z)-\text{MHLA}_{\Theta^{\prime}}(Z)\|\leq\frac{\epsilon-\frac{1}{N}\sum_{i\in[N]}\zeta_{i}^{2}+\frac{B^{2}}{N}\log(\delta^{-1})}{\lambda_{\min}\left(\Lambda_{D}\right)}\|Z\|_{F}^{6}. (60)

Appendix F Programs Expressible as Fixed Depth Linear Transformer

Tokens represent objects with several finite-valued attributes. Each head performs a linear transformation of a query attribute, looks up a matching key, and maps the retrieved value into an output attribute. Orthogonal encodings implement arbitrary finite lookup maps as matrices.

Algorithm 3 gives the generic program form. Multiple matching keys would sum values, so the simulator’s layout avoids unwanted collisions. Several heads update different attributes in parallel; additional generated tokens provide sequential operations.

Algorithm 3 Autoregressive MHLA Program
1:  Instantiate N instances OBJ = {obj(i)}i∈[N]\{\text{obj(i)}\}_{i\in[N]} of Class with set of Attributes {Attr1,Attr2,…,Attrk}\{\text{Attr}_{1},\text{Attr}_{2},...,\text{Attr}_{k}\}
2:  Each Attribute takes on values in an alphabet ΣAttribute\Sigma_{\text{Attribute}}
3:  for iter ∈\in [T] do
4:   Let obj​[r]\text{obj}[r] be the rightmost token
5:   Let obj​[r+1]\text{obj}[r+1] be a new token initialized with positional embedding obj​[r+1].pos=r+1\text{obj}[r+1].\text{pos}=r+1
6:   for each {AttrSource, AttrDest} in {Pairs of Attributes in Class} do
7:    #AttrKey and AttrValue can be any pair of Attributes (and can be distinct from VarSource/VarDest)
8:    LookupDict={{obj.AttrKey: obj.AttrValue} for obj in OBJ}\text{LookupDict}=\{\{\text{obj.AttrKey: obj.AttrValue}\}\text{ for obj in OBJ}\}
9:    # if multiple objects have same obj.AttrKey then returns sum of obj.AttrValues which we aim to avoid
10:    Let ℬQ\mathcal{B}_{Q} be any function from ΣAttrSource\Sigma_{\text{AttrSource}} to ΣAttrKey\Sigma_{\text{AttrKey}}
11:    Let ℬV\mathcal{B}_{V} be any function from ΣAttrValue\Sigma_{\text{AttrValue}} to ΣAttrDest\Sigma_{\text{AttrDest}}
12:    Let query = ℬQ\mathcal{B}_{Q}(obj[r].AttrSource)
13:    if query in LookupDict.Keys then
14:      obj[r+1].AttrDest = ℬV\mathcal{B}_{V}(LookupDict(query))
15:    end if
16:   end for
17:   Append next token OBJ={obj​[i]}i∈[r]∪{obj​[r+1]}\text{OBJ}=\{\text{obj}[i]\}_{i\in[r]}\cup\{\text{obj}[r+1]\}
18:   r=r+1r=r+1
19:  end for

Lemma F.1 .

For any program 𝒫\mathcal{P} written in the form of algorithm 6, there exists corresponding MHLA parameters Θ∈ΩH\Theta\in\Omega_{H} such that MHLAΘ​(Z)=𝒫​(Z)\text{MHLA}_{\Theta}(Z)=\mathcal{P}(Z).

F.1 Construction of UTM

The embedding stores the transition table separately from the word, positional codes, and current state. Disjoint coordinate blocks distinguish intermediate stages; shared coordinates are used deliberately for lookup tables. Each simulated tape symbol consumes a small block of generated tokens.

Algorithms 6–7 combine neighboring tape cells with a transition-table lookup, then handle locations left of, at, and right of the head. The original pseudocode is retained, including Algorithm 7’s repeated “move == L” conditions at lines 13 and 17; it should be checked as a construction sketch before implementation.

Definition F.2 (Embedding) .

Let MM be a TM over state space QQ, alphabet AA, transition function δ\delta. Then

Let p1,p2,…,pδp_{1},p_{2},...,p_{\delta} be "positional encodings" that assign unique id’s for every letter in the word xx.

Then we define Embedding(M,x) to be

Equations 61–63
Embedding​(M)=[q0q1⋯qk#a0a0⋯a0#δ⁡(q0,a0)δ⁡(q1,a0)⋯δ⁡(qk,a0)#a1a1⋯a1#δ⁡(q0,a1)δ⁡(q1,a1)⋯δ⁡(qk,a1)#]\text{Embedding}(M)=\begin{bmatrix}q_{0}&q_{1}&\cdots&q_{k}&\#\\ a_{0}&a_{0}&\cdots&a_{0}&\#\\ \delta(q_{0},a_{0})&\delta(q_{1},a_{0})&\cdots&\delta(q_{k},a_{0})&\#\\ a_{1}&a_{1}&\cdots&a_{1}&\#\\ \delta(q_{0},a_{1})&\delta(q_{1},a_{1})&\cdots&\delta(q_{k},a_{1})&\#\\ \end{bmatrix} (61)
Embedding​(x)=[p1p2⋯pipi+1⋯pδ#x1x2⋯xixi+1⋯xδ#00⋯q0⋯0#]\text{Embedding}(x)=\begin{bmatrix}p_{1}&p_{2}&\cdots&p_{i}&p_{i+1}&\cdots&p_{\delta}&\#\\ x_{1}&x_{2}&\cdots&x_{i}&x_{i+1}&\cdots&x_{\delta}&\#\\ 0&0&\cdots&q&0&\cdots&0&\#\end{bmatrix} (62)
Embedding(M,x)=[Embedding​(M)00Embedding​(x)]\text{Embedding(M,x)}=\begin{bmatrix}\text{Embedding}(M)&0\\ 0&\text{Embedding}(x)\end{bmatrix} (63)

Lookup:

Lookup uses identity query/value transformations to retrieve the value associated with the current token’s selected attribute and write it into the next token.

Copy:

Copy is a lookup by positional code. A fixed permutation shifts the query to an earlier position, allowing an attribute at a prescribed offset to be copied forward.

If-Then:

Conditional updates are compiled into a temporary table: successive dummy tokens store candidate condition/value pairs, then a lookup selects the matching output. Algorithms 4–5 retain the ordinary and attention-program versions; Algorithms 6–7 retain the simulator’s full instruction and branch listings.

Algorithm 4 If-Then Program
1:  # If attribute x is equal to any of a1,a2,…,aka_{1},a_{2},...,a_{k} then set attribute x′x^{\prime} to b1,b2,…,bkb_{1},b_{2},...,b_{k} respectively
2:  if Token.x == Token.a1a_{1}: then
3:   NextToken.x’ = Token.b1b_{1}
4:  end if
5:  if Token.x == Token.a2a_{2}: then
6:   NextToken.x’ = Token.b2b_{2}
7:  end if
8:  …\ldots
9:  if Token.x == Token.aka_{k}: then
10:   NextToken.x’ = Token.bkb_{k}
11:  end if
Algorithm 5 MHLA If-Then Program
1:  # If attribute x is equal to any of a1,a2,…,aka_{1},a_{2},...,a_{k} then set attribute x′x^{\prime} to b1,b2,…,bkb_{1},b_{2},...,b_{k} respectively
2:  token[r+1].s0 = token[r].a1a_{1}
3:  token[r+1].s1 = token[r].b1b_{1}
4:  NEXT TOKEN r=r+1r=r+1
5:  token[r+1].s0 = token[r].a2a_{2}
6:  token[r+1].s1 = token[r].b2b_{2}
7:  …\ldots
8:  NEXT TOKEN r=r+1r=r+1
9:  token[r+1].s0 = token[r].aka_{k}
10:  token[r+1].s1 = token[r].bkb_{k}
11:  NEXT TOKEN r=r+1r=r+1
12:  Table T = {obj[i].s0 : obj[i].s1}i∈[r,r−k+1]\{\text{obj[i].s0 : obj[i].s1}\}_{i\in[r,r-k+1]}
13:  token[r+1].x’ = Lookup(T,token[r].x)
Algorithm 6 Simplified Instruction Set MHLA Program for UTM for a single block
1:  # Initialize Lookup Tables for TM M and tape T1T_{1}
2:  # δ⁡(q,a)=[next-state, next-letter, next-move]\delta(q,a)=[\text{next-state, next-letter, next-move}]
3:  M = {q:[a0,δ⁡(q,a0),a1,δ⁡(q,a1)]}q∈Q\{q:[a_{0},\delta(q,a_{0}),a_{1},\delta(q,a_{1})]\}_{q\in Q}
4:  T1T_{1} = {token[i].PosEncoding: token[i].Letter}i∈[r]\{\text{token[i].PosEncoding: token[i].Letter}\}_{i\in[r]}
5:  # Begin Loading Information from M and previous tokens on tape
6:  # First copy letter/state from token -N-1 positions away
7:  # Attribute s(-1) = {letter, state} where state can be equal to None
8:  NextToken.s(-1) = Copy(Token[-N-1].s0)
9:  # Second copy letter/state from token -N positions away
10:  # Attribute s0 = {letter, state} where state can be equal to None
11:  NextToken.s0 = Copy(Token[-N].s0)
12:  # Third copy letter/state from token -N+1 positions away
13:  # Attribute s1 = {letter, state} where state can be equal to None
14:  NextToken.s1 = Copy(Token[-N+1].s0)
15:  NEXT TOKEN r=r+1r=r+1
16:  #Split into three branches to handle left, head, and right positions relative to head
17:  RUN BRANCH 1 (Token is Left of Head Position) See algorithm 7
18:  RUN BRANCH 2 (Token is at Head Position) See algorithm 7
19:  RUN BRANCH 3 (Token is Right of Head Position) See algorithm 7
Algorithm 7 Branches to handle cases Left of Head, Head, and Right of Head
1:  #Split into three branches to handle left, head, and right positions relative to head
2:  BRANCH 1 (Token is Left of Head Position)
3:  # we have loaded a state q into s1 (if left of head) and next we load [a0,δ⁡(q,a0),a1,δ⁡(q,a1)][a_{0},\delta(q,a_{0}),a_{1},\delta(q,a_{1})] into s2
4:  NextToken.s2 = Lookup(M,Token.s1.state)
5:  NEXT TOKEN r=r+3r=r+3
6:  if Token.s2.letter==a0\text{Token.s2.letter}==a_{0} then
7:   NextToken.s3 = δ⁡(q,a0)\delta(q,a_{0}) = [q’,w’,L/R]
8:  end if
9:  if Token.s2.letter==a1\text{Token.s2.letter}==a_{1} then
10:   NextToken.s3 = δ⁡(q,a1)\delta(q,a_{1}) = [q’,w’,L/R]
11:  end if
12:  NEXT TOKEN r = r+3
13:  if Token.s3.move == L then
14:   NextToken.return-letter = Token.s0.letter
15:   NextToken.return-state = q’
16:  end if
17:  if Token.s3.move == L then
18:   NextToken.return-letter = Token.s0.letter
19:   NextToken.return-state = None
20:  end if
21:  BRANCH 2 (Token is at Head Position)
22:  # we have loaded a state q into s0 and next we load [a0,δ⁡(q,a0),a1,δ⁡(q,a1)][a_{0},\delta(q,a_{0}),a_{1},\delta(q,a_{1})] into s2
23:  NextToken.s2 = Lookup(M,Token.s0.state)
24:  NEXT TOKEN r = r+3
25:  if Token.s2.letter==a0\text{Token.s2.letter}==a_{0} then
26:   NextToken.s3 = δ⁡(q,a0)\delta(q,a_{0}) = [q’,w’,L/R]
27:  end if
28:  if Token.s2.letter==a1\text{Token.s2.letter}==a_{1} then
29:   NextToken.s3 = δ⁡(q,a1)\delta(q,a_{1}) = [q’,w’,L/R]
30:  end if
31:  NEXT TOKEN r = r+3
32:  if Token.s3.next-letter is not None then
33:   NextToken.return-letter = Token.s3.next-letter
34:   NextToken.return-state = None
35:  end if
36:  BRANCH 3 (Token is Right of Head Position)
37:  # we have loaded a state q into s(-1) and next we load [a0,δ⁡(q,a0),a1,δ⁡(q,a1)][a_{0},\delta(q,a_{0}),a_{1},\delta(q,a_{1})] into s2
38:  NextToken.s2 = Lookup(M,Token.s(-1).state)
39:  NEXT TOKEN r = r+3
40:  if Token.s2.letter==a0\text{Token.s2.letter}==a_{0} then
41:   NextToken.s3 = δ⁡(q,a0)\delta(q,a_{0}) = [q’,w’,L/R]
42:  end if
43:  if Token.s2.letter==a1\text{Token.s2.letter}==a_{1} then
44:   NextToken.s3 = δ⁡(q,a1)\delta(q,a_{1}) = [q’,w’,L/R]
45:  end if
46:  NEXT TOKEN r = r+3
47:  if Token.s3.move == L then
48:   NextToken.return-letter = Token.s0.letter
49:   NextToken.return-state = None
50:  end if
51:  if Token.s3.move == R then
52:   NextToken.return-letter = Token.s0.letter
53:   NextToken.return-state = Token.s3.next-state
54:  end if

F.2 Proofs For Learning UTM

The in-distribution argument converts per-step prediction error to a probability of an incorrect rounded token, then unions over a bounded trace. Increasing the sample budget to reduce each step’s error yields the stated history-level guarantee.

For certified data, the smallest eigenvalue bounds coefficient disagreement on every input within the prescribed size budget. Fitting to sufficiently small error then permits consistent token decoding across that budget. These conclusions inherit the quantitative stability and generalization qualifications discussed above; the certificate does not itself supply representative traces.

Equations 65–69
𝔼(Z,y)∈𝒟​[(MHLAΘ^​(Z)−y)2]−minΘ∈ΩH⁡𝔼(Z,y)∈𝒟​[(MHLAΘ​(Z)−y)2]≤ϵ\mathbb{E}_{(Z,y)\in\mathcal{D}}\left[\left(\text{MHLA}_{\hat{\Theta}}(Z)-y\right)^{2}\right]-\min_{\Theta\in\Omega_{H}}\mathbb{E}_{(Z,y)\in\mathcal{D}}\left[\left(\text{MHLA}_{\Theta}(Z)-y\right)^{2}\right]\leq\epsilon (65)
Pr(M,x)∼𝒟[CHΘ^(M,x)≠CHΘ(M,x)]≤O(ϵΦ).\Pr_{(M,x)\sim\mathcal{D}}[\text{CH}_{\hat{\Theta}}(M,x)\neq\text{CH}_{\Theta}(M,x)]\leq O(\epsilon\Phi). (66)
Pr(M,x)∼𝒟[CHΘ^(M,x)c⁡(t)[:−kt]=xt]≥1−ϵ\Pr_{(M,x)\sim\mathcal{D}}\left[\text{CH}_{\hat{\Theta}}(M,x)^{c(t)}[:-k_{t}]=x^{t}\right]\geq 1-\epsilon (67)
‖MHLAΘ^​(Z)−MHLAΘ​(Z)‖≤ϵη​‖Z‖F6.\|\text{MHLA}_{\hat{\Theta}}(Z)-\text{MHLA}_{\Theta}(Z)\|\leq\frac{\epsilon}{\eta}\|Z\|_{F}^{6}. (68)
Pr(M,x)∼𝒟[CHΘ^(M,x)c⁡(t)[:−kt]=xt]≥1−ϵ\Pr_{(M,x)\sim\mathcal{D}}\left[\text{CH}_{\hat{\Theta}}(M,x)^{c(t)}[:-k_{t}]=x^{t}\right]\geq 1-\epsilon (69)

Corollary F.3 .

In particular, for sample complexity N=poly​(d,ϵ−1,log⁡(δ−1),n,t)N=\text{poly}(d,\epsilon^{-1},\log(\delta^{-1}),n,t), by Lemma B.1, we have with probability 1−δ1-\delta over the randomness in the data that the probability that the c⁡(t)c(t) step of the computation history of MHLAΘ^\text{MHLA}_{\hat{\Theta}} is equal to xtx_{t} is

where c⁡(t)≤O⁡((n+t)​t)c(t)\leq O((n+t)t). That is, the computation history of the MHLA returned by algorithm 1 is equal to the computation history of MM on xx.

Equation 64
Pr(M,x)∼𝒟[CHΘ^(M,x)c⁡(t)[:−kt]=xt]≥1−ϵ,\Pr\nolimits_{(M,x)\sim\mathcal{D}}\left[\text{CH}_{\hat{\Theta}}(M,x)^{c(t)}[:-k_{t}]=x^{t}\right]\geq 1-\epsilon, (64)

Appendix G Additional Definitions

Orthogonal token embeddings and nearest-token rounding define the symbolic interpretation of vector predictions. Algorithm 8 retains the complete cubic-feature extraction routine used by the regression algorithm.

Algorithm 8 Extract Features
1:  Input: Data D:={Zi}i∈[N]D\vcentcolon=\{Z_{i}\}_{i\in[N]} for Zi∈ℝd×niZ_{i}\in\mathbb{R}^{d\times n_{i}} and yi∈ℝdy_{i}\in\mathbb{R}^{d}
2:  for Zi∈DZ_{i}\in D do
3:   Let z1,z2,…​zdz_{1},z_{2},...z_{d} be the rows of ZiZ_{i} and let za,bz_{a,b} be the (a,b)(a,b) entry of ZiZ_{i}
4:   for j∈[d]j\in[d] do
5:    for k∈[d]k\in[d] do
6:      for ℓ∈[d]\ell\in[d] do
7:       Let 𝒳i∈ℝd×d2\mathcal{X}_{i}\in\mathbb{R}^{d\times d^{2}} be defined as follows
8:       𝒳i[j,kd+ℓ]=[⟨zj:,zk:⟩zℓ​ni]\mathcal{X}_{i}[j,kd+\ell]=\left[\langle z_{j:},z_{k:}\rangle z_{\ell n_{i}}\right]
9:      end for
10:    end for
11:   end for
12:  end for
13:  Return: {𝒳i}i∈[N]\{\mathcal{X}_{i}\}_{i\in[N]} such that
Equation 70
𝒳i:=[⟨z1:,z1:⟩z1​ni⟨z1:,z2:⟩z1​ni⋯⟨z1:,zd:⟩z1​ni⋯⟨z1:,zd:⟩zd​ni⟨z2:,z1:⟩z1​ni⟨z2:,z2:⟩z1​ni⋯⟨z2:,zd:⟩z1​ni⋯⟨z2:,zd:⟩zd​ni⋱⋱⟨zd:,z1:⟩z1​ni⟨zd:,z2:⟩z1​ni⋯⟨zd:,zd:⟩z1​ni⋯⟨zd:,zd:⟩zd​ni].\mathcal{X}_{i}\vcentcolon=\begin{bmatrix}\langle z_{1:},z_{1:}\rangle z_{1n_{i}}&\langle z_{1:},z_{2:}\rangle z_{1n_{i}}&\cdots&\langle z_{1:},z_{d:}\rangle z_{1n_{i}}&\cdots&\langle z_{1:},z_{d:}\rangle z_{dn_{i}}\\ \langle z_{2:},z_{1:}\rangle z_{1n_{i}}&\langle z_{2:},z_{2:}\rangle z_{1n_{i}}&\cdots&\langle z_{2:},z_{d:}\rangle z_{1n_{i}}&\cdots&\langle z_{2:},z_{d:}\rangle z_{dn_{i}}\\ \vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\ \langle z_{d:},z_{1:}\rangle z_{1n_{i}}&\langle z_{d:},z_{2:}\rangle z_{1n_{i}}&\cdots&\langle z_{d:},z_{d:}\rangle z_{1n_{i}}&\cdots&\langle z_{d:},z_{d:}\rangle z_{dn_{i}}\\ \end{bmatrix}~. (70)

Definition G.1 (Orthogonal Embeddings) .

Let Embed be a function Embed:Σ→ℝ|Σ|\text{Embed}:\Sigma\rightarrow\mathbb{R}^{|\Sigma|}. Let Σ\Sigma be an alphabet and let e1,e2,…,e|Σ|∈ℝ|Σ|e_{1},e_{2},...,e_{|\Sigma|}\in\mathbb{R}^{|\Sigma|} be a basis of orthogonal unit vectors. Then for each letter aa in an alphabet Σ\Sigma, we define Embed​(a)=ea\text{Embed}(a)=e_{a} where we associate a different unit vector to each letter.

Definition G.2 (Rounding) .

For any vector v=(v1,v2,…,vd)∈ℝdv=(v_{1},v_{2},...,v_{d})\in\mathbb{R}^{d}, let Round​(v)=ej\text{Round}(v)=e_{j} for j=arg​maxi∈[d]⁡⟨v,ei⟩j=\argmax_{i\in[d]}\langle v,e_{i}\rangle. Since we use orthogonal unit vectors for token embeddings we will refer to Round​(v)\text{Round}(v) as a token. We will often refer to a matrix Z∈ℝd×nZ\in\mathbb{R}^{d\times n} as being equivalent to a series of nn tokens a1,a2,…,ana_{1},a_{2},...,a_{n} to mean Round(Z[:,i])=ai\text{Round}(Z[:,i])=a_{i} for all i∈[n]i\in[n].

G.1 Training details of attention networks

The retained search table varies input dimension 2–16, heads 1–16, depth 1–4, learning rate 0.01/0.001, and batch size 32/64. The prose names Adam while the table specifies AdamW. This distinction is preserved instead of treating the experimental optimizer as uniquely specified.

hyper parameter search space
dd input dimension [2, 4, 8, 16]
mm number of heads [1, 2, 4, 8, 16]
nn number of layers [1, 2, 4]
learning rate [0.01, 0.001]
batch size [32, 64]
optimizer AdamW Loshchilov and Hutter [2018]

G.2 Training details in DFA Execution

The finite-automaton experiment uses a Llama-style Transformer with four layers, sixteen heads, hidden dimension 2,048, learning rate 0.00025, and 100 epochs. Training-set sizes range from 16 to 65,536 examples, with intermediate settings listed in the source; the complete hyperparameter table is retained.

EquationN∈{16,32,64,128,256,512,1024,2048,4096,6144,8192,12290,16384,20480,32768,65536}N\in\{16,32,64,128,256,512,1024,2048,4096,6144,8192,12290,16384,20480,32768,65536\}
hyper parameter search space
dd input dimension [2048]
mm number of heads [16]
nn number of layers [4]
learning rate [0.00025]
epochs 100
optimizer AdamW Loshchilov and Hutter [2018]

G.3 Additional Experiments

Figure 3 repeats the d = 4, N = 2,048 synthetic attention comparison, showing the error curves against training epoch. Its three-run uncertainty and the convex solver’s numerical floor should be kept in view when comparing convergence.

Original figure
(a) N=2048,d=4N=2048,d=4
Figure 3: Performance comparison of multi-head, multi-layer linear attention models and the original Transformer model (denoted as full). We trained using SGD on synthetic data generated from a single-layer linear attention model for varying training set sizes (NN) and input dimensions (dd), number of heads mm, and number of layers nn. We present mean squared error of the predictions w.r.t number of training epochs. Results demonstrate that multi-head architectures converge faster on different input dimensions and match the performance of our algorithm 1 (convex algorithm). Increasing the number of layers or incorporating multilayer perceptrons (MLPs) and layer normalization did not yield consistent improvements. Shading indicates the standard error over three different runs.

G.4 Learning the Computation History of Deterministic Finite Automata

The task supplies an explicit finite-automaton transition table and input word, and asks for the visited-state history. It tests executing a described automaton, rather than inferring an unknown transition system solely from examples. Although the introduction to this experiment mentions MHLA, its reported model is the conventional four-layer Transformer described in Section G.2.

Original figure
Figure 4: Data requirement for universal DFA simulation: We train a fixed sized Transformer (4-layers, 16 heads and 2048 hidden dimensions) to simulate a DFA given a transition table and input word. The vertical axis shows the number of tokens (expressed as word length LL times the number of examples QQ) required to obtain 99% next token accuracy.

Dataset

Each transition is encoded by a parenthesized state–symbol–next-state triplet. The model receives all transitions and the word, then predicts the history autoregressively with cross-entropy loss. The transition-table description uses five tokens per state/symbol pair, including parentheses.

Equation
(si,w,sj),…,∀si∈𝒬,w∈Σ∈δ⏟DFA transition function​∣w0​w1​…​wL⏟word∣​(s0​w0​s1),(s1​w1​s2),…,(sL−1​wL​sL)⏟computation history\underbrace{(s_{i},w,s_{j}),\dots,\forall_{s_{i}\in\mathcal{Q},w\in\Sigma}\in\delta}_{\text{DFA transition function}}\mid\underbrace{w_{0}w_{1}\dots w_{L}}_{\text{word}}\mid\underbrace{(s^{0}w_{0}s^{1}),(s^{1}w_{1}s^{2}),\dots,(s^{L-1}w_{L}s^{L})}_{\text{computation history}}

Results

Figure 4 varies states, word length, or alphabet size while fixing the other two at four. It reports the smallest training-token budget reaching 99% next-token accuracy. The curves are suggestive of subexponential scaling over the tested range; they neither prove polynomial scaling nor establish 99% accuracy for complete histories.

Concept demonstration

Open image ↗