PaperlayerView exact revision on arXiv

Source-linked AI summary

Exposing Attention Glitches with Flip-Flop Language Modeling

Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, Cyril Zhang

arXiv:2306.00946v2cs.LGcs.CL

TL;DR

The paper asks why Transformers can produce sporadic factual and reasoning errors despite strong capabilities. It introduces FFLM, a synthetic one-bit memory benchmark, and finds that Transformers exhibit attention glitches: a long tail of errors that mitigations reduce but do not fully eliminate. The results support studying architectural causes of closed-domain hallucinations, while the connection to natural LLMs remains unconfirmed.

  • Problem

    The paper addresses the unresolved brittleness of Transformer reasoning, especially sporadic errors on long chains and possible closed-domain hallucinations.

    Source: §1 · p. 1

  • Method

    The authors introduce FFLM, a parametric synthetic benchmark requiring models to copy binary symbols across long-range dependencies while ignoring intervening tokens.

    Source: §1 · p. 2, §3.1 · p. 4, §3.2 · p. 5

  • Results

    Transformers show a long tail of sporadic reasoning errors, whereas recurrent models can extrapolate perfectly; regularization reduces but does not eliminate Transformer errors.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    FFLM provides a minimal stress test for architectural robustness and motivates investigating recurrence and other architectural changes alongside data and regularization.

    Source: §1 · p. 2, §6 · p. 10

    The hypothesis that attention glitches account for natural-LM hallucinations remains unconfirmed because internal representations and training data lack adequate controls.

    Source: §6 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

Large language models can generalize on algorithmic sequences yet still produce sporadic, subtle errors on long reasoning chains. The paper introduces FFLM to isolate these failures and finds Transformer-specific attention glitches that regularization reduces but does not eliminate.

1 Introduction

  • The authors hypothesize that attention glitches may account for some closed-domain hallucinations in natural language models, but do not establish that connection.They describe confirmation or refutation as outside the paper’s scope because natural-language training data and internal representations lack adequate controls.Source: §1 · p. 1
  • FFLM is a parametric synthetic benchmark that isolates long-range reasoning by requiring models to copy binary symbols while ignoring intervening instructions.The task targets a minimal memory operation underlying algorithmic reasoning and complements existing long-range benchmarks.Source: §1 · pp. 1–2
  • Transformers can learn flip-flop sequences on held-out data yet make a long tail of unpredictable errors on both long- and short-range dependencies.The paper calls these failures attention glitches and contrasts them with perfect recurrent-model performance.Source: §1 · p. 2
  • Attention sharpening reduces reasoning errors by an order of magnitude, but no tested mitigation drives the error count to exactly 0.The study evaluates direct and indirect regularization approaches, including standard regularization and attention-sharpening methods.Source: §1 · p. 2

1.1 Related work

  • The benchmark uses an L∞ objective that treats any accuracy below 100% as a reasoning error and supports replicated, procedurally generated evaluation.This stringent criterion is intended to expose tail errors and avoid their amplification in larger computational networks.Source: §1.1 · p. 3

2 Background and notation

Sequence models map token sequences through learned transformations, with recurrent and self-attention architectures providing different inductive biases. The paper frames its background around the contrast between recurrent processing and non-recurrent attention for long-range dependencies.

2 Background and notation

  • Neural sequence models transform vector sequences into next-token distributions using embeddings, shared output mappings, and trainable internal computations.Both recurrent and self-attention architectures can fit the sequence-to-sequence functions needed for fluent parsing and reasoning.Source: §2 · p. 3
  • Recurrence naturally represents uniform algorithmic computations over arbitrarily long sequences, whereas Transformers rely on non-recurrent self-attention.The paper emphasizes that the architectures can learn qualitatively different solutions.Source: §2 · p. 3
  • Flip-flop machines provide elementary examples of sequential prediction tasks that require maintaining a discrete state across a sequence.The associated automata and examples motivate the later FFLM construction.Source: Figure 2 · p. 4

3 Flip-flop automata and the FFLM task

FFLM models valid sequences of write, read, and ignore operations over a single bit, requiring every read to return the most recent written value. The paper motivates this minimal task as a basic unit of memory and algorithmic reasoning.

3.1 Definitions

  • A valid flip-flop string alternates instructions and data, begins with write, ends with read, and requires each read to match the latest write.The alphabet contains write, read, ignore, and binary data symbols.Source: §3.1 · p. 4
  • The canonical FFL(T,p) family fixes the initial write and final read while sampling intermediate instructions and nondeterministic data according to p.This parameterization creates distributions with different frequencies of sparse and dense dependencies.Source: §3.1 · p. 4
  • FFLM can be evaluated in generative mode on all next-token predictions or deterministic mode that supervises only continuations at read operations.The paper reports the clean deterministic setting because nondeterministic-token prediction is irrelevant to the memory task.Source: §3.1 · pp. 4–5

