PaperlayerView exact revision on arXiv

Source-linked AI summary

Putting Transformer Theories to the Test

Awni Altabaa, Tobias Schnabel, Kiran Tomlinson

arXiv:2610.32104v1cs.LGcs.CL

TL;DR

Different transformer theories use different abstractions and consequently disagree about which tasks are easy or hard. The paper maps seven theories onto a shared task suite and tests their predictions through controlled experiments. No single theory explains the observed pattern: predictions break down when theories omit relevant transformer behaviors.

  • Problem

    Different theoretical abstractions yield conflicting predictions about transformer capabilities, leaving unclear which theories explain practical task performance.

    Source: §1 · p. 1

  • Method

    The authors map seven theories onto a common suite of tasks, complete missing predictions with theoretical results, and evaluate them using in-distribution, length-generalization, and pretrained-model experiments.

    Source: §1 · p. 2, §3.2 · p. 8, §3.3 · p. 10

  • Results

    No single theory explains the observed successes and failures, and predictions tend to break down when a task depends on a feature the theory omits.

    Source: §1 · p. 2, §5 · p. 14

  • Takeaways & Limitations

    A more practical theory should capture soft attention, content-dependent retrieval, bounded computation, learnability and inductive biases, and combine upper and lower bounds.

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

    Some expressivity claims are upper bounds rather than guarantees, and fixed-precision transformers cannot recognize some languages in TC0.

    Source: §2 · p. 4

Abstract

from arXiv · show

Several formal theories have been developed to characterize the capabilities and limitations of the transformer architecture, each employing different abstractions that capture different features of the architecture. Due to the differences in their underlying assumptions and conceptual frameworks, these theories can disagree in their predictions about what tasks transformers find easy or hard. We map out seven theories of transformer capability (Star-free, $\mathsf{AC}^0$, $\mathsf{TC}^0$, C-RASP, MPC, BAPO, and Sensitivity) and translate their results into a common matrix of predictions across a suite of tasks covering different computational structures. We provide new theoretical results to complete this matrix. We then evaluate theoretical predictions through controlled experiments measuring in-distribution sample complexity, length generalization, and pretrained language model performance. We find that no single theory explains the observed pattern of successes and failures. When a theory does not capture the transformer behaviors relevant to a task, its predictions break down; for instance, we show that the $k$-hop induction task is predicted hard by C-RASP because it does not model content-dependent attention, but we train small transformers on this task that length-generalize. Similarly, theories assuming hard attention like $\mathsf{AC}^0$ and BAPO predict binary majority to be hard, for which we also find success in practice. Together, our results point to several specific features that a theory of transformers must capture: soft rather than hard attention, dynamic content-dependent retrieval, bounded computation at each position, an account of learnability and inductive biases, and a combination of upper and lower bounds.

1 Introduction

The paper addresses a gap between transformer theory and practice: different abstractions make conflicting predictions about which tasks transformers can solve. It compares seven frameworks with experiments on small task-specific transformers and pretrained language models, finding that no single theory explains their observed behavior.

1 Introduction

  • The comparison covers seven theoretical frameworks and common tasks spanning Boolean, graph, and syntactic computation.Where existing analyses are missing, the authors add theoretical results and constructions.Source: §1 · p. 2
  • No theory fully explains small task-specific transformers or pretrained language models; predictions tend to fail when a task depends on features the theory omits.Hard predictions are more accurate overall, but a correct prediction of failure does not necessarily identify its cause.Source: §1 · p. 2
  • Loose upper bounds and unmodeled learning dynamics can also mislead: transformers fail to fit Parity training data, and positional encodings affect length generalization.Different encodings are needed for different tasks, and current theory does not account for these inductive biases.Source: §1 · p. 2
  • Hard-attention theories predict Majority is hard, while C-RASP predicts retrieval is hard because it cannot model content-dependent attention.Transformers nevertheless learn and length-generalize Majority; C-RASP requires exponential size for a retrieval task that softmax-attention transformers solve efficiently, and trained transformers show the same gap.Source: §1 · p. 2

2 Theories of Transformer Capabilities & Limitations

The paper compares seven frameworks that make predictions about transformer capabilities using distinct abstractions and assumptions. These frameworks differ in information flow, attention, computation, and whether they address expressivity or learnability; the paper also situates its comparison among related work.

