Q3: My second minor concern is that the theoretical research on Looped Transformers may have lost its research value…. In the most critical application areas for transformers, such as autoregressive models and LLMs, Looped Transformers are not commonly used, and their performance does not match that of transformer architectures.

A3: Looped Transformers hold their research value because of the following three points.

1. [Extensive Practical Applications and Research Interest.] Looped Transformers have been practically studied for efficient and competitive capabilities [1, 2] and remain an active area of research. Previous works have studied their Turing completeness [3], generalization ability [4, 5], inductive bias for reasoning tasks [6], ability of learning iterative algorithms for in-context learning [7, 8, 9], and potential to simulate graph algorithms [10].

   To highlight the advantages of Looped Transformers, we included the following sentence in the introduction section. We cover related works in subsection 2.2

   line 24: This structure offers advantages over standard Transformers, such as inductive bias, parameter efficiency, and Turing completeness.

2. [Distinct from RNNs.] Looped Transformers differ from RNNs. The recurrent structure is fundamentally distinct. In particular, Looped Transformers retain the parallelism that has been a critical advantage driving the adoption of Transformers over RNNs.

3. [Potentially Advantage for Complex Tasks.] Our experiments demonstrated that Looped Transformers solve certain dynamic programming problems, which standard Transformers struggle with (as shown below). Given the current trend of moving from language tasks to more complex ones like mathematical theorem proving, Looped Transformers may hold increasing value.

In research, we believe that significance lies not only in models already in use but also in exploring a broad range of models that may potentially become important in the future.

[1] Lan et al., ALBERT: A Lite BERT for Self-supervised Learning of Language Representations. ICLR 2020.
[2] Bae et al., Relaxed Recursive Transformers: Effective Parameter Sharing with Layer-wise LoRA. 2024.
[3] Giannou et al., Looped Transformers as Programmable Computers. ICML 2023.
[4] Dehghani et al., Universal Transformers, ICLR 2019.
[5] Fang et al., Looped Transformers for Length Generalization. 2024.
[6] Anonymous, Understanding Reasoning with Looped Models. ICLR 2025 under review.
[7] Yang et al., Looped Transformers are Better at Learning Learning Algorithms. ICLR 2024.
[8] Giannou et al., How Well Can Transformers Emulate In-context Newton's Method? 2024.
[9] Gatmiry et al., Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning? ICML 2024.
[10] Luca and Fountoulakis, Simulation of Graph Algorithms with Looped Transformers. ICML 2024.

We sincerely appreciate your time and thoughtful review of our paper. Please find our responses to your questions below.

Q1: My main concern lies with the novelty of the work. It is well known that Looped Transformers can be viewed as a type of tied-parameters transformer, and the universal approximation theory for transformers has already been extensively studied.

A1: Our paper is the first to establish the approximation rate of Looped Transformers, introducing three novel types of modulus of continuity newly defined for sequence-to-sequence functions. Due to the structural constraints imposed by weight-tying, which limit their flexibility, universal approximation theories for Transformers cannot be directly applied. Consequently, even proving the universal approximation theorem for fixed single-layer Looped Transformers is non-trivial.

For the case of ReLU networks, Zhang et al. [1] provided significant insights into the expressive power of weight-tied ReLU layers. While the universality of ReLU networks has been extensively studied, their findings regarding the surprising capacity of a single fixed-size ReLU layer and the potential for enhancement through composition were particularly novel.

The approximation rate provides a clear theoretical understanding of how the error decreases as the number of loops increases, its dependency on data, and the rate of reduction. It enables better model design with theoretical guarantees.

[1] Zhang et al., "On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network," ICML 2023.

We added the following explanation to clarify our novelty.

line 41: Due to the structural constraints imposed by weight-tying, which limit their flexibility, existing universal approximation theories for Transformers cannot be directly applied.

Q2: Moreover, the theoretical analysis presented does not yield any novel conclusions regarding the training of Looped Transformers. The finding that performance increases with the number of loops does not seem particularly innovative. Therefore, I have not yet identified any significant conclusions from this work.

A2: Beyond establishing the approximation rate, our work identifies a specific limitation inherent to the looped architecture. To address this, we introduce the incorporation of scaling parameters for each loop, implemented with conditioning on timestep encoding (see Sec.4). We demonstrate the enhancement via timestep encoding both theoretically and experimentally. While the result that performance improves with more loops may seem straightforward, the approximation rate we derive, along with its dependency on the continuity properties of sequence-to-sequence functions, represents a non-trivial contribution.

In addition, to validate the enhancement via timestep encoding, we add empirical evidence on in-context learning (decision tree function class) and language modeling (WikiText103).

