Ehrenfeucht-Haussler Rank and Chain of Thought

Pablo Barceló, Alexander Kozachinskiy, Tomasz Steifer · 2025

Read Ehrenfeucht-Haussler Rank and Chain of Thought by Pablo Barceló, Alexander Kozachinskiy, Tomasz Steifer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-12997.txt.

Description

Pablo Barceló, Alexander Kozachinskiy, and Tomasz Steifer tie a classic learning rank to transformer reasoning in a 2025 paper. The rank of a Boolean function anchors PAC learning theory. It yields fast learning for small decision trees. The team reframe rank through the Transformer architecture.

Rank equals the fewest chain-of-thought steps a one-layer Transformer needs. That count applies to a single-layer net with hard attention. Composing a function with itself sets an exact step price. Hunting the k-th one in a bit string also costs k steps. A multi-head rank extends the idea to richer models. Bounded rank classes get fresh learnability results.

Catalog record

CREATORPablo Barceló, Alexander Kozachinskiy, Tomasz Steifer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE101 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-12997

Browse the full library · About the Tower of Babel