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 HahnThe Forty-Second International Conference on Machine Learning (ICML, Accepted), 2025.

Bibtex Entry:

@inproceedings{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},
      month={july},
      booktitle={The Forty-Second International Conference on Machine Learning (ICML, Accepted)},
      github={https://github.com/lacoco-lab/scratchpad-bounds},
      url={https://arxiv.org/abs/2502.02393}, 
}