Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers
Authors: Charles London
Varun Kanade
Venue: NeurIPS 2025 poster ()
Keywords: complexity theory
transformers
learning theory
circuit complexity
Primary area: theory
TL;DR: We provide the first proof showing that pause tokens (such as "...") appended to the input of a Transformer can strictly increase its expressivity.

Abstract: Pause tokens, simple filler symbols such as "...", consistently improve Transformer performance on both language and mathematical tasks, yet their theoretical effect remains unexplained. We provide the first formal separation result, proving that adding pause tokens to constant-depth, logarithmic-width Transformers strictly increases their computational expressivity. With bounded-precision activations, Transformers without pause tokens compute only a strict subset of $\mathsf{AC}^0$ functions, while adding a polynomial number of pause tokens enables expressing the complete class. For logarithmic-precision Transformers, we show that adding pause tokens achieves expressivity equivalent to $\mathsf{TC}^0$, matching known upper bounds. Empirically, we demonstrate that two‑layer causally masked Transformers can learn parity when supplied with pause tokens, a function that they appear unable to learn without them. Our results provide a rigorous theoretical explanation for prior empirical findings, clarify how pause tokens interact with width, depth, and numeric precision, and position them as a distinct mechanism, complementary to chain-of-thought prompting, for enhancing Transformer reasoning.

Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers
Charles London
Varun Kanade
Department of Computer Science University Oxford
Department of Computer Science
University of Oxford
Oxford, OX1 3QG
Oxford, OX1 3QG
charles. londondcs. ox.
varun, kanade@cs ox ac
Abstract
Pause tokens, simple filler symbols such as "...", consistently improve Transformer performance on both language and mathematical tasks, yet their theoretical effect remains unexplained. We provide the first formal separation result, proving that adding pause tokens to constant-depth, logarithmic-wide Transformers strictly increases their computational expressivity. With mounded-precistoe activations, Transformers without pause tokens compute only a strict subset of AC functions, while adding a polynomial number of pause tokens allows them express the entire class. For Sggarithmic-precision Transformers, we show that adding pause tokens achieves expressivity equivalent to TC matching known upper bounds. Empirically, we demonstrate that two-layer causally masked Transformers can learn parity when supplied with pause tokens, function that they appear unable learn without them. Our results provide a rigorous theoretical explanation for prior empirical findings, clarify how pause tokens interact with width, depth, and numeric precision, and position them as a distinct mechanism, complementary chain-of of-uuuhgttthtt prompting, for enhancing Transformer reasoning.
Introduction
Transformers 38 have become ubiquitous modern machine learning, achieving state-of-the-art performance across wide range of tasks, particularly in natural language processing. Despite their empirical success, many aspects of their computational behaviour remain poorly understood. An intriguing recently observed phenomenon is that adding pause tokens (e.g. Transformer inputs can improve performance on some muestion-answeriie and mathematical tasks 30 [4] This phenomenon has raised questions about the computational role of such seemingly meaningless tokens, particularly in the context of chain-of-thought prompting and the faithfulness of intermediate reasoning steps.
token) to
In this paper, we provide a theoretical explanation for how pause tokens might improve Transformer performance. Specifically, we analyse how they affectt the expressivity of Transformers through the lens of circuit complexity. Our contributions are as follows:
Pause tokens allow Transformers simulate Boolean circuit classes exactly. We prove that constant-precisson Transformers with polynomial number of pause tokens are equivalent in expressivity to AC (constant depth circuits with and/or/not gates), while logarithmic precision Transformers with pause tokens match TC (circuits like AC with threshold gates).
2. Pause tokens strictly increase expressivity in constant- precision Transformers. We prove separation: Transformers without pause tokens are fundamentally less expressive than those with.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