3.2 Why focus on the flip-flop?

  • Flip-flop simulation is a minimal memory operation embedded in reasoning, parsing, code, semantic tracking, and tasks requiring irrelevant context to be ignored.The paper describes it as a depth-1 special case of Dyck-language processing and as a component of many finite-state computations.Source: §3.2 · p. 5
  • The flip-flop monoid is the smallest monoid with both non-commutative and non-invertible operations, and cascades of flip-flops can simulate all group-free finite-state automata.This gives the task formal relevance beyond a toy benchmark.Source: §3.2 · p. 5
  • Although a single attention head can perform the required long-range lookup, the paper tests whether attention-based architectures perform this operation robustly.This follows from attention’s intended role in selectively retrieving and copying distant data.Source: §3.2 · p. 5

4 Attention glitches: a long tail of errors for Transformer FFLMs

On FFLM, Transformers show irregular extrapolation errors while recurrent LSTMs extrapolate perfectly in the reported experiments. The paper analyzes several possible attention-glitch mechanisms, including soft-attention dilution and brittle hard-attention tie-breaking.

4 Attention glitches: a long tail of errors for Transformer FFLMs

  • Transformers exhibit a long, irregular tail of errors on both sparse and dense sequences, with strong variation across random seeds and training iterates.The experiments use FFL(0.98) and FFL(0.1) to probe distinct long- and short-range failure modes.Source: §4 · p. 6, Figure 3 · p. 6
  • A 1-layer recurrent model achieved 100% accuracy in 100 of 100 runs, despite using 20 times fewer training samples and iterations.This contrasts sharply with the Transformer results on the same extrapolation task.Source: §4 · p. 6
  • Natural language models at 10B scale can process natural embeddings of flip-flop languages, but rare read errors become more probable as sequence length grows.The capability emerges from in-context demonstrations yet remains non-robust.Source: §4 · p. 6

4.1 Multiplicity of mechanisms for attention glitches

  • A local n-gram explanation cannot account for correct very-long-range predictions or errors on dense sequences, so subtler mechanisms are required.The paper presents this model as an insufficient explanation of the observed Transformer failures.Source: §4.1 · p. 7
  • Soft attention can dilute across positions as sequence length grows, preventing the intended hard selection operation under fixed weight norms.The paper formalizes this limitation in Proposition 3.Source: §4.1 · p. 7
  • Even hard attention can confidently select the wrong index unless position-encoding weight matrices satisfy a precise orthogonality condition.The analysis suggests spurious local optima, though the paper does not prove that mechanism end-to-end.Source: §4.1 · p. 7

5 Mitigations for attention glitches

The paper evaluates direct data interventions, regularization strategies, and mechanistic patterns to reduce Transformer attention glitches in flip-flop language modeling. Training on rare sequences works best, while other interventions reduce but do not eliminate errors and reveal persistent mechanistic failure modes.

5.1 Effects of training data and scale

  • Training on rare sequences reliably produces far fewer errors, with 6 of 25 runs showing no detected errors.The baseline was trained on a uniform mixture of FFL distributions, and this outperformed resource scaling by a wide margin.Source: §5.1 · p. 7
  • Resource scaling helps extrapolation, but improvements are much smaller than rare-sequence training and trade off sparse- versus dense-sequence performance.Scaling included in-distribution data, training steps, and network size.Source: §5.1 · p. 7

5.2 Indirect algorithmic controls: a bag of regularization tricks

  • Many architectural choices and regularizers change out-of-distribution error rates by orders of magnitude, with embedding dropout and attention sharpening strongest for sparse sequences and fixed position embeddings strongest for dense sequences.The study evaluated weight decay, dropout, optimizer and positional choices, activation functions, and multiple attention-sharpening losses across at least 25 replicates per choice.Source: §5.2 · pp. 8–9
  • Despite partial mitigations, no tested Transformer setting reliably improves both sparse- and dense-sequence extrapolation over baseline, unlike the LSTM.Figure 4 summarizes dense- and sparse-sequence error pairs across 10,625 Transformer models.Source: Figure 4 · p. 8, §5.2 · p. 9

