Research map / Learning theory and algorithms / Sample complexity
Ehrenfeucht-Haussler Rank and Chain of Thought
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes the Ehrenfeucht-Haussler rank of a function as the number of chain-of-thought decoder iterations needed by a single-layer hard-attention transformer, extends this to H-head rank with communication-complexity and combinatorial lower bounds, and derives PAC-learnability results.
Problem
Understanding how many chain-of-thought steps a single-layer transformer needs to compute a Boolean or finite-alphabet function, and how this relates to decision-tree rank and PAC learnability.
Approach
Shows that rank of a function (generalized to non-Boolean alphabets via assignment queries) exactly equals the decoder depth (CoT iterations) of a single-layer unique hard-attention transformer, and extends this to H-head rank with matching communication-complexity lower bounds.
Key results
- Theorem: for any function f, rk(f) equals dd^(1)(f), the one-head decoder depth (CoT steps) of a single-layer hard-attention decoder.
- t-fold iterated composition has H-head rank exactly t for all but finitely many n, for every fixed H.
- The k-th one function has H-head rank k for all but finitely many n, proven by a combinatorial argument; the class of 2-head rank at most 1 functions is not properly PAC-learnable unless NP is contained in BPP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Allow H hard-attention heads instead of one head | t-fold iterated composition · t-fold iterated composition, all but finitely many n | required rank: \mathsf{rk}^{(H)}(\text{$t$-}\mathsf{Comp}_n) = t | No clear effect |
| Allow H hard-attention heads instead of one head | k-th one position · k-th one position, all but finitely many n | required rank: \mathsf{rk}^{(H)}(\one{k}_n) = k | No clear effect |
Surprising findings
- The communication-complexity technique that works for iterated composition cannot give the tight bound for the k-th one function, since a 2-round protocol with logarithmic communication exists for every partition.
Limitations
- Results apply to single-layer unique hard-attention decoders, not soft attention used in practice.
- Tight H-head bounds hold only for sufficiently large input length n (all but finitely many n).
- Properly PAC-learning hardness is shown only for 2-head rank at most 1 under NP not in BPP.
Experimental setup
Builds on: Ehrenfeucht-Haussler rank Transformer chain-of-thought pointer chasing
Closest papers by meaning
- Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (ICLR 2024 · similarity 0.85)
- Learning Linear Attention in Polynomial Time (NeurIPS 2025 · similarity 0.84)
- Transformers Provably Solve Parity Efficiently with Chain of Thought (ICLR 2025 · similarity 0.83)
- The Expressive Power of Transformers with Chain of Thought (ICLR 2024 · similarity 0.83)
- Analyzing the Power of Chain of Thought through Memorization Capabilities (NeurIPS 2025 · similarity 0.83)
- Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.