Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count

• URL: http://arxiv.org/abs/2410.15787v1
• Date: Mon, 21 Oct 2024 08:49:51 GMT
• Title: Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count
• Authors: Hanseul Cho, Jaeyoung Cha, Srinadh Bhojanapalli, Chulhee Yun,
• Abstract summary: Transformers often struggle with length generalization, meaning they fail to generalize to sequences longer than those encountered during training. In this work, we achieve approximately 2-3x length generalization on both tasks, which is the first such achievement in arithmetic Transformers.
• Score: 19.148785141454642
• License:
• Abstract: Transformers often struggle with length generalization, meaning they fail to generalize to sequences longer than those encountered during training. While arithmetic tasks are commonly used to study length generalization, certain tasks are considered notoriously difficult, e.g., multi-operand addition (requiring generalization over both the number of operands and their lengths) and multiplication (requiring generalization over both operand lengths). In this work, we achieve approximately 2-3x length generalization on both tasks, which is the first such achievement in arithmetic Transformers. We design task-specific scratchpads enabling the model to focus on a fixed number of tokens per each next-token prediction step, and apply multi-level versions of Position Coupling (Cho et al., 2024; McLeish et al., 2024) to let Transformers know the right position to attend to. On the theory side, we prove that a 1-layer Transformer using our method can solve multi-operand addition, up to operand length and operand count that are exponential in embedding dimension.

Related papers

• A Formal Framework for Understanding Length Generalization in Transformers [14.15513446489798]
  We introduce a rigorous theoretical framework to analyze length generalization in causal transformers. We experimentally validate the theory as a predictor of success and failure of length generalization across a range of algorithmic and formal language tasks.
  arXiv  Detail & Related papers  (2024-10-03T01:52:01Z)
• Looped Transformers for Length Generalization [41.99378201613648]
  We show that looped Transformers with an adaptive number of steps significantly improve length generalization. We train looped Transformers using our proposed learning algorithm and observe that they learn highly length-generalizable solutions for various tasks.
  arXiv  Detail & Related papers  (2024-09-24T01:21:17Z)
• Length Generalization of Causal Transformers without Position Encoding [59.802708262402824]
  Generalizing to longer sentences is important for recent Transformer-based language models. We study the length generalization property of Transformers without position encodings. We find that although NoPE can extend to sequences longer than the commonly used explicit position encodings, it still has a limited context length.
  arXiv  Detail & Related papers  (2024-04-18T14:38:32Z)
• Transformers Can Achieve Length Generalization But Not Robustly [76.06308648699357]
  We show that the success of length generalization is intricately linked to the data format and the type of position encoding. We show for the first time that standard Transformers can extrapolate to a sequence length that is 2.5x the input length.
  arXiv  Detail & Related papers  (2024-02-14T18:18:29Z)
• What Algorithms can Transformers Learn? A Study in Length Generalization [23.970598914609916]
  We study the scope of Transformers' abilities in the specific setting of length generalization on algorithmic tasks. Specifically, we leverage RASP -- a programming language designed for the computational model of a Transformer. Our work provides a novel perspective on the mechanisms of compositional generalization and the algorithmic capabilities of Transformers.
  arXiv  Detail & Related papers  (2023-10-24T17:43:29Z)
• Improving Length-Generalization in Transformers via Task Hinting [42.95479331339189]
  In particular, the performance of a transformer model trained on tasks up to a certain length drops sharply when applied to longer instances of the same problem. This work proposes an approach based on task hinting towards addressing length generalization.
  arXiv  Detail & Related papers  (2023-10-01T16:57:40Z)
• LongNet: Scaling Transformers to 1,000,000,000 Tokens [146.4077038371075]
  LongNet is a Transformer variant that can scale sequence length to more than 1 billion tokens. Our work opens up new possibilities for modeling very long sequences, e.g., treating a whole corpus or even the entire Internet as a sequence.
  arXiv  Detail & Related papers  (2023-07-05T17:59:38Z)
• Compositional Generalization and Decomposition in Neural Program Synthesis [59.356261137313275]
  In this paper, we focus on measuring the ability of learned program synthesizers to compositionally generalize. We first characterize several different axes along which program synthesis methods would be desired to generalize. We introduce a benchmark suite of tasks to assess these abilities based on two popular existing datasets.
  arXiv  Detail & Related papers  (2022-04-07T22:16:05Z)
• Length-Adaptive Transformer: Train Once with Length Drop, Use Anytime with Search [84.94597821711808]
  We extend PoWER-BERT (Goyal et al., 2020) and propose Length-Adaptive Transformer that can be used for various inference scenarios after one-shot training. We conduct a multi-objective evolutionary search to find a length configuration that maximizes the accuracy and minimizes the efficiency metric under any given computational budget. We empirically verify the utility of the proposed approach by demonstrating the superior accuracy-efficiency trade-off under various setups.
  arXiv  Detail & Related papers  (2020-10-14T12:28:08Z)

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.