Lost in Transmission: When and Why LLMs Fail to Reason Globally

Understand

Despite their many successes, transformer-based large language models (LLMs) continue to struggle with tasks that require complex reasoning over large parts of their input.

• We argue that these failures arise due to capacity limits on the accurate flow of information within LLMs.
• To formalize this issue, we introduce the bounded attention prefix oracle (BAPO) model, a new computational framework that models bandwidth constraints on attention heads, the mechanism for internal communication in LLMs.
• We show that several important reasoning problems like graph reachability require high communication bandwidth for BAPOs to solve; we call these problems BAPO-hard.