2 Theories of Transformer Capabilities & Limitations

  • The seven frameworks are Star-free, AC0, TC0, C-RASP, MPC, BAPO, and Sensitivity; the first six address expressivity, while Sensitivity addresses learnability.Their differing conceptual foundations produce conflicting task predictions.Source: §2 · pp. 2–3
  • Star-free, AC0, and TC0 form a strict inclusion chain, while C-RASP lies inside TC0 and MPC contains TC0; BAPO cuts across the hierarchy.C-RASP is incomparable with Star-free and AC0, and BAPO includes Star-free but excludes some C-RASP and AC0 tasks.Source: §2 · p. 2
  • Theories differ in causal versus bidirectional information flow, hard versus soft attention, and local-computation assumptions.Hard attention restricts global aggregation; C-RASP uses uniform averaging rather than query-dependent attention, while MPC and BAPO allow unbounded local computation.Source: §2 · p. 3
  • Star-free models causal hard attention and predicts tasks easy when they are star-free languages, such as bounded-depth Dyck, but hard otherwise, including Parity.Star-free languages express event order but not periodic counting; this is the most restrictive theory in the suite.Source: §2 · p. 4
  • AC0 models constant-depth Boolean circuits and predicts Majority and Parity hard; TC0 adds threshold gates and predicts both easy.AC0 is linked to bidirectional hard attention, while TC0 models soft-attention transformers; its transformer relation is an upper bound, not a converse.Source: §2 · pp. 4–5
  • C-RASP compiles programs using Boolean values, integer counts, and prefix-counting into causal softmax transformers, but its uniform-prefix attention omits dynamic content-dependent retrieval.A C-RASP program solving a task gives a transformer construction, hence a lower bound on transformer capability.Source: §2 · p. 5
  • MPC models positions as machines exchanging bounded messages over rounds, while BAPO measures prefix-to-suffix information using a summary and suffix-informed token selections.MPC allows arbitrary local computation; BAPO classifies a task as easy when constant bandwidth suffices, but has no formal simulation result relating it to transformers.Source: §2 · p. 5

2.1 Additional Related Work

  • Sensitivity links Boolean-function sensitivity to sharp loss minima, but applies only to Boolean functions under uniform distributions; related work also spans learnability, generalization, chain of thought, and empirical studies.The paper's empirical contribution is to compare competing predictions across in-distribution sample complexity, length generalization, and pretrained-model performance.Source: §2 · p. 6, §2.1 · p. 7

3 Methodology

The methodology tests whether seven theories’ predictions align with empirical transformer behavior. It applies the theories to a diverse task suite, fills prediction gaps with analysis, and evaluates success through in-distribution learning, length generalization, and pretrained language models.

3 Methodology

  • The study compares theoretical predictions with experiments on small task-specific transformers and frontier language models to map each theory’s domain of validity.The goal is to synthesize which abstractions capture features that matter in practice.Source: §3 · p. 8

3.1 Suite of Tasks

  • The task suite targets disagreements among theories and covers Boolean functions, retrieval, sparse functions, Dyck languages, iterated retrieval, and graph problems.Tasks probe structures such as global aggregation, stack-like nesting, and composition of content-based lookups.Source: §3.1 · p. 8

3.2 From Theories to Predictions

  • Each theory is applied to each task to produce an Easy/Hard prediction, with missing cells filled from prior analysis, known model results, new proofs, or conditional results.For missing analyses, the authors construct Easy results or prove lower bounds or impossibility results for Hard predictions.Source: §3.2 · pp. 8–9

3.3 Experimental Design

  • The experiments measure in-distribution learning, length generalization, and pretrained LLM performance, classifying tasks as solved at a normalized-accuracy threshold of 90%.Length-generalization models train on inputs up to 32 and are tested up to 256; the LLM evaluation tests up to n = 128 without reasoning in the main evaluation.Source: §3.3 · p. 10
  • In-distribution experiments vary input size and training-set size for a fixed four-layer causal transformer, while length-generalization experiments vary model size and positional encoding.In-distribution runs use five seeds; length-generalization models train on n = 8 to 32 and test on larger inputs.Source: §3.3 · p. 10

4 Results

The paper compares seven theories’ task predictions with three experiment lines and adds theoretical results to complete the prediction matrix. Across the results, theories disagree about task difficulty, and observed learning varies by task and setting.

4.1 Theory

  • Among seven theories, Star-free is most restrictive, predicting Easy on only 8 of 19 tasks, while TC0 and MPC are most powerful, predicting Easy on 17 of 19.For retrieval tasks whose range grows with n, Star-free and C-RASP predict Hard; C-RASP also predicts Hard for k-Hop Induction because it lacks content-dependent attention.Source: §4.1 · p. 11
  • New analyses place bounded-depth Dyck and k-Hop Induction outside C-RASP’s capabilities and establish BAPO-hardness for unbounded Dyck-k and BinaryAdd.The paper also identifies a width separation between C-RASP or uniform-attention transformers and softmax attention transformers on query-key retrieval tasks.Source: §4.1 · p. 11

