Representational Strengths and Limitations of Transformers

Summary

This paper investigates the representation power of attention layers in transformer networks and compares them with other neural network architectures. The authors establish both positive and negative results on the benefits and limitations of attention layers, focusing on intrinsic complexity parameters such as width, depth, and embedding dimension. The positive results include the demonstration of a sparse averaging task where transformers scale logarithmically in the input size, compared to polynomial scaling in recurrent networks and feedforward networks. They also show the necessity and role of a large embedding dimension in transformers. On the negative side, they present a triple detection task where attention layers have linear complexity in the input size. However, they also provide variants of the task that can be efficiently solved by attention layers. The paper's contributions include the formalization of computational limits using communication complexity, the establishment of the representational capabilities and limitations of self-attention units, and the demonstration of the impossibility of computing Match3 using standard multi-headed attention layers in an efficient manner.

Strengths

- This paper brings some original contributions to the understanding of attention layers in transformer networks. It provides a mathematical analysis of the representation power of attention layers and compares them to other neural network architectures. The paper introduces some interesting tasks, such as sparse averaging, pair matching, and triple matching, to evaluate the capabilities and limitations of attention layers. This approach introduces fresh perspectives on the benefits and deficiencies of attention layers and offers valuable insights into their role in deep learning. - The paper demonstrates a high level of quality in terms of its analysis and proofs. It presents rigorous mathematical formulations and provides formal definitions for the tasks and architectures under study. The proposed theorems and conjectures are well-supported and backed by detailed proofs, showcasing the authors' expertise in the subject matter. The use of communication complexity techniques adds depth and reliability to the analysis. The paper also includes supplementary proofs and explanations in the appendices, further enhancing the quality and comprehensiveness of the work. - The paper addresses an important gap in the literature by providing a mathematical analysis of the benefits and limitations of attention layers in transformers. The findings have implications for the design and optimization of deep learning models, especially in natural language processing and other sequential tasks. The identification of tasks that highlight the strengths and weaknesses of attention layers can guide future research in developing more efficient and effective architectures. The paper also raises intriguing conjectures, such as the impossibility of efficiently computing Match3, which can inspire further investigations and spark valuable discussions in the research community.

Weaknesses

- While the paper provides rigorous mathematical analysis and proofs, it lacks empirical evaluation of the proposed tasks and architectures. Including experiments using real-world datasets could provide practical validation of the theoretical findings and further strengthen the paper's conclusions. Empirical evaluation could also provide insights into the computational efficiency and generalization performance of attention layers compared to other architectures. - Providing concrete examples of how the theoretical findings can be applied to practical deep learning problems, such as natural language processing or computer vision tasks, would enhance the paper's relevance and impact. - While the paper is generally well-written, the mathematical formulations and proofs can be complex and challenging to follow for readers without a strong background in the subject area. Simplifying and clarifying the presentation of the mathematical concepts and providing more intuitive explanations or examples could improve the accessibility of the paper for a wider audience.

Questions

Please see above comments.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Not applicable.

Summary

The paper presents the representational strength and some limitations of the transformer architecture. 1. Strength: separation between a unit of self-attention and a one-hidden layer neural or a recurrent neural network. The authors present a task where the complexity of the latter networks scale with N (number of tokens) and the self-attention does not. 2. Limitation: the task Match2 can be computed with a self-attention unit that scales with the input dimension d, yet, a modification of the task, Match3, cannot be computed with a single transformer layer. Match3 can be computed with a standard and modified transformer model. The first makes assumptions over the input the second model modifies the self-attention module.

Strengths

The paper is very well written. I could easily understand and follow all the definitions and the Theorems presented in the paper's main text.

Weaknesses

The weakness of this paper lies in its relevance to the understanding of transformer networks. The paper presents problems qSA, Match2, and Match3, whose relevance to understanding neural networks in practice is unclear. This is even stated in the paper: "Future work by linguists, theoretical computer scientists, and empirical NLP practitioners could assess how foundational our primitives are and study whether there are any practical triple-wise problems that transformer models fail to solve." I think that when studying theoretical aspects of neural networks, it is the responsibility of the authors to motivate their theoretical results and why their assumptions or framework are relevant. Otherwise, such theoretical content belongs in a mathematical venue. Minor comment: When reading Section 1.1 for the first time, I could not follow the authors' intentions/message. Only after carefully reading the rest of the text and definitions could I understand it. As written now, I think it does not convey information properly for someone just interested in having a quick general idea of the results.

Questions

