Separations in the Representational Capabilities of Transformers and Recurrent Architectures

• URL: http://arxiv.org/abs/2406.09347v1
• Date: Thu, 13 Jun 2024 17:31:30 GMT
• Title: Separations in the Representational Capabilities of Transformers and Recurrent Architectures
• Authors: Satwik Bhattamishra, Michael Hahn, Phil Blunsom, Varun Kanade,
• Abstract summary: 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.
• Score: 27.783705012503237
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Transformer architectures have been widely adopted in foundation models. Due to their high inference costs, there is renewed interest in exploring the potential of efficient recurrent architectures (RNNs). In this paper, we analyze the differences in the representational capabilities of Transformers and RNNs across several tasks of practical relevance, including index lookup, nearest neighbor, recognizing bounded Dyck languages, and string equality. For the tasks considered, our results show separations based on the size of the model required for different architectures. For example, we show that a one-layer Transformer of logarithmic width can perform index lookup, whereas an RNN requires a hidden state of linear size. Conversely, while constant-size RNNs can recognize bounded Dyck languages, we show that one-layer Transformers require a linear size for this task. Furthermore, we show that two-layer Transformers of logarithmic size can perform decision tasks such as string equality or disjointness, whereas both one-layer Transformers and recurrent models require linear size for these tasks. We also show that a log-size two-layer Transformer can implement the nearest neighbor algorithm in its forward pass; on the other hand recurrent models require linear size. Our constructions are based on the existence of $N$ nearly orthogonal vectors in $O(\log N)$ dimensional space and our lower bounds are based on reductions from communication complexity problems. We supplement our theoretical results with experiments that highlight the differences in the performance of these architectures on practical-size sequences.

Related papers

• Transformers are Efficient Compilers, Provably [11.459397066286822]
  Transformer-based large language models (LLMs) have demonstrated surprisingly robust performance across a wide range of language-related tasks. In this paper, we take the first steps towards a formal investigation of using transformers as compilers from an expressive power perspective. We introduce a representative programming language, Mini-Husky, which encapsulates key features of modern C-like languages.
  arXiv  Detail & Related papers  (2024-10-07T20:31:13Z)
• Attention as an RNN [66.5420926480473]
  We show that attention can be viewed as a special Recurrent Neural Network (RNN) with the ability to compute its textitmany-to-one RNN output efficiently. We introduce a new efficient method of computing attention's textitmany-to-many RNN output based on the parallel prefix scan algorithm. We show Aarens achieve comparable performance to Transformers on $38$ datasets spread across four popular sequential problem settings.
  arXiv  Detail & Related papers  (2024-05-22T19:45:01Z)
• Perceiving Longer Sequences With Bi-Directional Cross-Attention Transformers [13.480259378415505]
  BiXT scales linearly with input size in terms of computational cost and memory consumption. BiXT is inspired by the Perceiver architectures but replaces iterative attention with an efficient bi-directional cross-attention module. By combining efficiency with the generality and performance of a full Transformer architecture, BiXT can process longer sequences.
  arXiv  Detail & Related papers  (2024-02-19T13:38:15Z)
• Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection [88.23337313766353]
  This work first provides a comprehensive statistical theory for transformers to perform ICL. We show that transformers can implement a broad class of standard machine learning algorithms in context. A emphsingle transformer can adaptively select different base ICL algorithms.
  arXiv  Detail & Related papers  (2023-06-07T17:59:31Z)
• Representational Strengths and Limitations of Transformers [33.659870765923884]
  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.
  arXiv  Detail & Related papers  (2023-06-05T14:05:04Z)
• RWKV: Reinventing RNNs for the Transformer Era [54.716108899349614]
  We propose a novel model architecture that combines the efficient parallelizable training of transformers with the efficient inference of RNNs. We scale our models as large as 14 billion parameters, by far the largest dense RNN ever trained, and find RWKV performs on par with similarly sized Transformers.
  arXiv  Detail & Related papers  (2023-05-22T13:57:41Z)
• Rich CNN-Transformer Feature Aggregation Networks for Super-Resolution [50.10987776141901]
  Recent vision transformers along with self-attention have achieved promising results on various computer vision tasks. We introduce an effective hybrid architecture for super-resolution (SR) tasks, which leverages local features from CNNs and long-range dependencies captured by transformers. Our proposed method achieves state-of-the-art SR results on numerous benchmark datasets.
  arXiv  Detail & Related papers  (2022-03-15T06:52:25Z)
• PnP-DETR: Towards Efficient Visual Analysis with Transformers [146.55679348493587]
  Recently, DETR pioneered the solution vision tasks with transformers, it directly translates the image feature map into the object result. Recent transformer-based image recognition model andTT show consistent efficiency gain.
  arXiv  Detail & Related papers  (2021-09-15T01:10:30Z)
• SOTR: Segmenting Objects with Transformers [0.0]
  We present a novel, flexible, and effective transformer-based model for high-quality instance segmentation. The proposed method, Segmenting Objects with TRansformers (SOTR), simplifies the segmentation pipeline. Our SOTR performs well on the MS COCO dataset and surpasses state-of-the-art instance segmentation approaches.
  arXiv  Detail & Related papers  (2021-08-15T14:10:11Z)
• Addressing Some Limitations of Transformers with Feedback Memory [51.94640029417114]
  Transformers have been successfully applied to sequential, auto-regressive tasks despite being feedforward networks. We propose the Feedback Transformer architecture that exposes all previous representations to all future representations. We demonstrate on a variety of benchmarks in language modeling, machine translation, and reinforcement learning that the increased representation capacity can create small, shallow models with much stronger performance than comparable Transformers.
  arXiv  Detail & Related papers  (2020-02-21T16:37:57Z)

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.