Exposing Attention Glitches with Flip-Flop Language Modeling
Authors: Bingbin Liu
Jordan T. Ash
Surbhi Goel
Akshay Krishnamurthy
Cyril Zhang
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Transformers
language models
hallucinations
long-range dependencies
generalization
extrapolation
out-of-distribution
TL;DR: Transformers fail to robustly keep track of a single bit of memory. The glitches are surprisingly subtle and persistent. We hypothesize that this accounts for some "closed-domain hallucinations".

Abstract: Why do large language models sometimes output factual inaccuracies and exhibit erroneous reasoning? The brittleness of these models, particularly when executing long chains of reasoning, currently seems to be an inevitable price to pay for their advanced capabilities of coherently synthesizing knowledge, pragmatics, and abstract thought. Towards making sense of this fundamentally unsolved problem, this work identifies and analyzes the phenomenon of _attention glitches_, in which the Transformer architecture's inductive biases intermittently fail to capture robust reasoning. To isolate the issue, we introduce _flip-flop language modeling_ (FFLM), a parametric family of synthetic benchmarks designed to probe the extrapolative behavior of neural language models. This simple generative task requires a model to copy binary symbols over long-range dependencies, ignoring the tokens in between. We find that Transformer FFLMs suffer from a long tail of sporadic reasoning errors, some of which we can eliminate using various regularization techniques. Our preliminary mechanistic analyses show why the remaining errors may be very difficult to diagnose and resolve. We hypothesize that attention glitches account for (some of) the closed-domain hallucinations in natural LLMs.

