Pith. sign in

REVIEW 3 major objections 4 minor 43 references

Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that adding polynomially many pause tokens strictly increases the expressivity of constant-depth, logarithmic-width Transformers, lifting constant-precision models from a strict subset of AC0 to all of AC0 and…

desk verdict The pause-token/AC0 separation is a timely and well-framed question, but the submitted proof has a concrete algebraic error in the attention construction, so the main claim is not established as written. read the letter →

arxiv 2505.21024 v1 pith:UFQOKN6U submitted 2025-05-27 cs.LG cs.CL

Charles London , Varun Kanade This is my paper
classification cs.LGcs.CL MSC 68Q0668Q15
keywords pausetokenstransformerexpressivityAC0TC0circuitcomplexityconstantprecisioncausalmaskingparity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Pause tokens—filler symbols such as "..."—are shown to be not merely an optimisation aid but a genuine source of computational power. The paper proves that constant-precision Transformers with logarithmic embedding dimension and a polynomial number of pause tokens are exactly as expressive as AC0, the class of constant-depth circuits with unbounded fan-in AND, OR, and NOT gates, while the same architecture without pause tokens computes only a strict subset of AC0. With logarithmic-precision activations, adding pause tokens lifts the model to TC0, the threshold-circuit class, matching prior upper bounds. These results give a complexity-theoretic explanation for the empirical gains from pause tokens and identify them as a width-increasing mechanism distinct from chain-of-thought.

What carries the argument

The construction is carried by a positional-encoding scheme that writes a description of the target Boolean circuit into the Transformer's input. Each input bit becomes an Inp token; each wire of the circuit becomes an argument token Arg(i,j) placed among the pause tokens; each gate becomes a Type or Thresh token. Interleaved encodings $k(i)=\mathrm{sbin}(i)\frown 1$ and $q(j)=B_p(\mathrm{sbin}(j)\frown(-1))$ are designed so that $k(i)^T q(j)=0$ for $i=j$ and $-B_p$ otherwise, making post-softmax attention a one-hot pointer after exponentiation. Two Transformer layers simulate one circuit layer: the first copies already-computed vertex values into the argument tokens, and the second sums the arguments at the gate token; a small ReLU feedforward network implements the threshold $\mathbb{I}[x>0]$, with De Morgan's laws handling AND gates. Saturation arithmetic is what lets a single gate token attend to polynomially many argument tokens without overflow, and repeating two layers per circuit layer keeps total depth constant.

What would settle it

Verify the paper's own attention arithmetic: with $k(i)=\mathrm{sbin}(i)\frown 1$ and $q(j)=B_p(\mathrm{sbin}(j)\frown(-1))$, the logit equals $B_p(\mathrm{sbin}(i)\cdot \mathrm{sbin}(j)-1)$, which is $B_p(m-1)$ when $i=j$ and lies strictly between $0$ and $-B_p$ when $i \neq j$. Simulating the constructed constant-precision Transformer on inputs up to, say, $n=4096$ and checking whether each gate token receives exactly the intended vertex value would reveal whether the one-hot copying step is realizable; if it is not, the AC0-simulation theorem needs a different attention construction.

Watch

Extended reading notes

Core claim

The central discovery is a pair of characterisations with a strict separation at constant precision. Theorem 4.1 states that TF[1,L,P], the class of constant-precision Transformers with logarithmic embedding dimension and polynomially many pause tokens, is exactly AC0: every AC0 circuit family can be simulated by such a Transformer, and every such Transformer can be simulated by an AC0 circuit. Corollary 4.2 then concludes TF[1,L,0] ⊊ TF[1,L,P], so pause tokens add genuine computational power rather than merely easing optimisation. For logarithmic-precision activations, Theorem 4.5 states TF[L,L,P] = TC0, matching the known upper bound for log-precision Transformers. The paper positions this as the first formal separation result for pause tokens and as an explanation of their observed benefit on question-answering and mathematical tasks.

Load-bearing premise

The load-bearing premise is that a constant-precision attention head can behave as an exact pointer: for every position in a polynomially long sequence, softmax assigns weight exactly 1 to the one token it should copy and weight 0 to all others, so gate values are retrieved without error.

Editorial extensions