4.2 Experiments

  • Transformers learn and length-generalize on Majority, contradicting hard predictions from Star-free, AC0, and BAPO, but fail to learn Parity even at modest sizes.At n = 8 with 65,536 training examples, Parity training-sample accuracy is only 49.7–59.1% across five seeds.Source: §4.2 · pp. 11–12
  • Sparse-All/Any is efficiently learnable and sometimes length-generalizes, whereas Sparse-Parity’s in-distribution success is fragile at n ≥ 64.At those sizes, at most one of 25 runs succeeds at each size.Source: §4.2 · p. 12
  • Small transformers learn Index at every input size, but Index-All/Any is solved only through n = 16 to 64 within the budget, and Index-Parity remains unlearnable.Length generalization is observed for Index and Index-All with some architectures; that evaluation bounds the index range and is not directly comparable to theory predictions.Source: §4.2 · pp. 12–13
  • Bounded-depth Dyck is solved in-distribution at every size but generalizes only weakly; unbounded Dyck is solved only through n = 64, with one configuration generalizing Dyck-1 to n = 256.The successful configuration was one of 27 searched, and one of five seeds succeeded.Source: §4.2 · p. 13
  • BinaryAdd is learned only on small inputs, while Directed and Undirected Reachability remain unsolved even on 8-node graphs.Edge Existence also resists learning in the main setup but becomes learnable with denser supervision on every edge.Source: §4.2 · pp. 13–14
  • Pretrained LLMs succeed robustly only on All and Edge Existence; with reasoning, GPT-5 solves most settings through n = 128, except Dyck, BinaryAdd, and Index-All with k = 3.The paper notes that Dyck failures may reflect its per-position next-token-set prediction evaluation.Source: §4.2 · p. 14

5 Discussion

The discussion argues that mismatches between theoretical predictions and transformer behavior reveal which features a theory omits. It identifies gaps in attention models, computational bounds, learnability, positional-encoding inductive biases, and accounts of pretrained language models.

Models of attention: soft vs hard, and dynamic retrieval

  • Theories modeling hard attention miss global aggregation, while C-RASP’s uniform averaging misses dynamic, content-dependent retrieval.The discussion argues that a faithful attention model should be both soft and content-dependent.Source: §5 · p. 14

Unbounded computation and loose upper bounds

  • TC0 and MPC can model global aggregation and content-dependent retrieval, yet predict Easy for tasks transformers fail to learn.The discussion attributes some errors to excess computational resources and loose upper bounds; MPC and BAPO also allow unbounded local computation.Source: §5 · p. 14

Failures of learning, not expressivity

  • Expressivity theories do not explain learning failures such as Parity’s optimization difficulty, BinaryAdd’s seed variation, or Edge Existence’s dependence on denser supervision.Only Sensitivity among the seven theories makes learning claims, and its scope is narrower than expressivity theory.Source: §5 · p. 14

Positional encoding & inductive biases

  • Length generalization depends strongly on positional encoding, and no encoding scheme succeeds across all tasks.Sinusoidal encodings generalize on bounded-range Index, relative encodings succeed on 1-Hop Induction, and NoPE succeeds on unbounded Dyck-1.Source: §5 · p. 15

LLMs are more complex objects

  • Small transformers and pretrained LLMs behave differently: LLMs fail on Majority and Index as n grows, while small models learn them.The discussion points to tokenization, training data, training recipes, and simultaneous multi-task training as factors beyond current expressivity theory.Source: §5 · p. 15

6 Conclusion

The conclusion finds that no single theory explains transformers’ full pattern of successes and failures, which involve expressivity, learning, positional-encoding inductive biases, and interactions among these mechanisms. The appendix separates mathematical task definitions from experimental sampling, tokenization, and supervision choices.

6 Conclusion

  • No single theory explains transformer successes and failures across expressivity, learning, positional encoding, and their interactions.The paper also reports that pretrained LLMs and small transformers trained from scratch can succeed on different tasks.Source: §6 · p. 15
  • Future theories should model soft, content-dependent attention, bound computation at each position, explain what training finds, and account for LLM-specific complexity.The task suite and prediction matrix are offered as a testbed for new theories.Source: §6 · p. 15