I would be happy to change my mind about the paper since the paper is written technically very well. Better than most theoretical papers I encounter! Can the authors at least give some intuitive explanations why they think the tasks presented in the paper are relevant to NLP or any other ML task? Maybe a small experimental study on a small transformer network and show that the functions qSA, Match2, and Match3 somewhat resemble the functions the transformer networks actually compute? More so, through the years, I haven't encountered a single theory paper about the representational power of neural networks that actually sheds any light on understanding neural networks better in the practical sense of explaining their performance (other than the original universal approximation paper). For example, one can study the VC dimension of different architectures, but this does not bring us any step closer to understanding neural networks in practice. In its current form, I think the paper is suited to a pure theoretical venue such as a math journal or a theoretical CS conference. To make it more suitable for an ML venue, a reasonable amount of effort is required to motivate theoretical setup and questions. In that case, it's likely that the scope of the paper would not fit a conference paper but in a journal.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

The authors adequately addressed the limitations of their work.

Summary

This paper focuses on the representational capabilities of attention layers in transformer models and showcases both the strengths and limitations. On one hand, the paper proves that attention layers excel at the presented sparse averaging task compared to RNNs and FNNs. On the negative side, they have complexity scaling linearly in the input size for the triple detection task. The paper theoretically showcases the strengths and limitations of the expressivity of attention layers, especially the role of embedding dimension of the attention layer.

Strengths

To my knowledge, the presented theoretical results are novel in the study of transformers and their representational capabilities. However, this work is out of my expertise and I cannot go into depth about the significance of the work. I do appreciate the authors in providing some empirical evidence about the theoretical findings of the work.

Weaknesses

As said previously, this is not within my area of expertise. I am however interested in how relevant/connected are the proposed tasks (e.g. sparse averaging and triple detection) to empirical studies such as language or visual data modeling. I think the work would be improved if more insights could be provided as to how the theoretical results can be connected to real-world practices.

Questions

My questions and suggestions are listed above.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

This is a theory paper and the authors provided open directions for future work.

Summary

This paper mainly investigates the inductive biases of attention-based models. They propose three computational tasks that show the limitations of Transformers, namely, sparse averaging, pair matching, and triples-matching. Specifically, they analyze the representational power of embedding dimensions and show that the sparse averaging task scales more favorably in the input size as opposed to the other two tasks. Various proofs are provided to support the investigations and conclusions.

Strengths

* Interesting and relevant topic on interpreting the Transformer computations and learning progress. * Good connections with relevant prior works in setting the backgrounds for inspiring the tasks and their practical implications proposed

Weaknesses

* Initially the notation is a bit confusing, especially in section 1.1 that details the contributions. Variables $y$ and $z$ should be more clearly defined and explained when mentioning results of the theoretical analysis. * The intro can maybe be reworked to slowly work in the details and notation of the method instead of initially presenting the mechanisms that the different tasks enable

Questions

* It seems somewhat obvious that the representational capacity of performant Transformeres is related to the embedding space and operations for comparison performed on thus. Have the authors experimented with different contexts aside from the embedding space?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

3 good

Limitations

Yes.

Summary

The authors study the representational power of transformers. They quantify how the transformers are superior to other neural network architectures, as well as the limitation of the transformer architecture. They focus on the $q$-sparse averaging (qSA) task which amounts to averaging $d$-dimensional input vectors over subsets of size $q$ over a set of size $N$. They show by an explicit construction a unit of self-attention with $m \geq q$ dimensional embedding can approximate qSA. Using tools from communication complexity between two parties, they show fully connected networks require $\Omega(Nd)$ hidden layers, and recurrent neural networks require $\Omega(N)$ bits of information. They further show that standard transformers can approximate functions that intrinsically depends on input pairs, while failing to approximate functions that depends on triplets instead. Finally, they propose a variant of transformers that can approximate the triplet-functions.

Strengths

- The authors leverage the communication complexity to show that the self attention layers add more representational capacity as compared to fully connected and recurrent neural networks. - They use Match2 and Match3 problems to show rigorously that 2nd-order functions represent the threshold of efficient approximability for transformers. - The variants of Match3 problems hint at transformers leveraging some local structures present in the data to go beyond pair matching. This reconciles the Match3 impossibility result with the much presumably higher order successes of transformer models. - They additionally show higher order transformers can solve the higher order function approximations.

Weaknesses

- The fixed precision (Theorem 2) result still uses precision that needs to grow with the data size and approximation parameters. Although it is a good first step, it leaves open the approximability with constant precision (which is used in most practical cases). - The ``third-order tensor self-attention" is an important claim in the paper, but it is fully omitted in the main paper. It will be good to at least introduce the basic ideas in the main paper.

Questions

- Given a fixed constant precision $p$ what is the bottleneck in creating the transformers that can approximate q-SA? What if $z_i$s are themselves restricted to some $O(p)$ precision? - Is the use of communication complexity in the approximability of Transformers (and broader Neural networks) novel in this work?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

It is hard to foresee any potential negative societal impact of this theoretical work.

Response to Rebuttal

I thank the authors for their helpful comments. The lowering of the precision required for their bounds is welcome. The argument sounds reasonable (although not fully verified). Overall my concerns are addressed. These concerns did not influence my evaluation much. I will maintain my score.