5.3 Preliminary mechanistic study of the trained networks

  • Attention sharpening promotes simpler, more interpretable hard-attention patterns that can match an ideal sparse solution in the flip-flop simulation.The mechanistic study compares regular and sparse multi-layer models with idealized one-layer, one-head patterns.Source: §5.3 · p. 9, Figure 5 · p. 10
  • Sharpened attention still makes sporadic errors, including confidently selecting incorrect write positions and shifting toward wrong positions during length generalization.These failures are attributed partly to complex, redundant attention patterns and causal-mask effects, complicating mechanistic interpretation.Source: §5.3 · p. 9

6 Conclusion and future challenges

The paper introduces FFLM as a controlled benchmark for extrapolative reasoning and concludes that Transformers exhibit sporadic attention glitches, while recurrence and long-tailed training can eliminate them in this setting.

6 Conclusion and future challenges

  • FFLM isolates one-bit memory retrieval as a minimal benchmark for probing fine-grained extrapolation in neural sequence models.The benchmark uses a one-bit memory operation that forms a fundamental building block of algorithmic reasoning.Source: §6 · p. 10
  • Transformers exhibit a long tail of sporadic reasoning errors on FFLM, whereas recurrent models are far more robust across efficiency, stability, and extrapolation.The conclusion states that recurrence and training on longer-tailed data work perfectly, and that Transformers are far inferior to recurrent sequence models in this setting.Source: §6 · p. 10
  • The proposed natural-LLM implication remains a hypothesis: attention glitches may contribute to closed-domain hallucinations, but confirming this is outside the paper’s scope.The authors identify opaque internal representations and inadequate training-data controls as methodological obstacles.Source: §6 · p. 10

A.1 Flip-flop terminology and history

  • The flip-flop automaton stores one bit through write-0, write-1, and do-nothing operations, making it a minimal unit of sequential computation.Its transition function sets the state to 0 or 1 for writes and preserves the current state for the ignore operation.Source: §A.1 · p. 18

A.2 Additional related work

  • FFLM complements prior synthetic and algorithmic benchmarks by providing a parametric, procedurally generated stress test for long-tail reasoning errors.Its difficulty can be adjusted through sequence length and other parameters, and the authors recommend measuring glitch rates for architectural innovations.Source: §A.2 · p. 20

A.3 Why this flip-flop language?

  • The autoregressive formulation makes FFLM compatible with standard causal language modeling, while introducing an instruction–data association challenge.The authors describe this indirection as a natural representation-learning challenge and note that coarser tokenization can remove it.Source: §A.3 · p. 20

A.4 Attention glitches in natural LLMs

The paper hypothesizes that attention glitches in internal algorithmic subnetworks may contribute to closed-domain hallucinations, but emphasizes that this connection is difficult to test rigorously and does not address open-domain hallucinations.

A.4 Attention glitches in natural LLMs

  • The hypothesis is difficult to formulate and test because neural networks’ internal representations resist simple mechanistic characterization.The authors state that rigorous validation faces significant methodological challenges.Source: §A.4 · p. 20
  • In FFLM, hard retrieval means retrieving the bit associated with the most recent write position, with correctness defined by matching the flip-flop machine on every input sequence.These definitions provide a concrete resolution to ambiguities about retrieval and ground truth.Source: §A.4 · pp. 20–21
  • The paper does not address open-domain hallucinations, where outputs contradict real-world knowledge, because those errors may be unrelated to attention glitches.Its ground-truth framework is designed for closed-domain formal reasoning with deterministic outputs.Source: §A.4 · p. 21
  • The analysis considers both end-to-end networks and individual attention heads, revealing that overparameterized Transformers often implement the task through soft attention.The relevant submodule can vary from the whole network to a single head or other localized component.Source: §A.4 · p. 21
  • Attention glitches are hypothesized to cause some closed-domain hallucinations when internal subnetworks fail to represent flip-flop-like operations perfectly.The paper treats this as a hypothesis about natural-language Transformers, not as a confirmed explanation.Source: §A.4 · pp. 20–21

B.1 Details for LLM addition prompts (Figure 1)

  • The addition examples establish non-robustness but cannot support claims that larger models fail only at longer sequences or that no prompting strategy can improve reasoning.The examples were selected adversarially and ad hoc, and the authors explicitly leave prompt effects unresolved.Source: §B.1 · p. 21

B.2 Extrapolation failures of standard Transformers (Section 4)

Controlled FFLM experiments show that Transformers sometimes extrapolate successfully but retain an irregular tail of errors, while a one-layer LSTM extrapolates perfectly across all tested replicates.