If this is right

  • For constant-precision (quantized) Transformers, a polynomial supply of pause tokens is enough to compute every AC0 function; removing them leaves a strict gap, so any observed gain from pause tokens on constant-depth tasks has a complexity-theoretic explanation.
  • In the logarithmic-precision regime, pause tokens give constant-depth Transformers the power of TC0, which includes parity and majority; this matches known upper bounds and makes the architecture's expressivity independent of whether weights are quantized as long as activation precision and feedforward thresholding stay logarithmic.
  • Because the simulation uses two Transformer layers per circuit layer, constant-depth circuits stay constant-depth Transformers: the gain from pause tokens is parallel width, not serial depth, so pause tokens cannot push the model beyond AC0 (or TC0) at fixed depth.
  • For fixed-depth uniform models, quasi-polynomially many pause tokens already separate the class from the no-pause-token class, showing the width-versus-depth tradeoff is real even under uniformity constraints.
  • The empirical parity result indicates that the theoretical construction is not purely existential: a two-layer causally masked Transformer can learn parity with pause tokens and hint supervision, whereas the same model without pause tokens fails on sequences past length 100.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same two-layer-per-circuit-layer simulation should extend to other parallelisable TC0 problems such as sorting networks or iterated addition: if pause tokens are allocated as argument and gate registers, supervised hints analogous to the threshold values should make these learnable by shallow causal transformers.
  • The width-not-depth framing predicts a sharp resource threshold: a circuit of size $s$ requires roughly $s$ pause tokens, so providing far fewer should give no expressivity gain; this is testable by sweeping the number of pause tokens on a task whose minimal AC0 circuit is known.
  • Under the conjecture $\mathsf{TC}^0 \neq \mathsf{P}$, pause tokens and chain-of-thought occupy complementary regimes—chain-of-thought adds sequential computation up to $\mathsf{P}$, pause tokens add only parallel width—so a hybrid that interleaves generated pause tokens across steps should be expressively stronger than either alone, though the paper does not prove this composition.
  • If weight-only quantization preserves the TC0 result, then 4-bit weight quantized models with full-precision activations should retain the ability to solve threshold-based tasks such as parity; measuring this would localize the expressivity bottleneck in the feedforward nonlinearity.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper claims a first formal separation result for pause tokens in Transformers: with constant precision and logarithmic width, Transformers without pause tokens compute a strict subset of AC^0, while adding a polynomial number of pause tokens yields exactly AC^0 (Theorem 4.1, Corollary 4.2). For logarithmic precision, the paper claims equivalence with TC^0 (Theorem 4.5). The proof strategy is to simulate a Boolean circuit by encoding its vertices and edges as pause tokens, using two Transformer layers per circuit layer; the first layer copies already-computed values to argument tokens via exact hard attention, and the second layer aggregates them at gate tokens. The paper also reports experiments suggesting that two-layer causally masked Transformers can learn parity with pause tokens and hint supervision.

Significance. If the main results were correct, this would be a notable contribution: it would give the first formal proof that pause tokens strictly increase the expressivity of constant-precision, logarithmic-width Transformers, and it would connect pause tokens to the circuit classes AC^0 and TC^0 in a clean way. The paper is also commendable for making its uniformity conventions explicit and for separating upper-bound and lower-bound arguments. However, the central lower-bound construction rests on an arithmetically incorrect claim about attention logits; the error is load-bearing and affects both Theorems 4.1 and 4.5. The upper-bound containments and the empirical parity experiments are not sufficient to establish the paper's main separation claims.

