acceptodds
Under review as a conference paper at ICLR 2027

Universal interpolation for deep residual self-attention networks

Abstract

Universal approximation is a necessary qualitative property of learning architectures to benefit from scaling laws. While it is generically verified on a variety of neural architectures and random feature models, it typically involves infinite width limits. In this work, we focus on deep self-attention models and consider instead the `dual' regime, where approximation power is enabled entirely by depth, and featuring strong parameter sharing across layers, motivated by recent models such as the Looped Transformers. More specifically, we ask whether one can find a predefined finite set of parameters, each defining an attention block, such that the resulting finite set of transformations can map any collection of sequences of tokens to any other collection of sequences of tokens. Crucially, these transformations are fixed independently of the input and output collections: only the order in which the blocks are applied, their signs, and their durations depend on the particular interpolation task. Our main result establishes it for residual softmax attention using only two frozen single-head blocks with Gaussian-initialized projection matrices. The result holds at both continuous and finite depth. We also characterize the restrictions imposed by causal masking and establish corresponding universal interpolation guarantees.

Primary area:
learning theory
Keywords:
transformer expressivity, universal interpolation, self-attention, geometric control theory, neural ODEs

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_54CrOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the expressive power of deep residual self-attention networks, where depth rather than width provides the expressivity. Motivated by looped transformers, it asks whether a small set of attention blocks, fixed before seeing the data, can map any N input sequences to any N targets. Fitting a dataset only chooses the order, signs, and durations of these blocks. The paper calls this universal interpolation and proves it with a Lie-bracket criterion from control theory. The main result shows that two random single-head blocks suffice, for any N and sequence length. The paper also shows that causal masking rules out interpolation when N > d.

Critical strengths
  • Novelty. Universal interpolation is a stronger notion than exact interpolation, and it is motivated by a practical setting, looped transformers. I find the Lie-bracket idea intriguing: it shows that compositions of a few fixed nonlinear maps can be highly expressive.
  • The main result is strong and clean. Only two random blocks are needed, and the same draw works for every batch size N and sequence length n (Thm. 3.5). This extends the two-field result of Agrachev & Letrouit (2026) to standard softmax attention, which they left open.
Critical weaknesses
  1. There is little implication for practical ML methods. The results give no quantitative bound on the number of loops (depth). The authors state this themselves: "Neither construction gives a bound on total depth or parameter norms" (Sec. 2.3). The block durations or scalar gains may also be arbitrarily large. That said, the theoretical contribution of this paper should be evaluated on its own.

  2. The setting differs from actual looped transformers. I understand that universal interpolation is a useful notion, as the looped-transformer motivation shows. However, this paper uses random weights for each block and chooses the sign, coefficient, and position of each block depending on the data. This seems far from the actual setting. In particular, a looped transformer usually repeats one trained block a fixed number of times. Here, the data-dependent order of the two blocks and the real-valued gains do the work that training does in practice. The model also has no MLP or layer normalization.

  3. The numerical evidence is limited. Sec. M only checks the Lie rank at small sizes (D ≤ 36, plus one pilot run at D = 96), and the results are sensitive to the numerical tolerance near the threshold. The paper does not show any actual interpolation trajectory, even on a toy example, so we cannot see the depth or the gains that are needed in practice.

Questions for authors
  • What practical implications do you have in mind? For example, Sec. M notes that a single generator has Lie rank at most one, so looping a single fixed block cannot interpolate. Does this mean that a looped transformer needs at least two blocks that are mixed in a data-dependent order? What would this look like in a real architecture?
  • Can you say anything about how the required depth or gains grow with N, even for a toy example?
2 comments

We thank the reviewer for the positive feedback and the constructive suggestions.

W1+Q2+W3 “There is little implication for practical ML methods. The results give no quantitative bound on the number of loops (depth) (...) That said, the theoretical contribution of this paper should be evaluated on its own.” + "(...) The paper does not show any actual interpolation trajectory, even on a toy example, so we cannot see the depth or the gains that are needed in practice." + "Can you say anything about how the required depth or gains grow with N, even for a toy example?”

Indeed, we do not provide quantitative upper bounds on depth, the number of switches, or durations. A direct consequence of the interpolation property for generic targets is that the number of parameters diverges as the required memorization capacity increases with a lower bound of NndNnd on the depth. For a concrete numerical illustration, please see our response to W2a+W4+Q2 of Reviewer 1Qtf. Among the 38 successful cases, 25 (66%) were solved at the initial search depth of 16=2Nnd16=2Nnd layers, and 35 (92%) used at most 32=4Nnd32=4Nnd layers. These are the depths found by the search, rather than minimum required depths. They provide an empirical indication of the depth needed in this toy setting, but do not establish a general upper bound or a scaling law with NN. A natural next step is then to establish approximation rates, which is a distinct question beyond the scope of this paper. See also our answer to your W2a for a discussion of the trade-off between gain magnitude and depth in approximate interpolation.

As mentioned in the conclusion, a promising direction is also to better understand the trade-off between depth and the number of distinct frozen blocks. A larger dictionary may provide directions directly that would otherwise require higher-order Lie brackets, reducing the depth needed for interpolation. Asymptotic comparisons would help quantify this trade-off. This thus motivates the (natural) intuition that a looped transformer may require greater effective depth to match the expressivity of a transformer with independently parameterized layers. Making this connection precise remains an interesting open question.

W2a The setting differs from actual looped transformers. I understand that universal interpolation is a useful notion, as the looped-transformer motivation shows. However, this paper uses random weights for each block and chooses the sign, coefficient, and position of each block depending on the data. This seems far from the actual setting. In particular, a looped transformer usually repeats one trained block a fixed number of times. Here, the data-dependent order of the two blocks and the real-valued gains do the work that training does in practice.

Our motivation from looped transformers is to understand how extreme parameter sharing affects expressivity. The surprising finding is that even two randomly sampled, frozen attention blocks suffice for universal interpolation on the stated domains, through repeated composition with suitable signed scalar gains and sufficient depth. However, our result goes beyond transferring task-dependent parameters from attention matrices to scalar gains. Indeed, while real-valued gains enable exact universal interpolation, they are unnecessary when approximation suffices. Specifically, a flow of duration tt along a signed attention field can be approximated by roughly t/ht/h residual updates with a common, sufficiently small step size hh. Once hh is chosen for the desired approximation, each layer only selects the block and its sign: durations are encoded by repetition counts, with smaller steps requiring greater depth. This shows that strong parameter sharing remains compatible with universal interpolation. We agree that this does not directly establish the same property for a standard trained looped transformer; it provides an intermediate theoretical result toward understanding expressivity under extensive parameter reuse.

W2b The model also has no MLP or layer normalization.

Our attention-only setting isolates the expressive contribution of attention. We discuss which results extend directly and outline possible adaptations for MLPs and LayerNorm in our response to W2b+Q4 of Reviewer 1Qtf.

Q1 What practical implications do you have in mind? For example, Sec. M notes that a single generator has Lie rank at most one, so looping a single fixed block cannot interpolate. Does this mean that a looped transformer needs at least two blocks that are mixed in a data-dependent order? (...)

Thank you for pointing that out! A consequence of our results is indeed that if you consider a looped transformer with only one attention-only block, you will not be able to have exact interpolation in the continuous-depth regime for generic targets. See also our answer to Q5 of Reviewer 1Qtf for our discussion on possible practical implications.

Thank you for the detailed responses and the new toy experiments. The step-size argument for approximate interpolation is convincing. This addresses my concern that the data-dependent parameters are simply moved into the gains. The toy experiments also give a concrete picture of the depth needed in the actual setting. I suggest adding both the step-size argument and the toy experiments to the revised paper.

The lack of a depth bound and of practical implications remains a limitation, as you also acknowledge, but I think the theoretical contribution is interesting on its own. I therefore raise my score from 3 to 4.

Reviewer_1QtfOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper analyzes the expressiveness of attention-only networks (Transformer blocks without positional encoding, MLP, LayerNorm). For this given architecture, the authors define the property of "universal interpolation": First, a set of attention blocks is initialized and frozen without training. Then, only the order of the blocks, their signs, and durations are adjusted to map input tokens to the corresponding output tokens.

The paper finds that two single-head attention blocks initialized with Gaussian distribution are expressive enough for almost any token configuration (e.g. no zero tokens) independent of the sequence and its length. In the case of causal attention, this property is more limited: Since the first token only attends to itself, the update is linear, and linear relationships between first tokens of sequences cannot change. When there are more sequences than token dimensions, an exact interpolation cannot be modeled, and it only works when input and target sequences share the first token relationships.

Overall, it is a very clean theoretical contribution. However, it mainly reports the existence of this property and does not provide any bounds on how deep the attention network must be, how such a configuration can be found, and how well it generalizes. Therefore, practical impact remains limited.

Critical strengths

The research question is well positioned in the literature and relevant: Looped and recurrent-depth transformers both use stacks of identical blocks, so asking if stacking fixed blocks is universal is interesting for the field in general. The results themselves are not obvious and genuinely interesting and the message that "two random attention blocks have all the needed expressive power" is striking.

Especially since looped transformers are explored more and more in language tasks, these findings provide a theoretical grounding.

Also, the limitation regarding causal attention is honestly mentioned, and the reasons are analyzed and well discussed.

The mathematical formulation and the proofs I checked look solid, and I could not find any issues or reason to doubt them. It relies on well-established principles from control theory, which is good.

Critical weaknesses

The paper reports the existence of this universal interpolation property but does not provide any bounds regarding the depth, number of switches, and durations. Since each layer only adds one free number (the gain), the network will likely require many layers. It could be argued that the data-dependent parameters are not removed but are moved into the gains of the added layers. This strongly limits the relevance for practical applications. Also, part of the motivation, namely the link to looped transformers, might be weaker than admitted: while looped transformers generalize, the described framework does not address generalization and it could just be memorization in sufficiently many gain parameters.

Furthermore, the paper focuses on the existence of the solution but not how it can be learned. So it remains unclear how the ordering and scaling of the blocks can be obtained. The model itself is limited to the self-attention blocks and does not have positional encoding, MLP layers, LayerNorm, etc. Again, while this is fine for a theory paper, the practical impact is limited.

The main result that 2 attention blocks are expressive enough needs a single head with a width of at least the token dimension. For the typically used multi-head attention, a proof is only given with a number of blocks growing with dataset-size. For a fixed number of blocks, only numerical checks are provided. Also, many properties are limited to non-causal Transformers and do not fully transfer to decoder models, which are the currently dominant paradigm.

While the theoretical side is strong, the experimental side is thin: There is no demonstration of building such a network to fit a dataset, nor one with a full looped model.

Also, I had some issues with the terminology. E.g., explicitly saying that batch means the entire dataset, or removing dual regime from the abstract could help. Also, each symbol should carry just one meaning across the entire paper (e.g., p, r, A, H, M, m).

Questions for authors
  1. A lower bound could be that the network needs at least Nnd layers (one gain per layer for Nnd targets), is this correct? Could you give an upper bound?
  2. Can you build a toy case (small dimensions, artificial data) and then build such a network with two blocks and measure the error? E.g. could the blocks and order be fixed and then the layer-gains be optimized using gradient descent?
  3. Can you explain why universal approximation is necessary to benefit from scaling laws, i.e., how this claim is supported?
  4. Which part of the results would survive if a full Transformer block is used (adding LayerNorm, MLP, etc.)?
  5. What would you say is the most valuable practical impact of this finding?
2 comments

We would like to thank the reviewer for the positive feedback and the constructive suggestions.

W 1a The paper reports the existence of this universal interpolation property but does not provide any bounds regarding the depth, number of switches, and durations. Since each layer only adds one free number (the gain), the network will likely require many layers. It could be argued that the data-dependent parameters are not removed but are moved into the gains of the added layers.

Indeed, we do not provide quantitative bounds on depth, the number of switches, or durations. A direct consequence of the interpolation property is that the number of parameters diverges as the required memorization capacity increases. A natural next step is then to establish approximation rates, which is a distinct question beyond the scope of this paper.

As mentioned in the conclusion, a promising direction is also to better understand the trade-off between depth and the number of distinct frozen blocks. A larger dictionary may provide directions directly that would otherwise require higher-order Lie brackets, reducing the depth needed for interpolation. Asymptotic comparisons would help quantify this trade-off. This thus motivates the (natural) intuition that a looped transformer may require greater effective depth to match the expressivity of a transformer with independently parameterized layers. Making this connection precise remains an interesting open question. See also our answer to your Q1.

W1b Also, part of the motivation, namely the link to looped transformers, might be weaker than admitted: while looped transformers generalize, the described framework does not address generalization and it could just be memorization in sufficiently many gain parameters.

We agree that our results concern expressivity and do not establish generalization. Our motivation from looped transformers is to understand how extreme parameter sharing affects expressivity. The surprising finding is that even two randomly sampled, frozen attention blocks suffice for universal interpolation on the stated domains, through repeated composition with suitable signed scalar gains and sufficient depth. However, our result goes beyond transferring task-dependent parameters from attention matrices to scalar gains. Indeed, while real-valued gains enable exact universal interpolation, they are unnecessary when approximation suffices. Specifically, a flow of duration t along a signed attention field can be approximated by roughly t/ht/h residual updates with a common, sufficiently small step size hh. Once hh is chosen for the desired approximation, each layer only selects the block and its sign: durations are encoded by repetition counts, with smaller steps requiring greater depth. This shows that strong parameter sharing remains compatible with universal interpolation. We agree that this does not directly establish the same property for a standard trained looped transformer; it provides an intermediate theoretical result toward understanding expressivity under extensive parameter reuse.

W2a + W4 + Q2 “The paper focuses on the existence of the solution but not how it can be learned. So it remains unclear how the ordering and scaling of the blocks can be obtained.” + “There is no demonstration of building such a network to fit a dataset, nor one with a full looped model” + “Can you build a toy case (small dimensions, artificial data) and then build such a network with two blocks and measure the error? E.g. could the blocks and order be fixed and then the layer-gains be optimized using gradient descent?”

Our main goal is to gain insight into how parameter sharing affects network expressivity; as such we do not claim to propose a new optimization algorithm for our network construction.

To complement this theoretical analysis and address your request, we constructed and fitted toy networks with N=n=d=2N = n = d= 2, reusing two frozen Gaussian-initialized attention blocks. We considered two tasks: a 90-degree rotation of unit-circle tokens, and interpolation between independently sampled Gaussian inputs and targets. We used a two-phase search on CPU, with eight searches running in parallel. The first phase tried alternating and random block sequences, optimizing the scalar layer gains from different initializations using damped Gauss-Newton. When this did not find a solution, the second phase revisited promising candidates, perturbed their gains or modified their block sequences and depths, and then reoptimized the gains. With at most 64 layers and a shared wall-clock budget of 120 seconds per problem, the procedure achieved relative Frobenius error below 10−410^{-4} in 38/40 cases across 20 seeds evaluated on both tasks: 18/20 for rotation and 20/20 for random interpolation. Of these, 34 cases were solved in the first phase and 4 in the second. Among successful cases, 25/38 (66%) were solved at the initial search depth of 16=2Nnd16= 2Nnd layers, and 35/38 (92%) used at most 32=4Nnd32=4Nnd layers (these are the depths found by the search, rather than minimum required depths).

Although this experiment searches over block sequences, optimizing the block order is not necessary for expressivity when depth is unrestricted. Any KK-layer composition of the two blocks can be embedded in a fixed alternating schedule of at most 2K2K layers by assigning zero gains to unused positions. Consequently, the discrete ordering could be fixed in advance, leaving only scalar gains to optimize. The resulting optimization over scalar gains may still be challenging in practice.

Reviewer_YXnDOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper asks whether the same attention blocks can memorize different datasets without changing their weights. It shows that two randomly initialized, frozen noncausal softmax attention are enough, under assumptions, for almost all input–target datasets. Each dataset is fitted by changing how the blocks are repeatedly applied and scaled. The results cover both continuous-depth models and networks with finitely many layers, although they do not bound the required depth. The paper also studies causal attention and dentifies restrictions caused by the first token attending only to itself and proves interpolation guarantees for inputs and targets.

Critical strengths
  1. This paper is well written. Although the topic is quite technical, the authors do a good job of explaining the research question, the gap in existing work, and the motivation for their theoretical contributions.

  2. The theoretical results appear novel and important. They show that softmax attention has strong interpolation capabilities using fixed-weight blocks, covering both continuous and finite depth as well as causal attention. I find the results interesting and the theoretical development comprehensive. However, I am not an expert in Lie algebra, the main mathematical tool used in the proofs, so my assessment may be mistaken.

Critical weaknesses
  1. The main proof ideas could be more accessible to ML readers unfamiliar with Lie algebra. A simple example or figure showing how the proof tools lead to exact interpolation would help. Also in the proof, some paragraphs combine several derivation steps, which I found hard to follow. Breaking them into shorter steps and explaining the purpose of each would improve readability (although my difficulty may partly reflect my limited familiarity with these techniques, I'll leave this to AC's judegement) For longer arguments, such as the proof of thm 3.5 in appendix L, especially lemma L.7, a clearer roadmap would help me understand the overall logic before working through the details.

  2. Although the results follow a logical order, the large number of formal statements makes it difficult to track what each adds. This is particularly noticeable around thm 3.3, corollary 3.4, thm 3.5, and corollary 3.7. Transition between this result will be helpful. Short reminders of what has been established, what changes in the next result, and why that matters would help readers follow the argument.

Questions for authors
  1. I'm curious what would change if it were replaced with linear attention? Not asking for a new proof, but a brief discussion of which guarantees or proof steps would change would help clarify the scope of the results.

  2. My understanding is that exact interpolation corresponds to memorizing a finite dataset. Could you briefly compare your results using frozen blocks with the memorization-capacity results in [1]? A short discussion of the differences in assumptions and guarantees would help clarify the connection.

[1] Tokio Kajitsuka and Issei Sato. “On the Optimal Memorization Capacity of Transformers.” ICLR, 2025.

2 comments

We would like to thank the reviewer for the positive feedback and the constructive suggestions.

W1a. The main proof ideas could be more accessible to ML readers unfamiliar with Lie algebra. A simple example or figure showing how the proof tools lead to exact interpolation would help.

Thank you for pointing that out, we’ve accordingly updated Section 2.2.1 (with changes highlighted in red) to provide more intuition about Lie brackets, the Chow-Rashevskii theorem, and their connection to exact/universal interpolation.

W1b. Also in the proof, some paragraphs combine several derivation steps, which I found hard to follow. Breaking them into shorter steps and explaining the purpose of each would improve readability (...) For longer arguments, such as the proof of thm 3.5 in appendix L, especially lemma L.7, a clearer roadmap would help me understand the overall logic before working through the details.

Thank you for this suggestion. We have added a roadmap at the beginning of Appendix L and reorganized the proof of Lemma L.7 into explicit steps and with more details, to make the overall argument easier to follow.

W.2 Although the results follow a logical order, the large number of formal statements makes it difficult to track what each adds. This is particularly noticeable around thm 3.3, corollary 3.4, thm 3.5, and corollary 3.7. Transition between this result will be helpful (...)

Thank you for pointing that out, we’ve accordingly updated the manuscript!

Q1. I'm curious what would change if it were replaced with linear attention? Not asking for a new proof, but a brief discussion of which guarantees or proof steps would change would help clarify the scope of the results.

It’s an interesting question! For linear attention, each sequence $X = (x_1, …, x_n) $ (with the tokens in column here) evolves as F(X)=A(X)X=(VXX⊤W)XF(X)= A(X ) X = (V X X^\top W) X Hence all linear relations among its tokens Xc=∑cixi=0X c = \sum c_i x_i = 0 are preserved at both continuous and finite depth. When n>dn>d, generic targets violate these relations, ruling out universal interpolation even for N=1N=1. For n≤dn \leq d, the question requires further analysis. Our proofs use softmax concentration to isolate tokens, and exponential asymptotics and independence to establish full Lie rank and connectedness for two blocks. These steps do not transfer directly, although the general control-theoretic framework remains applicable.

Q.2. My understanding is that exact interpolation corresponds to memorizing a finite dataset. Could you briefly compare your results using frozen blocks with the memorization-capacity results in [1]? A short discussion of the differences in assumptions and guarantees would help clarify the connection.

Thank you for this comment. Exact interpolation is indeed a form of finite-sample memorization. Kajitsuka and Sato [1] quantify the number of parameters needed to memorize discrete labels under separation and consistency assumptions, using a single attention layer and deep feed-forward networks of fixed width. Our exact-interpolation results isolate the role of attention in memorization: residual attention-only networks can fit prescribed real-valued outputs on admissible configuration domains, without feed-forward blocks. This complements the attention-only memorization results of Dana et al. 2025. Our guarantees concern feasibility, without complexity bounds comparable to those of [1]. Our frozen-block results additionally require a dictionary fixed independently of the dataset, which we call universal interpolation. We’ve updated our related work section.

Thank you to the authors for the clear rebuttal. My concerns have been resolved. This will be an interesting paper. I'll raise my score accordingly.

One small suggestion, though it won't affect my evaluation

  • A geometric overview figure could make the main result more intuitive. For example, it could visualize how two fixed attention blocks successively transform a simple 2D dataset to fit the target outputs.

Comments on the paper

1 comment

Dear Reviewers,

We would like to thank you all for the positive and constructive discussions. Following the suggestions of Reviewers 1Qtf and 54Cr, we've added the toy experiments to Appendix Q. We've also included the step-size argument in Remark 2.11, as suggested by Reviewer 54Cr. We will also add a geometric overview figure, as suggested by Reviewer YXnD.

Thank you again for your time and helpful suggestions.

The authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.