A Task Suite Details

  • The appendix separates task functions and languages from the experiments’ sampling, tokenization, and supervision choices.Its mathematical definitions use one-based positions, binary data unless stated otherwise, and task parameters fixed independently of n.Source: A Task Suite Details · p. 21, §A.1 · p. 21

A.1 Mathematical task definitions

  • Boolean tasks include all-ones, any-ones, majority, and parity; indexed tasks apply a Boolean function to values at queried positions.The appendix also defines fixed-range Index and its Index-* variants.Source: §A.1 · p. 21
  • Sparse Boolean tasks apply AND, OR, or XOR to fixed hidden positions, while BinaryAdd checks whether two n-bit operands sum to a proposed (n+1)-bit result.The appendix also defines Dyck languages by bracket types and a grammar, with nesting depth measured across prefixes.Source: §A.1 · p. 21
  • k-Hop Induction repeatedly retrieves the position after the most recent earlier occurrence of the current symbol, returning null if a hop is undefined.Graph tasks distinguish edge existence, directed reachability, and reachability when edge directions are ignored.Source: §A.1 · p. 22

A.2 Experimental tasks

The appendix specifies how tasks are sampled, encoded, and supervised across experiments. It describes the shared setup and the task-specific formats for Boolean, retrieval, addition, Dyck-language, induction, and graph experiments.

A.2 Experimental tasks

  • The appendix documents task sampling and encoding, while Table 3 lists settings and their use in in-distribution, length-generalization, and pretrained-LLM experiments.The table caption reports 34 in-distribution settings; the default scoring position is the final input token.Source: §A.2 · p. 22, Table 3 · p. 22

A.2.1 Boolean tasks

  • Boolean inputs use task-specific bit distributions; Majority uses uniform bits, with label 1 slightly more likely because of ties.For All, Any, and Parity, bit probabilities are chosen to balance the labels.Source: §A.2.1 · p. 22

A.2.2 Indexed retrieval

  • Index appends an address token to a sequence, while Index-All, Index-Any, and Index-Parity append multiple addresses and combine the queried bits.In-distribution range grows with n; length-generalization fixes the address range at 20.Source: §A.2.2 · p. 23

A.2.3 Sparse Boolean functions

  • Sparse Boolean tasks hide the queried positions from the input, requiring models to infer them from training data.For length generalization, hidden positions are drawn from the first 20 positions and shared across lengths.Source: §A.2.3 · p. 23

A.2.4 Binary addition

  • Binary addition uses two n-bit operands and trains autoregressive prediction of all n+1 result bits, with teacher forcing during training.The main-text figures use blocked operand layout and most-significant-bit-first output; evaluation requires every generated bit to be correct.Source: §A.2.4 · p. 23

A.2.5 Dyck languages

  • Dyck experiments predict the set of tokens legally allowed next after START and each bracket, rather than classifying membership directly.Inputs are correctly nested bracket strings; evaluation requires every predicted legal set to be exactly right.Source: §A.2.5 · pp. 23–24

A.2.6 Iterated retrieval: k-Hop Induction

  • k-Hop Induction uses a four-symbol sequence and applies one to three retrieval hops, returning a null class if a hop has no earlier match.Each hop moves to the position immediately after the most recent earlier occurrence of the current symbol.Source: §A.2.6 · p. 24

A.2.7 Graph tasks

  • Graph tasks share a directed-graph input format and differ by whether the query asks about an edge, directed reachability, or undirected connectivity.The dense Edge Existence variant places the query before the edge list and labels each edge’s match, alongside the final answer.Source: §A.2.7 · p. 24

B Experimental Details

Appendix B documents experimental procedures and evaluation conventions, including model architecture and training protocols, normalized accuracy and chance levels, and LLM prompts for directed reachability and undirected connectivity queries.

B.1 Model architecture and training

  • From-scratch models are decoder transformers with softmax attention, pre-layer normalization, and two-layer GELU feedforward blocks, trained with AdamW at a constant 10−3 learning rate.They use batch size 256, bfloat16 mixed precision, gradient clipping at 1.0, and no weight decay or dropout; embeddings are tied except for graph tasks and BinaryAdd.Source: §B.1 · p. 24

B.2 In-distribution learning

  • In-distribution runs vary training-example counts while holding compute fixed, using a four-layer, width-256 transformer and five seeds per configuration.Runs use 2,048 optimizer steps and 8,192 held-out examples; comparisons across example counts are paired within seed, and a setting is Easy only if a seed reaches 90% normalized held-out accuracy at n = 256.Source: §B.2 · pp. 24–25

