Transformers Provably Learn Sparse XOR with Polylogarithmic Parameters

\name Yaomengxi Han \email [email protected] \addr School of Computation, Information and Technology Technical University of Munich Boltzmannstrasse 3, 85748, Munich, Germany, \name Debarghya Ghoshdastidar \email [email protected] \addr School of Computation, Information and Technology Technical · 2025

Read Transformers Provably Learn Sparse XOR with Polylogarithmic Parameters by \name Yaomengxi Han \email [email protected] \addr School of Computation, Information and Technology Technical University of Munich Boltzmannstrasse 3, 85748, Munich, Germany, \name Debarghya Ghoshdastidar \email [email protected] \addr School of Computation, Information and Technology Technical (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-2502-07553.txt.

Description

Yaomengxi Han and Debarghya Ghoshdastidar ask, in a 2025 theory paper, how lean a Transformer can be and still learn a sparse parity rule. Such rules are a testbed for how nets find the few inputs that count. In the XOR task, the label is the product of two hidden bits in a long string. Past proofs leaned on plain feed-forward nets, which need a count of parts that grows with the string length. The pair proves that one layer with two heads breaks that bar. Its part count grows just with the log of the length.

With one gradient step, the net finds the two key bits and drives the loss near zero for all inputs. They also show, in tests, that true softmax attention drives that fast find, past linear and part-wise forms. A sample count bound adds a grasp claim.

Catalog record

CREATOR\name Yaomengxi Han \email [email protected] \addr School of Computation, Information and Technology Technical University of Munich Boltzmannstrasse 3, 85748, Munich, Germany, \name Debarghya Ghoshdastidar \email [email protected] \addr School of Computation, Information and Technology Technical
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-07553

Browse the full library · About the Tower of Babel