In-Context Algorithm Emulation in Fixed-Weight Transformers
Authors: Jerry Yao-Chieh Hu
Hude Liu
Jennifer Yuntong Zhang
Han Liu
Venue: ICLR 2026 Poster (2026)
Keywords: In-Context Learning
Attention Mechanism
In-Context Gradient Descent
Transformer
Universal Approximation
Primary area: foundation or frontier models, including LLMs
TL;DR: We prove that a minimal Transformer with frozen weights emulates a broad class of algorithms by in-context prompting

Abstract: We prove that a minimal Transformer with frozen weights emulates a broad class of algorithms by in-context prompting. 
We formalize two modes of in-context algorithm emulation.
In the *task-specific mode*, for any continuously differentiable function $f: \mathbb{R} \to \mathbb{R}$, we construct a single-head softmax attention layer whose forward pass reproduces functions of the form $f(w^\top x - y)$ to arbitrary precision.
This general template subsumes many popular machine learning algorithms (e.g., gradient descent, linear regression, ridge regression).
In the *prompt-programmable mode*, we prove universality: 
a single fixed-weight two-layer softmax attention module emulates all algorithms from the task-specific class (i.e., each implementable by a single softmax attention) via only prompting.
Our key idea is to construct prompts that encode an algorithm’s parameters into token representations, creating sharp dot-product gaps that force the softmax attention to follow the intended computation.
This construction requires no feed-forward layers and no parameter updates. 
All adaptation happens through the
prompt alone. 
Numerical results corroborate our theory.
These findings forge a direct link between in-context learning and algorithmic emulation, and offer a simple mechanism for large Transformers to serve as prompt-programmable interpreters of algorithms. 
They illuminate how GPT-style foundation models may swap algorithms via prompts alone, and establish a form of algorithmic universality in modern Transformer models.

Published as a conference paper at ICLR 2026
IN-CONTEXT ALGORITHM FIXED-WEIGHT TRANSFORMERS
EMULATION
IN
Jerry Yao-Chich Hult
Hude Liu"
Jennifer Yuntong Zhang Han Liu
Northwestern University
Ensemble Al
Univeesiity of Toronto
jhulu. northwesetn. edu, hndeliiu2280@mail.ccom
seniferyt..hanggaeee utwronto..coom ca. hanlin@horttheestern..c
ABSTRACT
We prove that minimal Transformer with frozen weights emulates a broad class of algorithms by in-context prompting. We formalize two modes of in-context algorithm emulation. In the task-specific mode, for any continuously differentiable function f: TR IR, we construct single-head softmax attention layer whose for- ward pass reproduces functions of the form f(w x x-y) y) to arbitrary precision. This general template subsumes many popular machine learning algorithms (e.g., gradi- ent descent, linear regression, ridge regression). In the peoppt-programmaiiin mode, we prove universality: single exed-weight two-layer softmax attention module emulates all algorithms from the task task-specific class (i.e., each implementable by a single softmax attention) via only prompting. Our key idea is to construct prompts that encode algorithm's 's parameters into token representations, creating sharp dot-product gaps that force the softmax attention to follow the intended computa- tion. This construction requires no feed-forward layers and parameter updates. All adaptation happens through the prompt alone. Numerical results corroborate our theory. These findings forge direct link between in-context learning and algo- rithmic emulation, and offer a simple mechanism for large Transformers to serve as prompt-programman. interpreters of algorithms. They illuminate how GPT-style foundation models may swap algorithms via prompts alone, and establish a form of algorithmic universality in modern Transformer models.
INTRODUCTION
We show that minimal Transformer architecture with frozen weights is capable of emulating a broad class of algorithms through prompt design alone. This stylized problem setting isolates the core of in- context computation and provides an analytic lens on fundamental questions in Transformer models: How do fixed-weight models execute diverse tasks from context alone? How does a prompt turn into an algorithmic procedure? How do prompt-encoded parameters and query-key routing realize task identification and stepwise exccution? What minimal architectural ingredients suffice for general in- context capability? ? As foundation models rise to prominence in modern AI (Bommasani, 2021), these questions are central, since much of their practical utility comes from in-context learning (prompting) rather than explicit retraining (Brown et al., 2020; Liu et al., 2023). Against this backdrop. this work offers rigorous basis for in-context task learning' supplies a simple mechanism for Transformers act as
algorithm libraries, and shows how GPT-style models may swap algorithms via prompts alone, shedding light on their general-purpose capabilities.
Large Transformer models exhibit ability adapt to a task by conditioning examples instructions provided in the prompt without any gradient updates. This capability is known as In- Context Learning (ICL) (Min al., 2022; Brown et al., 2020). Prior work on Transformer in-context
Equual contribution. Part of the work done during JH's internship at Ensemble AI. Code is available at https://gituh..om//M www.///////M///A..... CEIICS-LABAL LAB/alloo_oo feau Latest version is at https://arxiv.orr/bbb/// 17550. We use "task" highlight algorithm-level adaptation (to diverse tasks), not pattern completion.

---