B.3 Length generalization

  • Length-generalization tests use five training lengths and 19 evaluation lengths, while indexed-task addresses remain within positions 0–19 and are all seen during training.Thus, longer indexed-task inputs add unqueried positions rather than unseen addresses; these settings differ from the in-distribution tasks and are not compared with theory predictions in Table 2.Source: §B.3 · pp. 25–26

B.4 Pretrained language models

  • The pretrained-model evaluation covers 27 task settings at eight input sizes, excludes sparse tasks, and grades each model by whether normalized accuracy reaches 90% at n = 128.Models receive shared prompts with three solved examples and a test input; answers must match exactly, while refusals, invalid JSON, and completion-budget exhaustion count as incorrect.Source: §B.4 · pp. 26–27

B.5 Normalized accuracy

  • Normalized accuracy subtracts the best constant-answer chance level and scales by 1 − chance; sequence-answer tasks use unnormalized full-sequence accuracy.A setting is solved at a size when normalized accuracy reaches 90%, with each experiment applying its own rules across seeds and lengths. For unbounded Dyck-1, the best constant answer has accuracy about 0.25, and failed models at n ≥ 128 score 0.2–0.33.Source: §B.5 · pp. 27–28

B.6 LLM prompts

  • The LLM prompt appendix illustrates the evaluated format with one size-8 test prompt per task, while noting that each actual prompt includes three solved size-12 examples.For tasks with multiple settings, the shown prompt represents one setting; other settings alter task parameters such as query count, bracket types, depth, hop count, or output-bit order.Source: §B.6 · p. 29
  • The directed-reachability prompt asks whether a path connects the source to the target and requests a JSON Boolean answer.Edges are written as "u -> v".Source: §B.6 · p. 33
  • The undirected-connectivity prompt asks whether a path joins two nodes and treats repeated edges as having no extra meaning.Edges are written as "u -- v", and the response is a JSON object with a Boolean answer.Source: §B.6 · p. 34

C Additional Experimental Results

The appendix extends the experiments with dense supervision for Edge Existence, fuller task-setting results, and analyses of length generalization and GPT-5 reasoning. These additions show that supervision and experimental configuration matter, while reasoning-enabled results require accounting for truncated responses.

C.1 Edge Existence with dense supervision

  • Dense supervision makes Edge Existence learnable: it is solved in-distribution at every size except n = 128, and one medium Shaw-relative configuration generalizes to n = 256.At n = 128, the best seed reaches 0.87 normalized accuracy; the length-generalizing configuration uses medium model size.Source: §C.1 · p. 35

C.2 In-distribution learning

  • Figure 4 supplies the full n × N in-distribution grid, adding omitted task settings including dense-supervision Edge Existence and additional Dyck, BinaryAdd, index, and sparse-task variants.The figure reports normalized accuracy by input size and training-set size, with minimum, mean, and maximum across five seeds.Source: §C.2 · p. 35, Figure 4 · p. 36

C.3 Length generalization

  • Figures 5–8 extend length-generalization results across task settings and compare positional encodings, attention direction, and uniform attention against the best configuration.Some tasks succeed only with certain positional encodings; causal and bidirectional performance is fairly consistent overall, while uniform attention performs substantially worse across many problems.Source: §C.3 · p. 37, Figure 5 · p. 37, Figure 6 · p. 38

C.4.1 LLMs with reasoning

  • With medium reasoning, 3% to 25% of GPT-5 BinaryAdd responses are truncated and counted incorrect, making accuracy non-monotone in n for three formats.Excluding truncated responses raises intermediate-size accuracy by up to 0.58 but does not change any task grade.Source: §C.4.1 · p. 40, Figure 9 · p. 40

D Background on the Theories

This appendix details the assumptions and formal relationships behind the theories and transformer classes, including a new separation result for query-dependent retrieval. Its comparisons depend on attention type, information flow, and technical constraints such as precision and positional encoding.