3. Empirically, pause tokens help causally masked Transformers learn functions requiring global computation. We show that two-layer causally masked Transformers struggle learn parity (which belongs to TCº) unless pause tokens are introduced. This provides some insight into how pause tokens interact with architectural constraints in practice.
We consider both uniform and non- uniform Transformer and circuit classes (see Definition 3.6). covering the cases where Transformer parameters and positional encodings can be entirely arbitrary, and where they must be generated by efficiently computable procedure.
Our results provide principled explanation for recent empirical findings on pause tokens while also highlighting broader implications for Transformer expressivity. In particular, they suggest that Transformer's computational power not solely determined by depth and width, but also by how computation is distributed across the token sequence. The addition of pause tokens effectively expands the available computational workspace of the model, allowing it to implement more expressive computations within the same architectural constraints. These results have implications for the faithfulness of Chain-of-tthouhh reasoning, the tradcoffs between width and depth in Transformer architectures, and the impact of quantization on Transformer computation.
The remainder of this paper is organised as follows. Section reviews prior work on Transformer expressivity and the use of pause tokens (more related work is in the appendix). Section 3 introduces key concepts from eircuit complexity and formally defines the Transformer models we study. Section 4 presents our main theoretical results, establishing the expressivity of Transformers with and without pause tokens. Section provides empirical evidence that pause tokens facilitate learning of parity under causal masking. Finally, Section 6 discusses implications and Section 7 poses open questions.
2 Related Work
We first note the difference between the use of pause tokens and of-in-of-thhugile (CoT, Wei et al. (39) in Transformer computation. While both methods purport to increase the computational space or memory of the Transformer to enable to solve more problems, they do so very different ways. In CoT, Transformer generates tokens autoregressively and attends to its own output, enabling deeper sequential computation. With pause tokens, we simply pad the input to the Transformer with filler tokens, enabling "wider" parallel computation. While pause tokens are more efficient (as they can be computed in parallel), they are strictly less expressive than CoT 28 22
The notion of adding padding to a Transformers input to improve performance traces back Burtsev al. (5), in which they prepended memory tokens to the input to Transformer encoder, but achieved only marginal gains. Lanham et al. [21 experimented with replacing Transformer CoT tokens with blank "..." tokens at test time, and found they decreased performance versus COT. The first work to empirically demonstrate an advantage in using pause tokens was Goyal et al. [4], in which they pre-trained Transformer to use between 0 and 50 pause tokens before responding. This led to increased performance on natural language and mathematical benchmarks including CA (35) and GSM8K [0). Since then, Pfau et al. (30 have replicated this improvement on simple mathematical tasks and proposed quantifier depth as the theoretical explanation.
Transformers with pause tokens:
Formal models of Transformers: Since the invention of the Transformer, there have been many at- tempts to formally characterise their computational power. Initial works determined that Transformers were Turing complete [31], but required infinite precision for the result. More recent works have used tools from theoretical computer science, including circuit complexity, communication complexity. and formal language and automata theory, to analyse more realistic models of the Transformer and derive limitations on the languages they can recognise and problems they can solve. For machine learning, language recognition can be thought of as binary classification of input strings. This section covers work using circuit complexity, but further related work can be found in Appendix[A]
Circuit complexity. Hao et al. [6 showed that log-precision Transformers using unique hard attention (attending to only a single position) are contained within AC while averaging hard attention Transformers can express non-AC" languages. Merrill and Sabharwal [27] proved that log precision Transformers (with standard softmax attention) are contained within logspace-uniform
TC", while Chiang [9] extended these results to show that Transformers with (ppoy (n)) precision are in uniform TC Further works have also used the circuit complexity perspective to determine

---

the expressive power of both constant- and log-precinn precision Transformers using intermediate chain-of- thought steps, showing that they are equivalent P (uniformly, or P/poly non con-uniformly) [22 2822
Preliminaries
In this section, we introduce the relevant computational complexity concepts, including circuit classes and logspace uniformity, well definitions of the Transformer model considering and fixed precision arithmetic.
3.1 Boolean Circuits
Boolean circuits are model of computation that uses logical operations to process binary inputs and produce binary outputs. They are natural way formalise parallel computations (like Transformers), as their depth corresponds roughly to the parallel time required to compute a function, and their width corresponds to resource requirements at each level of parallel computation.
Definition 3.1. (Boolean circuits). A Boolean circuit C. is directed acyclic graph with sources and one sink, computing function {0, 1 + {0, 1}. Non-source vertices are gates labeled with logical operations. The output C, (x)) is determined recursively. |C, is the number of gates; depth is the longest path from any source to the sink.
We restrict ourselves two classes: AC and TC with constant ((1) depth and at most polynomial poly(n) size. AC circuits use NOT, AND, and OR gates with unbounded fan-in. TC circuits use threshold gates f()) iE 24 > 0] and f(z) IEi= 2t 0). known AC ç TC [3] ACP and TC; these classes restricted depth < l.
3.2 Circuit Families and Logspace Uniformity
Definition 3.2. (Circuit families). Let T N N be function. A T(n)-size circuit family is sequence {Cn)ner of Boolean circuits, where C, has n inputs and a single output, and [Cal < T(n) for all
Circuit families implicitly define a language that they accept, as follows:
Definition 3.3. (Language recognition). A circuit family {Cn, recognises L C {0, 13" if, for all {0, 13", (zx(()) 1 if and only x E
Without further constraints, circuit families recognise undecidable languages, such variants of the halting problem. avoid this, we use uniform circuits, which can be constructed by some computable function. A family {C., is logspace uniform if there is Turing machine using Oloog n) space that outputs Cn given 1 (for formal definition, see Definition B.2). Logspace uniformity ensures that circuits can be constructed systematically, avoiding non-uniform "hard-coded" solutions for each input size.
3.3 Limited Precision Arithmetic
We follow Li et al. (22 in using a fixed-point numerical representation, with bit for the sign, p(n) bits before the point, and p(n) bits afterwards. When working with constant precision p(n) = O()), and for logarithmic precision p(n) = 0(logn) We will use the shorthand p(n).
Definition 3.4 (Fixed precision arithmetic). For a fixed precision level p:
Values represented in F,- {c k P c {-1,1), E N,O 2 1}.
Arithmetic operations (e.g., addition, multiplication) round results to the nearest representable value in F,.. We define by [zlp R Fp the operation that rounds the nearest representable number. When addition iterated, we operate left to right, rounding after each operation (so is no longer associative).
Saturation arithmetic used: values exceeding the representable range [-Bp, Bp), where B, 2P - 2-P, are clamped to BBp

---

We justify these choices as a reasonable approximation of how arithmetic is done in quantized neural networks. These quantized networks often use form of outlier clipping (saturation arithmetic) to avoid issues with overflow, and round numbers to the closest number in the representable range [8]
3.4 Transformer Definition
All theoretical results this work apply to both decoder-only and encoder-only Transformers models (i.e. with and without causal masking). In our proofs on the lower bounds of Transformer expressivity, we assume causal masking as this setting is more restrictive, but results still hold if removed.
Definition 3.5 (Transformer). A Transformer consists of layers, each composed of multi- heat masked self-attention mechanism and feedforward network. Given an input sequence X = (f1,,..,,Tr)) where xy E Rdd
Self-Attentio:: Each head computes weighted sum of a linear transform of the input tokens
X + XWV. softmax (xwQxx) x + M)
(1)
where W WV E Rdxd and M E R=**, In the case that the Transformer is causally masked M lower triangular, with -B, above the diagonal, and all other elements zero. Without masking, M is the zero matrix. The models we consider have fixed number of attention heads.
Feedforward Network: A position-wise feedforward network, with constant depth and (dd)
width, is applied to each token after each attention layer.
Positional Encodings: Fixed or learned positional encodings ((i, n) E IRd are added or appended to each input token z; to encode token positions.
Residual Connections: Each sublayer (attention/fecdforvarr)) has residual connections.
We will define by TF [F)p(n), d(n), b(n)] the family of problems L {0, 13" + {0. 13 for which
there is an integer such that there exists an (-layer Transformer with precision 2p(n) embedding dimension d(nz), and b(n) additional blank tokens that computes C(x) on any E {0, [0.
In this work, will largely operate with classes of Transformers with some range of functions p(n), d(n), B(n). In the constant precision case, the classes we consider are:
1. TF[1, L, 0] = UseN TF(c, clog n, 0].
2. TF(1, L, P] UcEN TFlc, log n, n²),
3. TF(1, I, Q] = UCEN TF|c, c log n, 2 2logn)"1
These are Transformers with constant precision, logarithmic embedding size, and no, polynomial, and quasi-polynomic pause tokens, respectively. We choose logarithmic embedding size feel it is the most practically relevant to current architectures, while still enabling attention over the entire input sequence. To define the uniform class TF(1, L, Q), also have define notion of polylogspace- uniformity, which can be defined analogously to logspace-uniformity (see Definition B.3).
In the logarithmic precision case, the classes TF[T., .] |] are defined analogously, with p(n) replaced by p(n) = clog n. We denote by TF, the family of Transformers with depth < I.
3.5 Logspace Uniform Transformers
Prior work on Transformer expressivity has largely focused on two extremes of uniformity. On the one hand, Li et al. [22] analyses non-uniform Transformers, where separate parameters can be freely defined for each input length effectively allowing different models for different input sizes. On the other hand, Merrill and Sabharwal [27] consider Transformers where the positional encoding function d(i) is the same for all input lengths. If want allow the embedding size increase for longer input sequences (necessary in the constant precision case), our embedding function must be
"2p(n) have p(n) bits before the fixed point and p(n.) bits after.

---

able to depend on n i.c. p(i, n). In practice, when model with larger context window is needed, often the embedding size increased (and whole new model is trained)
We introduce a logspace-uniforn Transformer class as a middle ground between these approaches. Our construction captures more realistic computational model while still enforcing constraints that prevent edge cases where Transformer families could encode undecidable problems through arbitrary variations in their parameters.
Definition 3.6 (Logspace uniform Transformer families), A family of Transformers {Tn } logspace uniform if there exists Turing machines Mi and M2 operating with logarithmic space such that: Mi takes as input 1 and outputs the weights and biases Tn; M2 takes as input 1 and the binary encoding of an index i and outputs @ n)).
This formulation allows for naturally size-dependent embeddings and weights but prevents freely designing entirely unrelated models for different n. This definition also allows us to draw natural connections with uniform circuit classes, ensuring that expressivity results reflect constraints efficiently computable models rather than arbitrary, hett--lengt---specffe designs.
Expressiveness of Transformers with pause tokens
Given the empirical improvements observed with pause tokens, a natural question is whether these tokens simply aid optimisation, fundamentally alter the Transformer's expressivity. In this section, we present our main theoretical contributions, which establish a rigorous computational foundation for increasing Transformer expressivity with pause tokens.
4.1 Constant precision Transformers and AC
We begin with the case where the Transformer operates with constant- pprecist-rreciiion arithmetic. Under- standing expressivity in this regime has become more important due to the widespread use of low-bit quantized LLMs. First, we show that the class of constant-precisien Transformers with polynomial number of pause tokens is equivalent to AC This demonstrates that the pause tokens can act as intermediate computational units, allowing Transformer to effectively encode the computation of Boolean circuit within residual stream.
Layer 24
Layer 26
Ary
Type
Topc
Tokens circuil layers S
Tokens for circuit layers [++
Figure 1: Two layers of Transformer with pause tokens can simulate layer of a Boolean circuit. In the first layer, inputs to the gates in the layer are copied argument positions. In the second layer, these arguments are combined at the gate position to compute the output of the gate. U; represents the value of vertex in the circuit, whether that be an input or a gate. Arg(i, j) tokens denote an edge from gate to gate i, and Type(i) tokens denote gate i. The red arrow represents the direction of computation.
Our first result demonstrates that TF(1, I,, P] is computationally equivalent to AC (both uniformly and non-uniformly), even when the Transformer has causal masking.
Theorem 4.1. TF L. P1 AC
For example, when moving from Llama2 to Llama3, Meta doubled the embedding dimension of the largest model and increased the context window from 4096 128, 000 tokens [2].
5

---

To prove this equivalence, we show that (1) any function in AC can be computed by a Transformer in TF[1, L, Pl. and (2) every function computed by such a Transformer is in AC We sketch a proof below.
Simulating AC" with Transformers. Let Cn be a logspace-uniform AC circuit family computing a Boolean function f: 10, + {0. 1}. We construct causally masked Transformer that simulates Cn as follows:
Token representation: The Transformer receives as input sequence of length n encoding a binary string A polynomial number of pause tokens are appended, each representing an edge vertex
Cn-
The Transformer's positional encodings represent the structure of Ca. specifying the connectivity between input bits, intermediate gates, and the final output gate. Attention weights ensure that each gate token attends only to its input tokens.
Positional encodings:
Computation by Transformer layers: Each pair of Transformer layers 2 + and 2k- + mimic a single layer of the circuit Cn2 The first attention layer copies the values of previously computed gates to the edge tokens, and the second attention layer computes the (rounded) sum of the inputs each gate (see Figure [). The feedforward layers are used as thresholds to compute the exact bit value of the gate output.
full construction, including explicit positional encodings, weight matrices, and feedforward computations can be found in Theorem C.1
Transformers are contained in AC Every function necessary to implement a Transformer in TF[1, L, P] can be implemented by an AC circuit. The positional encoding function is logspace- uniform, with O(log n) size outputs, and is thus computable in (uniform) AC 27 Attention mechanisms and feedforward layers involve multiplication, division and exponentiation of constant amount of constant precision numbers, and addition of at most polynomial amount of constant precision numbers, all of which are in (uniform) AC Since a Transformer has a fixed number of layers, its overall computation is in AC See Theorem C.5 for the detailed proof.
Given this equivalence, we can move on to proving separations between Transformers with and without pause tokens. Our next result demonstrates that in the non-uniform case, Transformer with polynomial number of pause tokens is strictly more expressive than one without.
Corollary 4.2. For the non-uniform class of Transformers, TF[1, L,0 & P..
follows from the result of Li al. 22 that TF[1, I., O] &. AC Without pause tokens, the number of available computational units in the Transformer is limited by the sequence length We can obtain an upper bound on the size of the circuits it can simulate by considering the size of the circuits that can simulate it. This will be of some fixed polynomial size O(n²) (dominated by the size of the circuit needed to add n numbers). By the non-uniform size hierarchy for Boolean circuits [.] there exist functions in non-uniform AC that require circuit size greater than On The class of Transformers without pause tokens is strictly less expressive than AC and therefore less expressive than P..
In the uniform case, the separation weaker, as there no equivalent of the non-uniform size hierarchy. Instead, we make of the fixed-depth uniform size hierarchy for AC (see Lemma D.3 to prove separation for Transformers of some fixed depth l.
Theorem 4.3. For the uniform class of Transformers, TF L, LF,
In this case, our separation is between fixed-depte Transformers with no blank tokens, and those with a quasi- mousi-pplynomial number of blank tokens (for the proof see Theorem D.4).
It should be clear that the addition of pause tokens does not enable the Transformer class to solve problems that require more serial computation steps, but instead increases the parallel width of computation. While it seems intuitively obvious that deeper Transformer (still of fixed depth) that can perform more sequential steps is more expressive, not immediately obvious what is not computable at a fixed depth with a polynomial number of pause tokens. In the interest of rigour, we prove the following lemma.
Lemma 4.4. For any depth there exists constant > I such that TF C TF [1, PI.

---

The proof of this lemma is based on the result of Hastad [17, who showed that there exist functions within AC1+1 that are not computable by any poly-size circuit in ACI.
1+1
4.2 Logarithmic Precision Transformers and TC
In the previous section, we established that constant precision Transformers with pause tokens are equivalent to AC We now extend this analysis to (uniform and non-uniform) logarithmic preciisii Transformers, showing that they are equivalent to the strictly larger class TC constant-depth Boolean circuits with threshold gates.
Theorem 4.5. TF L, TC
This result is equivalent to that obtained in Merrill and Sabharwal [27]. that Transformers with polynomial advice (extra input to TM that is allowed to depend on the input length but not the input itself) contain TC but our definition of Transformer uniformity leads to equality in the uniform case.
The proof structure is very similar to the constant precision case, with the key difference being that logarithmic precision allows attention layers to perform threshold-like computations, as required to simulate TC In the reverse direction, it is necessary show that the iterated of a polynomial amount of logarithmic precision numbers is in TC For the full proof, see Appendix C.2
While this result establishes theoretical equivalence, we are unable to prove strict separation between TF|L, L, 0] and TF|L, L, P] as we did in the constant precision case. Unlike AC where several superpolynomial bounds are well established, TC lower bounds are still open area of research. The best known wire lower bounds for TC are of the form n It- for some > 1, and a TC" circuit simulating a Transformer trivially requires (2(2)) wires due to the attention between all tokens 7
Experiments: learning parity with pause tokens
Parity as TC benchmark. Parity is canonical problem within TC separating AC from TC by requiring threshold-like computations to count the number of set bits modulo 2 [13]. While we are unable to theoretically separate TF[L, L, 0] and TF|L, L, Pl, prior work has established that learning parity is difficult for Transformers without pause tokens [3]. Our experiments investigate whether pause tokens enable practical learning of parity in a 2-layer Transformer.
We hypothesize that some the observed performance increases afforded by pause tokens are due to the restrictive nature of causal masking in decoder-only Transformers. This masking limits the model's 's ability to aggregate information globally over the input sequence, as only the final token can attend to the entire sequence. For parity, a standard construction for 2-layer threshold circuit involves n threshold gates in the first layer, with each gate taking all n input bits as input (i.e. global information, see Appendix E). A causally masked Transformer may struggle to simulate this, while pause tokens, by providing additional "gates" that can attend to the entire input, offer a mechanism to bypass this bottleneck.
Our main reason for focusing on the TC regime is practical. To effectively simulate the AC regime would require that our precision log n. requiring either scaling the input unrealistic lengths (for our compute budget) with full precision or training heavily quantized models, which we found to be unstable and non-performant.
Experimental setup. We train a 2-layer, 4-head GPT-2-style Transformer [32 on bit sequences of length E {20,... 300). The model is trained to compute the parity of the input sequence, where the final token's 's output used for classification. To study the impact pause tokens and causal masking, consider the following scenarios: instant answer with causal masking; instant answer without causal masking; and n pause tokens (with causal masking). Training details are in Appendix
Hints. We found that in all regimes, gradient- training for shallow Transformer struggles to learn parity using only the loss on the final prediction (never performing above chance at any length). Therefore, follow Pfau et al. [30 in providing additional "hint" labels during training.
7

---

For the non non-causal and pause token Transformers, this is in the form of the threshold values t, = = 2; 2 j] for all j E [1. This hint analogous to operations performed by the first layer of the reference 2-layer threshold circuit for parity. When training with pause tokens, we compute the loss of the final prediction, and with respect the hint over the pause tokens, as depicted below. This additional supervision directly encourages parallel threshold-like computations
Input Labels
Zn
-1
END ... bn PARITY,
h
Loss mask
When training the non-causal Transformer without pause tokens, we use the same hints, but located below, with loss computed over all tokens.
Input Labels
In la
END PARITY
For the causal Transformer, the hint has to be serial, as it cannot compute threshold values for the entire sequence at any token but the last. We provide serial hints in the form of subparities: for token zj. the label is the parity until index j. Pj = P. In the instant answer regime, the loss is computed over the entire sequence below.
Input Labels
In
END PARITY
P1
Pn
Results. We can see in Figure 2 that with causal masking and no pause tokens, the accuracy of the Transformer on parity falls to random guess- ing by the time the sequence is 100 bits long. The removal of the causal mask allows the Trans- former to achieve near-perfect accuracy until the sequence reaches 200 bits, providing support hypothesis that causal masking leads to bottleneck when the Transformer needs global information. However, pause tokens provide non-trivial gain above and beyond removing the causal mask, suggesting that there additional benefits over providing extra tokens for global information aggregation, even for the case of parity where the required circuit size should sim- believe these
0.0
Accuracy
0.1
0.2
Non-Causal
Causal
Sequence Length
Figure 2: Test accuracy on predicting the parity of sequence for Transformers with learned posi- tional encodings, with and without pause tokens and causal masking. Averaged over 3 random seeds.
ply be linear in n. Specifically, pause tokens can act as dedicated "workspace" positions that simplify how the Transformer routes and aggregates information across the sequence. Having separate tokens for intermediate or partial computations can reduce the complexity of attention patterns in a way that is not possible without them.
Our empirical results suggest that, in causally masked Transformers, if task requires global infor- mation, pause tokens can allow it to learn the task more easily, provided an appropriate signal is provided during training. This could help explain improvements on tasks like question-answering and mathematical reasoning, where the entire input is relevant to the final answer.
Discussion
The role of pause tokens. Our findings suggest that pause tokens can enhance the computational expressivity of Transformers, particularly in the constant precision setting. In constant precision settings, pause tokens allow Transformers express all of AC", and in logarithmic precision settings,

---

this increases to TC This provides a theoretical underpinning to the empirical results of Goyal et al. and Pfau et al. [30]
14
is known that CoT with a polynomial number of steps allows Transformers to compute everything in P (uniformly and P/poly non-uniformly). It is not proven, but it is widely believed by complexity theorists that TC ç P/poly, which would imply that log-precision Transformers with CoT strictly more expressive than those with pause tokens. In fact, a Transformer with CoT only requires depth 2 to compute anything in P/poly [22], which suggests that for fixed depth, it is strictly more powerful. However, CoT requires running multiple forward passes through the Transformer (up to poly(n) for full P/ p/poly expressivity). while pause tokens provide their additional expressivity within a single forward pass. This suggests that the two mechanisms may be complementary in improving Transformer performance, with pause tokens offering a more parallel form of computation.
That said, the practical utility of pause tokens appears limited. The theoretical gains require a polynomial number of pause tokens, and in practice models struggle exploit this capacity effectively. These factors likely explain the weak empirical results reported by Burtsev et al. [5] and Lanham et al. 21.. Pause tokens can only help when the task demands additional computational "width" rather than depth, may require orders of magnitude more pause tokens than input tokens, and empirically need specific training strategies to become useful.
Chain-of offtthtght faithfulness. A natural concern is whether pause tokens introduce an additional layer of obfuscation in Transformer reasoning. Some prior work has suggested that thain-of-though (CoTT) reasoning can be misleading, in the sense that models may generate intermediate reasoning steps that are causally linked to the final prediction [77. Given that results establish theoretical advantage of pause tokens in expressivity, it raises the question of whether a model could use such tokens obfuscate computations.
Our findings suggest that the risk of pause tokens being used for deceptive reasoning limited. Unlike CoT, pause tokens are only useful for more restricted class of problems (under the conjecture that TC Ç P), and training data for reasoning tends to be in the form of sequential computation steps, rather than parallelizable as would be necessary to utilize pause tokens. seems likely that the default learned behaviour of a Transformer, especially one trained via next-token prediction, will be to generate tokens that are meaningful to the problem it trying to solve, Even in the case that a model does learn to make use of intermediate filler tokens, Bharadwaj [ demonstrates that non-obfuscated tokens can be recovered from the intermediate layers.
Quantization. Our results offer insights into how quantization affects Transformer expressivity. Specifically, we show that if both weights and activations are quantized to constant precision, the model is limited to AC expressivity. However, if only weights are quantized while activations retain logarithmic precision, the Transformer remains in TC with the caveat that we need exact thresholding in the feedforward layers.
This follows from our proof that TC S TFIL, I, P] (Theorem C.7 which does not rely on weights having logarithmic precision except to perform thresholding in the feedforward network. The self- attention mechanism does not impose an expressivity constraint with constant precision weights (and saturation arithmetic), as long as the embedding dimension and activation precision remain log-size. This suggests that in mixed precision Transformer models, the expressivity bottleneck may be in the non-linearit of the feedforward network. If threshold-like behaviour can be implemented at sufficient precision, the model retains TC expressivity even with weight quantization.
7 Future directions and limitations
Our theoretical results rely on specific choices in modeling Transformer computation, particularly regarding numerical precision and arithmetic operations. Here, we outline future directions for refining these results and addressing some of the limitations.
Saturation arithmetic and circuit complexity assumptions. Our proof that TF L, PJ AC relies on the use of saturation arithmetic to allow the Transformer to attend to a polynomial number of locations when simulating AC gates with polynomial fan-in. While this assumption is a reasonable approximation to practical implementations of quantized neural networks, changing the arithmetic definition can change the expressivity of the models. It is possible to replace saturation arithmetic

---

with modular arithmetic and still demonstrate that AC S TF P). but this breaks the equivalence as modular addition is not in AC (in this case the Transformer belongs to ACC*). Further work could analyse the expressivity under different numerical assumptions.
Tighter bounds on the expressivity of TF.. For the non-uniform setting, we are able to prove a strict separation between TF[1, L, 0J and TF[1, L, PI. However, in the uniform fixed-depth setting, our separation requires a quasi-polynomial number of pause tokens. Stricter upper and lower bounds on the expressivity of fixed-depth Transformers could lead to stronger separations between uniform Transformers with and without pause tokens. In the logarithmic precision case, tighter bound might enable the use of the depth TC super-linear gate and super-quadratic wire lower bounds of Kane and Williams [20] to separate very shallow Transformers with and without pause tokens.
Separating TF L, and TFIL, L, Pl. While we prove that TF[L, L, P] TC, we are unable to show that TF[L, L, 0j & TFLL, L, Pi. This primarily due to the lack of known superpolynomial lower bounds for TC cireuits, long-stane mon-sttnding open problem in circuit complexity. such bounds were established, they could lead to provable separation between Transformers with and without pause tokens in the logarithmic-precssonn regime. Alternatively, perhaps approaching the problem from the Transformer side could provide some intuition for improving TC" lower bounds. Empirically, our results suggest that pause tokens can significantly improve the ability of causal Transformers to learn global functions, but we leave formal separation results as an open problem.
Expressivity vs. learnability. Our work focuses entirely on what Transformers with pause tokens can compute, but provides no theoretical results on whether they can learn to use this additional expressivity effectively. Empirically, we (and Pfau et al. (30]) observe that pause tokens can improve performance, but only when parallelizable explicit supervision provided. An avenue for further research is to theoretically analyse the learnailiity of Transformers with pause tokens, to determine whether gradient-ban based training can access the full expressivity benefits.
Acknowledgments
The authors would like to thank Hanlin Ren for illuminating discussions on several circuit complexity results. CL was supported by the Engineering and Physical Sciences Research Council, grant number EP/W524311/7
References
[1] Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.
[2] Aryasomayajula Ram Bharadwaj. Understanding hidden computations in of reasoning, 2024. URL http::ttt///rrrtt http:://axxvvvvoo http://rg///bb///eeeee 04537
[3] S. Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers recognize formal languages. In Conference on Empirical Methods in Natural Language Processing, 2020. https:/// www.nticsccoooooooooo wwwphhollroooo//ooooo
222225236
[4] Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the representational capabilities of transformers and recurrent architectures. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https
//openreview hwt::/oorrriiii--HHUUUUODWYT
[5] Mikhail S Burtsev, Yuri Kuratov, Anton Peganov, and Grigory Sapunov. Memory transformer. arXiv preprint arXiv:2006. / /527, 2020.
[6] Lijie Chen and Roei Tell. Bootstrapping results for threshold circuits "just beyond" known lower bounds. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 34-41, New York. NY, USA, 2019, Association for Computing Machinery. ISBN 978 77778455067059 doi: 10. 1 111144/3333276.3316333333
htlp.htts:://dde //rg//oo//o////////////////
10. 1 10.1144/3313277 331 3336
10

---

[7] Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer transformer. ArXiv, abs/2412.02975, 2024. URL https://api. semaaaiiccacniicolca.aa /ttpss///pp...eaattsccoooobaaaas http://p...eaaaaooooooooooooorrp OrggCorppusID 274464787
[8] Mengzhao Chen, Yi Liu, Jiahao Wang, Yi Bin, Wenqi Shao, and Ping Luo. Prefixquant: Static guantization beats dynamic through prefixed outliers llms. arXiv preprini urXiv:2410.05265, 2024.
[9] David Chiang, Transformers in uniform TC Transactions Machine Learning Research, 2025.
[10] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, et al. Training verifiers to solve math word problems. arXiv preprint 1rXiv:21 2021.
[11] Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Marcus Hutter, Shane Legg, and Pedro A. Ortega. Neural networks and the chomsky hierar- chy, ArXiv, abs/2207.0200 2022. URL htthsttp:: //ap api www.nti org/ het//orrpssID
250280065
[12] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The Ilama 3 herd of models. arXiv preprint arXi::2407.2178. 2024.
[13] Merrick Furst, James Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory, 17(1):13-27, 1984.
[14] Sachin Goyal, Ziwei Ji, Ankit Singh Rawat, Aditya Krishna Menon, Sanjiv Kumar, and Vaishnavh Nagarajan. Think before you speak: Training language models with pause tokens. In ICLR, 2024. URL https:://ppenreeiieeeeee wtt.:e//ooorrmiddddodotoooo
[15] Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020. doi: 100000 URL
2020. 1ttp:///.o///0....01a111.11.111. tac1-1.11/
[16] Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard atten- tion transformers: Perspectives from eircuit complexity. Transactions of the Association for Computational Linguistics, 10:800-810 2022.
[17] J Hastad. Almost optimal lower bounds for small depth circuits. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC '86, page 6-20, New York, NY, USA, 1986. Association for Computing Machinery. ISBN (89991 1938. doi: 10.1 10.1145/12130.1215 URL htttt::///// org/10. 1145/12110. 12132
[18] William Hesse. Division is in uniform TC In International Colloquiun on Automata, Languages, and Programming, pages 104-114 Springer, 2001.
[19] Neil Immerman. Descriptive Complexity. Springer Verlag, 1998.
[20] Daniel M Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 633-643, 2016.
[21] Tamera Lanham, Anna Chen, Ansh Radhakrishnan, Benoit Steiner, Carson Denison, Danny Hernandez, Dustin Li, Esin Durmus, Evan Hubinger, Jackson Kernion, et al. Measuring faithfulness in chain-of-thought reasoning. arXiv preprint arXiv:2307.13702, 2023.
[22] Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. In The Twelfth International Conference Learning Representations, 2024. URL
net/ferunu Fid=3EWTEyWyTTT
[23] Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. fixed-depth hierarhyy theorem for AC via the coin problem, 2019. URL. https //arxiv. org//rg///.....oooo.. abs//809..... 04092

---

[24] Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Trans- formers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations, 2023. URI.
[25] Robert McNaughton and Seymour A. Papert. Counter-Free Automata (M.L.T. research mono- graph no. 65). The MIT Press, 1971. ISBN 0262130769.
[26] William Merrill. Formal languages and neural models for learning on sequences. In International Conference on Graphics and Interaction, 2023. FRRI.ttpss: :/api: wwwanticscoolllrrr.......... http:p///ppp...eaanccccccco..... org/ CorpusID:26110190
[27] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023,
[28] William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreevex. httpppprrrrrrreeeeeeeorruuddaada hidiorrnnnnniddiiidihhhahhhaa
[29] Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture. ArXiv, abs/2402.08164, 2024. URL https: //api. gemanticschola.. org/
CorpusID: : 20::6676333 267666555
[30] Jacob Pfau, William Merrill, and Samuel R. Bowman. Let's think dot by dot: Hidden computa- tion in transformer language models. In First Conference Language Modeling, 2024. URL
https://openreeiiee www.///eu//mniiiee http:/orrmuddddiiiibdrttttt
[31] Jorge Pérez, Javier Marinković, and Pablo Barceló. On the turing completeness of modern neural network architectures. In International Conference on Learning Representations, 2019.
URL
[32] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9 2019.
[33] Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers, ArXiv, fbs/2300.02896 2023. URL
org/
[34] Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal lan- guages can transformers express? a survey, Transactions of the Association for Computational Linguistics, 12:543-561, 2023. URL httpp:://pp. ftttpss//ap..smmntticchhoo///// semantccscoolar. Drg//CoppsID; 264853196
[35] Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsensequ: A question answering challenge targeting commonsense knowledge. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pages
2019.
[36] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprini
2023.
[37] Miles Turpin, Julian Michael, Ethan Perez, and Samuel Bowman. Language models don't t always say what they think: unfaithful explanations in chain-of-thouge prompting. Advances in Neural Information Processing Systems, 36, 2024.
[38] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 6000-6010, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860966
[39] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoe Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL. forum?ide Prrum?dd=Viilliee diaddd=_jjMMMM______
net/
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All theoretical claims are supported by complete proofs, and all assumptions are stated. The empirical claim regarding learning parity clearly presented as supportive but not definitive.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss several limitations in detail in Sections 6 and 7. These include assumptions of fixed-point and saturation arithmetic, and that separations in the logarithmic precision regime remain conjectural. We also note that it is possible to construct experiments that exactly match theory in the limit.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
13

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical results in the paper are fully formalised, with explicit assump- tions on numerical precision, saturation arithmetic, masking behaviour, and uniformity. All proofs are provided in the appendix and cross-referenced from the main text. Where theorems rely on known results (e.g., Hastad's ' switching lemma, depth-hierarchy theorems), these are appropriately cited and the proof' clearly state their dependence.
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Yes, code to reproduce the experimental results is provided in .zip file, and experiment hyperparameters can be found in the appendix (and the code).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
14

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: Code reproduce the experimental results is provided in .zip file, along with a shell script to run all experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
public/guides/ Saaaaddee/ooeeSummsiiiiooeoeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ mnaps.cc/publcc/uuudee
www.bbmmmnsioooooooiy.c for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Brief experimental details are provided Section of the main paper, and full details can be found in the appendices and code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: We do not report statistical significance or error bars. Our experiments serve primarily as illustrative case studies to support the theoretical claims, and we run small number of seeds sufficient to observe the key qualitative differences discussed.
15

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative етгог rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments can be run on a single V100 GPU, as detailed in the appen- dices.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httph:ttt////ttt http://rrrrpp..cpppppbb/cehcchee
Answer: [Yes]
Justification: Our work consists entirely theoretical analysis and synthetic experiments on algorithmically generated data (bitstrings). There are foreseeable ethical concerns, nor is any sensitive data or human subject data involved.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
16

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We assess our work as having no immediate socictal impact. as it is purely theoretical study of Transformer expressivity under idcalised conditions. Any downstream impacts would depend on further engineering or empirical deployment, which we do not pursue in this paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work does not release any model or data with dual-use or misuse risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
17

---

Justification:
The original GPT-2 paper [32] is cited, and the Huggingface implementation is used under Apache license. All data used was generated as part of the project.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssittcooeee thoode com datasetss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new datasets, models, benchmarks.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemmodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our study does not involve crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
18

---

Answer:
[NA]
Justification:
No human subjects research involved.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were used only for non-substantive code generation and copy-editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy htttg://aaarrsse.c////ooeeeeeees for what should or should not be described.
19

---

A Further related work
Communication complexity. A related line work has considered Transformers from commu- nication complexity perspective, though these results mostly applicable single-layer models. Peng et al. [29] use communication complexity techniques to show limitations the representational power of single-layer Transformers, while Sanford et al. [3] and Bhattamishra et al. [4] use them to contrast the expressivity of Transformers and recurrent models. More recently, Chen et al. 7 have extended some of these results to the multi-layer case.
Formal languages and automata. Many papers have analysed Transformers through the lens M1. attempting to determine the class of languages that they can recognise. Liu et al. [24] proved theoretically that Transformers with Oloog n) depth can simulate all finite-state automaton on inputs of length n, and so require depth that increases (mildly) with input length to capture all regular languages.
of formal languages [3] 34 26
B Logspace uniformity and circuit descriptions
A logspace Turing machine may not have the space to write down its output, if the output size is ((logn)) n). For this reason, we instead require that the TM can compute any desired bit of the output in logarithmic space, i.c. it is implictly logspace computable [
Definition B.1. (Implicitly logspace computable) A function f {0. 1} + f0, 1 is implicitly logspace computable the mapping x, + f(x); can be computed by Turing machine using logarithmic space.
Definition B.2. (Logspace uniformity) A circuit family {C,,} is logspace-uniform if there is an implicitly logspace computable function mapping 1" the description of the circuit Cn,-
Definition B.3. (Polylogspace uniformity) circuit family (C,, } is logspace-uniss uniffrr there an implicitly polylogspace computable function mapping 1 to the description of the circuit C...
We will define circuit descriptions Des)(C,,) for C. as a topologically ordered string of vertices, Vertex(1),.... Vertex([Cxl), where the first vertices correspond to input variables Inp(1)..... Inp(n), and the remaining vertices represent logic gates. For AC circuits, each gate vertex Vertex(i) is defined by the string:
1. Arguments: Args(i,j), which specifies that the output of vertex j serves as an input to vertex
2. Type: Type(i), indicating the gate's operation (AND, OR, NOT).
For TC cireuits, Vertex(() is defined by the string:
1. Arguments: Args(i, which specifies that the output vertex serves as input to vertex i.
2. Direction: Dir(i), which species if the threshold gate is > <.
3. Threshold: Thresh(i), numerical value 0 representing the threshold for activation of the gate.
The topological order ensures that if we computed the circuit in order from its description, all inputs vertex would already have been computed by the time the vertex itself evaluated. We will define the length of the description [Deso(C.)) as the total number of input, argument, and type or threshold strings.
C Transftrmer-cireuit equivalence
In this section, we will demonstrate the equivalence between Transformers with pause tokens, and the circuit classes AC and TC We will demonstrate the equivalence in the uniform case, but all the proofs still hold if these uniformity requirements are relaxed.
20

---

C.1
Constant precision
We will first consider Transformers with constant precision, p(n) (1). While full precision FP32 Transformer will almost always have precision 2 logn, n. for any realistic input length more and more LLMs being served with aggressive quantization, with 8-bit, 4-bit, and even 1.58-bit models becoming more popular. It therefore becomes necessary to understand the computational power of models under these circumstances. The constant precision regime also allows us to show strong separations between Transformers with and without pause tokens, due to the existence of universal AC lower bounds.
Theorem C.1. AC C L,
Proof. Consider any logspace uniform AC circuit family {Cn). Given Turing machine that generates the description of {Ca]. we can modify it to instead generate the position encodings and parameters of constant precision Transformer family } that simulates the circuits, using b(n) & (es)(C,,) pause tokens.
Positional encodings. We will construct positional encoding for every input symbol Inp( argument symbol Arg(i, and gate symbol Type(i). All encodings have dimension d(n) Ollog n),, and we will use the notation bin(i) to refer to the binary vector representation of 0 < S b(n), and sbin(i) = 2bin(1)
We will use a.") to represent the interleaving two vectors x and
y of the same dimensionality, so that (æ"y)2s y)2-1 = z; and (e"y)z = y;- Finally, we will define k()) = sbin(i) 1, and q(i) (sbinin(i) (-1)). This means that
ifi=j Bp otherwise.
k(i) q()
Post-cxponentiation, the pre-normalized attention values will be for i and 0 everywhere else. We reserve 0 as a privileged index, such that for all indices i in the circuit description ((0) ((i) - BB, Our position encodings will then take the following forms:
Inputs
((Ip(1)) = ((),0,, (1)).
Arguments
(0.00...(000)),kkk..()) ((rg((,.)) ((.
if Type(()) is OR otherwise.
Gates
if Typee()) is AND otherwise.
d (Type(i))
(0,0,0,
We will denote the positional encoding corresponding circuit Cn as Φ(C.). Given description of On in prefix form, (CC,) has the following structure
(CC.) = ((mpp()))...mmm()()))))
1.5)). ((Arg(n + 1, 1,K))) + 1)). (oT..
The input to the Transformer is then binary string r of length with b(n) = poly(n) pause tokens appended to We choose to use for the pause tokens to simplify the construction, but any fixed E F will work, as it can be corrected for in the feedforward layers. We append the position encodings at each position, to give vectors in O(logn) In matrix form, the encoded input appears
21

---

X
o Desc(Cn))
Transformer layers. For each individual layer in the AC circuit, we will construct 2 (causally masked) Transformer layers that perform the same computation. For an AC circuit of depth I, this will result a Transformer with 2/ (and hence constant) layers.
The proof proceeds by induction. If we assume that the first layers of the circuit have been computed correctly, then at each Ttpe(i) token location in the input preceding layer 1+ 1, we have the computed value of Vertex(i) U; (this is 24 for (n), and the recursively computed value for Tipe(i)). Each argument token Jr) will have value For (tpe(t) tokens in layers [ the value at this point can be arbitrary (denoted by D) as it will be overwritten. For convenience, we will denote the set of vertices in the first layers of the circuit C, by C, I I]. We will demonstrate that the next two Transformer layers correctly compute the output values for the gates in layer 1 + 1.
The first attention layer copies previously computed vertex values into the correct argument positions for layer I + 1. We construct WQK such that query
Inp(t) attends only to itself.
ji attends only to Vertex(j).
Type(i) attends only itself.
After softmax and normalization, we will have attention value of on the token u it attends to, and 0 everywhere else. The value matrix W will pass through the first index of the token attended (uz), and zero out everything else (explicit matrices for WQK and W can be found in Appendix C.3.1). Concretely, after the attention layer and residual connection, for each token type we will have
Inp(i) -2
if Vertex(j) E C,[S
Arg(i. +-
(4)
otherwise.
20
if Vertex(1) E C,|< !]
Type(i)
(5)
otherwise.
We get the factors of 2 due to self-attention and residual connections, but these are corrected for the feedforward network. We apply constant-depth feedforward network to each token u, computing U1 + l[(u) u2) * 0] U1 ui + O (for the ReLU network construction, see Appendix C.3.2 u2 is 1 if corresponds Arg(i. and Type(i) is AND or NOT, and otherwise. Therefore, post feedforward and residual connection, we have
Inp(i) 24
(6)
if Type(i) is OR and Vertex(j) E C,(s (], Type(i) is AND or NOT and Vertex(j) E C,| 4]. otherwise.
Ar) +-
1
Uy
(7)
0
if Vertex(i) E C
Type(i)
(8)
otherwise.
The positional encodings of tokens are unaffected by these layers, as they zero out the positional information, and the residual connections copy over.
22

---

The second Transformer layer then computes the gate outputs for layer / + 1. Due to our use of saturation arithmetic, we can attend an arbitrary subset of input locations with constant precision. The maximum value of the normalizing constant in the attention computation is Bp, and post- exponentiation attention values are either 0 I, so our minimal non-zero attention value is 1/ Bp 2 1/2", and so is still representable as a non-zero value, WQK constructed such that query
Inp(i) attends only itself.
jr) attends only to itself.
Type(i) attends to all Arg(i, )), and does not attend to itself.
WPV again only allows through u1. If we define m, as the input arity of Vertex(i). and define
r pp then the representation of each token after the attention layer and residual connection becomes
Inp(i) 4 20%
(9)
20
if Type(i) OR and Vertex(j) Cn I], if (ipe(i) AND or NOT and Vertex(j) E C 4]
Jr) t
2 - 20y
(10)
D
otherwise.
Σ Ld Arg(i.5)3
Type(i) is OR and Vertex(i) E Cn 1 1], if Type(i) is AND or NOT and Vertex(i) C. + 1], otherwise.
Type(i)
ls Arg(t.))) u1
(11)
The addition is iterated fixed point addition, but all we require that the result will be non-zero any of the addition terms is non-zero. The value of Type(i) will be if is: OR and any argument Vi = I; AND and any argument úi = 0; NOT and the argument v, = 0. Otherwise, the value will be The feedforward network will then compute
if 44 = 1 (u is an Arg token),
[ui 0) un 1/u1 >
if u. 0 and u3 (u Type(i) with type AND), (12) otherwise.
u1
Ui +-
(13)
where is any token. Combined with the residual connection, this feedforward layer sets un to 1 if
u1 = 0 and u corresponds to an AND gate, if u is an Arg token, and T[u > 0) for all other tokens.
We that for each token Type(r) in circuit layers < 1 if it
NOT: the first Transformer layer copies the arguments to the correct position and computes NOT (1 -y);; and the second layer copies to the gate location.
OR: the first layer copies all arguments to the correct position, and the second layer computes OR by summing the inputs and returning only the sum is >
AND: the first layer copies all arguments to the correct position and computes their NOT (1 - (1-e;), and the second layer computes the negation of the OR of the negated arguments, by returning only if the sum = 0. By De Morgan's 's laws, this is an AND gate.
Thus, following the evaluation of these two Transformer layers, the residual stream will now contain the value of all the gates in layers < / + 1 of the AC circuit, the input tokens are unchanged, and all arguments have value 0, required compute the next layer. Evaluating all 2/ layers will result in the final value of C, being output at the final position.
23

---

Lemma C.2. 127] Let f - (0, 10 be a linear space computable function. There exists Turing machine that, for all N and R+, uses at most clog n log m space to map input 1 an AC circuit of size at most ne + clog m and depth 3 that computes f on inputs of size at most e llog n.
+
Lemma C.3. (Li et al. (221) For any fixed E N, sump : (F₂) + Fp has uniform AC circuits.
Remark. While Li et al. [22] do not explicitly state that their construction is uniform, their proof hinges on the fact that constant precision saturation arithmetic is computable by counter-free free automata. Such automata recognize star-free languages, which are definable in FO[K] [25]. Since
FO[<] corresponds to DLOGTTIME-unifom AC 19] and DLOGTIME C I,, the construction logspace uniform.
Lemma C.4. Exponentiation [e"]] lp- multiplicationn [zy)] and division [x/vy]p of constant precision numbers z, E Fp has uniform AC circuits.
Proof. These functions are finite and can therefore be implemented as a constant-size lookup table. A logspace TM can trivially hardcode this constant-size circuit description.
Theorem C.S. TF(1, L, PJ S AC
Proof. We demonstrate that every logspace uniform Transformer with logarithmii-dimensioona embeddings, constant precision, and polynomial pause tokens be simulated by uniform cir- cuit family. The proof proceeds by decomposing the Transformer's operations into components computable AC
Positional encodings. By construction, our positional encodings can be computed in logarithmic space, with binary inputs i and n of dimension at most log n, and outputs dimension m log n. We can use logarithmic space to construct counter maintaining the index i (from 1 to b(n)) and construct constant-size circuits to convert é into binary. By Lemma
C.2 we can construct a logspace
Turing machine mapping 1 to the description of an AC circuit computing (ii,
Attention layers. We will prove that the action of single head can be computed in uniform AC and model uses constant number of heads, the action of the entire layer is in uniform AC Recall that the attention computation is defined as
x; t WV Σ exp(f(xr,, j=1
(14)
Zi
f(i,j) x WQK x
(15)
2, = Σ
(16)
j=1
First, we demonstrate that the attention function f has uniform AC circuits. By definition WQK K is logspace computable, and so we can determine any entry W can therefore be computed in logspace, by using a counters and / over the length of the vectors, computing each WrkQ WI (ax, )a (,) and storing the summation of these terms in constant space. By Lemma C.2 f is in uniform AC To do this for all query and key vectors, we can use two counters over the token locations.
KQ by simulating Mj using logspace. f
Exponentiation of these attention values and multiplication with vy can be done in uniform AC by Lemma C.4 Summation over the (up to poly(n)) attention values for calculating the normalizing constant and summation of the value vectors can be done in uniform AC by Lemma C.3
As V is logspace computable, we can construct logspace computable function to compute W.Z. 2, again by using counters over the indices of W This function has a logarithmic output dimension, and
use Lemma C.2 to prove that g has uniform AC circuit.
24

---

Feedforward layers. Each feedforward layer involves multiplying token vector with logspace computable weight matrix. Similarly to this is in uniform AC
As we have demonstrated that all Transformer computations for each layer are uniform AC", and we have constant number of layers. TF[1, L, P] S AC
Corollary C.6. TF L, P] P AC
C.2 Logarithmic precision
Theorem C.7. TC TFILL L,
Proof. Consider any logspace uniform TC circuit family }C, Given a Turing machine that generates the description of {Cn]. we can modify it instead generate the position encodings and parameters of constant precision Transformer family {T, that simulates the circuits, using b(n) Desc(C,.) pause tokens.
Positional encodings. Define k(i) and (i) as in the AC case, though Bp now refers to the largest representable number with logarithmic precision. The positional encodings are:
Inputs
(Inp(i)) (0.0,0.t(). (1))
Arguments
(Arg(i,))) = (0, (0,0,,,,(0).4)))),.))))) (i))
Dir(i) is (0, otherwise.
Gates
(0,00m,, 0, (x), (0. 0/m/ 0, k(), ((),, q())
(())
if Dir(i) otherwise,
((hrresh())
where 0 is the threshold value and m; is the input arity of the vertex.
(CCn) has the following structure
I ((mp))))) 1, @(Arg(n + 1, ( + + ((Tressoold((Caa))
((C.)) ((Inpp())..
Transformer layers. Again, we use two Transformer layers per circuit layer, and proceed by induction, assuming that all previous circuit layers have been correctly computed.
The first attention layer performs the same operation as in the AC case, copying previously computed vertices argument locations. The first feedforward layer computes
[lu > 0] ui
if U2 otherwise.
W1 +
(17)
[[ 0]
Ui 4-0.
(18)
Post feedforward and residual connection, have
25

---

Inp(i) tii
(19)
U
if Dir(t) is > and Vertex (j) E C 1). if Dir(i) is and Vertex (j) Cp 4]. otherwise.
Arg(i, x
U
(20)
if Vertex(() E Cx otherwise.
Thresh(i) <-
(21)
The second attention layer also acts in the same way as in the AC case. However, due to the logarithmic precision we no longer have potential overflow when attending to poly(n) argument locations, and the attention layer will be able to attend to all arguments with attention weights summing to 1, that averaging of the inputs is performed correctly. After the attention layer and residual connection we have
Inp(i)= 22;
(22)
20j
if Dir(i) is > and Vertex(í) E C [], if Dir(i) is < and Vertex(j) Cn [], otherwise.
Arg(
20g
(23)
Σ Gi Arg((.5)) Vj ([]())()))) -i
if Dir(i) is > and Vertex E C2 ++ Dir(i) is < and Vertex(i) C,[s/+1] otherwise.
Thresh(i)
(24)
The second feedforward layer will compute
U1 + -1 [[(u - -ua) > 0] un
u4 = 1 (u an Arg token)
(25)
otherwise,
4- 0
(26)
For every token type, have
Inp(i)= 4-2
(27)
Jrg(i, +0
(28)
Σ li | Ang(E.))) >
if Dir(i) is > and Vertex(i) E Ca(s 1+ 1), if Dir(i) < and Vertex(t) E C.|S++ 1], otherwise.
Thresh(i) +
I
Eg Arg(F.)) 0/
(29)
These the correct output values for the threshold gates in layers < <1+1, 1, and we have ensured that we have the required residual values to compute the next layer. Evaluating all 2/ layers will result in the final value of C, being output at the final position.
Lemma C.8. (Merrill and Sabharwal (27). paraphrased) For any p(n) O(log n), the function
sump(()) (F p()))) + Fiin) has uniform TC circuits.
Lemma C.9. [18 Multiplication and division of two n-bit numbers is in uniform TC Lemma C.10. Exponentiation [ea] "ptn)) of an p(n) O(log n) bit number is in uniform TC
Proof. By Hesse 18]. iterated multiplication of n n-bit numbers in uniform TC As exponen- tiation of an p(n) O(log n) bit number can be seen as iterated multiplication of n constant bit numbers, it is in uniform TC
D
26

---

Theorem C.11. T, PI C
The only difference between this proof and the constant precision case is that we must be able to perform the required arithmetic with logarithmic precision. By Lemma C.8 Lemma C.9 and Lemma C.10, all the necessary arithmetic operations are in uniform TC Corollary C.12. TC = TF PI
C.3
Model parameters and feedforward networks
C.3.1 Attention weights
First layer:
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
WoK
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
0
0
0
0
Second layer:
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
WoR
WV
0
0
0
0
0
0
0
0
0
100
0
0
0
0
0
0
0 0 0
These weights encode a very simple connectivity pattern and can easily be constructed in logspace.
C.3.2 Feedforward networks
Constant precision. We first define ReLU function
(a-1))
29 )
g(a) BB (ReLU(a)+Rel))
(30)
Bp and 2 are the largest and smallest representable positive values in F,, and as [B,/29] = 1,
g(a) I[a 0). The first feedforward network in our Transformer computes [[(u] u2) * 0 U1. which can be done by the following ReLU function
g(u - uz) + g(us u1) ReLU(u;) - ReLU(-u,
(31)
implementable by 3-layer feedforward ReLU network.
The second feedforward network computes
ReLU(1 g(u1) us 4n 1) ReLU(g(u)) Uy -us) ReLUUu)) ReLU(-u1).
(32)
implementable by 4-layer feedforward ReLU network.
27

