Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers

Amiri, Alireza; Huang, Xinting; Rofin, Mark; Hahn, Michael

by Alireza Amiri, Xinting Huang, Mark Rofin, Michael Hahn

Reference:

Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention TransformersAlireza Amiri, Xinting Huang, Mark Rofin, Michael HahnPreprint, 2025.

Bibtex Entry:

@article{amiri2025lowerboundschainofthoughtreasoning,
      title={Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers}, 
      author={Alireza Amiri and Xinting Huang and Mark Rofin and Michael Hahn},
      year={2025},
      journal={Preprint},
      url={https://arxiv.org/abs/2502.02393}, 
}