Relations between theories

  • BAPO and Sensitivity lack formal containment relations to transformer classes, while the diagram’s other relations depend on technical assumptions and caveats.The compared base classes differ in positional-encoding assumptions; BAPO is omitted alongside Sensitivity for lack of a formal containment relation.Source: D Background on the Theories · pp. 41, 44
  • Bidirectional unique-hard-attention transformers are contained in non-uniform AC0, but they cannot recognize approximate majority, an AC0 language.With positional encodings, these transformers can recognize every regular language in AC0, including (aa)∗, which is not star-free (Barceló et al., 2024, Corollary 1; Schützenberger, 1965).Source: D Background on the Theories · p. 42
  • Average-hard attention can recognize Majority, while its bidirectional O(log n)-precision transformer class has a log-space-uniform TC0 upper bound.The cited Majority constructions use uniform attention and a CLS token (Chiang, Cholak, and Pillay, 2023, Proposition 11), or future positional masking (Barceló et al., 2024, Corollary 2).Source: D Background on the Theories · pp. 42–43
  • The softmax-attention TC0 upper bound assumes O(log n)-bit precision and log-time-computable positional encodings; its tightness is conjectured, not established.The cited upper bound is for a restricted model (Merrill and Sabharwal, 2023a, Theorem 2), and narrower fixed-precision results do not cover soft attention at O(log n)-bit precision.Source: D Background on the Theories · p. 43
  • C-RASP compiles into causal softmax transformers, and fixed-precision transformers without positional encodings can be simulated by C-RASP with an exponentially larger program.The cited constructions use uniform attention and layer normalization for one direction, and enumeration of finitely many activation values for the reverse direction (Yang and Chiang, 2024, Theorems 4.3, 5.7, and 7.1).Source: D Background on the Theories · p. 44
  • One causal softmax attention head solves query-dependent retrieval over 2m key-value items at residual width m + 2, while C-RASP requires Ω(2m/m) prefix-count nodes.The result establishes a separation at comparable size (Theorem 1).Source: D Background on the Theories · p. 44
  • Star-free is strictly contained in AC0, which is strictly contained in TC0; C-RASP is strictly inside TC0, and TC0 is contained in MPC.Star-free and AC0 differ on (aa)∗, AC0 and TC0 differ on Majority, and C-RASP and TC0 differ on Parity; TC0 ⊆ MPC follows from constant-round simulations under stated memory assumptions.Source: D Background on the Theories · p. 44

E Notes on the Theory–Task Predictions

The notes explain how task-specific results support the theory–task prediction matrix, including cases where predictions depend on input encodings or complexity conjectures. They also introduce the circuit, C-RASP, and BAPO frameworks used in those explanations.

E Notes on the Theory–Task Predictions

  • Table 9 marks theory–task predictions as easy, hard, non-trivial results proved here, or conjecture-dependent.Table 10 links each prediction to its explanation and references.Source: Table 9 · p. 45, E Notes on the Theory–Task Predictions · p. 45
  • Reachability predictions for TC0, C-RASP, and MPC are conditional on stated complexity assumptions, while BAPO-hardness is stated for reachability.For directed reachability, the TC0 and C-RASP predictions assume L ≠ NL; MPC hardness relies on conjectures.Source: E Notes on the Theory–Task Predictions · p. 49
  • The prediction notes justify entries with task-specific constructions and lower bounds, organized by task family.For example, growing-range Index is nonregular but has uniform AC0 circuits under binary encoding, while atomic-address BAPO bounds do not establish the same result for binary indices.Source: F Supporting Theory–Task Results · p. 49

F.1.1 Circuits and logic

  • DLOGTIME-uniform AC0 uses constant-depth, polynomial-size circuits, and TC0 additionally permits unbounded-fan-in majority gates.The fragment FO[<] defines exactly the star-free languages.Source: §F.1.1 · pp. 49–50

F.1.2 C-RASP

  • C-RASP uses Boolean streams and integer-valued count streams, with prefix counting as its information-moving operation.A program accepts from its final Boolean stream at the last input position; counting depth measures the longest chain of counting operations.Source: §F.1.2 · p. 50

F.1.3 BAPO

  • BAPO combines a prefix summary, selected attended prefix tokens, and the suffix to compute the task output.Its functions are the prefix oracle, attention function, and suffix oracle.Source: §F.1.3 · p. 50

F.2 Fixed-range Index

For fixed index ranges, the paper gives constructions showing that Index and its fixed-arity Boolean variants fit several formal frameworks. The constructions rely on the index bound and, for the logic results, valid input formats.