---

Logarithmic precision. We use the same but now defined over 13 pp(n), where p(n) Oloo n).
The first feedforward network computes
(Re) + + - +)+ + (ReLU(g(ui) u2) - ReLU((u)) - ReLU(-ui)) (33)
implementable by 4-layer feedforward ReLU network.
The second feedforward network computes
ReLU(g(u; - -u3) - -u) - ReLLU(u) ReLU(-u1),
(34)
implementable by a 4-layer feedforward ReLU network.
D Separations in expressivity
We will use the notation (In)) (and [M())) to define the class functions computable by AC (TC*) circuits with (h)))) gates/vertices.
D.1
Non-uniform constant precision Transformers
Lemma D.1.
(22) L, AC
Proof (sketch). The crux of this argument is that when the Transformer has only tokens and d(n) (log v.) embedding dimension, it can be simulated by AC (n*) for some fixed k: e N, as all positional encoding, attention, and feedforward operations are computable by fixed polysize eircuits. can therefore always find some non-uniform AC circuit with size n* where S k', such that the function computed by this circuit is not in TF[1, L, 0].
This is no longer the case when the Transformer is allowed poly(n) (n) pause tokens, as an AC circuit simulating this Transformer must be able add poly(n) Ukenn terms compute the attention layer, and cannot be of fixed size n.
Corollary D.2. For non-uniform Transformers and AC L, & TF,L,
Proof. By Corollary C.6 TF[L, L, P] P|= = AC", and by Lemma D.1 TF[L, L, ACO.
D.2 Uniform constant precision Transformers
In the uniform case, is more difficult to construct function fü for all k E N such that fs E AC and fk & AC [n However, we can do this for fixed-depth circuits using the tight AC lower bounds for parity 13
Lemma D.3. (Limaye et al. (23), paraphrased) There exists a fixed depth size hierarchy for uniform AC such that ACI [n Ç [n for some fixed < 1.
Proof (sketch). This result Hastad states that any depth-/ AC circuit for parity of variables must have size 20(+ which is tight due to the folklore depth-l AC upper bound of 20(xt(11), These bounds give separation between circuits of size < e < 1. The same separation holds between sf and s for any s < so, by taking the parity function < variables. If we take s(n) O(n*) (m (n)) between AC [x]] and [n](
20( and si for some fixed
obtain separation
This separation holds in uniform AC", parity over (A: log -1 bits can be computed via simple uniform divide-andd-ooquer approach that computes the parity Olog n) bit chunks parallel at each layer.
28

---

Theorem D.4. TF 0, & TF,
Proof. By a similar argument to Lemma D.1 we have that TFi L, S [n for some k E N and 0
1. By Lemma D.3 know that there is some function In over suitably chosen potylog(n) bits such that fn [n] and Ln [n"
By Theorem C.I we know that TFi[L, L, [Decc(Cn) can compute any function computed by circuit of depth 1/2 with [Cn, unbounded fan-in AND, OR, and NOT gates. By the parity bounds, we know that depth 1/2 circuit of size [C,,] = 20( (m=2//003)) /(--)
can compute parity over m input bits. For
m poolyoo(()) n.). this is munsi-polynomill in [Desc(C,) cannot be more than quasi- pousi-pplynomiall in [C2], and so the number pause tokens necessary to compute the function still quasi maasiiipllnomiall..
Therefore fn & TF, I, 0] and Jn E IQQ] It is intuitively obvious that TF: L, 0] [1 L, Q). and so the proof complete.
C
D.3 Width cannot compensate for depth
should clear that the addition of pause tokens does not enable the Transformer class to solve problems that require more serial computation steps. instead increasing the parallel width of compu- tation. For finite-depth, constant precision Transformers with up to poly(n) pause tokens, we will always be limited to the class AC A prudent question is whether, within this class, increasing the depth of the Transformer increases its expressivity? This seems intuitively obvious, but we provide formal proof below.
Theorem D.5. For any depth i there exists constant > I such that TF L, P! & TF L, P]-
we have that ACI/2 S. TF,[L, S. ACH. By the result of Hastad [17, there exist functions in AC that are in ACO (with polynomial size). Therefore, TF. [1, L, Pl. where m 2 2l', is strictly more expressive than TF, L, PI.
Proof. By Theorem C.1 and Theorem C.5
E
2-layer threshold circuit for parity
Let a.... Fn 10, } be the inputs. Define Σ Zz.
First Layer: For 1, ..,.,, construct threshold gate
Gk =
k
In other words,
1 if k;
G 0 otherwise.
Note that exactly G1, G2,..., G2 will output 1, and the gates Gstly..., Gn will output 0.
Second Layer: Introduce one additional threshold gate F that takes inputs from GI...., Gu:
Σ (-1)+t
G.
Correctness:
1
Σ
(-1) ++ G Σ (-1
This is a simple alternating sum of and -1 for terms, which is s is odd, and 0 it is even. Therefore,
a E-1) G 2 1 is odd.
F=1
Thus F outputs exactly when the number of I's among 31,..., Fn odd, i.e. F computes the parity function.
29

---

F Experiment details
All experiments were conducted using a single NVIDIA V100 GPU, The model a custom variant of Huggingface's s GPT-2 implementation, to allow for different input dimensions and position encodings. Our Transformer model uses layers, attention heads, and a hidden dimension of 32. Positional encodings are learned during training. All models are trained for 50 epochs using the Adam optimiser with a learning rate of x 10 10-1, B1 0.9, 32 = 0.999, and no weight decay. We disable mixed precision and gradient clipping, as the models are small and training is stable.
Validation accuracy is monitored each epoch, and the model achieving the highest validation accuracy is used for test set evaluation. Training, validation, and test datasets consist of 500,000, 5,000, and 50,000 examples, respectively. The datasets consist of uniformly sampled bitstrings. where the label is the parity. We generate a dataset per random seed for each length in {20, 50, 100, 150, 200, 250, 300}.
All experiments logged using Weights & Biases, including batch and epoch metrics. Models saved every 5 epochs and upon reaching a new maximum validation accuracy. The final test accuracy reported in the plots is averaged over three random seeds.
G Attention pattern analysis
Here we analyse the positional attention patterns of trained models in each class of causal, non-causal, and pause tokens, to try and understand what mechanisms//llorrihms they may be using compute the parity.
To compare attention distributions across positions, transform raw attention weights p(k: q) for query position and key position & into a symmetric normalised form that measures deviation from uniform baseline while remaining bounded and zero-centred. Let Ket(g) denote the number of unmasked keys visible to query and define the uniform reference distribution U Ulk q) = L/KeH(()) We first form the likelihood ratio
p(k q)
rkk 4))
Kotf (4) p(k g);
U(k 1)
which quantifies how strongly query q attends to key relative to a uniform baseline. To obtain symmetric, bounded representation, we define
Kott (ạ) p(k 9) 1
SLR(k 9) =
E (-1,1).
Ken (q) p(k 9) +1
Here SL.((k q) O corresponds to uniform attention, positive values indicate higher-than-unifomm weighting, and negative values indicate suppression relative to the baseline. This symmetric log-ratio (SLR) mapping preserves the ordering of the original likelihood ratios, compresses large deviations, and provides bounded scale suitable for visual comparison across layers and heads.
In Figure we can see that the unmasked and pause tokens models attend very uniformly to all tokens in the first layer, would be expected if it were implementing method similar to the 2-layer threshold circuit described in Appendix E In the second layer, the first two heads the pause token model attend largely to pause token positions (rather than input tokens), again corresponding circuit. However, it does not attend heavily to all the pause tokens, suggesting some divergence from this mechanism. The non-causal model attends layer 1, as would be expected if it were using the threshold circuit mechanism. The causal model has less structured attention patterns that elude easy analysis.
the
all tokens when combining head 1 and head 2 in
30

---

Positional attention causal
lasn Heal
Loper Maat
Lapst 0 %
Loge 2 Hong
10
0.5
Laver 1- Hend.
Layer 1- Heas
Lastr 1 1-dead2
Lawer 1: Read
10
(a) Causally- masked model.
Positional attention non-causal
10-
0.0
15-
-1.0
Layer
Layer Head
Layer
1.0
0.5
2.0
0.0
15
-0
20
10
15
20
1.0
15
20
100
13
20
10
15
Ouery pos
Query pos
Qvery pos
Query p3s
(b) Unmasked model.
Positional attention
Layer D- Headl
Larre D. Hend
Lager Hear
Lasts D. Head
H-Hrdd
Rear
Heled
40
(c) Causally masked model with pause tokens.
Figure 3: Symmetric attention maps, demonstrating deviation from the uniform distribution for each query position.
31


Reviews:
[{"review_id": "KCsmnKoG0I", "reviewer": "Reviewer_KjRB", "summary": "Attention mechanisms and transformer architectures have achieved significant advancements in natural language processing and computer vision, forming the foundation of many recent large-scale models. Incorporating intermediate reasoning steps and chain-of-thought prompting has led to improved performance across tasks such as mathematical reasoning and question answering. Recent studies have found that inserting intermediate, seemingly meaningless tokens—pause tokens—can also improve model performance, though this effect remains unclear within the COT framework. This paper provides a theoretical explanation for the benefit of pause tokens in enhancing transformer expressivity, grounded in circuit complexity. Specifically, it proves that 1) constant-precision transformers with a polynomial number of pause tokens match the expressivity of AC0 (constant-depth circuits with and/or/not gates), and 2) logarithmic-precision transformers with pause tokens correspond to TC0 (AC0 with threshold gates). These results support the conclusion that 3) pause tokens increase transformer expressivity. The theoretical claims are empirically validated on a parity benchmark, building on prior findings that parity is hard for transformers without pause tokens. Results show that pause tokens enhance performance on this task and enable causally masked transformers to learn globally dependent functions.", "questions": "Transformers have been used in many domains such as NLP and Computer vision. Could you please provide some tasks in various domains that can benefit from pause tokens while being tied to the proposed theories in this paper?\n\n\nHow does increasing the number of layers affect the number of pause tokens required and accuracy?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strength:\n-- While transformers have achieved remarkable success across various domains, their theoretical foundations remain limited. This paper offers a theoretical analysis that clarifies the non-obvious reasons behind the performance gains observed when pause tokens are introduced. \n\n-- Explaining the benefit of adding pause tokens to improve transformers’ expressivity through the lens of circuit complexity is both novel and non-trivial.\n\n-- The results presented in Figure 1 and their analysis show the advantages of pause tokens on enhancing the transformer performance when the sequence length increases. This is particularly interesting because the transformers with pause tokens stay absolutely stable while other versions drop substantially. This shows the advantages of capturing global information once the pause tokens are introduced. \n\nWeaknesses\n\n-- The paper may be challenging to understand for a general audience due to its highly technical and theoretical nature. This could be improved by incorporating concrete examples, visualizations, and other intuitive elements to make the content more accessible and engaging for non-expert readers.\n\n-- Although the abstract and introduction highlight the advantages of using pause tokens in QA and mathematical reasoning tasks, the experimental evaluation is limited to the parity benchmark. Expanding the evaluation to include additional datasets in QA and mathematical reasoning would strengthen the connection between the theoretical insights and real-world applications.", "was_revised": true, "final_justification": "Thanks to the authors for their response to my comments. I still believe that adding more experiments on various datasets in different domains could better show the advantages of this study.", "rebuttal": "We thank the reviewer for their time and thoughtful comments. We are glad they appreciated the theoretical contribution and the connection to Transformer expressivity.\n\n**On clarity and accessibility:**\nWe appreciate the feedback and will add more concrete examples and intuitive explanations to improve accessibility. In particular, we will include examples of simple Boolean functions that are in $\\mathsf{AC}^0$ and require different circuit sizes, and therefore different numbers of pause tokens n our framework.\n\n**On empirical scope:**\nWe agree that broader evaluation is valuable. Our theoretical work was directly motivated by existing empirical results, particularly Goyal et al. (2023) and Pfau et al. (2024), which show that pause tokens improve performance on question answering and mathematical reasoning tasks. Our goal was to explain why this works, rather than to re-establish those results. To evaluate the alignment between theory and practice, we focused on the parity task, where the underlying complexity class (in $\\mathsf{TC}^0$ but not in $\\mathsf{AC}^0$), and the required $\\mathsf{TC}^0$ circuit size, is precisely known. This allows us to make a concrete connection between circuit complexity and Transformer expressivity. We will highlight these connections and refer more explicitly to prior empirical results in the final version.\n\n**Question 1:**\nWe will elaborate further in the final version, but to briefly address the question: while a direct mapping from $\\mathsf{AC}^0$/$\\mathsf{TC}^0$ to real-world NLP or vision tasks is difficult, prior work provides concrete empirical domains where pause tokens help. For example, Goyal et al. report gains in several mathematical and QA benchmarks, including GSM8K and CommonSenseQA, and Pfau et al. demonstrate improvements in multi-hop reasoning. These tasks involve long-range dependencies and intermediate computations, which are well modelled by the circuit-style reasoning our theory supports. We could also add some examples from formal language theory that may make the connection to NLP more concrete if you think it would be helpful.\n\n**Question 2:**\nThis is addressed in Lemma 4.4 of the paper. We show that for any depth $l$, there exists $m > l$ such that $\\mathsf{TF}_l[1,L,P] \\subsetneq \\mathsf{TF}_m[1,L,P]$. That is, increasing the number of layers strictly increases the class of functions the model can compute, even when pause tokens are available. This shows that depth and pause tokens are complementary mechanisms of expressivity. By Hastad’s switching lemma (1986), there also exist functions that require smaller circuits, and therefore fewer pause tokens, if the depth is increased. You may also find the concurrent work of Merrill et al. (2025) interesting, as they consider how increasing and even looping over depth affects expressivity in the presence of pause tokens (but only in the log-precision setting)."}, {"review_id": "mEmpgApDzO", "reviewer": "Reviewer_awq1", "summary": "This paper provides a theoretical investigation of the empirically observed phenomenon that adding \"pause tokens\"  to the input of the Transformer can improve its performance. The authors analyze the expressive power of constant-depth Transformers through the lens of circuit complexity. The paper proves that constant-precision, logarithmic-width Transformers with a polynomial number of pause tokens are computationally equivalent to the circuit class AC0. With logarithmic precision, they are equivalent to TC0. The authors demonstrate that a 2-layer causally masked Transformer, which struggles to learn the parity function, can successfully learn it when provided with pause tokens and appropriate training hints.", "questions": "See the Weaknesses part above.", "limitations": "The authors discuss the limitations of this work and point out future directions.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- This work is the first one to study the expressive power of Transformers with \"Pause Tokens\".\n- This paper is well-written and structured. It clearly motivates the problem and states its contributions.\n\n## Weaknesses\n**Gap Between Theory and Practice**: The theoretical results rely on adding a polynomial number of pause tokens to simulate arbitrary circuits. However, the empirical works that motivate this paper (e.g., Goyal et al., 2024) see benefits with a much smaller, often constant, number of tokens. The paper does not fully bridge the gap between its theoretical requirements and these practical observations.\n\n**Limited Empirical Scope**: The experiments are confined to the parity problem. While this is a canonical benchmark in complexity theory, it is a synthetic task. It remains an open question how these findings translate to the more complex natural language and mathematical reasoning tasks where pause tokens have been shown to help.\n\n**Incomplete Separation for Log-Precision**: The paper does not prove a strict separation between logarithmic-precision Transformers with and without pause tokens (TF[L,L,0]⊊TF[L,L,P]), as this would require solving open problems in circuit complexity. While the authors are transparent about this limitation, it means the results for the log-precision case are less conclusive than for the constant-precision case.", "was_revised": true, "final_justification": "The authors' rebuttal has addressed my concerns, so I am raising my score to 4.", "rebuttal": "We thank the reviewer for their thoughtful comments and for recognising the novelty and clarity of our theoretical investigation into pause tokens.\n\n**On the gap between theory and practice:**\nOur main results establish equivalences between constant-depth Transformers with pause tokens and the well-studied circuit classes $\\mathsf{AC}^0$ and $\\mathsf{TC}^0$. These are general upper bounds that require a polynomial number of pause tokens to simulate arbitrary circuits from those classes. However, this does not preclude significantly smaller constructions for specific tasks. For example, if the task is evaluating DNF Boolean formula, the size of the circuit grows with the number of clauses, so if the number of clauses is constant, the number of pause tokens required will be constant. More generally, if the output only depends on a fraction of the input tokens (as in some math word problems or similar), the Transformer will not need a polynomial number of pause tokens in the entire input size, and may only need pause tokens corresponding to those positions. While the practical works cited (e.g. Goyal et al. 2024) observe benefits with a constant number of pause tokens, these do not aim for asymptotic circuit-level equivalence, and our results do not contradict them. In fact, as they have an upper bound on the input length, the number of pause tokens required is theoretically constant. That said, our results do imply that some dependence on input length is necessary in the worst case, given the strict separations without pause tokens.\n\n**On empirical scope:**\nWe agree that broader empirical evaluation is a promising direction, but note that our contribution is primarily theoretical and motivated by existing empirical work. Several prior papers (including Goyal et al., 2024, and Pfau et al., 2024) have already demonstrated that pause tokens can improve performance on natural language and mathematical tasks, and our work aims to explain why this might be the case. We use the parity function in our tests due to previous works empirically demonstrating the difficulty in learning it without pause tokens, and because we can exactly characterize its circuit complexity (in $\\mathsf{TC}^0$, not in $\\mathsf{AC}^0$). This allows us to make the theoretical separation more empirically concrete. Extending these results to richer domains is a natural direction for follow-up work.\n\n**On the log-precision separation:**\nWe appreciate the reviewer’s understanding on this point. As noted in the paper, separating TF[L,L,0] from TF[L,L,P] in the logarithmic-precision setting would require resolving major open problems in circuit complexity. It has been conjectured in some previous papers (see Merrill et al., 2023 and Pfau et al., 2024) that there exists a size hierarchy for $\\mathsf{TC}^0$, which would suffice to prove a separation, but this conjecture remains open. While we cannot resolve this, we believe the formulation of the question in our framework is itself a meaningful step forward, and hope it invites further theoretical progress."}, {"review_id": "HSjzTeiZiK", "reviewer": "Reviewer_UV3u", "summary": "The authors study the expressivity of transformer when the input is extended by a sequence of blanks (\"pause tokens\"). Since positional encoding is applied to these additional tokens, the resulting transformers are more expressive. To be more precise, the authors consider Boolean functions in AC0 and TC0, well known classes defined via sequences of circuits. I give a rough description of how these classes are defined. A Boolean function is treated as a sequence of functions f_1, f_2,... (where f_n takes inputs of length n). We say it is in the class if there is a sequence of circuts, satisfying some conditions, that can be generated in uniform, space-efficient way, such that n-th circuit computes the n-th function. \nIn particular, the authors show that transformers with constant precision and poly number of pause tokens are equivalent to AC0 and allowing logarithmic precision gives equivalence to TC0. So for instance for a sequence of functions from AC0 or TC0 there exists a sequence of transformers, satisfying the corresponding conditions, such that n-th transformer computes the n-th function and there is a uniform, space-efficient way to generate these transformers.\nWhat's important is that the addition of pause tokens increases expressivity in the sense described above. This happens because the authors assume positional encodings that are dependent on the input length and then for a given input length, they can take a corresponding circuit and hardcode it inside these positional encodings.", "questions": "Q1: Can you say something about the situation where we have a single transformer for all input lengths and add pause tokens? A partial answer to this question can be found in your proofs but perhaps you have some additional insights.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Expressivity of transformers is an important theoretical topic of practical relevance. Papers in this area have been presented at NeurIPS before.\n- The presented results are novel and technically sound. The proofs seem correct.\n\n\nWeaknesses:\n- This particular contributions is probably of very limited practical relevance. While there is some sort of uniformity in this setting, it is not the kind of uniformity that is relevant from the practical point of view, i.e., having a single transformer which is capable of computing the function on inputs of arbitrary length (perhaps even with length-dependent positional encodings). Indeed, the authors give some experimental results for parity, but these are not very exciting, since generally the problem with training transformers for parity is more about length generalization and not training on fixed length inputs. That being said, it is plausible that this work will have practical impact by motivating the other authors to extend this setting to a more practical scenario.", "was_revised": true, "final_justification": "- Expressivity of transformers is an important theoretical topic of practical relevance. Papers in this area have been presented at NeurIPS before.\n- The presented results are novel and technically sound. The proofs seem correct.", "rebuttal": "We thank the reviewer for their time, their generous comments, and for carefully checking the technical details.\n\n**On the question of single-model uniformity:**\nWe agree this is an important question. As you note, our construction achieves uniformity in the standard circuit-theoretic sense: there exists a log-space Turing machine that generates the weights and positional encodings of the $n$-th Transformer given $n$. This does not correspond to a single Transformer computing $f_n$​ for all $n$, which would require a stronger notion of uniformity.\n\nIn our view, a key technical bottleneck is the ability to address all positions in the input. Implementing arbitrary circuits requires routing information to specific locations, which in turn demands positional encodings that grow with $\\log n$. Without sufficient positional resolution, we do not believe it is possible to simulate general uniform circuits, even with pause tokens. While our construction assumes access to length-dependent positional encodings, we also show (Appendix C.3) that the Transformer weights themselves are block-structured andonly the size of the blocks depends on the input length (not the value of the weights). If an upper bound $n_{\\text{max}}$ on input length is known, a single Transformer with fixed weights can compute all $f_n$ for $n \\leq n_{\\text{max}}$​, using either length-dependent or length-independent positional encodings. In the length-independent case, the number of required pause tokens grows by an additional multiplicative factor of $n$ in our construction (but remains in $\\text{poly}(n)$.\n\nWe agree that further work on formalising single-model uniformity and understanding its relationship to positional encoding and expressivity would be valuable, and we will clarify this point in the final version."}, {"review_id": "C0IcKvI686", "reviewer": "Reviewer_3UPU", "summary": "In this paper, the authors theoretically studied the expressivity of constant-depth log-embedding-dimension transformers with pause tokens, which are filler symbols appended to the end of the input sequences that provide more space for computation. \n\nFor constant precision transformers, the authors prove that transformer with polynomial pause tokens is computationally equivalent to AC\\^0. Moreover, for the non-uniform class of transformers, transformers without pause token are strictly less expressive than its counterpart with polynomial pause tokens; for the uniform case and for a fixed length $l$, an $l$-layer transformer without pause token is strictly less expressive than its $l$-layer counterpart with quasi-polynomial pause tokens.\n\nFor logarithmic precision transformers, the authors show it is equivalent to TC\\^0 when allowing polynomial number of pause tokens, although the separation for logarithmic precision transformers with and without pause tokens still remains open.\n\nFinally, the authors conduct experiments on learning parity function, and show it is easier to learn with pauses tokens and appropriate hints during training.", "questions": "1.\tIn Figure 2, for the causal and non-causal settings, there seem to be thresholds for each setting where the model has perfecta test accuracy below the threshold and collapse to random guess when exceeding the threshold. Also, the value of the threshold is not very small (~100 or 200). Do authors have any intuition about the value of the threshold given a fixed configuration of the transformer class?\n\n2.\tThere could be two possible explanations of the results of Section 5. One is the performance gap is due to expressivity with and without pause tokens. The other is they might have same expressivity but the one with pause tokens requires much fewer samples to learn. (Similar to what authors mentioned at the end of the main text as “expressivity vs learnability). Do authors have any (indirect) proof of which explanation might be correct?", "limitations": "See weaknesses and questions.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1.\tThis is the first theoretical work studying the benefits of pause tokens. Since pause token is empirically showed useful, it is important to (theoretically) understand its benefit. \n2.\tThe paper provides strict separation for constant precision transformers with and without pause tokens. For log-precision transformers, the paper shows it’s equivalent to $TC\\^0$.\n3.\tThe paper is well written and easy to follow.\n\n**Weaknesses:**\n\n1.\tFor logarithmic precision transformer, the paper does not show a separation between “no pause token” and “polynomial pause token”. (although it is acceptable to me since the lower bound of $TC\\^0$ is still open and might not be easy to improve)\n\n2.\tIt would be interesting to investigate more in section 5. Currently, the authors only compare the test accuracy among three different settings. It would be interesting to know their respective underlying mechanisms and see why those different mechanisms lead to performance difference (does not necessarily need to be theoretical analysis since analyzing training dynamics theoretically could be much more complicated and might be beyond the scope of the current paper). This could provide a more solid evidence of the benefits of using pause token for certain TC\\^0 tasks.\n\n3.\tIt might also be helpful to add some discussions of the comparison of pause tokens and CoTs. In particular, it could provide a clearer picture of the theoretical gain of purely increasing the computation space (or “width”) vs allowing step-by-step intermediate computation.", "was_revised": true, "final_justification": "The additional results of the attention patterns in two layers and the discussion of CoT vs pause tokens (especially the tradeoff between the inference cost and expressivity) make sense to me. Overall, I'm leaning towards acceptance and will keep my score.", "rebuttal": "We thank the reviewer for their time and constructive comments.\n\n**On log-precision separations:**\nWe agree that the lack of separation in the log precision case is a limitation that we have acknowledged in the paper. We expect that proving this separation would require significant progress in complexity theory. A (even fixed-depth) size hierarchy theorem for $\\mathsf{TC}^0$ would suffice, as has been conjectured in previous papers (see Merrill et al., 2023 and Pfau et al., 2024).\n\n**On mechanisms:**\nWe agree that understanding how pause tokens help during training is an important and interesting direction. At present, our empirical study in Section 5 is limited to performance outcomes and ablations. At your suggestion, we examined the learning curves and attention patterns of the trained models. The learning curves do not provide direct evidence for a specific mechanism, but they do display clear signs of grokking-like behaviour: the Transformer maintains near-random accuracy for most of training, and then suddenly transitions to perfect accuracy within a few steps.\n\nThe attention patterns for the pause-token model show that in the first layer, the pause tokens attend to all input tokens, while in the second layer the output token attends to all pause tokens. This suggests the Transformer may be learning a function similar to the canonical $\\mathsf{TC}^0$ circuit in Appendix E, with the first layer computing intermediate threshold sums, and the final layer combining them into parity. In the non-causal case, we see a similar pattern. In the first layer, input tokens attend broadly to all others, while in the second layer, the final token attends to all inputs. In the causal case, the patterns are less structured and harder to interpret. It would be interesting to analyse how these patterns evolve during training, and we will endeavour to include such an analysis in the final version.\n\n**On CoT vs pause tokens:**\nWe currently have a brief discussion on the relative strengths of CoT and pause tokens in sections 2 and 6. We will expand on this discussion with the following points. It is known that CoT with a polynomial number of steps allows Transformers to compute everything in $\\mathsf{P}$ (uniformly and $\\mathsf{P/poly}$ non-uniformly). It is not proven, but it is widely believed by complexity theorists that $\\mathsf{TC}^0 \\subsetneq \\mathsf{P/poly}$, which would imply that Transformers with CoT are strictly more expressive than those with pause tokens. In fact, a Transformer with CoT only requires depth 2 to compute anything in $\\mathsf{P/poly}$ (see “Chain of Thought Empowers Transformers to Solve Inherently Serial Problems”, Li et al., 2024), which certainly suggests that for a fixed depth it is strictly more powerful. However, CoT requires running multiple forward passes through the Transformer (up to $\\text{poly}(n)$ for full \\mathsf{P} expressivity), while pause tokens provide their additional expressivity within a single forward pass. This suggests that they may even be complementary in improving Transformer performance.\n\n**Question 1:**\nThis is a good question, and our intuition is that the threshold arises from a combination of the effective capacity of the Transformer and the number of samples required to generalise at longer lengths. Even at length 100, there are $2^100$ possible inputs, and the model sees only a very small fraction of them during training. As noted above, we observe grokking-like behaviour when the model does succeed in learning, and therefore observe either random accuracy or 100% accuracy, with little in between.\n\nTo disentangle whether the effect is driven more by the sample complexity or by model capacity, we are running further experiments with wider and narrower Transformer models to see how the threshold for accuracy collapse shifts. We do not yet have conclusive results, but we aim to include them in the final version.\n\n**Question 2:**\nSo far we only have speculation, and are not yet comfortable putting it in the paper. However, our hypothesis is that the form of the pause token hints reduces the sample complexity of learning parity, and so this is more a function of learnability than expressivity. It is conjectured that parity is difficult to learn because it is a high-sensitivity function (see “Why are Sensitive Functions Hard for Transformers?”, Hahn et al., 2024), where a change to a single input bit changes the output bit. By contrast, the threshold sum values that use as hints are significantly less sensitive, and so should be much easier to learn when they are given as a target. Given these threshold values, the threshold computed by the second layer of the canonical $\\mathsf{TC}^0$ circuit is also significantly less sensitive, and so if the model first learns to compute the threshold sums, it should then be much easier for it to learn the overall parity. We aim to analyse this further in a follow-up work."}, {"review_id": "plsR7dsbsi", "reviewer": "Reviewer_MSH9", "summary": "This paper formally characterizes how pause tokens increase the expressivity of transformers. In the fixed precision case, the paper shows that transformers with pause tokens are equivalent to the circuit class $\\mathsf{AC}^0$, and strictly more expressive than transformers without pause tokens. In the log precision case, transformers with pause tokens are equivalent to $\\mathsf{TC}^0$, but the paper does not provide a separation result for transformers without pause tokens. Empirically, the paper shows that (log precision) transformers with pause tokens can solve the parity task on long inputs, where tranformers without pause tokens fail.", "questions": "- Would it be possible to give an example of a problem in $\\text{AC}^0$ that can be solved with padding tokens but not without padding tokens?\n- In the experiment section, is the non-causal model (without pause tokens) also trained with hints? Would it be possible to provide an analogous figure to the figure at the bottom of page 7?\n\n\nMinor comments:\n\n- What is $\\mathcal{A}$ (in line 150)?\n- It could be helpful to briefly define \"advice\" (in line 261), for readers who aren't familiar with the reference.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "*Strengths*\n\n- This paper provides theoretical insight into the empirical finding that pause tokens can improve performance on some tasks. This can help explain some empirical results that have found pause tokens to be helpful in some cases but not others, and (as the authors discuss) possibly have implications for understanding chain-of-thought and the limitations of quantized models.\n- I found the writing to be very clear, and I appreciated the discussion section and the detailed discussion of areas for future work.\n- Experiments show that pause tokens allow transformers to solve the parity task on long inputs, where models without pause tokens fail. There is a helpful ablation showing that the benefit of pause tokens is not simply due to overcoming the causal mask.\n\n*Weaknesses*\n\n- The paper does not provide a theoretical separation result between $\\mathsf{TF}[L,L,0]$ and $\\mathsf{TF}[L,L,P]$ (i.e., showing that log-precision transformers with pause tokens are strictly more expressive than without pause tokens). This limitation is discussed in detail and seems reasonable to me.\n- The experiment (section 5) is not directly related to the theoretical results. To my understanding, a log precision transformer without pause tokens is expressive enough to compute parity (using the two layer circuit construction). The experiment shows that these models struggle to learn it in practice, while pause tokens make learning easier in practice. This result is interesting, but not directly related to the expressivity results in the paper. The authors discuss these limitations.\n- It would have been interesting to see experiments with fixed precision transformers, but I understand that it is impractical to train models with precision $< O(\\log n)$, which the authors discuss.\n\nOverall, I think this paper makes a clear and valuable contribution to our theoretical understanding of transformers. I think all of the weaknesses are reasonable, and acknowledged in the paper.", "was_revised": true, "final_justification": "This paper provides new theoretical insight into an empirical phenomenon, the paper is clearly written, and the theoretical results are supported by some empirical analysis. The limitations of the paper are reasonable and clearly acknowledged by the authors. After the reading the rebuttal and the other reviews, I still recommend to accept the paper.", "rebuttal": "We thank the reviewer for their thoughtful and constructive comments, and are glad they found the contribution clear and valuable.\n\n**Weaknesses:**\nWe are glad the reviewer agrees that the limitations are reasonable and acknowledges the difficulty in replicating asymptotic constant precision in practise. We agree that parity should be computable by a two layer Transformer without pause tokens, especially without causal masking. There may exist a separation with causal masking, but as you note, achieving this separation theoretically would require a major breakthrough in $\\mathsf{TC}^0$ lower bounds.\n\n**Question 1:**\nYes, the canonical example is the Sipser function. Most easily, this can be defined as follows.\n\nFix a depth $d$ and a fan-in $w$ such that $n = w^d$. Then repeat the following procedure until the $d$th layer produces a single output bit.\n\nFirst layer: Group the inputs $x$ into blocks of $w$ consecutive bits. If $d$ is odd, take the OR of each block, if $d$ is even take the AND. This produces $w^{d-1}$ output bits as input for the next layer.\n\nSecond layer: Group the $w^{d-1}$ input bits to this layer into blocks of $w$ consecutive bits. Flip the gate type used in the previous layer (AND to OR and vice versa), and apply it to each block, leaving us with $w^{d-2}$ output bits.\n\nAfter repeating this procedure for $d$ layers we have a single output bit which is the output of the Sipser function $f_{d,w}$.\n\nHastad’s switching lemma tells us that a depth-d circuit needs only $O(n)$ gates to compute this function, while any circuit of depth less than $d$ needs at least $n^{\\Omega(\\sqrt{\\log n})}$ gates.\n\nIf we take a Transformer of a fixed depth without pause tokens, our Lemma D.1. states that the Transformer can be simulated by some $AC^0$ circuit of depth $d$, with no more than $n^k$ gates where $k$ is constant. Therefore, if we take the Sipser function $f_{d+1,w}$, the Transformer will be unable to compute the function without pause tokens as soon as $\\sqrt{\\log n} > k$. We can always construct such a function no matter the depth of the Transformer, and so this is a concrete function that cannot be computed without pause tokens.\n\n**Question 2:**\nYes, the non-causal model is provided the same hints as the causal model trained with pause tokens. We will clarify this and add a figure into the final version.\n\n**Comments:**\nThank you for catching this. The reference to $\\mathcal{A}$ (referring to the vocabulary or alphabet of the Transformer) was an oversight, and as we only consider binary functions this should be replaced with {0, 1}.\n\nWe will also add a brief definition of the complexity theoretic notion of advice in the final version."}]

Author rebuttal:

Meta-review: **Summary of Scientific Claims and Findings**

The paper provides the first theoretical proof that adding "pause tokens" to constant-depth Transformers strictly increases their computational power. It formally connects constant-precision models with pause tokens to the complexity class $AC^0$ and logarithmic-precision models to $TC^0$. Empirically, it shows that pause tokens enable a Transformer to learn the parity function, a task it otherwise fails.


**Strengths**

* **Novelty:** It is the first paper to provide a rigorous theoretical explanation for the benefits of pause tokens.
* **Technical Soundness:** The theoretical results, grounded in circuit complexity, are considered correct and significant.
* **Clarity:** The paper is well-written and clearly articulates its contributions and the problem's motivation.


**Weaknesses of the Paper**

* **Theory-Practice Gap:** The theory requires a polynomial number of pause tokens, while practice often uses a small constant.
* **Limited Empirics:** Experiments are confined to the synthetic parity task, not the real-world tasks mentioned in the motivation.

**Reasons for Recommendation**

The paper makes a fundamental and novel contribution to our theoretical understanding of Transformers. It provides a solid foundation for an empirically observed phenomenon. The strengths of this foundational work outweigh the weaknesses, which are reasonably acknowledged as being outside the paper's primary scope. Thus I recommend acceptance.

**Summary of Discussion and Rebuttal**

The authors provided a strong rebuttal that successfully addressed reviewers' concerns.
* **On empirical scope and theory-practice gap:** The authors clarified their goal was theoretical explanation, not replication, and the polynomial token requirement is a worst-case bound. This satisfied reviewer **awq1**, who raised their score.
* **On mechanisms and comparisons:** They provided analysis of attention patterns and a clear distinction between single forward pass for pause tokens and multiple forward pass for Chain-of-Thought (CoT).
* **On technical clarifications:** They provided a concrete example (the Sipser function) for the theoretical separation when requested by **MSH9**.
Decision: Accept (poster)