major comments (3)
  1. [C.1, Eq. (2)] Equation (2) is false under the definitions given. With k(i)=sbin(i)⌢1 and q(j)=B_p(sbin(j)⌢(-1)), substituting into the inner product gives k(i)^T q(j)=B_p(sbin(i)^T sbin(j)-1) if 1 and -1 are scalars appended to the sbin vectors, and B_p(sbin(i)^T sbin(j)-m) if they are all-ones/all-minus-ones vectors of length m. In the first reading, the diagonal value is B_p(m-1), not 0, and off-diagonal values vary with the Hamming distance between the binary representations. In the second reading, the diagonal is 0 but off-diagonal values range down to about -2B_p, not all equal to -B_p. The exact attention pattern asserted in the following sentence ('1 for i=j and 0 everywhere else') is therefore not produced.
  2. [C.1, Eqs. (2)-(11)] The routing mechanism cannot be realized by a logarithmic-dimensional QK construction. The logit matrix required for the claimed exact attention is L = -B_p(J-I), with 0 on the diagonal and -B_p off it, and this matrix has full rank n. Any single attention head computes logits of the form KQ^T with K,Q in R^{n x d}, so its logit matrix has rank at most d = O(log n). Hence the exact matrix in Eq. (2) is not representable for the class TF[1,L,P]. Since Eqs. (3)-(11) rely on Arg(i,j) attending only to Vertex(j) and Type(i) aggregating only its own arguments, the inductive invariant in Theorem C.1 fails as soon as attention is approximate; the resulting leakage into the copied values propagates through the two-layer block. This invalidates the proof of AC^0 subseteq TF[1,L,P] and therefore also the strict separation in Corollary 4.2.
  3. [C.2, Theorem C.7] The logarithmic-precision lower bound reuses the identical k(i), q(i) construction ('Define k(i) and q(i) as in the AC0 case'), so it inherits the defect in Eq. (2). In the logarithmic-precision setting B_p is about 2^p = n^{Theta(1)}, and for distinct indices with nearby binary codes the value sbin(i)^T sbin(j)-1 can be positive, making the nonmatching logit positive as well; the claimed separation between matching and nonmatching positions is therefore not even a gap. Consequently, the equality TF[L,L,P] = TC^0 in Theorem 4.5 is unproved in the lower-bound direction.
minor comments (4)
  1. [Section 3.3, Definition 3.4] The definition of F_p allows c*k*2^{-p} with c in {-1,1} and 0 <= k <= 2^{2p}-1, which makes zero appear twice and gives overlapping representations; please state explicitly that c*k is a signed integer in the intended range.
  2. [Section C.1 and C.2] The notation x⌢y is defined for two vectors of the same dimensionality, but it is later used with scalars in k(i)=sbin(i)⌢1 and q(j)=B_p(sbin(j)⌢(-1)); please clarify whether 1 and -1 denote scalars or vectors of ones and minus ones, since the ambiguity is directly relevant to the validity of Eq. (2).
  3. [Proof of Theorem C.5] The text says 'By Theorem C.2, f is in uniform AC^0', but the statement quoted is Lemma C.2; please correct the cross-reference.
  4. [Section 5, Figure 2] The caption does not state the number of pause tokens used in the pause-token condition; the text says 'n pause tokens', but the figure's x-axis is input length, so please clarify whether the pause-token count equals n for all lengths and whether hint supervision is also used in the non-causal condition.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theoretical results are derived from external circuit-complexity results and constructive simulations, and the hint-supervised experiments are not presented as formal predictions.

full rationale

The paper's central claim, TF[1,L,P] = AC0 (Theorem 4.1), is not circular. The lower-bound direction (Theorem C.1) is a constructive simulation: it takes a logspace-uniform AC0 circuit family and shows how pause tokens encode the circuit description and compute gate values with two Transformer layers per circuit layer. The upper-bound direction (Theorem C.5) decomposes the Transformer into positional-encoding, attention, and feedforward computations and shows each is in uniform AC0, using external results (Li et al. on iterated addition, Merrill and Sabharwal on positional encodings, Hesse on division, Limaye et al. on the fixed-depth AC0 size hierarchy). None of these external results assumes the theorem being proved, and none is authored by the present authors, so there is no load-bearing self-citation. The only self-citation, Bhattamishra et al. [4] (co-authored by Kanade), appears in related work on communication complexity and is not used to justify any theorem. The empirical parity study uses hint labels (threshold values and subparities) during training, so it is not a parameter-free test of the theory; the paper states this explicitly ('we found that in all regimes, gradient-based training... struggles to learn parity using only the loss on the final prediction'). This is an experimental-design caveat, not a circular derivation: the trained model is evaluated on held-out test examples, and the theoretical results do not depend on these experiments. Two self-reported limitations are relevant: the paper says the equivalence 'relies on the use of saturation arithmetic', and it says it cannot separate TF[L,L,0] from TF[L,L,P] without TC0 lower bounds; both confirm the theorems are not assumed into existence. A separate correctness concern, that Eq. (2)'s claimed dot-product values do not follow arithmetically from the given definitions and that exact hard attention may not be realizable with O(log n) embedding dimension, is a realizability issue in the construction, not circularity, because it does not make the conclusion an input to the derivation. No step in the paper reduces to its own inputs.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The theoretical claims rest on four axioms: a specific arithmetic model, a specific uniformity notion, the realisability of exact hard attention in constant precision, and standard circuit-complexity facts. The third axiom is the fragile one: the paper's Eq (2), which is supposed to guarantee the hard-attention property, is false as written. The free parameter listed is the empirical hint design, which is required for the parity experiment to work.

