Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers
Charles London, Varun Kanade · 2025
Read Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers by Charles London, Varun Kanade (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21024.txt.
Introduction
Charles London and Varun Kanade prove that pause tokens strictly increase the expressivity of constant depth transformers. Pause tokens are simple filler symbols that reliably improve transformer performance on language and math tasks, with no theory to explain why. A formal separation result settles what the tokens actually add.
With bounded precision activations, transformers without pause tokens compute only a strict subset of a basic circuit class. Adding polynomially many pause tokens lets them express the whole class. With logarithmic precision, pause tokens reach a stronger class that matches known upper bounds. Empirically, two layer masked transformers learn parity with pause tokens but appear unable to learn it without them.
Catalog record
| CREATOR | Charles London, Varun Kanade |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21024
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers Charles London, Varun Kanade 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 𝖠𝖢 0 \mathsf{AC}^{0} functions, while adding a polynomial number of pause tokens allows them to express the entire class. For logarithmic-precision Transformers, we show that adding pause tokens achieves expressivity equivalent to 𝖳𝖢 0 \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. 1 Introduction Transformers [ 38 ] have become ubiquitous in modern machine learning, achieving state-of-the-art performance across a 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. a “…” token) to Transformer inputs can improve performance on some question-answering and mathematical tasks [ 30 , 14 ] . 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. In this paper, we provide a theoretical explanation for how pause tokens might improve Transformer performance. Specifically, we analyse how they affect the expressivity of Transformers through the lens of circuit complexity. Our contributions are as follows: 1. Pause tokens allow Transformers to simulate Boolean circuit classes exactly. We prove that constant-precision Transformers with a polynomial number of pause tokens are equivalent in expressivity to \mathsf{AC}^{0} (constant depth circuits with and/or/not gates), while logarithmic precision Transformers with pause tokens match \mathsf{TC}^{0} (circuits like \mathsf{AC}^{0} with threshold gates). 2. Pause tokens strictly increase expressivity in constant-precision Transformers. We prove a separation: Transformers without pause tokens are fundamentally less expressive than those with. 3. Empirically, pause tokens help causally masked Transformers learn functions requiring global computation. We show that two-layer causally masked Transformers struggle to learn parity (which belongs to \mathsf{TC}^{0} ) 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 an efficiently computable procedure. Our results provide a principled explanation for recent empirical findings on pause tokens while also highlighting broader implications for Transformer expressivity. In particular, they suggest that a Transformer’s computational power is 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-thought reasoning, the tradeoffs 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 2 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 circuit 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 5 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 chain-of-thought (CoT, Wei et al. [39] ) in Transformer computation. While both methods purport to increase the computational space or memory of the Transformer to enable it to solve more problems, they do so in very different ways. In CoT, a 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 ] . Transformers with pause tokens : The notion of adding padding to a Transformers input to improve performance traces back to Burtsev et al. [5] , in which they prepended memory tokens to the input to a 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. [14] , in which they pre-trained a Transformer to use between 0 and 50 pause tokens before responding. This led to increased performance on natural language and mathematical benchmarks including CommonsenseQA [ 35 ] and GSM8K [ 10 ] . Since then, Pfau et al. [30] have replicated this improvement on simple mathematical tasks and proposed quantifier depth as the theoretical explanation. Formal models of Transformers : Since the invention of the Transformer, there have been many attempts 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. [16] showed that log-precision Transformers using unique hard attention (attending to only a single position) are contained within \mathsf{AC}^{0} , while averaging hard attention Transformers can express non- \mathsf{AC}^{0} languages. Merrill and Sabharwal [27] proved that log precision Transformers (with standard softmax attention) are contained within logspace-uniform \mathsf{TC}^{0} , while Chiang [9] extended these results to show that Transformers with O(\mathrm{poly}(n)) precision are in uniform \mathsf{TC}^{0} . Further works have also used the circuit complexity perspective to determine the expressive power of both constant- and log-precision Transformers using intermediate chain-of-thought steps, showing that they are equivalent to \mathsf{P} (uniformly, or \mathsf{P/poly} non-uniformly) [ 22 , 28 ] . 3 Preliminaries In this section, we introduce the relevant computational complexity concepts, including circuit classes and logspace uniformity, as well as definitions of the Transformer model we are considering and fixed precision arithmetic. 3.1 Boolean Circuits Boolean circuits are a model of computation that uses logical operations to