Pith. sign in

REVIEW 3 major objections 6 minor 1 cited by

Ehrenfeucht-Haussler Rank and Chain of Thought

T0 review · 3 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The Ehrenfeucht–Haussler rank of a function equals the minimum number of chain-of-thought iterations a single-layer hard-attention decoder needs to compute it.

desk verdict Genuinely new and mostly solid equivalence between rank and CoT depth; the NP-hardness proof has a real gap in Lemma 6 that needs fixing. read the letter →

arxiv 2501.12997 v2 pith:GX7OFEAG submitted 2025-01-22 cs.LG cs.AI

Pablo Barceló , Alexander Kozachinskiy , Tomasz Steifer This is my paper · ORCID
classification cs.LGcs.AI
keywords Ehrenfeucht-HausslerrankchainofthoughttransformerhardattentiondecisiontreesPAClearningiteratedcompositioncommunicationcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes an exact equivalence between a classical measure from learning theory and the number of chain-of-thought steps in a simple transformer model. Specifically, for any function $f$ over finite alphabets, the Ehrenfeucht–Haussler rank $rk(f)$ equals the minimum number $dd^{(1)}(f)$ of iterations of a single-layer hard-attention decoder with one head that computes $f$; the equality extends to $H$ heads by defining an $H$-head rank $rk^{(H)}$ and showing $rk^{(H)}(f) = dd^{(H)}(f)$. This characterization yields tight bounds on two concrete problems: the $t$-fold iterated composition function requires exactly $t$ steps and the function returning the position of the $k$-th one in a binary string requires exactly $k$ steps, in both cases for all sufficiently large inputs and regardless of the number of attention heads. The paper also shows that classes of functions of bounded $1$-head rank are properly PAC-learnable in polynomial time over any finite alphabet, and that bounded multi-head rank classes are improperly PAC-learnable, while the class of $2$-head rank-$1$ Boolean functions is not properly PAC-learnable unless $\mathrm{NP} \subseteq \mathrm{BPP}$.

What carries the argument

The load-bearing object is the assignment query (a-query), which returns the first assignment $(i,\sigma)$ in a fixed total order of all possible assignments that is consistent with the input word. Decision trees over such queries have depth equal to the function's rank. The decoder simulation encodes every node of the tree as a coordinate of a real vector; the positional encoding of each assignment $a$ at a node $v$ has value $1/\tau_v^{-1}(a)$, where $\tau_v$ is the order of assignments at $v$, so the attention score of a candidate assignment is inversely proportional to its position in that order. A unique hard-attention head therefore picks exactly the assignment the tree would ask next, and a feed-forward block rewrites the one-hot node encoding to the next node. For $H$ heads, the construction runs the same mechanism on $H$ orders in parallel, making an $H$-degree a-query precisely the information one chain-of-thought step with $H$ heads can resolve. The tree-to-decoder direction embeds the whole a-query tree into a high-dimensional real vector space, so the embedding dimension can grow exponentially in the tree size.

What would settle it

For a small concrete instance where the paper predicts a specific rank, solve the decoder-synthesis problem over the reals: for example, take $2$-thOne on binary strings of length $n=6$, where the paper predicts $rk = 2$. Use quantifier elimination to determine whether there exists any dimension $d$, real matrices $K,Q,W_1,W_2,W_O$, positional embeddings, and output map $\alpha$ such that a one-head single-layer decoder computes the function in one iteration. The paper's Theorem 1 and Corollary 2 predict no such decoder exists; exhibiting one would falsify the characterization. Alternatively, a brute-force comparison of a-query tree depth with decoder-depth lower bounds for all functions on a small finite domain (e.g., $4$-bit inputs) would settle the identity on those instances.

Watch

Extended reading notes

Core claim

The central discovery is that a function's minimal decision-tree depth over assignment queries—the rank introduced by Ehrenfeucht and Haussler for Boolean functions and extended here to arbitrary finite alphabets—is exactly the minimum number of chain-of-thought iterations of a single-layer hard-attention decoder required to compute the function. The proof is two-sided: any $r$-step decoder is simulated by an $r$-depth assignment-query tree, since each attention step can be reproduced by one assignment query; conversely, any $r$-depth assignment-query tree is compiled into an $r$-step decoder whose unique attention head, at each iteration, selects exactly the assignment the current tree node would ask about, and the decoder then updates a one-hot encoding of the current node in the tree. The same construction works with $H$ independent heads, yielding $rk^{(H)}(f) = dd^{(H)}(f)$ for $H$-degree assignment-query trees. These identities convert classical rank lower bounds into chain-of-thought lower bounds, giving exact linear bounds for iterated composition and for the $k$-th-one function, and they transfer PAC-learnability results from rank-bounded classes to decoder-bounded classes.

