Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers

We thank the reviewer for their thoughtful and constructive comments, and are glad they found the contribution clear and valuable.

Weaknesses: We 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.

Question 1: Yes, the canonical example is the Sipser function. Most easily, this can be defined as follows.

Fix 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.

First 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.

Second 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.

After repeating this procedure for $d$ layers we have a single output bit which is the output of the Sipser function $f_{d,w}$.

Hastad’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.

If 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.

Question 2: Yes, 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.

Comments: Thank 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}.

We will also add a brief definition of the complexity theoretic notion of advice in the final version.

We thank the reviewer for their time and constructive comments.

On log-precision separations: We 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).

On mechanisms: We 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.

The 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.

On CoT vs pause tokens: We 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.

Question 1: This 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.

To 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.

Question 2: So 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.

We thank the reviewer for their time, their generous comments, and for carefully checking the technical details.

On the question of single-model uniformity: We 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.

In 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)$.

We 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.

We thank the reviewer for their thoughtful comments and for recognising the novelty and clarity of our theoretical investigation into pause tokens.

On the gap between theory and practice: Our 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.

On empirical scope: We 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.

On the log-precision separation: We 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.

We thank the reviewer for their time and thoughtful comments. We are glad they appreciated the theoretical contribution and the connection to Transformer expressivity.

On clarity and accessibility: We 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.

On empirical scope: We 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.

Question 1: We 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.

Question 2: This 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).