Published as a conference paper at ICLR 2026
Concatenated Input and Weights
Gradient Descent
Gradient Descent
Linear Regression
Linear Regression
Frozen Softmax Attention Layer
X
Lasso Regression
Lasso Regression
W*
Ridge Regression
Ridge Regression
Coonpt-Programmann In-Context Algorithm Emulation Overview. X denotes the data input, and W* encodes the instructions of the algorithm we aim to emulate. We show that even a 2-layer softmax attention module suffices to emulate broad class of algorithms by changing prompt (Theorem 4. i.e., the W" in the prompt. This separates algorithm information (in the prompt) from "model parameters" (frozen). By sending the algorithm-speet
Figure 1:
information (e.g.. instructions + data) to a fixed-weight model, the prompt acts as the program and the frozen transformer as the interpreter. This makes the "weights as dasa" mechanism explicit and is the core mechanism of promp--roggammabiily:: a minimal frozen Transformer serves as a modular interface in which swapping the prompt swaps the algorithm with no retraining.
learning falls into two strands. One trains models that learn in context for a specific function class (Garg et al., 2022; Akyürek et al.. 2023; Li et al., 2023; Ahn et al., 2023; Zhang et al., 2024). The other hand-engineers Transformers to enact particular algorithms with fixed weights (Bai et al., 2023; Von Oswald et al., 2023; Wu et al., 2025). In particular, Bai et al. (2023) demonstrate that task-specific attention layers attention mechanisms with weights designed for given task imppleent variety of algorithms without gradient updates. For example, a single Transformer with fixed, task- tailored weights achieves near-optimal performance on algorithms such as beast-squares/rigee/lass regressions, and gradient descent (Bai et al., 2023; Wu et al., 2025), PCA (He et al., 2025), time series regression (Wu al., 2026), Newton's 's method (Giannou et al., 2024; Fu al., 2024), Bayesian network (Cao et al., 2025), causal learning (Nichani et al., 2024; Edelman et al., 2024). These results suggest that Transformers are capable of in-context algorithm emulation. Yet these approaches retrain per task or hard-wire per algorithm. They do not give single fixed architecture that is prompt-rogrammabbl across many algorithms with explicit guarantees and minimal components.
To combat this, we advance this line of research by omitting the need for designing new Transformer block for every algorithm. We propose a frozen Transformer architecture to emulate a library of ceeention-basedd algorithms in context without weight updates. We achieve this by embedding citoortthmsppccfffe information into input prompts. Specifically, we formalize two emulation modes, and establish explicit guarantees and constructive minimal designs for both. In the task-specific mode (Section 3), a dedicated attention module with fixed weights (single- or multi-head) executes one algorithm in context. In the Transformer module with fixed weights re-programs itself through different prompts to execute multiple algorithms on the fly. These constructions yield universality and minimality results for in-context algorithm emulation. Specifically, we demonstrate minimalist model of internal algorithm swapping, where prompts serve as the context carrying algorithmic instructions.
mode (Section 4), by contrast, single
Contributions. We establish a new form of in-context learning universality for algorithm emulation. limited to inpentiooniimlleentablee algorithms. Our contributions are three-fold:
Task-Specite Emulation of f(w y).. A single-head, single-layer softmax attention with a linear map universally approximates functions of the form f(w x y)æ for any continuous f. with frozen weights and suitable prompt. This general result subsumes, for example, computing per-sample gradients and performing gradient descent updates (by choosing f as a loss derivative), well solving linear and ridge regression in one forward pass.
Constructive, Interpretable Prompt Design for Algorithm Emulation. We give an explicit prompt design strategy that encodes the target task's parameters and induces large query-key margins so softmax follows the intended pattern, furnishing an interpretable, verifiable recipe for prompt-programming fixed attention-only module.
A Simple Mechanism for Internal Algorithm Swapping of Transformer Models. Changing only the prompt-encoded algorithm weights swaps the algorithm executed by the fixed attention- only module, without retraining. Theory (finite libraries) and experiments (e.g., Lasso, ridge, linear regression) confirm high-fidelity swapping. Altogether, these results shed light the general- purpose capability of GPT-style Transformer models to select and swap internal routines via prompts (our formal proofs concern attention-only modules).
2

---

Published as a conference paper at ICLR 2026
In conclusion, show minimalist transformer architecture serve general purpose algorithm emulator in context through prompt design. Our findings contribute to a sharp theoretical foundation for viewing in-context learning as in-context algorithm emulation. They suggest that large pretrained softmax attention models (such as GPT-style Transformers) encode a library of algorithms, and swap among them based on prompts. This is achieved within unified attention architecture and without any parameter updates. We believe this perspective opens new opportunities for understanding the emulation ability of Transformer models.
Organization. Section 2 presents ideas we build on. Section 3 presents illustrative examples of learning statistical models in-context with task-specific attention heads. Section 4 presents our main results. Appendix A presents our proof strategies. Section 5 presents numerical validations.
Related Work. Due to page limits, we defer related work discussions Appendix B.
Notations. We denote the index set {I,...,4} } by [4]. We use lowercase letters for vectors and (m) IR" denotes the one-hot vector with in the j-th uppercase letters for matrices. The vector e position and 0 elsewhere. We write X E IRdxn for the input sequence, where d is the token dimension and n is the sequence length. We denote the number of attention heads by H. We use || lloo and I| 2l2 for the vector oc-norm and 2-norm, respectively.
2 PRELIMINARIES: ATTENTION, IN-CONTEXT LEARNING AND EMULATION
Softmax Attention. We define a multi-layer self-attention layer with softmax activation as follows.
Definition 2.1 (Softmax Attention Layer). For any input sequence X E [Rdx", the multi-head attention output (with H heads) is
H
Attam (X) = Σ w X Softmax (W X) w X) w gd.xno h=1
doxn
XXnu
where wi(h) wh(h) E RRdxxd, xd, wh() E RRdodd and with) Ruxxn for h [H]. We use Atin, to
denote single-head self-attention.
Following the notation of (Hu et al., 2025a), we pick non-identical dimensions for weight matrices WK, Wq. Wy for generality of our analysis?.
In the common K == WK Q = VVX.V Wy X notation, a single-layer softmax attention value vectors V {ui,..., .., Un }. and a query vector q,
takes set of key vectors K fk....., }.
to produce an output as a weighted sum of the value vectors. The weights on e; is Softmax(k: (k, q). emphasizing values whose keys are most similar the query. That is, the softmax attention uses the query as a cue to retrieve the most relevant information from the values (via their keys).
Linear Transformation Layer Linear(-). Throughout this paper, we sometimes compose atten- tion with an additional linear mapping for flexibility and simplicity of our proofs". Such a linear transformation layer uses learned parameters to increase expressivity in attention-basee constructions.
Definition 2.2. Let Z [21,.... 2n
d be the input sequence with columns 2; E Rd. We use Lincar: : dx n > Raxm (for some output length m) to denote column-wise linear affine maps. Each output column depends only on one input column, possibly with replication or an additive bias. We write Linear when dimensions are clear (input/output shapes chosen to match attention).
This layer is generic column-wise affine operator. It preprocesses the input to an attention mech- anism or post-processes its output. For example, Attn, Linear(Z) applies per-token affine projection (optionally with replication,
# n) before single-head attention. It subsumes the
"The right- moatt-uultipyinn (h) in Definition 2.1 is nonstandard. Yet, this it not an issue. One can recover standard left-multpplyng w-(h) (i.e.. Attu, (X) = Σn' V/ott/Sofaaxx(H VV) by including two extra attention layers following (Huu et al., 2025a. Section G & Remark E.2). All our results still hold. We adopt this convention for simplicity the proofs of Section Our Section 4 does not rely on the presence of Wx(h) We remark that, one can replace all Linear(:) throughout this paper following (Hu et al., 2025a, Remark E.1) via extra input preprocessing. We Linear(-) )) in this paper for simplicity of our proofs.
3

---

Published as a conference paper at ICLR 2026
practical per-token linear layer the special case with shared parameters and optional bias: Linear 2) = AZ + b1, E R2x* with A E RPxd b E R" and a the all-ones vector. In all cases, columns are processed independently (no cross-column mixing).
In-Context Learning Setup. In in-context learning, a fixed model (c.g., a pretrained Transformer) performs new task without parameter updates. Formally, the model aims to approximate unknown function f : X + Y given a few examples of f in the input prompt. At inference, we provide n exemplar pairs and query ziq. and concatenate them into a single sequence
X
T1
12
In yn
E (d+1))x and Lig Rddx1
(2.1)
V11
U2
Namely, the model receives (X, x.)) as the input prompt. The goal of ICL is for the model, given input prompt (X, Fy), to (i) infer f from the exemplars and (ii) apply it to zgg predict B/ f(z)). All the learning happens in the forward pass through the sequence X in an implicit fashion.
Task-Specific Attention. Task-specific attention uses fixed parameters carry out particular task when the prompt follows the required structure (see (Bai et al., 2023) for examples.)
Definition 2.3.
An attention layer is task task-specific if there exists a prompt family P such that, for any prompt P constructed from task parameters/data, the attention's 's forward pass implements the task's 's mapping on the query token(s), with no parameter change.
In particular, we embed the task's defining transformations (e.g. a linear mapping corresponding or part of f) into the attention weight matrices. Given a well-formed prompt of exemplar and query tokens, the attention selects and combines these tokens compute the correct output. Effectively, this allows attention layer to approximate diverse functions in context without weight updates.
Task-Specific vs. Trompt-Programmatiy In-Context Emulation. In-context algorithm emulation refers to executing an algorithm through a forward pass without weight updates. The core contribution of this work is formalize two in-context modes and study their scope:
Terminology:
Task-Specific In-Context Emulation: for each algorithm A. there exists attention module (possibly multi-head) whose forward pass on a well-formed prompt implements A on the query token(s). Each algorithm therefore requires its dedicated parameters.
Prompt-Programmale In-Context Emulation (via single frozen module): there exists single attention module with fixed weights Attn such that, for every AA in a target class, suitable prompt PA makes Alin* implement on the query token(s). All adaptation occurs through the prompt rather than through weight changes. Namely, one Atin" implements a library of algorithms.
These modes are complementary: the first reflects the conventional dedicated-moduu view (e.g.. (Bai et al., 2023)), while the second is stronger - one fixed-weight attention module emulates many algorithms via prompts (our contribution). In the remainder of the paper, Section 3 develops the task-specific case. Section establishes the prompt-programmbble case by showing how the latter subsumes the former via in-context simulation of task- mask-specific modules.
3
IN- IN-CONTEXT ALGORITHM EMULATION
We present multiple examples demonstrating how softmax attention modules mimic behaviors of various learning algorithms including gradient descent and linear regression. We begin with very general result showing that even a single-layer, single-head attention mechanism is universal approximator for a broad class of functions defined in the prompt.
In-Context Universal Approximation of f( x y)ι. Let x E ER.yER, E Rd, and let f: + R be continuously differentiable. We consider functions of the form f(w x y)z, where acts the residual w x y. This template is very general: many learning rules for linear models take this form, including many residual/gradient-styy wide family of esiiuall-driven updates central to machine learning. Thus, their in-context realization explains much of in-context learning. To this end, showing that attention is capable of emulating any continuous f(w x y) indicates powerful and general capability. It means the attention module
updates*. Hence f(w x - -y) subsumes a
*For example, f(t) = corresponds to the raw residual (w Tu 5)x. ʃ(-) V..l()) corresponds to per- sample gradients V (w,((w" x y)æ linear regression classification with loss e(-), and nonlinear f (sigmoid, step, etc.) corresponds perceptron updates or other eroorcorreccing rules.
4

---

Published as a conference paper at ICLR 2026
implements any continuous adjustment or mapping based the prediction w x and the label y. The next theorem shows how a single-head attention approximates [f(w" 24 20 arbitrarily well.
Theorem 3.1 (In-Context Emulation of f(wTx x - y)æ with Single-Head Attention), Let [Lming maxx be bounded interval containing all values of w x y. and let
X
22
In
((++))xn and W w
w E
Rax=
1/2
Vn
where 2; E R E R, and w E Rd is the coefficient vector. Define the input as:
21
T2
Zn
X E IR (2d+ 1)xn
2 =
V1
Vic
=
(3.1)
w
w
w
Assume max (I [Wl I B. For any continuously differentiable function f: IR - and any >> 0, there exists single-head attention Attn, with a linear layer Linear such that
||Attn, o Linear(Z) [[w" x1 v1)
sww In Un Jn)
2lx S for any e 0.
Proof. See Appendix D.1 for a detailed proof.
Theorem 3.1 establishes that even the simplest softmax attention alone suffices to encode any continuous function of the form f(w x y)æ by incorporating weights the prompt. A direct implication is by replacing f with the derivatives of differentiable loss function follows.
Example 1: In-Context Emulation of Single-Step GD. Building on Theorem 3.1, we show that softmax attention layer emulates Gradient Descent (GD) in-context. First, we replace the continuous function f-)) in Theorem 3.1 with Vf(-), where f R + IR is any differentiable loss function. We show that the softmax attention emulates per- sample gradients in context.
Corollary 3.1.1 (In-Context Emulation of Per-Sample Gradients). Let é: IR be differentiable and l' R T for its scalar derivative, (t)
(t). For w x y with E IR., R. E IRd. denote V=l(=) == (z). Set f(-) = (-) in Theorem 3.1. With = [X:W] W] as in (3.1), for any c >> 0, there exist a single-head attention Attn, (-) and linear map Linear(-) such that,
ll
Attn, Linear(Z)
1 (w x1 yn ................................ E' (w xn yo )aml olx0
= approximated per-sample gradient matrix
torget per-sample gradient matrix
Corollary 3.1.1 shows that single-layer single-head softmax attention with linear map approximates the individual (per-sample) gradient terms (f'(w x4 )., } Moreover, the layer outputs all per-sample gradient terms in parallel. Next, we extend Corollary 3.1.1 show that fixed attention layer implements the full gradient-descent update across all samples in-context.
Aggregating the per-sample gradients gives one GD step
(w)
Σ f(w T x. vi). (wn( = Σ 1=1
D:)
From Corollary 3.1.1, let G be the attention output and choose the readout u == 1 1n E R (equivalently, right-multiply by Wo u in Definition 2.1). Define the attention estimate of the average gradient as " = Gu. Then ğ Av g, and the target update w = w v, Feeding in the prompt and applying the same readout produces single d-dimensional update vector from the layer. The next corollary states the precise approximation guarantee.
Corollary 3.1.2 (In In-Context Emulation of a Single GD Step). Let é: R + R be differentiable
and define L, (w) 1 Dn l(w a single-heat head attention Attn, and linear map Linear such that, with Z = [X; W] as in (3.1), choosing the readout = 1 1,, (equivalently, right-multiply by Wo in Definition 2. 1), we have
v1). For any step size > 0 and any >> 0, there exist
WGD = w + (Attn, Linear (Z))u E dd and || - (w - VL (w)) 1oc S
w w-11
WD
5

---

Published as a conference paper at ICLR 2026
Proof. See Appendix D.2 for detailed proof.
Corollary 3. 3.1.2 shows that single-layer, single-head softmax attention with a linear map aggregates the per-sample gradients via the output projection. It produces a d-vector (GD that approximates the GD update wOD scaled per-sample gradient term. Averaging via the readout
v/V LVL((w) (w). Notably, each output column encodes copy of together with 1,, then recovers wCD up to e.
Example 2: In-Context Emulation of Multi-Step GD. We extend the single-step construction to show that multi-layer softmax attention network emulates multi-step gradient descent. In particular, an (L+1 llaye transformer approximates steps of gradient descent.
Stack (I++) copies of the single-head layer from Corollary 3.1.2. At layer (0 S < I.), the readout (1) 1n and the prompt Z = [X; W with W := GD ... (()) Define
(0) cn == w, and wan := Attn, o Linear( (1) (t.))
For the target iterates, set WGD = w and (1+1) Lemma D.4 and
GD = WGD V/ (w By Corollary 3.1.2,
|| Illo || 22, we arrive
(0) wCD lo S tc, tE [L].
Example 3: In-Context Emulation of Linear Regression. We now present the construction for squared loss. We show that a multi-layer softmax attention emulates linear regression in-context.
Corollary 3.1.3 (In-Context Emulation of Linear Regression). For any dataset {æ,, y/ } with H, E IRd, Yi E I and any > O, there exists a depth-L. stack of single-head attention layers [Attng]
L-1 linear maps [Linear'] 1/-0 and readout u E R² such that the iterates
linear = W Winear + (Attn', Linear' (Z'))
Ł= .,...,,--
with = (x; W4 and W = | Whnsaal as in (3.1) (for any fixed bounded w²), satisfy 1 Wlincar 00 S,
where Whincar := argmin 2n Σ (ww, .r)) y.)
Proof. See Appendix D.3 for detailed proof.
Example 4: In-Context Emulation of Ridge Regression. We add regularization term and show that multi-layer softmax attention emulates ridge regression with L2 penalty.
Corollary 3.1.4 (In-Context Emulation of Ridge Regression). For any input-output pair (I,, y.). where v; E gd 31 I, i [n]. and any there exists depth-L stack of single-head attention layers {Attn') Ji= linear maps (Linear' 1-1 and a readout u R such that the iterates
ridge = whidge (Attn', Linear' (Z'))
t= 0,..,, I. 1,
with zl = [X; W and W = | .... indgel as in (3.1) (for any fixed bounded w²), satisfy
|| | - Wridge a0 S
where Wridge ar argminwwer 2n ((m (I,, x;))
y1)2 + 2 w| with regularization term À 2
Proof. See Appendix D.4 for detailed proof.
So far our constructions Section 3 show that, given freedom choose parameters per algorithm, attention modules emulate gradient descent, linear regression, ridge regression, and related updates in context. These results establish the expressive power task-specific in-context emulation, akin to (Bai et al., 2023). In Section 4, we build this foundation and prove stronger universality: single frozen attention module Attn", via prompt programming, simulates all such aask-specific modules.
4 PROMPT-PROGRAMMEN
IN-CONTEXT ALGORITHM EMULATION
This section presents our main results: softmax attention is capable of (i) emulating task-specific attention heads in-context (Section 4.1), (ii) emulating statistical models in-context (Section 4.2), and (iii) emulating any network (with linear projections) in-context (Section 4.3). Unlike Section requiring separate task-specific module for each algorithm, here fix frozen module Attn and

---

Published as a conference paper at ICLR 2026
show that suitable prompts instruct it to emulate every algorithm in the target class. This establishes universality: one set of weights executes a library of algorithms through prompt programming.
4.1 IN-CONTEXT EMULATION ATTENTION
We first specify the input prompt with weight encoding.
Definition 4.1 (Vectorization). For any matrix X E Rddxd we define X voe(X) E Rdd, such that X (t- 1)d+3 = X5 for all i [d,] and j E [d].
Definition 4.2 (Input Prompt of In-Context Emulation of Attention). Let X E R be the input sequence, and let Wk. Wq. Wv 12dh xd the weight matrices the target attention head to be emulated. Define the vectorizations
W K == vec(Wx) E dRdd, Wo= vec(W)) E TR ddn. Wv == vee(Wv) E Rdddn
and w W Wo: Wy] E pedd, where w is concatenation WK Wa, g Wy. Finally, define the extended input Xp for in-context emulation of the attention head specified by WK. WQ, Wv
X
X, =
Win im In
with
Win =
w
1 w
2 w W
(n
1) w
E R xddxaxn
w
In other words, Win is block-row) and w E Rddn (in the second block-row), for j = 0, I,..., 1. Appending Win as additional rows X produces the prompt Xp that encodes the target weights.
block matrix whose j-th column consists of j. E Rdd, (in the first
Using this weight-encoding prompt, we now design two-layer attention mechanism to reproduces the effect of the target attention head in-context.
Theorem 4.1 (In-Context Emulation of Attention). Let X Rdxn be an input sequence, and let WK, Wo; Wv & Rdd xd be the weight matrices of the target attention head we wish to emulate in-context. Assume || [ oo |X I BKQv with BxQv 0. Then, for any e > 0, there exists a two-layer attention network - a multi-head attention layer Attnm followed by single-head attention layer Attn, such that
Attn, Attum (Xp)
Wv XSotmaaa ((Wx ( 1000 Se,
Emulator
Target
where Xp is the prompt defined in Definition 4.2.
Proof. See Appendix A.1 for the proof sketch and Appendix D.5 for detailed proof. Remark 4.1 (Permutation Equivariance). Our construction keeps the permutation equivariance of attention in its approximation. This means changing the order of columns in X results in an identical change the order of the columns in Attn o Attmn (Xp))
We now provide an alternative formulation of the above result. In this variant, single-head attention layer comes first, followed by multi-heat Melli-headdee layer with sequence- wise linear projections.
Theorem 4.2 IonCConeext Emulation of Attention; Alternative Formulation). Let X E RRdx be the input sequence, and let Wx. Wo, Wy Rexd be the weight matrices of the target attention. Assume B = || [W [ [W@lloo [W and || oo || X < BxQv for BKQV= 2 Then, for any 0, there exists a single-heat head attention layer Attn, followed by multi-head attention layer with linear projections such that
X
3n Atly. o Linear,(
WT W
Altng
))
Wv X Softmax, (WxxX)Too) Im S..
W
nxn
Proof. See Appendix A.2 for the proof sketch and Appendix D.6 for detailed proof.
Theorems 4.1 and 4.2 allow us to approximate arbitrary target one-layer attention using another two-layer attention. This construction requires no feed-forward layers and no parameter updates. All
7

---

Published as a conference paper at ICLR 2026
approximation happens through the prompt alone (by embedding target attention weights and input X into the prompt).
Target Attention Approximation for Algorithm Emulation. Theorems 1 and 4.2 present a general algorithm emulation result: a fixed-weight two-layer softmax attention mod- ule emulates all algorithms implementable by softmax attention via only prompting. For exam- ple, if we choose the input sequence X E Rdxn in Theorem 4.1 and Theorem 4.2 to be the Linear(Z) E 22(24++2)xxnf attentions implementing target algorithms of the f(w we achieve in-context emulation of the entire class of algorithms expressible as [(w] x y)x.
Discussion:
in Theorem 3.1, then we are able to approximate all one-layer
y) class: Corollaries 3.1. to 3.1.4. Thus,
This provides a constructive toy model of (i.e., one fixed-weight model for many tasks). Moreover, the construction is explicit, interpretable, and softmax-nativ A few remarks are in order.
transformer exhibiting, general-purpose ability
Remark 4.2 (Differences between Theorems 4.1 and 4.2). Theorems 4.1 and 4.2 both establish that a fixed multi-head attention network can approximate any given attention head in-context. We present two versions of the construction using different formulations and analytical techniques. In particular, Theorem 4.1 encodes the target algorithm into the token representations (keeping the sequence length fixed), whereas Theorem 4.2 achieves similar effect by encoding the weights as additional tokens in the input sequence (keeping each token's 's dimension fixed).
Remark 4.3. Our constructions may contain non-standard choices, including encoding information along the embedding dimension and using 3n parallel attention heads. We emphasize that the methods apply to approximate more realistic attention with far fewer hidden dimensions and number of heads in practice. Section 5 provides further details.
Remark 4.4 (Comparison with Prior Work). We remark that our results differ from prior work in three key aspects. First, we study the practical softmax attention rather than linear or ReLU attention (Bai et al., 2023; Von Oswald et al., 2023; Vladymyrov et al., 2024). Second, our results in Section 4 go beyond task-specific ICL and establish that fixed-weight Transformers are prompt-programmably (Bai et al., 2023; Wu et al., 2025; Li al., 2025). Third, our results are constructive, providing concrete emulation examples in contrast to prior prompting expressivity (Wang et al., 2023; Furuya results (Pérez et al., 2021: Giannou et al., 2023; Qiu al., 2024). The closest works to ours are (Bai et al., 2023; Giannou et al., 2023):
al., 2024) or muring-completnnes
Bai et al. (2023) show that Transformers can execute several standard algorithms in-context. How- ever, their constructions use ReL.Ubaased attention and require separate customized Transformer for each algorithm (i.e., task-specific). By contrast, we study Transformers with softmax attention, used in practice, and give constructive results. We show that single fixed attention module emulates a broad class of algorithms through prompt changes, with explicit mechanisms and guarantees. In particular, Section 3 establishes softmax-attention counterparts of their main results.
Giannou et al. (2023) are closest in spirit, since they also use one fixed model for many tasks. However, their goal is arbitrary program exccution via Turing completeness. They achieve this with much heavier 13-layer construction with looping. Our scope is narrower but cleaner: we show that a fixed two-layer attention-only module emulates any algorithm implementable by a softmax attention layer. The prompt supplies the program, and the model executes it. While our results are also extensible to looped setting (i.e., Corollary 1.2), our focus is different: we use an attention-onle FFN-free model and analyze its algorithmic universality constructively. This yields a more transparent mechanism for algorithm emulation and a sharper theory of internal algorithm execution in softmax Transformers.
4.2 IN-CONTEXT EMULATION OF STATISTICAL METHOSS
Theorem 4.2 shows that a frozen attention module approximates target attention head by embedding the head's weights into its input prompt. We now leverage this idea to emulate a broader class of algorithms. In essence, we replace the embedded target attention weights with the parameters of an arbitrary statistical method that we aim to emulate. By the same principle, the fixed attention module then mimics the behavior of diverse statistical models within the in-context learning framework.
Corollary 4.2.1 (In-Context Emulation of Statistical Methods). Let A be the set of all algorithms implementable by a single-layer attention network in-context. For any finite collection of algorithms
8

---

Published as a conference paper at ICLR 2026
{a1, "01.0.....,, .x} := Ao S A. there exists two-layer attention network (a single-head layer Attn, composed with multi-head layer Attn,)) such that for each E Ao in the collection
3n
Attn, o Attny Linear, [
a(X)lloo S
f=1
where / is the W defined as Definition 4.2 using W W Wp.
Proof. See Appendix D.7 for detailed proof.
We show that a fixed attention module emulates an arbitrary finite library of in-context algorithms by varying prompt. This result highlights the flexibility of softmax attention: unlike prior work that requires re-training fine-tuning of the model, here provably achieve task-specific behavior by modifying the input prompt. In effect, a pretrained Transformer internalizes small set of fundamental procedures and later deploys them, via prompting, across wide range of data distributions. Since the number of distinct algorithms is far smaller than the number of possible datasets, a model that learns handful of algorithms can leverage them to handle many different scenarios.
4.3 ATTENTION MAKES EVERY (LINEAR) NETWORK IN- CONTEXT
We now extend the above ideas to show that softmax attention emulates any network (comprised of linear transformations) in-context. Consider any layer of a neural network that applies a trainable linear map - Oz with weight matrix θ Our results imply that if θ is provided part of the input sequence, a fixed attention module is capable of approximating this transformation to arbitrary precision. Hence linear layers in standard architectures weights are encoded in the prompt rather than learned. This substitution turns the network into an in-context learner in place of, alongside, conventional training.
replaceable with attention whose effective
Remark 4.5 (In-Context Emulation of Linear Layers). For example, suppose model contains linear layer f(x) = Oz with weight matrix O By including è (appropriately encoded) in the input in constructions above, single softmax attention layer emulates f(x) in-context arbitrary precision. In other words, any trainable linear mapping in the original network is replicable with a prompt-programmatee attention layer whose parameters set by the input sequence. This enables the overall network to adjust that layer's 's behavior on- on-the-fly fly via prompts, rather than having to learn & through pre-training.
Number of Heads Plot
5 NUMERICAL STUDIES
Mean Loss
3-
This section provides numerical results to back up our theory. We validate two building blocks on synthetic data: (i) approximation of contin- uous functions (Section 5.1); and (ii) approxi- mation of attention heads (Section 5.2). These studies quantify approximation error and its lation to model size and the number of heads.
1-
2
10
12
Number of Heads
Figure 2: Sensitivity of Attention Emulation to the Number of Heads. We report loss (MSE) as the mean and one standard deviation (shaded region) over 10 ran- dom seed runs. use synthetic data of 50000 data points with sequence length being and input dimen- sion being 24. We set batch size to be 32 and hidden dimension to be 48. Fach multi-head model and the single-head softmax attention layer trained for 50 epochs. The optimizer used Adam with learning rate 0.001. We visualize the performance (MSE + Std) for 1,2,4, 4, 6, 8, 12 heads.
5.1 PROOF-OF- OFCONEOF EXPERIMENT ON THEOREM 3.1
Objective: Verifying Attention Approximates f(w x -z-y)a: y)ar. We investigate accuracy of soft- max attention approximating fw xx y) by training single-head softmax attention with linear connection.
Data Generation. We randomly generate X E Raxd drawn from a normal distribution, X ~ 10 (N, 5. We also generate weight matrix W E Rand and E IR" both randomly drawn from standard normal distribution, N(00 1). Here, represents the sequence length and d represents input dimension. The true label f(w x y)æ, where we choose f(-) tanh(-).
Model Architecture. We train a single-head attention network to approximate tanh (w x 1 We first apply linear transformation to both [X:y] and W. We then train the single-head attention model approximate target function shown in the proof of Theorem 3.1.

---

Published as a conference paper at ICLR 2026
Results. As shown in Figure 2, evaluated on Mean Square Error loss, the model approximates the target tanh(w (w" _ x - y) with minimal error. This experiment proves our theory.
5.2 PROOF-OF-CONCHRT EXPERIMENT ON EMULATING ATTENTION HEADS
Objective: Verifying Approximation Rates. We investigate the affect of the number of attention heads H on the accuracy of softmax attention approximating softmax attention head.
Data Generation. We randomly generate sequence of tokens X = [21 Fnl E IRdx, where each entry 24 is drawn independently from normal distribution,
X (N,
W .Q = -WxX E R and V W E Rddx We also generate weight matrices K = W XT
Each parameter matrix is randomly drawn from a standard normal distribution, (N, 1). Here, n, d, represents the sequence length, token dimension, and hidden dimension, respectively. The true label Y E d results from applying a single-layer softmax attention mechanism on inputs X, K, Q, V.
Model Architecture. We train a multi-layer attention network to approximate softmax attention. We first train separate multi-head models approximate K, Q, and V. Then, we use a single-head softmax attention layer to approximate softmax attention function as in the proof.
Results. As shown in Figure 2 and Table 1, the result validates our claim that multi-head soft- max attention mimics a target softmax attention head to arbitrary precision. Moreover, it demon- strates the convergence of multi-head softmax at- tention emulating softmax-basse attention map- ping as the number of heads increases. The approximation rate is in the trend of O1)HH) where H is the number of heads. The small and decreasing MSE error indicates that the simple softmax attention model approximates softmax attention head with stability.
Table Sensitivity to the Number of Heads. Emula- tion MSE (mcan + std) for multi-head softmax attention with 1, 2, 4, 6, 8, and 12 heads.
Heads
4
6
8
12
MSE
3.469
2.802
1.222
1.012
0.793
0.686
Std
0.381
0.413
0.603
0.204
0.127
0.171
Additional Experiments. Due to page limits, we defer several experimental results to Appendix C. These include simulations of statistical algorithms (Appendix C.1) and approximations of statistical models on real-world datasets where the model does not have access to the true algorithm weights (Appendix C.2). They further illustrate the approximation capabilities of Transformer in practice.
DISCUSSION AND CONCLUSION
We study in-context algorithm emulation in fixed-weight Transformers and formalize two modes: lask-specific (Section 3) and poopt-programmade algorithm emulation (Section 4). For the former, we show that even a single-layer, single-head module suffices for emulating core families (of the form f(w x - y)æ² such as one-step gradient descent and linear/ridge regression, achieving architectural minimality (Theorem 3.1). For the latter, we show that a two-layer multi-head softmax attention module emulates broad class of algorithms by embedding the algorithm's 's weights into the input prompt (Theorem 4.).. Altogether, fixed softmax attention module becomes library of algorithms: weights remain frozen, and the prompt selects the routine.
The mechanism is constructive. By encoding target weights in the input and creating large dot-product margins, softmax attention routes along the intended computation without weight updates. Numerical studies support the theory: on synthetic data the model accurately approximates continuous maps of the form f((w, æ) y) x and emulates attention heads. Approximation error decreases as the number of heads grows. On a real dataset (Ames Housing), the frozen module-driven by prompts rather than true algorithm neights-achieves low error against standard statistical models.
Mechanism.
Implications. Our results tighten the link between in-context learning and algorithmic emulation. Viewing prompts callable subroutines that select and configure algorithms within frozen model, we draw three takeaways: (i) prompt engineering becomes interface design for algorithm selection, (ii) pretraining objectives could, in future work, be designed to encourage learning compact libraries of reusable procedures, and (iii) analyses of internal routing help clarify how foundation models select among algorithms. This lens explains the breadth of in-context generalization, guides prompt design, and motivates new pretraining objectives for more effective algorithm installation and utilization.
10

---

Published as a conference paper at ICLR 2026
ETHIC STATEMENT
This paper does not involve human subjects, personally identifiable data, or sensitive applications. We do not foresee direct ethical risks. We follow the ICLR Code of Ethics and affirm that all aspects of this research comply with the principles fairness, transparency, and integrity.
REPRODUCIBILITY STATEMENT
We ensure reproducibility on both theoretical and empirical fronts. For theory, we include all formal assumptions, definitions, and complete proofs in the appendix. For experiments, we describe model architectures, datasets, preprocessing steps, hyperparameters, and training details in the main text and appendix. Code and scripts are provided in the supplementary materials to replicate the empirical results.
ACKNOWLEDGMENTS
JH thanks Alex Reneau, Yingyu Liang, Mimi Gallagher, Sara Sanchez, T.Y. Ball, Dino Feng and Andrew Chen for valuable conversations; Po-Chiao Lin for meticulous proofreading and pointing out typos; Po-Chiao Lin, Xiwen Zhang, Mingcheng Lu, Hong- Yu Chen, Maojiang Su, Weimin Wu, Zhao Song and Pin-Yu Chen for collaborations on related topics; the Red Maple Family for support. The authors also thank the anonymous reviewers and program chairs for constructive comments.
This work is in remembrance of Prof. Bi-Ming Tsai (February 1965 October 21, 2025). Her wisdom in health, cooking, and the art of thoughtful living continues to inspire JH.
JH is partially supported by Ensemble Al and Northwestern University's Walter P. Murphy Fellowship and Terminal Year Fellowship (Paul K. Richter Memorial Award). Han Liu is partially supported by NIH ROILM1372201. NSF AST-2421845, Simons Foundation MPS-AI-00010513, Abb Dolby and Chan Zuckerberg Biohub Chicago Spoke Award. This research was supported in part through the computational resources and staff contributions provided for the Quest high performance computing facility Northwestern University which is jointly supported by the Office of the Provost, the Office for Research, and Northwestern University Information Technology. The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding agencies.
REFERENCES
Jacob Abernethy, Alekh Agarwal, Teodor Vanislavov Marinov, and Manfred Warmuth. mecha- nism for sample-efficient in-context learning for sparse retrieval tasks. In International Conference on Algorithmic Learning Theory, pages 3-46. PMLR, 2024.
Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn implement preconditioned gradient descent for in-context learning. Advances in Neural Information Processing Systems, 36:45614 45650, 2023.
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in-context learning? investigations with linear models. In The Eleventh International Conference on Learning Representations, 2023.
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers as statisticians: Provable in-context learning with in-context algorithm selection, Advances in neural information processing systems, 36:57 11-57125-57211, 2023.
Rishi Bommasani. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07255 072558 2021.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neurul information processing systems, 33:1877-1901, 2020.
Yuan Cao, Yihan He, Dennis Wu, Hong-Yu Chen, Jianqing Fan, and Han Liu. Transformers simulate mle for sequence generation in bayesian networks. arXiv preprint arXiv:2501.00 02547, 2025.
Dean De Cock. Ames, iowa: Alternative to the boston housing data as an end semester regression project. Journal of Statistics Education, 19(3):1-33, 2011.
11

---

Published as a conference paper at ICLR 2026
Ezra Edelman, Nikolaos Tsilivis, Benjamin L Edelman, Eran Malach, and Surbhi Goel. The evolution of statistical induction heads: In-context learning markov chains. Advances in neural information processing systems, 17:64273-6433 2024.
Deqing Fu, Tian-Qu nin-Qi Chen, Robin Jia, and Vatsal Sharan. Transformers learn to achieve second-order convergence rates for in-context lincar regression. Advances in Neural Information Processing Systems, 37:98675-98716, 2024.
Takashi Furuya, Maarten V de Hoop, and Gabriel Peyré. Transformers are universal in-context learners. arXiv preprint arXiv:2408.01366 2024.
Shivam Garg, Dimitris Tsipras, Perey Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30533-30598, 2022.
Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason D Lee, and Dimitris Papailiopoulos. Looped transformers programmable computers. International Conference on Machine Learning, pages 11398-1144) 1442. PMLR, 2023.
Angeliki Giannou, Liu Yang, Tianhao Wang, Dimitris Papailiopoulos, and Jason D. Lee. How well can transformers emulate in-context newton's 's method? In Advances in Neural Information Processing Systems, 2024.
Yihan He, Yuan Cao, Hong-Yu Yu Chen, Dennis Wu, Jianqing Fan, and Han Liu. Learning spectral methods by transformers. arXiv preprint urXiv:2501.013122 2025.
Jerry Yao-Chich Hu, Hude Liu, Hong- Yu Chen, Weimin Wu, and Han Liu. Universal approximation with softmax attention. arXiv preprint arXiv:2504. 15956, 2025a.
Jerry Yao-Chich Hu, Wei-Po Wang, Ammar Gilani, Chenyang Li, Zhao Song, and Han Liu. Fun- damental limits of prompt tuning transformers: Universality, capacity and efficiency. In The Thirteenth International Conference on Learning Representations, 2025b.
Tokio Kajitsuka and Issei Sato. Are transformers with one layer self-attention using low-rank weight matrices universal approximators? In The Twelfth International Conference on Learning Representations, 2024.
Brian Lester, Rami AI-Rfou, and Noah Constant. The power of scale for pframeter-efficient prompt tuning. Proceedings of the 2021 Conference on Empirical Methods Natural Language Processing (EMNLP), 2021.
Gen Li, Yuchen Jiao, Huang, Yuting Wei, and Yuxin Chen. Transformers meet in-context learning: A universal approximation theory. arXiv preprint wxXiv:2506.05000 2025.
Xiang Lisa Li and Percy Liang. Prefix-tuning: Optimizing continuous prompts for generation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics (ACL), 2021.
Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers as algorithms: Generalization and stability in-context learning. In International conference on machine learning, pages 19565-19594 PMLR, 2023.
Hude Liu, Jerry Yao-Chieh Hu, Zhao Song, and Han Liu. Attention mechanism, max-affine partition, and universal approximation. In Advances in Neural Information Processing Systems, 2025.
Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing. ACM computing surveys, 55(9):1-35, 2023.
Sheng Liu, Haotian Ye, Lei Xing, and James Zou. In-context vectors: Making in context learning more effective and controllable through latent space steering. In Forty-first International Conference on Machine Learning, 2024.
12

---

Published as a conference paper at ICLR 2026
Xiao Liu, Kaixuan Ji, Yicheng Fu, Weng Tam, Zhengxiao Du, Zhilin Yang, and Jie Tang. P-tuning: Prompt tuning can be comparable to fine-tuning across scales and tasks. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 61 61-68, 2022.
Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 11048-1 1064, 2022.
Eshaan Nichani, Alex Damian, and Jason Lee, How transformers learn causal structure with gradient descent. arXiv preprint mrX1::2402.14735, 2024.
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1-35, 2021.
Ruizhong Qiu, Zhe Xu, Wenxuan Bao, and Hanghang Tong. Ask, and it shall be given: On the turing completeness of prompting. arXiv preprint wxXiv:241.00192 2024.
Max Vladymyrov, Johannes Von Oswald, Mark Sandler, and Rong Ge. Linear transformers are versatile in-context learners, Advances in Neural Information Processing Systems, 37:48784 2024.
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In International Conference on Machine Learning, pages 35151-35174, PMLR, 2023.
Yihan Wang, Jatin Chauhan, Wei Wang, and Cho-Jui Hsieh. Universality and limitations of prompt tuning. Advances in Neural Information Processing Systems, 36:75623-75643, 2023.
Dennis Wu, Yihan He, Yuan Cao, Jianqing Fan, and Han Liu. Understanding transformers for time series forecasting: A case study on moirai. In The Fourteenth International Conference Learning Representations, 2026.
Weimin Wu, Maojiang Su, Jerry Yao-Chieh Hu, Zhao Song, and Han Liu. In-context deep learning via transformer models. In International Conference on Machine Learning. PMLR, 2025.
Chulhee Yun, Srinadh Bhojanapalli,, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequene functions? In International Conference on Learning Representations, 2020.
Ruiqi Zhang, Spencer Frei, and Peter Bartlett. Trained transformers learn linear models in-context. Journal of Machine Learning Research, 25(49):1-55, 2024.
Yufan Zhuang, Chandan Singh, Liyuan Liu, Jingbo Shang, and Jianfeng Gao. Vector-icl: In-context learning with continuous vector representations, In The Thirteenth International Conference on Learning Representations, 2025.
13

---

Published as a conference paper at ICLR 2026
Appendix
A Proof Sketches
15
A.1
Proof Sketch for Theorem 4.1 Proof Sketch for Theorem 4.2
15
A.2
17
Related Work
18
B.I
Core Related Work
18
B.2
Broader Discussion
19
Additional Numerical Studies
20
C.I Proof-of-Concey Experiment Emulating Statistical Models
20
C.2 World Experiment on Emulating Statistical Models
C.3 Proof-of-Concee Experiment Theorem 4.2
22
D Proofs of Main Text
22
D.I Proof of Theorem 3.1
................................
D.2 Proof of Corollary 3.1.2.
45
................................
D.3 Proof of Corollary 3.1.3..
45
D.4 Proof of Corollary 3.1.4
46
D.5 Proof of Theorem 4.1
47
D.6 Proof of Theorem 4.2
59
D.7 Proof of Corollary 4.2.1
77
In-Context Application of Statistical Methods by Modern Hopfield Network
78
IMPACT STATEMENT
We prove that a single frozen softmax attention head emulates broad library of attention- implementable algorithms via prompt design, establishing pretrained Transformers as universal algorithm stores and reducing the need for task-specifie fine-tuning. This sharpens the theoretical basis of in-context learning, offers principled recipe for prompt engineering, and equips auditors with a clear test for hidden prompt-encoded behaviors, all without releasing new models or data. Therefore, the work advances foundational understanding, lowers compute and energy demands, and introduces minimal socictal risk.
LIMITATIONS AND FUTURE DIRECTION
Prompt length grows linearly with the weight dimension, which limits practicality. The proofs assume exact real-valued softmax and ignore token discretizations numerical noise. Prompts are hand-crafted. Learning them automatically is open. Language and vision inputs are untested. Weight encoding happens along embedding dimension. The construction is not permutation invariant, but permutation equivariant of the input data. Lastly, we leave tighter constants, shorter prompts, extensions to deeper models and connection with model pretraining future work.
LLM USAGE DISCLOSURE
We used large language models (LLMs) to aid and polish writing, such improving clarity, grammar, and conciseness. We also used LLMs for retrieval and discovery, for example exhausting literature to identify potential missing related work. All technical content, proofs, experiments, and results are original contributions by the authors.
14

---

Published as a conference paper at ICLR 2026
Xp
mm
Wx X
Concatenate Predicted Values
WoX
Input Data
X
K O
Softmax Attn,
Weight Encoding
W
Recovering
Wy X
Position Encoding
In
V
Approx. Error
W K X W X
Concatenate True Values
K Q
Softmax Attn,
Weight
W
Calculating Wy X
Figure 3: Visualization of Proof Sketch for Theorem 4.1. We visualize our proof technique. We combine input data, weight encoding, and position encoding into X, as input the multi-head attention Attn.. to recover approximate key, query, and value representations. We then compare the single-head attention Attn, outputs from approximate values with ground truth values to obtain approximation error.
A PROOF SKETCHES
We present proof strategies here.
A. PROOF SKETCH FOR THEOREM 4.1
construct a two-layer Transformer (single-head layer Attn, followed by multi-head layer Attum)
that replicates the target attention to within any error >> 0. Recall from Theorem 4.1:
Step
Step
Attn, Attil
X
Wy (WoXttmaxx((Wxx)) T 1oo0 S
Step 2
Target
Emulator
The high-level idea is: (Step 1) augment the input with prompt encoding of the target weights WK, Wo, Wv. (Step use groups of heads in Attn approximate the matrices K W k X, Q = WoX. V == W in-context (up to small error), and (Step 3) apply Attn, with fixed weights to assemble the Attnm output: the approximators K", Q', V'. We then argue in (Step 4) approximation eиrог can be made via a stability bound softmax attention.
Step 1: In-Context Weight Encoding, We augment the input X E Rdxn by appending special tokens encoding the matrices WK. Wo, Wy. We denote the augmented input as Xp. This allows the transformer Attn, Attn "read" the relevant weight parameters in its attention heads.
Explicitly, we embed both the data sequence and the target head into the input (Definition 4.2):
X,
W In
in
with
Wi.
[0 1 w
10
(n 1) w 2 w
where w [WT. T. WT. WT concatenates every column of WT, WT tion 4.2. The block T, provides token-position codes used in construction.
Q Wi following Defini-
15

---

Published as a conference paper at ICLR 2026
The idea of this augmentation is to emulate the target computation WyyXSoftmax((M x x with the emulator: a two-layer transformer Attn, o Attum To achieve this, Attn, Attnn must access the information of X, WK. Wo and Wy in-context. The augmentation above encodes these parameters (target algorithm's specifications) in the prompt.
Step 2: Multi-Head Decomposition for In-Context Recovery of K, Q.V. We devote the first attention layer (Atinm) to recovering the key, query, and value matrices that the target attention would compute. By definition, each row in K, Q. and V takes the form: K; X, g, X and o, X. Here k &. and v. are rows in WK, Wq and Wv. Our goal is, for each data token z; (the i-th column of X), to approximate k F4. 93 Fú, and vj I;- To do this, we design Attn to have a fixed number of heads partitioned into three groups, corresponding to K, Q, and V respectively. Combining heads' outputs within each group yields approximations of K, Q, and V. Explicitly, in the first multi-head layer Allum, split the heads that:
A group of heads jointly approximates Wx By (Hu et al., 2025a, Theorem 3.2), the heads this group admit further subdivision into sub- groups. Each sub sub-group outputs linear transformations of X, namely k X for rows k X of K.
Another group of heads approximates WoX in similar manner.
A final group approximates Wv
Concatenate or combine these head outputs so that the final embedding from Attnm (Xp) contains (up small error) the blocks [K; Q; V] for all positions in X.
Explicitly, for each row kj of Wx (and similarly for qj and v.) ) we prepend the corresponding heads with token-wise linear map A(-). A(Xp) pulls out the target row (i.e., ky) from w and repeats it n times. The resulting sub-puu prompt A(Xp) has the form
0 ky ky
1 ky
(n (1) kj lij
...
kj
Ln
so the corresponding softmax heads return KJ X up to any error by the truncated- linear interpolation theorem (Theorem D.1). With H = [2 - a)/((n 2)co)] heads per sub- sub-group, we cover all d,. rows in K (and similarly for Q and V). Altogether, the 3N 3d, heads satisfy
du
2d
3d
Atin K (Xp) - S co. II
Σ
Aun (Xp) Q11x S co:
Σ j=
Attn (Xp) -V c0-
j=dy +1
K'
Q'
We collect these outputs column- wise into
K' Q' V
K Q' I
K Q
and
||
11 E0.
Step 3: Single-Head Assembly for Emulated Map. We consider the second layer Atin, as single-head attention with fixed weights chosen to "read" the K' K',Q', V' triples from Z Attnm (Xp) and perform the "emulated" attention mechanism. Explicitly, apply a single-head attention layer Attn, whose parameters are to read off the K, Q, and V sub-blocks in each token embedding:
Attn. = w 7Softmax((W 2) (w/) (T 2)).
16

---

Published as a conference paper at ICLR 2026
For Z = Attum (Xp), choose fixed weights
w()) Odd x2dn
Id,l,
W [dn
Od 02nx2
w
[Ods xdn
Ida
Odnxda],
so that
7 WvX.
Hence,
K Q'
Aun, Ating Atlnm (Xp) Allns(
('Softmax((K")) Q')
Wv XSWottoxxxxxxxa WQ
To be precise, because K', Q', V differ from K, Q, V by most eo (in || bloo), first-order perturbation argument for softmax (uniform Lipschitz in sup-norm) shows
K Q'
K Q
Attn
Il S co + #BRgvve,
V
where BRQv bounds X, WK. Wo, Wy and O(eo).
Step 4: Error Bound. Finally, make the approximation arbitrarily precise. Because capable making each head's linear approximation arbitrarily close, we ensure
Attn, Attum ([x; W]) Wy XSottmax((xxX Wo se
for any > O. This completes the construction, proving in-context emulation of the target attention. Please see Appendix D.5 for a detailed proof and Figure for proof visualization.
A.2 PROOF SKETCH FOR THROREM 4.2
We outline how to emulate the desired attention dep-bb-step with fixed two-layer transformer. Similar to Theorem 4.1 (and Theorem D.I), our construction ensures each token't 's representation in the intermediate layer carries approximate copy of its key, query, and value vectors, which the final layer uses to perform the softmax attention. All necessary components (including the weight matrices WK, Wo, Wy themselves) are encoded into the input, so the network's 's weights remain untrained and generic.
Step 1: Encoding Weights into the Input. Let X E Rddx be the input tokens. Append "weight encoding" matrix W that contains the rows of WK. Wo, Wy (the weight matrices of the target attention head). This forms an extended input [X; W]. The entries of X and W remain within bounded range [- B, B). This bound ensures that all inner products remain finite.
Step 2: Multi-Head Approximation K, Q, V. The first layer has many heads. Partition them into three groups. One group approximates K == W X; one approximates Q == XQ and one approximates V X. Then
Simulating Dot Products on 1D Grid. Consider a single entry kj xe. All entries in K, Q. V lie between [-dB² ddB)), since the entries of X and W remain within bounded range [-B, B, B). We create grid points Lo < ... < Lp covering i-dB² dB²). We design the head's key and query that the softmax assigns each grid point L; weight based on its distance to kJ xz. We set the value vector to encode Lę- Thus, the head output for token
Te approximates kJ Fe- Fine grids reduce the error.
17

---

Published as a conference paper at ICLR 2026
Lincar
Atto K
Concatenate Predicted Values
Input Data
X
K
Softmax Attn,
Linear
Attn m
Q'
Weight Encodling
W
Linear
Attn
V
Approx. Error
Wx4 X
Concatenate True Values
We X
K
Softmax Attn,
Real Weight
W
Calculating Wy X
Q
Figure 4: Visualization of Proof Sketch for Theorem 4.2. We visualize our proof technique. We combine input data and weight encoding as input. Each key, query, and value has unique set of linear transformation of input (Linear) and multi-her head attention (Attmm).. We feed the input into each set attain the approximate key, query, and value representations, respectively. We then compare the single-head attention Atmn, outputs from approximate values with ground truth values to obtain approximation error.
Reconstructing Full K, Q V. Repeat this idea for every entry in K, Q, V. Each uses one head to approximate kj X, 93 X, or v. X. Combine these approximations to obtain the matrices K', L',VV' V The sup norm
K Q' V
K Q
||
1oo,
can be made arbitrarily small.
Single-Head Assembly the Attention Output. The second layer, Attn,, has one head. to pick out K', Q', V' from each token's embedding. We set its weight matrices W w(() w Then, Attn, computes
Step 3:
V'Softmax (KK) ((') WVXXSotmaa(Wxxx))W WQx),
since K' K. x' and V'
Step 4: Error Bound. Softmax and matrix multiplication are continuous. Small errors in K', Q', V cause small error in the final output. By refining the grid (and using enough heads), we make the sup norm error below any > 0. Please see Appendix D.6 for detailed proof and Figure for proof visualization.
B RELATED WORK
Our results diverge from prior findings on Transformer universality and in-context learning.
B. CORE RELATED WORK
Universal Approximation. Prior studies establish that Transformers approximate arbitrary functions, but they do not address in-context learning and often assume complex architectures. For example, Yun et al. (2020) prove that deep multi-head Transformers with feed-forwart layers are universal approximators continuous sequence-tor suueenee-o--squenee functions. Subsequent advances tighten this finding: Kajitsuka and Sato (2024); Hu al. (2025b) show that
18

---

Published as a conference paper at ICLR 2026
single-layer Transformer realizes any continuous sequence function. However, these results treat Transformers as parametric function approximators. The model requires re-training and re- re-prompting to adapt to new target function instead of handling multiple tasks through context. In contrast, prove that a minimal Transformer architecture, even a single-layer, single-head attention module with feed-forward network, emulates broad class of algorithms without weight updates by varying its prompt. This result achieves a new level of generality through context alone (i.e. prompt-based conditioning) despite a fixed minimalist model.
In-Context Learning and Algorithm Emulation. Another line of recent theory bridges Trans- formers with in-context learning by designing model components to carry out specific algorithms. For example, Bai al. (2023) show that Transformers execute a broad range of standard algorithms in-context, but each algorithm requires a distinct, tailored attention head. In comparison, we extend this approach by showing that one fixed attention mechanism emulates any specialized attention head via prompt encoding. Rather than crafting different attention module for each algorithm, single frozen softmax-bas -based attention layer takes its instructions from the prompt to perform all tasks in context. This minimal model thus becomes unified and compact in- in-context algorithm emulator. It switches behaviors by changing only its input prompt, setting it apart from earlier approaches that required per-task reparameterization.
B.2 BROADER DISCUSSION
Universal Approximation and Expressivity of Transformers. Transformers exhibit strong ex- pressive power as sequence models. Recent theory shows even minimal Transformer architectures approximate broad classes of functions. Kajitsuka and Sato (2024); Hu et al. (2025b) prove single-layer, single-head Transformer can memorize any finite dataset perfectly. Kajitsuka and Sato (2024) achieve this with low-rank attention matrices, while Hu et al. (2025b) use attention matrices of any rank. Adding two small feed-forward layers makes it a universal approximator for continuous sequence functions under permutation-equiiarraaee show self-attention layers alone are universal approximators. Specifically, two attention-only layers approximate continuous sequencceto-seqqueece mappings, and even single roftmax-attention layer suffices for universal approximation. Similarly, Liu et al. (2025) also demonstrate that one single-head attention connected with linear transformations is sufficient to approximate any continuous function in T. norm. These results eliminate the need for feed-forward networks, improving on earlier constructions. Overall, these findings highlight the inherent expressiveness of minimal attention mechanisms.
More recently, Hu et al. (2025a)
Transformers as In-Context Learners and Algorithm Emulators. Large Transformers also learn in-context by conditioning on examples in their prompts, without updating weights (Brown et al., 2020). Recent work formally explains this by showing attention-based models implement standard learning algorithms internally. Bai et al. (2023) construct Transformer heads executing algorithms such linear regression, ridge regression, Lasso, and gradient descent steps, achieving near-optimal predictions. Wu et al. (2025) further build Transformers explicitly simulating multiple gradient descent iterations for training deep neural networks, with provable convergence guarantees. Empirical and theoretical studies confirm Transformers internalize learning algorithms when meta-trained on task families. Garg et al. (2022) show meta-trained Transformers mimic classical algorithms, such as ordinary least squares regression, in in-context. Similarly, Akyürek et al. (2023); Von Oswald et al. (2023): Zhang et al. (2024) analyze Transformers trained on linear regression tasks and demonstrate their outputs mimic gradient descent steps precisely. Overall, existing literature shows that sufficiently trained or carefully designed Transformers emulate step-by-step computations of standard algorithms through prompt conditioning.
Frompt-Tuning Prompt-tuning adapts frozen models by learning a short continuous prefix (Lester et al., 2021: Li and Liang, 2021; Liu et al., 2022). It keeps backbone weights fixed and updates only prompt embeddings. Our setting is stricter: prompts are hund-designed, not learned, and we give exact approximation bounds. Thus we expose the theoretical limit of prompt control: a single frozen softmax head can mimic any task-specific head.
19

---

Published as a conference paper at ICLR 2026
Encoding Context Along Embedding Dimension. Recent work in in learning explores encoding and manipulating context in the embedding space rather than sequence dimension. For example, Liu et al. (2024) propose In-Context Vectors for steering the model's behavior by adding task-specific vectors along the embedding space. Zhuang et al. (2025) extend this idea by showing that manipulating embedding vectors such interpolation makes in-context learning more control- lable. Abernethy et al. (2024) showcase that appending additional information along the embedding dimension allows the model perform sample-efficient in-context learning.
Comparison Our Work. The above results demonstrate the versatiliiyy of Transformer networks, but they require task-specific weights, training, or learned prompts. For instance, Bai et al. (2023) design different task-specific head for each algorithm of interest, raising the question of whether single fixed attention mechanism could instead serve as a universal emulator for any algorithm given the right prompt. Our work directly addresses this question. In contrast, we prove one fixed softmax head emulates any specialized head through prompt encoding alone. No additional weights or training are required. Even the simplest attention (one layer, one head) acts as universal algorithm emulator when given the right prompt, shifting focus from architecture prompt design.
C ADDITIONAL NUMERICAL STUDIES
We extend the synthetic validation to statistical algorithms (Appendix C.I) and include a real-world study (Appendix C.2). The frozen attention module emulates linear, ridge, and lasso on synthetic data. On the Ames Housing dataset, the model operates without access to true algorithm weights and achieves low approximation error. In addition, validate Theorem 4.2 through handcrafted frozen attention weights and parameters as constructed in the proof (Appendix C.3).
C.I PROOF-OF-CONCEPT EXPERIMENT ON EMULATING STATISTICAL MODELS
Emulation of Statistical Models. We investigate the accuracy of a frozen softmax attention approximating statistical models including Lasso, Ridge and linear regression by only varying the input prompts.
Objective:
Data Generation.
We simulate an in-context dataset by randomly generating a sequence of input tokens X [21, , rn] Raxd where each x; is independently drawn from scaled standard normal distribution,
24 ~ 2 10, 1.
task- spec--secffic prompt vector E Rex sampled from N(. 1). In the case of Lasso, we randomly zero out entries in w with probability 0.5 to induce sparsity. We generate the output sequence Y E IRax1 via a noisy linear projection: Y Xw + e, where e N(0 o²) Gaussian noise. For Ridge, we calculate weights using (X X Xa)
with =
Model Architecture and Training. We use mixture of statistical data to train single-layer attention network with linear transformation. Each input sample consists X E IRadd and algorithm- specific prompt E I.P. We replicate across the sequence length and concatenate it with X along the feature dimension to obtain augmented input [X; w| (nx(d+)), We pass it through a multi-head attention layer. We train the model for 300 epochs using the Adam optimizer with learning rate of 0.001. We use 6 attention heads, hidden dimension of 48, an input dimension of 24, a batch size 32, and 50000 synthetic samples. After training, we freeze the attention weights, resulting in fixed softmax attention layer. We evaluate the frozen model on its ability to emulate various statistical algorithms using test data.
Baseline Architecture. We train three separate attention models for Lasso, Ridge, and linear regression. That is, each attention model weights are adaptive its corresponding algorithm. We use
20

---

Published as a conference paper at ICLR 2026
these models baselines for comparison with the frozen attention model we propose. All baseline models use the same haper-parameters as the frozen model.
Results. As shown in Table 2, we compare mean MSE and standard deviation over random seed runs for the frozen attention model against baseline for Lasso, Ridge, and linear regression on the synthetic data. The frozen attention model performs as well as the baseline models trained individually on each algorithm. It achieves lower MSE Lasso and linear regression tasks compared to their corresponding baselines. It shows that frozen attention mechanism generalizes across these tasks given task specific prompts. Moreover, the frozen model exhibits lower variance across all tasks, suggesting increased stability and robustness. These results support our claim that frozen softmax attention layer, when conditioned on task-specific prompts, emulates statistical algorithms in context without much performance degradation.
Table 2: Comparison Between Baseline and Frozen Attention Layer on Synthetic Dataset. We compare loss (MSE) as the mean and one standard deviation over random seed runs for baseline vs. frozen model on different algorithms. We train on 50000 training data points evaluate on 10000 testing data points for each algorithm.
Model
Lasso
Ridge Regression
Linear Regression
Baseline
0.015
0.0043
0.147++0.067 0.120+0.000
Frozen Attention
0.059+00000
0.0002
C.2 WORLD EXPERIMENT ON EMULATING STATISTICAL MODELS
Objective: Real-World Emulation of Statistical Models. Building on Appendix C.I, we use real-world data to investigate the accuracy of frozen softmax attention emulating algorithms.
Data Collection and Processing. We collect data from Ames Housing Dataset (De Cock, 2011). This dataset consists of 2930 observations and 79 features. We process the data by toggtraasforming the target variable, encoding categorical variables with one-hot vectors, replacing missing entries with median values, and standardizing numerical features. The resulting data consists of 262 features. We fit the processed data Lasso, Ridge, and linear regression models to obtain algorithm weights as part of the input.
Model Architecture and Training. We use mixture of statistical data to train single-layer attention network with linear transformation. The input is passed through a multi-head attention layer with linear transformation. We train the model for 300 epochs using the Adam optimizer with learning rate of 0.001. We use 8 attention heads, a hidden dimension of 524, and a batch size of 32. After training, we freeze the attention weights, resulting in fixed softmax attention layer. The frozen model is then evaluated on its ability to emulate various statistical algorithms using test data. We train the baseline models the same way as the synthetic experiment.
Table 3: Comparison Between Baseline and Frozen Attention Layer on Ames Housing Dataset. We compare loss (MSE) as the mean and one standard deviation over 5 random seed runs for bascline vs. frozen model different algorithms. We train on 80% training data and evaluate 20% testing data for each algorithm.
Model
Lasso
Ridge Regression
Linear Regression
Baseline
0.0354100.000 0.0322-10.0000
0.0132-10.0000 0.0252-10.0000
Frozen Attention
0.0250=0.0000
Results. As shown in Table 3, we compare mean MSE and standard deviation over random seed runs for the frozen attention model against baseline for Lasso, Ridge, and linear regression Ames
21

---

Published as a conference paper at ICLR 2026
Housing Data. The results shows the frozen attention model performs well as the baseline models trained individually. We use an auxiliary network to approximate the required weight encoding. Our experiment validates that the mechanism works even when the exact weights are not supplied in real world scenarios.
C.3 PROOF-OF-CONCEP" EXPERIMENT ON THEOREM 4.2
Objective: Verifying Handcrafted Frozen Attention Approximates Attention. We validate that the frozen attention prescribed Theorem 4.2 approximates softmax attention with low error. In particular, we handcraft the weights in the proof of Theorem 4.2.
Data Generation. We create synthetic dataset. We randomly generate E 1n drawn from a uniform distribution over 1-1, X U-,,,
Number of Interpolation Points Plot
0.6
Mean Loss
For each sample, we generate three weight matrices WK, Wo, Wv E Rxxd drawn from standard mal distribution NO0,)) 1). We then compute K W Q WaX
0.4
0.2
Wy R=x"
The true target attention output is therefore given
0.0
by Y VSoftmax(( K Q) E Raxx.
20
30
40
80
Number of Interpolation Points
Following the proof in Ap- pendix D.6, we hard-wire the linear layer weights, attention weights, and interpolation points for the two-layer softmax attention module as our emulator. The model operates in a zero-shot, one-pass setting with training or parameter updates.
Model Architecture.
Figure 5: Sensitivity of Handcrafted Atten- tion Emulation the Number of Interpolation Points. We report loss (MSE) the mean one standard deviation (shaded region) over sample data points. Each data point has sequence length 12 and input dimension d 24. We set soft- temperature
We visualize the perfor- mance (MSE + Std) for 20, 30, 40, 60, 80.
Results. We report the results in Table and Figure 5, We compare the MSE loss between the emulator output and the target attention output. Specifically, we fix the number of data points input dimension d, softmax temperature 8, and number of samples for testing. We vary the number of interpolation points The result validates our claim that the handcrafted frozen attention approximates the target attention. Moreover, we show that as P increases, the approximation error and standard deviation both further decrease.
Table 4: Sensitivity to the Number of Interpolation Points. We report MSE loss (mean::: std) between outputs of handcrafted frozen attention and target attention varying number of interpolation points / over 4 samples. We choose
12, 4, 8 2, samples = for evaluation.
P
20
30
60
80
Mean MSE Std
4.002 x 10 10
2.442 x 10
5.852 x 10
5.770 X 10
5.037 X 10
2.393 x 10
1.451 x 10-2
8.538 x 10-5
1.994
10-9
1.620
10-14
D PROOFS OF MAIN TEXT
To prepare our proofs, we state the following axillary definitions and lemmas.
22

---

Published as a conference paper at ICLR 2026
Definition D.1 (Truncated Linear Function).
We define the truncated linear function as follows:
a t S a S b, b 5 x.
Range ()))
Intuitively, Range/a.a))) is the part of a linear function whose value in (a, b).
We then define the interpolation points in (a, b] that are used in later proofs.
Definition D.2 (Interpolation). Let [a, bj C I be an interval with I 6 and let p E N be positive integer. We define
[l..0] = a, Ila.b = b, [/ = a + i -0 a), i= 11.
Hence, Lo < L1 < < Ln forms uniform partition of [a, bj. We also write
AL i.!aall
T. ie [p].
We often omit the superscript (a, b] when the context is clear.
We also propose the following lemma to show Hardmax property that is capable of being approximated by Softmax.
Lemma D.1 (Lemma F.1 in (Hu et al., 2025a): Approximating Hardmax with Finite-Tenee Temperature
Softmax), Let [21, T2,..., Fn] E R", , > Define Softmax (-) as
Softmax;(x) = exp(3xx)
exp( (3xx) プラ exp(exxx
プラ exp(Bxx)
The following statements hold:
Case of a Unique Largest Entry. Assume 21 maxie(mi V, is unique, and x2 max;e(o](() 2t. Then, if (In(n 1) (n(c))/(z) 22), have
(oftmaxx(x) - c S c,
where e RR is the one-hot vector corresponding to the maximal entry of a (i.e., x).)) Case Two Largest Entries (Tied or Separated by 8). Assume #1 and 22 are the first and second largest entries, respectively, with 5 =
2 0. Let be the third largest entry and is smaller than x by constant 7 > irrelevant to the input. Then, B 2 (In(n 2) ine)/ we have
e-8
(oftmaxx(x))
+ e
61
1 e 36
S E.
The following technical lemma used in the proof of Theorem D.I.
Lemma D.2 (Refined Version of Lemma F.2 in (Hu et al., 2025a): Cases of All Heads in Attn H) For E LLo, LH(n-2)]. For any h E [H], define three cases of the relationship between a and
Case 1: [I(h- -2 Ln(i () 12)
Case 2: a & ((h-1))n-2)111 T I, 2
Case 3: a E (Lqn-1)(-22)1 Lne- 1) 22 (Tnn(n-2)-1- [M(-2))
23

---

Published as a conference paper at ICLR 2026
These cases includes all possible situation. Then for all h, only two cases exists
a falls in Case 1 for an h and Case 2 for all others.
a falls in Case 3 for two adjacent and Case for all others.
Proof. Because
[Lo, [n)) and
[Lo, LH(n-2)) (h 1)(n Ln(n-2))
we have
a E (1)-2-1)) Ton 2)-
(D.I)
for an arbitrary ha-
This leads only two possible cases
Case 18; a E [L 11)n Ln, (n- (n-2)-1)
Case 2 a E (2-)) (n-))
Case 1o: a E (L(no-1)(r 2); (nn(m-2)- Because E [L 1)(nn 1)(m-2) we have
Inn(n (n- 2) for + has
T(((n-2)-2 T-n(n-2) Ti(ho-1)(n 1))nn2)) h < ha
Ln(n-2)41 ( 1y(n 1)(n-2)-1 2 Lia h > ha.
Thus
[n( = [n 11(n (n [ 1)(n 2) Ln(nn2))
(h 1)(
[T 1))(n n 2) (T
for all h * ha-
This means that a does not fall into Case nor Case 3 for other h E [H]. Thus has to fall into Case 2 for other h.
Case 2*: [T<ha- Iin.-1inn 1) 2) U (n-2)-11 (n-)) ity, assume to be in the left half [T<(hh 1)(nn2) Tu(h 1)( Because
Without loss of general-
[L (0)nn))(n-2)))) I(n (1a-
[L (ob--1)(n-2)1111 L 1)(mn-))1 2))-
(Case 3 of hts 1)
[T<h.- ()) -- 1)(nn1)220000--- 2) = [T 1))m - 1)(x-)))
(Case 3 of ha)
this means falls into Case for ha and ha - 1.
This completes the proof.
We are now ready to prove a refined version of (Hu et al., 2025a, Theorem 3.2).
Theorem D.1 (Multi- Head Attention Approximate Truncated Linear Models In-Context). Let X IR dxn be the input. Fix real numbers and let the truncation operator Range)..) (-) follow Definition D. I. Let denote the linear coefficient and / denote the bias of the in-context truncated linear model. Define W, as
W₂ =
00 Ws
10s
(n - 1) Ws Ws
g 2dxn
Ws
W,
24

---

(3d+ 2n Published as a conference paper at ICLR 2026
For precision parameter > n with e = O(1pp), number of head H = p/(n 2) there exists single-layer, H-head self-attention Attn with linear transformation A : Rdx - R (3d+ xn. such that Attn A IRdxn - Rd.xx satisfies, for any E [n].
X W, ).. Rango (a, (w vi + t)ex lleo I maxf|al,lb]) co
Attn A(
- a (n
2)
t t.
Einite f softmax emror
interpolation
Here c22 the one-hot vector with a 1 at position k; index and O elsewhere, and
k; G(k:) E [do], with k; argmin (-2x, w; 2t, + Lo L&) k, (0.1, 1-
where G [p] + [dg] denotes any set-to-constant function sending each selected interpolation index k; into an appropriate integer k [do] for E [n].
Remark D.1. We remark that, the same in-context approximation guarantee holds for bias-less truncated linear model (i.e., generalized ReLU) Range(a.M) (w: 43) 1,)e%.
Proof. Define A Rdxn (3d+m))x for the input sequence X
X Wa
Tad+n On (nx(33d+m)
0(3d+n)xn
A(X)
& t
W. In
+
In
t In
In
token-wise linear
positional encoding
(3d++)) xm
Thus, A is token-wiss linear layer augmented with positional encoding, as it applies a linear projection each token and then adds unique per-token bias.
Let be precision parameter, without loss of generality, let it be divisible by 2 and denote p/ - 2) as H.
Now we define the multi-head attention Attn of heads. Denote 4 = following Definition D.2. Let Cg 2k:. We denote the h-th head Attm,, and define the weight matrices as
k(Lx + Lo) for E [p]
Odxd
2Ta
2 1)(n - 2) I
0axn
0
(h)
B
Oxxd 01xd
01xd
0 01xd
01xn E(h ((h1))(n-))-
E ((h11)(n-2)
(n(n-2)
01xd
01xd
01xn ((h-1)(n-2)- 2)
Cih ()
... Ch(n-2)
(d+2)x33d+2n))
Ia
Oaxed
0axn
0dxm
wilh)
=
O Oxxd
0 0xx2d
0ixn
11xm
O Oxxd
01x2d
lixn
01xn_
(442)x(34+2h))
(h(
0z (d.x(3d+1)
L(n-1)(n-2) nts 1(--1j(n-20) 22 1Xx 2)
Lngn- 2)
0a.
for every h E [H].
Here 8
coefficient we control the precision of our approximation. The attention
reaches higher precision as 3 gets larger.
Let With the construction of weights, we are also able to calculate the K, Q, V matrices in Attn
(())_ w(t) A(X)
25

---

Published as a conference paper at ICLR 2026
X W
I
In
22
0 Ws
Ws
(n
1)
Wx
(k)
(16)
Cn (1)
Odxd
-21d
22(
1)
2) 1/4a
0dxn
0
0
0
- 3-
01xd
01xd
01xd
01xn
l( 1
(n(n-2)) 2})
0 01xd
01xd
01xd
01xn
C(h 0(1-1)(1-2)-1
c(h-1)(n-2)
Ch(n-2)
(3d+2)
21
322
In
0 W0
1 W0
(n
1) Ws
W
Ws
W
11)
( en (1)
en
(3d+2n) xn
2[ () 2)
1|w
2h(n 2)w
-
(2=1)[(=22)1
(2(n2)
(D.2)
1(h-1)(x-2)-1
ch(n-2)
(d+2)xn
where the last equality comes from multiplying X with O, thus this is extraction of non-zero entries WK.
For Q, we have
Q(n) = =W A(X)
X W.
la
Odx2a
Oaxn
0axn
0 01xd
01x2d
01xn
1ixn
In
01xd
0 0xx2d
1ixn
01xn_
In
2m)
X lixn
(D.3)
11x0_
(d+1)xx
For V, we have
((h)
whO) A(X)
X W
=Oodxxad 0d
0d.x1
L 1)(n - 2) ((n--10--9))
Li(n= (ainn-2)-a 16 1C
Baco-
0d
t. T
In
d. (3d422))))
(3d+2n)xx
26

---

Published as a conference paper at ICLR 2026
Odo L(h-1)(n ((b-1))(-2)%k kea 1)(n-)) L (1--1) kr 11 -
En(n Sh(n-2)-11 10-19kain k)(n-2)-1
Odo
doxn
(D.4)
Given that all ky, where [p), share the same number in [do], denote this number by kg. Hence we rewrite (h) as
v(h) [Od. 1nn- eka
Ln(n-2)-1 Od
We define my as
m. max max [813.
By the definition of V(h), we have
V S max (L.} S m
(D.5)
P!
Remark D.2 (Intuition the Construction of (())), ) As previously mentioned, L, for E [p],
are all the interpolation points. In this context, (h) encompasses the (n 2) elements of these
interpolations (i.e., (h- (n 2) to h(n - 2) 1). Meanwhile, the value the two ends of V are both set to 0a,, because we suppress the head and let it output O when the input X is not close enough to the interpolations of the head.
Now we are ready to calculate the output of each Attna
Attny (A(X))
((M) Softmaxx( (Q(h))
[ - 1) - 2) 1/
2h(n 2)w]
X Lixn [tix
Softmax
-B
((1-1)(0-2)-
(
G(h-1)(n-2)-
Ch(n-2)
where last line is by plug in (D.2) and (D.3). Note the i-th column of the attention score matrix (the Softmax nested expression) is equivalent to the following expressions
Softmax (acnaaxx(KK) (M)TT T
(Q())) ),
2( - 1)(n - -2 -1]w ((1-1)(a-2--
(h-1)(0-2)-1
X
Softmax(-8
lixn )
-2h T)w
()(n22) Ch(n-2)
tixn_
-[( 1)(n - 2) 1|w T xx ((b-1)(n ()(n))) C(h-1)(nn ()hn-1))--2-11 -t"
-2(h 1)(n 22)'" x E(1 11111)(n-2) 1)( C(h-1)(n-2)
Softmax
-B
-2h(n 2)w x, (n(n-2) 2) Ch((a22) -
(pick column i)
(h 1)(n 2) 1](-2w T x; + I 1) -1 + Lu) 2 1) 2) 1/6
(h - 1)(n - 2)( (~2w x; + T-p 1)(n-2) + Too) 2(h - 1)(n - 2)
Softmax
-B
h(n - 2-) Txx
xi + En(n-2) + Σoo - -2h(n 2)
27

---

Published as a conference paper at ICLR 2026
2x w- 21 + Lo Ln ((hh1)(n2)--)) 1(h 1)(n 2) 1ALL1
B
(-2, w 2t Lo + Lih (h- 1)(x (h- 11)(1 22)
Sootmax
AT.
(-2x) w + Lo 2))))2)) h(n - 2)
(By mutiplying and dividing by AL)
2x, w 2t + Lo + L(h 1)(n 2) (L 1)(n 2)-1 Lo)
B
1-2x, 2t Lo + Lb- 22)
(L1(h- 1)(n Lo)
= Softmax
AL
(-2xr w -t Lo + Ln)n (In(n-2) - Lo) (By KAL La -Lo)
2x,
T w 2t) Lich (0hh1))1
(1-11)(n-2) 1)(n-2)-111 + (1( 1)² + a + t)²
B
-2x 2t) L(n 1) + (L(h-1)(n-2) )2 + (z) t)²
=Softmax
AL
(-2x, w - -11) Tun(n-2) + (In(n-2))² (r. LeTun w + 1)2
(z w + t - (((n2))-1) 1
B AL
(x. w + L(n (0--1)(0 1) 2) )
Softmax
(D.6)
:
(x] w T (m))))
Here, the second-last equality arises from the fact that the softmax function is shift-invariant, allowing us subtract and add constant across all coordinates. To be more precise, we first expand the product for k-th coordinate of the column vector
(-2x) w 21 + T.o + [Tx - TTo)
(-2x, w 2t + Lo + 12 2rr w - w L. Lo
(-2x) w Lt + L (-2x, Lo - 12
the coluumn
Then, dropping the constant and adding another constant (x, w + 8)2 across all coordinates, the above equation becomes
(-2x, w- w 2t) + L3 (I. [e.Twr. +1)2 (I, w +t- 2x)
Hence we finish the derivation of (D.6). Thus we have
(x w + Lig -(h-1)(n
1)(n- 1) 27
8
(a. w + L(n 21)
(A(3)) ( Softmax
(D.7)
AL
(x) w + Lisn 2))2
For specific h, we calculate the result of (D.7) column by column. Let X; denote any column (token) of the matrix X. We partition the situation at each column (token) into three distinct cases:
Case 1: w X; + is strictly within the interpolation range of Attn, (X E [Lch-1)( 2), Ia(n-2)-1) This excludes the following range at the edge of the inter- polation range of
[L Li 1)6n 1)(122) 2)) U [In(n 2)-1 Ln(n-2))-
28

---

Published as a conference paper at ICLR 2026
Case 2: w wTx, + t is not within the interpolation range of Attn
w T X, +
Case 3: wt X, & on the edge (region) the interpolation range of Attmg:
w T X; + (L 1)(a- 1)(a-)))2220)) 2) L(e 1)(n - 2) ([n((--)) 2) In(n-
Two remarks are in order.
Remark D.3 (Cases of Single Head Attention). The H heads split the approximation of the truncated linear map across disjoint intervals. For head h,
Attna (X) Range " ((h-1)(n- 2) 1) s MMn Mxn 211 (X)llo E1.
where is arbitrarily small. With this understanding, w' X, +
Case 1: falls into the interior of the interpolation range of the h-th head Attnn, denoted as Rangela+ ((ta))(((())))))) -))-))))--pa-aaaaaie
Case 2: remains outside of the interpolation range of the h-th head Attm
Case 3: falls on the boundary of the interpolation range of the h-th head Attm,.
Remark D.4 (Cases of All Attention Heads). According Lemma D.2, for all heads in Attn H there possible cases:
Case 1 x falls into Case for head, and Case 2 for all other heads.
Case 2*; falls into Case 3 for two heads with adjacent interpolation ranges, and Case 2 for other heads.
This also means that when Case appears in Attn the situation of all head in Attn #f falls into Case 1* And when Case appears in Attn H the situation of all head in Attn falls into Case 2*, Thus, We discuss Case 2* in the discussion of Case 3.
Case 1: X2 E [Zqh-11nn-2) In(n- 2))n In this case, our goal is to demonstrate this attention head outputs value close (,, (w X, + t).
Let L, and L,41 be the two interpolants such that
w X; tte [Lo,
(D.8)
Then, and + are also the labels of the two largest entries in
(w X; - L 1)(n 22-1) 1
B
(w X, + I(p - 1)(n )2
AL
(w Xx + Ln(nn2))
29

---

Published as a conference paper at ICLR 2026
since
3
(w X; + )2
argmax
2
2)}
AL
argmin
T Xi + - L2a)²
argmin NE((0-I)(n-2)-11Mm--22
w X; + Lxl-
We also note that the distance of w T X; + interpolants beside L, and L.41 differs from w T X; +
for at least L, L,-1 = (b - a)/p or L,+1 L, = (b - aa/p.
This is equivalent to the occasion when #1 I' in Lemma D.1 is larger than
max
B
(w
X 12- (x, - Lo)² -
3 (w" X; + - X; + -ww"
=2ot))²}
AL
AL
8 b
12
AL
P
which is invariant to X₁.
Thus according Lemma D.I and the fact that the and s are the two largest entries in the i-th column of the attention score matrix, we have
(w" X1 + Lgh- ((nn-1)(n2)-1)) (w X; + t -((h-))(a- ())
-06
Softmax
AL
1
36 Es
1 1 e
85
Cx41
S 62
nx1
(w T Xi+ -In(n-2)) 12
for any > 0. This yields that
Tw X, +t - -Len 1)(n [(h-1)(n-2)) 2)(11 2
B AL
(w T X; +t LL ()
e 85 Cg V
V Softmax
:
V
1 1--8
+ e Cs41
20
(w) T X2 + Liin (2)) 22
(w X; + Lin 1 2) 2
B
(w X; t L 1)(1) 22) )
e
Softmax
1+ 36 6x
est1
V
AL
1 e- 36
x
(w T X; + I )
|V
This is equivalent to
e -96
1
SKoommax Q)., QQ)
1 1 e- L(0-1)(x-2)+0111
1 e-8 I(h- 1)(n-2)+sEke)) ll,
< ||ooo C2
(By |A
|||||
[B] (D.9)
< m,,22
where the last line is by (D.5).
30

---

Published as a conference paper at ICLR 2026
From (D.8), derive that
e
Len 12(n-)((n- (in-1)(m2))4---1 2) + c- 36 [n 1)n--)(n2))+ - (w TuuTx, + t)ekolll
1 1+ e 88
8-
6 8
(I e -8
(w
X; t)eka) 1l + 1+ e-8 (I
(1(n-1)(n-2)+s (w X; t))
(y convex combination (w" X + t) and triangle incquality)
1
b b-a
e
a
<
(By (D.8)
1 1+ e-
1 c 36
b-a
(D.10)
p
Combing (D.9) and (D.10) yields
||Voftmax (K Q)., (w T Xi + 1)
e-
< /Softmax K Q). 1 1ob-1)(n-))t--- 1 e e-8 Iin- 1)(x 1)(n 22)+oloc
1
1 e 100 20--1
T 06 L (h- 1))=)))==)+++ (wTx; t)ttaalla
(By triangle incquality)
b-a
5mmp2 +
(D.11)
p
where the first inequality comes from adding and subtracting the interpolation points' convex combi- nation and then applying triangle inequality.
Case X [L(b-1)(n-2) 2)-12-1--11 In(n-2) 2)}- In this case, X, falls out of the range of interpolation covered by Attng.
Without loss of generality, suppose w X; t lie left to the range of interpolation of Attng.
This yields that (((--))(n2)-1 the closest interpolant within Autn to w X, Furthermore, the second closest interpolant ()(=)) is at least further for at least (b - -a//p. which is constant irrelevant to X;
Then by Lemma D.I, we have
(w T X; + 1- L(h 1)(n2))(222))))) 3
B
Tw X1 + t -Lu- 1)(n ()
Softmax
El
Se,,
AT.
(w Tx, + [ )2
nxl
for any C3 >
This yields that
(w T X; + - Lip- 111n 1) 2
B
Tw, X; + Lin 1(n-1))m-2)) 1)(x )2
SSotmaa
e1 1oo0 ax1
AL
(w Tx + t -
V|loo 63
(By || S ||||| [[I]
E3
31

---

Published as a conference paper at ICLR 2026
where the last line is by (D.5). This is equivalent to
(w X; + Ligh (nn 2) )
(w ToTT X1 + [L 1)(n -n) 22) 2
V Sootmax
Odl
< m.eg.
(D.12)
AL
20
(w X; + [2)
According to Lemma D.2, when Case occurs for one head in the H heads Attn", all other head will be in Case 2.
Case 18.
Combining with the result in Case 2, we have the output of all heads as
||Attn " (A(X)):, (w X; + t)ekalla
= Σ
Attn A(X)..lloo + ||Attn, o A(X).; - (wT X, + +texe looo
(O)
b-a p
=H 1) + m2 +
(By (D.11) and (D.12)
b-a a H(n 2)
= (H 13 + m.e2 +
Setting e2, 63 to be
60
2
2(H 1)m
yields the final result.
Case 3 (and Case 2*): X E ( 1)a-))))22)))))))))))) [ 216- In this case, w. X; f is the boundary of the interpolation range of Attmng By Lemma D.2, it should also fall on the boundary
head with neighboring interpolation range. Without loss of generality, we set it to be Att Furthermore, Lemma D.2 indicates that w X, + should fall on no other interpolation range of any heads beside Attm and Attun--1-
Combining this with case 2, we have
Aun # (A(X))..
Σ Attng o A(X)..
[[-(H 2)m + Attn A(X):, + Attn A(X):.) ((I - 22)m, + Attmno a A(X).. + Attm o A(X)..)) (By (D.12))
By Lemma D.1, 8 denote
8 = L L ((t--)(a--)))) ()a-2))+
(w) X, t)eka - -Lta (L -w Xx t)ekal.
have
1
e e 96
8881 +
1 35 62)1 S c4.
32

