@inproceedings{yuan-etal-2026-barriers,
    title = "Barriers to Discrete Reasoning with Transformers: A Survey Across Depth, Exactness, and Bandwidth",
    author = "Yuan, Michelle  and
      Sun, Weiyi  and
      Rezaeian, Amir H.  and
      Singh, Jyotika  and
      Ghoshal, Sandip  and
      Wang, Yao-Ting  and
      Ballesteros, Miguel  and
      Benajiba, Yassine",
    editor = "Demberg, Vera  and
      Inui, Kentaro  and
      Marquez, Llu{\'i}s",
    booktitle = "Proceedings of the 19th Conference of the {E}uropean Chapter of the {A}ssociation for {C}omputational {L}inguistics (Volume 1: Long Papers)",
    month = mar,
    year = "2026",
    address = "Rabat, Morocco",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-eacl/2026.eacl-long.87/",
    pages = "1966--1978",
    ISBN = "979-8-89176-380-7",
    abstract = "Transformers have become the foundational architecture for a broad spectrum of sequence modeling applications, underpinning state-of-the-art systems in natural language processing, vision, and beyond. However, their theoretical limitations in discrete reasoning tasks, such as arithmetic, logical inference, and algorithmic composition, remain a critical open problem. In this survey, we synthesize recent advances from three theoretical perspectives: circuit complexity, approximation theory, and communication complexity, to clarify the structural and computational barriers that transformers face when performing symbolic computations. By connecting these established theoretical frameworks, we provide an accessible and unified account of why current transformer architectures struggle to implement exact discrete algorithms, even as they excel at pattern matching and interpolation. We review key definitions, seminal results, and illustrative examples, highlighting challenges such as depth constraints, difficulty approximating discontinuities, and bottlenecks in inter-token communication. Finally, we discuss implications for model design and suggest promising directions for overcoming these foundational limitations."
}