F.2 Fixed-range Index

  • Fixed-range Index is expressible in FO[<], hence star-free and in DLOGTIME-uniform AC0 and TC0 on valid inputs.The construction identifies the fixed queried position using a finite list of position predicates.Source: §F.2 · pp. 51–52
  • Fixed-range Index-* with fixed arity and Boolean function is likewise expressible in FO[<] and belongs to star-free, DLOGTIME-uniform AC0, and TC0.The proof retrieves each queried bit and applies the fixed Boolean formula; the result is on valid inputs.Source: §F.2 · p. 52
  • Fixed-range Index and Index-* each have a C-RASP program of counting depth at most two.For Index-*, the program retrieves each selected bit before applying the Boolean function.Source: §F.2 · p. 53
  • Fixed-range Index-* has a (k −1, k)-BAPO for fixed index bound, arity, and Boolean function.The construction uses the prefix oracle to save selected bits and the attention function to select prefix positions requested in the suffix.Source: §F.2 · p. 54

F.3 Growing-range Index

For growing-range Index tasks, the paper establishes results across circuit, finite-state, BAPO, MPC, and C-RASP models. Several results are encoding-specific, and the C-RASP lower bound rules out fixed-size programs as the query range grows.

F.3 Growing-range Index

  • Growing-range Index-* with fixed arity and Boolean function is representable in FO[<, BIT], hence has DLOGTIME-uniform AC0 and TC0 circuits on valid inputs.This result uses binary-encoded indices.Source: §F.3 · p. 54
  • Growing-range Index and fixed-arity Index-All, Index-Any, and Index-Parity are not finite-state computable, even on valid inputs.Their valid-input behavior therefore has no star-free realization.Source: §F.3 · p. 55
  • With atomic address tokens, growing-range Index has a (0, 1)-BAPO and fixed-arity Index-* has a (k −1, k)-BAPO.The result does not establish these bounds for binary-block addresses, where a split can divide an address.Source: §F.3 · pp. 55–56
  • Growing-range Index and fixed-arity Index-* have a three-round MPC protocol using O(n^δ) local memory per machine and polynomial total memory.The protocol gathers and decodes queries, routes requests to data owners, and returns the requested bits.Source: §F.3 · p. 56
  • A base C-RASP program for growing-range Index needs at least n log2(n + 1) primitive prefix-count nodes.The paper also concludes that these growing-range tasks have no fixed-size base C-RASP program valid for all n.Source: §F.3 · p. 56

F.4 Sparse Boolean functions

For fixed selected positions and a fixed Boolean function, Sparse-* has constructions in three formal frameworks. The constructions treat inputs shorter than the largest selected position as returning zero.

F.4 Sparse Boolean functions

  • Sparse-* with fixed arity, selected positions, and Boolean function is expressible in FO[<], hence star-free and computable by DLOGTIME-uniform AC0 and TC0.The formula identifies the fixed positions and applies a Boolean formula to their bits.Source: §F.4 · p. 57
  • Sparse-* has a base C-RASP program of counting depth at most two for fixed arity, positions, and Boolean function.The program returns zero when the input is too short to contain all selected positions.Source: §F.4 · p. 57
  • Sparse-* has a (0, k)-BAPO for fixed arity k, selected positions, and Boolean function.The attention function selects the relevant prefix bits, and the suffix oracle computes the output.Source: §F.4 · p. 58

F.5 Binary addition

The section proves that BinaryAdd verification is BAPO-hard: constant prefix-summary size and suffix bandwidth cannot suffice. Its proof counts records that distinguish candidate sums and also analyzes the task’s sensitivity.

F.5 Binary addition

  • BinaryAdd verification is BAPO-hard, ruling out constant prefix-summary size a and suffix bandwidth b.The proof establishes a lower bound by counting distinct records for candidate sums.Source: §F.5 · pp. 58–59
  • For the split x#y# | z, each candidate sum receives a record that forces every matching prefix to have that sum.Counting distinct records yields the lower bound.Source: §F.5 · pp. 58–59
  • The number of active operand positions is at most four times the maximum number of selected positions, bounding how many operand bits a record must retain.The proof obtains this bound by averaging over completions for a candidate sum.Source: §F.5 · pp. 58–59
  • At every accepting input, flipping any one of the 3n + 1 input bits makes the BinaryAdd verification fail.Each operand pair has a unique proposed sum, and changing any operand or result bit breaks equality.Source: §F.5 · p. 59

F.6 Dyck languages

This section examines C-RASP capabilities and limitations across Dyck-language membership, fixed-hop induction, and query-dependent retrieval from binary key-value databases. It reports computability and hardness results, and an exponential separation between counting and content-dependent retrieval as key dimension grows.