Load-bearing premise

The equality $rk(f) = dd^{(1)}(f)$ relies on the decoder having access to unbounded-dimensional real-valued embeddings, arbitrary real weight matrices, and an unconstrained output map; the construction from decision trees to decoders places information in positional coordinates whose values can require exponentially many bits, so the exact equality may break under finite precision or bounded dimension.

Editorial extensions

If this is right

  • For every function $f$, the minimum number of chain-of-thought iterations of a single-layer hard-attention decoder is an intrinsic combinatorial parameter of $f$, independent of the encoder weights: it is exactly the depth of the best decision tree over assignment queries.
  • The $t$-fold iterated composition function $t\text{-Comp}_n$ has $dd^{(H)}(t\text{-Comp}_n) = t$ for all sufficiently large $n$ and every fixed $H$, so no number of parallel attention heads can shortcut the sequential dependency of composition.
  • The $k$-th-one function has $dd^{(H)}(k\text{-thOne}_n) = k$ for all sufficiently large $n$ and every fixed $H$, so the obvious iterative algorithm that tracks one occurrence at a time is exactly optimal.
  • For any fixed $k$ and finite alphabet, functions of $1$-head rank at most $k$ are properly PAC-learnable in polynomial time, and functions of $H$-head rank at most $k$ are improperly PAC-learnable in polynomial time.
  • The class of Boolean functions of $2$-head rank at most $1$ is not properly PAC-learnable in polynomial time unless $\mathrm{NP} \subseteq \mathrm{BPP}$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The identity suggests that a-query depth is the 'serial time' of hard-attention reasoning; analogous rank-style parameters might characterize chain-of-thought depth for other attention variants, such as masked or causal decoders, where the available queries change at each step.
  • Because the decoder-to-tree direction is constructive, any lower-bound technique for a-query tree depth—from adversary arguments or communication complexity—automatically becomes a chain-of-thought lower bound, providing a transfer principle that could yield new bounds for other sequential functions.
  • The unbounded-precision model is an idealization; a finite-precision version of rank would be needed to translate the equality into practical transformer guarantees, and the paper's explicit openness on soft attention and multilayer decoders suggests the exact equality will need modification in those settings.
  • The PAC-learning boundary between one head (properly learnable) and two heads (NP-hard) for depth-$1$ functions indicates that the second head causes a genuine jump in representational power, possibly a general phenomenon for fixed-depth multi-head rank classes.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper establishes a bridge between the Ehrenfeucht-Haussler rank of a function and the number of chain-of-thought steps needed by a single-layer hard-attention decoder. It proves rk(f) = dd^(1)(f) for arbitrary finite-alphabet functions (Theorem 1), extends this to H attention heads via an H-head rank (Theorem 2), and derives exact lower bounds for iterated composition (Corollary 3) and for the k-th-one function (Theorem 3). It also proves that functions of bounded 1-head rank are properly PAC-learnable over arbitrary alphabets (Theorem 4) and claims that the consistency problem for 2-head rank-1 functions is NP-complete (Theorem 5), implying that this class is not properly PAC-learnable unless NP is contained in BPP.

Significance. If the proofs are correct, this is a valuable conceptual link between classical PAC-learning rank and Transformer expressivity. The characterization in Theorems 1 and 2 is explicit and checkable, the non-Boolean extension of rank is useful in its own right, and the communication-complexity lower bound for multi-head rank is a clean technique. The exact CoT bounds for t-Comp and k-thOne are genuinely tight results. The PAC-learning part is somewhat derivative of Ehrenfeucht-Haussler for the positive direction, but the NP-completeness result for 2-head rank-1 functions is a distinctive contribution. The main positive results do not rely on the contested Lemma 6; the NP-hardness and proper non-learnability claims do.

