2025/01/22 by Pablo Barceló, Alexander Kozachinskiy, Barceló, Pablo +3 · 2 voices · 1 citation
Arts and Humanities · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Philosophy, Science, and History
paper · pdf · doi:10.48550/arxiv.2501.12997
openalex publication_date 2025/01/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.