Understanding the Expressive Power and Mechanisms of Transformer for Sequence Modeling

Summary

This paper conducts a systematic study on the expressive power and mechanisms of Transformers for sequence modeling. It explores various properties of Transformers, including the number of layers, attention heads, width, and the use of dot production. The theoretical results are supported by experimental evidence.

Strengths

This paper appears to be technically solid. It provides a detailed formulation of the problem and explores the expressive capabilities of Transformers across various tasks. Notably, it includes experiments in Appendix H to validate its theoretical insights. However, I have not verified the correctness of the proofs. The paper contains some intriguing findings. I particularly want to highlight the exploration between dropout (DP) and relative position encoding (RPE), which I find especially interesting.

Weaknesses

The key weakness of this paper lies in its unclear presentation of motivation, innovation, and contributions. The detailed reasons are as follows: 1) The motivation of this paper appears weak. The authors state their motivation as "to gain a better understanding of how Transformers work in practice." However, there are already numerous studies exploring the expressive power of Transformers, covering most of the topics in this paper. It is unclear why the authors believe the current understanding of Transformers is insufficient and why the community needs this paper. 2) The technical contributions of this work are not clearly presented. It is difficult to discern which conclusions are derived from known techniques and which are based on new techniques proposed by the authors. Additionally, the nature of these new techniques is not clearly explained. 3) The paper's analysis is based on dividing tasks into three categories: modeling fixed, long but sparse memories; modeling adaptive, long but sparse memories; and modeling essentially sparse memories. However, the necessity of this categorization and the relationships between these tasks are unclear. The authors claim these categories are prevalent, but the supporting evidence is weak.

Questions

1) This paper includes numerous proofs, making it challenging to verify their correctness. Could the authors provide a proof sketch for Theorem 4.4? 2) The tightness of the bound is also uncertain. Could the authors provide a numerical result demonstrating the bound in a toy case?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

N/A

Summary

The paper investigates the approximation capabilities of transformers with relative positional encodings and derives approximation rates for three types of sequence modeling tasks. Each task corresponds to a particular choice of target function class. Namely, a first class of mappings are fixed, long but sparse memories (equation (5)), and the authors focus on dot-product free transformers. A second class are adaptive, long but sparse memories (equation (8)), and the authors consider deep transformers with specific precision and no SoftMax. The last class of mappings are essentially sparse memories and consist of convolving the input sequence with different kernels where, again, the considered Transformers are dot-product free. Each approximation rate is commented on the role of the feedforward and self-attention components, the role of dot-product attention (that is, the fact that the attention maps depend on the input sequence through pairwise interactions), and the effect of relative position encoding (whether it is of linear or logarithmic type).

Strengths

- The paper is well written and easy to follow. - The mathematical results are all supported with detailed and rigorous proofs. - Each Theorem is structured in the same way which eases the understanding of the whole paper. - The paper adresses the important question of approximation rates of Transformers in sequence modeling. - The paper establishes rigorous approximation results for Transformers on sequences modeling tasks. These results are significant and give insights on the role of the different Transformer components on their approximation capabilities. - The three problem formulations are clearly defined and commented.

Weaknesses

- Unless I missed something, the "true" attention mechanism (line 104) is never used in the paper to derive approximation rates. In sections 3 and 5 the attention is DPF, while in section 4 there is no softmax and quantization is used. I don't think this is a major problem, but it should be emphasised (perhaps by extending remark 2.2) that you never consider the transformer with all the bells and whistles. - I understand that the dimension of the embeddings grows with $Md$. This is not mentioned in the main text, nor commented on in the supplement. How does this compare with previous work? - Also, you mention that the number of heads needed grows at least polynomially with the $T_i$'s. I understand that this is due to the particular choice of RPE. Would other types of PE give a better dependency in the $T_i$'s ? How does the current dependency compare with previous works? - Paragraph l. 274 to l. 277 is unclear. When do you use this alternative in the rest of the paper? - Typo in l. 281 - l. 282, I don't understand the notation for the lower bound on $m$.

Questions

- Please see some questions in the Weaknesses part. - What do you mean by rate $n$ in all the theorems ? Is there an optimal choice for $n$ ? - What is the main reason why you did not consider the SoftMax in section 4 ? - How does $C(n)$ behaves with $n$ ? - Could you approximate the model with specific precision with another Transformer which does not rely on specific precision ? - Overall, the spirit of the approximation in the paper is always to form augmented tokens $(x_{t}, x_{t-t_1}, \dots x_{t-t_M})$ using attention and to apply the MLP on top of it. Do you think this is the "optimal" way ? And if so, what are the reasons behind it ?

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

Yes, the authors adequately addressed the limitations of their work.

Summary

The paper provides a thorough analysis of the expressive power of Transformers. It does so by investigating the relative importance of different architectural components, such as the mixing layer (dot product attention), the feed-forwad block and positional embeddings. More specifically, the paper studies three different tasks, characterised by different levels of complexity, sharing some key properties with relevant realistic applications such as n-gram models, sparse Boolean functions (Task I), Adaptive sparse Boolean functions, parsing, part-of-speech tagging (Task II), feature extraction in image and signal processing (Task III). On each of such tasks, the paper studies the approximation rates of transformer models defined in terms of their number of layers $L$ and heads $H$, the width of the feed-forward module $m$ and the type of relative positional embedding utilised (i.e. either Alibi or T5 style). Through its theoretical analysis the paper shows that the necessary model's complexity needs to adapt to the complexity of the task. Moreover by investigating the role of different components, the paper shows that dot-product attention is necessary for more complex tasks (Task II) while its dot-product free variant provably fails. Nevertheless, the authors show that the task can still be solved with a more parameter efficient alternative. In addition, the role of the feed-forward blocks is mainly to approximate readout functions and memory functions, aligning with classical results on approximating Barron functions. The theoretical results are corroborated with empirical results.

Strengths

* The paper meaningfully contributes to the very relevant research line on theoretical analysis of transformers models. * The paper originally addresses important questions, such as the relative role of different components in the transformer architecture and the necessity of the dot-product attention, through a principled approach and in a controlled framework. * Generally the paper is very well written (modulo some sparse and minor typos) and pleasant to read.

Weaknesses

* Some concepts could be better introduced: for example, it was not clear to the reviewer what the authors meant by "memories" in the introduction of the paper. While this gets clearer later, it would be helpful to clarify it earlier. * Layer normalization, an important component of modern transformers, does not seem to be included in the analysis. What effect do you expect it to have on your results? * The role of the embedding dimension $D$ is not considered in the reported rates. What is the effect of varying $D$ on the approximation rates of the model?

Questions

See weaknesses section.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

4

Limitations

The limitations of the paper are discussed in section 7