major comments (3)
  1. [Section 6.2, Lemma 6] The proof of Lemma 6 depends on a 'technical claim' that the only possible pairs of maximal elements are the four listed cases, but this claim is not actually proved. The text rules out non-u/v coordinates with an informal restriction argument, and the six 'bad pairs' are dismissed with 'One can check'. This claim is load-bearing: it is what forces all but one working 1-assignment to lie above all working 0-assignments in both orders, which is the step that converts a solution of the gadget instance back into a satisfying assignment for the original NAE-3-SAT instance. Without a complete case analysis, the converse direction of the reduction in Lemma 4 and hence Theorem 5's NP-completeness do not follow. Please provide a rigorous proof of the technical claim, including the interaction of both linear orders and the treatment of ties, or replace it with a different argument.
  2. [Section 5, proof of Theorem 2] The final step of the multi-head decoder construction is under-specified and appears arithmetically inconsistent as written. The proof states that W2 is the identity and that a conjunction of H+1 bits b0,...,bH can be written as ReLU(b0+...+bH−(H−1)). For all bits equal to 1, this expression evaluates to 2, not 1, so the claimed one-hot encoding of y_{t+1} is not produced by the stated matrices. The parenthetical remark that the special coordinate is used to express H−1 is not sufficient, because under the described WO the special coordinate of multihead+yt is zero. Please give the explicit W1 and W2 (or correct the formula and the role of the special coordinate) and verify that the one-hot invariant is maintained for H > 1.
  3. [Definition 2 and Theorem 1] The exact equality rk(f) = dd^(1)(f) is proved in a model with unbounded real-valued coordinates, arbitrary positional encodings, arbitrary output maps, and no precision or dimension bounds. The rank-to-decoder construction in Theorem 1 uses an embedding dimension exponential in the rank and coordinate values of the form 1/τ^{-1}(a), so it depends critically on exact real arithmetic and non-uniform per-length parameter choice. This is a substantive scoping restriction of the characterization. The related-work paragraph presents the absence of dimension and precision assumptions as a strength; the paper should state explicitly, in the introduction or in Section 7, that the equivalence holds in this idealized model and does not transfer to fixed precision, bounded dimension, soft attention, or multilayer decoders. The positive results remain correct within the stated model, but the framing should not overstate their reach.
minor comments (6)
  1. [Section 6.1] There is a typo in 'rank-k consisent' in the first paragraph of the proof; it should read 'rank-k consistent'.
  2. [Section 6.2, Lemma 4] The proof cites 'Schaefer' without a formal citation; the reference list entry for Thomas J. Schaefer should be cited explicitly.
  3. [Section 5, proof of Theorem 2] Near the end of the proof, 'the (a1,...,at)-labeled edge' should be 'the (a1,...,aH)-labeled edge'; the variables a1,...,aH are the H query answers, not a1,...,at.
  4. [Section 5.2, Lemma 2] The proof of Lemma 2 uses m/2 and sqrt(m) as if m were even and a perfect square; please state the necessary rounding conventions or handle non-integer quantities explicitly.
  5. [Section 5.2] The notation 'n2^{-ℓ}' in the proof of Theorem 3 is ambiguous; it should presumably be n^{2^{-ℓ}}, and the superscript should be typeset clearly.
  6. [Section 3, Proposition 4] The construction using cos i and sin i assumes exact real arithmetic and distinct angles for tokens i = 1, ..., n; the proof should state that it operates over exact real numbers and that n can be arbitrarily large in this model.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: rank and decoder depth are defined independently and proved equivalent by explicit constructions.

full rationale

