Representational Strengths and Limitations of Transformers

• URL: http://arxiv.org/abs/2306.02896v2
• Date: Thu, 16 Nov 2023 14:48:16 GMT
• Title: Representational Strengths and Limitations of Transformers
• Authors: Clayton Sanford, Daniel Hsu, Matus Telgarsky
• Abstract summary: We establish both positive and negative results on the representation power of attention layers. We show the necessity and role of a large embedding dimension in a transformer. We also present natural variants that can be efficiently solved by attention layers.
• Score: 33.659870765923884
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Attention layers, as commonly used in transformers, form the backbone of modern deep learning, yet there is no mathematical description of their benefits and deficiencies as compared with other architectures. In this work we establish both positive and negative results on the representation power of attention layers, with a focus on intrinsic complexity parameters such as width, depth, and embedding dimension. On the positive side, we present a sparse averaging task, where recurrent networks and feedforward networks all have complexity scaling polynomially in the input size, whereas transformers scale merely logarithmically in the input size; furthermore, we use the same construction to show the necessity and role of a large embedding dimension in a transformer. On the negative side, we present a triple detection task, where attention layers in turn have complexity scaling linearly in the input size; as this scenario seems rare in practice, we also present natural variants that can be efficiently solved by attention layers. The proof techniques emphasize the value of communication complexity in the analysis of transformers and related models, and the role of sparse averaging as a prototypical attention task, which even finds use in the analysis of triple detection.

Related papers

• DAPE V2: Process Attention Score as Feature Map for Length Extrapolation [63.87956583202729]
  We conceptualize attention as a feature map and apply the convolution operator to mimic the processing methods in computer vision. The novel insight, which can be adapted to various attention-related models, reveals that the current Transformer architecture has the potential for further evolution.
  arXiv  Detail & Related papers  (2024-10-07T07:21:49Z)
• Skip-Layer Attention: Bridging Abstract and Detailed Dependencies in Transformers [56.264673865476986]
  This paper introduces Skip-Layer Attention (SLA) to enhance Transformer models. SLA improves the model's ability to capture dependencies between high-level abstract features and low-level details. Our implementation extends the Transformer's functionality by enabling queries in a given layer to interact with keys and values from both the current layer and one preceding layer.
  arXiv  Detail & Related papers  (2024-06-17T07:24:38Z)
• Separations in the Representational Capabilities of Transformers and Recurrent Architectures [27.783705012503237]
  We analyze the differences in the representational capabilities of Transformers and RNNs across several tasks of practical relevance. We show that a one-layer Transformer of logarithmic width can perform index lookup, whereas an RNN requires a hidden state of linear size. We also show that a log-size two-layer Transformer can implement the nearest neighbor algorithm in its forward pass.
  arXiv  Detail & Related papers  (2024-06-13T17:31:30Z)
• CT-MVSNet: Efficient Multi-View Stereo with Cross-scale Transformer [8.962657021133925]
  Cross-scale transformer (CT) processes feature representations at different stages without additional computation. We introduce an adaptive matching-aware transformer (AMT) that employs different interactive attention combinations at multiple scales. We also present a dual-feature guided aggregation (DFGA) that embeds the coarse global semantic information into the finer cost volume construction.
  arXiv  Detail & Related papers  (2023-12-14T01:33:18Z)
• Adaptivity and Modularity for Efficient Generalization Over Task Complexity [42.748898521364914]
  We investigate how the use of a mechanism for adaptive and modular computation in transformers facilitates the learning of tasks that demand generalization over the number of sequential steps. We propose a transformer-based architecture called Hyper-UT, which combines dynamic function generation from hyper networks with adaptive depth from Universal Transformers.
  arXiv  Detail & Related papers  (2023-10-13T05:29:09Z)
• Points to Patches: Enabling the Use of Self-Attention for 3D Shape Recognition [19.89482062012177]
  We propose a two-stage Point Transformer-in-Transformer (Point-TnT) approach which combines local and global attention mechanisms. Experiments on shape classification show that such an approach provides more useful features for downstream tasks than the baseline Transformer. We also extend our method to feature matching for scene reconstruction, showing that it can be used in conjunction with existing scene reconstruction pipelines.
  arXiv  Detail & Related papers  (2022-04-08T09:31:24Z)
• P2T: Pyramid Pooling Transformer for Scene Understanding [62.41912463252468]
  We build a downstream-task-oriented transformer network, dubbed Pyramid Pooling Transformer (P2T) Plugged with our pooling-based MHSA, we build a downstream-task-oriented transformer network, dubbed Pyramid Pooling Transformer (P2T)
  arXiv  Detail & Related papers  (2021-06-22T18:28:52Z)
• Less is More: Pay Less Attention in Vision Transformers [61.05787583247392]
  Less attention vIsion Transformer builds upon the fact that convolutions, fully-connected layers, and self-attentions have almost equivalent mathematical expressions for processing image patch sequences. The proposed LIT achieves promising performance on image recognition tasks, including image classification, object detection and instance segmentation.
  arXiv  Detail & Related papers  (2021-05-29T05:26:07Z)
• Transformers Solve the Limited Receptive Field for Monocular Depth Prediction [82.90445525977904]
  We propose TransDepth, an architecture which benefits from both convolutional neural networks and transformers. This is the first paper which applies transformers into pixel-wise prediction problems involving continuous labels.
  arXiv  Detail & Related papers  (2021-03-22T18:00:13Z)
• Effects of Parameter Norm Growth During Transformer Training: Inductive Bias from Gradient Descent [44.44543743806831]
  We study the tendency for transformer parameters to grow in magnitude while saturated between these norms during training. As the parameters grow in magnitude, we prove that the network approximates a discretized network with saturated activation functions. Our results suggest saturation is a new characterization of an inductive bias implicit in GD of particular interest for NLP.
  arXiv  Detail & Related papers  (2020-10-19T17:40:38Z)
• Applying the Transformer to Character-level Transduction [68.91664610425114]
  The transformer has been shown to outperform recurrent neural network-based sequence-to-sequence models in various word-level NLP tasks. We show that with a large enough batch size, the transformer does indeed outperform recurrent models for character-level tasks.
  arXiv  Detail & Related papers  (2020-05-20T17:25:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.