Exposing Attention Glitches with Flip-Flop Language Modeling
Bingbin Liu'
Jordan T. Ash?
Surbhi Goel
Akshay Krishnamurthy Cyril Zhang?
CCarnegie Mellon University
2 Microsoff Research NYC
*University of Pennsylvania
bingbinl@cs. cmu edu, surbhigacis upenn edu, fash. jordan, akshaykr, maallzhhangmmiccoosootto
Abstract
Why do large language models sometimes output factual inaccuracies and exhibit erroneous reasoning? The brittleness of these models, particularly when executing long chains of reasoning, currently seems to be an inevitable price pay for their advanced capabilities of coherently synthesizing knowledge, pragmatics, and abstract thought. Towards making sense of this fundamentally unsolved problem, this work identifies and analyzes the phenomenon of attention glitches, in which the Transformer architecture's inductive biases intermittently fail capture robust reasoning. To isolate the issue, we introduce flip-flpp language modeling (FFLM), a parametric family of synthetic benchmarks designed to probe the extrapolative behavior of neural language models. This simple generative task requires model to copy binary symbols over long-range dependencies, ignoring the tokens in between. We find that Transformer FFLMS suffer from long tail of sporadic reasoning errors, some of which we can eliminate using various regularization techniques. Our preliminary mechanistic analyses show why the remaining errors may be very difficult to diagnose and resolve. We hypothesize that attention glitches account for (some of) the closed-domain hallucinations in natural LLMs.
Introduction
Recent advancements in scale have yielded large language models (LLMs) with extraordinary profi- ciency in nuanced reasoning with factual knowledge. Despite these achievements, LLMs are known to produce incorrect outputs, often referred to colloquially as "hallucinations" or "distractions" (Ji et al. 2023). Generally, ballucinations refer to the phenomenon that a model's 's outputs are syntactically and grammatically accurate but factually incorrect. There are various types of hallucinations, and the focus this work is the selosed-domaing " variety (Saparov and He 2022 OpenAl (202), where the model predictions contain factually incorrect or made-up information according a given context, regardless of their correctness in the real world.
Perhaps surprisingly, such hallucinations can be observed even on simple algorithmic reasoning tasks. As warmup, consider the queries shown in Figure I (and Appendix where we prompt LLMs to solve addition problems of various lengths. The responses simultaneously illustrate the following:
1. Nontrivial algorithmic generalization: In cases where the models succeed, it is unlikely that these exact numerical sequences appeared in the training data. To correctly output the first digit of the answer, the LLM must resolve long dependency chain which generally depends on every digit in the input. Somewhere within these networks' internal representations, implementations of addition algorithms have emerged.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Use:: What is 5493 235T!
User: What 84935834 23572898?
Inside the Transformer: (glitchy) learned adder
GPT-3.3: 10850
GPT-3.5: 108008732
GPT-4: 10850 /
GPT-4: 108508732
User: What is 999199919999999 61091991999900977
GPT-33: 161111991908100990 x
GPT-4: 16101199100099000
Answer: 16101199110900090
3
Figure I: Cherry-picked integer addition prompts, showing how state-of-the--an LLMs can generalize non-trivially on algorithmic sequences, but sporadic reasoning errors persist. The first digit of the correct answer depends on every imput; thus, an autoregressive model must propagate a "carry" bit across these long-range dependencies in a single pass. This (and many other algorithmic reasoning capabílities) can be implemented by Transformer model using internal flip-flops.
Sporadic errors ("hallucinationns)): These internal algorithms can be brittle and unreliable, especially when processing long inferential chains. Their failures can be subtle and unpredictable.
In this work, we consider the task of processing the flip-flp language, a minimal unit of sequential computation which consists of memory operations on single bit (see Definition T and underlies virtually all syntactic parsing and algorithmic reasoning capabilities (including implementing adders, and far more). A Slip-flop language modeling (FFLM) task is defined on sequences of write, read, and ignore instructions: write sets memory state to certain value which later retrieved by read, while ignoring any contents in between. We find that when trained to complete flip-flop sequences, the Transformer architecture exhibits a long tail reasoning errors (incorrect read retrievals), unlike previous-generation generation recurrent models such the LSTM (Hochreiter and Schmidhuber 1997). We coin the term attention glitch for this phenomenon, and hypothesize that this captures systematic failure mode of Transformer-bast -based LLMs when internally manifesting long chains of algorithmic reasoning.
Our contributions are as follows:
FFLM: minimalistic
long-range dependency benchmark. We propose flip-flpp language modeling, a parametric family of synthetic benchmarks for autoregressive sequence modeling, designed to isolate and probe reasoning errors like those demonstrated in Figure We view FFLM as a robust complement to the Long Range Arena (Tay al., (020) and some of the tests in BIG-Bench (Srivastava et al.) 2022), and recommend measuring g glitch rates as a "stress test" for architectural innovations sequence modeling
Main empirical result: attention attends glitchily. We find that while Transformer models can appear to learn flip-flop languages perfectly on held-out samples from the training distribution, they make a long tail of unpredictable reasoning errors (attention glitches). on both rong-range and short-range dependencies. We evaluate various direct and indirect mitigations, including commonly-used regularization techniques and catention-sharpeen and-play way to sparsify self-attention architectures. We find that attention sharpening reduces reasoning errors by an order of magnitude, but none of our attempts were successful in driving the number of errors to exactly 0. Mcanwhile, recurrent models work perfectly
regularizers - plug-
Preliminary mechanistic analyses. We provide some theoretical and empirical explorations which account for some of the internal mechanisms for attention glitches, and why they are so difficult eliminate completely.
1.1
Related work
The challenge of learning long-range dependencies a long-standing one the statistical modeling of sequences (Samorodnitsky et al. 2007). The Transformer architecture (Vaswani et al.) (017).
a maradigm-shfftingg sequence model. enables the scalable learning of a feedforward hicrarchy of
Moore precisely, whenever the desired algorithm needs to "store memory" (i.e. contains non-invertible state transformation); see Section 3.2
2To get started, see our data releases httpp::/huuginngfaac. http:///ww......e.ee.ee/////////
It could be the case that recurrent models may fail extremely long dependencies (Khandelwal et 2018

---

meaningful long-range dependencies. Yet, factual errors over long contexts persist in these models; this is the subject of many careful studies in deep NLP (Khandelwal et al. 2018 Tay et al. 2020
Guo et al. 2022 Ji et al. 2023).
The sporadic non-factual outputs of LLMs have been popularly called "hallucinations", especially when there is an expectation that producing a correct answer is disproportionately "easy". Popular approaches for improving robustness such errors include thain-of-thouse generation (explicitly outputting intermediate reasoning steps) (Nye et al. 202I; Wei et al. 2022b) and enforcing self- consistency (Wang et al., 2022). In the emerging taxonomy of LLM pathologies (Saparov and He. 2022, Ji et al. 2023). y. the hallucinations studied in this work are of the closed-domaix variety. under deterministic notion of factuality (namely, consistency with flip-flp transitions) which is unambiguously reflected by the training data. We provide further discussion on the connections to natural LLM hallcuinations in Section and Appendix A.4
Long-range dependency and reasoning benchmarks. Many datasets and benchmarks have been
designed to isolate qualitative issues in langauge modeling TTy et al.) 2020 Wu et al. 2021| Zhang
al. 2021 2022] Saparov and He 2022] Shi et al.) [203]] van der Poel et al., [023]] Eldan and
2023 Aside from being focused on the "smallest" and "purest" compositional unit of sequential
reasoning (see Section 3.2). FFLM is distinguished by a few factors:
"I objective: Unlike usual benchmarks, we consider any model with less than 100% accuracy exhibiting reasoning error. Aside from the motivation of completely eliminating hallucina- tions, we argue that this stringent notion of correctness is needed to avoid error amplification when flip-flops are embedded more complex networks; see Appendix [A.1 and Liu et al. (2023).
Parametric, procedurally generated, and generalizable: Our empirical study precisely quanti- fies long-tail errors via a large number of replicates over the randomness of both model initializa- tion and data generation. This methodology is easily adapted and rescaled (by adjusting T, p, and other difficulty knobs) to probe language models of any size.
We provide expanded discussion of related literature in Appendix A.2
Background and notation
Modern language models powered by seneence-to-sequeee (seq2seq) neural networks fe: RTxx + Rxx xd which transduce sequences of vectors according to internal computations determined by the inputs as well trainable parameters A. When equipped with mappings and from symbolic tokens (an "embedding layer" E [M] - Rd (here, M E N is the vocabulary size) and classification layer W Rd + ((M)). shared across positions), W ʃ
[M] + ([MM)) can represent an autoregressive generative model of joint distribution over tokens T1.7 E [M]] where the output
at the t-th position gives the estimated next-symbol probabilities Pr|a++1 = 2 The overarching challenge of statistical language modeling is to fit complex distributions such as natural language; recurrent (Elman) 1990, Hochreiter and Schmidhuber 1997 Wu et al. 2016) and self-attention-
based (Vaswani et al. (017)) architectures have shown remarkable capabilities in fitting the seq2seq functions necessary for fluent linguistic parsing and reasoning.
Recurrent inductive biases, attention, and length generalization. To correctly process uniform (i.e. ceaeddssrriptionllnnglll algorithmic computations on arbitrarily long sequences, it is natural to embed recurrences within seq2seq network, Imitating the recurrent nature of the Turing machine, one can hope for RNNs to learn representations of the desired looped computations (Sutskever et al., 2013 Graves et al. 2014 Linzen et al. 2016). However, the key innovation in the Transformer architecture a nonrrecureent self-attention module Various works have noted that Transformers and RNNs learn qualitatively different solutions, discussing potential ways to reconcile these nuanced discrepancies (Dehghani et al. 2018: Abnar al.) 2020
Liu et al. 2023).
'We define attfnattontion in Appendix C For in-depth breakdowns of the architectural components of
Transformers, see (Vaswani et al. 2017 Phuong and Hutter 2022 Edelman al. 2022
3

---

def #01 0 ignozo ignozo
transcript of events: Alice tuzas the light off. Then, Rob eats apple.
E.
Then, Rob eatx basana.
x ignoze
Then. Alice tuxas the light on.
Then. Bob eats banana.
ignore accert
Bob eats apple.
(0.1)
Q= 10, 1.
Nov. the light
== 1...0.1
== 1.r,i,0011
1
<div></div>
Usec: What is 44941 558527
</b1>
Bot:
<h2>
<div></div>
<><//p>
(a)
(b)
Figure 2: Elementary objects and examples associated with flip-flop languages. (a) the 2-state flip-flop machine (elided transitions are self-loops). (2) 4-state automaton which processes flip-flop languages (implying the existence of small RNN). (c) Simple examples of sequential prediction tasks which require processing flip-flop language.
3 Flip-flop automata and the FFLM task
3.1 Definitions
For any even number T 2 4, we define a flip-flop string as a sequence of symbols {w, i, O, 1)"². which have the semantics of instructions (write, read, ignore) and data (one bit). A valid flip-flop string consists of alternating pairs of instructions and data (e.g. "w 0 i 1 O r 0"), for which every symbol following r instruction must be equal the symbol following the most recent w; thus, "w 0 1 r 0" is not a legal flip-flop string. These sequences can be viewed as correct execution transcripts of program which can (perhaps occasionally) wri te single bit of memory. and always correctly reads its contents. All sequences are required to begin with and end with r.
There many possible choices of (probabilistic) flip-flop languages, which are distributions valid flip-flop strings. We define a canonical family of them: let (FL((Tp) p) be the distribution over length-T' flip-flop strings, parameterized by p Pe. E (((w, i)), such that:
(i) The first instruction 41 is always w, and the last instruction Tr-1 is always r.
(ii) The other instructions are drawn i.i.d. according to (Pv: Pr. Ps) with ps = Px Pr-
(iii) The nondeterministic data symbols (paired with i) are drawn i..dd and uniformly.
We are interested in whether language models can learn a flip-flop language from samples, which define as processing the read operations perfectly. Two variants of the autoregressive language modeling task can be defined on this distribution:
Generative ("noisy"") mode: Estimate the conditional next-token distribution Pr[z++1 [a1:e], for each & = 1..... for natural text in GPT-sttle training. Generative FFLMs be evaluated by checking their completions on prefix "prompts" (e.g. " x 0 1 i
1. In this mode, the sequences can be treated as drop-in replacements
[?]").
Predict only the continuations which are deterministic: correctly output ø++1 only for the prefixes Tıæ such that æ; = r. At the cost of a slight departure from vanilla language modeling, this setting isolates the long-range memory task. It is similar to the non-autoregren aoo-autoreeesssvve flip-flop monoid simulation problem discussed in Liu et al. (0023) with limited supervision.
Deterministic ("clean"") mode:
These tasks naturally embed the capability of simulating the flip-flop, a machine which memorizes a single bit (see Figure b for closely related variants) 0
It easy to that recurrent networks and
'ee observe similar behaviors across these settings (see Appendix B.2 but report results the "clean" setting in this paper. Predicting the deteememministic tokens is irrelevant the memory task hand. "A further discussion of the rationale for this specific manifestation of flip-flop sequence processing is deferred to Appendix A.3

---

2 2-layer Transformers (see Proposition 2 can both represent FFLM parsers. The question of whether they do, especially from less- bess-than--ie -heal data, turns out to be extremely subtle, and is the subject of the remainder of this paper.
3.2 Why focus on the flip-flop?
The most immediate rationale for this synthetic benchmark is that flip-flop simulation (maintaining memory in a sequence) is a direct necessity in many reasoning settings (see Figure 2 is a special (depth-1) case of Dyck language processing (Chomsky and Schützenberger 1959 Yao et al.
2021: Zhao et al. 2023), which necessary for parsing recursive grammars. It also captures certain structures in code language tasks, such as tracking semantic changes (Miceli-Barone
al. 2023)
or ignoring irrelevant contexts in general (Tafjord et al. [2000] Ho et al. 2020; [Shi et al., 2023). The
BIG-Bench suite of reasoning benchmarks (Srivastava al. (022) contains many tasks which require maintaining a discrete state over a sequence of transitions. Thus, more than a toy model, flip-flop languages are embedded verbatim within many sequence processing tasks. We offer some additional perspectives below.
Algebraic properties and expressive power Flip-flops are the computational building blocks of memory. The flip-flop monoid F (Definition T. an algebraic encoding of a flip-flop's dynamics. is the smallest monoid whose operation is both non-conumteeriee and non-invertible. JF plays an essential role in the Krohn-Rhodes theory of automata and semigroups (Rhodes al., 2010). whose central structure theorem (Krohn and Rhodes 1965 Zeiger 1967, Eilenberg] 1974) implies that constant-depth cascade of parallel flip-flops simulates all group-free finite-state automata. Thus, in
rigorous sense, the robust learning of flip-flops is not only a necessary condition for reasoning, but sufficient condition for a wide class of algorithmic capabilities.
Intended functionality of attention. One can also appeal to the origin of attention mechanisms (Bahdanau et al. 2014 Luong et al. 2015 Vaswani et al. 2017): attention was specifically designed to attend to (i.e. selectively retrieve and copy) ) data over long-range dependencies. Indeed, it is easy to verify that single attention head can perform the required lookup (see Proposition ( It is thus
logical to ask how well a purely attention baaeee architecture performs this elementary operation.
4 Attention glitches: long tail of errors for Transformer FFLMs
In our main set of synthetic experiments,
train neural language models to generate strings from the flip-flop language FFL((T = 512. p = (0.1, 0.1, 0.8)) (for short, FFL = 0.8)). and probe whether the networks robustly learn the language. Although every valid flip-flop string is supported in this distribution, some sequences are far rarer than others; we measure tail behavior via probes of extrapolation, defined here as out-of-distribution evaluations which amplify the probabilities of the rare sequences. To create these "challenging" sequences, we sample > 3 x 10 sequences from (O.90. (containing unusually many "sparse" sequences with mostly ignore instructions), as well as FFL().1) (many "dense" sequences). Training and evaluating the read accuracies of Transformer models of various sizes, as well as a recurrent LSTM model, we find the following (see Figure
(R1) Transformers exhibit long, irregular tail of errors. Such errors occur on both sparse and dense sequences. Further, a model's outto--distribution test error varies significantly between random seeds (initializations as well as stochastic minibatches), and even between iterates within the same training run.
(R2) LSTMs extrapolate perfectly. In stark contrast, with 20 times fewer training samples and iterations, a I-layer recurrent model achieves 100% accuracy, on 100 out of 100 runs.
Data release. For reproducibilit we publish this synthetic data at https://huggiine aatasets//ynthhh//liittttt
co/
16M FFL(0.8) training sequences, 16K FFL((.8) in-distribution
"What this formally entails for representation and generalization is topic of recent theoretical inquiry Edelman et al. 2022 Wei et al. (002aa).
"In the remaining of the paper, will use FFL((s) shorthand, with T 512 and pw pr =1- 1-p.
5

---

Transformers (20 more data steps)
Natural LM evalustions FFL10.6)
1-layer
Inditribcte s.s. (7F0..3)
i 35M
10
10-1
50
Test
GF Nook 208
10-1
Pyltti 120
GPT: 1.50
10
13
GPT22 137M
GP712 734M
183
250 Craining Banations
300
ade
50
10-
10
50
200
soquenoe longth
training nterations
FRL(P, = =08) wi101000000
FFL(0.9) MO.
FFL(0.1): 10
Figure 3: Top: Training curves of recurrent (left) vs. Transformer (center) architectures on FFLM, with best-so-far evaluation errors highlighted for clarity. Transformers fail to extrapolate robustly the long tail of long-range dependencies, even on this extremely simple task of remembering one bit. The [bolded box contains our chosen 6-layer 19M-parameter canonical baseline model. We find that the ability complete flip-flop language prompts emerges in natural language models, but is not robust (right). Bottom: examples from the sparser FFL(0.98) and denser FFL(0.1) distributions, causing distinct (long-range and short-range) failure modes for the baseline Transformer model.
test sequences, 160K sparse o.o.d. sequences from FFL(0.98). and 4K FFL((.1)) dense o.o.d. se- quences from F0.(9. Our data pipelines can be replicated exactly by taking the appropriate prefix slices of these datasets.
As a counterpart to these findings, we observe similar anomalies in real LLMs, when prompted to complete natural textual embeddings (Figure 2 top right) of flip-flop tasks:
(R3) 10B-scale natural LMs correctly process flip-flop languages, but not robustly. Beyond a certain scale, natural language models can learn to process (natural embeddings of) flip-flop languages from in-context demonstrations. However, this emergent capability is not robust: there exist rare read errors, whose probabilities amplify as the sequence length grows. We provide details for the few-shot evaluation protocol in Appendix B.2.1
4.1 Multiplicity of mechanisms for attention glitches
What failure mechanisms account for these reasoning errors, which occur for both short- and long- range dependencies? The model capability is not concern discussed earlier (see Proposition ().
In this section, we discuss how Transformer self-attention modules, when tasked with representing flip-flops, can exhibit multiple (perhaps mutually entangled) failure mechanisms. The accompanying
propositions are proven in Appendices C.2 and C.3
An insufficient explanation: implicit n-gram models. As a warmup. consider language model Pr|m++a| [gge]] which only depends on the n most recent tokens in the context. Then, n < 1-p"
the bulk of Pr's predictions on FFL(p: = p) can be no more accurate than random guessing. This recovers one qualitative trend (degradation of accuracy with dependency length) observed in the experiments. However, this cannot fully explain our findings: it fails to account for the incorrect predictions dense sequences. Furthermore, the Transformers" outputs on FFL(0.98) are mostly correct; their accuracies on very long-range dependencies are nontrivial, despite not being perfect. There must therefore be subtler explanations for these errors.
Lipschitz limitations of soft attention. Moving to finerggrained failure mechanisms, a known Hahn, 2020 Chiang and Cholak 2022) drawback of soft attention that softmax operation can be "too soft" for any weight matrices with fixed norms, the attention gets "diluted" across positions as the sequence length increases, and can fail to perform an intended "hard selection" operation. We provide formal statement and proof (Proposition in Appendix

---

Difficulty of non-commutative tiebreaking. Can we simply robustify soft attention by replacing it with hard attention? We present a brief analysis which suggests that even hard attention can be brittle. In stylized setting (one-layer models with linear position encodings), we show that self-attention can confidently attend to the wrong index, unless the weight matrices precisely satisfy an orthogonality condition (Proposition D This suggests the existence of spurious local optima, which we do not attempt to prove end-to-end; however, we provide supporting empirical evidence in the experiments in Appendix C.3
5 Mitigations for attention glitches
In this section, we investigate various approaches towards eliminating the long tail of reasoning errors exhibited by Transformer FFLMs. We select the 19M-parameter model (which has L layers, = 512 embedding dimensions, and H = heads) from Section 4 as a canonical baseline, and conduct precise evaluations of various direct and indirect interventions.
5.1 Effects of training data and scale
Ideal solution: improving data coverage. Prior work has made clear that data significantly impacts the performance (Schuhmann et al.) 2022] Eldan and Li 2023). Hence, begin by examining what is perhaps the most obvious solution: removing the need for out-of-distribution extrapolation, by
training directly more diverse examples. Indeed, verify that this works near-perfectly:
(R4) Training on rare sequences works best, by wide margin. By training on a uniform mixture of FFL distributions with pı {0.9, 0.98, 0.1}, the baseline architecture reliably converges to solutions with significantly fewer errors on each of these 3 distributions (teal violins in Figure 4 out of 25 runs, we did not detect single error.
This should not be surprising, in light of the realizabillity of flip-flops by self-attention (and, more generally, the existence of shortcuts functionally identical to RNNs (Liu et al. (023)), and corrobo- rates similar conclusions from (Zhang et al. (021). We also find that weaker improvements emerge by straightforwardly increasing scale parameters in the model and training pipelines:
(R5) Resource scaling (in-distribution data, training steps, network size) helps. However, the improvements are orders of magnitude smaller than those in (R4), and we observe tradeoffs between sparse- and dense-sequence extrapolation; see the blue violins in Figure
Another class of direct solutions is to externalize the chain of thought (CoT): train (or finetune, or prompt) the model explicitly output the intermediate reasoning steps (Nye et al.. 2021 Wei et al.) 2022b). We do not investigate this strategy in this paper, and note that prior work has provided sufficient evidence to affirm its efficacy
inducing the robust learning of recurrences on long synthetic sequences (Anil et al.) [002)] Zhou et al. 2022 Liu et al.) (023). Even when applying CoT in practice, we believe attention glitches may still occur, as flip-flops operations may be embedded within a single indivisible reasoning step. Thus, the focus of this work is to isolate and mitigate this intrinsic architectural issue. We provide additional references and discussion in Appendix A.2
5.2 Indirect algorithmic controls: a bag of regularization tricks
The interventions listed in Section 5. are all potentially practical, and may shed light on how closed- domain LLM hallucinations will diminish with data quality, scale, and improved inference strategies. However, it is not always feasible to implement these fixes under resource constraints (especially data). We next investigate an orthogonal design space, of how to robustify the internal memory mechanisms of neural sequence models. Note that the exceptionally strong extrapolative performance of the L.STM provides a "skyline", showing the possibility of far more robust architectures than the Transformer (in the flop-flp setting, with this restricted set of considerations).
Standard regularization heuristics. There a large array of tricks for "smoothing" the behavior of L.MSs. We test the extrapolative behavior of models trained with weight decay and dropout (at the attention, feedforward, and embedding layers), as well as host of algorithmic choices known to modulate generalization (batch sizes, learning rates, optimizer
algorithmic
7

---

Extrapolation of models trained on FFL(0.8)
10"
0.c.d test erher on FFUO 981 Espanse taill
10-1
10-1
FRLL 100
10-1
20-1
2011
10-0
20"
10-1
10-
30-44
10-1
other Transformers layer LSTH
20-4
o.o.d. tast erfor on F) (dense tall
Figure 4: A long tail of flip-flop errors for 10,625 Transformer models. Left: Out- Out-of-distribution evaluations for all models; some algorithmic choices help substantially (note the logarithmic axes), but nothing we tried, aside from training on o.o.d. data, could fully eliminate attention glitches. Right: Effects of individual architectural and algorithmic choices on both types of extrapolation (sparse and dense sequences). Some configurations reduce attention glitch rates by orders of magni- tude. Horizontal marks denote (min, 25% median, 75%, max] test errors on >> 3 x 10 predictions, over replicates (500 for the baseline model). Dots at the bottom indicate runs with error.
hyperparameters, position embeddings, activation functions). Due to the extreme variability noted in (RI), we quantify effects extrapolation by training and evaluating at least 25 replicates for each choice under consideration.
Attention sharpening: non-standard regularization technique. Inspired by the "diluted hard attention" calculation in Section 4.1 and the fact that the attention heads of trained models do not attend sharply (see Figure 5). we train Transformer models with attention-shar sharpening regularizers " during training, for attention weights A(TT), adding differentiable loss terms which encourage sparsity (e.g. the mixture's s entropy (a)), or negative p-norms - -|(o=] -|
(R6)
Many algorithmic choices influence extrapolative behaviors. We find that some architectural variants and regularization tricks have orders-of of-mmnnitude effects on the performance of Transformers; see the purple, brown, red, and gold violins in Figure 4 (right). Our strongest improvements on sparse sequences are obtained by large (0.5) embedding dropout and sitention-sharpeningg losses; on dense sequences, non-trainable position embeddings are the most helpful.
(R7) Despite many partial mitigations, nothing eliminates attention glitches entirely. The scatter plot in Figure 4 (left) gives an overview of our entire search over architectures and hyperparameters, showing (dense-sequence error, sparse-sequence error) pairs for every model we trained. We found it extremely difficult to find setting that reliably produces Transformer models with simultaneous improvements over the baseline on sparse and dense sequences. Recall that it is trivial do so with an LSTM model.
5.3 Preliminary mechanistic study of the trained networks
In this section, we move simpler setting to gain aner-grained understanding of how sparsity regularization affects the learned solutions. Specifically, we look at the task of simulating the fli-ffip automaton (Definition] D. whose inputs consist {oo, 01, 11 as two types of write and no-op. This task (elaborated in Appendix A) can be solved by a 1-layer Transformer with single attention head which attends sparsely on the most recent write position. also serves as a building block for more complex tasks (Liu et al. 2023), hence observations from this simple setup can potentially be useful in broader contexts.
"While less popular, such losses have been used to sparsify dependencies in similar contexts Zhang et al. Sukhbaatar al. 2021)
2018
8

---

(c)
(a)
(b)
(d)
Figure 5: Causal attention patterns for flip-flop simulation (Definition D orange dots blue diamonds mark the positions of write tokens do / 01. (b). subselected respectively from regular (non- sparse) and a sparse multi-layer model (details in Appendix [B.5). (c), (d) are from two I-layer 1-head models. The attention pattern highlighted by the purple box (b) coincides with the "ideal" attention pattern in (c). However, sparse models can be wrong, as shown in (d) (error marked in red).
Figure 5 shows examples of attention patterns the flip-flop simulation task. subselected from 6-layer 8-head models trained with and without attention- iieettin-shhrpening regularization. It is evident that the attention patterns of the sparse model are less complex and easier to interpret compared those of the un-regularized model. For example, we can identify one head the sparse model that exactly coincide with the attention pattern To that "ideal" 1-layer 1-head model implements (Figure 5cp.
(R8) Attention-sharpeningg regularizers successfully promote hard attention, but errors persist. As mentioned (R7), attention-sharpening regularization cannot fully eliminate the sporadic errors, which are partially induced by the complexity and redundancy of attention patterns. Moreover, sharpened attention can induce additional failure modes, such as confidently attend- ing incorrect write positions. An example is demonstrated in Figure 5d where the attention focuses on an initial write, likely caused by the fact that earlier positions are overemphasized due to the use of causal attention masks. Another example occurs in length generalization. where the attention correct at positions earlier in the sequence, but starts to confidently focus wrong positions moves towards later positions (Proposition 4
In similar spirit to concurrent work on generating Dyck languages (Wen et al. 2023) (a more complex capability which also requires parallel simulation memory registers), these glitchy solutions point to concrete obstruction to mechanistic interpretability. Due to factors such as overparameterization. spurious solutions, and the opaqueness of optimization dynamics, learned neural implementations of algorithms generally do not coincide with "ideal", "minimal", or "natural" theoretical constructions. Details for these experiments and further discussion are provided Appendix B.5
Conclusion and future challenges
We have introduced flip-flop language modeling (FFLM), synthetic benchmark for probing the fine-grained extrapolative behavior of neural sequence models, based on a one-bit memory operation which forms fundamental building block of algorithmic reasoning. Despite being able realize this operation trivially. Transformer models do not extrapolate robustly: they exhibit a long tail of sporadic reasoning errors, which we call attention glitches. Through extensive controlled experiments, we find that many algorithmic mitigations can reduce the frequency of attention glitches, but only recurrence and training on longer-failed data work perfectly. FFLM provides a concrete and minimalistic setting in which Transformers are far inferior to recurrent sequence models, with respect multiple criteria (efficiency, stability, and extrapolation).
While it well-known that attention patterns can misleading times (Jain Wallace 2019 Bolukbasi et al. 2021, Meister et al. 2021), they do provide upper bounds on the magnitude of the dependency among tokens. These upper bounds are particularly useful in the case of (1-)sparse attention: a (near) zero attention weight signifies the absence of dependency, which greatly reduces the set of possible solutions implemented.

---

What does this entail about hallucinations in natural LLMs? The motivating issue for this work is the phenomenon of "closed-domain hallucinations" in non-synthetic LLMs (e.g. the errors demonstrated in Figure D.. We hypothesize that attention glitches occur in the internal algorithmic representations Transformer models of natural language, and that they account for (a non-negligible portion of) the reasoning errors encountered in practice. To our knowledge, this is the first attempt to attribute model hallucinations to a systematic architectural flaw in the Transformer. However, confirming or refuting this hypothesis is far outside the scope of this paper; the opaque indirections and lack of adequate controls on the training data present significant methodological challenges. Even precisely articulating this hypothesis leaves degrees of freedom which are difficult resolve; see the discussion in Appendix A.4 We therefore leave these topics for future work.
Paths to hallucination-free Transformers? Our findings suggest that in the near term, there are many
approaches for reducing the frequency of attention glitches: data (particularly with high diversity). scale, and various forms of regularization. Yet, the strikingly outsized benefit of replacing the Transformer with an LSTM network suggests that architectural innovations towards the same ends are well worth examining. Obtaining a practical best-of-bothe worlds architecture is grand open challenge, for which new recurrent designs (Katharopoulos et al., 2020, Dao et al.) 2022 Peng et al. 2023] Anonymous) 2023) show great promise. Note that we do not make the claim that recurrent architectures are the only ones which can extrapolate robustly
Broader impacts and limitations. This work is inherently foundational, and focuses on precise measurements of generalization in an idcalized setting: see Appendix [A.4 for discussion of the limitations this entails. By introducing methodologies to isolate, measure, and control the long tail of reasoning eттоrs in neural sequence models, we hope that this work will contribute to the systematic and principled discovery of LLM pipelines with improved factual reliability. Such improvements may result unintended downstream consequences, such as higher-fluenc, malicious content generation.
Acknowledgements
We would like to thank Yuchen Li for helpful discussions and comments on the paper.
References
Abnar, S., Dehghani, M., and Zuidema, W. (2020). Transferring inductive biases through knowledge distillation. arXiv preprint arXiv:2006.00555.
Ahn, K., Cheng, X., Song, M., Yun, C., Jadbabaie, A., and Sra, S. (2023). Linear attention is (maybe) all you need (to understand transformer optimization). arXiv preprint arXiv: 2310.01082.
Anil, C., Wu, Y., Andreassen, A., Lewkowycz. A., Misra, V., Ramasesh, V., Slone, A., Gur-Ari, G., Dyer, E., and Neyshabur, B. (2022). Exploring length generalization in large language models. arXiv preprint vrXiv:2207.04900
Anonymous (2023). Mamba: Linear-tima sequence modeling with selective state spaces. In Submitted to The Twelfth International Conference on Learning Representations. under review.
Bahdanau, D., Cho, K., and Bengio, Y. (2014). Neural machine translation by jointly learning to align and translate. arXiv preprint MDXX:v114990473
Barak, B., Edelman, B., Goel, S., Kakade, S., Malach, E., and Zhang, C. (2022). Hidden progress in deep learning: Sgd learns parities near the computational limit. Advances in Neural Information Processing Systems, 35:21750-21764.
Barrington, D. A. M. and Thérien, D. (1988). Finite monoids and the fine structure of NC1. Journal of the ACM.
In particular, for algorithmic reasoning capabilities corresponding to the recurrent execution of deterministic finite-state machines, the results of (Liu et al. 2023) imply that the Transformer has "reparameterized" recurrent inductive bias, which parallelizes and hierarchizes any looped recurrence.
10

---

Bertsch, A., Alon, U., Neubig, G., and Gormley, M. R. (2023). Unlimiformer. Long-range transform- ers with unlimited length input. arXiv preprint arXiv:2305.01625.
Bhattamishra, S., Ahuja, K., and Goyal, N. (2020). On the ability and limitations of transformers to recognize formal languages. In Conference on Empirical Methods in Natural Language Processing.
Bolukbasi, T., Pearce, A., Yuan, A., Coenen, A., Reif, E.., Viégas, F,, and Wattenberg, M. (2021). An interpretability illusion for BERT. arXiv preprint arXiv:2104.07143
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020). Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901.
Chen, S., Zhang, F., Sone, K., and Roth, D. (2021). Improving faithfulness abstractive summariza- tion with contrast candidate generation and selection. North American Chapter Of The Association For Computational Linguistics.
Chiang, D. and Cholak, (2022). Overcoming a theoretical limitation of self-attenton. arXiv preprint arXiv:220..12177.
Chomsky, N. and Schützenberger, M. P. (1959). The algebraic theory of context-free languages. In Studies in Logic and the Foundations of Mathematics.
Creswell, A., Shanahan, M., and Higgins, I. (2023). Sclection-inference Exploiting large language models for interpretable logical reasoning. In The Eleventh International Conference on Learning Representations.
Dai, Z., Yang, Z., Yang. Y., Carbonell, J., Le, Q. V., and Salakhutdinov, R. (2019). Transformer-xh Attentive language models beyond fixed-lengti context. ACL.
Dao, T., Fu, Y., Saab, K., Thomas, W., Rudra, A., and Ré, C. (2022). Hungry hungry hippos: Towards language modeling with state space models. arXiv preprint 2rXiv:22/2.14052.
Dehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., and Kaiser, E.. (2018). Universal transformers. arXiv preprint arXiv: 1807.03819.
Dhingra, B., Faruqui, M., Parikh, A., Chang, M.-W., Das, D., and Cohen, W. (2019). Handling divergent reference texts when evaluating table-to-text generation. In Proceedings of the 57th Anmual Meeting of the Association for Computational Linguistics, pages 4884-4895, Florence, Italy, Association for Computational Linguistics.
Dziri, N., Madotto, A.. Zaiane, O., and Bose, A. (2021). Neural path hunter: Reducing hallucination in dialogue systems via path grounding. Conference On Empirical Methods In Natural Language Processing.
Dziri, N., Milton, S., Yu, M., Zaiane, O. R., and Reddy, S. (2022). On the origin of hallucinations in conversational models: Is it the datasets or the models? North American Chapter Of The Association For Computational Linguistics.
Eccles, W. and Jordan, (1919), A trigger relay utilizing three-electrode thermionic vacuum tubes. The Electrician, 83:298.
Eccles, W. H. and Jordan, F. W. (1918). Improvements in ionic relays. British patent number: GB, 148582:704.
Edelman, L., Goel, S., Kakade, S., and Zhang, C. (2022). Inductive biases and variable creation in
self-attention mechanisms. In International Conference on Machine Learning, pages 5793-5831. PMLR.
Eilenberg, S. (1974). Automala, languages, and machines. Academic Press.
Eldan, R. and Li, Y. (2023). TinyStories: How small can language models be and still speak coherent English? arXiv preprint 2rXiv:2305.07759
Elman, J. L. (1990). Finding structure in time. Cognitive science, 14(2):179-211
11

---

Garg, S., Tsipras, D., Liang, P. S., and Valiant, G. (2022). What can transformers learn in in-contex?? case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583-30598.
Graves, A., Wayne, G., and Danihelka, I. (2014). Neural turing machines. arXiv preprint arXiv:1410.5401.
Guo, M., Ainslie, J., Uthus, C., Ontañón, S., Ni, J., Sung. Y., and Yang, (2022). Longt5: Efficient text-to-text transformer for long sequences. In Carpuat, M., de Marneffe, M., and Ruíz, I. V. M., editors, Findings of the Association for Computational Linguisties: NAACL 2022, Seattle, WA, United States, July 10-15, 2022, pages 724-736. Association for Computational Linguistics.
Hahn, M. (2020). Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171.
Haviv, A., Ram, O., Press, O., Izsak, P., and Levy, O. (2022). Transformer language models without positional encodings still learn positional information. arXiv preprint arXiv:2203. 16634.
He, T., Zhang, J., Zhou, Z., and Glass, J. R. (2019). Exposure bias versus self-recovery: Are distortions really incremental for autoregressive text generation? Conference On Empirical Methods In Natural Language Processing.
Ho, X., Duong Nguyen, A...., Sugawara, S., and Aizawa, A. (2020). Constructing a multi-hop QA dataset for comprehensive evaluation of reasoning steps. Proceedings of the 28th Interna- tional Conference Computational Linguistics, pages 6609-6625, Barcelona, Spain (Online). International Committee on Computational Linguistics.
Hochreiter, and Schmidhuber, J. (1997). Long short-term memory. Neural computation, 978): 1780.
Jain, S. and Wallace, B. C. (2019). Attention is not explanation. North American Chupter Of The Association For Computational Linguistics.
Jelassi, S., Sander, M. E., and Li, Y. (2022). Vision transformers provably learn spatial structure. In NeurIPS.
Ji, Z., Lee, N., Frieske, R., Yu, T., Su, D., Xu, Y., Ishii, E., Bang, Y. J., Madotto, A., and Fung, P. (2023). Survey of hallucination in natural language generation. ACM Computing Surveys, 55(12):1-38.
Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F. (2020). Transformers are rnns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, pages 5156-5165. PMLR.
Khandelwal, U. He, H., Qi, P., and Jurafsky, D. (2018). Sharp nearby, fuzzy far away: How neural language models use context, arXiv preprint arXiv: 046.04623.
Khandelwal, U., Levy, O., Jurafsky, D., Zettlemoyer, L., and Lewis, M. (2019). Generalization through memorization: Nearest neighbor language models. International Conference On Learning Representations.
Krohn, K. and Rhodes, (1965). Algebraic theory of machines, I: Prime decomposition theorem for finite semigroups and machines. Transactions of the American Mathematical Society
Lanchantin, J., Toshniwal, S., Weston, J., Szlam, A., and Sukhbaatar, S. (2023). Learning to reason and memorize with self-notes. arXiv preprint arXiv: Arxiv-2305.00833
Lee, N., Sreenivasan, K., Lee, J. D., Lee, K., and Papailiopoulos, D. (2023). Teaching arithmetic to small transformers. arXiv preprini arXiv: 2307.03381.
Li, Y., Li, Y.-F,, and Risteski, A. (2023). How do transformers learn topic structure: Towards mechanistic understanding. International Conference on Machine Learning.
Linzen, T., Dupoux, E., and Goldberg, (2016). Assessing the ability of Istms to learn syntax- sensitive dependencies. Transactions of the Association for Computational Linguistics, 4:521-535.
12

---

Liu, B., Ash, J., Goel, S., Krishnamurthy, A., and Zhang, C. (2023). Transformers learn shortcuts to automata. International Conference On Learning Representations.
Longpre, S., Perisetla, K., Chen, A., Ramesh, N., DuBois, C., and Singh, S. (2021). Entity-
based knowledge conflicts in question answering. Conference On Empirical Methods In Natural Language Processing.
Loshchilov, I. and Hutter, F. (2017). Decoupled weight decay regularization. arXiv preprint arXiv:1711.0501.
Luong, M.-T., Pham, H., and Manning, C. D. (2015). Effective approaches to attention bbasd neural machine translation. arXiv preprint arXiv: weo::::0844400 04025.
Malkin, N., Wang, Z., and Jojic, N. (2022). Coherence boosting: When your pretrained language model is not paying enough attention. In Muresan, S., Nakov, P., and Villavicencio, A., editors, Proceedings of the 60th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). ACL 2022, Dublin, Ireland, May 22-27, 2022, pages 8214 8236. Association for Computational Linguistics.
Meister, C.,, Lazov, S., Augenstein, and Cotterell, R. (2021). sparse attention more interpretable? Annual Meeting Of The Association For Computational Linguistics.
Miceli-Barone, A. V., Barez, F., Konstas, I., and Cohen, S. B. (2023). The larger they are, the harder they fail: Language models do not recognize identifier swaps in python. arXiv preprint arXiv: 2305.15507.
Nanda, N. and Lieberum, T. (2022). A mechanistic interpretability analysis of grokking. Alignment Forum.
Nogueira, R., Jiang. Z., and Lin, (2021). Investigating the limitations of transformers with simple arithmetic tasks. 1rXiv:2102.13011
Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D., Dohan, D., Lewkowycz, A., Bosma, M., Luan, D., et al. (2021). Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114
OpenAl (2023). GPT-4 technical report. arXiv preprint arXiv:2303.08774
Orvieto. A., Smith, S. L., Gu, A., Fernando, A., Gulcehre, C., Pascanu, R., and De, S. (2023).
Resurrecting recurrent neural networks for long sequences. ARXIVOOG..
Parikh, A. P., Wang. X., Gehrmann, S., Faruqui. M., Dhingra, B.. Yang, D., and Das, D. (2020). Totto: A controlled table-to-text generation dataset. Conference On Empirical Methods In Natural Language Processing.
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., Vetooo, 7., Lin, Z.,, Desmaison, A., Antiga, L., and Lerer, A. (2017). Automatic differentiation in pytorch.
Peng, B., Alcaide, E., Anthony, Q., Albalak, A., Arcadinho, S., Cao, H., Cheng, X., Chung, M., Grella, M., GV, K., He, X.. Hou, H., Kazienko, P., Kocon, J., Kong, J.,, Koptyra, B., Lau, H.. Mantri, K. S. I., Mom, F., Saito, A., 'Tang, X., Wang, B., Wind, J. S., Wozniak, S., Zhang, R., Zhang, Z., Zhao, Q., Zhou, P., Zhu, J., and Zhu, R.-J (2023). RWKV: Reinventing RNNs for the Transformer era. arXiv preprint arXiv: 2305. 13048.
Petroni, F., Rocktäschel, Lewis, Bakhtin, A., Wu, Y., Miller, A. H., and Riedel, S. (2019). Language models as knowledge bases? Conference On Empirical Methods In Natural Language Processing.
Phuong, M. and Hutter, M. (2022). Formal algorithms for transformers. arXiv preprint arXiv:2207.09228.
Press, O., Smith, N. A., and Lewis, M. (2021). Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint 200..22108.12409
13

---

Rhodes, J., Nehaniv, C. L., and Hirsch, M. W. (2010). Applications of automata theory and algebra: via the mathematical theory of complexity to biology, physics, psychology, philosophy, and games. World Scientific.
Samorodnitsky, G. et al. (2007). Long range dependence. Foundations and Trends@ in Stochastic Systems, 133):163-257.
Saparov, A. and He, H. (2022). Language models are greedy reasoners: A systematic formal analysis of chain-of- thought arXiv preprint arXiv:2210.01240.
Schuhmann, C., Beaumont, R., Vencu, R., Gordon, C., Wightman, R., Cherti, M., Coombes, T., Katta, A., Mullis, C., Wortsman, M., et al. (2022). Laion-5b: An open large-scale dataset for training next generation image-text models. arXiv preprint (:Xiv:2210.084000
Shao, Z., Gong, Y., Shen, Y., Huang, M., Duan, N., and Chen, W. (2023). Synthetic prompting: Generating suuin-of-thougee demonstrations for large language models. ARXIVORG.
Shazeer, N. (2020). Glu variants improve transformer. arXiv preprint arXiv:2002.05202.
Shi, F., Chen, X., Misra, K., Scales, N., Dohan, D., Chi, E., Schärli, N., and Zhou, D. (2023). Large language models can be easily distracted by irrelevant context. arXiv preprint (xXXx:2302.00000
Srivastava, A., Rastogi, A., Rao, A.. Shoeb, A. A. M., Abid, A., Fisch, A., Brown, A. R., Santoro,
A., Gupta, A., Garriga-Alonso, A., et al. (2022). Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.0400 04615.
Su, J., Lu, Y., Pan, S., Murtadha, A., Wen, B., and Liu, Y. (2021). Roformer: Enhanced transformer with rotary position embedding. arXiv preprint arXiv:2104.09800
Sukhbuatar, S., Ju, D., Poff, S., Roller, S., Szlam, A. D., Weston, J., and Fan, A. (2021). Not all memories are created equal: Learning forget by expiring. International Conference On Machine Learning.
Sun, S., Krishna, K., Mattarella-Mick, A., and lyyer, M. (2021). Do long-range language models actually use long-range context? In Proceedings of the 202/ Conference on Empirical Methods in Natural Language Processing, pages 807-822, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
Sutskever, I., Martens, J., Dahl, G., and Hinton, G. (2013). On the importance of initialization and momentum in deep learning. In International conference on machine learning, pages 1 1139-1147. PMLR.
Tafford, O., Dalvi, B., and Clark, P. (2020). Proofwriter: Generating implications, proofs, and abductive statements over natural language. FINDINGS.
Tay, Y., Dehghani, M., Abnar, S., Shen, Y., Bahri, D., Pham, P., Rao, J., Yang, I.., Ruder, S., and Metzler, D. (2020). Long range arena: A benchmark for efficient transformers. arXiv preprint arXiv:2011.04006
Tian, R., Narayan, S., Sellam, T., and Parikh, A. (2019). Sticking to the facts: Confident decoding for faithful data-to-text generation. arXiv preprint arXiv: 1910.08684.
van der Poel, S., Lambert, D., Kostyszyn, K., Gao, T., Verma, R., Andersen, D., Chau, J., Peterson, E., Clair, C. S., Fodor, P., Shibata, C., and Heinz, J. (2023). Miregtest: A benchmark for the machine learning of regular languages. arXiv preprint arXiv: Arxiv-2304.07687.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017). Attention is all you need. Advances in neural information processing systems, 30.
Wang, X., Wei, J., Schuurmans, D., Le, Q., Chi, E., Narang, S., Chowdhery, A., and Zhou, D. (2022). Self-consistency improves chain of thought reasoning language models. arXiv preprint arXiv:
14

---

Wei, C., Chen, Y.. and Ma, T. (2022a). Statistically meaningful approximation: case study on approximating turing machines with transformers. Advances Neural Information Processing Systems, 35:1207: 2071--008.
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Chi, E., Le, Q. and Zhou, D. (2022b). Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11900
Wen, K., Li, Y., Liu, B., and Risteski, A. (2023). Transformers are uninterpretable with myopic methods: study with bounded Dyck grammars. In Thirty-sevnnth Conference xon Neural Information Processing Systems.
Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., al. (2019). Huggingface's transformers: State-of-the-art natural language processing. arXiv preprint 1iii::1900.333
Wu, Y., Rabe, M. N., Hutchins, D. and Szegedy, C. (2022). Memorizing transformers. International Conference On Learning Representations.
Wu, Y., Rabe, M. N., Li, W., Ba, J., Grosse, R. B., and Szegedy, C. (2021). Lime: Learning inductive bias for primitives of mathematical reasoning. In International Conference on Machine Learning, pages 1 1122-- PMLR.
Wu, Y., Schuster, M., Chen, Z., Le, Q. V., Norouzi, M., Macherey, W., Krikun, M., Cao, Y., Gao, Q.. Macherey, K., al. (2016). Google's neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv: 1609.08144.
Yao, S., Peng, B., Papadimitriou, C., and Narasimhan, K. (2021). Self-attention networks can process bounded hierarchical languages. arXiv preprint arXiv:2105.11115.
Zeiger, H. P. (1967). Cascade synthesis of finite-state machines. Information and Control.
Zhang. C., Raghu, M., Kleinberg, J., and Bengio, S. (2021). Pointer value retrieval: A new benchmark for understanding the limits of neural network generalization. arXiv:2107.12558
Zhang. J., Zhao, Y., Li, H., and Zong, C. (2018). Attention with sparsity regularization for neural machine translation and summarization. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 27)3)5007-518.
Zhang, M., Press. O., Merrill, W., Liu, A., and Smith, N. A. (2023). How language model hallucina- tions can snowball. arXiv preprint arXiv: 2305.13534.
Zhang, Y., Backurs, A., Bubeck, S., Eldan, R., Gunasekar, S., and Wagner, T. (2022). Unveiling transformers with lego: a synthetic reasoning task. arXiv preprint arXiv:2206.04301
Zhao, H., Panigrahi, A., Ge, R., and Arora, S. (2023). Do transformers parse while predicting the masked word? arXiv preprint arXiv:2303.08
Zheng, C., Liu, Z.,, Xie, E.,, Li, 7.,, and Li, Y. (2023). Progressive-hint prompting improves reasoning in large language models. arXiv preprint arXiv.2304.0979)
Zhou, H., Nova, A., Larochelle, H., Courville, A., Neyshabur, B., and Sedghi, H. (2022). Teaching algorithmic reasoning via in-context learning, arXiv preprint arXiv:2211.090
15

---

Appendix
Table of Contents
A Deferred background and discussion
17
A.1 Flip-flop terminology and history
17
A.2 Additional related work]
18
Why this tlip-flp language")
Attention glitches natural LLMS
B
Full
experimental results
20
B.1
Details for LLM addition prompts (Figure
................................
20
B.2
Extrapolation failures of standard Transformers (Section
21
B.3
Effects of training data and scale (Section 5.1)
24
B.4
Indirect algorithmic controls for extrapolation (Section 5
...........
25
B.5
Preliminary mechanistic study and challenges (Section 5.3
..........
27
Software, compute infrastructure, and resource costs
32
C
Proofs for Section 4.1
32
C.I
Realizability of FFL by small Transformers
32
Failure of soft attention: attention dilution with bounded Lipschitzness
34
C.3 Failure of hard attention: bad margin for positional emheddings)
34
16

---

A Deferred background and discussion
A.1 Flip-flop terminology and history
The flop-flop automator 12 enables retrieval of this bit. More precisely, the flip-flop automaton (illustrated in Figure a is defined as:
is two-state machine which remembers a single bit of memory, and
Definition (Flip-flop automaton). A flip-flop automaton A= [Q, (Q. is defined with state space Q = f0, 1}, imput alphabet Σ {oo, 01, 1,, and transition function 8 E Q where
(0) 0,
8(g.01) = 1,
Vg [0,
L( q
The semantics of the input symbols can be intuitively be identified with "write 0", "write 1", and "do nothing". This mathematical object is named after type of electronic circuit which can store single bit of state information (Eccles and Jordan 1918 1919); such physical constructions appear ubiqui- tously in electrical engineering as the building blocks of memory. The task of interest in Section 5.3 is simulating the flip-flpp automaton: the model takes as input a sequence of 01, 02 oT Σ. and learns output the corresponding states gt E for each E [T) after processing inputs d':t-
Naturally associated with the flip-flop automaton its transformation monoid, the closure 13 of its
state transformations d(.,a) Q + Q under function composition. Identifying each symbol with its state transformation map, we can compute the multiplication table of this monoid (f o g for every pair of transformations f,g):
00
9
00
00
00
0
01
01 1
00 01
This algebraic object called the flip-flpp monoid F. Its binary operation is clearly (1) non- invertible (intuitively: the history of the bit cannot be recovered after a "memory write"") and (2) non-commutative (the order of "write" operations matters); it also has (3) an identity element 1 (which does nothing to the memory bit). By enumeration of smaller objects, it can be seen that F the smallest monoid (in terms of order Fl, or fewest number of automaton states [Q) which has properties (1)-(3).
The flip-flop monoid plays a special role in the algebraic theory of automata (Rhodes et al. 2010): flip- flops can be cascaded to represent more complex functions. In particular, the celebrated Krohn-Rhodes theorem (Krohn and Rhodes 1965) gives "prime decomposition" theorem for all finite semigroups (associative binary operations), representing them alternating wreath products of flip-fop monoids and finite simple groups. Further developments (Zeiger) 1967 Eilenberg] 1974) have interpreted this theorem as a structural reparameterization of any finite-state automaton into feedforward hierarchy of simple "atomic" machines (namely, flip-flops and permutation semiautomata). Basic quantitative questions (e.g. "which functions of variables can L layers of poly(n) flip-flops represent?") have proven to be extremely hard to resolve; these are studied by the theories of -rohneRhodes complexity and circuit complexity.
was noted by Barrington and Thérien (1988) that these reparameterizatioon of finite-state automata entail the existence of parallel algorithms (i.c. shallow, polynomial-sized circuits) for sequentially executing finite-state state recurrences (thus, processing formal languages) on sequences of length T. More recently, Liu et al. (2023) establish implications for shallow Transformer neural networks: they show that they can size-efficiently (with depth Oloog T) and parameter count (TT); sometimes both
"SSmettmmss distinction is made between a semiautomaton (Q.E,) Σ, 8) and an automaton, which is a semiautomaton equipped with (not necessarily invertible) mapping from states to output symbols. We do not make such distinction; use "automaton" to refer to this dynamical system.
equip semiautomaton with the output function which simply emits the state and
IIn this case, the closure is the same as the generator set: no functions distinct from da, Ø1, J can be obtained by composing these three functions. This is not true for a general automaton.
17

---

improvable to O(1)) realize these parallel algorithms, and that standard gradient- gradient-based training can empirically learn < Tlayeer solutions on a variety of "hard" automata (e.g. composing a sequence of T 5-element permutations; multiplying T unit quaternions). Here, the role of the flip-flop monoid essential: provides natural way to think about the role of a single self-attention head in a hierarchy of indirections, in order to learn depth--onstrained parallel implementation of sequential algorithm.
A.2 Additional related work
Relevant challenges in NLP: hallucinations and long-range dependencies. The empirical lit- erature is rife with corroborations that neural language models have trouble with robustly fitting
long-range memory and multi-step reasoning (Khandelwal et al. [0188: Sun et al., 2021: Sukhbaatar
ct al. 2021: Malkin et al. 2022 Saparov and 22222 Orvicto et al.
2023] Creswell et al. (023))
Such failures can result in "hallucinations": incorrect outputs which either directly contradict factual
input in the context, or contain information absent in the context (Ji et al.)
2023).
Hallucination can be attributed to various factors, such as the noisiness in data sources (Dhingra ctt al. 2019 Dziri et al. 2022), imperfect encoding/decoding (Parikh et al.) 2020 Tian et al. (0,22019) 9), or the discrepancy in training and evaluation setups (He et al. 2019). In particular, the most related to our paper are the characteristics inherent to the model itselt. For example, prior work has found that Transformers tend to be biased towards information covered during training (Petroni al. 2019; et al. 202I), a potential cause to their poor -utttf-distribuutin performance, and may over-commit to their carlier errors (Zhang et al. 2023)
In terms of mitigation, various "external" methods (i.e. ones which do not modify the internal representations of the neural network) have been proposed to address some of the above factors, or post-processing model generations (Dziri et al.
2021 Chen et al., (02T), possibly utilizing several forward passes (Wang et al. [022 Zheng et al.
2023). Another line of work that have gained much
popularity and success is to incorporate explicit memory mechanisms, which we discuss next.
Explicit memory mechanisms in Transformers. Prior work has shown that augmenting the neural network with memory modules or knowledge base helps improve the performance on long-range texts [Khandelwal waad et al.] [019]] WW et al. 2022] Bertsch et al., 2023). An approach particularly effective for large-scale Transformers
ask the model to output immediate reasoning steps to
"scratchpad" which the model subsequently processes (Nye et al., 2021 Wei et al. 2022b Zhou et al.
2022 Anil et al. 2022 Shao et al., 2023). similar to writing to and reading from a memory tape. particular way to interact with the scratchpad is to interlace every other token with an annotation of "as a reminder, this is the state" (Liu al., 2023 Lanchantin et al., 2023), so that there are no more explicit long-range dependencies. However, this strategy is the same the recurrent solution implementable by RNNs, and it does not always exist, especially when attention glitches occur in an internal component of the model.
Transformers and algorithmic tasks. Compared to real-world language datasets, synthetic tasks provide cleaner and more controlled setup for probing the abilities and limitations of Transformers. Specific algorithmic reasoning. [Liu al. (2023) puts unifying perspective on the ability of small Transformers to succeed at tasks corresponding to algorithmic primitives. Specific tasks of interest
include modular prefix sums (Hahn) 2020 Anil et al. 2022), adders (Nogueira et al. 2021 Nanda
and Lieberum 2022, Lee et al. 2023). regular languages (Bhattamishra et al. [2200] van der Poel itt al., 2023), hicrarchical languages (Yao et al. 2021 Zhao et al. 2023), and following a chain of entailment Zhang et al. 2002
Comparison with Transformers Learn Shortcuts Automata. Liu al. (2023) study the parallel circuits efficiently realizable by low-depth Transformers. The authors identify shortcut solutions, which exactly replicate length-T recurrent computations ("chains of algorithmic reasoning") in the absence of recurrence, with very few (O(log T'; sometimes O(1)) layers. Their results contain general structure theorem of representability, and preliminary positive empirics for generalization and optimization, demonstrating that Transformers can learn these shallow solutions via gradient- based training on samples. contrast, the present work is a fine-grained study of the issue of generalization. Our main empirical contributions are minimally sufficient setup (FFLM) and
18

---

set of large-scald controlled experiments, towards providing reasonable scientific foundations for addressing the unpredictable reasoning errors of LLMs.
A.3 Why this flip-flop language?
Liu et al. (2023) (as well as our mechanistic interpretability experiments) use a purer instantiation of flip-flop sequence processing, in which the sequence-to-sequeene network tasked with non- autoregressive transduction: given the sequence of input symbols o1..... TT, output the sequence of states ....... !T- This is most natural when studying the Transformer architecture's algebraic representations in their most isolated form.
Our autoregressive sequence modeling setting is a slight departure from this setting; we discuss its properties and rationale below.
The autoregressive setting "type-checks" exactly with standard state-of-the-art autoregressive (a.k.a. causal, forward, or next-token-preed (oree--rediction) language modeling. This makes more convenient and intuitive as a plug-and and-play benchmark.
The cost is a layer of indirection: the model needs to associate "instruction" tokens with their adjacent "data" tokens. This is a natural challenge for representation learning, and is certainly a necessary cursor for robust extrapolation on natural sequences that embed similar tasks (like those considered in Figure It straightforward to remove this challenge: simply tokenize at a coarser granularity (i.e. treat (instruction, data) pair as a distinct vocabulary item).
The multi-symbol (and language are more parsimonious. If there are n instead of tokens, this language can be encoded with n + 3 commands. Without the decoupling of "instruction" tokens from "data", the vocabulary size would scale suboptimally with n. In Figure 12, we provide a quick demonstration that attention glitches persist in the presence of larger vocabularies.
etc.) generalizations of the binary flip-flop
The conclusions do not change: in smaller-scale experiments, we observe the same extrapolation failures between the autoregressive and non-au aon-autoregresivee task formulations.
A.4 Attention glitches in natural LLMS
In this section, we expand on the brief discussion from Section 6 At high level, we hypothesize that attention glitches cause (some) closed-domain hallucinations in Transformer models of more complex languages. However, due to the fact that neural networks' internal representations evade simplistic mechanistic characterization, it is significant challenge formulate a rigorous, testable version of this hypothesis. We discuss the subtleties below.
First, we discuss more general notion of attention glitches, of which the flip-flop errors considered in this papers are a special case. We define attention glitches as failures of trained altention-based networks implement a hard retrieval finctionalitty perfectly. To formalize this notion, there are several inherent ambiguities- namelyy the notions of "hard retrieval" and "perfectly", as well as the granularity of "subnetwork" at which an attention glitch can be defined non-vacuously. The FFLM reasoning errors considered in this work provide a minimal and concrete resolution of these ambiguities. We discuss each of these points below:
Hard retrieval: To succeed at FFLM, network's internal representations must correctly imple- ment the functionality retrieving a single bit (from a sequence of bits, encoded unambiguously by the network), selected via the criterion of "most recent write position". This be expanded into a richer functional formulation of hard attention, by generalizing the set of possible retrieved contents (a discrete set of larger cardinality, or, even more generally, continuous set), well as more complex selection criteria (c.g. "least recent position"))
Ground truth: Of course, to define "errors" or "hallucinations" reasoning, there must be well-defined ideal functionality. For FFLM, the notion of "closed-domain" reasoning and hallucinations is evident: the ideal behavior is for model's outputs to coincide with that of the flop-flop machine all input sequences. This straightforwardly generalizes to all formal languages, where the model is expected to correctly produce the deterministic outputs of automata
M~ 10 99M-parameter Transformers were trained in the making of this paper; see Appendix B.6
19

---

Input
GPT-3.55
GPT-4
Answer
8493
10850 /
10850
10850
2357
84935834
108008732 X
108508732 /
108508732
23572898
999199999999 19999999111 1999919999993
16111199100810999 X
16101 1991099999000 x
16101 1991 10900090
+ 6199199190990097
Table I: Examples (in Figure 1 of GPT variants addition: While models tend succeed at additions with a small number of digits, they (nondeterministically fail at longer additions.
which parse these languages. By considering expanded notions of "ground truth", it is possible to capture other notions of model hallucinations (such as incorrectly memorized facts). Our work does not address open-domain hallucinations (i.e. where the model output contradicts real-worls knowledge (OpenAl 2023)). which may be unrelated to attention glitches.
Submodules: Towards attributing implementations and errors to localized components of a network, it is impossible to provide single all-encompassing notion of "localized component". This perennial challenge faced in the mechanistic interpretability literature. Our work considers two extremes: the entire network (in the main experiments, where we probe end-to-end behavior), and single self-attention head (in Sections 4.1 5.3 and Appendix [.5 in which we probe whether single attention head can learn multiplication in the flip-flop monoid). Even when considering the same functionality, attention glitches can considered for different choices of "submodule" Our results reveal key subtlety: in the presence of overparameterization (more layers and parallel heads than necessary according to the theoretical constructions). Transformers learn to process flip-flop languages via soft attention.
We expect that to effectively debug the full scope LLM hallucinations, all of the above choices will need to be revisited, perhaps in tandem.
We hypothesize that the algorithmic reasoning capabilities of real LLMs (i.e. their ability to recognize, parse, and transduce formal symbolic languages) are implemented by internal subnetworks whose functionalities be identified with generalizations of the flip-flop machine. To the extent that such modules exist, attention glitches (the failure of these modules to represent the flip-flpp operations perfectly, due insufficient training data coverage) cause sporadic end-to-end errors ("closed-domain hallucinations"). In this work, we have treated the case of external attention (where the task is to learn the flip-flop directly).
B Full experimental results
B.1 Details for LLM addition prompts (Figure
These addition problem queries serve as quick demonstration of (1) non-trivial algorithmic general- ization capabilities of Transformer-basse LLMs; (2) the brittleness of such capabilities: we directly address this type of reasoning error in this work. Table [2 show these queries and results in detail.
We emphasize that these examples were selected in an adversarial, ad-hoc manner; we do not attempt to formalize or investigate any claim that the errors made by larger models are at longer sequence lengths. We also cannot rule out the possibility that some choice prompt elicits robust algorithmic reasoning (e.g. the prompting strategies explored in (Zhou et al.) ( The only rigorous conc lusiousion to draw from Figure [ that of non-robustness: even LLMSs exhibiting state-of-the-re reasoning continue to make these elementary errors for some unambiguous queries with deterministic answers. was last verified on May 8, 2023 that GPT-4 (in its ChatGPT Plus manifestation) demonstrates the claimed failure mode.
1 Beyond the two extremes considered in this work, some examples include "a subset of attention heads", "a subset of layers", and "a subspace of the entire network's embedding space".
20

---

Input
GPT-3.5
GPT-4
Answer
4491
13250 V
13250 /
13250
8759
80087394
143045342 X
143545342 /
143545342
63457948
510161 1078665398 + 8969499832888802
1.407110011134222==-11
14071 1091110111111111 1354196 x
1407111091 13542000
Table 2: More examples of GPT variants addition: While models tend succeed additions with a small number of digits, they (nondeterministically) fail at longer additions.
B.2 Extrapolation failures of standard Transformers (Section
This section provides full details for our empirical findings (R1) through (R3).
Architecture size sweep. We consider sweep over Transformer architecture dimensionalities, varying the three main size parameters. We emphasize that these somewhat larger than "toy" models: the parameters go up to ranges encountered in natural sequence modeling (though, of course, far short of state-of-the-ae LLMs).
The number of layers (depth) L E 6,,4,6,8).
The embedding dimension d E {128, 256, 512, 1024].
The number of parallel attention heads per layer Il 4, 16). In accordance with standard scaling rules-of-thumb, each head's dimension is selected to be d/H.
Other hyperparameter choices. We sequence length of 7 512, again reflect typical length of dependencies considered by nontrivial Transformer models. We use a canonical set of training hyperparameters for this sweep: the AdamW (Loshchilov and Hutter 2017) optimizer, with (81, (2) = (0.9, 0.999), learning rate 3 x 10-4, weight decay 0.1, 50 steps of linear learning rate warmup, and linear learning rate decay (setting the would-be 10001th step to O). We train for 10000 steps freshly sampled data, and choose minibatch size of 16; consequently, the models in this setup train on 81,920,000 tokens.
Training and evaluation data. Unless otherwise stated, we train our models on online samples (fresh i.i.d. batches) containing moderate-length dependencies (T 512, P: 0.8, Pa Pr 0.1, or FFL(0.8) for short). We evaluate on the following held-out test sets, which are held the same across all training runs:
(i) In-distribution: 10 sequences from the same distribution FFL(0.8), containing 26508 read instructions.
Sparse tail: 10y sequences from FFL(0.98), containing 353875 read instructions.
Dense tail: 3000 sequences from FFL(0.1), containing 345781 read instructions.
When showing training curves, we evaluate emrors only on (i) and the first 1% of (ii) every 100 steps; the purpose of these is only give qualitative sense of instability, and affirm the presence of errors. For the main suite experiments, we focus on reporting the high-precision glitch rate measurements on (ii) and (iii). Final errors (i) are exactly 0 except for small number of non-converged runs (2-layer architectures and badly tuned hyperparameters), so we omit these evaluations in favor of the more informative measurements which focus the sparse and dense tails.
(R1) Transformers exhibit a long, irregular tail of errors. Figure 6 shows training curves for replicates (random seeds) in each setting, while the scatter plot in the main paper shows variability of diitri--iitiiittionnn accuracy across random seeds for the baseline setup. We find that Transformers sometimes succeed at extrapolation, but erratically.
(R2) 1-layer L.STM extrapolates perfectly. We train I-layer L.TTM (Hochreiter and Schmidhuberi 1997) network, with hidden state dimension 128 (for total of 133K parameters), for 500
21

---

Transformer training curves; train on FFL(D, 0.8), test o.n.d. on FFL(p) 0.98)
2. 21:32-mmm 18-heas
4hoax
Shoed
21.25
1224-2m
117
10.1
10.1
10
128.d m 2-nood
4L 225-22m h-hazd
41 4L129 m Bincod
41 128-22200 head
250 2nood
4L235-imm deaa
250 Shoed
41 20 fead
41 2224ii tetd
4L 512- 4-hoad
41 4.5124 seod
41 41522-4mm head
4L 1024-44 2-hood
41 411224-000 2im h-aad
4L 10240-40 din B-houd
4L 1024-iim 16hood
4hoae
127
10.1
31 128- 2-nood
BL 1.2255-6 4-hoad
m 1. Bincod
BL 12112-d 4:3--dmm2d head
250 2nood
250 dim ahcud
BL dim head
01.5 512-4 m road
SL 512-dlm hoad
d1 m sead
81 51 head
SL 1024-dm 2-hood
BL 11102444u0 cin head
dL 1024 din S-huud
5L 1024-imm 16-ood
1.6 349 164
tlors
Figure 6: Examples of training curves over various Transformer architectures, ranging from 46K to 101M trainable parameters. We exhibit (randomly selected) random seeds for each architecture. Lighter curves show raw eггог percentages, while solid curves denote the lowest error far in each run. Notice the following: (1) non-convergence of shallow models (despite representability) (2) failure of most runs to extrapolate (i.e. reach 0% out-of-distribution error); (3) high variability between runs; (4) erratic, non-monotonic progress on out-of aut-of-distribution data, even when the in- distribution training curves appear flat; (5) small LSTM outperforms all of these Transformers (see Figure 3) The bolded box represents 19M-parameter baseline model.
steps with the same optimizer hyperparameters as above. The LSTM model achieves exactly 0 final-iterate o.o.d. error, over 100 out of 100 replicates. In smaller experiments, we found that larger LSTMs (width up to 8192, depth up to 4) also extrapolate perfectly.
22

---

Transformer training ourves: data RMG socds x medel RNG soods
deta nocele
diae model1
dite moM2
dolo D. me
deta C. TODE
Generative Transfommr FFLMs
324
11-
1371
2. model
2 mode2
mobel
329 sioce
EL Shoce
1324 Shead
daaa mooent
eyn mast?
323.dim 2heae
m4has
1102d Shad
2.0 0.1
training tteratiors
149
Figure 7: Additional training curves. Left: Identical baseline architecture, varying the data seeds and 5 model seeds: models in the same encounter the same sequence of data, while models in the same column start from identical initializations. Both sources of randomness affect training dynamics and extrapolation, and it is not clear which is more important. Right: Similar findings for models trained in "fully generative" mode (scoring on all tokens); baseline architecture is in the bolded box
Canonical baseline. We select the 6-layer, 512-dimensional, 8-head architecture (with 19M trainable parameters) as our canonical baseline model: it is large in relevant dimension:"n to real Transformers, while being small enough to allow for thousands of training runs reasonable cost. To fully understand the variability of this single architectural and algorithmic setup, we train and evaluate 500 replicates in this setting.
Random data vs. random initialization. Recent synthetic probes on the surprising behavior of deep neural nets on hard synthetic tasks (Barak et al. 2022; Garg et al. 2022) obtain additional insights by disentangling the effects of data randomness (i.e. the precise sequence of minibatches) vs. model randonness (e.g. random initialization and dropout). We provide a quick demonstration
in Figure 7 (left) that both sources of stochasticity matter. We do not perform more detailed investigation of their precise influence and roles.
Fully generative setting: similar negative results. As mentioned in Section 3.1 to capture setting closer to standard autoregressive (sometimes called GPT-style) language modeling, we find similar failure extrapolate when models trained to predict all tokens, rather than only the deterministic ones (I++1 such that 2e = r). Figure 7 (right) exhibits some training curves for this setting, showing non-extrapolation, variability, and instability. We observe that training (to in- distribution convergence) takes slightly longer this setting, and usually succeeds with the baseline architecture. We do not perform further controlled experiments in this setting.
B.2.1 Evaluating real LLMs on flip-flops
We provide quick corroboration that while LLMs in practice can perform in-context reasoning when the sequences are unambiguously isomorphic to a flip-flpp language. We use the natural language
Except the vocabulary size. In preliminary experiments, we obtained similar findings in the case of token spaces larger than {0, 1).
23

---

User game shell wel "here instrs arite
ther Hore io sequence w 10 11111 1 10: 10/11200 11312 0111311 1011
mad, andiggoce will une an cenoee each of them, resesctvve
Each indtn on wat the britweertty solue 30 1) and
ChandPt the " ter operrton
anoithe whbel ensptterary
that givan secuence oi andivsiuee the sag pencer atiops
opeertons, the va associated with the bus a
with dieesww in couppe thev
wed
gare
(b) Correct short sequences.
CheePPT Ves. unskentend the garne. to danity beteur sthell
Chwrset: varyyay tmightt like bai aree bu vitiie, for inc nec, 1 hu yealenn and medetiitine off.
On
ler iatarci for 'winte lend will wheeps ba followed to takee 10
cedit gowsion lue the unitl you ger
nemence beginningg and and reppetive and commer bebweer them, ihs you turinn off on white and reading the recurs Howerer wi pan more
with the
sistinds for "grord' id will lako be fo Rewwod by wa or 1X
chwags
ends Ir,
pecer se cann ger on aets lmmsee entend
to output the sa that is pained winh the foot the sequence befove fesl With undertanddngg ng lets play ease provid requerte Jento
diswing wia up apen to drow wie oohingon serthigg a pope: but wi hour knowing the movemont nost untions, itss incossblle to peeepee cupuu ot thh
sequanio
(a) Explaining FFLM to ChatGPT.
(c) Wrong on long sequences (input length 1000).
Figure 8: Examples of interacting with ChatGPT-4 (as of 05/22/2023) by explaining FFLM to it.
example from Figure 2 (top right), and evaluate the capability of popular pretrained LLMs to correctly remember the state of light switch. Specifically, write instructions in the FFLM task are either "Alice turns the light off" or "Alice turns the light on". The ignore instructions are either "Bob eats a banana" or "Bob eats an apple". All models are prompted with translated, length- 16 FFLM task that's been translated to English in this way before evaluation.
We measure this accuracy as a function of the sequence length for several well-known LLMs: GPT-2, GPT-2-large, GPT-2-xl, Pythia- and GPT-NeoX-20EE -2BB. Figure 3 shows how well these models perform on this task (i.e. the correctness of the model when prompted with "The light is turned ") as the sequence length is varied. Consistent with the findings of this paper, larger models tend to perform best at this task, and the quality of all models deteriorates with increased sequence length. Each point on the plot considers 500 sequences of the indicated length. All models were prompted with randomly generated, length 16 flip flop sequence to allow the model to learn the task in context. Accuracy is measured according to the frequency with which the model correctly predicts the current state of the light switch, as described in Section B.2.1
(R3) 10B-scale natural LMs can correctly process flip-flop languages, but not robustly.
Note that it is impossible to quantify the degree to which these sequences are "in-distribution" (it is unlikely that any sequences of this form occur in the training distributions for these LLMs). Much like linguistic reasoning evaluations in the style of BIG-bench (Srivastava et al.] 2022). we rely on the emergent capability of in-context inference (Brown et al., 2020) of the task's syntax and semantics. As discussed in Appendix [A.4] this layer of indirection, which is impossible to avoid in the finetuning-free regime, can cause additional (and unrelated) failure modes to those studied in our synthetic experiments. Fully reconciling our findings between the synthetic and non-synthetic settings (e.g. by training finetuning on sequences of this form, or via mechanistic interpretation of non-synthetic language models) is outside the scope of this paper, and yields an interesting direction for future work.
Direct in-context induction of flip-flop languages? Given the conversational abilities of LLMs, another way to interact with existing pretrained model is to explain the definition of FFLM in natural language, and ask the model to output the correct state for r. We test this using ChatGPT (with GPT-4), demonstrated in Figure 8 ChatGPT seems to understand the rules and can get short sequences correct (up to sequence length 400), but makes errors with unexpected connections on longer sequences.
B.3 Effects of training data and scale (Section 51
Here, we provide more details for the interventions outlined in Section 5.1 training distributions and resources.
which directly modify the
24

---

Scaling (data, compute, network size) effects on o.o. o.dd performance
All Scale related runs
10a
o.d.d test error on FFL(0.90) (sparse tail)
10
10
10"
10
10-5
10-1-
-0-
10
10
4oodd daca
10
3x/10 ditapsteps
5Tad (tans)
-0
wond data
Sa and stpp
cod dato
10r oud data lor and staps
3x data stees
1pc deta stage
23
at 51.d
au 5t
1024d
o.o.d. ertor FFL(O.1)
10-h
10- 10-1
Idense tail)
21
Figure 9: Detailed comparisons of various scaling axes, showing violin plots for selected runs (left) and an annotated scatter plot for runs (right); + markers show medians for particular configurations. Increasing training data diversity is by far the most effective way to mitigate attention glitches FFLM. The other scaling axes (increasing the amount of fresh data, increasing the number of optimization steps on the same dataset, and changing the model size) have mixed effects on rare- sequence performance. In particular, we wish to highlight that neither overparameterization nor underparameterrizatoon strongly modulates the rate of glitches.
Long-tailed data. For direct training on long-tailed sequences, we train on an equal mixture of (O.)). FFL(0.98), and FFL(0.1), ensuring that the the sparse and dense tails are both adequately represented in training.
Scaling up data and compute. For both the default and long-tailed training distributions, we consider increasing the number of training iterations by factor of 10, either with freshly generated samples (*Nx data"") or looping over the same training dataset for multiple epochs (*Nx steps").
Scaling up the model. We also perform these exhaustive tail error evaluations all 64 of the architecture scale settings shown in Figure 6 as well as a limited number of larger architectures (shown in Figure 9).
(R4) Training on rare sequences works best, by a wide margin. See the teal violins in Figure 9 (left); training for longer (either with fresh data, or for more epochs on the same data) reduces the fraction of unlucky error-prone outliers. Recall that extrapolation is possible without such favorable coverage, via using a recurrent model.
(R5) Resource scaling (in-distribution data, training steps, network size) helps. Training more data from the same distribution, as well as for more steps on the same examples, both improve sparse-sequence performance, the expense of dense-sequence performance (blue violins in Figure 9 (left). As best seen through Figure D (right), there is no discernible monotonic relationship between any of the Transformer's ss standard architecture size parameters (i.e. number of layers, embedding dimension, and number of parallel self-attention heads per layer) and extrapolative performance (navy violins).
B.4 Indirect algorithmic controls for extrapolation (Section 5.2
As shown in Figure in the main paper, various architectural, algorithmic and regularization choices can help improve error rates compared to the baseline Transformer. The various settings of weight decay, aattettinn, MLP, embedding) dropout, position embedding, activation function, attention- sharpening penalty are all found in Figures TO and
Details for architecture variants. There is no clear consensus the advantages and drawbacks of various positional encodings, but has been known Dai et al. (2019) that the choice of positional symmetry-breakiee scheme modulates long-sequence performance natural tasks. We evaluate
25

---

Regularizer effects o.o.d. performance
10
#L/00.9 (8) erer
10
10
10-1
10-4
10-4
+0
10:3
#L.00111 enoor
10
10
10-4
10-3
10-4
GL BH 512d (base)
decay D
decay 0.03
wi. diecay 0.03
decay decay
attn drapout 0.05
attn dropour t. 15
aitn atin dropout 0.2
attn drgpoit
atn dropeit
mip drapout 0.
mip diopout 0.1
mip mip dropaut 0.2
drapout 0.15
mip dropout
mip dropoit 0.4.
emb drapout 05
emt d dropout 1.15
dropon 0.1.
dropout 0
am doreen O
code D
copeact US
corree 0.55
and dropsutt D. Ponnee
mne droginut
0.65
diepen
emb amb and come
and mmm de aui
Figure 10: Detailed comparisons of standard regularizers (weight decay, and 3 forms of dropout). While some regularizer choices reduce rare-sequence enror rates (in particular, large embedding dropout reduces sparse-sequence errors by 2 orders of magnitude), nothing eliminates the glitches entirely.
Architecture attertion-sharraninn effects on o.od. performance
10-4
2
10-1
10-4.
10-1
10-4
10-1
m) ener
10
10-1
10
GL 52r (taze)
dineciif PE
Rope
ne
Ac
oomo
deeuu
swiurr
we alm shar
L usep
wex meep
aiuutode drop
75 1olp
TBI eutrope sharp
Figure 11: Detailed comparisons of selection of architectural changes, attention-share sharpennig losses, and combinations indirect algorithmic controls. Our best runs come from jointly tuning these interventions, including an annealing schedule for the attention sharpennhaagggggg loss; however, even the best models have nonzero glitch rates. Figure B provides an exhaustive view of these results.
26

---

Strat fied beseline line model
0.35
10
0030
0.23
2000
0015
10
10
10-1
10-
0.000
10-9
4t Lite
nei sp
gpoted
de synted
oymsoo
Depondency kegg)
Hemp
Figure 12: Supplementary plots. Left: Additional comparisons: modifying the softmax temperature
inside the attention heads (multiplying the attention alignment scores by 1/3), and generalizations of the FFLM task to larger vocabularies (i.e. the "data" tokens are uniformly drawn from {0, 1,.... 1}). In the rightmost violin, "2*2" refers to token space consisting of length-2 bitstrings. In all of these settings, attention glitches remain (and mostly worsen). Right: Distribution of dependency lengths (number ignore operations since last read write operation) of wrong answers the union of the o.o.d. test sets, for a canonical baseline model. This serves as a quick check that the errors are diverse.
various choices which appear and RoPE (Su et al., 2021). We also try the zero positional encoding (which breaks symmetry via the causal attention mask; see Haviv et al. (2022). We find that non-trainable position encodings help on dense sequences (FFL(..1)), but have no clear benefit on sparse ones (FFL(0.98)) (8)) which require more handling of long-term dependency. We also try the gated activation units considered by (Shazeer, 2020).
LLMs: sinusoidal, Icarned, ALiBi (Press al.) 202T).
Details for attention sharpening. There are many possible choices of continuous regularization terms which can promote sparsity in an attention head's weights- we consider entropy, negative L2 loss, and negative Loe loss. These terms are averaged across every attention head in the Transformer, and added as surrogate objective during training. We perform large grid sweep over coefficients {0.01, 0.03. ..., 0.1, 0.3, 1, 10, 30), annealing schedules (linear and oscillating, starting from 2000, and 5000 steps), and display in Figure II the 3 choices which appear on the Pareto front.
Optimizer hyperparameters. We also varied the optimizer parameters for AdamW (9, (0.85, 0.9, 0.95), 32 E (0.95, 0.99, 0.999), learning rate E {0.0001, 0.0003, 0.001, 0.003)) and found significant improvements extrapolation performance.
We restate the main findings:
(R6) Many algorithmic choices influence extrapolative behavior. We sweep over various forms of implicit and explicit regularizers; see Figures 10 and 11 Details are provided below.
(R7) Despite many partial mitigations, nothing eliminates attention glitches entirely. Refer to the scatter plot in Figure 4 (left) for a visualization of every training run.
Figure 12 provides few supplementary experiments, verifying that attention glitches persist: scaling the attention softmax temperature, and larger vocabularies for the memory register. We also provide quick verification that errors are not concentrated at the same dependency lengths (i.e. distances between write and read).
Finally, to provide a bird bird's-eye view of all of our experiments, Figure 13 provides a seatter plot of o.o.d. error rates for all models trained in this paper, color coded by intervention category.
B.5 Preliminary mechanistic study and challenges (Section 5.3
We continue the discussions Section 5x3 and provide preliminary mechanistic interpretability results simulating the flip-flp automaton (Definition Recall the main takeaway:
27

---

Errors by
187
Extrapolation FFL(0.8)
100
basalinc
10
Scalc data/compute
12-
12-0
=22
10-1
10'
optimbzer
62
0.0.A bask WEFOP on FFUJO (83 (xpatie
13-4
10-1
-00
12-
10
10-1
10-1
101
FFLI0.95) (..09)
reguirization
architectrre
12-1
10-1
boodir Tarobamee
locehre melion
catalcamoure
13
10
12-4
10-7
30-
arch Starpon
eln Sturpoiing
3tth sharpening
10r
arch reg sharpon
10-1
10-1
12-4
10-4
10-1
20-0
10
0.0.d. tast errer on FFLJ0.11 Idense tail
FFL
Figure 13: Error scatter plots for all models evaluated in this work (a larger version of Tigure from the main paper), color-coded by intervention category. Left: All runs on the same plot. Right: Segmented by intervention type. The best runs result from an exhaustive joint hyperparameter search over dropout, position embeddings, and annealed attention-shara sharionnnnaarnnnnnggg regularizers.
(R8) Attention-sharpening regularizers successfully promote hard attention, but errors persist.
Sparsity regularization helps sharpen the attention. Figures 16a and [16ppcomprr the attention patterns of I-layer 1 1-head models with or without attention sharpennhaggggggg regularization. While both types of models give correct results, the attention attention-sharpened model puts all attention weights to the most recently write position, which is the solution given according to the definition of the task, whereas the attention patterns of the non-regularized model (Figure T6a are much less clean.
Are there solutions other than the "ideal" solution? There is solution naturally associated with the definition of the flip-flop automaton (i.e. the sparse pattern shown in Figure 16b), but is necessarily the only solution. For example, an equally valid (dense) solution is for the model to attend every write token of the correct type.
Are attention patterns reliable for interpretability? Prior work has pointed out the limitations of interpretations based solely on attention patterns (Jain and Wallace 2019 Bolukbasi et al. 2021 Wen et al., 2023). The intuition is that attention patterns can interact with other components of the network in various ways; for example, Wv project out certain dimensions have contributed to a large attention score. Hence, for multi-layer multi-head non-sparse models, the magnitude of attention weights may not have intuitive interpretation of "importance" (Meister et al. 2021). This is observed in our experiments as well; for instance, Figure [7 shows examples where the attention on incorrect token may higher than that of the correct token. However, in a 1- lllayer -hhad model, 1-sparse attention (Figure 16b) indeed offers interpretability. since if zero
though they may
17 However, we consider the "importance influence" as measured by the norms the attention attentio-weeihhted value vectors, then the max norm still corresponds to the correct token, which helps explain why the final output is correct.
28

---

Figure 14: Attention drifts as the length increases. The model is trained on length-500 sequences
with p(ar * 0.5. The testing sequences are (a) [2, 0.... and (b) [1, ..... 2, ....... 0 We
800
sample every 32 positions for visualization.
attention weight 18
necessarily means the absence of dependency, which greatly reduces the set of possible solutions implemented.
Sporadic errors persist. Section Section 5.1 (R5) showed that none of the mitigations was suc- cessful at making Transformers reach 100% accuracy. One common failure mode is long-range dependency, where the input sequences contain very few writes. The failure could be attributed to multiple factors; we will explore one aspect related attention patterns, demonstrated with a 1-layer 1 1-head Transformers with linear position encoding,
length-834 sequence with 2 writes. As shown in Figure [4] the attentions for positions early in the sequence correctly attend to the most recent write. However, attention starts to "drift" as we move to later positions, and the positions at the end the sequence attend entirely to the recent read tokens, which contains no information for solving the task. This may be because the attention weights undesirably affected by the position encodings, as discussed in Proposition
19
Optimization hurdles. While sparse solutions may be preferred for various reasons, sparsity itself is not sufficient to guarantee good performance: As shown in Figure [6d] sparsity regularization can lead to bad local minima, where the model tends to (incorrectly) rely on earlier positions. This is observed across different types of sparsity regularization. While we do not yet have a full explanation of the phenomenon, possible explanation for this bias that earlier positions show up more often during training, due to the use of the causal attention: valid flip-flop solution is for the model to attend to every write token the correct type; positions earlier in the sequence get observed in more subsequences because of the causal mask, and are hence more likely to be attended to. We also observe that the phenomenon seems be closely related to the training distribution. For example, the model is much more likely to get stuck at bad local minima when p = 0.5 (denser sequences) compared to p(L) 0.9 (sparse sequences). We leave a more thorough study on the training dynamics (Jelassi et al. 2022 Li al. 2023 Ahn et al. 2023) for future work.
Effect of sparsity regularization on training dynamics An interesting future direction to understand the learning dynamics of flip-flop tasks with attention-sharpenigg regularization, as suggested by the (quantitively and qualitatively) different results and optimization challenges. As some initial empirical evidence that the regularization indeed have a large impact the dynamics, found that sharpened attention seems to have a regularization effect on the weight norms (Figure T5) and also lead different behaviors of the attention heads (Figure [8]
18 By "zero" we mean an attention score on the magnitude 1c-8 empirically. The attention weights that the most recent write sum up around 1e-7.

---

non-regularized
attention-sharpened attention-sharpened from epoch
attention c_attn
230
200
Stop
Step
20
40
8b
20
40
50
80
attention c_proj
MLP c_proj
6
5
4
40 60 50op
3
Step
20 40
80
Figure 15: Frobenius norms of weight matrices in 1-layer 1-head models, trained without regulariza- tion (blue), with attention-sharpening regularization (yellow), first without regularization and then adding regularization from epoch 30 (red; epoch 30 marked by the dashed lines). The solid curve and the shadow shows the median and the standard deviation calculated on 8 models.
6: Og
0g
00
de Oo
de
Og
(a)
(c)
Figure 16: Attention-sharpeningg regularization on 1-layer 1-head models. Compared to non- regularized model (16a), the sparsity-regularized model (16b) shows clear attention at the last write position. However, sparse attention does not have to align with the "ideal" pattern (T6c), and can even be wrong (I6d). Positions with yellow borders are where the max attention in each row occur; errors marked in red.
More examples of attention patterns Figure 19 shows the full set of attention patterns of two 6-layer 8-head models trained with and without siictiio-sharpening regularization, corresponding to Figure 5) (a.b). Attention-sharpening regularization can be applied in different ways; for example, Figure 20 shows results of a model for which only the first layer is regularized. The attention patterns of subsequent layers remain sharp, even though there is no explicit regularization.
6
1 0g 6
0
Non-sparse atten- tion pattern can be misleading: non-sparse model may put more attention on an incorrect token (i.e. token that is not the write with the right type), while making the correct pre- dictions. Yellow boxes mark the position of the max atten- tion each row.
Figure 17:
30

---

14
14
(a) Model trained without sparsity regularization.
22
60
(b) Model trained with entropy sparsity regularization with X = 0.01.
Figure 18: Examples of the l difference attention patterns from two 6-layer 8-head 512-dimension
models. Differences are calculated between all pairs of heads in the same layer.
(a) Without regularization.
(b) With attention attention-sharpening sharpening regularization.
Figure 19: Attention patterns for 6-layer 8-head 512-dimension models on the input sequence [o1, Li o. 1, Jo, Ti, L]: attention attention-sharpening regularization lead to cleaner attention patterns. 1 attention head in the first layer of the regularized model (marked by the purple box) matches the "ideal" attention pattern Figure 5c
31

---

L3
LA
82
(a) la differences between pairs of attention heads in the same layer, throughout training (x-axis).
(b) Attention patterns on the input sequence 01.1,00 0o. L, -, o L..
Figure 20: Attention heads and attention patterns for a 6-layer 8-head 512-dimension model, trained with attention-sharpeningg regularization (entropy regularization with strength 0.01) on the first layer only. attention head in the first layer (marked by the purple box) matches the "ideal" attention pattern Figure 5c
B.6 Software, compute infrastructure, and resource costs
GPU-accelerated training and evaluation pipelines were implemented in PyTorch Paszke et al. (017)) For the FFLM experiments, used the x-transformers" iiplemennations of the Transformer architecture and variants. For the fine-grained mechanistic interpretability experiments on the pure flip-flops, used the "vanilla, GPT-2"-like Transformer implementation published by HuggingFace (Wolf et al. 2019), Our benchmarks have been released at htttps://huggingtt Bynthseq/ flipflop
Each training run was performed on one GPU in an internal cluster, with NVIDIA P40, P100, V100, and RTX A6000 GPUs, with least 16GB of VRAM. Each (6-layer, 312-dimensional, 8 8-head) baseline model took ~ 10 minutes to train (and evaluate online) for 10 steps. A nontrivial fraction fine-graing evaluation through the course of training. The vast majority of training runs are close to these specifications; consequently, one set of replicates under identical conditions (i.e. each violin plot in each figure) is the product of ~4 GPU-hours of training time.
of the compute time (~ 20%) was spent
We hope that this computational investment will aid in understanding how to build robust Transformer models and training pipelines at much larger seales.
C Proofs for Section 4.1
A Transformer (Vaswani et al. (0177) consists of multiple self-attention layers. Given d-dimensional embeddings of length-7 sequence, denoted as X RTxx self-attention layer o computes
Transformer recap.
f(X) o( WwWWsoftmaxxwWWaa....
X XWv Wc).
(C.1)
where Wo. WK E Raxx for S d are the query and key matrix; Wv, W E Rdx project the representations from and back to IRd. softmax calculates row-wise softmax. Φ Rdd - Rd is a 2-layer fully-connected network. Residual links and layer norm can be optionally included at different places of self-attention layer.
C.1 Realizability of FFL by small Transformers
Proposition 2. 2-layer I-head Transformer with residual connections can represent "deterministic" FFL.
32

---

Proof. Let us consider predicting in the deterministic mode (Section 3.1 Then we need to predict It-1 given I1:t with 2; r. In order to do this, we need to find the largest
such that z, w
and output #1+1- There are multiple ways to implement this, we will consider the following: (1) layer converts FRL to the flip-flop automaton (Definition T). (2) layer 2 implements the flip-flop
construction. For layer 2, we can use the construction described in Liu et al. (2023). Here we present the full construction for completeness.
We will consider a two-layer Transformer with one head in each layer followed by a 2-layer MLP and a residual connection. In particular, for x E {w, 1,,,0,
f(x) Φ2 W (2) (o 2 w (2)
(f())) 2 w
where (x) = E(x) + th (W (1) soltmax(B(() D T
BW w
K
where ((x) E RX' is the encoding for the input sequence x given some encoding function E.
Our construction is as follows:
Select d = 7, = 2, =1 (recall from Equation hhtt d, k are the dimensions of Wo. WK). Among the d = 7 embedding dimension, two dimensions are for the operations (w versus r, i), two for the two write values, one for the positional embedding, one for padding, and the final dimension is for storing whether the previous position is the most recent write, as calculated by the first layer.
Select input symbol encodings such that for the token at position 6, denoted as It.
E(x)) := 1[x; = w|e1 + [ = r V = ile2 + [zz = 0je3 + 1 = 1]eı + + + P, E.ERR ER,
where P. is the positional encoding. We use the linear positional encoding P; == (1/C) c6, for some (large) constant C. For fixed sequence length T,
set C = T.
w(O)
65
E
RTx2
w
30
066
Tx2 for c == 0(T log())) w
e1
0
E
7x2
and
W
(1)T
e7
0
E 7x2
W (2)
E 7x2
W
(2)
E Tx2 for c = O(T w
=
es e5
=
ee7
ce6
e4 0
E
Tx2
and W
ei
0
E
7x2
In layer 1, the unnormalized attention score for query position i to key position is
(WO)
K ( 33
c 1,, x]. J [1, (1,11 T
3
3
1|r = w] +1))
Te
T
Note that the max attention value for position i is achieved at if x;-1 1 * w. else the max is achieved at position i- --1 1.
In the setting of hard attention, the output for the in token after the attention module is [[x;-1 M V x; = w/e7. Now similar to the constructions in Liu et al. (2023) (Lemma 6), with a appropriate choice of ( log T), we can approximate hard attention by soft attention, and subsequently use the MLP to round the coordinate corresponding to e7. The MLP otherwise serves as the identity function. Together with the residual link, the first layer output (i.e. the second layer input) at position i takes the form
(Ix)) E(v.)) [x;-1 x; xje7. In layer 2, the unnormalized attention score computed for position i attending to j is
W fi(x)), w S((15)
[1,1];
j 1 w) T
T
j [[ u] + T
=c.
33

---

Note that the max attention value is achieved at the position right after the closest w to T;. Let us denote this position by f then with hard attention, the output at the ish position is 2,61, as desired. Now similar to before, we can approximate this with soft attention and use the MLP to do the appropriate rounding to get our final construction.
The construction in Proposition 2 is a construction, but it is not the only construction. For example, for the second layer implementation for the flip-flop automaton, there could be an equally valid dense solution, where the model uniformly attends to all write tokens of the correct type.
Remark:
C.2 Failure of soft attention: attention dilution with bounded Lipschitzness
Consider any attention layer with weight matrices Wo. WK E R If [[ Welle is bounded, then the attention cannot be sparse as the sequence length increases:
Proposition 3 (Leaky soft attention). Assume the latent variables have bounded norm, i.e. || S 1 for any latent vector v E Rd, and let m denote the max singular value of W Wo. Then for T ((exp(20 max)), any sequences of latent vectors {Ur}re(T). ||softmax( (softmax(Fxx)rees (rr)re(())l
12(1).
Proof.
The proof follows directly from simple rewriting.
For any u with ||u]|,, ||ol|a < 1, the pre-softmax attention score is bounded by u W Wov
(-Omaxs mmax).
exp(v, W Wour)
exp (mmax)
T
=
ErERy exp(e, W Wqur) exp(Omaxx + (T' exp((Omax) mmax)
T- + exp max)
where the last term is (2(1) when T = ((exp(2o)).
Attention dilution and failure on dense sequences Strictly speaking, attention dilution caused by an increased sequence length does not necessarily affect the output of the layer. For example, if ignore gets mapped to a subspace orthogonal to that of write, then Wv can project out the ignore subspace, making the weighted averaged depending only on the number of writes. Hence with the presence of layer norm, attention dilution won't be a problem for the final prediction if the number of write is upper bounded regardless of the sequence length.
For the experiments in Section 5.1 denser sequences (i.e. larger p(write)) do increase the number of write compared to the training distribution, hence attention dilution can be a potential cause for the decrease in performance.
C.3 Failure of hard attention: bad margin for positional embeddings
In this section, we look at failure mode that I-layer 1-head Transformer has on the flip-flop automaton simulation task. Why do we care about this setup? Simulating the automaton is in fact a sub-task of FFLM. For example, the second layer of the construction in Proposition Propositionn/reduces. simulation task.
the
Consider a I-layer 1-head Transformer with parameters Wq, Wx E R Write the attention query matrix Wq Wq [WQ.. Worl. where WQe (d-1) corresponds to the embedding dimensions, and Wo corresponds to the dimension for the linear positional encoding. Write WK = WKee Wxpl similarly.
Then, we claim that the following must be true, regardless of the choice of the token embedding:
Proposition 4. Consider linear positional encoding, i.e. Pt = i/C' for some (large) constant C. Then, perfect length generalization to arbitrary length requires W WKp 0.
Proof. Let e+)) E Rd-1 denote the embedding vector (without the position encoding) for token i E 2,. Let v. [er. E Idd denote the embedding for the 4 token, where e, (e("), e((), el2) 3Rd is the embedding of the token itself, and Pt = i/C the linear positional encoding.
el2)
34

---

Let 8i-1 denote the pre-softmax attention score that the inh token puts on the juh token, which is given by
Si-j (WQu, WKUj)
(C.2)
=c Wq WKee e. W WKp
Ps + +(,))
" WK Wop Ps + W
WKp PiPj
(C.3)
e, W Q: Wkp
jt (e,)_Kka Wer
W
WKP
kp
=e WQe Wxee+ +
ij.
(C.4)
C
will prove the proposition in two cases, which respectively require W W WK
WKp Qp
and
Qp Kp 2 O.
Case W WKp I 0 required Consider the case of long-term dependency, where the input sequence consists of an initial write and a series of reads, i.c. and og for t >> 1. Then for the Tea position, the score for the first write token is
8T (WQUT, WKU1)
(C.5)
+ e(0) W Qo
WKO.
(e(1) WKe Ke Woe W WKP
=0 Wo w
T +
(C.6)
C
C
C
(e(1)) -(ee") WKe Wap
W WKp
-T+01)= = O(T),
(C.7)
C
C
and the score for the last write token
ST (WQUT, WKUT)
(C.8)
0) T
Wo W..W (o)
e
W
Qc
WKP
W
KPTT
T
e00)
WKoWon
T
W WKp Kp
T
(C.9)
C
C
C
Wi Wx T T
(C.10)
C
Think of C as going infinity. If W W
ST-- > ST-11- Hence we need W Op Kp 0, then there exists sufficiently large 7 such that
Qp WKp I 0.
Case 2: WT WKp 2 0 required Consider the input sequence where σ1 = = or-1 = 2, and 0: 0 for & E [T] 11,-11 1}. Similar to the above, calculate the pre-softmax attention scores for 01,0T-18 as
8T -TT)
(C.11)
WT WKP Or C
ST-T-1
T2 + OTT).
(C.12)
Since we need ST-T-1 ST must be that WT
WKp Kp 2 0.
Qp
35


Reviews:
[{"review_id": "iwx4Kq4Bb0", "reviewer": "Reviewer_ZZvs", "summary": "This paper presents a paradigm for diagnosing one cause of closed-domain (intrinsic) hallucinations in large language models (LLMs) and presents its analysis results.\n\nTo understand why LLMs can be factually inaccurate or prone to erroneous reasoning, the authors proposed a flip-flop language model (FFLM) task designed to verify behavior during extrapolation. By controlling the probability of ignoring behavior, the FFLM can generate sequences with both dense-and-short and sparse-and-long dependencies. \nThis allows us to observe changes ofTransformer's learning outcomes and behavior between these sequences. \n\nThe analysis revealed that occasional, long-tail inference failures cause errors, and currently, their occurrence cannot be predicted. Some of the effects can be mitigated with regularization, but they cannot be completely eliminated. \n\nThe main claims are as follows:\n\n- Proposing the flip-flop language modeling task. This task is designed to probe issues during the inference of long sequences easily.\n- Transformers can learn flip-flop language, but regardless of dependency length, they occasionally cause long-tail errors. \n- To mitigate this attention glitch, several regularization techniques are verified. No method can resolve the problem entirely, though each technique has a certain effect. \n\n### after rebuttal\nI increased my score from 5 to 6 based on the explanations provided in the feedback. ", "questions": "\nThis is just a simple idea: Consider a unit with more memory bits. Would it be possible to create a unit that defines the ignore probability for each bit independently? \nIs it possible that a multi-head attention can learn FFLM (with more bits) efficiently, by aligning the number of bits and heads?", "limitations": "Well discussed in the manuscript. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "- Proposal of FFLM, a controllable long-range dependency resolution task, under a simple task setting. The adjustability of the dependency range by the ignore action's probability is easy to understand.\n- According to the authors, this is the first attempt to attribute model hallucinations to a systematic architectural flaw in the Transformers.\n- Presenting various experimental results and possible explanations from many aspects. Unfortunately, none in this report are definitive causes and/or solutions (most are denied by exceptions), but they can be utilized as one of the initial investigation items in the analysis of natural language LM's hallucination.\n- It's interesting that LSTMs and 1-layer single Transformers can solve some issues, but multi-layer LSTMs are not good at the issues. This suggests the necessity of architectural innovations beyond just stacking self-attention layers.", "weaknesses": "- While the paper presents several interesting results to the readers, currently, the manuscript does not provide a clear guideline on what steps should be taken to counteract hallucinations in natural language LLMs. The impression I get from the current manuscript is that 'our current knowledge does not pinpoint the cause of hallucinations in natural language LLMs'.\"\n\n- I found it interesting that LSTMs and 1-layer single Transformers sometimes performs better than the multi-layer LSTM. Why does this happen? I believe there must be important implications, so if I have overlooked the explanation, please point it out in the review answers. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the thoughtful comments and great questions! We are glad that the reviewer finds it interesting that FFLM exposes the failure of multi-layer Transformers when smaller architectures can perform better, and hope to address the concerns below.\n\n**Why LSTM / smaller Transformers perform better**\n\nThere might be some typos in the reviewer’s original question, and we would like to make sure our understanding is correct: we interpret the question as: “why can 1-layer LSTM and 2-layer Transformers perform better than multi-layer Transformers?”\nRepresentationally, both 1-layer LSTM and 2-layer Transformers are minimally sufficient to solve the task. Comparing these two, we hypothesize that the LSTM has a recurrent inductive bias that is more suitable for the FFLM task, which is consistent with prior works aiming to solve some reasoning tasks via 'recurrent prompting' [1,2,3] or by introducing recurrence into the architecture directly [4,5,6].\nComparing 2-layer and multi-layer Transformers, the latter performs worse likely due to the redundancy in the architecture, which allows more solutions that are consistent with the training samples but can have more unexpected behaviors on unseen samples. \n\n**This is a comprehensive negative result paper**\n\nWhile Section 5 documents a wide selection of algorithmic interventions that can quell the attention glitch pathology by orders of magnitude, it is true that we do not provide a solution on par with data diversity or the recurrent network. The goal of this paper is to highlight one specific kind of hallucination, and to emphasize that this is particular to the Transformer, regardless of its scale or specific architecture; recurrent predecessors have no such shortcoming. \n\nFFLM offers a precise probing mechanism for benchmarking progress on hallucinations of this kind, and further, helps to identify one concrete, disambiguated cause of the general LLM hallucination problem. We believe that advancing language models requires both thorough experimentation that identifies specific, classifiable kinds of hallucinations and honed tools like FFLM to study them closely — our work makes these contributions.\n\n**Generalizations beyond 1-bit memory.**\n\nThere are several ways to generalize the FFLM, as we discussed in Appendix A.4. Below are some options most related to generalizing the memory:\n- Keeping the instruction set to be the same, and using a larger set of values. For example, two isomorphic ways to write a sequence could be “$w\\ 3\\ i\\ 2\\ i\\ 1\\ r\\ 3$” (“4 symbols”) and “$w\\ 1\\ 1\\ i\\ 1\\ 0\\ i\\ 0\\ 1\\ r\\ 1\\ 1$” (“2*2 symbols”). Figure 2 in the global rebuttal attachment shows that errors persist (and, in fact, both long- and short-range error rates worsen) with increasing vocabulary size.\n- Keeping the set of values to be the same, and using a larger instruction set: for example, when there are 2 memory units (indexed as 0 and 1), a sequence could be “$w_0\\ 0 \\ w_1\\ 1\\ r_1\\ 1\\ r_0\\ 0$” where $w_i$ ($r_i$) refers to write at (read from) memory bit $i$. This has more flexibility in the probability hyperparameters and can be solved using a construction similar to the one given in Proposition 2, but extended to using more heads. This is analogous to interleaving multiple FFLM tasks and slightly tangential to our current investigation, and we are happy to include more results in the camera-ready.\n\n**References**\n\n[1] Maxwell Nye et al. Show Your Work: Scratchpads for Intermediate Computation with Language Models.\n\n[2] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, Denny Zhou. Chain-of-Thought Prompting Elicits Reasoning in Large Language Models.\n\n[3] Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, Cyril Zhang. Transformers Learn Shortcuts to Automata.\n\n[4] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, François Fleuret. Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention.\n\n[5] Daniel Y. Fu, Tri Dao, Khaled K. Saab, Armin W. Thomas, Atri Rudra, Christopher Ré. Hungry Hungry Hippos: Towards Language Modeling with State Space Models.\n\n[6] Bo Peng et al. RWKV: Reinventing RNNs for the Transformer Era.\n"}, {"review_id": "JKo0g1u7CI", "reviewer": "Reviewer_FpxV", "summary": "This paper introduces Flip-Flop Language Modeling (FFLM), a synthetic benchmark designed to evaluate language model's (LMs) ability to perform operations on a single-bit of memory. LMs are evaluated on their ability to generalize to out-of-distribution (OOD) sequences. The training setups are varied along several axes including hyperparameters (random seed, training steps, weight decay, dropout), architectural changes (number of layers, hard vs. soft attention, positional encodings), and dataset properties (additional OOD data). In all cases, the LMs produce attention glitches, i.e., they exhibit errors in their reasoning. In contrast, an LSTM generalizes perfectly. The authors provide preliminary hypotheses explaining the failure modes.", "questions": "Questions:\n1. Were there any other hypotheses explored in Section 4.1? It would be nice to have a more careful enumeration (perhaps by category) of the possible hypotheses driving the lack of OOD generalization. Moreover, one of the proposed mechanisms is already present in previous work. \n\nTypos:\n1. Line 867: \"the regularization indeed have\" --> \"the regularization indeed has\"", "limitations": "Although there appears to be a limitations section in Appendix A.4, I think it would be appropriate to more clearly note in the main body that this work does not posit a full list of possible mechanisms driving poor performance on FFLM nor will solving performance on FFLM constitute a transformer with robust reasoning.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "*Originality:* although synthetic benchmarks have been often studied in NLP, FFLM focuses on the smallest reasoning capability (memory on a single bit), reducing confounding factors driving mistakes.\n\n*Quality:* the experiments are comprehensive and cover most of the \"standard\" training and architectural tricks. Moreover, the FFLM benchmark is well-designed and is appropriately justified as a benchmark. These two factors lead to a useful analysis of current limitations of LMs. \n\n*Clarity:* the paper is well-written and figures + captions are self-explanatory\n\n*Significance:* understanding reasoning errors in LMs is a crucial step towards improving their reliability and thus future deployment in real-world systems. Moreover, this work provides a minimal benchmark with which to evaluate any proposed architectural changes to LMs. ", "weaknesses": "The main weakness with the work is a lack of actionable insights. Although several mechanistic hypotheses are proposed as to explaining the behavior behind the benchmark, they are not adequately explored nor clearly organized. This leads to the following concerns: \n\n**Evaluation concerns:**\n\n* *Lack of experiments studying whether the proposed hypotheses in Section 4.1 actually drive the errors examined.* I appreciate the compilation of possible hypotheses explaining the LM errors. However, there don't appear to be experiments attempting to falsify these hypotheses? For example, one could examine whether the LMs do indeed only attend to the previous $n$-tokens.\n\n**Clarity concerns:**\n* *Does not emphasize the benchmark properties of FFLM.* Although the authors defined success on FFLM as achieving 100% performance accuracy, if people are to evaluate their architectural innovations on FFLM, it would be helpful to have a more continuous notion of progress (rather than solved vs. unsolved). Possible suggestions include: \n    * Defining a notion of difficultly of generalization. E.g., FFL(0.1) is harder than FFL(0.2) given training data from FFL(0.98). Perhaps one could introduce an easy and hard test set.\n    * Classifying severity of failures. Is there perhaps some metric that would estimate how close the LM attention patterns match either the ideal solution or any other possible solution? Intuitively, there should be some distinction between the attention weights of a randomly-initialized network and the attention weights of a trained model with error (Figure 5d). Perhaps one metric could be the proportion of attention weight placed on all the previously encountered write tokens vs. on all other tokens\n\n* *Should have a clearer list of future directions.* I think it would help guide future work if there was a compiled list of actionable experiments and / or hypotheses to test that were provided in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your thoughtful comments! We are glad that you found findings from our minimally sufficient FFLM task to be original and significant. There were some great points raised in the review, which we’d like to address below.\n\n**Providing a list of actionable future directions**:\n\nThank you for the great suggestion! Here are our current thoughts:\n- *Learning from synthetic setups*: Our results show that simple synthetic setups can serve as clean, controllable sandboxes for isolating and analyzing various mechanisms in the architecture. Designing benchmarks or probing tasks like FFLM could help better understand Transformer’s capabilities and limitations.\n- *FFLM extensions and connecting to natural languages*: An obvious limitation of a synthetic setup is its gap to the real-world settings. One direction is to study whether and how findings can transfer to real-world setups; as an example, please see our response [A1] to Review 4Fu7 regarding the effect of data. Another direction is to expand the synthetic setup to narrow the gap to natural languages, for which we provided several directions in Section A.4, such as incorporating more complex selection criteria and expanded notion of ground truth.\n- *More error analyses and (mechanistic) understanding*: While our paper provides explanations of two failure modes and some preliminary mechanistic study, a more comprehensive understanding of Transformer’s internal mechanism can be helpful. In contrast to single-component analyses in our work, such understanding under natural languages setups can be much more challenging and nuanced; for example, please see our discussion “Submodules” in Section A.4.\n- *Better metrics*: as the reviewer pointed out, a continuous notion of progress can be much more informative than a binary answer or accuracy. One direction is to take inspiration from works on hidden progress throughout training, such as Barak et al. 22, Nanda et al. 23.\n- *Architectural innovations*: Attention glitches is essentially a problem with the architecture: Transformer fails at FFLM, while LSTM succeeds easily. Therefore, architectural innovations are likely a necessary part of the fix. As discussed in Section 6, one idea is to integrate the recurrent inductive bias into the Transformer architecture, which several prior works have shown promising results [Katharopoulos et al. 2020, Dao et al. 2022, Peng et al. 2023].\n\n\n**Better understanding the task and the failures**\n\nAs the reviewer correctly noted, the success metric of our proposed task is to process FFLM perfectly, which can be practically thought of as performing as well as recurrent networks (LSTMs). A continuous progress measure could be the accuracy, and it is a great question to find other metrics that could serve as more informative progress measures; please see the list of future directions above. Comparing attention weights is an interesting idea that is worth trying, though our current guess would be that it might not be directly helpful, since various prior work has shown that attention patterns can be misleading as discussed in Footnote 7 and Appendix B.5.\n\nTo better highlight the effects of various mitigation methods on the errors, we added Figure 1 in the global response PDF, which shows that each type of methods may be helpful for improving the OOD error on either the denser sequences or the sparser sequences, but no method was able to improve both simultaneously.\n\n\n**Hypothesis driving lack of OOD performance**\n\nWe explored several potential hypotheses that lead to poor OOD performance (not explicitly organized in Section 4.1). Let us reiterate them here organized by the different aspects of the training pipeline:\n- (Architecture) _H1: Small Transformers are not capable of representing the FFLM language perfectly_. We refuted this by showing a theoretical construction of a 2-layer (low parameter count & low-norm) Transformer that realizes FFLM with 100% accuracy. \n- (Architecture) _H2: Soft attention can lead to dilution_. We supported this hypothesis by showing that attention sharpening indeed improves generalization across sparse sequences.\n- (Architecture) _H3: Transformers can only focus on the recent $n$ tokens_: We show that this explanation is insufficient since the model makes errors even on dense sequences.\n- (Data) _H4: OOD generalization requires coverage of tails_. We support this by showing that adding sparse and dense examples improves OOD performance. \n- (Optimization) _H5: Bad local minima exist_. We support this in our interpretability studies by showing that even after enforcing hard attention, the optimization can find solutions that confidently choose the wrong argmax on certain sequences.\n\nNote that none of the hypotheses fully explains all the failure modes we observe in our experimentation, which helps highlight the challenge of explaining OOD failures using simple mechanisms. Towards developing an end-to-end explanation, we would need to incorporate the interplay between different attention heads in each layer and across different layers, and the impact of optimization on the in-distribution loss on the OOD loss, which is highly non-trivial.\n\nThank you also for the suggestions on clarifying the limitations of setup and for correcting the typo; we will update the camera ready version accordingly.\n"}, {"review_id": "wBBymLbaO6", "reviewer": "Reviewer_vbMc", "summary": "This work studies the phenomenon of \"attention glitches\" in LLMs. Attention glitches are instances where an LLM's attention mechanism fails to capture long-range dependencies, resulting in factual inaccuracies or erroneous reasoning. The authors introduce a new synthetic benchmark called flip-flop language modeling (FFLM) to probe the extrapolative behavior of LLMs. FFLM is a simple generative task that requires an LLM to copy binary symbols over long-range dependencies, ignoring the tokens in between. The authors find that Transformer Transformer-based FFLMs suffer from a long tail of sporadic reasoning errors, even when the task is relatively simple.", "questions": "- The paper showed that 1-layer LSTM works perfectly for FF while transformers are not. However, it is unclear to me whether that is due to an effect of overfitting (to the distribution of training data). Could authors elaborate more on this? \n- \"We hypothesize that attention glitches occur in the internal algorithmic representations of Transformer models of natural language, and that they account for (a non-negligible portion of) the reasoning errors encountered in practice. \" Is there a way to validate the hypothesis?\n- It would be great if the authors can release the code to reproduce the results.", "limitations": "- It should be made clear that the full experiments and analysis are based on synthetic setting.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The paper studies a critical problem on attention glitches for transformer-based models. It can potentially have a huge impact on the community.\n- The synthetic FFLM benchmark can be useful to study long-range dependency in a controllable way.\n- The findings/research questions provide more insights on the issue.", "weaknesses": "- The paper discussed and aimed at drawing a connection between hallucination and long-range dependency, however, there is no further discussion on how these two terms interact with each other.\n- While it is understandable that the paper studied the behavior of attention glitches, there is no proposed path to fix the issue which limits the contribution of this work. \n- The setting is fully synthetic. It is unclear how any findings can be transferred into realistic and more complex tasks.\n- Some experimental settings that are critical to the conclusion are unclear, e.g., dataset construction and sequence lengths, tokenizer choice, etc.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful review! We are glad that you find the attention glitches phenomenon to be a critical problem that is worth studying, and hope to address your concerns below.\n\nFor the first three concerns in Weakness, please refer to the global response:\n- **[W1] Hallucination vs long-term dependency?** Please see [G1] in our global response.\n- **[W2] Is there a clear fix?** Please refer to [G3] in our global response.\n- **[W3] how do insights transfer to more complex / real-world setups?** Please refer to [G2] in our global response.\n\nBelow we would like to discuss the remaining questions.\n\n**[W4] Details about experimental setups**\n\nAttention glitches are found even as we vary the dataset, sequence length, and tokenization. Figure 3 (right) demonstrates that attention glitches become more frequent as sequence length increases, and that this phenomenon appears across multiple commonly studied LLMs. Many of these models have different tokenization strategies and training sets. We have provided experimental details in Appendix B; please let us know if there are particular setups that you are concerned about, and we are happy to clarify further.\n\n**(Q1) Is Transformer failing because of overfitting?**\n\nWe interpret “overfitting to training distribution” as “overfitting the empirical distribution of training samples” (please let us know if we misinterpreted your question), which we do not think is the reason. Note that we train both LSTM and Transformers on online data where each batch is freshly sampled (as described in the detailed setups, i.e. Appendix B.2 – Training and evaluation data), which can be considered as training for 1 epoch and hence unlikely to overfit.\n\n**(Q2) Connecting attention glitches to hallucination in natural languages?**\n\nPlease refer to [G2] in our global response.\n\n**(Q3) Code release**\n\nWe plan to release the code upon publication, thank you for the suggestion!\n\n**(L1) Clarify all experiments are synthetic**\n\nWe believe this is rather clear already, since we have explicitly stated this in multiple places:\n- FFLM is stated as “a parametric family of synthetic benchmarks…” in the abstract (line 9), in the list of contributions at the end of the introduction (line 47), and in the conclusion section (line 292).\n- Section 3.2 also clearly states that FFLM is synthetic and is dedicated toward justifying the importance of the benchmark. \n- The beginning of Section 4 (line 162) states that the experiments are synthetic.\n\nPlease let us know if you have suggestions on better highlighting the setup, thank you very much! \n"}, {"review_id": "YdhG94UsN8", "reviewer": "Reviewer_ycg1", "summary": "The paper identifies a simple task for which the Transformer architecture fails. The authors introduce flip-flop language modeling, towards quantifying the extrapolation capabilities of different architectures. Transformer models are determined to suffer from long tail errors, in a phenomenon termed \"attention glitches\". \n\nThroughout the paper, this new synthetic task is analysed and the failure modes of Transformer models are identified. The authors embark and compare different techniques to mitigate the failures. Some theoretical justification and some mechanistic interpretability are also provided.", "questions": "1. It will be helpful to report errors as a function of difficulty. This can be done by presenting the errors as a function of sequence length (as done in Figure 3-right) or by also presenting errors as a function of different FFL tasks. If we define as $d$, the distance between the last write and the current read operation, is there a connection between the distribution of $d$ in the training set and the types of errors in the extrapolation set? How many examples of distance $d$ need to be presented for the model to generalize? For (possible) outliers $d$ in the training set, is the model fitting them correctly? There might be some interesting connections with Grokking [1, 2], where the model switches from a state of memorizing to one of generalizing.\n2. Preposition 2 states that a 2-layer 1-head Transformer can represent FFL. Is there is practice any benefit with depth?\n3. Other ways to decrease the entropy of the attention include the change of the temperature inside the softmax (which is not included in Proposition 3), or the method of [3].\n\nFixes:\nFigure 3 (left) x-axis is cropped (50 -> 500), also middle-right (10->10K). \n\n[1] Power, Alethea, et al. \"Grokking: Generalization beyond overfitting on small algorithmic datasets.\" arXiv preprint arXiv:2201.02177 (2022).\n\n[2] Thilak, Vimal, et al. \"The slingshot mechanism: An empirical study of adaptive optimizers and the grokking phenomenon.\" arXiv preprint arXiv:2206.04817 (2022).\n\n[3] Martins, André, et al. \"Sparse and continuous attention mechanisms.\" Advances in Neural Information Processing Systems 33 (2020): 20989-21001.", "limitations": "The paper proposes a simple example to study failure in extrapolation of Transformer models. The authors identify the lack of correct inductive bias in the model as the major shortcoming. Although many different regularization techniques are proposed, no clear answer is given for this phenomenon. I believe that this will however steer the community towards the right direction, for answering fundamental questions what these models is concerned. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper discusses a very simple task for which recurrent networks triumph, but Transformer present failure cases, attributing these failures to the inductive bias of the model. The task proposed is very simple and adequately motivated.\n2. Long range dependencies are a common failure case of Transformer models. FFLM allows for easy to check failures for reasoning tasks.\n3. Extensive experiments with different regularizations are provided. ", "weaknesses": "1. I feel some of the implications and connections to Ji et al., 2023 are not highlighted. From Figure 3, depth does not seem to have a direct consequence on performance.\n2. Although some theoretical justification is provided, assumptions are in cases too strong, i.e. linear positional encoding.\n3. Although a series of regularization and other techniques are proposed to solve the errors, no clear solution is proposed that works. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the careful read and for the insightful comments! We are glad that you find the FFLM task to be well-motivated and helpful for steering the direction of the community towards fundamental concerns about the models. We hope to address your concerns below.\n\n**[W1] Connection to hallucination and insights from Ji et al. 2023**\n\nThis is a great question. Please refer to [G1] in our global response.\n\n**[W2] Some assumptions for theory are strong**\n\nAs our experiments highlight, the OOD distribution errors have a long-tail behavior and the OOD performance itself varies drastically across different random seeds, as well as, across different iterates in the same runs. This makes it highly non-trivial to develop a complete end-to-end theory for attention glitches. Our work takes the first step towards this by characterizing the impact of the self-attention head on the failure of OOD. We understand that the assumption on linear position encoding and focusing on a single attention-head is strong, but we believe the insights here are already useful in highlighting the challenge of FFLM and how simple fixes may not be enough to fix the OOD problem.\n\n**[W3] No clear mitigation strategy is proposed.**\n\nPlease see [G3] in our global response.\n\n\n**[Q1] Error as a function of “difficulty”; relation to grokking**\n\nWe have added an additional plot (please see Additional Figure 3 in the rebuttal pdf) highlighting the fraction of errors by dependency length. Note that the errors occur at both short and long dependency range. Plotting fine-grained OOD performance using richer metrics of the training set beyond the ignore token probability $p$ used to generate it is a great suggestion. Note that $p$ itself does characterize the distribution of distance between read and write for the training set (as long as we have enough samples), which is why we used this simple metric. We would be happy to add additional experiments looking more closely at the relationship of errors and training distribution. We agree that understanding how much of the OOD data of each type is necessary to generalize well is a very interesting question for future work.\n\nMoreover, our results are not directly related to grokking, since the training is done in an online fashion (i.e. each batch of samples is freshly sampled) and hence there is no overfitting.\n\n\n**[Q2] Practical benefit / Role of depth of Transformer**\n\nProposition 2 emphasizes that depth-2 is sufficient to represent the FFLM language. We believe depth-2 is necessary as well. In our experiments, we not only train Transformers with depth-$2$ but also depth-$\\{4, 6, 8\\}$. (We also provide a few runs at larger depths, up to $16$; see Figure 1 in the rebuttal attachment.) However, we do not see a significant correlation between depth and OOD performance in the $>10000$ training runs with various hyperparameters. Since depth adds more representation power, it might seem that it offers an overparameterization benefit. However, it also introduces entanglements with optimization dynamics, where the benefits/drawbacks of depth are not so clear. There has been some recent work [1] that highlights that bigger models might end up being less robust than smaller models. We believe that understanding the role of overparameterization would be an interesting direction for future work.\n\n\n**[Q3] Attention sharpening by changing the temperature**\n\nFollowing [2], we used a $\\log(\\tau t)$ temperature, where $\\tau$ is the temperature parameter, and $t$ is the position (i.e. we use a different temperature for each position). However, this method was not able to help mitigate OOD errors, as shown in Figure 2 of the global response PDF.\n\n**References**\n\n[1] Miceli-Barone, A. V., Barez, F., Konstas, I., and Cohen, S. B. (2023). The larger they are, the harder they fail: Language models do not recognize identifier swaps in python. arXiv preprint arXiv: 2305.15507.\n\n[2] David Chiang, Peter Cholak. Overcoming a Theoretical Limitation of Self-Attention.\n"}, {"review_id": "ds3cfNZZHm", "reviewer": "Reviewer_4Fu7", "summary": "The paper introduces Flip-Flop Language Modeling (FFLM) to examine closed-domain\nhallucinations of Large Language Models (LLMs). Flip-Flop languages are\nsynthetic benchmarks which model a single bit of memory and its operations: read\n(r), ignore (i), and write (w). For example, the string \"w 1 i 0 r 1\" is valid\nas the same bit was written and read, but \"w 1 i 0 r 0\" is invalid. The task of\nthe Transformer is to attend to the last write operation and generate the\ncorrect bit for the read operation.\n\nThe authors discover that the Transformer exhibits a long tail of reasoning\nerrors even on this simple task (they call these attention glitches), and these\nerrors are very hard to mitigate. Interestingly, the LSTM can perform the task\nperfectly, with 20x less training.\n\nThey also introduce a preliminary study on the effect of attention sharpening on\ntraining Transformers to simulate the flip-flop automaton. Intuitively\nsharpening should help as the Transformer only needs to attend to the most\nrecent write. They find that sharpening can indeed help but also introduce new\nerrors.\n\n", "questions": "In the flip-flop language the value can be only 0 or 1. It could be interesting\nto extend the task to more values (like 0-15, or a single byte, 0-255). How\nworse do you think the Transformer and the natural LMs would perform in that\ncase? Do you think that the LSTM would still perform very well?\n\nThe attention sharpening regularization uses $-\\Vert\\alpha\\Vert_{2}$, but usually\n$L_1$ norm is used for sparsification. I found the reasoning behind\n$L_\\infty$ and entropy in the cited paper (Zhang et al.), but I still don't\nsee how using $L_2$ norm sparsifies. Could you elaborate on this?\n\n", "limitations": "The limitations are addressed thoroughly in the Conclusion.\n", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper provides very interesting and significant insights into the workings\nof the Transformer architecture.\n\nSome of the most interesting findings:\n- Transfomers make reasoning errors on the long tail\n- 1-layer LSTMs can learn the same task perfectly\n- Transformers exhibit high variance in the OOD test error between random seeds\n  and even iterations withing the same training run\n- 10B-scale LLMs cannot solve the task robustly\n- architectural and regularization changes can have orders-the-magnitude effects\n  on OOD performance\n- in contrast to LSTMs, it seems that completely eliminating attention glitches\n  is not possible for Transformers\n\nFlip-flop languages are also interesting as they are realizable by\nself-attention (as the authors explain in lines 221-224), so they could\nrepresent a reasoning task which should actually be easier for LLMs.\n\nThe paper is also very well written, I could not find any errors or opaque\nsections.\n\n", "weaknesses": "I think the main weakness of the study is that it's limited to flip-flop\nlanguages. That being said, I think this is just because of the foundational\nnature of the study: examining other languages would be outside the scope of the\npaper and could be explored in future work.\n\nStill, although the findings are very interesting, some of them may be specific\nto flip-flop languages. For example, (R4), training on rare sequences, would be\nvery hard to do in the general case of natural language, and so I'm not sure\nwhat (R4) means in the general case. Also, (R5) says that scaling improvements\nare orders of magnitude smaller, I wonder if that stands for natural language\ntoo as it's much more diverse.\n\nThe authors include some natural language experiments isomorphic to a flip-flop\nlanguage and a discussion about natural language in the Appendix.\n\nEven though Section 5.3 is a preliminary study it would be good to include some\nquantitaive results.\n\nI believe that Fig. 5 (d) is incorrect: the error marked in red should be\n$\\sigma_0$ and $\\sigma_1$.\n\nThe notation $\\Delta$ could be introduced, I don't think it's widely\nused in probability.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the encouraging feedback and for the helpful suggestions! We are glad that you find our results interesting and significant, and would like to discuss the remaining concerns below. \n\n**[W1] Generalizing insights to natural languages**\n\nThis is a great question; we provided some discussions in [G1] of the global response. We’d also like to comment on “incorporating rare sequences'', which is as of now the only effective solution. While it is unclear how to formally define “rare sequences” in natural languages, we intuitively think of it as “improving data diversity”, which has been proven effective by several related works in various setups. The closest to our setting is Jelassi et al. 2023, which showed that adding as few as 10 OOD samples can greatly improve the generalization performance on arithmetic tasks. More generally, data diversity is shown to be the main contributor of CLIP’s robustness (Fang et al. 2022), and a properly chosen data mixture can improve the pretraining results (Nguyen et al. 2022, Xie et al. 2023).\nRegarding scaling improvement, we have some partial evidence that while scaling helps improve the performance, it cannot fully eliminate the errors. Please see (R3) in our paper, as well as discussions in Appendix B.2.\n\n**[W2] Quantitative results on mechanistic interpretability**\n\nIn Appendix B.5, we provided quantitative results on the regularization’s effect on weight norms (Figure 11) and difference in attention patterns (Figure 14, Figure 16(a)). We are happy to incorporate further suggestions to the results!\n\n**[W3] Potential typo in Fig 5(d)**\n\nThank you for the close read! The figure is actually correct, that is, the error is indeed on the read token marked as the red $\\bot$. Note that a seemingly incorrect attention pattern does not necessarily mean a wrong prediction; please see our footnote 8 and the discussion in “Appendix B.5 – Sparsity regularization helps sharpen the attention – Are attention patterns reliable for interpretability?” In this case, Even though the attention for the last $\\sigma_0$ and $\\sigma_1$ are on the wrong token, their predictions are still correct. We apologize for the confusion and will make this clear in the revision.\n\n**[Q1] - FFLM with multiple symbols**\n\nWe experimented with more symbols and report the results in Figure 2 of the global response PDF. Note that the 1-layer LSTM solves all of the task variants perfectly; please see [G4] in our global response for more discussions.\n\n**[Q2] Attention sharpening with L2**\n\nNote that we are regularizing on vectors after the softmax, where each attention vector has an L1 norm equal to 1 (i.e. on the simplex, which is denoted by $\\Delta$). The largest L2 norm on the simplex is achieved when the vector is one-hot, hence encouraging a large L2 norm is equivalent to sharpening the attention. We will clarify this in the revised paper, and also define $\\Delta$ clearly.\n\n"}]

Author rebuttal:
We thank all the reviewers for their thoughtful comments. In this global response, we address questions posed by multiple reviewers, and outline additional experiments we ran during the author response period.

**[G1] Gap between FFLM and natural languages:** We certainly agree that there are numerous discrepancies between FFLM vs. natural language modeling. We introduce FFLM not to act as a representative distribution for the many diverse capabilities needed to process natural language; rather, we use it to isolate *one* important capability where Transformers exhibit subtle errors. We reiterate the perspectives discussed in our paper:
* Instances of FFLM are embedded in distributions of natural language and code, as seen in Figure 2c. We see in practice that natural LLMs exhibit similar sporadic errors when prompted to complete such sequences (Figures 1 and 3 (top right)). Thus, robust FFLM processing is a necessary (but far from sufficient) condition for robust language processing.
* Shallow, parallel compositions of flip-flops can process a large class of formal languages known to be relevant in syntactic parsing and algorithmic reasoning [Liu et al. ‘23]. Thus, FFLM is an “atomic” unit of more complex sequence processing capabilities, and attention glitches may provide a way to tackle the notoriously hard problem of diagnosing the internal representations of LLMs. We are excited to tackle this in future work.

**[G2] Gap between attention glitches and hallucinations in practice:**
* We are only claiming that Transformers’ errors on flip-flop strings to be similar to a specific type of hallucination: namely, closed-domain hallucinations, where the model’s generations contradict unambiguously presented factual information provided in the context. Our intent is to provide a _minimal_ example which fulfills this criterion and reveals a shortcoming in the inductive bias of Transformers.
* We _do not_ claim to address (or even define) LLM hallucinations in their full scope; the full question of defining LLM factuality is ambiguous and philosophical in nature.
* As noted by reviewer ycg1, work by [Ji et al., 2023] suggests that LLM hallucinations broadly tend to improve with increasing depth, but here we find that deeper language models are not necessarily more resilient to attention glitches. Attention glitches are a particular kind of hallucination that Transformer architectures are susceptible to, and the architectural particulars of a Transformer-based model (like depth) do not remedy them. Our work, which considers various architectures, tokenizers, and regularizers, suggests that more invasive interventions are necessary to solve attention glitches. 

**[G3] Regarding algorithmic fixes:** Reviewers ZZvs and ycg1 shared concerns about lack of algorithmic fixes. Rather than a weakness, we view this to be our work’s **central negative result**: we searched comprehensively for a clear fix, and did not find one (apart from changing the distribution or eschewing the Transformer).

While Section 5 documents a wide selection of algorithmic interventions that can quell the attention glitch pathology by orders of magnitude, it is true that we do not provide a solution on par with data diversity or the recurrent network. The goal of this paper is to highlight one kind of hallucination, and to emphasize that this is particular to the Transformer, regardless of its scale or specific architecture; recurrent predecessors have no such shortcoming. FFLM offers a precise probing mechanism for benchmarking progress on hallucinations of this kind, and further, helps to identify one concrete, disambiguated cause of the general LLM hallucination problem. We believe that advancing language models requires both thorough experimentation that identifies specific, classifiable kinds of hallucinations and honed tools like FFLM to study them closely — our work makes these contributions.

**[G4] Additional experiments and plots:** During this response period, we launched a few more sets of training runs, to address some of the reviewers’ curiosities. Figures are provided in the attachment.
* Dependence on scale: Figure 1 shows violin plots for o.o.d. errors across various model sizes, showing no clear trend (and no significant gain from increasing or decreasing model size). This corresponds to the hyperparameter grid sweep outlined in Figure 6 in the appendix of the original manuscript.
* Temperature: Prior work has suggested that sparsity of attention heads can be achieved by scaling the attention scores before the softmax by a constant (i.e. tuning the temperature). Our preliminary finding is that this does not improve extrapolation (Figure 2); note that direct attention sharpening *does* work (though not perfectly).
* Different number of states: Reviewers ZZvs and 4Fu7 both suggest variants of this experiment (which is also mentioned as a natural generalization axis in the paper); see our response to ZZvs for an explanation of the variants. Our preliminary findings: the long-tail errors persist; the 1-layer LSTM solves all of the task variants perfectly.
* Stratified errors by dependency length: in Figure 3, as requested, we exhibit a breakdown of error rates as a function of dependency length (distance from the current read token to the previous non-ignore token), on 3000 sequences from FFL(0.1) and 30K sequences from FFL(0.98)). This shows, in a finer-grained manner, that the errors are diverse in nature (not concentrated on any particular $n$-gram length), corroborating that this phenomenon evades oversimplified characterizations.


Meta-review: This paper proposes a synthetic task, called Flip-Flop Language Modeling (FFLM), for evaluating "attention glitches" in language models (LMs), which are cases when the model fails to capture long-range dependencies, resulting in factual inaccuracies or erroneous reasoning. The task simulates read/write/ignore operations over a single bit of memory, that requires copying binary symbols over long-range dependencies while ignoring the tokens in between. The authors find that transformers struggle on this simple task, with errors that are very hard to mitigate, while LSTMs can perform the task perfectly with 20x less training. 

The main concerns raised by the reviewers and discussed during the rebuttal focused on (a) lack of actionable insights, (b) the fact that the paper discusses a connection between hallucinations and long-range dependencies, without discussing how these two terms interact with each other, and (c) the evaluation being limited to a fully synthetic task, making it unclear if the findings will generalize to natural languages and more complex tasks. Most of these concerns were adequately addressed by the authors, who listed concrete ways for future work to use their findings, and clarified the scope of their work.

Overall, there was a general agreement that the paper makes substantial contributions, both introducing a succinct and valuable evaluation for LMs and exposing a key limitation of the core neural architecture that has been dominating the NLP field (and is widely used in other fields as well). Findings from this work might be valuable for tackling the problems of long-range dependencies and hallucinations in language modeling, which are central problems today.
Decision: Accept (spotlight)