Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformer

• URL: http://arxiv.org/abs/2409.09239v3
• Date: Fri, 20 Sep 2024 21:12:25 GMT
• Title: Autoregressive + Chain of Thought = Recurrent: Recurrence's Role in Language Models' Computability and a Revisit of Recurrent Transformer
• Authors: Xiang Zhang, Muhammad Abdul-Mageed, Laks V. S. Lakshmanan,
• Abstract summary: We investigate the influence of recurrent structures in neural models on their reasoning abilities and computability. We shed light on how the CoT approach can mimic recurrent computation and act as a bridge between autoregression and recurrence.
• Score: 29.970200877158764
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Transformer architecture excels in a variety of language modeling tasks, outperforming traditional neural architectures such as RNN and LSTM. This is partially due to its elimination of recurrent connections, which allows for parallel training and a smoother flow of gradients. However, this move away from recurrent structures places the Transformer model at the lower end of Chomsky's computational hierarchy, imposing limitations on its computational abilities. Consequently, even advanced Transformer-based models face considerable difficulties in tasks like counting, string reversal, and multiplication. These tasks, though seemingly elementary, require a level of computational complexity that exceeds the capabilities of the Transformer architecture. Concurrently, the emergence of ``Chain of Thought" (CoT) prompting has enabled Transformer-based language models to tackle tasks that were previously impossible or poorly executed. In this work, we thoroughly investigate the influence of recurrent structures in neural models on their reasoning abilities and computability, contrasting the role autoregression plays in the neural models' computational power. We then shed light on how the CoT approach can mimic recurrent computation and act as a bridge between autoregression and recurrence in the context of language models. It is this approximated recurrence that notably improves the model's performance and computational capacity. Moreover, we revisit recent recurrent-based Transformer model designs, focusing on their computational abilities through our proposed concept of ``recurrence-completeness" and identify key theoretical limitations in models like Linear Transformer and RWKV. Through this, we aim to provide insight into the neural model architectures and prompt better model design.

Related papers

• Retentive Neural Quantum States: Efficient Ansätze for Ab Initio Quantum Chemistry [10.423935999935315]
  We explore the use of the retentive network (RetNet) as an ansatz for solving electronic ground state problems in quantum chemistry. We show that RetNet overcomes this time complexity bottleneck by processing data in parallel during training, and recurrently during inference.
  arXiv  Detail & Related papers  (2024-11-06T13:24:34Z)
• Does Transformer Interpretability Transfer to RNNs? [0.6437284704257459]
  Recent advances in recurrent neural network architectures have enabled RNNs to match or exceed the performance of equal-size transformers. We show that it is possible to improve some of these techniques by taking advantage of RNNs' compressed state.
  arXiv  Detail & Related papers  (2024-04-09T02:59:17Z)
• Uncovering mesa-optimization algorithms in Transformers [61.06055590704677]
  Some autoregressive models can learn as an input sequence is processed, without undergoing any parameter changes, and without being explicitly trained to do so. We show that standard next-token prediction error minimization gives rise to a subsidiary learning algorithm that adjusts the model as new inputs are revealed. Our findings explain in-context learning as a product of autoregressive loss minimization and inform the design of new optimization-based Transformer layers.
  arXiv  Detail & Related papers  (2023-09-11T22:42:50Z)
• Composable Function-preserving Expansions for Transformer Architectures [2.579908688646812]
  Training state-of-the-art neural networks requires a high cost in terms of compute and time. We propose six composable transformations to incrementally increase the size of transformer-based neural networks.
  arXiv  Detail & Related papers  (2023-08-11T12:27:22Z)
• 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)
• 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)
• A Recursively Recurrent Neural Network (R2N2) Architecture for Learning Iterative Algorithms [64.3064050603721]
  We generalize Runge-Kutta neural network to a recurrent neural network (R2N2) superstructure for the design of customized iterative algorithms. We demonstrate that regular training of the weight parameters inside the proposed superstructure on input/output data of various computational problem classes yields similar iterations to Krylov solvers for linear equation systems, Newton-Krylov solvers for nonlinear equation systems, and Runge-Kutta solvers for ordinary differential equations.
  arXiv  Detail & Related papers  (2022-11-22T16:30:33Z)
• Decision Transformer: Reinforcement Learning via Sequence Modeling [102.86873656751489]
  We present a framework that abstracts Reinforcement Learning (RL) as a sequence modeling problem. We present Decision Transformer, an architecture that casts the problem of RL as conditional sequence modeling. Despite its simplicity, Decision Transformer matches or exceeds the performance of state-of-the-art offline RL baselines on Atari, OpenAI Gym, and Key-to-Door tasks.
  arXiv  Detail & Related papers  (2021-06-02T17:53:39Z)
• Enriching Non-Autoregressive Transformer with Syntactic and SemanticStructures for Neural Machine Translation [54.864148836486166]
  We propose to incorporate the explicit syntactic and semantic structures of languages into a non-autoregressive Transformer. Our model achieves a significantly faster speed, as well as keeps the translation quality when compared with several state-of-the-art non-autoregressive models.
  arXiv  Detail & Related papers  (2021-01-22T04:12:17Z)

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.