Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers

• URL: http://arxiv.org/abs/2404.04393v1
• Date: Fri, 5 Apr 2024 20:36:30 GMT
• Title: Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
• Authors: Andy Yang, David Chiang,
• Abstract summary: We introduce the temporal counting logic $textbfK_textt$[#] alongside the RASP variant $textbfC-RASP$. We show they are equivalent to each other, and that together they are the best-known lower bound on the formal expressivity of future-masked soft attention transformers.
• Score: 8.908747084128397
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Deriving formal bounds on the expressivity of transformers, as well as studying transformers that are constructed to implement known algorithms, are both effective methods for better understanding the computational power of transformers. Towards both ends, we introduce the temporal counting logic $\textbf{K}_\text{t}$[#] alongside the RASP variant $\textbf{C-RASP}$. We show they are equivalent to each other, and that together they are the best-known lower bound on the formal expressivity of future-masked soft attention transformers with unbounded input size. We prove this by showing all $\textbf{K}_\text{t}$[#] formulas can be compiled into these transformers. As a case study, we demonstrate on paper how to use $\textbf{C-RASP}$ to construct simple transformer language models that, using greedy decoding, can only generate sentences that have given properties formally specified in $\textbf{K}_\text{t}$[#].

Related papers

• 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)
• Transformers learn variable-order Markov chains in-context [10.210508887119643]
  We study the ICL of variable-order Markov chains (VOMC) by viewing language modeling as a form of data compression. We show that two-layer transformers can match the ICL performance of transformers, and more interestingly, some of them can perform even better despite the much-reduced parameter sets.
  arXiv  Detail & Related papers  (2024-10-07T21:04:53Z)
• Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
  We study transformers' ability to learn random $n$-gram LMs of two kinds. We find that classic estimation techniques for $n$-gram LMs such as add-$lambda$ smoothing outperform transformers.
  arXiv  Detail & Related papers  (2024-10-03T21:21:02Z)
• Transformers Can Represent $n$-gram Language Models [56.06361029539347]
  We focus on the relationship between transformer LMs and $n$-gram LMs, a simple and historically relevant class of language models. We show that transformer LMs using the hard or sparse attention mechanisms can exactly represent any $n$-gram LM.
  arXiv  Detail & Related papers  (2024-04-23T12:51:37Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  Chain of thought (CoT) is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness.
  arXiv  Detail & Related papers  (2024-02-20T10:11:03Z)
• The Expressive Power of Transformers with Chain of Thought [29.839710738657203]
  In practice, transformers can be improved by allowing them to use a "chain of thought" or "scratchpad" We show that the answer is yes, but the amount of increase depends crucially on the amount of intermediate generation. Our results also imply that linear steps keep transformer decoders within context-sensitive languages.
  arXiv  Detail & Related papers  (2023-10-11T22:35:18Z)
• Learning Transformer Programs [78.9509560355733]
  We introduce a procedure for training Transformers that are mechanistically interpretable by design. Instead of compiling human-written programs into Transformers, we design a modified Transformer that can be trained using gradient-based optimization. The Transformer Programs can automatically find reasonable solutions, performing on par with standard Transformers of comparable size.
  arXiv  Detail & Related papers  (2023-06-01T20:27:01Z)
• 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)
• 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.