mlsanityData to 14 Oct 2026

Ehrenfeucht-Haussler Rank and Chain of Thought

arXiv 2501.12997 ↗First posted 22 Jan 2025cs.LG cs.AIcited by 6

On the map: LLM reasoning → Prompting and chain-of-thought reasoning

Abstract (arXiv)

The notion of rank of a Boolean function has been a cornerstone in PAC learning theory, enabling quasipolynomial-time learning algorithms for polynomial-size decision trees. We present a novel characterization of rank, grounded in the well-known Transformer architecture. We show that the rank of a function f corresponds to the minimum number of Chain of Thought (CoT) steps required by a single-layer Transformer with hard attention to compute f. Based on this characterization we establish tight bounds on the number of CoT steps required for specific problems, showing that (ℓ)-fold function composition necessitates exactly (ℓ) CoT steps. Furthermore, we analyze the problem of identifying the position of the (k)-th occurrence of 1 in a Boolean sequence, proving that it requires (k) CoT steps. Finally, we introduce the notion of the multi-head rank that captures multi-head single-layer transformers, and perform the analysis of PAC-learnability of the classes of functions with bounded multi-head rank.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Placed in Prompting and chain-of-thought reasoning, one of 17 directions in LLM reasoning. Builds on 14 of its 27 references that are in the map. First posted on arXiv 22 Jan 2025.

Builds on

14 of 27 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problems20 Feb

Other references · 13

  1. 2017Attention Is All You Needcited by 60,361
  2. 2019What Does BERT Look At? An Analysis of BERT's Attentioncited by 1,003
  3. 2019Analyzing Multi-Head Self-Attention: Specialized Heads Do the Heavy Lifting, the Rest Can Be Prunedcited by 856
  4. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 288
  5. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  6. 2022Formal Language Recognition by Hard Attention Transformers: Perspectives from Circuit Complexitycited by 93
  7. 2023Mitigating Large Language Model Hallucinations via Autonomous Knowledge Graph-based Retrofittingcited by 70
  8. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 66
  9. 2024On Limitations of the Transformer Architecturecited by 63
  10. 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 49
  11. 2024Theoretical limitations of multi-layer Transformercited by 45
  12. 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
1 more
  1. 2023Logical Languages Accepted by Transformer Encoders with Hard Attentioncited by 38

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 4.

6 papers.

  1. 2025Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformerscited by 28
  2. 2026Parity, Sensitivity, and Transformerscited by 5
  3. 2025Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Trainingcited by 4
  4. 2026When does Chain-of-Thought Help: A Markovian Perspectivecited by 2
  5. 2026Indexing: the Beginning and the Endcited by 2
  6. 2026A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attentioncited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2026A Sharper Picture of Generalization in Transformers
  2. 2025Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently
  3. 2025Discovering Hidden Algebraic Structures via Transformers with Rank-Aware Beam GRPO
  4. 2026Tight Sample Complexity of Transformers
  5. 2025Softmax Transformers are Turing-Complete
  6. 2025Minimalist Softmax Attention Provably Learns Constrained Boolean Functions
  7. 2026Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity
  8. 2024Transformers Provably Solve Parity Efficiently with Chain of Thought