free parameters (1)
  • hint supervision for pause-token parity experiments = n threshold values t_j = I[sum x_i >= j] for j=1..n
    The empirical claim that pause tokens enable parity learning only holds when this hand-designed auxiliary loss is supplied; without hints, no configuration learns parity (Section 5).
assumptions (4)
  • domain assumption Saturation fixed-point arithmetic with rounding is an accurate model of quantized Transformer computation.
    Used in Definition 3.4 and throughout the proofs; the authors acknowledge in Section 7 that changing arithmetic changes expressivity.
  • domain assumption Logspace-uniform Transformer families (Definition 3.6) are the right uniformity notion.
    This is a new definition introduced by the paper; it borrows logspace uniformity from circuit complexity.
  • ad hoc to paper Exact hard attention (attention weight 1 on the intended token, 0 elsewhere) is realizable with constant precision and O(log n) embedding dimension.
    Assumed in Theorem C.1; Eq (2) states the required inner-product property, but the property is false under the given definitions, and the required separation may not be representable with constant precision as n grows.
  • standard math AC0 containment and size-hierarchy results from prior work (Li et al., Limaye et al., Hastad).
    Used in Lemma D.1 and Theorem D.3; standard accepted results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers." pith.science (2026). https://pith.science/paper/UFQOKN6U

@misc{pith2026250521024,
  author       = {Pith},
  title        = {Pith review of: Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UFQOKN6U}},
  note         = {Machine review of arXiv:2505.21024}
}
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 allows them to express the entire 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.

Figures

Figures reproduced from arXiv: 2505.21024 by the authors.

