Ehrenfeucht-Haussler Rank and Chain of Thought
Pablo Barcelo, Alexander Kozachinskiy, Tomasz Steifer
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.
BibTeX
@inproceedings{
barcelo2025ehrenfeuchthaussler,
title={Ehrenfeucht-Haussler Rank and Chain of Thought},
author={Pablo Barcelo and Alexander Kozachinskiy and Tomasz Steifer},
booktitle={Forty-second International Conference on Machine Learning},
year={2025},
url={https://openreview.net/forum?id=94ZmvjqMWu}
}