---
title: "Simulating Hard Attention Using Soft Attention — Yang 2026"
description: "For these, they build soft-attention transformers that use inverse-polynomial temperature or… 26 references, cited by 3 papers here."
authors: ["Andy Yang", "Lena Strobl", "David Chiang", "Dana Angluin"]
year: 2026
venue: "Transactions of the Association for Computational Linguistics"
source: "https://aclanthology.org/2026.tacl-1.8/"
doi: "10.1162/tacl.a.597"
licence: "CC BY 4.0 (ACL Anthology)"
licence_url: "https://creativecommons.org/licenses/by/4.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/yang-2026-simulating-hard-attention-soft-attention/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/yang-2026-simulating-hard-attention-soft-attention/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2026](https://md.research.elamur.ai/free/en/papers/2026/page/4/) / Simulating Hard Attention Using Soft Attention

# Simulating Hard Attention Using Soft Attention

**Authors:** Andy Yang, Lena Strobl, [David Chiang](https://md.research.elamur.ai/free/en/authors/david-chiang/) and [Dana Angluin](https://md.research.elamur.ai/free/en/authors/dana-angluin/) · **Year:** 2026 · **Venue:** [Transactions of the Association for Computational Linguistics](https://md.research.elamur.ai/free/en/venues/tacl/) ([Transactions of the Association for Computational Linguistics (TACL) 2026](https://md.research.elamur.ai/free/en/venues/tacl/2026/)) · **Publisher:** [The MIT Press](https://md.research.elamur.ai/free/en/publishers/the-mit-press/) · **Licence:** [CC BY 4.0 (ACL Anthology)](https://creativecommons.org/licenses/by/4.0/)

**Links:** [Publisher's page](https://aclanthology.org/2026.tacl-1.8/) · [PDF](https://aclanthology.org/2026.tacl-1.8.pdf) · [DOI 10.1162/tacl.a.597](https://doi.org/10.1162/tacl.a.597) · [OpenAlex](https://openalex.org/W7125481907)

**Citations:** 1 citations (OpenAlex, 2026-10-14) · 3 in our library, of the 149,439 papers whose bibliographies we read

## Summary
Theoretical analyses of transformers often assume hard attention, which puts all weight on the top-scoring position (unique-hard, UHAT) or spreads it evenly over all tied top positions (average-hard, AHAT). Practical models use softmax instead. This paper asks when softmax attention can reproduce hard attention in a general way that is also parameter-uniform, meaning one fixed set of parameters works for inputs of any length. A lemma by Hahn (2020) rules this out under standard assumptions, so the authors relax two of them: they allow temperature scaling or position embeddings that grow with input length.

They first study language classes recognized by hard-attention transformers that can be described in fragments of linear temporal logic, including the UHAT-recognizable languages. For these, they build soft-attention transformers that use inverse-polynomial temperature or polynomially bounded position embeddings. They then prove that any AHAT can be approximated by a softmax transformer with the same parameters. This works when the temperature is only slightly below the AHAT's attention-score gap γ(n). As a result, many existing hard-attention constructions carry over to soft attention.

## Key points
- Hahn's lemma says that soft attention with bounded position embeddings and Lipschitz operations makes outputs change by only O(1/n) when one input symbol changes. The paper lists four ways around this: temperature scaling, rounding, layer normalization, and unbounded PEs. It develops the first and the last.
- Every AHAT has a strictly positive gap (Proposition 24), and constructions in the literature typically have gaps of Ω(1/n^k).
- Theorem 26 says that for an AHAT with gap γ(n), a τ-SMAT with identical parameters stays within any inverse-polynomial error of it. For γ(n) = 1/n^k, the required inverse temperature is O(n^k log n). The hidden constant grows exponentially with depth L.
- The results apply to several tasks:
  - The k-hop induction head task is solvable with τ(n) = 1/n.
  - Every S-RASP transduction is exactly computable with τ(n) ∈ Ω(1/(n³ log n)).
  - DYCK-k is solvable with the same bound, via the algorithm of Yao et al. (2021).
- The authors conjecture that DYCK-2 cannot be defined in the temporal-logic fragment used for the first set of results.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [Yale University](https://md.research.elamur.ai/free/en/universities/yale-university/) — University, New Haven, United States · 95 works · 12,765 citations
- [University of Notre Dame](https://md.research.elamur.ai/free/en/universities/university-of-notre-dame/) — University, Notre Dame, United States · 51 works · 36,717 citations
- [Umeå University](https://md.research.elamur.ai/free/en/universities/umea-university/) — University, Umeå, Sweden · 4 works · 43 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 16,667 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 16,194 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 16,039 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 15,891 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 252 works

## Cite

Cite as: Andy Yang, Lena Strobl, David Chiang and Dana Angluin. 2026. Simulating Hard Attention Using Soft Attention. Transactions of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@article{yang2026simulating,
  title = {{Simulating Hard Attention Using Soft Attention}},
  author = {Andy Yang, Lena Strobl, David Chiang and Dana Angluin},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2026},
  doi = {10.1162/tacl.a.597},
  url = {https://doi.org/10.1162/tacl.a.597}
}
```

- [← previous Select2Reason: Efficient Instruction-Tuning Data Selection for Long-CoT Reasoning](https://md.research.elamur.ai/free/en/papers/yang-2026-select2reason-efficient-instruction-tuning-data/)
- [next → Sparse-RL: Breaking the Memory Wall in LLM Reinforcement Learning via Stable Sparse Rollouts](https://md.research.elamur.ai/free/en/papers/luo-2026-sparse-rl-breaking-memory-wall/)
- [↑ back to papers of 2026](https://md.research.elamur.ai/free/en/papers/2026/page/4/)

## References

26 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. [Layer normalization](https://md.research.elamur.ai/free/en/papers/ba-2016-layer-normalization/). In Proceedings of the NIPS 2016 Deep Learning Symposium.
2. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. [Neural machine translation by jointly learning to align and translate](https://md.research.elamur.ai/free/en/papers/bahdanau-2014-neural-machine-translation-jointly-learning/). In Proceedings of the Third International Conference on Learning Representations (ICLR). problems. In Proceedings of the 12th International Conference on Learning Represen…
3. Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. 2023a. Exposing attention glitches with flip-flop language modeling. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 25549–25583. [find](https://scholar.google.com/scholar?q=Bingbin+Liu%2C+Jordan+T%2E+Ash%2C+Surbhi+Goel%2C+Akshay+Krishnamurthy%2C+and+Cyril+Zhang%2E+2023a%2E+Exposing+attention+glitches+with+flip%2Dflop+language+modeling%2E+In+Advances+in+Neural+Information+Processing+System)
4. Pablo Barceló, Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir Podolskii. 2024. Logical languages accepted by transformer encoders with hard attention. In Proceedings of the Twelfth International Conference on Learning Representations (ICLR). [find](https://scholar.google.com/scholar?q=Pablo+Barcelo%CC%81%2C+Alexander+Kozachinskiy%2C+Anthony+Widjaja+Lin%2C+and+Vladimir+Podolskii%2E+2024%2E+Logical+languages+accepted+by+transformer+encoders+with+hard+attention%2E+In+Proceedings+of+the+Twelfth+Interna)
5. Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. 2023b. Transformers learn shortcuts to automata. In Proceedings of the Eleventh International Conference on Learning Representations (ICLR). [find](https://scholar.google.com/scholar?q=Bingbin+Liu%2C+Jordan+T%2E+Ash%2C+Surbhi+Goel%2C+Akshay+Krishnamurthy%2C+and+Cyril+Zhang%2E+2023b%2E+Transformers+learn+shortcuts+to+automata%2E+In+Proceedings+of+the+Eleventh+International+Conference+on+Learning+Rep)
6. David Chiang. 2025. Transformers in uniform TC 0 . Transactions on Machine Learning Research. [find](https://scholar.google.com/scholar?q=David+Chiang%2E+2025%2E+Transformers+in+uniform+TC+0+%2E+Transactions+on+Machine+Learning+Research%2E)
7. David Chiang and Peter Cholak. 2022. Overcoming a theoretical limitation of self-attention. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (ACL), pages 7654–7664. https://doi.org/10.18653/v1/2022.acl-long.527 [↗](https://doi.org/10.18653/v1/2022.acl-long.527)
8. Colin McDonald and David Chiang. 2021. Syntax-based attention masking for neural machine translation. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Student Research Workshop, pages 47–52, Online. Association for Computational Li… [find](https://scholar.google.com/scholar?q=Colin+McDonald+and+David+Chiang%2E+2021%2E+Syntax%2Dbased+attention+masking+for+neural+machine+translation%2E+In+Proceedings+of+the+2021+Conference+of+the+North+American+Chapter+of+the+Association+for+Computa)
9. Benjamin L. Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. 2022. Inductive biases and variable creation in self-attention mechanisms. In Proceedings of the International Conference on Machine Learning (ICML), pages 5793–5831. [find](https://scholar.google.com/scholar?q=Benjamin+L%2E+Edelman%2C+Surbhi+Goel%2C+Sham+Kakade%2C+and+Cyril+Zhang%2E+2022%2E+Inductive+biases+and+variable+creation+in+self%2Dattention+mechanisms%2E+In+Proceedings+of+the+International+Conference+on+Machine+Lea)
10. William Merrill, Jackson Petty, and Ashish Sabharwal. 2024. The illusion of state in state-space models. In Proceedings of the International Conference on Machine Learning (ICML). [find](https://scholar.google.com/scholar?q=William+Merrill%2C+Jackson+Petty%2C+and+Ashish+Sabharwal%2E+2024%2E+The+illusion+of+state+in+state%2Dspace+models%2E+In+Proceedings+of+the+International+Conference+on+Machine+Learning+%28ICML%29%2E)
11. 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, Dario Amodei, Tom Brown, Ja… [find](https://scholar.google.com/scholar?q=Nelson+Elhage%2C+Neel+Nanda%2C+Catherine+Olsson%2C+Tom+Henighan%2C+Nicholas+Joseph%2C+Ben+Mann%2C+Amanda+Askell%2C+Yuntao+Bai%2C+Anna+Chen%2C+Tom+Conerly%2C+Nova+DasSarma%2C+Dawn+Drain%2C+Deep+Ganguli%2C+Zac+Hatfield%2DDodds%2C+Da)
12. Ken M. Nakanishi. 2025. Scalable-softmax is superior for attention. arXiv:2501.19399, Jorge Pérez, Javier Marinkovic, and Pablo Barceló. 2019. On the Turing completeness of modern neural network architectures. In Proceedings of the Seventh International Conference on Learning Representations (ICLR… — [arXiv:2501.19399](https://arxiv.org/abs/2501.19399) [find](https://scholar.google.com/scholar?q=Ken+M%2E+Nakanishi%2E+2025%2E+Scalable%2Dsoftmax+is+superior+for+attention%2E+arXiv%3A2501%2E19399%2C+Jorge+Pe%CC%81rez%2C+Javier+Marinkovic%2C+and+Pablo+Barcelo%CC%81%2E+2019%2E+On+the+Turing+completeness+of+modern+neural+network+arc)
13. Dan Friedman, Alexander Wettig, and Danqi Chen. 2023. Learning Transformer programs. In Advances in Neural Information Processing Systems 36 (NeurIPS). [find](https://scholar.google.com/scholar?q=Dan+Friedman%2C+Alexander+Wettig%2C+and+Danqi+Chen%2E+2023%2E+Learning+Transformer+programs%2E+In+Advances+in+Neural+Information+Processing+Systems+36+%28NeurIPS%29%2E)
14. Clayton Sanford, Daniel Hsu, and Matus Telgarsky. 2024. Transformers, parallel computation, and logarithmic depth. In Proceedings of the International Conference on Machine Learning (ICML). [find](https://scholar.google.com/scholar?q=Clayton+Sanford%2C+Daniel+Hsu%2C+and+Matus+Telgarsky%2E+2024%2E+Transformers%2C+parallel+computation%2C+and+logarithmic+depth%2E+In+Proceedings+of+the+International+Conference+on+Machine+Learning+%28ICML%29%2E)
15. Michael Hahn. 2020. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8, 156–171. https://doi.org/10.1162/tacl_a_00306 [↗](https://doi.org/10.1162/tacl_a_00306)
16. Tao Shen, Tianyi Zhou, Guodong Long, Jing Jiang, Shirui Pan, and Chengqi Zhang. 2018. [DiSAN: Directional self-attention network for RNN/CNN-free language understanding](https://md.research.elamur.ai/free/en/papers/shen-2017-disan-directional-self-attention-network/). In Proceedings of the 32nd AAAI Conference on Artificial Intelligence. https://doi.org/10.1609/aaai.v32i1.11941 [↗](https://doi.org/10.1609/aaai.v32i1.11941)
17. Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. 2024. Chain of thought empowers transformers to solve inherently serial Kenneth J. Sible and David Chiang. 2024. Improving rare word translation with dictionaries and attention masking. In Proceedings of the 16th Conference of the Association for Mach… [find](https://scholar.google.com/scholar?q=Zhiyuan+Li%2C+Hong+Liu%2C+Denny+Zhou%2C+and+Tengyu+Ma%2E+2024%2E+Chain+of+thought+empowers+transformers+to+solve+inherently+serial+Kenneth+J%2E+Sible+and+David+Chiang%2E+2024%2E+Improving+rare+word+translation+with+d)
18. A MLP Rounding Lena Strobl, Dana Angluin, David Chiang, Jonathan Rawski, and Ashish Sabharwal. 2025. Transformers as transducers. Transactions of the Association for Computational Linguistics, 13:200–219. https://doi.org/10 .1162/tacl_a_00736 [find](https://scholar.google.com/scholar?q=A+MLP+Rounding+Lena+Strobl%2C+Dana+Angluin%2C+David+Chiang%2C+Jonathan+Rawski%2C+and+Ashish+Sabharwal%2E+2025%2E+Transformers+as+transducers%2E+Transactions+of+the+Association+for+Computational+Linguistics%2C+13%3A200%E2%80%93)
19. Proof. Telgarsky (2015, Lemma 2.1) proves that if a ReLU FFN of depth  and width m computes a function f : R → R then f is continuous piecewise affine with at most (2 m )  pieces. So we need to show that any piecewise affine function rounding a p  -bit number to a p -bit number requires at least… [find](https://scholar.google.com/scholar?q=Proof%2E+Telgarsky+%282015%2C+Lemma+2%2E1%29+proves+that+if+a+ReLU+FFN+of+depth+%04+and+width+m+computes+a+function+f+%3A+R+%E2%86%92+R+then+f+is+continuous+piecewise+affine+with+at+most+%282+m+%29+%04+pieces%2E+So+we+need+to+show)
20. Because Sanford et al. (2024) consider precision p = Θ(log n ) and p  \> p , this implies that a constant-depth ReLU MLP to round p  -bit numbers to p -bit numbers must have width at least n for some \> 0. [find](https://scholar.google.com/scholar?q=Because+Sanford+et+al%2E+%282024%29+consider+precision+p+%3D+%CE%98%28log+n+%29+and+p+%11+%5C%3E+p+%2C+this+implies+that+a+constant%2Ddepth+ReLU+MLP+to+round+p+%11+%2Dbit+numbers+to+p+%2Dbit+numbers+must+have+width+at+least+n+for+som)
21. Lemma 27. Let p and p  be positive integers with p  \> p . Any ReLU FFN to round p  -bit numbers to p -bit numbers with  layers and width m satisfies (2 m )  ≥ 2 p . [find](https://scholar.google.com/scholar?q=Lemma+27%2E+Let+p+and+p+%11+be+positive+integers+with+p+%11+%5C%3E+p+%2E+Any+ReLU+FFN+to+round+p+%11+%2Dbit+numbers+to+p+%2Dbit+numbers+with+%04+layers+and+width+m+satisfies+%282+m+%29+%04+%E2%89%A5+2+p+%2E)
22. Anej Svete and Ryan Cotterell. 2024. 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 Technologies (NAACL HLT), pages 6841–6874. https://doi.org/10 .18653/v1/2024.n… [find](https://scholar.google.com/scholar?q=Anej+Svete+and+Ryan+Cotterell%2E+2024%2E+Transformers+can+represent+n+%2Dgram+language+models%2E+In+Proceedings+of+the+2024+Conference+of+the+North+American+Chapter+of+the+Association+for+Computational+Lingui)
23. Matus Telgarsky. 2015. Representation benefits of deep feedforward networks. arXiv:1509.08101. — [arXiv:1509.08101](https://arxiv.org/abs/1509.08101) [find](https://scholar.google.com/scholar?q=Matus+Telgarsky%2E+2015%2E+Representation+benefits+of+deep+feedforward+networks%2E+arXiv%3A1509%2E08101%2E+%E2%80%94+%5BarXiv%3A1509%2E08101%5D%28https%3A%2F%2Farxiv%2Eorg%2Fabs%2F1509%2E08101%29)
24. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. [Attention is all you need](https://md.research.elamur.ai/free/en/papers/vaswani-2017-attention-all-need/). In Advances in Neural Information Processing Systems 30 (NeurIPS).
25. Andy Yang and David Chiang. 2024. Counting like transformers: Compiling temporal counting logic into softmax transformers. In Proceedings of the Conference on Language Modeling (CoLM). [find](https://scholar.google.com/scholar?q=Andy+Yang+and+David+Chiang%2E+2024%2E+Counting+like+transformers%3A+Compiling+temporal+counting+logic+into+softmax+transformers%2E+In+Proceedings+of+the+Conference+on+Language+Modeling+%28CoLM%29%2E)
26. Andy Yang, David Chiang, and Dana Angluin. 2024. Masked hard-attention transformers recognize exactly the star-free languages. In Advances in Neural Information Processing Systems 37 (NeurIPS). [find](https://scholar.google.com/scholar?q=Andy+Yang%2C+David+Chiang%2C+and+Dana+Angluin%2E+2024%2E+Masked+hard%2Dattention+transformers+recognize+exactly+the+star%2Dfree+languages%2E+In+Advances+in+Neural+Information+Processing+Systems+37+%28NeurIPS%29%2E)

*Updated 31 October 2026*