Ehrenfeucht-Haussler Rank and Chain of Thought

Pablo Barcelo, Alexander Kozachinskiy, Tomasz Steifer
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:2968-2977, 2025.

Abstract

The notion of rank of a Boolean function has been a cornerstone in PAC learning, 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 $\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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-barcelo25a, title = {Ehrenfeucht-Haussler Rank and Chain of Thought}, author = {Barcelo, Pablo and Kozachinskiy, Alexander and Steifer, Tomasz}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {2968--2977}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/barcelo25a/barcelo25a.pdf}, url = {https://proceedings.mlr.press/v267/barcelo25a.html}, abstract = {The notion of rank of a Boolean function has been a cornerstone in PAC learning, 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 $\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.} }
Endnote
%0 Conference Paper %T Ehrenfeucht-Haussler Rank and Chain of Thought %A Pablo Barcelo %A Alexander Kozachinskiy %A Tomasz Steifer %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-barcelo25a %I PMLR %P 2968--2977 %U https://proceedings.mlr.press/v267/barcelo25a.html %V 267 %X The notion of rank of a Boolean function has been a cornerstone in PAC learning, 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 $\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.
APA
Barcelo, P., Kozachinskiy, A. & Steifer, T.. (2025). Ehrenfeucht-Haussler Rank and Chain of Thought. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:2968-2977 Available from https://proceedings.mlr.press/v267/barcelo25a.html.

Related Material