Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages

• URL: http://arxiv.org/abs/2310.13897v4
• Date: Wed, 30 Oct 2024 00:44:17 GMT
• Title: Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages
• Authors: Andy Yang, David Chiang, Dana Angluin,
• Abstract summary: We study exact characterizations of transformers with hard attention and attention masking. With strict masking (each position cannot attend to itself) and without position embeddings, these transformers are expressively equivalent to linear temporal logic.
• Score: 7.938342455750221
• License:
• Abstract: The expressive power of transformers over inputs of unbounded size can be studied through their ability to recognize classes of formal languages. In this paper, we establish exact characterizations of transformers with hard attention (in which all attention is focused on exactly one position) and attention masking (in which each position only attends to positions on one side). With strict masking (each position cannot attend to itself) and without position embeddings, these transformers are expressively equivalent to linear temporal logic (LTL), which defines exactly the star-free languages. A key technique is the use of Boolean RASP as a convenient intermediate language between transformers and LTL. We then take numerous results known for LTL and apply them to transformers, showing how position embeddings, strict masking, and depth all increase expressive power.

Related papers

• Theoretical Analysis of Hierarchical Language Recognition and Generation by Transformers without Positional Encoding [32.01426831450348]
  We show that causal masking and a starting token enable Transformers to compute positional information and depth within hierarchical structures. We demonstrate that Transformers without positional encoding can generate hierarchical languages.
  arXiv  Detail & Related papers  (2024-10-16T09:56:01Z)
• Extracting Finite State Machines from Transformers [0.3069335774032178]
  We investigate the trainability of transformers trained on regular languages from a mechanistic interpretability perspective. We empirically find tighter lower bounds on the trainability of transformers, when a finite number of symbols determine the state. Our mechanistic insight allows us to characterise the regular languages a one-layer transformer can learn with good length generalisation.
  arXiv  Detail & Related papers  (2024-10-08T13:43:50Z)
• A Transformer with Stack Attention [84.18399019794036]
  We propose augmenting transformer-based language models with a differentiable, stack-based attention mechanism. Our stack-based attention mechanism can be incorporated into any transformer-based language model and adds a level of interpretability to the model. We show that the addition of our stack-based attention mechanism enables the transformer to model some, but not all, deterministic context-free languages.
  arXiv  Detail & Related papers  (2024-05-07T17:47:57Z)
• Towards Lightweight Transformer via Group-wise Transformation for Vision-and-Language Tasks [126.33843752332139]
  We introduce Group-wise Transformation towards a universal yet lightweight Transformer for vision-and-language tasks, termed as LW-Transformer. We apply LW-Transformer to a set of Transformer-based networks, and quantitatively measure them on three vision-and-language tasks and six benchmark datasets. Experimental results show that while saving a large number of parameters and computations, LW-Transformer achieves very competitive performance against the original Transformer networks for vision-and-language tasks.
  arXiv  Detail & Related papers  (2022-04-16T11:30:26Z)
• On the Power of Saturated Transformers: A View from Circuit Complexity [87.20342701232869]
  We show that saturated transformers transcend the limitations of hard-attention transformers. The jump from hard to saturated attention can be understood as increasing the transformer's effective circuit depth by a factor of $O(log n)$.
  arXiv  Detail & Related papers  (2021-06-30T17:09:47Z)
• Thinking Like Transformers [64.96770952820691]
  We propose a computational model for the transformer-encoder in the form of a programming language. We show how RASP can be used to program solutions to tasks that could conceivably be learned by a Transformer. We provide RASP programs for histograms, sorting, and Dyck-languages.
  arXiv  Detail & Related papers  (2021-06-13T13:04:46Z)
• Scalable Transformers for Neural Machine Translation [86.4530299266897]
  Transformer has been widely adopted in Neural Machine Translation (NMT) because of its large capacity and parallel training of sequence generation. We propose a novel scalable Transformers, which naturally contains sub-Transformers of different scales and have shared parameters. A three-stage training scheme is proposed to tackle the difficulty of training the scalable Transformers.
  arXiv  Detail & Related papers  (2021-06-04T04:04:10Z)
• Transformer visualization via dictionary learning: contextualized embedding as a linear superposition of transformer factors [15.348047288817478]
  We propose to use dictionary learning to open up "black boxes" as linear superpositions of transformer factors. Through visualization, we demonstrate the hierarchical semantic structures captured by the transformer factors. We hope this visualization tool can bring further knowledge and a better understanding of how transformer networks work.
  arXiv  Detail & Related papers  (2021-03-29T20:51:33Z)
• Position Information in Transformers: An Overview [6.284464997330884]
  This paper provides an overview of common methods to incorporate position information into Transformer models. The objectives of this survey are to showcase that position information in Transformer is a vibrant and extensive research area.
  arXiv  Detail & Related papers  (2021-02-22T15:03:23Z)
• On the Ability and Limitations of Transformers to Recognize Formal Languages [9.12267978757844]
  We provide a construction of Transformers for a subclass of counter languages. We find that Transformers do well on this subclass, and their learned mechanism strongly correlates with our construction. Perhaps surprisingly, in contrast to LSTMs, Transformers do well only on a subset of regular languages with degrading performance.
  arXiv  Detail & Related papers  (2020-09-23T17:21:33Z)
• Segatron: Segment-Aware Transformer for Language Modeling and Understanding [79.84562707201323]
  We propose a segment-aware Transformer (Segatron) to generate better contextual representations from sequential tokens. We first introduce the segment-aware mechanism to Transformer-XL, which is a popular Transformer-based language model. We find that our method can further improve the Transformer-XL base model and large model, achieving 17.1 perplexity on the WikiText-103 dataset.
  arXiv  Detail & Related papers  (2020-04-30T17:38:27Z)

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.