---

Published as a conference paper at ICLR 2026
and
(I (Q(l-11) -
1+ 1 c- +
1
1 86 en S Es.
96
for any <4, 65
Thus we have
Softmaxxx((((()) (()(() + p(h (ottm (Q(h-1))
1
e
e6 96
1
e e
-V( 1te-00 61
1
62
1 1+
-n- +
1 1 38 en en)
$ (e4 + es).
This is equivalent to
(otoD))Sommax(( ((1-1)) (((hh)))))
1
c66
e
88 0+
1 B6 Cka 1yn- +)+ + 1 1 ( (1-10a222-
1 e- 88 Cko) 01
$ |V (ca + ct).
Thus we have
Softmax (K ((11)) + v(h (ofttax 1((-11))
e 88
Ite 26 Cbg [(h- +
Ite I Cko I 1)(n 2)
S (ello +6))
which implies
-88
Autm, (A(X)) - 005 eke 110 +
1 000 tko Lc (alil-i)nn222)))) -
H 23 + IV (ca+
(D.13)
Finally, since
e-3 38
b -
1 Cka L(h- ()n-)))s
38 Cka ((th- (w Twxx, X; + t)kka 1ll0 S
p
(By (D.10)
combining with (D.13), we have
Atta, (A(X)) (w ToTx;++ x))
H
-88
Attnn(((X)) -
35 Cko T 1(h-1)(n-2)40 +
+ e-8 Cko Iuth-1)in-2)+-- 2)+
1=1
98
1
||(
e Ckc Lib (((h))(an-)-)))
1 15
(1 - - (w TuTxx + t)Eka llo (By triangle incquality)
b a
(H - 23 + (e4
p
33

---

Published as a conference paper at ICLR 2026
b (H 2) max[la), 16|tes + max[[a], [b|{(es + ts). Hnn - 2)
Setting 63, 64, 65 be
c0 63 3(H - 2)
64 E5
yields the final result.
This completes the proof.
Lemma D.3 (Attention Prepended with Token-Wiig Wise Linear Transformation Still Transformer).
For any attention Attn and any linear transformation A, Attn A is still an attention.
Proof. We denote the transformation matrix of A also as MA. Denote the attention Attn
Attn(Z) = Wy ( WoZ).
Then we have
Attn A(Z) = WW. M
It is a new attention with parameters Wx.Ma.WMM and Wv
Lemma D.4 (Lemma 14 in (Bai et al., 2023): Composition of Error for Approximating Convex GD).
Suppose f _Rd + R is convex function. Let w* argmin f(w), R 2 2||w= 12. and assume
that f is smmoohh (R). Let sequences Jezo C IR and {wED Jezo Rd be given by T W = 0,
w++1 = T0 -7V((()) +é,
1
s+1 WOO n f(w())) GD
for all 8 2 0. Then as long as n S 2/ L,, for any 0 s L - R/(2c), it holds that | wEDlla s Le
and | 2| <
R + L
R.
Corollary D.1.1 (Corollary A.2 in (Bai et al., 2023): Gradient Descent for Smooth and Strongly
Convex Function). Suppose L : Rd + 18 is a a-strongly convex and {-smoooh for som 0 < a S 8. [(+1)
Then, the gradient descent iterates W
wan L(WE)) with learning rate n 1/8 3 and
initialization w&D E Rdd satisfies for any / 1,
-4)
IluED w11 < exp
- - -w'13
exp (-1) 1lw@D - w w1
I(WED) I((w)) < 2
where x B/a is the condition number of L, and w² =- argmin L(w).
D.1 PROOF OF THEOREM 3.1
34

---

Published as a conference paper at ICLR 2026
Definition D.3 (Interpolation Points). f. ie.. the range of w y:
Define P + 1 interpolation points of the effective domain of
L; Liin + 7 (Lmux Emnu), for
where [Lmin Lmax] is bounded interval containing all values of w x
Theorem D.2 (In-Context Emulation of fww"= y)æ with Single- Head Attention: Theorem 3.1
Restate). Let [Tmin [max] be bounded interval containing all values of w y, and let
X
22
In
b(d+1)xn
and
W
w
w] Rdx=
1/2
yn
where E Rd, E R, and Rd is the coefficient vector. Define the input as:
En
Z =
1/1
1/2
3/
=
W
E R (264 1)x+
(D.14)
Assume mIx [
I B. For any continuously differentiable function f IR. - and any > 0, there exists single-hear head attention Attn, with a linear layer Linear such that
||Attn, Linear(Z) [s(w] x 21)
f(w In yn )xn] lloe
for any 0.
Proof. We define the linear transformation of as concatenation of two functions with some manual padding of zeros:
Linear, (X)
Linear(7) (7)
Linear (W) 0(2d)=+))xnP
2(d-m+2)xn(P+.)
where define Linear, IR (2d++)2))xx((PP) and Linear, E (2)+++2)xx below. We define Lincar, as:
Odxe
W
-ixn
-lixn
la 0ld+n+2)xd
Lineaww(W) =
W + dxn
Oaxn 1 1ix In
Oaxo Lixn In
(2d+n+2)xx)
+2)+
(2d-
We define Linear, as:
(X)
Ta+1
x [ox((- 2Loe:") (n) 2 (n)
2Lpe(a) (n) (px(n-9(P41))
0 ((a=1+))((++))
(d+1)xx
(044n+2)x(dH+)
nxn(P+1)
Odd
0(241)]
Ia
Og
X (oxx((-))P4)) f(Ta)e {(TA)e
S(TT)c)))
Onx(n-ij(++1)
(m+1)xxd
Op+1
(d+1)xx
nxn(P+1)
(2dd-)
35

---

Published as a conference paper at ICLR 2026
(244))((44))
(124)))((44)
5
1Ix(11)))
Cel (Ix(P+n) (2(+2+))x)(P+1)
[71
T2
T...
(2d+n+2)xm(P4))
(n) where {1,))=0 are the P + 1 interpolation points (Definition D.3); 6, E RRt is the one-hot vector with index and elsewhere; C' is constant to determined later, and
1x(++11 = [1
11.
Ix(P-1)
=
L
-L]
[p]
1x(P+1)
L
2L
2Lpx
Looy
2L18
2Lryi
7,
(Loo)
[(L))
[(Lp)
T..
-lap
Cel
(n)
Ce
Ce
(n)
(2
So our Linear(Z) is:
2
2Lp
2
2L
2o
2Lp
Lo
2Lp
T
T2
Ta
[(Lo)o
[(Lp)
I (Lo)an
[(Lp)
Waxn
OdxuP
-b
-L
LP
-1ixn
O1xPP
Ce
Ce
Cen
Cen
(n)
Lincar(Z)
Odxn
OdxnP
Wdxn
OdxnP
1ixn
01xnP
lixn
01xnP
In
OxxnP
0dxn
0axnP
1ix
01xnP
In
OnxuP
2(24m++)xnn(Pt))
Now we construct WK. Wo. Wv, Wo to be:
WK T2a+n42 2(244==2)x(244+++2)
(2d+n+2)x x 2(2d))
We = (0244++2)) [2d4n+2]
Wy = Oax
Ia (2
dx2(2d+n+2)
In
Wo OnPxn
n(P+1)xn
36

---

Published as a conference paper at ICLR 2026
Thus,
W WxxLinear(Z)
[
T2
nn.
(Wi selects the T, blocks in Linear (2))
(2d++n+ + 2) 11(++1)
Wdxn
OdxnP
-1xx
01xPP
Wo
Oaxn
OaxaP
(Wa selects the bottom (2d n 2) rows in Linear (Z))
lixn
0rxar
I
Onxur
(2d+n+2) xn(++1)
Wy-Linear(2)
F1
F2
Fn..
(Wy selects the (d 2)-th row in T:)
dxn(P+1)
where we define F; as:
F = (((L)) S(h))= [(Lp)a))
dx(P+1)
Therefore,
Attn, o Linear(2)
WyLineer(2) Softmax, (WW..e/erWWWLLeeeeeeeeea W WoLinear(Z)) Wo
x(P+1)xn(Pt))
Waxn
OdxnP
1ix=
01xnP
In
F2
Fa Softmaxx [ T2
Tn]
Odxn
OdxnP
Onpxn
(D.15)
1ix
01xUP
1++1
a( (2d++m++))
Tn
OnxnP
n(P-1)xn
(24+m+2)xm(P41)
For simplicity of presentation, we define
Ti
T2
Tx
x22+t))(26+++2)
For the Softmax, part in (D.15), have:
W Winnncar Z)) Wo
Waxn
Odxur
11xm
01xuP
In
= =Softmaxg(
Odxn
OdxuP
(By the definition of 7
Onpxn
((P+1)x(2d+++22)
lix
O1xmP
In
OnxnP.
n(P+1)xn
(a4+x+2)xn(P4)
37

---

Published as a conference paper at ICLR 2026
Waxa -lixn
OdxnP
01xnP
=Sotmaaxx(
T
Oaxn
T
OaxnP
Ia Onpxn m(P+1)xn
1ixn
01xnP
In
OnxuP_
n(P+1)xXP
(By distributivity of matrix multiplication over block concatenation)
W dxxn
OdxpP
lixn
01xnP
In
Softmax (T
Oaxn
Softmax (T
OdxnP
Onpxn
1ix
01xnP
In
OnxuP_
n(P+1)xn
n(P+1)xn
n(P m(P+1)xmP
(By the column-wise operation nature of Softmax,))
Waxn -1xxn Oaxn 11xn
Softmax;3 [T1
T2
Tx
)
(
Iu (owexn
selects the first Softmax, block)
((P=1)x(2d++++)
In
(22)x)
Since our target is a token-wise approximation, we focus on single token. We consider the e-th column (c (n]) in the Softmax, part, and we have
W
T2
1
( "aaaarr WaLinear(Z)) Wol. Softmax
Og
1
Eec
n(P n(P+1)x(2++++2)
(2d+++2)x1
Mi,e
M2,0
Softmax
M Mn.
n(P4))x1
where each sub-block Mi,, E (P+1)x1 for E [n] is
w
Mc. =
0a
xP41)x
(2d+n+2)xx
2 T
2LoMh
[(Lo)a
-L3 c(e(m)) T
2L
2L1Vi
f(L))o]
-13
c(e) ( T
1
0,
(By transpose of Ti)
2LpxT
2LPb
f(Lr)=]
-
cT
(2+1)x(2d+a+2)
(2d+n+2)x1
38

---

Published as a conference paper at ICLR 2026
2 w 2LoV/ L + Clizc 2L,0, -L L + Clime
2Lpx, w 2Lr L3 + Cllize
(P+1)x1
where i= denotes the indicator function of = c.
For simplicity, let
4 = 2L,x; w 2L - Dj.
for jE (O....,PP
(D.16)
such that
Ug + Clizc
(
+ Cli
M1.-
" + Cl
(P+1)x1
This means that
(Softmaxx (Wx Linear(Z)) (Wxiiarrrr T W WoLinear(Z)) Wo).c
M1,c
M2,0
= Softmax(B
M
x(P+1)x1
exp e B(u) (0) +c1==))
(n(P+1) ((-D)P+))+H)))
- exp Bluf) + +Cl==d)
n(P+1ix1 (By the definition of Softmax,)
Thus have
Attn, Linear(Z).n
Wy-Linear(2. (Z)
(Softmax;((W Linear
(2) Liner
Wo WoLincar(Z)) Wo).
P
exp ((u) ( +L1==))
F1
Fn
(m(++1)
2j'=0 exp A(u))) (P) +11v=))
(EDD(P+))++))
dxm(P+1)
n(P+1)x1
[S(L))
[(p))
((LO) s(Lp)
(By definitoin F:)
dxn(P+1)
exp(Bluf C11==))
(n(P+1))
P
exp Blu))) -CI
((-D(P+D+GH))
n(P-1)x1
P
exp B(u +C
E exp B(u (3)
CDv=c))
#=
39

---

Published as a conference paper at ICLR 2026
(((L)
f(Lp)01
f(Lo)an
(n(P+1)) f(Lp)nn)
((DD)PDD+UA)
dxn(P+1)
n(P-1)x1
(By distributivity of matrix multiplication)
B(u + +
[(Tgg) 3i.
i= j=0 2i'=0 exp Blu ) + +[N==))
dx1
(The one-hot vector retrieves the ((i 1) (1 1))-th column)
Again, our goal is to approximate f(x w Ve) with:
exp exp{ B(u -((=o)
P
Attn, Lincar = Σ
f(L,)az.
(D.17)
EP=1 - exp Blug)) C(V==))
We start to analyze the summation of weights
E for = and * We use the result of this analysis to bound our target approximation | o Linear(Z).e f(x w - ye)xelloo later.
For every i E [n], if + have
o cup(
(By Diye = ffr +
E Ey= exp Blug) (1)
Ef exp Bul
( (2)
(D.18)
Σ = exp B(ug) (1)) + {c}
S 60:
(D.19)
where (D.18) by taking only the 1' c term, and the last line by the softmax-shift equality
E E e"
E eny+C ec E E"d
for any constant C and choosing C = M- Eq (max, Lj) (2dB² + +BB In with Eo > 0.
Thus, the weight assigned + cis tiny.
'More explicitly, recall (D.16): u = 2T,z 2T, 1.7. Since max([[XX]c,]111111 S B, have
| B, lnal < B, || B,
which implies [| I dB. Let L, = max; Li For fixed pair of i, i', we have
50 v 2Lg ((x, - 23) w (y. - -w))
(((x; L1
vz) T wl + ln ))
(By triangle incquality)
< 2L. ([lz, - æ [| + 1p will
(By L. := max, |b,l and Hölder's incquality)
< 2L. ([]x)) + +11x)<1o0)) [|w]la + b.l+ + b))
(By triangle incquality)
< 2L.
(By 1120//00 B, vl B and ||w]] < dB)
< 2L. (2dB" + 2B) M.
40

---

Published as a conference paper at ICLR 2026
For i c, have
Σ)- exp B(u +c})
m/ Ej - exp f(u + +C1==0)
Eife Ej= exp Blu 1 + cli=d)
EP= Ej'= exp Blug ( + Clv=z)
(By Eifo Eyso(..) ) +isc ---0(---= (D.21)
=
21 (n 1)E0,
where the last inequality follows from (i.e., (D.19))
Σ Litc Eラ= exp B(u,) ( + +Cliz))
$ (n 1)E0.
E =0= exp Bluy + CDp=e)
and setting 0 < co 1/(n 1). Therefore, the weight concentrates i
From (D.19), (D.21), and our target approximation
||Att Linear Linear(Z).c f(x w - velooooo
P
s +c11=0)}
[(1))=; [(x w ve)eelloo: (D.22)
0= -x=1 E exp p(u)))) (2) -C1=e)
we split (D.22) into terms
exp B(u))) + +11==))
f(L,)=; f(x. w vc)
P exp B(u (2) +Clr=d)
i=
=0=0
exp
f(L,)xx
= = exp 3(u)) +CI
P
i
1=0
P
exp 3(u (8) +1
f(L,) - f(x w ye) xe
exp Mlly
(9)
+ C(1==)))
j=
(By splitting the summation over i into two parts: = and * e)
Hence, we have u.t) < u(()) M, which implies
an S LaMaaayy
for all j e (O....,P) P}.
(D.20)
Then, (D.18) becomes, for any constant C,
Σ/ exp Seu (1)
3M Epe exp Bu(
B(M-C))
exp(3C) Eo exp (3((0)
(1))
eC Ei -o exp [n
Chonsing : M 1 In (max, L,): (2dB² 2B) Inco. we obtain the desired bound eg-
41

---

Published as a conference paper at ICLR 2026
exp Spp(3(
P
exp Blul)) [ [1b)))0:110
(D.23)
Σ
P
#e 0
=0=0
P
exp
Blu 10 +0]
f(L))a - f(x w vo)xelloos
== p= Ej'= exp Bluy
P
(8)
+ cl
(IT)
(By triangle inequality)
where we are capable of bounding term (7) with (D.19) and term (IT) as follows.
For term (7) in (D.23), we have
(1)
exp B(u
n
f(Ly)xxlloo
= f = exp B(u + =
i j
exp 3(4,0))
f(Ly)xillo
(By triangle inequality)
Ex=1
j =0 exp B(ug) + Cll==))
P
ie
P
exp 8(u
|f(1))xill>
(By non-negativity of exponential)
exp Blu + +1L==o))
ie j=0
s(
P
ΣΣ
[f(L)] 112,11x
2im mml E
0 Blu (7 Clv=ol)
ifc
(By [[ = (5(())) -Imi)l)>))
Life Ej=o exp {(
By B
E Ep= exp Blu}5) + C1v=e)
(By By = max [f] and max (|o [1o] S B)
(ne
(By (D.19))
where we define By = max Ifl as the bound for f.
For term (11) in (D.23), we have
(II)
Bul +01}
exp
[(Tyg) Fc -1xx w ye)
Fe 1oc dx1
P 1=0
j' = exp
B(u (9) + +(1==))
dx1
P
exp
B(u +0]
(f(L,) f(x. w - ve)
P 1=
Ek exp 3(u (lr=o)
Σp- exp
Blu + +01}
-
f(x w Nc)xtello
Σ == EP exp
B(( (1) +CV==))
(By E, 2g B, D E, 3 D) - (1- EeA2)D)
42

---

Published as a conference paper at ICLR 2026
P exp
Blu, +01
o Alu =0}
(f(Ti))te [(x w vc)
Σ ='==0 exp p( (0) +0]
P
Ex=1 E exp Blub
(1) Clv=dd]
1=0
Σj exp Bl +0]
-
f 1 vc)xelloc
x=11 Ek=o exp Blub (1) +11==))
EB (B, - (1- E 12 ) = =E 2/2 [ D) (1- E (1-2)))D)
exp Blu + +01
(f(1,) -f(x -yc)))
P ) - exp B(u, +0]
j=0
Σ Eyz exp Bluy (c) + +0]
(1
f(z w vo)xollo
(By 5 <))
Ep= Ekeo exp
Blub (i) + +CIv=d))
exp Blu + +01
(5(t,) SHx w -ya)l ||
Dg =0=0 exp B (c) +0]}
Σ/ exp
B(ugg + {1}
- -(1
1f w - ye]l |
P= = exp B((uk) (0) + +1v==))
(By triangle inequality, and |ae|| ~0 |a| || where IR and Rtt)
M(u) (c) + +01
exp
If(L,) f(x. w --oll | + (n - 1y
28 exp B(u +0]
j
(By (D.21) and By == max
exp Bny 3xp (0)
P
[f(1,) - f(x. w -e)l 1 + (n B,
=0= exp B
P
1=0
(By exp B(u) (Bu)
+ +c1] = =xxp( exp(BC) and max (IIx [W]| B)
exp - 3(x= Ye -,,
=0 expl - -3(x, w Be L, -I((T)) f(xx w ve)l ||aee|oe + (n By.
=(I1-2)
((1-1)
(D.24)
where the last equality follows from completing the square
4 =2L5x w 2L,ye L3 (L, (x. w -ve)) + (xx w yc)²
For term (TI-1) in (D.24), we have
(11-1)
exp - [xx T w Be 2
Σ
-f((T)) f(x w ve)l ||
== exp( - (rr [.w ye 1,,)22
exp 13 3xx
w - Bc - L,)
Il(L,)) -fxx] w - vc)l 1x
L; [n_ SAL = expl (x. w ye 12
43

---

Published as a conference paper at ICLR 2026
P Σ
exp -3 _ Yc [ Ej expl - 3(x w - Ve - 1,
1f(Lg) - f(z w Uc)l |
b1 (0? w- Do
(D.25)
where we define AL = (Imax Impiu)/ / P and divide the interpolation points into two groups with one group least AL away from x. Yos and the other within AL.
For the first term in (D.25), we set AL to be sufficiently small (P large enough) such that,
((() - s(() S c1, Vel > 0,
when I ---th S AL.
For the second term in (D.25), we set 3 to be sufficiently large such that
( -3xx T ye =,,)3 S C2. -xxx
Σ
(D.26)
vo) E expl 3ax Yc 12}
j11,- w
for any 0 < E2
Thus, for term (II-1), we have
(II-1)
exp - w - Yo - L
Σ
[f(Lg) f(xx w Uo)l ||00|l00
=0= exp( - [ w yc 13
exp (2x w Be -1
1s(1,) {ax w voll |
P L exp (zx Ve 22
J: (x] we
- w 2e L
H: (Ir -o SAIL Σ exp( -(xx w Ve 12))23 .1
expl - [xx T ye 10--1 2
5:14y (x] w- AL Ej-=0 exp - Bxx - Ye 1o-s))) [2 (lf(L,)) + If(xTw w vc)l)
(By (s(L,) (x= w - yc)l c1 max(1IX1] olc [| o1 S B, and triangle inequality)
exp { 30x _ w Uc 1
1:L, (x] VSL ES- expl - B(x w Me - 1= -6
expt [xx T w Be - L,)3}
2B B
(By By = max (fl)
Jil,, (&T ALL =0 exp { - Bxx _ w ye -1;))
exp -xx T w
B 3 c2 2B, B (By (D.26)
J. (N. wi- SAL 0 expl B(x. w yc [2
$ B B+G 2.. 2B, BB Combining (I), (II-1), and (11-2), we have:
(Byx11)
Attn, o Linear( (2),e f(x w veleelloo & (n L)eo BeB + 2e, 2,, B (n 1)
from
from (TI-1)
from (11-2)
44

---

Published as a conference paper at ICLR 2026
Since co, 61 and 62 arbitrarily small, we have
|Attn o Linear(Z);, - f(x. w - -oooooloo Se,
for any c > 0.
This completes the proof.
D.2 PROOF OF COROLLARY 3.1.2
Corollary D.2.1 (In-Context Emulation of Single GD Step: Corollary 3.1.2 Restate). Let é R > be differentiable and define L, (w) := 1 Σi=1 E(w I; yt). For any step size rj > and any > 0, there exist single-head attention Attn, and a linear map Linear such that, with Z = [X;; W] as (3.1) 1), choosing the readout u == n, (equivalently, right-multiply by Wo = u in Definition 2.1),
have
Gu=ō
CGD == (Attn, Linear Z) E Rd
and |@ (w - VLn
1lc Sc.
vg
Proof. From Theorem 3.1 and Corollary 3.1.1, let f(.) := -ne(()) (.), and we derive that (Attn, Linear): (-n x; =l) for all i [n]. Let readout == 1 Then, have
n
Attn, Linear (Z))u
Attn, o Linear (Z));
n
V x; =; c'
VVVV((w +e'
Therefore,
" TGD w +
Σ
(Attn, o Linear( Z));
7
= 7/ (w)) +6'
WGD +
where WGD is the approximate and w is the exact GD iterate. This completes the proof.
D.3 PROOF OF COROLLARY 3.1.3
Theorem D.3 (In-Context Emulation of Linear Regression; Corollary 3.1.3 Restate). For any
dataset ((z,, 3:) P with x; E Rd E R and any c > 0, there exists a depth-Z L stack of single-head L-1 attention layers (Attn' I=0 ) linear maps (Linear") L-1 and a readout u E R such that the iterates 11=0
11+ = Winnar + (Attn' o Linear' (Z))),,
È t 0,0,...,4.
with z : [X; and W i
linear in (3.1) (for any fixed bounded w²). satisfy
| Winnar 11 30 S e,
where Whinear := argmin
2n 1 Σn ((w, xx) 12
45

---

Published as a conference paper at ICLR 2026
Proof. Define the squared-loss objective
(w)) = 2n E (ww, y:) Whinea = arg min Ln (w).
Assume L, is a-strongly convex and B-smooth, and take stepsize 1/B.
Let 122 be the exact gradient descent iterates for minimizing T.n. By Corollary 3.1 1.1 each attention layer emulates one GD step with per-layer:
| finear
10x S Se/2,
1= 0......; 1-1.
(D.27)
Next, applying Corollary D.1.1 to L= gives
I. S exp
I Wiineur
| Whnear 112:
3/a.
Taking square roots and using ||
11l00 S yields
T.
1 Whinear 20 1 Wiineur 12 cxp
1
Wiinear 1/2.
(D.28)
2x
Choose L. large enough so that |luE Whinear |1 S c//2. Finally, by triangle inequality together with (D.27) and (D.28),
fneer Wlncar I 0o I | 1 w0Dlloo + 1 - Wlinear 1100 S E.
This completes the proof.
D.4 PROOF OF COROLLARY 3.1.4
Theorem D.4 (Restate of Corollary 3.1.4: In-Context Emulation of Ridge Regression). For any onput-output pair (Ia, yi), where I; E Rd Y/ R, E [n]. and any > 0, there exists a depth-L L stack of single-head attention layers {Attn 11=0 such that the iterates
LL-1 L-1 linear maps {Linear T== and a readout E TR
-1-
Widge (Attn', Linear (Z')), L= 0.0,..,,-11
ridge
with z = [X; and W
[wt Fidge ridgel as in (3.1) (for any fixed bounded w²), satisfy
| Wridgell S 6,
where Whidge argmin WER4
we 2n Σi ((1, y1)2+ 2 [| with regularization term À 2
Proof. Define the loss objective
[n(w) = 2n. Σ (10, - -1:)² +
1
1 1 2
Wridge == arg min (w)) DER
I, is a-strongly convex and 8-smooth, and take stepsize = 1/8. Let { twon be the exact gradient descent iterates for minimizing T.n.
46

---

Published as a conference paper at ICLR 2026
By Corollary 3.1.2, each attention layer emulates one GD step with per-layer:
|| WGDllo S E/22,
0,...,
(D.29)
Next, applying Corollary D.1.1 to L = L,, gives
L Wridge
S exp
Wridge 1
3/a.
Taking square roots and using || 11 S || yields
1| Woodgoloo
< WO - Wridgell2 S exp 2x
|
Wridge
(D.30)
Choose L large enough so that I wridgelle 1l S Se/2. Finally, by triangle inequality together with (D.29) and (D.30),
i Wridgell 0o S 1100 wOD 10,0 1
Wridge 0100 S c.
This completes the proof.
D.5 PROOF OF THEOREM 4.1
Theorem D.5 (In-Context Emulation of Attention; Theorem 4. Restate). Let X E Rgdx be an input sequence, and WK, Wq: Wy Te be the weight matrices of the target attention head we wish to emulate in-context. Assume XIl [ ||Wv ll I BRQv with B > 0. Then, for any 0, there exists a two-layer attention network multi-head attention layer Attmn followed by single-head attention layer Atin, such that
Attn, Attn (Xp)
Wy X (( X) X) 110 S
Emulator
Target
where X, is the prompt defined in Definition 4.2.
Proof. We state our high-level proof sketch first.
Step 1: In-Context Weight Encoding.
We define
= da
WK
Q dy X
W d, xd
da X
xd
dxn
di
x
dxn
da Xn
dxn
We aim to approximate the attention mechanism VSoftmax (KTQ Q) using two-layer transformer Attn, o Attnm- Therefore, the transformer Attn, o Attn must have in-context access to the information about Wx, We and Wy. This is equivalent to exposing the transformer Attn, Attnm to the target algorithm's 's specification.
To that end, augment the input sequence X with two auxiliary blocks:
1. The weight encoding Win of the target algorithm. Wi contains the vectorization of the target weights Wx. Wq and Wy.
2. A positional encoding Tn. 7n exposes token indices.
47

---

Published as a conference paper at ICLR 2026
Concretely, following Definition 4.2, form
X
X =
Win T
with
Win
0
w
w
2 w
(n2 -
1)
10
W
W
w
6dd,
+n) xX
and
W W
3dd,
Step 2: Multi-Head Decomposition for In-Context Recovery of K, Q, V. In this step, we use the multi-head layer Attum to build approximators of K, Q. and V from the prompt Xp. We denote these approximators by K", Q', and V", corresponding to K, Q, and V. Explicitly, have
Atta (Xp))
K
Q'
Q
1100 S ED.
3d,
3dg
Intuitively, this works as: Xp contains the raw input and the weight encodings WK. Wq and Wy. Then AttDm "reads" X and the target weight parameters from Xp within its attention heads to form the desired approximation.
Step Single-Head Assembly for Emulated Map. We use the single-head layer Attn, to perform the attention computation. From K', Q', V", Attn, produces
V"Softmax;((K")) T').
For reference, the target computation is VSoftmax ((tttmaxx((KK)) ((K) (K)TQ). with the target attention, using the approximated K", Q', V' as inputs.
Q). This step aligns the output of Attn,
Step 4: Error Bound. Finally, we bound the gap between the computed and target attention:
(K") T')) V/Softmxxg((K)) Q)1 (k))) ca nBxQvG.
Our proof starts here.
Step 1: In-Context Weight Encoding. For clarity and simplicity, define
k; = (WK).. E Rd
(D.31)
= (We). )r E Rd.
(D.32)
" (Wy) ) Rd.
(D.33)
48

---

Published as a conference paper at ICLR 2026
such that the vectorized weight matrices W K. Wq. Wy in Definition 4.2 become
h1
U1
12
92
W
TRddd
We
E Rdddy
W
E Rdd
K
kdn
gd
Ud
and to becomes
k1
kdn
W K
91
w
W Q
W v
Qd
V1
Ud,
Win remains as
Win =
0 w
1 -
2 w
(n - 1) w W
Redd, xn
W
Then, for the input X, we append it with the target weights Win and the positional encoding I, as in Definition 4.2. We denote this result with X, and write it out as
X W
Xp
in In
(D.34)
(d+ +
Step 2: Multi-Head Decomposition for In-Context Recovery of K, Q, In this part, we con- struct upproximators for K. Q and via Attn We construct the approximators by approximating each row of K, Q, V and then aggregating the results across rows. Each row in K, Q and V has the form: k. X, q. X, and n. X. To approximate these rows in K, Q. V, we apply Theorem D.1 each row separately. Namely, we allocate H-head attention to each row of K Q and V to carry out the row-wise approximations. Since K, Q, V E Rd Xn each K, Q, V uses H d, heads. We interpret // as the number of heads per row dimension, since each K, Q, and V has d, rows. Finally, we define a multi-head attention Attm, as the union of these three groups of Hd,, heads. Therefore, Att has 3Hd, heads in total.
We label the 3Hd, heads in Attn as:
K Attn R
E [d,], he (J+1. H):
(Approximates K)
Attn J
Q
[2da] [da], he L......... ..... H}:
(Approximates Q)
V Attn
j [3da] [2da], 1 J+ HH,,
(Approximates V)
where we define J = (j 1)H to simplify our notation. Each Attn Attn Q j.b and Attn V. is j single-head attention. Index j identifies the target row, and index h identifies the head allocated to that row. Here j E [2dr] [dx] denotes the set difference. That is, E [2dn] \ [da] means j E (dg, 11...,,d,, )d
j.K
49

---

Published as a conference paper at ICLR 2026
Thus, A consists of three groups of attention heads:
da
J+H
2d
J+H
3dp.
J+H Σ
Attnm
Attn
+
Σ
Σ
Attn
2
+
Attn
V J.h
j=1 h=J+1
du +1 K=J+1
2d
K=J+1
Approximates K
Appeuximates
Approximutes V
In the subsequent proof, we provide the constructions of Attu j,b Attn Q rem D.I.
Attn y J.b
from Theo-
J.K'
To apply Theorem D.I to construct heads in Attum, let a and b denote the minimum and maximum of the inner products k Fmas qi I' and v. Ims over all E [dz] and m [m]:
a S (in 3m, Le Im, Us Fmn and max Jm, q Jmn vi Fm S b.
Next, we choose
== 2(b a) (n 2)00 1.
such that the interpolation error in Theorem D.I is at most 2 for any > 0.
Third, Theorem D. requires a single map A Rdxx - R (3d+))xn shared across all H heads. In our construction, we realize this augmentation by prepending each head of Attn H in Theorem D.1 with head-specific linear map A IR Gdd, +n)xn - I (3d++))xn The map Aÿ maps the input Xp to the desired dimension and picks out the target k; q: or v, (this equivalent to the w, Theorem D.I.) to Attn" " perform the desired linear transformation k: X, v. X or q; X. Here still identifies the single head assigned to a specific row. By Lemma D.3, Attn Aj remains an H-head attention.
Therefore, Attn H Ay to build the heads in AttD
construct Aç as
Ta Odxd Odxd Onxd
Oax3dda ET Eń Onx3dd,
Odx3dds Odxedds Kg F Onx3dda
0axm
Odxn
A
Oaxn In
(dd+n)x(4+Gdd))
where
Ej = 1 [0x(((//H) Ia Odx(3adn - -d(h/H)-
dx3dd,
K2 = [0% 1) - -1].
Here 5%H denotes the remainder of dividing h by H. We define % such that instead of the common (kH))
kH%H H, for all k +
50

---

Published as a conference paper at ICLR 2026
Applying Ar Xy yields
la
Odx3dds Ex E
Odx3dd, Oax3dd, K2 F
Odxn Odxn Odxn In
X W I
Oaxd
A% -pp ==
(By the definition of A₁ and Xp)
Odxd
Onxd
3ddn
3ddi
(d+ +n)x2
(3d++)) ( (d+6dd
X Odx3dd Kj. [r In
E
W
Win
(3d+n) Xn
where
3ax
Win expands as
E
Odx3ddn
Win
0
(n -
Oax3dd,
w
dxbidd
6ddn xn
E
10.w
w 2 w
(n - 1) w + 10xxadd,
[
W
107
3xdddn
3dd,
3dd,,
0 Ffw
1. E
2 Egw
(n - 1) E W
and
h1
kd
41
F = 10 (0 Ta Oxx(dd -dd (dHH11d)))-
(By the definition of Ej and w)
dx3dds
Adn
U1
1/
3dd,
1 1 < Hdh
=
Hd, < T 2Hd,
(D.35)
2Hd, < T < 3Hd,
U16/H112d,"
The equality (D.35) holds since Fg selects the [h/ -th block in Similarly, F
K2 Fgl
Wi, expands as
F
K2 F
Wi
0 w w 2 w
(n - 1) w
[E
K3 ER
(By definition of Win)
dxx Gdda
6dd,, Xn.
51

---

Published as a conference paper at ICLR 2026
00 1 w 2-
(n - 1) w + K7,Bi. W
W
dx3dd,
3dd, xn
dx33ddn
3dda xn
(By
[A
D
=
AB+CD)
[g (K₁ 1) (K₁ 100-11 F
dxn
Up here, capable of selecting target k; qi Us, and start build our heads in Att When S Hd,, we compute A Xp as
X
0 k kiafen
1 kkjmm
(n (n- 1) kiaym 1
A Xp =
In
(3d4n)xx
This means every in (J +J+ 1, 1....,... J + H} with j [dx] has the same A₁, Xp:
X
0 kj kj
1 kj
(n - 11-1 1). .i kj
kj
kij
In
(3d+n))xn
For each j E [dx], by Theorem D.I, there exists an H-head attention Attn', (3d+m)) 1R3d such that the output satisfies
(3d+n)xx
|| Attn', Ag Xp ):s - (k) x4)
(3dm) 2x
10 S co.
(D.36)
3d x1
3d x1
for every E [n]] and any co > From (D.36), we have
(3d4n)xx
Attn's Ag X,
(3dm) kJ X 1o S 60.
3d,
3d, xn
where
(3dn) k. x
(KJ De (3dk)
(K: x2)e (3da)
(k3 (nj] (3dn))
3d,, Xn
We use Attn,()) (s) to label the heads in Attn and we define Attn 3
(Z) to
Attn (Z) = Attn, (T)) (Ar (A 2),
(Z E R g(d+add, denotes any input)
where j E [da] and h E [J + 1...... JJ H)
52

---

Published as a conference paper at ICLR 2026
By Lemma D.3, Attn K 3,h (Z) is still an attention.
Thus
J+H
Attu, (Z)= = Σ
h=J+1
also attention.
Thus, we have
Attn K (Xp)
e)
(Bdia) kj
10 S cD.
3d,, xn
3da
This means that
dh
K Ocn
Attu j (Xp)
11 S ED.
(D.37)
Od xm
3da Xn
3da
Similarly for Q, by (D.35), when Hdh < h S 2Hd,, we have
Eq. = 9 H
dx
and
X
0 dj-n
1 qj
(n 1) dn
Ag Xp
ds
gp-do
In.
(3d+n)xx
where j E [2da] \ [da]-
For each j E [2dh]] \ [di], by Theorem D.I, there exists an H -head attention Attn`, ((3d+n)xa + 33d, X such that
|| Attn"(Ap X,)
(3dh) cj
qi
X 1100 S EO.
3d, xn
3dh xn
for any 60 > 0.
Then construct Attn Q in way similar to Attn K j.
3.b
Attn 2 j.h (2) (Z) = Attn, (()) (()) (Az
Z),
(Z E g(d+add, +n)xn denotes any input)
where j E [2dw] \ [da] and (J + 1.....JJ
J H).
By Lemma D.3, Attn Q (Z) is attention.
3.h
53

---

Published as a conference paper at ICLR 2026
Thus
J+H
(Z) = Σ
Attn 2
(2),
J
k=J+1
also an attention.
Thus, we have
Attn 2 (Xp)
Ej
(3da) T
qj -j-dh
X 1lcc S co.
3dy, X
3dp xm
This means that
2d Σ
Od
A
1100 ED.
(D.38)
j=dy
Od xn_
3da
For V, with analogous construction to that of and Q, there exists an H-head attention Attny R3d+4))x R 3d, xn such that
Attn V (Xp)
ej 1/ 2d,, X
(3da)
1100 co:
3da X
3dl xm
for each E [3dy] [2d,] and any cu >
This means that
3dg
Oa, xn Odaxn
Attn (Xp)
11 S cp-
(D.39)
2= +1
3dg Xn
3da xn
Combining (D.37), (D.38) and (D.39), have
K
Altmm (Xp))
Q
V
du
K
2ds
Oo xn
3ds
Od, xn
Attn, K (Xp))
Ods xn
+
Σ
Attn (Xp) -
Q
+
Attn (Xp)
Od xn V
1lx0
Odl xn
j=d++ +1
Oddn xn_
f=2da +1
< E0-
(D.40)
We define
Attn (Xp):
3d
54

---

Published as a conference paper at ICLR 2026
Thus, (D.40) becomes
K
K
Q'
Q
1
co.
(D.41)
3da xn
3d,, Xn
Step 3: Single-Head Assembly for Emulated Map. attention mechanism
Our goal in this part is to reconstruct the
V VSSoftaax ((K') Q'), and V Q))
from K", "', V' and K, Q, V via Atin
In order achieve this, construct Attn, to be Attn, (Z) 00d x2d
Ia, Softmax, ((TT, Od2 x2d Z)
Odn xda Ida
Odp xdal 2),
-Vv.
WK..
-Wa.
where Z E 3d xn denotes any input.
Thus, have
dx xn
K
Attn,
Q
V
Softmax ((K)aaxx((()ooo (K)Q)
(D.42)
du Xn
3d,
and
da xn
K
Attn,
Q'
V
Softmax
(K') Q'))))
(D.43)
da Xn
3dg
Step 4: Error Bound.
From (D.42) and (D.43), we have
K
Attn.(
Q'
Attn.
v'
Softmax, K
Softmax (K' TQ)
(By (D.43) and (D.42))
Xn
dnn
= V'Softmax K" T ②') VSoftmax K" Q') + VSoftmax (MT Q') (K
= (V' - V)Softmax (K"T Q') + (SSoftmax Q') Softmax, (K (K Q)),
(D.44)
and the last equality follows from the distributivity of matrix multiplication.
Then, (D.44) yields
K Q'
K
||ttn, Attn, (
(
Q
[|vv V)Softmax K" Q') + (Sooftmax (K'T Q') - Softmax, (T)))ll
55

---

Published as a conference paper at ICLR 2026
IV V)Softmaxy(K" 10 + |V(Softmaxg (" Q') Softmax, (K' 2)),. (D.45)
and the last inequality follows from the triangle inequality. For term (T) in (D.45), since each column Softmax,5t a ( K" Q') sums up to 1, then
Softmax (K"T Q')...
dg X
ax1
weighted sum of the columns in (V" V). Thus we have
(IVV' V)Softmaxx (KT Q')cillo S SIV - Vl S 60.
and the first inequality holds since the column average of (V' - V) has a maximum entry no greater than the maximum entry among the original columns (V" -V). The second inequality holds since (D.41).
Then we get
(1) S ED-
(D.46)
Term (IT) in (D.45) is
(1I) (S (K"TQ) Q') (oftmaxg(KTQ)))
For simplicity of presentation, define
AS = Softmax, (K'QQ) Q') - Softmax o( Q),
such that for each entry in (TT), we have
(VAA))/ =
Vae (e((S))))
(By the definition of matrix multiplication)
n
<
Viel ((
(By triangle incquality and lab] = |a] (b] for all a, E R)
|
||
(By Vial S || and (AS)ay & ||4511>0)
n/| Vl
| 20:
and this leads to
(1I) S Vl |/S
(D.47)
For each entry in AS, have
(AS),al
(D.48)
-(Softmax,
(KT
Q²)
Softmax Q))a1
9
(K), Q,, Kr, Qi denote the i-th column in K", V"
En
BK.
D
56

---

Published as a conference paper at ICLR 2026
e KK.
@k.
EV= OK,
OK
ΣV ==== ok, Qj
= o0., Qj
====1
OK. OaKI.
+ 10ak:Q0
e. )
(By triangle inequality)
2p=1 OK,
21==1 3K,
Σ 3k Q3 1
((KKQg-K/ K. +
Ev= BK, o
=== (KKI
==
(By non negativity of exponential)
Σ -i==1 @a Qj
1 -2
(D.49)
Σx=1 B
(11-1)
:= (1T-2)
and the last inequality holds since
e BK
1,
1.
R2 -1===
sK2
E 1==1
eK Q2
To bound term (II-1) in (D.49), we recall
K |
K
Q' V"
Q
|| S 6D,
3dxxn
3da xn
SO
K" - K 100 S6D0
d
Q² Q 1lo S c0-
dy dn
Let K/ 2/ K₁ Qi denote the i-th column in K", Q' K, Q, then we have
AK, = K-- K
|A S cD.
dxx1
AQ = Q Qi
||Q S co.
du xI
1
Thus, for term (1/-1) in (D.49), we have
(II-1)
= |1 exp (8(K Q, - K4 -
= [1 (3p( OK-(K; + AK.) (Q₂ + +Q,)))
(By K K.+ AK, and Q, =0++
= |1 exp(- AQ, -G, + AK, AQ;),,
(By K. Q - + -Q) AQ,) K. AQ, + +0, A.Q,AKKK4 AK, AQ))
and we know
K, AQ; + Q3 AK, + AK, AQ;
57

---

Published as a conference paper at ICLR 2026
dr ||Kelle
AQ,1lo |
dr . -12 AK + dn ||AK; =
(By a 6 & du.1|a|l= ||b|| for all a, b E 12)))
S 2d,. BxQveo + dac--
(By |
1Q S BxQv and || | S co)
Thus, we have
(II-1) - ==d_(22kov
(D.50)
For term (TT-2) in (D.49), we have
(11-2)
n
( Q
=
/
OK,
(By the definition of (/I-2))
Ex=1 O
=
(By KG = K2 + AKy and Qi = Q: AQ,)
Σ n
Dp=1 (
E Q
=1 Σ (K, Q5+ 3Q, ,K
and for all the denominator, we have
Ky - Q3 - K2 AQ, + Q3 AK, + AK, AQ;
K₁y Q2 - dn
+ d4 || 00 1 bloo + dn - -IIKK ||
||
(By a bs dulla|l~ |1b|| for all a, b E 124))
S Ky Qj 2d,, BxQvEo + da (Byl]Ka 11 S BRQv and Ao, |eQQbllo 6o)
Thus,
(II-2)
Er= R,
=11
Er= @K(K 2 AK a (aKK
Ex=1e e 9
S
Ex= Q +2 BrQv
E Q
1 3d, (2
(xx independent of i')
Σ Q.
(2K
(D.51)
and the last equality holds since the common factor Ei=1 0K cancels out. Combining (D.49), (D.50), and (D.51), we have
(Softmax (K K" Q") Softmax (QT)))
2 e (o
< 2 (2x
(By requiring 0 << $
Thus for any 0 < E1 < 2, when eo satisfies
In(1 1 0 < S min(1, Bdn (2 (2BxQv + 1)
58

---

Published as a conference paper at ICLR 2026
have
(K" ((Softmax (K"Q' Q*) -Sotmmxx (TTQ))) < c1.
(D.52)
From (D.47) and (D.52), we have
(11) S
BBKQQve
(D.53)
since |V I BKQv and | < 61
Combining (D.45) with (D.46) and (D.53) yields
K
K Q
[
Q'
Attn
oo eo + nBKQvεr.
V
When we take eo and to be infinitely small, the right-hand side tends to O.
This completes the proof.
D.6
PROOF OF THEOREM 4.2
Theorem D.6 (Theorem 4.2 Restate). Let X Rdxx be the input sequence, and let WK. Wi. Wv E Rd be the weight matrices of the target attention. Assume B = max [|XX] oooo [[oolo || |o and || [W || I|Wy |oo I Bxqv for BxQv 2 0. Then, for any e > 0, there exists single-head attention layer Attn, followed by multi-head attention layer with linear projections such that
X WT W
3n Attny o (
Attnn
))
Wv Softmax, (WKX)T 100 S.
W
nxn
Proof. Follow our proof sketch in Appendix A.2, our proof consists of four conceptual steps.
Step Encoding Weights into the Input. For clarity and simplicity, define
h; = (W E Rdd
4: = (WQ) ):. E Rdd
#; (W )., E Rd
such that WR. WT. WiT writes out
W
1k
kn
W (1 42
gnl.
W
[0]
U/
dxn
dxn
Then, we express the input as
X
T2
Fn
W
T
kj
k22
kn
K
(D.54)
W
Q
Q1
Q2
qn
W
C1
02
Cn.
4dxn
where 3i, Kis di and v; are all d dimensional vectors for i [n].
59

---

Published as a conference paper at ICLR 2026
Step 2: Multi-Head Approximation of K, Q.
For the simplicity of presentation, define
K
WK nxd dxn
W
V =
Wv nxd
dxn
dxn
Writing WK, WQ. and Wv row-wise as
k
q
kgg
Q2
U2
WK
Wq=
Wv
k
nxd
and X
[1
Inl. express K, Q, and V entry-wise
k
41
kj
12
k nn
11 21
kg
D2
kg In
k x2
kn Fn
1 x
01 12
" Tn
92 21
92 22
Q2 In
On 11
4 Jn.
U U 21
0 n
1/2 41
01
U2 Tn
=
U, F1
0 22
0 Zn
Here KjT q.= and of identify the i-th row of K, Q and V, while xy identifies the j-th column.
In this section, our goal is to approximate K, Q, and V. Our strategy is to approximate K, Q, and V row by row, and within each row, entry by entry. More precisely, for each E [ni]. we approximate
k X,
q. X, of x,
by approximating the scalar products
k x. of mg, of xy for all j E [n).
and then collecting these approximations to form approximations the full matrices K, Q, and V.
To approximate each scalar K Iz, of xj. and va zj, first determine their joint range over all i E [n.]. Within this joint range, we construct a set of uniform-space grid points. Then, we approximate each target entry &. 2y, q Iz, uf x3 by entry-specific weighted sum of these grid points, where grid points closer to the target entry value receive larger weights. In this way, we represent every entry by its own set of interpolation weights, while all approximations share the same global grid.
We introduce notation for the uniform grid points used in our interpolation scheme.
Interpolations.
We recall
B max(||X| || Iloo, Woll l(V))
60

---

Published as a conference paper at ICLR 2026
Thus, for all j,j E [n]]
d. B² B k Ty. li 25 o2 - d. B²
(D.55)
Namely, [-dB², d contains all entries of K, Q, and V.
Then, we take Lo == ddB² and Lp == dB² as the two endpoints of our interpolation and define for i (0) 1
L iLp + (P (P-i)Lo
(D.56)
P
where P is the number of interpolation steps (the number of equal divisions of [Lo Lp)). The points {Li form our uniform grid over the target range.
We use AL to denote the length of the interval between two neighboring grid points. We have
Lp
Lo
2dB
AL
(D.57)
P
Now we have all the ingredients needed to approximate each entry using a weighted sum. However, the input,
X
Σ
D2
nn
W
k
K2
kin
W
Q
On
W
11
02
2/.
4dxM
contains information from all rows in the target K, Q, and V, but does not contain the grid points. We need a mechanism to select a specific ki qi or v2 (corresponding to one row of K, Q, or V) and include the grid points for us.
To address this, we introduce row-specific linear transformations Lineary, where j E [3n]. since we have n rows for each of K, Q, and V. Each Linear, serves purposes: it incorporates the input and the uniform grid points, and selects the k, qi, v; associated with index (corresponding to one row of K, Q, or V/).
For the clarity of presentation, we relabel these 3n linear transformations according to whether they are responsible for K, Q, or V
Linear K
= Linear,, jE [n].
(Responsible for K)
Linear Q Linearatj: E [n].
(Responsible for Q)
Lineary V = Linearzetj j [n].
(D.58)
Later in the proof, specify the explicit form of these Lineary-
So far, Linear, allows us to combine the input with the uniform grid points and to select the desired k, dis v;. The next step is to implement the entry-specific weighted sums to approximate the entries of K, Q, and V.
For this, approximate k. X using the weighted sum, one head to approximate 9, X in the same manner, and one head to approximate V; X in the same manner. Each such head operates token-wise: given its designated row the head approximates all scalars k.T,,, x.. qf Ty, v. across j E [n].
row-specific single-head attention: for each __n].. we assign head to
Since each of K, Q, and V has rows and we use single-head for each row, we use total of 3n heads to approximate K, Q, and V. use Attn, to label these 3n heads and j [3n].
61

---

Published as a conference paper at ICLR 2026
Again, for the clarity of presentation, provide another equivalent way, Attny, label these 3n heads
Attn. == Attng, jE [n],
Attn/ Attma+ji E [n],
Attmy = Attngatj> j E [n].
(D.59)
Later in our proof, we provide the construction of these Atinj explicitly.
Now we are ready to approximate each K, Q, and V. We approximate first to demonstrate our procedure and deal with Q and V in similar manner later.
In-Context Calculation of K. First, we define the linear transformation Linear R2dxx K
(224+3)x attached before Attn as:
T Oaxd
Odxd La
Oax2d
K (Z) Lineary
Oax2d
Z
2L0e,
2L1e,
(n)
2Lpe,
03xd
03xd
03x2d
4dxm
nx(P+1)
(2d+3)xad
(7 E Rddx denotes any input)
La
Oaxd
0ax2d
(22x((+1)
Oaxd
Odxd
Oax2d
% Inn
Onx(P+1-n)
Mi
03xd
03xd
03x2d_
Adx
nx(++1)
Mr
(2d+3)x4d
(2++3)
where M1, My are
Mi = 1ixn OIx(P+I-n))
(D.60)
Ix(P+1)
Lo
L1
Lp 12P
Mr.
(D.61)
T2
2x(P+1)
The Linear K
layer takes the input [X
WK
We
Wv]
and outputs in the following way:
X WT
Linear
W
W
Taxx
Oaxdd
Odx2d
Ø1
22
En
Odxd
Ta
Odxed
ki
l2
kn
2oge
(n)
2L1e (n)
2Lpe (n)
+
Osxed
Oxxed
Ozxe2d
Q1
Q2
qn
U1
U2
Un
nx(P+1)
(2d+3)x1d
4
La
Oaxd
0ax2d
Ø1
X2
O2dx(P+1) Mi
k1
k2
kn
Oxxed
Oaxd
0ax2d
[In Onx(P41-n))
+
(By (D.54)
Osxed
Oxxd
Oaxed
Q1
Q2
On
M
U1
Un
nx(P+1)
(2d+3)x4d
(24+3)
4d
62

---

Published as a conference paper at ICLR 2026
[
Oax1 R2
Odx1
h1
kn 03x1
2
2[1e)
p (n)
03x1
03x1
nx(++1)
(2d+3)xx
211
22
Zn 0ax1
(P41)P+1) Mi
0ax
0ax1
In (mx(P+1-n) +
03x1
03x
03x1
Mr
nx(P+1)
(2d+3)xx
(2d+3)x(PPM)
[By selecting i; and 2; with La for all E [x])
Odx1
Odx1
Oax1
I1
22
In
0ax1
0ax1
2Tokg
k
2Tp
0ax1
0ax1
0ax1
0ax1
0ax1
+
03x1
03x1
03x1
03x1
03x1
03x1
03x1
03x1
(2d+3)x(P+1)
(2++3)x(P+))
(By selecting by with c((")
02dx1
02dx1
02dx1
02dx1
02dx1
1
1
1
0
T.
T11
Tn-1
In
Lp
Lg
Li
L2
L.pp..
(2443)
(By the definition of M1 and ML; ie., (D.60) and (D.61))
F1
I2
In
Od
Od
2Lakj
2L
2Ln-1kg
2L kg
2Lpks
1
(D.62)
Lo
1,
L Ln-
In
Lp
- T2
12-11
12
-.P
(2443)
Next, we construct Attn (2243))((P+)
panx to be
Attn (D) (D) = W Ky
Softmax Kyd D
D)
Q
(Px(F+1)
(P+1)X(P-1)
(P41)xn
where E R (22443) denotes any input, and
W
Kuj
Oaxd
Ia
Oax1
0ax1
0dx1
(D.63)
R
O1xd
01xd
1
(24+3)
la
Odxd
Oax1
Oax1
0dx1
(D.64)
Q
01xd
01xd
0
(d+1) (2d+3)
K.j.
(3m)
01x(2d+1)
1 0].
(D.65)
1x(24+3) 3nx1
W WKs Kij
In O(p+1-n)XR
(D.66)
0
(P+1)xn
63

---

Published as a conference paper at ICLR 2026
We define the K5 of Attny be:
X
W
Rj = WKy Lineary K
K
)
W
W
J1
32
In
0d
2Lg
2L kj
2
2Lp
Oaxd
la
0ax
Oax1
0ax
0
01xd
01xd
Lo
L1
L Ln
Lp
(2d+))
L
12
- 177
(24+3)x(P+1)
(By (D.63) and (D.62)
2Lokj
2L1kj
2Ln-1kj
2Lpkj
(D.67)
LO L
12 12-1
Lp
(d+1)x(P+1)
and the last equality holds since la selects the 2T,cky row, and 1 selects the - - row where {0) U [P].
We define the Q of Attu, K
to be:
X W
T
25 = w.k..
Linear K
K
W
W
I
T2
En
0g
Laa
2L kj
2 kg
2Lpk
Ia 01xd
Oaxd
Odx1
Odx1
0ax1
Oxxd
Lo
L1
Ln-1
Lp
(d+1)x(2d-3)
L3
L
1
(P++))
(By (D.64) and (D.62)
T1
In
Odx(P-1-n)
(D.68)
(1x(P+1-n)
(d+1)x(P41)
and the last equality holds since la selects the æy row where i [n.]. and 1 selects the 1, row.
We define the Vi of Attny to be:
X
vzK W.is. Linear
W
W
T
W
W
I2
En
Os
O0 2Lpk,
2o
2L1ks
1nn
2L,ky
=e, (3n) 0 (1x(24+1)
1 0
To
T T-
I'n
T.p
3nx1
(x(2))3)
T2
I
I.P
(24+3)
(By (D.65) and (D.62))
64

---

Published as a conference paper at ICLR 2026
(3n)
Lo
L1
Ln-1 Ln
Lp]
(D.69)
3nx1
Ix(++1)
and the last equality holds since the 1 selects the L, row where E [0) U [P].
Combining the results of R5. and 2,,, we calculate the Softmax, (( in Attn as
Softmax (1 (K)
)Q7)
Softmaxx(
2L - Li
2L,k;
2L 1h
2Lp 1i
D2
In Odx(P+I-n)
-
1 01x(P+1-n)
(P+1)x(d+1)
(d+1)x(P+1)
(By definition of R, and 0f;; i.c. (D.67) (D.68)
2Lgh
LB
k
32 1
In Odx(P+1-m)
(By the transpose of R,²)
(1+
2Lpk]
-
(d+1)x(P+1)
(P+1)x(d+1)
2Lok, Ø1 - -L3
2Lak x2 L3
2 In L3 (ax(P+1-n)
2L1k, x1 - L
2 x2
Li
2L1 kj In
Odx(P+1-n)
S
php 11
I2
2I pkk x2
L2p
2bpk In LPp
(p
(P+1)x(P41)
(By matrix multiplicatton)
[KJ Lo)2 + (k] x))
- (k. In Lo)² 2 (k. )n) Odx(P+1-n)
(k) 21 12)² + (kg )1
- (Ki I,,)² + (ki In Odx(P+1-n)
= (
(k] x Tp)² + (k.. x1)²
[k] on - Lp) + (k]aaa) xn)²
Odx(P+1-m)
(P+1)X(P+1)
(2L,k) 3m Li -Kk] 2m 1.)² (k) am) where i E (0) and E [nl)
u1 L0)2
-KT In Lo)2 O2x(P+1-n)
(K) σ1 21)
(k) In L1)2 0ax(P+1-n)
S
)
(D.70)
(k] an T.p)2 - (k. vn Lr) Odx(P+1-n)
(P+1)X(P+1)
and the last line holds since the following property of Softmax
Softmax,(r) = Softmax, + C I(--1)x))
for any vector e E P++ and C IR.
From (D.70), we have
((R,)a w
65

---

Published as a conference paper at ICLR 2026
[k #1 Lo)
- [k: In Lo)²
Odx
(kj L1 L1)
(k) In L1)
Odx
In
= S
0pt+--n)xn
(ki 21 - Lp)²
[k] In Lp)
(P-n
(P+1)xn
(P+1)x(P41)
(k] To)2
- (ki In T=0)2
(13 _1)²
(k: In 12
= S
(D.71)
: (K] 01 Lp)² (kk] In Lp)
(P+1)xn
where the last line follows from the column-wise nature the Softmax,5( function. From (D.71), we have
e C- kk 20)²
(Ko w E e: 3|L, - 2o)3
Ö Jee
for every r (0) (P) and c [n]-
Thus, for each column in (D.71), we have
P
-- xc)² xz)))
(5o1tmax,(R33)
W )
(P+1)
(D.72)
2 B(b, -k mc)
r+1
(P41)x1
Combining i and ((R)) w.kk) )..o.
), we obtain
VK (Softmax;((R5)) W Kid ):
(LLL-kkaa) 2.)
(3n)
Lo
La -n-1
In
Lp
(P41)
BlLa-kJ 2.
rr1
Es=0 e
3nx1
Ix(P+1)
(P+1)xI
(By (D.69) and (D.72)
P
e B(L,, kJ xc)²
j
(3n)
-BL,, kg 2c)² Lo Ln
Ln-1 In
Lp
e
(P+1)
1=0
0
1x(441)
(P+1)x1
[By the distributivity of matrix multiplication)
P
e B(L, - kk_ xc)²
(3n)
(P++) (c+41 selects L, for every (P))
B(L, kJ xc)²
1=
0=
3nx1
walar
P
B(L, 20)
Line (3m)
(D.73)
2== e Bll, -kj 22j22a 22
for every [n].
Hence,
VK. ((R,maxx((RR)TT)) -w w
66

---

Published as a conference paper at ICLR 2026
is a weighted average of the vectors Lrez ( with weights depending on 8 and the distance between
L, and k Te.
We recall: VjK (Softmax: ( W Kis) ) gives the e-th column of Attn.. Therefore, each column of Attnş stores a weighted sum approximator for each entry in k. X.
We show that (I.73) is close to k. ne:
10 (Softmax RK ((K))
Q3) wi )i. kj Iee ej e 11
A(L, -k)=))a)))) x2)²
Σ 0= e 8(,, nc)² Ly c
(3n)
kj tee oj
(3m) 1loc
(By (D.73)
scalor
scalar
e -B(L, o0)²
2E=D B(L, x0) Ly kj [c) . 33a) 1100
C 8(L, 20)
Ly - RiJxel xcl
(We have one non-zero entry in (3w))
25 AKL, 20)
e M x.)²
J, Er -(L,r 20)²
Ee M1,, -kj 2z)² k3 xcc
B(1,, kz)
8=0
(By EE e - no)
+ =1)
P
- z0)²
B(L, k 20) (Lr - kj xz)l
s=0
A(T.r kk 20)²
B(I.r -k3 20)²
Σ
Ee e B(I., - x.)a (Lr - kTTae) xz) +
r: kJ ze12AL Σe e -8(1.. Ail.e-h k 20) (Lr - kij xc))
Σ
(By dividing the L, into groups: one within AL away from ky xc. at least AL away from kj xc))
e M(,, -k] A3] x2)²
e B(T,, N3 m²)
<
Σ
E. e BlI, -k 2.)a (Ir - Rj rc)l +
Σ
E B(1,, 111 kj ac)2 (Trr kij sc)l
L: -kj #oLKAL
r: AJa.2AL
(By triangle inequality)
M(L, k3 xz)²
8(L, KJ xe)²
Σ
2c Lr kJ xcl
Σp B(L BlLo- 20)2 L, k3 xcl
EP Bl bb
r: -J RdL
r:bhe 2o/2AL
((I)
(D.74)
and the last inequality holds due to the triangle inequality and the non-negativity of the exponential function.
For term (1) in (D.74), we have
(I)
-(T,, mz)²
m²)
r:],, - KJ saLSAL E B((., m2)3 Ter - k. xel
Σ
(By the definition of term (T) (D.74)
e B(L, - kj xTe)
<
Σ
AL
(In this group of Lr. [L, - kJ xzl <
KJazel
AL)
-(L,, Eieee - kTaa)² mc)²
r:1,,-k] -J] ael< (lll,-JaallLL
< AT,
(D.75)
67

---

Published as a conference paper at ICLR 2026
and the last inequality holds since
Emite, Enllt,JJackaat A.T. 3(b
11.
(The numerator is part of the denominator)
E. e --bllb 8c)
For term (IT) in (D.74), we have
(11)
B(L, kJ 26)²
Σ
20 B(L, kg xc)² 1r ki xel
(By the definition of term (IZ) (D.74)
n11, kj ne RAT.
- k 0c)²
S
Σ
Ex=o B(,,, -kj mz)² 2dB2
r:l,, -k] aelL
(By (D.55) and (D.56), have [T, kJarel 2dB²)
Σ
kg x.) 2dB
Lo B(L, -kk
rIL, 2dl2AL
(By [T, - Kg xel 2 AT, we have AKt,,-kJaas koo) --8112
e --L2
Σ
2dB²
maxafe
Kj -BLL,
B(L,- mo)²
r/l, -kk--kj kJ 2el 2AL
(We only keep the contribution from the nearest L, kj st)
-ALL
Σ
ع 2dB²
(D.76)
r1L, AJ RAL
and the last inequality holds since, by our construction of L, in (D.56), the distance from kj ze to the nearest L, most AL That is,
AL for so = argmin L, - k3 xel-
L.o - kg] xcl s
2
From (D.76), we have
Σ
2dB² < Pe 2..11 2dB²
(D.77)
IL k..kJaan a.lkka.
and the last inequality holds since, by our construction of I., in (D.56), at most P points satisfy
[Tr |T,- k. xal 2 AT. This P-point scenario occurs when the value of k. ae equals one of the I., grid points.
Combining (D.74), (D.75), and (D.77), we have:
I (()ft
wK: )a.
k. xe
x. (3a)
(al S AL Pe - 2dB
=(a)
=(6)
(D.78)
For term (a) in (D.78), we recall
AL 2dB²
(By the definition of AT. i.c., (D.57)
P
68

---

Published as a conference paper at ICLR 2026
To bound AL, choose
4dB²
P>
6
for any > O, such that
AL
For term (6) in (D.78), we set
4 1 In
$ 2
3 (AL)²
such that
Pe 1/31122220
2dB S
C
2
Thus, from (D.78), we have
I1/ (Soltmax;((R25) Φ5)
Wx )
kJ Se
(3m)
1mx S
SAL+ Pe
1BAL 2d
scalar
3xx1
61
2
f
and this leads to
I0g Softmax (( (R wK...
(3m)
k3
x
x
S
C1.
(D.79)
3nx1 1
1xn
We recall
VyK ((f W
X
X
X
k Lincar K
W K
S (W k Lincar K
W
K
)) T W Ky
Lincar
K
W K
))
W.
W Q
WO
Q
W
Q
W
W
W
(By the definition of RJ. QK and (7K
X
W
= Attn K Li K
(
K
(By the definition of Attn
W
Q
W.
Thus, we write (D.79) as
X
WT W W.
Atttn K o Linear K
(3n)
k X
oo00 S
En
Q
Ixn
69

---

Published as a conference paper at ICLR 2026
and sum the index to obtain the approximation
X W
Attn K Linear,
(
Onxn Onxn
1l00 c1,
(D.80)
W
W.V
for any 61 O.
In-Context Calculation of and V. of K.
We approximate and V using the same procedure that
We start with Q.
Again, define Linear? preceding A first. We construct Linear @ similarly to Linear K only difference is the position of the identity La in the first term. Explicitly,
The
Oaxx
Oaxe
Oaxd
Odxd
Oaxd 03xd
Oaxd
La
Odxd
Z 4dxn
(n) (200
2L1e, (1)
... 2Lpe,
(nl +
O3xd
Oaxd
03xd
nx(P+1)
(2d-3)
la
Oaxd
0ax2d
(2dx
Oaxd
Oaxd
Odxed
Z [nn Onx(P+1-m)
M1
Osxd
0sxd
O3scdd
4dxn
#x(++1)
ML
(2d+3)x4d
(2++3)x(P+1)
g takes
[XT
WK
We
Wv]
as input and outputs:
X
T2
In
Oa
0a
2L
2L
2In-19h
2L 4
2Lp4
WT
Lincar (
1
1
1
0
W
Lo
L1
Ln-1
Ln
Lp 13
W
L3
L
L2
L2
Next, we construct Attn ((2443)((P+)) R 3nxn be
(D)
w
Softmax
25 D)
TW
D).
was
Q
(Px(P+1)
(P+1)x(P+1)
(P+1)xn
where (22443)((P+)) denotes any input, and
Q = Kis
Oaxd 0ixd
La
0ax1
0ax1
0ax1
R
=
O1xd
0
(d+ (x
Qu
W
Kij
La
Oaxd
0ax1
0ax1
0
01xd
Oxxd
O
(d+ x)+1)xx(0 (2d++33
(3m)
0
Oxxd
0].
1x(24+3)
70

---

Published as a conference paper at ICLR 2026
W W
In -n)
(P+1)xn
We define the K2 of Attn to
R2 W
Linear
(
W
2Lo L
2L 1
2ln-10) 10
2Lp
(D.81)
R
W
-2
Lp
W
(d+1)x(P+1)
We define the Q3 of A be
X
29 W Linear o
W
31
32
En
(px(P+1-n)
(D.82)
W
1
0Ix(P+1-n)
W
(d+1)X(P+1)
We define the De of Attn to be
0 w Linear ( (
W
K
(3m)
Lo
L
Ln-1
Ln
Lpl
(D.83)
W
WV
3nx1
Ix(P+1)
Then, by going through the same calculations those of K, we have
X W W
Onxn Q [nxn_
Atta L
11o0
S El.
(D.84)
W
To approximate V, define
O
Oaxd
Oaxed
0dxd
Linear (Z) (Z) =
Oaxed
Oaxd
Oaxe
Ia 03xd
Z 2o0e
2L1e, (n)
2Lpe,
(n)
+
03xd
03xd
Oaxd
idxn
nx(P+1)
(2d+33 xd
Ia
Oaxd
Odx2d
O2dx
Odxd
Odxd
Oaxed
2. In Onx(P+1-n)
+
Mi
Oaxd
03xd
03x2d
Mr
nx(P+11
(2d+3)xxdd
(24+3)x(P+1)
Lineary outputs in similar manner as Linear K:
22
En
Og
0a
2LQU
2L103
2L 1
2L
2Lprj
Lineary (Z) (2)ear)()Z==
1
Lo
L1
Ln-1
Ln
Lp
L3
L3
L2
L2
L3
71

---

Published as a conference paper at ICLR 2026
Next, we construct Attn R (224+3))(P+1) + R to be
Attn V
W W
Softmax ((W Vis
D) W
D)
D)
W
R
3mx(P+1)
(P+1)X(P+1)
(P+1)xn
where D ((2243))((4)) denotes any input, and
W
Wk
Oaxd 01xd
la
0ax1
0ax1
0xx1
R
R
01xd
0
0
(x4+))(22+3)
WV W
Vi
WKk.s
La
Oaxd
0ax1
0ax1
0ax1
2
01xd
01xd
0
(d+1)x(24+)))
WV
C2
(3n)
101xd
01xd
0].
3nx1
(x(2++3)
WV
Wks 6
In 1pp+1-n)xn
(P+1)xn
We define the Ry to be
X W
Ry- WVV.. Lineary
2L. I
2h I
2 2m
pLp
(D.85)
R
W
12
T.p
W
(d+1)x(P+1)
We define the Q to be
X
Qj WVs.. Lineary
W
22
En Odx(P+1-n)
(D.86)
W
1
(Ix(P+1-n)
W
(d+1)x(P+1)
We define the V. to be
X
vy WV Vv Lineary
W
2n+
(3n)
Lo
Li
L
Ln
Lp].
(D.87)
W
W
x1x1
Ix(P+1)
Similarly, by going through the same calculations those of K, we have
X W W Q
Tnxx
Attny Lineary V
Onxn
al,c S1.
(D.88)
W
72

---

Published as a conference paper at ICLR 2026
Then, by combining (D.80), (D.84), and (D.88), we have
X
X W
W
K
Onxn
Σ
Attn K Linear K
Onxn
Σ
A Lincar q
K
Q
W
W W
0nxm_
Onxn
WV
X
Tnxn
W &
Σ Attn Lincary (
)
Onxn V
1l00 S 61
W
Q
W
As previously stated in (D.58), Linear, Linear 2 and Lineary denote Lineary, Linear,+) and Linearza+s respectively. Also, as (D.59), Alinz Autnf and Autn denote Atinj, A and Atlngatt-
Thus, we have
X W WQ W.
Attny Linear,
(
1o S 61
(D.89)
S
We define
X
KK'
3n
W
Q' V'
= Σ
Attn Linear,
K
)
==
W
such that (D.89) becomes
K Q' V
K
Icc S
c1.
(D.90)
Step 3: Single-Head Assembly of the Attention Output. attention mechanism
Our goal in this part is to reconstruct the
((So Q'), and ((K) Q):
from K',Q' V and K, Q, V via Attn,.
To achieve the reconstruction of attention mechanisms, we build Attn, as
Attn,(Z) [0nx2n In) Z Softmax:((LIn 0nx2n] T) 1nxx In 0nxn] Z),
where Z 3nxn denotes any input.
Then, have
TXB
K
Atlna
Q
Softmax
(KK) QQ) Q).
nxn
3r Xn
73

---

Published as a conference paper at ICLR 2026
and
X.
KK'
Attna( (
Q
Softmaxx
(K)
nxn
BXn
Step 4: Error Bound
From the results of Step 3, we have
Attn,( Q'
A
V'Softmax (K" Q') 3Softmax K (TQQ) Q)
V (K" Q') VSoftmax, Q²) VSoftmax (K" Q²) - VSoftmax,((F Q)
(V' S)Sofmaa K Q' V(Softmax,(X" (K" Q) Softmax (K QQ).
Thus, we have
K |Attn, (
K Attn, (
Q' V'
Q
||
|I(V' V)Softmaxx K" Q²) + (SSoftmax;(K"" Q') Softmax TQ)
< (IV V)Softmax (K" 20 + |V(Softmax, (K Q') - Softmax (K Q))],o, (D.91)
and the last inequality follows from the triangle inequality.
For term (A) in (D.91), since each column in Softmax & (KT (KTQ')) sums up to 1, then for each column of (A),
(V' V) Softmax, (K"" (K"TO Q'):s
7X
ax1
a weighted sum of the columns from VV-V).. Then, we have
(IV "7)Softmax((K3 (M" Q')sill S VIV - -Vloo S 6
and the first inequality holds since the column average of (V' - V) has maximum entry greater than the maximum entry among the original columns (V' - V). The second inequality holds since (D.90). This conclusion holds for every column in term (A), we obtain
(A) S E1.
(D.92)
Term (B) in (D.91) is
B = (V((oflmax; (K" Q') Softmax, Q))
For the simplicity of presentation, we define
AS Softmax, (K' Q') Softmax,( Q),
74

---

Published as a conference paper at ICLR 2026
such that for each entry in (B), we have
((VA))yl= =
Va (A)
(By the definition of matrix multiplication)
Viel ((45)a)
(By triangle inequality and |ab] = |a] |6 for all a. 6 E R)
1=1
<
| ||45|| 0c
(By Vial S 1|V and (45)as) & ||5|))))
n VI
| 800
and this leads to
(B) S vllV ||AS|
(D.93)
For each entry in AS, we have
(())),y
(Softmaxx (K"T Q²) Softmax (K T Q))aal
(3 11
(K), Qu K, Qu denote the i-th column in K', Q'. K', K, Q)
E @K,. 02
eBk.Qq)
2==
BK.
EV= BK,
ΣV= BK, o
E e
+ 90:
Dx= C.K )
(By triangle inequality)
D F==1
3K 4
2p== 3K.44
OK,Q'
Q
2v== Q, Q
K.0 +
=1=1 3K,
R=
-m==1
(By non-negativity of exponential)
Σ == Bk. Qi
< 1- -(KK
-3.
+|1
(D.94)
n =1
BK. Q
=(B-1)
(B.2)
and the last inequality holds since
e KK'
ek, 4 Q,
1,
1.
Σ 12
-1==1
To bound term (B-1) in (D.94), we recall
K
K
Q'
Q
loc S 61
3nxn
Inxn
SO
K" K 100 El,
7
75

---

Published as a conference paper at ICLR 2026
Q 1Q'- S1.
TXX
Let Ki Qú Ki. Qi denote the i-th column K', Q' K, Q, then we have
A
K
K₁
|AK 0o S 61
nx1
AQ = Q Qi.
| S 61.
ax1
nx1
Thus, for term (B-1) in (D.94), we have
(B-1)
= | expl [KK Q, - K; (K/-29H
= | exp( Q, 33-(A4 Q5-(K,+ + AK,) (Q + AQJ))H
(By K = K; AK; and Qi Q0+
= 11 exp(-3(K, AQ, + +Q, AK; + +A,, ,Q,,),,
(By K; Q3 (K: + AK:) (Q: AQ.) (K, AQ, Q3 AK. AK, AQ)))
and we know
K2 AQ, + Q3 AK, + AK, AQ,
Sn. || Kx AQjI n |Q, |ox || A
+ n ||K,
(By a S a||aa|>< |b6| for all a, 6 E 12")
< 2nnKqqe + ne..
(By | |oo, 10 S BxQv and || |AQ Se)
Thus, we have
(B-1) - -
(D.95)
For term (B-2) in (D.94), we have
(B-2)
n BK
Q2
=
(By the definition of (B-2))
P==
E Q,
=
Σ f
(
(By KG = Kr + AKp and Q = Qu AQ.)
P=
E SK
= Σ (Kg Kgt -Q, +Q,+0, AK,
and for all the denominator, we have
Kp Q, + Kg AQ, +Q₃ AK2 + AK₁ AQ;
< Ky Q, n || AQQ bo + n || 1l /o0
A K loo || booe || AQ
(By a-a b S rl|aa] [16] for all 6 E R2")
S Kg Q, + 2n 2n + n
11o S BKQv and / 5e)
Thus,
(B-2)
76

---

Published as a conference paper at ICLR 2026
LP= eBlK AQ t0
Ei==1 ( R= e +2nBKQVALnne)
<
(e (en((2Bovvate)) is independent of 1')
(n(2Bkevr Ev= QK
[1 -n(22kaveettt)
(D.96)
and the last equality holds since the common factor Ex= e cancels out. Combining (D.94), (D.95), and (D.96), have
(Softmax ( Q') Softmax Q))aal
< 2 -Bn(2Bxqvente))
$ 2 -
(By requiring < 1
Thus, for any 0 < ED < 2, when Ej satisfies
In 2)
0 <<< S min(1, 3n(2BxQv +
we have
[(Softmax, (K' (K Q') -Sottaxx (K)))aal < Eg.
(D.97)
From (D.93) and (D.97), we have
(B) S n < <BBKQve.
(D.98)
since V S BBQV and || < cp-
Combining (D.91), (D.92) and (D.98) yields
K
K Q
|
Q' V'
Attn,
lo < + nBKQvee-
When we take co and 6 be infinitely small, the right-hand side tends to This completes the proof.
D.7 PROOF OF COROLLARY 4.2.1
Theorem D.7 (Restate of Corollary 4.2.1: In-Context Emulation of Statistical Methods). Let A denote the set of all the in-context algorithms that a single-layer attention is able to approximate. For an a E (that is, a specific algorithm), let We. W WD denote the weights of the attention that implements this algorithm. For any > 0 and any finite set Ao A, there exists 2-layer attention Atln Allln such that
3m
([xx ( [ 1
Attn, Attn, Linear,
a(X)lloo Se, a An
where W/a is the W defined Definition 4.2 using W7, W&, Wg.
77

---

Published as a conference paper at ICLR 2026
Proof. Without loss of generality, assume all W WQ, Wy to be of the same hidden dimension since we are always able to pad them to the same size. According to Theorem 4.2, there exists a network د5= Attn, Attn, Linear, that approximate a(X) with emror no larger than when given input of the form:
X W
W T
W
Then for of E Ag, define P., max.c..o p!a)
By Theorem 4.2, there exists network consisting of a self-attention followed by a multi-head attention with linear layer and parameter P equals P... such that for any Ao, we have
X W W
3n
Attn, Attny Linear,
a(X)llo Sc. a Ao.
W
This completes the proof.
E IN-CONTEXT APPLICATION OF STATISTICAL METHODS BY MODERN HOPFIELD NETWORK
Definition E.1 (Modern Hopfield Network), Define Y (y1..... :N) E R& as the raw stored pattern, R = (r1.-.. rr)] E R R. as the raw state pattern, and Wq E Rdxd, WK E pdxd, Wy E Rdd xd as the projection matrices. A Hopfield layer Hopfield is defined as:
dxN
Hopfield Y, Wo, WK. Wv) Wy WxY Sofumax (B(WxY e Rdxxs
(E.1)
xd
Nxs
where 3 is temperature parameter.
With K IRdx denoting WxY. Q RdxS denoting Wo R and V Rd. denoting Wy WyWKY,
(E.1) writes out as:
Hopfield R: WQ. WK. Wv) VSoftmax(B K KTQ) RAxS
Theorem E.1. Let Z = [21, 22, 2n E IR dxx denote the input from a compact input domain.
For any linear transformation I(=) + b Rdd + R, and any continuous function f + where o is the output dimension, there exists a Hopfield network Hopfield such that
-Hopfeld((Z)((((())) f(((2))
[(((z))) lbc Se.
for any 0.
Proof. We first perform simple token-wiin linear transformation on the input:
Linear(2)
Laxa 01xd
7
+
Oxxn Lixn
Z
(d++1)xn
1ixa
78

---

Published as a conference paper at ICLR 2026
We then construct Wi be:
Wq [(tt))
which is identity matrix of dimension R(++1)x(4+1), This yields that
Q = WoLincar(Z))
Z 1ixn
E (d+1)xx
Following the definition of Interpolations in Appendix D.6, K, V are constructed as (here we omit Y since it's the input):
20ya
2
2Lpa 2Lpb 1.
K 2Lab 13 2L1b
V (f(Lo) f(L1) f(Lp)).
By Definition E.I, we have
Hopfield(2) 2)
21(21) - 13 21(21)41 L
21((2) - L3
21(2n) Lo - L 21(2n) L7
21(22)L1 L
[[[o) f(La) f(Lr) Softmax
B
22((1) Lp - Li
21(x2)Lp LP
21(z)) - 17p1
This is equivalent to:
Hopfield(Z)
(1(11) - Lo)
(1(z2) Lo)2
(1(zn) Lo)2
(1(1)) - L1)
(1(22) - L1)²
(1(z)) L1)
= [s(Lo) S(Li) ((LP) Softmax
-3
(((z)) Lp)
(1(z2) Lp)
(1(z)) Lp)
For any column E [n] in (Z), we have
(((ze) - Lo) )2
(1zz)) L 2
Hopficld(Z).c. (f(Lo) S(L)) (LLp)]
[(((z)) Lp)
e -B((
r==l -(1((z)) L,r33 f(Lr).
When 3 is large enough, we have
-(((
E -AL
Σ
Σ
< Pe - E1,
3(1(()) L,r)²
BAT
(1(.)) 1.))-1.)2AA1
for any > 0.
79

---

Published as a conference paper at ICLR 2026
This means that the proportion of the fL,) in Hopfield(2).c that deviates from [(2e) is no larger than 61.
Since and are continuous, and Z comes from compact domain, ((2)) comes from compact domain for all i [m]. Thus f is uniformly continuous on its imput domain. This means that for any (2 there exists á > 0 such that when(æ y)² 6, [l) fl S c2.
Configuring AL v yields:
(2),
-(.)
- Ers1 (-11((z))-1 -,,)) ( (((=,))
e-A((=))--
(1(z)) (16.)-4))222L -r -11(())) 15(L,) - f(((2)))
Σ
-l((()))
(1(z.) PE. Er e -111)) [1](TT)) )(((z)))llo
Σ
< 2B - - E1)E2,
where = 1 is the bound of f in infinite nomm.
We set 62 c/2, 61 I c/(4). This yields:
|Hoffield ()). S(((2))) Se. .B2 (1 61)22
S 4B
2B + 2
This completes the proof.
Theorem E.2. Define
[2 1/1
X =
22
on
(d+1))xn and
W = [w w] E dxx
y22
yn
where D2 E Rd and y E R are the input-output pairs. w e Rd the linear coefficient to optimize. Suppose 2i, Yi and are bounded by B in infinite norm.
For any continuous function f R > R, there exists a Hopfield layer Hopfield with linear connec- tions such that
[WW [[ T -1) s(w x2 y2)222 f(w xn yn [w]] 1lxc S e,
for any e 0.
Proof. Before plugging input W to the Hopfield layer, we pass through a linear transformation Linear
Oaxo
W
-1xx
-1xxn
Linear,
22)+
Ta
W +
0uxon
04xn
E g
=2(2d+++)xxn
-11x
lixn
In
In
We also pass X through linear transformation Linearz: Linear.(X))
80

---

Published as a conference paper at ICLR 2026
la+1
x (d+1)xx
(0xx(01)((41)
2T
2
2bp, (m) (px(n-0(P+1))
(()+1+))((+t))
exn(P+1)
(2d+n+2) x(++1)
O(a-1)xd
0(a+1)
Id
Od
x (nxx(x-nxCH1) f(Lo)e) f(L)),
f(Lp)e) (0 Onx(n=:)(P+I))
(n+1))xd
Oz+1
(2d-n+2)x(d-1)
((2++1)((P1)
(2d++1)((P+)
5
5
(2dB² B - Ineo)e (m) (Ix(P+1)
(2d B I
(m)
(2d+n+2)xm(P41)
[Ti
T2
Tal.
where
11x(P+1) == [1
1] E (2x((+1),
= --1 -L3
Lij E BII(P+1))
2L
2L1x;
2Lp
2Lo
2L
2Lp
T=
[ [(Lo)a
[(LI) Jai
f [(Lp) p)
R(2++++)x((P)))
L
L
1
(2dB² + B In c (m)
(2dB² + B In cn)e
(n)
(2dB² B In (n)
Here eo is parameter that will designate later according to Now construct WK, Wo, Wy to be:
Wº= == I2d4n+2,
Wx 12d+n+2:
W = [0ax(d-1) Ia 0ax(n+1) E (2xx(24+2+))
Therefore, by Definition E.1, the output becomes:
Hopfield(Linear, (W); Li)ear,(X)) Wy (X Linear (W)),
where
W
- -lixn
Softmax(Linear, Lincar,(WW) = Softmax(B [Ti
Tb
Tz]
Oaxn
-1ixn
In
This is equivalent to:
T
w
T
1
(Linear,(X))
LiinanX Linear,(W))....
0₂
T
81

---

Published as a conference paper at ICLR 2026
Mi,e M2,c
where
w
Mi. : T
02
(m)
2T 2Lo8:
T2 + (2d + B - -n i=c
2 w 2L19: + (2dB² + -B 2l 1is
pLr w- 2Lpys L3 (2dB² + B - B-lneo)l1
where E [n] and c [n], and == represents the indicator function of i
This means that
Softmax Softmax(8Lincar, (3Lincar, Linear, (W)))
M
M2.0
Softmax(B
MM,.v.
exp 2 w
2L - L3 + (2dB² + 1 (n (nP) (2) E ES exp u + (2dB² +B (1n
(1-1)P45
Thus we have (without loss of generality, we ignore the parameter in Softmax):
Hopfield(Linear,(WW): Lineea (X)),e
WyLiinaa, (X) SoftmaxxiLiin (X) Lincar, (W))..
(W, only retrieves the (d (d++3) 2) row T:)
exp(2L u w 2L,y, L3 + (2dB² + B - In
[Fi
(nP)
(1-1)P+5
Σn プラ ΣS exp 2 - 2L 12 + (2dB2 B - -ine))
P
exp 2L w 21,21 L7 + (2dB² In 60 }
[(T,))r..
- E exp 2L w 2L, Vr L3 + (2dB² B In ln 1ize
=1
where is:
F :== f(L,)a f(Lp)=.)
For every i [n], i c, we have
exp 2L w 2L,01 - L2 + (2dB² + In 1=
E'= E exp 2T....... 2T. - 123 (2dB2 + In 11
82

---

Published as a conference paper at ICLR 2026
P
exp (x 2L.iVi [13)
1=0 L1==1 =1== 2j'=0 exp 21 24 22. L13. (2d132 + B In ln
exp 2 w - 2L,3/i- -
2S =0= exp 2 21. - 12y + (2dB² + B - lnco) j
(only taking the = e part)
exp + }
P Pexp(2d1 2dd + B Inee) 60
==
For i C, since
n
exp 22 w - 2L L3 + (2dB² +B - -lm
S (n (n)
i= Ev= Ex= exp 22, 2L 2L - L3. + +2dB3 + B lnc
we have
E/ exp(u, (1) +
+ B -Inn))))
E Ej'= exp L T. w 22 L3. + (2dB² B In lime)
exp u/ (0) + (2dB² lm)
Σ /=0 Li=1 = exp 2L 2 2Ly L.. (2dB² + B In l
2 1 (n- 1)co.
Thus for the parts in the weighted sum output that corresponds to rows in M. in the attention score matrix, we have
P
expfug
+ (2dB² + -lnea) // (0)
f(L,)=e f(x, w ve)xello
j=0 21==1 2s'=0 exp 2L 2 2Lyur - -1z. (2dB2 + -l
P
P
exp
uj
(c) (2dB² + B - 1l
(f(L)) - f(xJ w -yo)xe)
P
exp uy + (2dB² B - ln)
0=0
===
ΣS exp
(c) Uj + (2dB² + +B 18--hn -11
Σ / 11 Σ exp " (P) + (2dB2 + 1-In 60) i=c
E/ exp
Uj + (2dB² + +B Im6o)
-(1
)fxx. w- ve)xeeloo
M m1 Ek exp " + (2dB² + - (mm
(1)
exp U; + (2dB² + B - In }
(6)
[5(L)) - Mao No)l dllxcelloo
P
(c) (2dB2 + B InEo)
1=
=0==
exp ug
Σj-
P
exp w/ + (2dB² B ln
[[(xx w ye)llxxelb
EP
(1) (2dB² + B In ll
exp
u/
83

---

Published as a conference paper at ICLR 2026
(c) 4j + (2dB² + - -Inco)
P exp
[s w ye)ll
Σj P
j =0=0 exp "j (c)
(2dB² -Boln
1=
(n 1xello
expl " (0)
[(Ty) - [(x) yolllleello (n ( By 1/11oello0
2''=0 P==D exp uj
exp( - (5x Ve _,
If(L,) f(zz w 2e)ll<ee1>> (n 1) 1x
Lp'=0 exp( - (xx w - ye 1
where we define B = | the bound for f- For any 61 > 0, set AL be sufficiently small such that
10(x)) [w)) S EI,
when x - y/ $ AL.
Then when 3 is sufficiently large, have
exp B(x Yc - -,
Σ
S 62;
Ejz expl - [ w yo - L3)
(xx
LL, [L. Bell
for any > 0.
Thus
exp( -5 w - yc - -,))2}
[s(1,) 5(x Ne)l
=0= exp( (xx w )]
1=0
exp ((xx w -- - L5)3}
Σ
|f(L,) - f(x -yy)l
Ej'= =0= exp - (xx w Ye Lg
(x ----
expl 3(x Ve L,)
+
([(T.) 5(x! w yc)1
[L, (1r w W--B)IAAAL E exp( (B ye -e-
< E2 2BB +11.
This completes the proof. Corollary E.2.1 In-CContxxt GD of Hopfield Layer). Define
X
=
Σ 22
Fn
(d+1))xn and W ww
w|
E Rdxx
y/1
1/2
yn
where F; d and y; R are the input-output pairs Rd is the linear coefficient aim to optimize. For any differentiable loss function & I - IR, There exists a Hopfield layer Hopfield with linear connections such that
[ [Vl 91)a
Vl(w D2 v2)
Vl(w" In yn yn) lllo S c
for any 6 > 0.
Proof. Replacing the continuous function f in Theorem E.2 with V completes the proof.
84


Reviews:
[{"review_id": "nO63aespLf", "reviewer": "Reviewer_YySt", "summary": "think this paper makes only a marginal contribution over prior work (e.g., [1], [2]). The authors show how a single attention layer can emulate, in context, a broad class of algorithms (with an additional linear layer on the input) — specifically, any function of the form $f(w^Tx-y)x$. As special cases, they derive linear regression, (stochastic) gradient descent, and ridge regression. However, all these results have already been demonstrated in previous works [1], [2], [3], [4] etc.\nThey further show that attention itself can be emulated in context using two attention layers. One question that arises is why one would want to emulate attention in context when direct access to the attention mechanism is already available. This part mainly illustrates that any attention layer can, in principle, be emulated in context by a fixed-weight transformer by defining appropriate prompts(prompt-specific mode).\n\n[1]: Bai, Yu, et al. \"Transformers as statisticians: Provable in-context learning with in-context algorithm selection.\" Advances in neural information processing systems 36 (2023): 57125-57211.\n\n[2]: Giannou, A., Rajput, S., Sohn, J., Lee, K., Lee, J.D. &amp; Papailiopoulos, D.. (2023). Looped Transformers as Programmable Computers. \n\n[3]: Von Oswald, Johannes, et al. \"Transformers learn in-context by gradient descent.\" International Conference on Machine Learning. PMLR, 2023.\n\n[4]: Giannou, Angeliki, et al. \"How Well Can Transformers Emulate In-context Newton's Method?.\" arXiv preprint arXiv:2403.03183 (2024).", "questions": "1. Could the authors clarify the motivation or potential use cases for emulating attention using attention itself? For example, are there theoretical insights or architectural benefits (e.g., modularity, composability) that justify this construction?\n\n2. Can the authors clarify whether their constructions differ in expressive power or generality from prior results (e.g., in [1], [2])? Are there cases where their framework captures algorithms that earlier works could not? (Even if the layers are less -- it is important to have a comparison of constant vs logarithmic for example). \n\n3. How does the proposed notion of “prompt-programmable emulation” differ technically from “in-context algorithm selection” in previous work? Is there a formal distinction or new capability demonstrated here?\n\n4. If the authors believe the contribution lies in unifying or simplifying prior results, could they argue this explicitly and explain how this framework might enable new theoretical or practical insights?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The distinction between task-specific and prompt-programmable emulation is a useful conceptual framing.\n\n2. The coverage of residual update forms $f(w^Tx-y)x$ is broad and subsumes many standard learning procedures.\n\n3. The extension from emulating a single-layer attention mechanism to emulating full (linear) networks is conceptually compelling.", "weaknesses": "1. Most (if not all) of the results presented in this paper have already been proved in previous works, possibly using deeper—but still fixed—architectures. Results on linear regression have appeared in [1], [2], [3], and those on ridge regression in [1], [4] (using softmax attention instead of linear attention introduces only a small approximation error).\n\nIn-context algorithm selection was also demonstrated in [1] and [4]—not explicitly, but implicitly through the design of pointer mechanisms that determine which function is executed in context.\n\nOverall, the contribution of this paper is limited.\n\n[1]: Bai, Yu, et al. \"Transformers as statisticians: Provable in-context learning with in-context algorithm selection.\" Advances in neural information processing systems 36 (2023): 57125-57211.\n\n[2]:Von Oswald, Johannes, et al. \"Transformers learn in-context by gradient descent.\" International Conference on Machine Learning. PMLR, 2023.\n\n[3]: Giannou, Angeliki, et al. \"How Well Can Transformers Emulate In-context Newton's Method?.\" arXiv preprint arXiv:2403.03183 (2024).\n\n[4]:  Giannou, A., Rajput, S., Sohn, J., Lee, K., Lee, J.D. &amp; Papailiopoulos, D.. (2023). Looped Transformers as Programmable Computers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yYG5WaVODv", "reviewer": "Reviewer_6rGC", "summary": "This paper investigates the capability of fixed-weight Transformer architectures to emulate a broad class of algorithms through in-context prompting, addressing a core question in Transformer research: how frozen models execute diverse tasks via context alone. The authors formalize two modes of in-context algorithm emulation:\n\n1. Task-Specific Mode: A single-head softmax attention layer (with a linear map) can universally approximate functions of the form $f(w^\\mathrm{T}x-y)$ (for any continuous $f$) to arbitrary precision. This template includes key machine learning algorithms like gradient descent (GD), linear regression, and ridge regression.\n2. Prompt-Programmable Mode: A single fixed-weight two-layer softmax attention module achieves universality—emulating all task-specific algorithms via prompt design alone. The key mechanism is encoding algorithm parameters into prompts to create sharp dot-product gaps, forcing softmax attention to follow intended computations without feed-forward layers or parameter updates.\nThe authors validate their theory numerically: synthetic experiments confirm accurate approximation of continuous functions, with error decreasing as the number of attention heads increases; real-world tests on the Ames Housing dataset show the frozen module matches performance of task-specific baselines.\n\nIn conclusion, this paper show a minimalist transformer architecture serve as a general-purpose algorithm emulator in context through prompt design.", "questions": "- Prompt Compression: Given that prompt length scales with weight dimension, have you explored methods to compress prompt-encoded parameters (e.g., low-rank approximation, quantization)? Would compression preserve the sharp dot-product gaps needed for accurate emulation?\n\n- Non-Linear Algorithms: Your framework excels at linear/gradient-based algorithms, but how would it handle non-linear algorithms (e.g., logistic regression with sigmoid loss, or k-means clustering)? Do you need to modify the prompt structure to capture non-linearities, or does the continuous function $f$ in Theorem 3.1 suffice?\n\n- Feed-Forward Layers: You omit feed-forward layers in your constructions. Would adding feed-forward layers improve emulation accuracy for complex algorithms, or does this break the \"minimal architecture\" claim? Do feed-forward layers introduce interference with prompt-encoded parameters?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Foundational Theoretical Value: The formalization of two emulation modes and universal approximation results establish a rigorous basis for viewing ICL as \"in-context algorithm emulation,\" addressing open questions about fixed-weight Transformer flexibility.\n\n- Interpretability: Unlike black-box ICL studies, the paper provides a clear mechanism (prompt-encoded parameters + softmax routing) for how frozen models execute algorithms—enabling future work on principled prompt engineering.\n\n- Broad Algorithmic Coverage: The task-specific template unifies diverse algorithms (GD, linear/ridge regression), showing that a single attention layer can capture core ML workflows.", "weaknesses": "- Prompt Scalability: The prompt length grows linearly with the weight dimension of the target algorithm (Section 6, Limitations). This limits practicality for high-dimensional algorithms (e.g., deep neural network training), as prompts could become prohibitively long.\n\n- Lack of Comparison to Prompt-Tuning: The paper focuses on hand-crafted prompts but does not compare to learned prompt-tuning methods (e.g., Lester et al., 2021). It is unclear how hand-crafted prompts perform relative to learned prompts for complex algorithms.\n\n- Limited Algorithm Diversity: The empirical validation focuses on regression and GD—algorithms with clear linear/gradient-based structures. It is unknown if the framework extends to non-linear algorithms (e.g., decision trees, k-means) or sequential tasks (e.g., sorting).\n\n- No Language/Vision Extension: The paper tests only tabular/structured data. It is unclear if the prompt-programmable framework applies to language (e.g., few-shot text classification) or vision (e.g., in-context image segmentation)—domains where ICL is widely used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "891u0Tv0pz", "reviewer": "Reviewer_BBMQ", "summary": "This paper studies the expressive power of the transformer architecture (especially a single attention layer) in the in-context learning (ICL) setting. It shows that (i) a single attention layer can implement the map $[x; y; w] \\mapsto f(x^\\top w - y)x$, extending much of the existing work on the ICL expressivity of transformers; and (ii) Transformers can express the functorial map $(X, A) \\mapsto A(X)$, where $A$ is an attention layer specified by its weights, i.e., there exists a fixed-weight transformer that, given a prompt containing data X and a \"program\" A, executes the program and outputs A(X), provided A is represented in terms of attention weights.", "questions": "(1) Section 4.1 shows how transformer can express $(X, A) \\mapsto A(X)$ when $A$ is described by attention weights. Could a stronger result show that a transformer can express $(X, A) \\mapsto A(X)$ for circuits/Turing machines A subject to structural constraints (e.g., bounded depth)? Does the construction extend to this setting?\n\n(2) Corollary 3.1.3 and 3.1.4 are stated for single-layer attention, but their proof seems to be based on stacking attention attention layers that are implementing GD.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written, and the intuition is explained in detail. The theoretical results are strong and extend several prior papers on the ICL capabilities of Transformer architectures.", "weaknesses": "(1) The innovation over Hu et al. (2025) should be discussed more comprehensively. For the proof of Theorem 3.1, the ideas appear to follow Hu et al. (2025), albeit with substantial technical development. It would be beneficial to clarify which ideas/techniques are inherited from prior work and what are new here.\n\n(2) The dimension of the linear layer is not stated explicitly in the theorems. Providing an explicit bound on this dimension (e.g., in Theorem 3.1, in terms of regularity conditions on $f$) would help readers understand the expressivity at bounded width and would be useful for establishing generalization bounds.\n\nI will adjust my score provided the issues above are addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "X86NKmAlZq", "reviewer": "Reviewer_wRby", "summary": "This work provides a theoretical framework that **frozen softmax attention modules** within minimal Transformer architectures can emulate a wide class of algorithms purely through **prompt programming**. The authors formalize two emulation modes — *task-specific* and *prompt-programmable*. In the **task-specific mode**, they show that a single-head softmax attention layer with a linear map can approximate functions of the general form $f(w^\\top x - y)x$ for any continuous $f:\\mathbb{R}\\to\\mathbb{R}$ and arbitrary precision $\\epsilon>0$. This includes key algorithmic operations such as per-sample gradient computation, single-step and multi-step gradient descent, linear regression, and ridge regression. The main theoretical statement, **Theorem 3.1**, asserts that for any bounded input $X\\in\\mathbb{R}^{(d+1)\\times n}$ and coefficient vector $w\\in\\mathbb{R}^d$, there exists a single-head attention $Attn_s$ and linear map $Linear$ to achieve the desired precision.\n\nFrom this, they derive **Corollary 3.1.1**, which shows that with $f(t) = \\ell'(t)$ for differentiable loss $\\ell$, the layer emulates per-sample gradients $\\ell'(w^\\top x_i - y_i)x_i$, and **Corollary 3.1.2** extends this to one-step gradient descent: for $\\eta>0$, there exists an attention map producing the respective approximation of the $w^{+}_{GD}$.\n\nMulti layer extensions show that stacking $(L+1)$ single-head attention layers yields $L$ gradient descent steps with bounded cumulative error. Similarly, **Corollaries 3.1.3** and **3.1.4** construct attention-based emulations for linear and ridge regression respectively.\n\nIn the **prompt-programmable mode**, the paper’s main result (**Theorem 4.1**) proves that a two-layer softmax attention module with fixed weights can emulate any single attention head by embedding its weights $(W_K, W_Q, W_V)$ into the prompt. Specifically, defining the prompt as\n$$X_p = \\begin{bmatrix} X \\ W_{\\text{in}} \\ I_n \\end{bmatrix}, \\quad W_{\\text{in}} = \\begin{bmatrix} 0\\cdot w & 1\\cdot w & \\cdots & (n-1)\\cdot w \\ w & w & \\cdots & w \\end{bmatrix},$$\nwhere $w = [\\text{vec}(W_K);\\text{vec}(W_Q);\\text{vec}(W_V)]$, they prove\n$$|Attn_s \\circ Attn_m(X_p) - W_V X \\operatorname{Softmax}((W_KX)^\\top W_QX)|_\\infty \\leq \\epsilon.$$\nThus, a **two-layer frozen Transformer** is *universal* for all algorithms implementable by single-layer attention. **Theorem 4.2** provides an equivalent formulation, showing that a single-head attention followed by a multi-head layer with linear projections approximates the same target attention mapping, implying that prompt-programmed softmax attention retains permutation equivariance and can simulate any bounded attention mechanism. **Corollary 4.2.1** extends this to a library $\\mathcal{A}_0 = {a_1,\\ldots,a_k}$ of algorithms, proving that one fixed two-layer module can emulate every $a\\in\\mathcal{A}_0$ \n\nFinally, the authors generalize this to arbitrary linear networks, showing that any trainable linear map $f(x)=\\Theta x$ can be emulated by encoding $\\Theta$ in the prompt — turning static networks into in-context learners that execute dynamically programmable linear mappings.\n\nEmpirical studies (Figures 1–2, Table 1) confirm that softmax attention layers approximate $f(w^\\top x - y)x$ and even emulate attention heads with mean squared error decreasing roughly as $O(1/H)$ with the number of heads $H$. The findings demonstrate that fixed-weight softmax attention networks can serve as **prompt-programmable algorithmic evaluators**.", "questions": "1. The use of ‘L’ seems overloaded at times. What exactly are ‘L’ and ‘P’ in the proof of theorem D.1 in appendix, initiated at lines 1553-54 of appendix in the definition of $\\textbf{X}$ ? Do they follow the same initialization as in lines 2040-2050 on page 38 in the proof of theorem D.6? \n\n2. I am curious if the authors have thought about the extensions to the cases with positional encoding (some form of absolute/relative positional encodings), instead of the Identify pos encoding used in the proofs, along with the default input $\\textbf{X}$. Please note that this question DOES NOT reflect my score, and I am just curious, as the authors have put in much effort to characterize the in-context setup, whether there are any thoughts on the positional encoding case. I understand some forms of positional encoding will break equivariance as well, but irrespective of this, what is your opinion on whether positional encodings will induce any extra complications in the proof sketch if any?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The extension of previous works to propose a framework adaptable to a broader class of algorithms via the prompt-programmability with the fixed attention module transformer is a strong contribution to the community, especially to the line of research focused on guarantees for prompting based approaches. \n\n2. I believe the emphasis in lines 361-363 about - “our results are constructive, providing concrete emulation examples in contrast to prior prompting expressivity (Wang et al., 2023; Furuya et al., 2024) or Turing-completeness results ...” - is a strong contribution as well.", "weaknesses": "1. I have a concern about the final bound discussed in lines 1704 to 1727. Specifically, for the value of $\\epsilon$ that will be attained by plugging the values of $B_f$ and $B$, the bounds for $\\epsilon_1$ and $\\epsilon_2$ need to be quite tight. Can the authors discuss this in a bit more detail? I think this is an important characterization. \n\n2. I have  a serious question about experimental section 5.1 - since the data has been generated synthetically and the parameters ‘W’ as well as the labels ‘y’ are known, I understand that the task should be use the construction in the proof of theorem 3.1 to adjust the input as well as the attention weight matrices appropriately to observe the approximation error. Why was there a need to use an optimizer to perform explicit training? And even if the training has been performed using the optimizer, a direct check is to compute the difference between the learned attention layer weights and the weights generated explicitly in lines 1578-1585 of the proof – although I understand this will likely fail due to issues in optimization and convergence to the other minima. Open to any other suggestions from the authors and looking forward to the clarification in case I mis-understood something here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)