Pith. sign in

REVIEW 1 major objections 4 minor 27 references

Simulating Hard Attention Using Soft Attention

T0 review · 1 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read A gap-based temperature bound makes softmax attention a faithful stand-in for average-hard attention, with the same transformer parameters.

desk verdict A genuinely new and correct simulation theorem: softmax transformers can approximate average-hard attention with temperature tied to the score gap; the paper deserves a serious review. read the letter →

arxiv 2412.09925 v2 pith:Z5ZGCFCM submitted 2024-12-13 cs.LG cs.CLcs.FL

Andy Yang , Lena Strobl , David Chiang , Dana Angluin This is my paper · ORCID
classification cs.LGcs.CLcs.FL MSC 68T0768Q4503B44
keywords average-hardattentiontemperaturescalingsoftmaxtemporallogicwithcountingtransformerspositionembeddingsparameter-uniformsimulation
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

This paper asks when the standard softmax attention used in transformers can replicate hard attention, where all weight is placed on the maximally scoring position or positions even though softmax never assigns exact zeros or ones. It proves that for several logics that capture what hard-attention transformers recognize—temporal logics with previous/next, since/until, and counting terms—softmax transformers can simulate them using either an inverse-polynomial temperature or polynomially growing position embeddings. The main theorem is general: an average-hard attention transformer whose attention scores are separated by a gap $\gamma(n)$ can be approximated by the same-parameter softmax transformer at temperature $\tau$ with $1/\tau(n) \in O((1/\gamma(n)) \log(n x_{\max}(n)/\gamma(n)))$. For the gap $\gamma(n)=1/n^k$ and polynomially bounded inputs, this is $1/\tau(n) \in O(n^k \log n)$, so the cooling needed stays inverse-polynomial. This matters because many discrete reasoning tasks have previously been solved only with hard attention, and the result gives parameter-uniform soft-attention solutions with controlled error.

What carries the argument

The load-bearing object is the gap $\gamma(n)$: the smallest difference between a maximal attention score and any other score, over all inputs of length $n$. The mechanism is temperature-dependent softmax, $\mathrm{softmax}_\tau(s)_j = \exp(s_j/\tau)/\sum_k \exp(s_k/\tau)$, which concentrates on the maximum once the gap is amplified to $\gamma/\tau$. The proof bounds the approximation error per layer by roughly $n e^{-\gamma/\tau}$ plus a propagated input error multiplied by $x_{\max}/\tau$, using a ziggurat score-shape lemma, parabolic table-lookup scores, and specially constructed tie-breaking score perturbations that turn rightmost or leftmost hardmax into softmax-friendly patterns. A feedforward rounding function converts approximate Booleans back to exact $0/1$ values, and first/last-position markers supply quantities like $1/i$ that the attention patterns need. Iterating the per-layer error bound through $L$ layers yields the temperature formula in Theorem 26, with constants that may grow exponentially in depth but not in $n$.

What would settle it

Run the paper's S-RASP-derived DYCK-2 transformer in fixed-precision floating point (say 32-bit) for $n = 2^{16}$, with the prescribed temperature $\tau \approx 1/(n^3 \log n)$, and check whether the winning position still receives a clear majority of attention weight; if rounding makes the scores collapse to a tie, the simulation depends essentially on the unbounded-precision assumption, which the paper states but does not remove.

Watch

Extended reading notes

Core claim