F.6 Dyck languages

  • For fixed k and D, Dyck-(k, D) membership on nonempty inputs has a base C-RASP[∅] program with O(kD) channels and counting depth at most three.The construction checks prefix-height underflow and overflow, type-specific opening and closing counts at each depth, and final height zero.Source: §F.6 · pp. 60–61
  • Unbounded Dyck with any fixed k is BAPO-hard: recognizing it on inputs of length at most N requires N < 4(2^a + 1)(2^b + 1), hence a + log2(b + 1) > log2 N − 4.For any fixed 0 < ε < 1, if b = o(N^(1−ε)), the bound forces a = Ω(log N).Source: §F.6 · pp. 61–62

F.7 Fixed-hop induction

  • For fixed alphabet Σ and hop count k, each k-Hop Induction output language is FO[<]-definable, and therefore star-free with DLOGTIME-uniform AC0 and TC0 circuits.The construction defines one hop as a relation between positions and composes it k times.Source: §F.7 · pp. 62–63
  • For fixed k and an alphabet with at least k + 3 symbols, final-position k-Hop Induction output is not computable in base C-RASP.The proof encodes a language whose strings, after deleting e symbols, contain two consecutive b symbols, contradicting its C-RASP nondefinability.Source: §F.7 · pp. 63–64

G.1 The Query-Dependent Retrieval Task

  • Query-dependent retrieval uses a sequence of 2m key-value items followed by a query key, and requires retrieving the bit for the matching key.The provided passage begins the task definition by introducing the input as a database.Source: G An Exponential Width Separation… · p. 65, §G.1 · p. 65

G An Exponential Width Separation between C-RASP and Softmax Transformers on Content-Dependent Retrieval

  • For query-dependent retrieval, one causal content-dependent softmax head solves the task at width m+2, while C-RASP needs Ω(2^m/m) count nodes and uniform-attention transformers need d=Ω(2^m/[D(p+m)]).The task asks a model to retrieve the bit associated with a matching key. The separation shows that uniform attention cannot dynamically select history items based on the query and must instead store the history in residual channels.Source: G An Exponential Width Separation… · p. 65

G.1 The Query-Dependent Retrieval Task

  • The task exhibits an exponential separation between counting and content-dependent retrieval as a function of key dimension m.The input has 2^m key-value pairs followed by one query token.Source: §G.1 · p. 65
  • Each input encodes all binary keys with assigned ±1 values and a query key, and the task is to output that key’s assigned value.Key-value items are represented by concatenating the m-dimensional key with its value; the query token contains the key and a zero in the value coordinate.Source: §G.1 · p. 65

G.2 Main Separation Result

Query-dependent retrieval sharply separates content-dependent softmax attention from C-RASP and uniform attention: the former can retrieve with linear width, while the latter require exponential resources. The bounds trace this gap to whether aggregation can depend on the query.

G.2 Main Separation Result

  • One causal softmax attention head solves retrieval with width m + 2, while C-RASP and uniform attention require exponential size.The gap remains exponential when uniform-attention transformers have depth and precision polynomial in m.Source: §G.2 · p. 66, §G.4 · p. 70

G.4 Content-Dependent Attention Upper Bound

  • Content-dependent attention uses query-key comparisons to select the matching database item and retrieve its value.The construction uses one layer and one head, with residual width m + 2, and needs neither a feedforward layer nor positional encoding.Source: §G.2 · p. 66, §G.4 · p. 69

G.3 C-RASP and Uniform Attention Bounds

  • C-RASP requires exponentially many prefix-count nodes, although a depth-one construction solves the task using L nodes.The lower bound holds at any count depth.Source: §G.2 · p. 65, §G.3 · p. 66

G.5 Experiments

On query-dependent retrieval, the experiments compare softmax and uniform attention across key dimensions and two model sizes. Softmax models solve the task throughout the tested range, while uniform-attention accuracy degrades as the key dimension grows.

G.5 Experiments

  • The experiment tests key dimensions m = 2 through 6, using databases of 2^m items and five random seeds per attention type and model size.The minimal model has one layer, one head, and width d = m + 2; the standard model has four layers, four heads, and width d = 256.Source: §G.5 · pp. 70–71
  • 100% accuracy in every seed, key dimension, and model size for softmax attention contrasts with uniform attention falling to about 55% at m = 6.At m = 2, the standard uniform-attention model solves the task and the minimal model reaches 90%.Source: Figure 11 · p. 71, §G.5 · p. 71
  • The accuracy pattern agrees with Theorem 1, though the authors note uniform-attention failures may reflect representational limits or difficulty learning content-dependent retrieval.Inputs use independently sampled binary values and a uniformly sampled query, making chance accuracy 50%.Source: §G.5 · pp. 70–71
Loading 2610.32104v1…