B.2 Extrapolation failures of standard Transformers (Section 4)

  • The evaluation probes in-distribution behavior and sparse- and dense-tail extrapolation under FFL(0.8), FFL(0.98), and FFL(0.1) conditions.The sparse and dense tails contain substantially more read instructions than the in-distribution set and are the focus of the main measurements.Source: §B.2 · pp. 22–23
  • Transformers exhibit a long, irregular tail of extrapolation errors despite sometimes succeeding, with variability across random seeds.The main experiments emphasize high-precision measurements on sparse- and dense-tail evaluation sets.Source: §B.2 · p. 23
  • 0 final-iterate out-of-distribution error was achieved by a 1-layer LSTM in 100 of 100 replicates, whereas Transformer extrapolation remained erratic.The LSTM used 133K parameters, and larger LSTMs also extrapolated perfectly in smaller experiments.Source: §B.2 · p. 23
  • The canonical baseline is a 6-layer, 512-dimensional, 8-head Transformer with 19M trainable parameters evaluated over 500 replicates.The architecture was chosen to be substantial in relevant dimensions while remaining affordable for many runs.Source: §B.2 · p. 23
  • Both model initialization and data randomness affect outcomes, indicating that stochasticity contributes to the observed variability.The study demonstrates that both sources matter but does not fully characterize their separate influence.Source: §B.2 · p. 23
  • A fully generative autoregressive setting shows similar non-extrapolation, variability, and instability, although in-distribution training usually succeeds with the baseline architecture.Training takes slightly longer in this setting, and the authors do not conduct further controlled experiments there.Source: §B.2 · p. 23

B.2.1 Evaluating real LLMs on flip-flops

Natural-language and synthetic evaluations show that language models can infer flip-flop rules but lose accuracy and extrapolation reliability as sequences lengthen.

B.2.1 Evaluating real LLMs on flip-flops

  • GPT-2, GPT-2-large, GPT-2-xl, Pythia-12C, and GPT-NeoX-20B were evaluated on translated length-16 flip-flop prompts while sequence length varied.Accuracy measured whether the model correctly predicted the light switch’s current state.Source: §B.2.1 · pp. 23, 26
  • Transformer training curves show non-convergence, failed out-of-distribution extrapolation, high seed variability, and erratic progress despite flat in-distribution curves.A small LSTM outperformed the Transformers in the comparison.Source: Figure 6 · p. 24, Figure 7 · p. 25
  • As sequence length increases, all evaluated natural LMs deteriorate, although larger models generally perform best.Each plotted point used 500 sequences of the indicated length.Source: §B.2.1 · p. 26
  • The natural-language evaluation introduces in-context inference and additional failure modes, so fully reconciling it with the synthetic experiments remains outside the paper’s scope.The authors identify reconciliation through training, finetuning, or mechanistic interpretation as future work.Source: §B.2.1 · p. 26
  • ChatGPT-4 followed short natural-language flip-flop sequences up to length 400 but made unexpected errors on longer sequences.The model appeared to understand the rules before failing on longer inputs.Source: §B.2.1 · p. 26

B.3 Effects of training data and scale (Section 5.1)

The study tests whether broader training coverage, additional resources, and model scaling improve Transformer extrapolation on rare flip-flop sequences.

B.3 Effects of training data and scale (Section 5.1)

  • Training on rare sequences works best by a wide margin for reducing attention glitches.Long-tailed training directly improves coverage of sparse and dense sequence regimes.Source: §B.3 · pp. 26–27, Figure 9 · p. 27
  • Resource scaling helps overall, but its effects depend on the sequence-density regime and do not replace favorable training coverage.Training longer reduces unlucky error-prone outliers, while recurrence can extrapolate without such coverage.Source: §B.3 · p. 27
  • More training data or optimization steps reduce sparse-sequence errors but trade off against dense-sequence performance.The comparison includes fresh data and repeated epochs over the same dataset.Source: §B.3 · pp. 26–27
  • Increasing model size shows no discernible monotonic relationship with extrapolative performance.The evaluated architecture settings varied layers, embedding dimension, and attention heads.Source: §B.3 · p. 27, Figure 9 · p. 27

B.4 Indirect algorithmic controls for extrapolation (Section 5.2)

Architectural, algorithmic, and regularization choices substantially change extrapolation error, but their benefits are uneven and no tested control removes glitches completely.