The paper's central result, Theorems 1 and 2, equates the Ehrenfeucht-Haussler-type rank with the minimum number of chain-of-thought steps for single-layer hard-attention decoders. These two notions are defined independently: rank is the minimal depth of a decision tree over assignment queries (Definition 1 and Definition 4), and decoder depth is the minimal number of iterations of a concrete attention-layer decoder (Definitions 2 and 3). Both directions of Theorem 1 are proved by explicit simulation: decoder-to-rank uses the decoder's attention scores and positional encodings to define an a-query that recovers the attended token, while rank-to-decoder embeds the tree's a-queries into positional coordinates and constructs the attention layer step by step. Theorem 2 extends the same construction to multiple heads. No fitted parameter is renamed as a prediction, and no load-bearing claim is imported from the authors' prior work; the self-citations in the related-work section provide background on hard-attention expressivity but do not supply the target equality. The lower bounds for iterated composition and k-th-one use independent combinatorial and communication-complexity arguments. The main caveat in the manuscript is not circularity but a proof gap: Lemma 6 relies on a 'technical claim' about the four possible maximal pairs and says 'One can check' for the bad cases, so the NP-hardness direction of Theorem 5 is not fully demonstrated. That is a correctness/completeness concern, not a circularity concern, because it does not reduce the theorem to its own assumptions. Overall the derivation chain is self-contained and non-circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No numeric parameters are fitted to data. The central equivalence is proven by explicit simulation in both directions. The only external inputs are standard results in communication complexity, NP-completeness, and PAC learning theory. The dominant domain assumption is the unbounded real-valued decoder model, which is stated but not discussed as a limitation in the main text.

assumptions (4)
  • standard math Proper polynomial-time PAC learnability is equivalent, under randomized polynomial-time reductions, to polynomial-time solvability of the consistency problem.
    Invoked in Section 6 to translate Theorems 4 and 5 into PAC learnability statements; cited as folklore from Kearns and Vazirani.
  • standard math The k-round Bob-first communication complexity of pointer chasing PC_m^k is Ω(m) for constant k.
    Used in Corollary 3 to lower-bound rk^(H)(t-Comp_n); cited to Duris et al. 1987, not proved in the paper.
  • standard math Monotone NAE-3-SAT is NP-complete.
    Used as the source problem in the NP-completeness reduction of Lemma 4; cited to Schaefer.
  • domain assumption The decoder model permits arbitrary real-valued positional encodings, arbitrary real weight matrices, and an arbitrary output function, with no precision or dimension bounds.
    Definition 2 and the proof of Theorem 1 rely on this unbounded real-valued model. This is the main abstraction separating the result from practical Transformers with finite precision and constrained readouts.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Ehrenfeucht-Haussler Rank and Chain of Thought." pith.science (2026). https://pith.science/paper/GX7OFEAG

@misc{pith2026250112997,
  author       = {Pith},
  title        = {Pith review of: Ehrenfeucht-Haussler Rank and Chain of Thought},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GX7OFEAG}},
  note         = {Machine review of arXiv:2501.12997}
}
abstract