In-Context Learning (MSE(↓) for Decision Trees)

Language Modeling (WikiText-103)

Dear Reviewer MxAi,

Thank you for taking the time to review our paper and provide valuable feedback. We have submitted a rebuttal addressing the issues and suggestions you kindly pointed out. Could you confirm if our response has adequately resolved the concerns you raised? If there are any areas where our response may still be insufficient, we would greatly appreciate further clarification or guidance, as we are eager to engage in a constructive discussion.

Your insights are essential for improving the quality of our paper, and we sincerely look forward to hearing from you.

Best regards

We sincerely appreciate your time and thoughtful review of our paper. Please find our responses to your questions below.

Q1: The experimental validation is relatively limited. In particular, only one task is evaluated on the timestep encoded model compared with the baseline. The authors are encouraged to test on more tasks including basic ones (e.g. inductive heads) for better validation of the model improvement and use ablation studies for more detailed characterization.

A1: Thank you for your helpful suggestions. We expanded 5 experiments include additional dynamic programming problems (subset sum, knapsack, LCS), in-context learning (decision tree function class), analogous to inductive heads, and language modeling using the WikiText-103 dataset. We are conducting additional experiments and will report the results in the discussion thread if they are ready in time.

Dynamic Programming (Accuracy (↑))

In-Context Learning (MSE(↓) for Decision Trees)

Language Modeling (WikiText-103)

Q2: How tight is the approximation rate bound derived from the paper? It would be interesting to see empirical results that validate equation (9) or (10).

A2: Thank you for your insightful question. The tightness of the approximation rate remains an open issue. Although we can state that it aligns with the findings of prior studies on ReLU networks [1], designing sequence-to-sequence functions while controlling the three types of continuity is challenging. Furthermore, even the tightness of ReLU has not been thoroughly investigated. This will be addressed as a direction for future research.

[1] Zhang et al., "On Enhancing Expressive Power via Compositions of Single Fixed-Size ReLU Network," ICML 2023.

We add this limitation in Conclusions as follows.
line 537: While we have derived upper bounds, the tightness of these approximation rates is still undetermined.

We sincerely appreciate your time and thoughtful review of our paper. Please find our responses to your questions below.

Q1: To enhance clarity, it would be beneficial to include comparison charts against current Looped Transformer models. These charts would help to emphasize the advantages of the proposed methodology and illustrate the behavior observed across different models.

A1: To enhance clarity, we add the chart of our timestep encoding methodology as Figure 2: Timestep encoding architecture. The difference is relatively straightforward, so the pseudocode below provides a simple comparison, which I hope will be helpful for understanding.

Standard Block

def forward(x):
    x = x + attn(norm1(x)) 
    x = x + mlp(norm2(x))
    return x

w/ Timestep Encoding

def forward(x, t):
    t_emb = timstep_enc(t)
    scale_msa, scale_mlp, gate_msa, gate_mlp = ada_mlp(t_emb).chunk(4)
    x = x + gate_msa * attn(norm1(x) * (scale_msa)
    x = x + gate_mlp.unsqueeze(1) * mlp(norm2(x) * scale_mlp)
    return x

Q2: Are you planning to scale up experiments by using different models? Is it anticipated to be feasible to apply the proposed architecture to different scenarios? Are there any future work plans?

A2: Thanks to your suggestion, we expanded 5 tasks: dynamic programming problems (subset sum, knapsack, LCS), in-context learning (decision tree function class), and language modeling using the Wikitext-103 dataset. We are conducting additional experiments and will report the results in the discussion thread if they are ready in time.

Dynamic Programming (Accuracy (↑))

In-Context Learning (MSE(↓) for Decision Trees)

Language Modeling (WikiText-103)

Q3: The redaction can be challenging to follow in certain sections, particularly where large equations are interspersed with text (e.g., Theorem 3.7, Lemma 4.2).

A3: The layout is currently constrained by space limitations; however, we will make effort to address this issue and improve readability.

Dear Reviewer H7Gd,

Thank you for taking the time to review our paper and provide valuable feedback. We have submitted a rebuttal addressing the issues and suggestions you kindly pointed out. Could you confirm if our response has adequately resolved the concerns you raised? If there are any areas where our response may still be insufficient, we would greatly appreciate further clarification or guidance, as we are eager to engage in a constructive discussion.

Your insights are essential for improving the quality of our paper, and we sincerely look forward to hearing from you.

Best regards

Experimental results

Dynamic Programming (Accuracy (↑))

In-Context Learning (MSE(↓) for Decision Trees)

Language Modeling (WikiText-103)