The central claim is Theorem 26: every average-hard attention transformer $T$ with gap $\gamma(n)$ can be approximately simulated by the softmax transformer obtained by replacing $\mathrm{ahardmax}$ by softmax at temperature $\tau$, with exactly the same parameters, provided $1/\tau(n) \in O((1/\gamma(n)) \log(n x_{\max}(n)/\gamma(n)))$. Here $x_{\max}(n)$ bounds the initial activation entries over all inputs of length $n$, and $\gamma(n)$ is the minimum separation between the maximum attention score and every lower score across all layers, positions, and inputs of that length. If $\gamma(n) = 1/n^k$ and $x_{\max}(n)$ is polynomial in $n$, then $1/\tau(n) \in O(n^k \log n)$. The paper also proves matching simulations for subclasses: the logics $\mathrm{TL}[\ominus,\oplus]$, $\mathrm{TL}[\text{since},\text{until}]$, and the counting logic $\mathrm{TL}[\reflectbox{$\leftharpoonup$}\#,\rightharpoonup\#, +, \mathrm{Mon}]$ can each be computed by softmax transformers with $\tau = 1/n$ and bounded position embeddings, or with $\tau = 1$ and position embeddings that include $n$, $i/n$, $i$, and $i^2$ as needed.

Load-bearing premise

The constructions assume exact real-valued arithmetic, so attention scores can encode differences as small as $1/\mathrm{poly}(n)$ and position embeddings can carry unbounded values like $n$, $i/n$, and $1/i$ without precision loss.

Editorial extensions

If this is right

  • Every transduction expressible in the S-RASP programming language is computable by a softmax transformer with temperature $\tau(n) \in \Omega(1/(n^3 \log n))$, because S-RASP compiles to an average-hard attention transformer with gap $\Omega(1/n^3)$.
  • The DYCK-$k$ balanced-bracket language becomes computable by a softmax transformer with the same $\Omega(1/(n^3 \log n))$ temperature, via the paper's S-RASP program for prefix validity.
  • The basic and iterated induction-head tasks are computable by a softmax transformer with $\tau(n)=1/n$, because they are definable in the since/until temporal logic that the paper simulates at that temperature.
  • All these simulations are parameter-uniform: the same weights work for every input length, unlike earlier rounding-based simulations whose depth or width must grow with $n$.
  • Because approximate Booleans are rounded exactly, the simulations compose: a module with a fixed-size acceptance gap can feed into later modules that expect exact discrete inputs.

Reading between the lines

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

  • A testable practical reading is that training with a temperature schedule tied to sequence length—cooling like $1/n$ or $1/(n^k \log n)$ for tasks with known gap—should let a standard softmax transformer solve discrete subroutines rather than merely approximating them; this is an extension, since the paper proves existence in an exact-arithmetic model, not trainability.
  • The results suggest that hard attention is not an expressivity boost over soft attention for these classes; the same parameters run in soft mode already suffice once temperature or position embeddings are allowed to vary with input length. An implicit consequence is that the real obstruction in previous no-go results is fixed temperature and bounded position embeddings, not softness itself.
  • A natural next step would be to combine temperature scaling with layer normalization or rounding and ask whether the required precision or cooling can be reduced; the paper lists these as separate interventions but does not analyze their interaction.
  • For practitioners, the gap $\gamma(n)$ can be measured empirically by running a trained or constructed model over all inputs up to some $n$ and recording the minimum score separation; if that gap decays faster than any inverse polynomial, the theory predicts such a model will need much colder temperatures to keep its hard-attention behavior.
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

1 major / 4 minor

Summary. The paper studies when softmax attention can simulate hard attention in transformers. It first proves that several fragments of linear temporal logic (TL[⊖,⊕], TL[since,until], and the counting logic LTL[↼#,⇀#,+,Mon]) can be simulated by temperature-scaled softmax transformers, either with inverse-polynomial temperature or with polynomially unbounded position embeddings. These results cover the star-free languages recognized by unique-hard attention transformers and extend to counting terms and numerical predicates. The paper then proves its main theorem (Theorem 26): any average-hard attention transformer with gap γ(n) can be approximated by a softmax transformer with the same parameters, using a temperature τ(n) satisfying 1/τ(n) in O((1/γ(n)) log(n x_max(n)/γ(n))). In the typical case γ(n)=1/n^k and x_max(n) in n^{O(1)}, this gives 1/τ(n) in O(n^k log n). The proofs are carried out through explicit softmax-versus-hardmax concentration bounds, tie-breaking constructions, and a layerwise error propagation lemma. The paper closes with applications to induction heads, S-RASP transductions, and Dyck language membership.

Significance. If the results hold, they resolve a natural open question about the relationship between hard and soft attention in a parameter-uniform, rate-explicit way. The constructions are general and parameter-uniform, and the temperature schedule is tied to a concrete, checkable quantity (the attention-score gap). The paper gives explicit credit to prior work, including the parameter-free UHAT-equals-LTL characterization of Yang et al. (2024), and builds on it without circularity. The main theorem is supported by a detailed chain of lemmas (Lemma 6, Lemmas 8 and 7, Lemma 25, Lemma 29, and the geometric-series composition in Theorem 26). The applications to induction heads, S-RASP, and Dyck-k are concrete and illustrate the reach of the results. A caveat, stated clearly in the paper, is that the constructions use exact real arithmetic and unbounded position embeddings; the quantitative guarantees would need revisiting under fixed-precision arithmetic.

major comments (1)
  1. [Section 5, Theorem 26 (Appendix C.4)] Lemma 25 is stated for input perturbations with ε ≤ 1, but the iterative proof of Theorem 26 applies the lemma layer after layer without explicitly verifying that the intermediate layer errors stay bounded by 1. This is a genuine gap in the proof as written, though it is easily fixed: choose the constant in the O-bound so that the final error bound is below 1; because the geometric bound is monotone in the layer index, all intermediate bounds are then also below 1. Adding this verification would make the proof fully rigorous.
minor comments (4)
  1. [Section 3.3, Lemma 8] The symbol γ is used both for the gap of the original scores and for the scaling factor in the transformed scores. The proof is correct, but the double use is confusing; consider renaming one of the two parameters.
  2. [Appendix C.4, proof of Theorem 26] The recursion as displayed contains two typos: the term 'a = K x_max n e^{γ/τ}' should read 'a = K x_max n e^{-γ/τ}', and the condition on ε(n) should be ε(n) ≥ α/n^β rather than ε(n) ≤ α/n^β, since ε(n) ∈ Ω(1/poly(n)) is a lower bound on the allowed error. The intended reasoning is clear, but the displayed formulas should be corrected.
  3. [Section 4.1, Theorem 12(a)] The score formula ͡s_{ij}=6(½(−1)^j+j/(2n)) is combined with temperature τ=1/n to obtain the effective scaled scores of Theorem 8b. The role of the temperature in producing the factor n could be made explicit, since the connection is easy to miss.
  4. [Section 5, Definition of x_max] The definition of x_max(n) as the maximum absolute entry of initial activation vectors is fine, but the sentence 'This is well defined because there are finitely many different inputs of length n' should also mention that the position embedding PE_n(i) and the word embedding take only finitely many values for fixed n; this is implicit but worth stating.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the simulation theorems are derived from explicit first-principles bounds; self-citations are independent, parameter-free prior results and are not used to force the paper's new conclusions.

full rationale

The paper's central result, Theorem 26, is a direct constructive bound: given an AHA transformer with gap gamma(n), Lemmas 6-8 establish exponential softmax-versus-hardmax concentration under ziggurat, table-lookup, and tie-breaking score patterns; Lemma 25 bounds one-layer error by K x_max(n)(n e^{-gamma/tau} + x_max(n) epsilon/tau); Theorem 26 iterates this per-layer bound through a geometric series to obtain 1/tau in O((1/gamma) log(n x_max/gamma)). The bound depends on the AHA transformer's worst-case score gap, which is an input condition of the theorem, not an output fitted by the simulation. The LTL simulations in Theorems 12, 15, and 20 are likewise built from explicit attention-score constructions and FFN rounding, with no parameter fitted to the target language or to an observed prediction. The paper does cite prior work by overlapping authors—Yang et al. (2024) for the UHA-T/LTL equivalence and for elementary Boolean/FFN facts, Yang and Chiang (2024) for prefix-count constructions—but those results are published, parameter-free, and independent of the present simulation claims; none is a uniqueness theorem or an ansatz that smuggles in the conclusion. The only caveats are the paper's explicitly stated model assumptions (real-valued arithmetic and unbounded position embeddings) and a minor technical gap in the proof of Theorem 26: Lemma 25 is stated for input errors epsilon <= 1, but the layer recursion does not explicitly verify this invariant before reapplying the lemma. That gap is patchable by choosing the constant in the O-bound so the intermediate errors remain below 1, and it is a rigor issue, not circularity. No step in the derivation reduces to its own input by construction.

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

The central claims rest on standard mathematical analysis, the transformer model definitions, and two prior theorems (one self-authored). No new physical or architectural entities are postulated. The free parameters are analytical choices, not data-fitted values.

free parameters (3)
  • temperature schedule tau(n) = 1/n, 1/i^2, or 1/i depending on theorem
    Chosen by hand to make the effective score gap constant; the value depends on the input length n but is not learned from data.
  • attention score scale factors (e.g., 6, 2*gamma*n, gamma*n^2) = 6 in Theorem 12/15; 3 in Theorem 20; gamma*n^2 in Lemma 8a
    Constants selected so that the ziggurat gap conditions of Lemma 6 are satisfied, producing the desired error bounds.
  • Boolean rounding threshold delta = 1/4
    Arbitrarily chosen in Lemma 9; any delta < 1/2 works, affecting only constants.
assumptions (4)
  • domain assumption Masked UHA transformers recognize exactly the LTL-definable languages (Yang et al. 2024)
    Used to extend the LTL simulations in Corollary 17 to all masked UHA transformers; this is a prior theorem, not re-proved here.
  • domain assumption Softmax attention with temperature tau converges to hard attention as tau approaches 0, with the Edelman et al. (2022) bound for the rate
    Basis for the error bound in Lemma 32; cited prior work supplies the constant.
  • domain assumption Transformers compute with exact real numbers and arbitrary-precision position embeddings
    All constructions rely on exact arithmetic, e.g., computing i/n, 1/i, and n inside attention scores. No finite-precision model is assumed.
  • domain assumption Multi-head attention can be simulated by multiple single-head layers with residual connections
    Stated in Section 2.2; used implicitly so that single-head constructions suffice.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Simulating Hard Attention Using Soft Attention." pith.science (2026). https://pith.science/paper/Z5ZGCFCM

@misc{pith2026241209925,
  author       = {Pith},
  title        = {Pith review of: Simulating Hard Attention Using Soft Attention},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z5ZGCFCM}},
  note         = {Machine review of arXiv:2412.09925}
}
read the original abstract

We study conditions under which transformers using soft attention can simulate hard attention, that is, effectively focus all attention on a subset of positions. First, we examine several subclasses of languages recognized by hard-attention transformers, which can be defined in variants of linear temporal logic. We demonstrate how soft-attention transformers can compute formulas of these logics using unbounded positional embeddings or temperature scaling. Second, we demonstrate how temperature scaling allows softmax transformers to simulate general hard-attention transformers, using a temperature that depends on the minimum gap between the maximum attention scores and other attention scores.

Figures

Figures reproduced from arXiv: 2412.09925 by the authors.

Figure 1
Figure 1. Simulation by 𝜏-SMAT. Solid arrows denote results proved in this paper. Key: 𝜏 = tem￾perature; PE = position embedding. Thus, LTL[ ↼ # , ⇀ # , +, Mon] defines a subclass of the languages recognized by AHATs, and various frag￾ments of LTL[ ↼ # , ⇀ # , +, Mon] define smaller sub￾classes. Our first set of results (Section 4) ex￾amines several such subclasses – among them, the languages recognized by UHATs – and shows t… view at source ↗
Figure 2
Figure 2. Illustration of the various attention score [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 16 canonical work pages

  1. [1]

    URL: " 'urlintro :=

    ENTRY address author booktitle chapter edition editor howpublished institution journal key month note number organization pages publisher school series title type volume year eprint doi pubmed url lastchecked label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block STRINGS urlintro eprinturl eprintpr...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  3. [3]

    Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. https://doi.org/10.48550/arXiv.1607.06450 Layer normalization

    arXiv doi:10.48550/arxiv.1607.06450 2016

  4. [4]

    Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. https://arxiv.org/abs/1409.0473 Neural machine translation by jointly learning to align and translate . In Proceedings of the Third International Conference on Learning Representations (ICLR)

    arXiv 2015

  5. [5]

    Pablo Barcel \'o , Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir Podolskii. 2024. https://openreview.net/forum?id=gbrHZq07mq Logical languages accepted by transformer encoders with hard attention . In Proceedings of the Twelfth International Conference on Learning Representations (ICLR)

    work page 2024

  6. [6]

    David Chiang and Peter Cholak. 2022. https://doi.org/10.18653/v1/2022.acl-long.527 Overcoming a theoretical limitation of self-attention . In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (ACL), pages 7654--7664

    doi:10.18653/v1/2022.acl-long.527 2022

  7. [7]

    R \'o bert Csord \'a s, Kazuki Irie, and J \"u rgen Schmidhuber. 2022. https://openreview.net/forum?id=KBQP4A_J1K The neural data router: Adaptive control flow in transformers improves systematic generalization . In Proceedings of the Tenth International Conference on Learning Representations (ICLR)

    work page 2022

  8. [8]

    Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang

    Benjamin L. Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. 2022. https://proceedings.mlr.press/v162/edelman22a.html Inductive biases and variable creation in self-attention mechanisms . In Proceedings of the International Conference on Machine Learning (ICML), pages 5793--5831

    work page 2022

Show all 27 references
  1. [9]

    Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dari...

    2021

  2. [10]

    Dan Friedman, Alexander Wettig, and Danqi Chen. 2023. https://papers.nips.cc/paper_files/paper/2023/hash/995f693b73050f90977ed2828202645c-Abstract-Conference.html Learning T ransformer programs . In Advances in Neural Information Processing Systems 36 (NeurIPS)

    2023

  3. [11]

    Michael Hahn. 2020. https://doi.org/10.1162/tacl_a_00306 Theoretical limitations of self-attention in neural sequence models . Transactions of the Association for Computational Linguistics, 8:156--171

    2020 doi

  4. [12]

    Yiding Hao, Dana Angluin, and Robert Frank. 2022. https://doi.org/10.1162/tacl_a_00490 Formal language recognition by hard attention transformers: Perspectives from circuit complexity . Transactions of the Association for Computational Linguistics, 10:800--810

    2022 doi

  5. [13]

    Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. 2024. https://openreview.net/forum?id=3EWTEy9MTM Chain of thought empowers transformers to solve inherently serial problems . In Proceedings of the 12th International Conference on Learning Representations (ICLR)

    2024

  6. [14]

    Bingbin Liu, Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. 2023 a . https://proceedings.neurips.cc/paper_files/paper/2023/hash/510ad3018bbdc5b6e3b10646e2e35771-Abstract-Conference.html Exposing attention glitches with flip-flop language modeling . In Advanc...

    2023

  7. [15]

    Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang

    Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. 2023 b . https://openreview.net/forum?id=De4FYqjFueZ Transformers learn shortcuts to automata . In Proceedings of the Eleventh International Conference on Learning Representations (ICLR)

    2023

  8. [16]

    Andre Martins and Ramon Astudillo. 2016. https://proceedings.mlr.press/v48/martins16.html From softmax to sparsemax: A sparse model of attention and multi-label classification . In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 1614--1623

    2016

  9. [17]

    William Merrill, Jackson Petty, and Ashish Sabharwal. 2024. https://proceedings.mlr.press/v235/merrill24a.html The illusion of state in state-space models . In Proceedings of the International Conference on Machine Learning (ICML)

    2024

  10. [18]

    William Merrill, Ashish Sabharwal, and Noah A. Smith. 2022. https://doi.org/10.1162/tacl_a_00493 Saturated transformers are constant-depth threshold circuits . Transactions of the Association for Computational Linguistics, 10:843--856

    2022 doi

  11. [19]

    Jorge Pérez, Javier Marinković, and Pablo Barceló. 2019. https://openreview.net/forum?id=HyGBdo0qFm On the T uring completeness of modern neural network architectures . In Proceedings of the Seventh International Conference on Learning Representations (ICLR)

    2019

  12. [20]

    Clayton Sanford, Daniel Hsu, and Matus Telgarsky. 2024. https://proceedings.mlr.press/v235/sanford24a.html Transformers, parallel computation, and logarithmic depth . In Proceedings of the International Conference on Machine Learning (ICML)

    2024

  13. [21]

    Lena Strobl, Dana Angluin, David Chiang, Jonathan Rawski, and Ashish Sabharwal. 2024. https://arxiv.org/abs/2404.02040 Transformers as transducers . Transactions of the Association for Computational Linguistics. To appear

    2024 arXiv

  14. [22]

    Anej Svete and Ryan Cotterell. 2024. https://aclanthology.org/2024.naacl-long.381 Transformers can represent n -gram language models . In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolog...

    2024

  15. [23]

    Matus Telgarsky. 2015. https://doi.org/10.48550/arXiv.1509.08101 Representation benefits of deep feedforward networks . arXiv :1509.08101

    2015 doi arXiv

  16. [24]

    Gomez, Lukasz Kaiser, and Illia Polosukhin

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. https://proceedings.neurips.cc/paper/2017/hash/3f5ee243547dee91fbd053c1c4a845aa-Abstract.html Attention is all you need . In Advances in Neural I...

    2017

  17. [25]

    Andy Yang and David Chiang. 2024. https://openreview.net/forum?id=FmhPg4UJ9K Counting like transformers: Compiling temporal counting logic into softmax transformers . In Proceedings of the Conference on Language Modeling (CoLM)

    2024

  18. [26]

    Andy Yang, David Chiang, and Dana Angluin. 2024. https://arxiv.org/abs/2310.13897 Masked hard-attention transformers recognize exactly the star-free languages . In Advances in Neural Information Processing Systems (NeurIPS). To appear

    2024 arXiv

  19. [27]

    Shunyu Yao, Binghui Peng, Christos Papadimitriou, and Karthik Narasimhan. 2021. https://doi.org/10.18653/v1/2021.acl-long.292 Self-attention networks can process bounded hierarchical languages . In Proceedings of the 59th Annual Meeting of the Association for Computational Lin...

    2021 doi

Pith tools

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