The notion of \emph{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 \emph{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 \(\ell\)-fold function composition necessitates exactly \(\ell\) 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently

    cs.LG 2025-11 conditional novelty 6.0 of 10

    Under hand-designed masks and task-specific activations, RL fine-tuning learns a k-sparse Boolean reasoning chain in one gradient update while SFT learns it one CoT step per update.

Reference graph

Works this paper leans on

28 extracted references · 22 canonical work pages · cited by 1 Pith paper

  1. [1]

    Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages

    Dana Angluin, David Chiang, and Andy Yang. Masked hard-attention transformers and boolean RASP recognize exactly the star-free languages. CoRR, abs/2310.13897, 2023

    work page Pith review arXiv 2023

  2. [2]

    Podolskii

    Pablo Barcel \' o , Alexander Kozachinskiy, Anthony Widjaja Lin, and Vladimir V. Podolskii. Logical languages accepted by transformer encoders with hard attention. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024 . OpenReview.net, 2024. URL https://openreview.net/forum?id=gbrHZq07mq

    work page 2024

  3. [3]

    Theoretical limitations of multi-layer transformer

    Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer transformer. arXiv preprint arXiv:2412.02975, 2024

    arXiv 2024

  4. [4]

    Tighter bounds on the expressivity of transformer encoders

    David Chiang, Peter Cholak, and Anand Pillay. Tighter bounds on the expressivity of transformer encoders. In ICML, volume 202, pages 5544--5562, 2023

    work page 2023

  5. [5]

    Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D. Manning. What does BERT look at? an analysis of bert's attention. In Tal Linzen, Grzegorz Chrupala, Yonatan Belinkov, and Dieuwke Hupkes, editors, Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, BlackboxNLP@ACL 2019, Florence, Italy, August...

    doi:10.18653/v1/w19-4828 2019

  6. [6]

    Lower bounds on communication complexity

    Pavol Duris, Zvi Galil, and Georg Schnitger. Lower bounds on communication complexity. Information and Computation, 73 0 (1): 0 1--22, 1987

    work page 1987

  7. [7]

    Learning decision trees from random examples

    Andrzej Ehrenfeucht and David Haussler. Learning decision trees from random examples. Information and Computation, 82 0 (3): 0 231--246, 1989

    work page 1989

  8. [8]

    A combinatorial characterization of treelike resolution space

    Juan Luis Esteban and Jacobo Tor \'a n. A combinatorial characterization of treelike resolution space. Information Processing Letters, 87 0 (6): 0 295--300, 2003

    work page 2003

Show all 28 references
  1. [9]

    Theoretical limitations of self-attention in neural sequence models

    Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Trans. Assoc. Comput. Linguistics, 8: 0 156--171, 2020 a

    2020

  2. [10]

    Theoretical limitations of self-attention in neural sequence models

    Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 0 156--171, 2020 b

    2020

  3. [11]

    Formal language recognition by hard attention transformers: Perspectives from circuit complexity

    Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Trans. Assoc. Comput. Linguistics, 10: 0 800--810, 2022 a

    2022

  4. [12]

    Formal language recognition by hard attention transformers: Perspectives from circuit complexity

    Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Transactions of the Association for Computational Linguistics, 10: 0 800--810, 2022 b

    2022

  5. [13]

    An introduction to computational learning theory

    Michael J Kearns and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994

    1994

  6. [14]

    Investigating a general hierarchy of polynomially decidable classes of cnf’s based on short tree-like resolution proofs

    Oliver Kullmann. Investigating a general hierarchy of polynomially decidable classes of cnf’s based on short tree-like resolution proofs. Citeseer, 1999

    1999

  7. [15]

    Communication Complexity

    Eyal Kushilevitz and Noam Nisan. Communication Complexity. Cambridge University Press, 1996

    1996

  8. [16]

    Chain of thought empowers transformers to solve inherently serial problems

    Zhiyuan Liu, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. In ICLR, 2024

    2024

  9. [17]

    The parallelism tradeoff: Limitations of log-precision transformers

    William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Trans. Assoc. Comput. Linguistics, 11: 0 531--545, 2023

    2023

  10. [18]

    The expressive power of transformers with chain of thought

    William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. In ICLR, 2024

    2024

  11. [19]

    Papadimitriou

    Binghui Peng, Srini Narayanan, and Christos H. Papadimitriou. On limitations of the transformer architecture. CoRR, abs/2402.08164, 2024

    2024 arXiv

  12. [20]

    Attention is turing-complete

    Jorge P \' e rez, Pablo Barcel \' o , and Javier Marinkovic. Attention is turing-complete. J. Mach. Learn. Res., 22: 0 75:1--75:35, 2021

    2021

  13. [21]

    Computational limitations on learning from examples

    Leonard Pitt and Leslie G Valiant. Computational limitations on learning from examples. Journal of the ACM (JACM), 35 0 (4): 0 965--984, 1988

    1988

  14. [22]

    A lower bound for dll algorithms for k-sat (preliminary version)

    Pavel Pudl \'a k and Russell Impagliazzo. A lower bound for dll algorithms for k-sat (preliminary version). In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pages 128--136, 2000

    2000

  15. [23]

    The complexity of satisfiability problems

    Thomas J Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 216--226, 1978

    1978

  16. [24]

    A theory of the learnable

    Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27 0 (11): 0 1134--1142, 1984

    1984

  17. [25]

    Gomez, Lukasz Kaiser, and Illia Polosukhin

    Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurIPS, pages 5998--6008, 2017

    2017

  18. [26]

    Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned

    Elena Voita, David Talbot, Fedor Moiseev, Rico Sennrich, and Ivan Titov. Analyzing multi-head self-attention: Specialized heads do the heavy lifting, the rest can be pruned. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. Association...

    2019

  19. [27]

    Counting like transformers: Compiling temporal counting logic into softmax transformers

    Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. CoRR, abs/2404.04393, 2024

    2024 arXiv

  20. [28]

    Masked hard-attention transformers recognize exactly the star-free languages

    Andy Yang, David Chiang, and Dana Angluin. Masked hard-attention transformers recognize exactly the star-free languages. In NeurIPS, 2024

    2024

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.