B.4 Indirect algorithmic controls for extrapolation (Section 5.2)

  • Regularization and architectural variants produce orders-of-magnitude differences in Transformer out-of-distribution performance.Large embedding dropout and attention-sharpening losses help sparse sequences, while non-trainable position embeddings help dense sequences.Source: §B.4 · pp. 27, 29
  • Large embedding dropout reduces sparse-sequence errors by 2 orders of magnitude, yet does not eliminate glitches.Figure 10 compares weight decay and three dropout forms.Source: Figure 10 · p. 28
  • Attention-sharpening and other jointly tuned interventions produce the best runs, especially with an annealing schedule, but residual glitch rates remain nonzero.Figure 11 reports the selected architectural, loss-based, and indirect controls.Source: Figure 11 · p. 28
  • Non-trainable position encodings help dense sequences but show no clear benefit on sparse sequences requiring longer-term dependency handling.The study also evaluates sinusoidal, learned, ALiBi, RoPE, and zero positional encodings.Source: §B.4 · p. 29
  • Changing AdamW hyperparameters yields no significant extrapolation improvement.The sweep varied β1, β2, and learning rate.Source: §B.4 · p. 29
  • Attention glitches persist, and generally worsen, when softmax temperature or vocabulary size is changed; errors also span diverse dependency lengths.Figure 12 provides supplementary comparisons and a dependency-length distribution.Source: §B.4 · p. 29

B.5 Preliminary mechanistic study and challenges (Section 5.3)

Mechanistic analyses show that attention sharpening can create cleaner, task-aligned patterns, but attention drift, bad local minima, and interpretability limits help explain why glitches persist.

B.5 Preliminary mechanistic study and challenges (Section 5.3)

  • Attention-sharpening regularization promotes hard attention, yet errors persist.This is the section’s central mechanistic finding.Source: §B.5 · p. 29
  • Attention patterns need not reveal importance: non-sparse models may assign higher attention to an incorrect token while producing the correct prediction.In a 1-layer, 1-head model, 1-sparse attention is more interpretable under the paper’s assumptions.Source: §B.5 · p. 30, Figure 17 · p. 34
  • In a long sequence with two writes, attention initially selects the latest write but later drifts toward recent reads that contain no task information.The authors suggest positional encodings may undesirably affect attention weights.Source: §B.5 · p. 30, Figure 14 · p. 32
  • Sparse attention is not sufficient for correctness because regularization can produce bad local minima that rely on earlier positions.The authors suggest causal masking may make earlier positions more frequent during training, but leave the mechanism incompletely explained.Source: §B.5 · p. 30, Figure 16 · p. 33
  • Attention-sharpening changes weight norms and later-layer attention behavior, with sharp patterns propagating even when only the first layer is regularized.The paper presents these observations as preliminary evidence about altered training dynamics.Source: §B.5 · p. 32, Figure 15 · p. 33, Figure 19 · p. 35

B.6 Software, compute infrastructure, and resource costs

  • The appendix reports that identical baseline runs take about 10 minutes per 10^4 steps on one GPU, with replicate sets requiring about 4 GPU-hours.The software and compute description identifies PyTorch-based implementations and released benchmarks.Source: §B.6 · pp. 32, 36

C.1 Realizability of FFL by small Transformers

  • A 2-layer, 1-head Transformer with residual connections can represent deterministic FFL, but the construction is not unique because dense solutions can also implement the task.The proof uses one layer to convert FFL into the flip-flop automaton and another to retrieve the latest write.Source: §C.1 · pp. 36–37

C.2 Failure of soft attention: attention dilution with bounded Lipschitzness

The section identifies two attention failure modes: bounded soft-attention scores become diluted on sufficiently long sequences, while linear positional encodings impose constraints needed for perfect length generalization.

C.2 Failure of soft attention: attention dilution with bounded Lipschitzness

  • For T = Ω(exp(2σmax)), bounded-norm latent vectors yield max softmax weight 1 − Ω(1), so attention cannot remain sparse as sequences grow.The proof bounds pre-softmax scores within [−σmax, σmax], making the maximum attention weight bounded away from one for sufficiently large T.Source: §C.2 · p. 37
  • Attention dilution need not affect final prediction when ignore tokens occupy a subspace projected out by WV and the number of writes remains bounded.In the experiments, denser sequences increase the number of writes beyond training, making dilution a potential cause of reduced performance.Source: §C.2 · p. 38

C.3 Failure of hard attention: bad margin for positional embeddings

  • The hard-attention analysis studies a one-layer, one-head Transformer because automaton simulation is a sub-task of flip-flop language modeling.The setup decomposes query and key matrices into embedding and positional components under linear positional encoding.Source: §C.3 · p. 38
  • With linear positional encoding pi = i/C, perfect arbitrary-length generalization requires positional query/key interactions to satisfy sign constraints; positive interaction can eventually reverse the desired attention ordering.The analysis considers long-term dependencies and compares the final position’s scores for an early write and a later write.Source: §C.3 · pp. 38–39

Related papers

Loading 2306.00946v2…