- 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
-
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.
-
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.
-
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
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.
We thank the reviewer for the positive feedback and the constructive suggestions.
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 Nnd 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=2Nnd layers, and 35 (92%) used at most 32=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 N. 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.
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/h residual updates with a common, sufficiently small step size h. Once h 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.
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.
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.