Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent

Bo Chen, Zhenmei Shi, Zhao Song, Jiahao Zhang · 2025

Read Provable Failure of Language Models in Learning Majority Boolean Logic via Gradient Descent by Bo Chen, Zhenmei Shi, Zhao Song, Jiahao Zhang (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-2504-04702.txt.

Description

Bo Chen and three co-authors prove a hard limit on how language models learn a basic logic rule. The rule is majority vote: given a string of bits, say which value fills more than half the slots. Models can in form state this rule, since their class can hold such gates. The open point is whether training by gradient steps, the standard method, can teach it from samples.

Tests used a lean form of the transformer model, the base design of most language tools. Sample counts ranged from modest to vast in the input size. Even after a vast count of gradient steps, the error on fresh inputs stayed large and grew fast with input size. The proof pins the flaw on the training path, not the model shape. It warns that fluent speech can hide weak logic skill.

Catalog record

CREATORBo Chen, Zhenmei Shi, Zhao Song, Jiahao Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE77 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-04702

Browse the full library · About the Tower of Babel