Figure 1
Figure 1. Two layers of a Transformer with pause tokens can simulate a layer of a Boolean circuit. In [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Test accuracy on predicting the parity of a sequence for Transformers with learned posi￾tional encodings, with and without pause tokens and causal masking. Averaged over 3 random seeds. Results. We can see in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 24 canonical work pages

  1. [1]

    Cambridge University Press, 2009

    Sanjeev Arora and Boaz Barak.Computational complexity: a modern approach. Cambridge University Press, 2009

    2009

  2. [2]

    Understanding Hidden Computations in Chain-of-Thought Reasoning

    Aryasomayajula Ram Bharadwaj. Understanding hidden computations in chain-of-thought reasoning, 2024. URLhttps://arxiv.org/abs/2412.04537

    work page Pith review arXiv 2024

  3. [3]

    Bhattamishra, Kabir Ahuja, and Navin Goyal

    S. Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. InConference on Empirical Methods in Natural Language Processing, 2020. URLhttps://api.semanticscholar.org/CorpusID:222225236

    work page 2020

  4. [4]

    Separations in the representational capabilities of transformers and recurrent architectures

    Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the representational capabilities of transformers and recurrent architectures. InThe Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: //openreview.net/forum?id=6HUJoD3wTj

    work page 2024

  5. [5]

    Memory transformer

    Mikhail S Burtsev, Yuri Kuratov, Anton Peganov, and Grigory V Sapunov. Memory transformer. arXiv preprint arXiv:2006.11527, 2020

    arXiv 2006

  6. [6]

    just beyond

    Lijie Chen and Roei Tell. Bootstrapping results for threshold circuits “just beyond” known lower bounds. InProceedings 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 9781450367059. doi: 10.1145/3313276.3316333. URL https://doi.org/ 10.1145/3313276.3316333

    arXiv 2019

  7. [7]

    Theoretical limitations of multi-layer transformer

    Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer transformer. ArXiv, abs/2412.02975, 2024. URL https://api.semanticscholar.org/CorpusID: 274464787

    arXiv 2024

  8. [8]

    Prefixquant: Static quantization beats dynamic through prefixed outliers in llms.arXiv preprint arXiv:2410.05265, 2024

    Mengzhao Chen, Yi Liu, Jiahao Wang, Yi Bin, Wenqi Shao, and Ping Luo. Prefixquant: Static quantization beats dynamic through prefixed outliers in llms.arXiv preprint arXiv:2410.05265, 2024

    arXiv 2024

Show all 43 references
  1. [9]

    Transformers in uniform TC0.Transactions on Machine Learning Research, 2025

    David Chiang. Transformers in uniform TC0.Transactions on Machine Learning Research, 2025

    2025

  2. [10]

    Training verifiers to solve math word problems.arXiv preprint arXiv:2110.14168, 2021

    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 arXiv:2110.14168, 2021

    arXiv

  3. [11]

    Gr´egoire Del´etang, 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.02098, 2022. URL https://api.semanticscholar.org/CorpusID: 250280065

    2022 arXiv

  4. [12]

    The llama 3 herd of models.arXiv preprint arXiv:2407.21783, 2024

    Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models.arXiv preprint arXiv:2407.21783, 2024

    2024 arXiv

  5. [13]

    Parity, circuits, and the polynomial-time hierarchy.Mathematical systems theory, 17(1):13–27, 1984

    Merrick Furst, James B Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy.Mathematical systems theory, 17(1):13–27, 1984. 10

    1984

  6. [14]

    Think before you speak: Training language models with pause tokens

    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. URLhttps://openreview.net/forum?id=ph04CRkPdC

    2024

  7. [15]

    Theoretical limitations of self-attention in neural sequence models.Transactions of the Association for Computational Linguistics, 8:156–171, 2020

    Michael Hahn. Theoretical limitations of self-attention in neural sequence models.Transactions of the Association for Computational Linguistics, 8:156–171, 2020. doi: 10.1162/tacl a 00306. URLhttps://aclanthology.org/2020.tacl-1.11/

    2020 doi

  8. [16]

    Formal language recognition by hard atten- tion transformers: Perspectives from circuit complexity.Transactions of the Association for Computational Linguistics, 10:800–810, 2022

    Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard atten- tion transformers: Perspectives from circuit complexity.Transactions of the Association for Computational Linguistics, 10:800–810, 2022

    2022

  9. [17]

    Almost optimal lower bounds for small depth circuits

    J Hastad. Almost optimal lower bounds for small depth circuits. InProceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, STOC ’86, page 6–20, New York, NY , USA,

  10. [18]

    Division is in uniform TC0

    William Hesse. Division is in uniform TC0. InInternational Colloquium on Automata, Languages, and Programming, pages 104–114. Springer, 2001

    2001

  11. [19]

    Springer Verlag, 1998

    Neil Immerman.Descriptive Complexity. Springer Verlag, 1998

    1998

  12. [20]

    Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

    Daniel M Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. InProceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 633–643, 2016

    2016

  13. [21]

    Measuring faithfulness in chain-of-thought reasoning.arXiv preprint arXiv:2307.13702, 2023

    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

    2023 arXiv

  14. [22]

    Chain of thought empowers transformers to solve inherently serial problems

    Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. InThe Twelfth International Conference on Learning Representations, 2024. URLhttps://openreview.net/forum?id=3EWTEy9MTM

    2024

  15. [23]

    Venkitesh

    Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. A fixed-depth size-hierarchy theorem for AC0[⊕] via the coin problem, 2019. URL https: //arxiv.org/abs/1809.04092

    2019 arXiv

  16. [24]

    Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang

    Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Trans- formers learn shortcuts to automata. InThe Eleventh International Conference on Learning Representations, 2023. URLhttps://openreview.net/forum?id=De4FYqjFueZ

    2023

  17. [25]

    Papert.Counter-Free Automata (M.I.T

    Robert McNaughton and Seymour A. Papert.Counter-Free Automata (M.I.T. research mono- graph no. 65). The MIT Press, 1971. ISBN 0262130769

    1971

  18. [26]

    Formal languages and neural models for learning on sequences

    William Merrill. Formal languages and neural models for learning on sequences. InInternational Conference on Graphics and Interaction, 2023. URLhttps://api.semanticscholar.org/ CorpusID:261101973

    2023

  19. [27]

    The parallelism tradeoff: Limitations of log-precision transformers.Transactions of the Association for Computational Linguistics, 11:531–545, 2023

    William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers.Transactions of the Association for Computational Linguistics, 11:531–545, 2023

    2023

  20. [28]

    The expressive power of transformers with chain of thought

    William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. InThe Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=NjNGlPh8Wh

    2024

  21. [29]

    On limitations of the transformer architecture.ArXiv, abs/2402.08164, 2024

    Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture.ArXiv, abs/2402.08164, 2024. URL https://api.semanticscholar.org/ CorpusID:267636545

    2024 arXiv

  22. [30]

    Jacob Pfau, William Merrill, and Samuel R. Bowman. Let’s think dot by dot: Hidden computa- tion in transformer language models. InFirst Conference on Language Modeling, 2024. URL https://openreview.net/forum?id=NikbrdtYvG. 11

    2024

  23. [31]

    On the turing completeness of modern neural network architectures

    Jorge P´erez, Javier Marinkovi´c, and Pablo Barcel ´o. On the turing completeness of modern neural network architectures. InInternational Conference on Learning Representations, 2019. URLhttps://openreview.net/forum?id=HyGBdo0qFm

    2019

  24. [32]

    Language models are unsupervised multitask learners.OpenAI blog, 1(8):9, 2019

    Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners.OpenAI blog, 1(8):9, 2019

    2019

  25. [33]

    Representational strengths and limitations of transformers.ArXiv, abs/2306.02896, 2023

    Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers.ArXiv, abs/2306.02896, 2023. URL https://api.semanticscholar.org/ CorpusID:259075636

    2023 arXiv

  26. [34]

    What formal lan- guages can transformers express? a survey.Transactions of the Association for Computational Linguistics, 12:543–561, 2023

    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 https://api.semanticscholar.org/CorpusID: 264833196

    2023

  27. [35]

    Commonsenseqa: A question answering challenge targeting commonsense knowledge

    Alon Talmor, Jonathan Herzig, Nicholas Lourie, and Jonathan Berant. Commonsenseqa: A question answering challenge targeting commonsense knowledge. InProceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Languag...

    2019

  28. [36]

    Llama 2: Open foundation and fine-tuned chat models.arXiv preprint arXiv:2307.09288, 2023

    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 preprint arXiv:2307.09288, 2023

    2023 arXiv

  29. [37]

    Language models don’t always say what they think: unfaithful explanations in chain-of-thought prompting.Advances in Neural Information Processing Systems, 36, 2024

    Miles Turpin, Julian Michael, Ethan Perez, and Samuel Bowman. Language models don’t always say what they think: unfaithful explanations in chain-of-thought prompting.Advances in Neural Information Processing Systems, 36, 2024

    2024

  30. [38]

    Gomez, Łukasz Kaiser, and Illia Polosukhin

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. InProceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 6000–6010, Red Ho...

    2017

  31. [39]

    Chi, Quoc V Le, and Denny Zhou

    Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V 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...

    2022

  32. [41]

    2.Type:Type(i), indicating the gate’s operation (AND,OR,NOT)

    Arguments: Args(i, j), which specifies that the output of vertex j serves as an input to vertexi. 2.Type:Type(i), indicating the gate’s operation (AND,OR,NOT). ForTC 0 circuits, Vertex(i)is defined by the string:

  33. [42]

    2.Direction:Dir(i), which species if the threshold gate is>or<

    Arguments: Args(i, j), which specifies that the output of vertex j serves as an input to vertexi. 2.Direction:Dir(i), which species if the threshold gate is>or<

  34. [43]

    Threshold: Thresh(i), a numerical value θ 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 to a vertex would already have been computed by the time the vertex itself i...

  35. [1986]

    ISBN 0897911938

    Association for Computing Machinery. ISBN 0897911938. doi: 10.1145/12130.12132. URLhttps://doi.org/10.1145/12130.12132

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.