Lost in Transmission: When and Why LLMs Fail to Reason Globally
Authors: Tobias Schnabel
Kiran Tomlinson
Adith Swaminathan
Jennifer Neville
Venue: NeurIPS 2025 spotlight ()
Keywords: LLM limitations
chain of thought
reasoning
communication complexity
Primary area: deep_learning
TL;DR: We develop a theoretical model of information flow constraints in LLMs that predicts LLM failures on global reasoning tasks.

Abstract: 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. Our experiments corroborate our theoretical predictions: GPT-4o, Claude, and Gemini succeed on BAPO-easy tasks and fail even on relatively small BAPO-hard tasks. BAPOs also reveal another benefit of chain of thought (CoT): we prove that breaking down a task using CoT can turn any BAPO-hard problem into a BAPO-easy one. Our results offer principled explanations for key LLM failures and suggest directions for architectures and inference methods that mitigate bandwidth limits.

Lost in Transmission:
When and Why LLMs Fail to Reason Globally
Tobias Schnabel' Microsoft Research
Kiran Tomlinson" Microsoft Research
Adith Swaminathan Netflix
Jennifer Neville Microsoft Research
Abstract
Despite their many successes, transformer-bus 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 accu- rate 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 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. Our experiments corroborate our theoretical pre- dictions: GPT-4o, Claude, and Gemini succeed on BAPO-easy tasks and fail even on relatively small BAPO-hard tasks. BAPOs also reveal another benefit of chain thought (CoT): we prove that breaking down a task using CoT can turn any BAPO-hard problem into a BAPO-easy one. Our results offer principled explana- tions for key LLM failures and suggest directions for architectures and inference methods that mitigate bandwidth limits.
Introduction
Despite the empirical successes of transformer-based large language models (LLMs), they exhibit persistent failures global problems that require integrating information across the entire input, such as chaining syllogisms [1] function composition [10), and formal language recognition [5]. Our core hypothesis is that these failures arise due to an inability of LLMs to accurately commu- nicate information across residual streams [13), the sequences of transformer blocks correspond- ing to each input token. For an LLM to solve problem, information about early tokens must be transmitted through attention into the last token's 's residual stream. While some problems, such as needle-in-a- -nall--ii--h tasks, do not require much information to cross residual streams, we show that global problems with complex inter-token dependencies require substantial communication. We conjecture that L.LMs fail on such problems due to a limit on the amount of information they can accurately transmit between residual streams, which we refer to as their effective bandwidth. This supported by prior work on capacity bounds on attention Causal attention exacerbates communication issues by forcing pre-processing in early streams to be independent later tokens, increasing the representation size of problems. Figure illustrates the issue of information flow and previews empirical results.
and sparse attention ( 4
33 41
To formally analyze these issues, we propose the bounded attention prefix oracle (BAPO) model new computational model designed to capture the communication constraints and causal attention of transformer- based LLMs. BAPOs capture how much information must be communicated between residual streams to solve problem, abstracting away other details of the transformer architecture. When producing an output, there are two ways in which transformers can integrate information about the last token with information from earlier tokens (i.e., from a prefix of the input): they can attend to
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

INDEX
REACHARILITY
Iow bundwill
casy
LLMs
bundwiah land LLMs
E20044 Conern 1. 60.90 5)
OPT40
Oasini 15
24
25
Sonset
(c.)) (c.d)
0h d (d.0)
(d.g)
Clask:35
Serncc
150 320
50
100
150
200
Figure 1: We conjecture that LLMs have a limit on their effective bandwidth, which we illustrate above by constrained information flow across one particular prefix-suflix split of the input. The BAPO model quantifies the communication bandwidth needed for transformers with causal attention to solve problem. INDEX requires low communication bandwidth and LLMs solve it without issue; REACHABILITY requires high bandwidth and LLMs struggle with it.
precomputed values from higher layers of prefix streams, they can attend the raw prefix token values (or both; see Figure 2a). The BAPO model captures these two types of information flow and quantifies limits on the amount of information transmitted. In contrast with existing theoretical work on the expressivity of the transformer model class [40] 23 15
37 34 []. we seek to characterize
the (in)ability of LLMs to solve global reasoning problems in practice. Strikingly, our experiments suggest that the effective bandwidth of modern LLMSs is small constant, so we call problems BAPO-hard they cannot solved by a constant-bandwidth BAPO and BAPO-easy if they can.
Theoretical contributions. We begin by highlighting the power of attention, which makes several hard communication problems (EQUALITY, DISJOINTNESS, and INDEX) BAPO-easy. In contrast, we show that a variety of important global problems are BAPO-hare thus posing challenge to LLMs with imprecise internal communication. In particular, we prove BAPO-hardness for REACH- ABILITY, MAJORITY, MATCH3, (34), UNIQUE, and SETDIFF, with lower bounds on the commu- nication bandwidth required for each problem. On the positive side, we show that chain of thought (CoT) allows us to break down any BAPO-hard problem into a sequence of BAPO-easy steps, sug- gesting one mechanism for the success of CoT (24 1S 30. Specifically, we show that CoT renders constant-bandwide BAPOs complee. This enables them to solve any decidable problem given a enough output tokens (although this number might be impractically large).
Empirical contributions. Our experimental results confirm the predictive power of the BAPO model: GPT-4o, Claude, and Gemini systematically fail solve even relatively small instances of BAPO-hard problems, while performing well on BAPO-easy tasks across instance size (as pre- viewed in Figure I We also demonstrate how real-world LLM tasks such as aggregating reviews and variable- trackingg in code contain BAPO- hard components, namely MAJORITY and REACHA- BILITY, and thus present challenge for LLMs. This illustrates the significance of our theoretical work in practice. Supporting our CoT result, the reasoning models o3 and Gemini 2.5 Flash perform very well even on BAPO-hard problems, albeit with a very large number of reasoning tokens. Our code is available at httttttt::///h thub. com/ mi microooft/bbapp
Implications. Identifying BAPO-hard and BAPO-easy sub-tasks enables practitioners to antic- ipate LLM limitations and proactively employ mitigation techniques like inference-time scaling, hybrid architectures, or tool-calling. key feature of the BAPO model is that it abstracts away the low-level details of transformers and instead focuses how much information must flow solve a problem, yielding a characterization that can be applied more broadly and intuitively. Our work also shows how chain-of-thought reasoning can alleviate the communication needs of problems by breaking a problem down into steps requiring only a small amount of information flow, suggesting low bandwidth requirement as an additional objective in learning from reasoning chains. Ultimately, BAPOs offer an explanatory foundation for observed LLM failures on global reasoning problems and can unlock principled innovations overcome these limitations.
2 A communication model of LLMs
The goal of our model is to represent the information processing flow within transformers while abstracting away lower level details. At high level, recall that a transformer with causal attention

---

S
suffix oracle
S/22
bandbwidthh
haadwith
821
prefix oracle s
attention
22
.33
1k++1
333
1k++1
(a) A three-layer transformer with input tokens 21..... In- Node sy is the transformer block at position and layer j. Information from the prefix needed for the solution output at Sus is gathered by attending to either (i) past tokens (here, 23 and z²x) or (ii) intermediate outputs (here, $21 and Suz). The at- tention to prefix tokens is captured by the attention g of a BAPO, while the prefix oracle f a BAPO mad- els all other transmitted information from the prefix.
(b) An (a, b)-BAPO computes its result from the out- put of the prefix oracle f (limited to a bits), atten- tion function g (limited to b tokens), and suffix to- kens ls + 1,..., n. The attention function can choose which tokens attend but the decision to attend to each prefix token is inde- pendent from other prefix tokens. An arbitrary subset G of size b is received by h if g attends to more than b tokens. Every component has access to token indices.
function of the suffix,
Figure 2: A simplified view of transformer and our bounded attention prefix oracle (BAPO) model.
makes next-token predictions at every token position in parallel. Additionally, no residual stream knows how far from the end of the input it is what tokens come later in the input, due to causal attention. As such, if a transformer needs to solve a problem and we split its input into a prefix and suffix, any pre-processing done in the prefix streams should be useful no matter the suffix tokens. Moreover, information about the prefix must be communicated to the suffix streams, as they need to make next-token predictions that may depend prefix tokens. This communication must occur across every possible prefix-suffis split, but for simplicity, we will model and analyze an arbitrary (usually worst case) split.
To make this more concrete, Figure 2a visualizes the computation of the next token Fn+1 inside a transformer, with nodes contributing to the prediction of In+1 highlighted (other attention weights are 0). A particular prefix-sufiix split is shown with a dashed gray line, dividing the input tokens and their residual streams (i.e., the columns above each token). The output stream in the suffix must have all relevant information about the prefix tokens to solve a problem that depends on the whole input. That is, all needed information about the prefix tokens must cross the dashed gray line. This information can either come from (i) attending to input tokens directly (arrows crossing the split into s.1) (ii) attending intermediate outputs from the prefix streams (arrows crossing the split into 8n2 and 8n3). As we have emphasized, any intermediate outputs from prefix layers must be usable for all possible suffixes, since prefix streams cannot depend on future tokens due causal attention.
Our central hypothesis is that LLMs have a limited ability to exactly communicate a large number of tokens or a large intermediate result across residual streams, thus causing failures problems that require high information flow. We call this the effective bandwidth of an LLM. This hypothesis is informed by prior work that has derived capacity limits attention heads [12]. shown that problems requiring reasoning over many tokens pose a challenge I1, and proved that individual token impacts on attention tend to zero as the input length grows (18).
Our model isolates the issue of limited effective bandwidth as it plays a role in LLMs with causal attention. For simplicity, we consider problems with single-toker token solutions, which includes all decision problems. More formally, we consider tasks where an LLM is prompted with fixed problem description P E Σ* concatenated with an input I 2.. E Σ*, where is the token vocabulary. The goal is to produce a solution E Σ, which we represent with the function p Σ Σ with
BAPOs.
= y. We begin with an intuitive overview of the model.
Informal Definition 1. A bounded attention prefix oracle (BAPO; see Figure 2b must solve a problem given an input split arbitrarily into a prefix and suffix. A BAPO computes the solution given the suffix, a bits output by a prefix oracle f that accesses only the prefix, and b prefix tokens selected individually by binary attention function g. with full positional information. The prefix
3

---

oracle f models the intermediate processing in prefix residual streams, which has no access to the suffix due to causal attention. The limits on the output size of f and on the number of tokens g may attend to are the key bandwidth constraints of the model, capturing limited attention head capacity.
Given this intuition, we provide the formal definition of BAPOs (using N- = ->o), which makes explicit how BAPOs account for positional encodings and what happens if g tries attend to too many tokens (intuitively, the BAPO must work given any set of tokens to which g attends).
Definition 1. An (a, b)-BAPO (bounded attention prefix oracle) is defined by a prefix oracle f E + {0, 1]", an attention finctiin g "²* X N x D x N - {0, 1}. and suffix oracle h : xN + E. An (a, -BAPO solves computational problem E* + E
10.13a x0.1)xX (==o(xN (((((z) TR); Gb In, k) = p(æ) ... In) for all < n and all G S C [(x,, 1) S
i S K g( ... In, k, F2 4) = 1 with G| min |G }.
We call a the prefix bandwidth (measured in bits) and the attention bandwidth (measured in tokens) of the BAPO. We call problem BAPO-easy if it can be solved by BAPO with constant bandwidths (w.r.. n) and BA BAPO-hard otherwise. If a problem requires bandwidths that scale with |=| we say is BAPO-E-hard. Note that any problem with n-token inputs can be solved by a (n [log2 [>]]] 0)- BAPO or by (0, -BAP as the prefix oracle can forward the entire prefix or the attention function can attend to the entire prefix; we call this the trivial upper bound on BAPO complexity. Lastly, given a language L C "", we say that a BAPO recognizes L if it solves p(r) 1/x E LJ.
Assumptions. We briefly discuss some trade-offs in the underlying assumptions for BAPOs. On the generous side, assume that the prefix streams and suffix streams have unbounded computa- tional power However, this fact is tempered by the fact that a BAPO must work for all possible prefix-suflix splits. Regarding the attention function, our model is pairwise in the sense that g can only look at a single prefix token 2; at a time, as in real transformers. BAPOs differ though in that g base its attention decisions the entire suffix. However, transformers can compensate for this by communicating information between the suffix streams across multiple layers. Our model also assumes perfect positional encoding, whereas this is a point of failure in real transformers (II]. Finally, the attention g can only operate on the token layer, whereas in transformers, attention can also aftend outputs of subsequent layers. However, this is offset by the ability of the suffix oracle in our model to perform arbitrary computation on the attended tokens. Appendix [explores some variations of the modeling assumptions and how they affect the expressive power of the model.
3 BAPO theory
We prove that a variety of important global reasoning problems like graph reachability are BAPO- hard and therefore pose a challenge for LLMs under our effective bandwidth hypothesis. Table I summarizes our hardness and tractability results. Strikingly, we also prove that chain of thought en- ables constant- constant-bandwidtt BAPOs to solve all decidable problems, suggesting reduction in required bandwidth as another mechanism for the empirical success of chain of thought.
3.1 BAPO-easy problems
Before turning to problems that BAPOs fail to solve, we first show the kinds of problems that are BAPO-easy. requiring only constant bandwidth. As we will see, these all share the key property that they can be computed from small summary local portion of the input.
One attention token is all you need to solve hard communication problems. Our first BAPO- easy problems establish a separation from the standard one-way communication model [3] upon which BAPOs are based. BAPOs are at least as powerful: any problem solvable with a(n) bits of one-way communication on n-bit inputs also solvable by a (a(n), (...0-BBBOOO by having the prefix oracle implement the communication protocol. However, adding even just little attention makes BAPOs strictly more powerful than pure one-way communication. Strikingly, even (1, 1)APPOs can solve DISJOINTNESS, EQUALITY, and INDEX, which are maximally hard problems for one-way communication requiring n bits of communication (T] (see Appendix
[A] for full definitions).
RRequiingg f. 9. and i to be computable rather than arbitrary has effect on our results.

---

Table 1: Overview of our BAPO upper and lower bounds in terms of (prefix bandwidth, atten- tion bandwidth). n: input length, m: number of edges, C: any integer 2 3, c: arbitrary constant (0, 1). b(n): any o(n) function, [Q]: state complexity of the language. Trivial upper bounds: (n logg [=]],00 0) or (0, n). Adding chain of thought (CoT) brings the upper bound down to (2,3) for
all decidable problems, but may require a large number of CoT steps.
Problem
Lower bound
Upper bound
INDEX (Thm.
(0, 1)
EQUALITY (Thm.
(1, 1)
BAPO- easy
DISJOINTNESS (Thm.
(1.1)
MATCH2,, (Thm.
(0.1)
regular languages (Thm.
(flog2 1Q].0)
REACHABILITY (Thm.
(o(m"// // log m), o(m 2
trivial
BAPO- hard
MAJORITY (Thm.
(o(log n), o(n²-9)
(flog2 n1.0)
MAтCH3, (Thm.
(o(n (b()/())))))))))))))))) b(n)
trivial
BAPO-
UNIQUE (Thm.
(o >
(2 Σ
E-hard
SETDIFF (Thm.
(ol
> /
Low BAPO complexity suggests that LLMs should be able to solve these problems well, which is corroborated by our empirical results in Section 4 These problems are also known be efficiently expressible by transformers [6]. Note also that INDEX is conceptually very similar to the common needle-in-a-haysttcc benchmark tasks.
Theorem 1. DISJOINTNESS and EQUALITY have (1, 1)-PPss and INDEX has (0, 1)-BAPO.
Proof sketch. Access to token indices allows the attention function to attend to bits that would be counterexamples to EQUALITY DISIOINTNESS, while the bit output by the prefix oracle needed when the prefix contains all of x and some of INDEX is trivial thanks to the attention function, which can pick out the indexed token. See Appendix B for the full proof.
Regular languages. We also show that recognizing any regular language is BAPO-easy, since any string's prefix can be summarized in constant space by a state the minimal automaton for the language by the Myhill-Nerode theorem [25]. However, this BAPO construction requires prefix bandwidth scaling with the language's state complexity, the minimal number of states in an automa- for the language. So, for any LLM with constant effective bandwidth, there may be infinitely many regular languages it cannot recognize. We thus think of the class of regular languages as "fixed paramete tractable" for BAPOs.
Theorem 2. For any regular with state complexity [Q], some (ilog2 () recognizes L.
Proof. Let E,,E, go. F) be minimal deterministic finite automaton (DFA) recognizing L. The BAPO's prefix oracle sends binary encoding of the DFA's state after runs on the prefix. The suffix oracle finishes running the DFA on the suffix and outputs I iff the final DFA state is in F.
3.2 BAPO-hard problems
We now show that the following problems are BAPO-hard (see Appendix A for formal definitions):
REACHABILITY: given directed graph G and two nodes 8, f, check if G has an s-t path.
MAJORITY: determine whether bit-string has strictly more ones than zeros.
MATCH3,, given input x E Z determine whether there are some i, E [n] such that Fn + I; + xy (mod m). Additionally, MATCH2, (which the problem of determining whether there is some i E [n] such that Ir, + I; = (mod m). These last-token versions of MATCH2 and MATCH3 [34]
show is BAPO-easy) is
UNIQUE (hard w.r.t E)): output any token that appears exactly in the input.
SET DIFF (hard w.r. E.: output token that is in the first input string but not the second.
5

---

We begin our hardness results with the important REACHABILITY problem, which encompasses many natural reasoning tasks, e.g., checking whether a conclusion follows from a chain of implica- tions. We show that mnnitedbbandwidng BAPOs cannot solve REACHABILITY, and our lower bound smoothly trades off between the prefix and attention bandwidth requirements. We provide a high- level sketch of the proof strategy, which is common to all of our hardness proofs. All full proofs omitted from the paper can be found in Appendix B
Theorem 3. No (o(m²// log m), o(m=-2/e))--Ba nodes and m = ((n)) edges for any integer constant 2 3.
can solve REACHABILITY in graphs with
Proof sketch. Suppose for a contradiction that some limited-bandwide BAPO (f, h) solves the problem. We construct a family of prefixes and suffixes such that: (1) the prefixes have substantial overlap with each other, (2) the attention function 9 pays attention to tokens that are common to all prefixes and thus cannot distinguish between them, (3) the number of prefixes is sufficiently large that the prefix oracle f is not one-to-one by the pigeonhole principle, and (4) given any two prefixes for which f collides, we can find a suffix that results in different solutions when concatenated to the colliding prefixes. This construction gives us contradiction: two instances of the problem with opposite answers which the BAPO cannot distinguish between, as it sees the same suffix, the same output of f. and the same set of attended tokens (given some adversarial choice of G).
We suspect this bound is not tight; closing the gap between Theorem and the trivial (m [log m], 0)- and (0, m))AAOS is an interesting open problem.
Next, we consider simple problem where our lower bound is tight, MAJORITY. According to the circuit-based analysis of transformer expressivity that shows they are in TC (23] this problem should be trivial, as it is solved by a single majority gate. However, as we will see in our experiments, LLMs struggle with MAJORITY; here, we show that BAPOs require super-constant bandwidth to solve it and that even near-lineal attention bandwidth is insufficient to improve the prefix bandwidth requirement. Our proof follows the same high-level strategy as with REACHABILITY.
Theorem 4. No n)), -)---OO can solve MAJORITY on length n inputs for any 0 < e < 1. This prefix bandwidth is tight: there is a ([log2 n1, 0) solving MAJORITY.
In Appendix B we show that increasing the attention bandwidth even beyond near- -ear-linear eventually reduces the prefix bandwidth lower bound for MAJORITY.
Turning to the next problem, Sanford et al. (34] showed that 1-layer transformers can efficiently solve MATCH2, but must scale polynomially to solve MATCH3. To keep the single-token output of our problems, we consider the contained subproblems of outputting the last item, which we call MATCH2,, and MATCH3 We show that manited-bandwidth BAPOs can solve MATCH2, but not MATCH3,, paralleling the results of Sanford et al. (34). Our proof again follows the same strategy as before, and with REACHABILITY, our lower bound trades off between the two bandwidths.
Theorem 5. For any b(n) onn) with b(n) 2 no (o(n/b(n)), b(n))-BAPO can solve MATCHI,, over 2% In contrast, there is (0, 1)-BAPO for MATCH12,.
In Appendix C we show that our BAPO-hardness proofs above are robust to more powerful general- izations of the BAPO model where allow multiple layers of attention functions operating sequen- tially, as well as real-valued attention scores rather than binary. While not affecting the hardness of REACHABILITY, MAJORITY, or MATCH3,, this augmented model is able to solve the (multi-hop) induction heads task (26), which otherwise appears to be BAPO- -hard.
Finally, we show two problems are BAPO-E-hard, starting with UNIQUE, the problem of finding an item that appears exactly once in a sequence. Here, the difficulty of the problem is parametrized by the size of the token vocabulary Σ rather than the length of the input A very similar approach applies to SETDIFF, for which we find the same bound.
Theorem 6. Let k [Σ]. For any b(k) = o(k) with b(k) 2 1, no (o(k/b():)), b(k))-BAPP can solve UNIQUE This is tight b(k) O1),, as there is (2k, -)-BAPO solving UNIQUE
Theorem 7. Let k [ For any b(k)) = o(k) with b(k) 2 1, no (o(k:((())), B(K))-BAPO can solve SETDIFF This is fight for b(k) = O(1), as there is a (k, -BAPO solving SETDIFF

---

3.3 BAPOs with chain of thought
We now show that any (decidable) BAPO-hard problem can be broken down into a sequence of BAPO-casy steps in the spirit of chain of thought (CoT) [43]. Previous work has shown how CoT makes transformers Suring-compled
(24). We show that CoT has an even stronger benefit: adding CoT to BAPOs lets them solve all decidable problems with constant bandwidth, indicating that even LLMs with constant effective bandwidth are turing-complett with CoT.
To formalize CoT in the BAPO setting, we repeatedly apply fixed BAPO to the input concatenated with the BAPO's 's previous output tokens, just as in auto-segressive decoding in LLMs.
Definition 2. An (a, b)-bounded attention prefix oracle with chain of thought (BAPO-CoT) that solves a computational problem p -n Σ is (a, BBAPO over the token set I 2 U {D} that solves some computational problem p' I + I' such that for all inputs I E ) to p. there exists some sequence of strings $1,..., 8m 1 with the following properties. (1) 81
(the
I...., m7 (at each step, it produces some chain-of of-thhugtttth token), (3) p' (s.) D if and only if m 1 (at the last step only, outputs the halt token), and (4) ps(mm2) = p(z) (it solves the problem before halting).
BAPO-CoT starts with x as its input), (2) 8,+1 = ssp)(s;) for all
Let T = (x E I::
|x|| S n). We show that bow-bandwidth BAPO-CoTTs exist for any decidable problem; the core idea is that simulating a single Turing machine step is a wwwbbanwidth problem.
Theorem 8. Let L be language decided by a Turing machine with s(n) space and input alphabet = [0, 1]. For any n, there exists a (2,3) -)APPOCC that recognizes LS".
Proof sketch. The BAPO-CoT simulates a Turing machine M by writing out the contents of the tape and the state at every step of M's execution. The attention function attends to the prefix to retrieve the current state and the prefix oracle passes along the bit under the tape head (if they are not in the suffix), allowing the suffix oracle to simulate a step of M. See Appendix B for details.
4 BAPO complexity predicts empirical LLM failures
Our experiments test whether BAPO complexity predicts LLM failures. Supporting our effective bandwidth hypothesis, we find that LLMs across model families consistently struggle with BAPO- hard problems and usually succeed on BAPO-casy problems. We choose three big model families (GPT (27] Gemini [6) and Claude 3 ) and focus first on model versions without (latent) reasoning chains to align with the single-token-output BAPO model.
Except for INDEX and the BAPO-E-hard problems UNIQUE and SETDIFF, all problems have yes/no answers (so guessing achieves 50% accuracy). We designed problem instances so that there would be no obvious shorteut or heuristic, pushing models to fully consider each problem. LLMs are fed with inputs of various lengths n, where n corresponds to the parameter specified in each problem's 's definition. For all problems, we generate 100 i..dd instances and report average accuracy along with the 95% t-test confidence interval. All data generating distributions, prompts, and model details are available in Appendix D.I and our code available at hittt:::/ //githuu conmmmccoooofii bbppo
4.1 BAPO hardness aligns well with LLM failures
Figure shows the accuracy of LLMs across six different tasks (see Appendix D.2 for additional problems). The top row shows three BAPO-easy problems and the bottom row three BAPO-hard problems (cf. Table TT. Performance is low or rapidly dropping for BAPO-hard problems; in par- ticular, there is no LLM that performs well for all n. In contrast, most LLMS perform consistently well across all n BAPO-easy problems, with MATCH2 appearing the hardest. We suspect that representational issues interfere in this setting, as the LLM needs perfect understanding of integers.
Comparing models of different scales (solid vs. dashed lines), we can see that in line with the typical observations, larger models appear to perform better overall. However, even with increased scale, no model is able to avoid the degradation our BAPO framework predicts.
7

---

buss
Egg AUTY
Macad
model
0.3
GPT-4o
accuncy
0.6
Clodke 1.5 Somrel
Chade Halko
0.4
Gamm 1.5
Genzi 1.5 Flads
150
200
50
150
200
150
700
REAcIVALITY
MasseITY
Macad
0.8
aoumey
0.6
0.4-
0.2
1.50 2000 50
150
200
90
200
Figure 3: BAPO-hard problems (bottom row) show much larger drops in accuracy compared to BAPO-easy problems (top row). Not even large LLMs can solve BAPO-hard problems at length 200 with an accuracy above random guessing.
Co1)
pet
GPT-4c
300mm2y
GPT-4o
Clande
Clande 3.5 Hallo
0.4-
0.2
Ganm 1.5 Flach
Gerri 2.5 Flads
50
100
150
200
50
100
150
200
50
1000
1.00
200
Mantac
0.6-
0.4-
0.2
10
100 1.40
7000 11 10 1000 1.00
7000
400
1000 1.50
700
Figure 4: Adding CoT can help LLMs do better on BAPO-hard problems, but substantial perfor- mance drops still occur with limited CoT budget (soft limit of 250 words for non-reasoning models). Without imposing limit on their internal reasoning, o3 and, to a lesser extent, Gemini 2.5 Flash perform extremely well (see Appendix D.1.2 for their CoT token counts, often in the thousands).
4.2 thain-of-thought reasoning helps on BAPO-hard problems
Given how powerful BAPO-CoTs are in theory, the obvious question is whether CoT improves performance on BAPO-hard tasks. To test this, we prompted each LLM to perform CoT before producing the answer, with a soft limit of 250 words. We also tested o3 (28) and Gemini 2.5 Flash [17), which use (potentially many) internal chain of thought tokens. As Figure F shows, CoT modestly improves non-reasoning LLM performance on BAPO-hard problems for smaller input sizes n. The fact that issues still persist indicates that these LLMs may not be applying good low- bandwidth COT procedures, or that they may require more reasoning tokens. Indeed, without the limit on CoT tokens, o3 and Gemini 2.5 Flash succeed on BAPO-hard problems. This is likely due to the much larger number of CoT tokens they use (over 10k in some cases; see Appendix [.1.2p and the fact that they are (presumably) trained to use CoT tokens effectively.

---

MARorm (MacerT))
(heex/ Namorrll Harmac)))
model
0.3
GFF-4
accrnayy
Clasde Senrel
Clande Halku
Genui 1.5
Genzi 1.5 Flaal
30 100
30
100
30
100
Figure 5: There is good evidence that BAPO-difficulty translates to real-world settings, LLMs can solve real-world tasks that contain BAPO-casy problems (left plot) with much greater accuracy than BAPO-hard problems (two plots on the right).
4.3 BAPO hardness in real-world tasks
We finally turn to set of experiments that examine real-world tasks corresponding to BAPO prob- lems. For the first domain, inspired by the ZeroScrolls benchmark [38], we consider hotel reviews from the SPACE dataset [2] and either ask the LLM find negative review in collection of positive reviews (analogous to the BAPO-easy INDEX problem) or decide whether the majority of reviews are positive (analogous to the BAPO-hard MAJORITY problem). We ensure that baseline LLM can determine the sentiment of each review. The second domain is programming. where we define two chains of assignments and ask whether the final variable has value "a" or "b", extending the variable tracking task from the RULER benchmark (20). This task is special case of REACHA- BILITY, one of BAPO-hard problems. See Appendix D.I.3 for experiment and data details. The plots in Figure 5 show that again, AAPO-hardness is good predictor of LLM performance.
5 Related work
Theoretically, limitations of transformers have been studied via communication complexity [35] 29), cireuit analysis [23] [3] and parallel computation frameworks B5 37,. among other methods. We contribute to this toolbox with the BAPO model, which provides a natural way to study how causal attention exacerbates limits on information flow in LLM architectures.
Among the best known results on transformer expressivity is that transformers are log-space uniform TC 23 39] Strobl et [40] survey known theoretical results showing an inherent ex- pressivity gap for transformers to recognize certain formal languages. For instance, Hahn [18] show that transformers with one-hot hard attention cannot solve PARITY and 2DYCK, while Bhattamishra et al. [6] show that two-layer transformer can solve INDEX, EQUALITY, and DISJOINTNESS. RASP 44 offers a higher-level way to establish similar upper bounds by constructing a transformer program, although without causal masking. Some expressivity analyses depend the size of the transformer: Sanford et al. [35), Fagnou al. [14] derive logarithmic lower bounds on the num- ber of transformer layers required for graph and entity tracking tasks (related to similar bounds for map-reduce (32). while Sanford et al. [34] show that a single transformer layer can efficiently rea- pairs of tokens (MATCH2) but not triplets (MATCH3). However, transformer expressivity does not always align with empirical observations of LLM performance. Rather than characterizing theoretical expressivity, the BAPO model captures high-level information flow, which we hypothe- size underlies many problem-solving failures in practice.
Even when task is, in principle, solvable by transformer, it might still be hard to learn { Edel- man et al. [12] argue that attention in transformers tends to represent dependencics among only a small number of tokens, causing failures for global problems. Hahn and Rofin [19 show that al- though PARITY is representable, is hard to learn a sennth--enerallee
solution because the training loss landscape is highly sensitive to all the inputs. Similarly, Thomm et al. 42 show that LLMs are data inefficient over compositional problems and Liu et al. (22) argue that transformers learn short- cuts to simulating finite-state automata. Our BAPO model captures this representability- learabbbiyyyyy gap by positing that although architecturally the communication bandwidth from prefix tokens of a transformer be large, the effective communication bandwidth in LLMs is very limited.
Lastly, the success of CoT 43 has also been analyzed theoretically. Merrill and Sabharwal 24 showed that CoT makes transformers Turing-complete, and Feng et al. [1] argue that CoT enables

---

transformers to solve dynamic programming problems that bounded-depth transformers cannot. Our theory shows that CoT has another benefit, as it dramatically lowers bandwidth requirements: any Turing machine can be simulated by a constant-bandwiith BAPO-CoT.
6
Discussion
Our finding that the effective bandwidths of LLMS are small despite their massive size suggests that simply adding more layers, attention heads, or embedding dimensions might not translate directly to higher BAPO bandwidth. We still lack a full understanding of what causes this severely limited bandwidth. It might even be feature rather than bug: low effective bandwidth may aid flexible and generalizable next-token prediction, and there could be tradeoff between generalization ability (required for natural language) and exact imput representation (required for global reasoning).
Beyond the precise mathematical framework of BAPOs, applying the intuition that lower- bandwidth problems are easier for L.MMs can help understand their successes. For instance, many in-context learning tasks can be solved by a k-nearest neighbor approach, matching a new instance to a small number of in-context examples. This is a procedure whose bandwidth requirement does not scale with the number of in-context examples, but whose accuracy does; this provides a possible ex- planation for the success of LLMs on such tasks. As another example, geedle-in-a-haystade tasks commonly used to benchmark LLMs also require small amount of cross-stream communication.
Lowering bandwidth. Our model also deepens the understanding of CoT by proving that it re- duces the communication requirements of
the number of reasoning steps can be impractically large. This motivates future work to take better advantage of the mandwidth-lowerinn benefits of CoT or directly optimizing for low bandwidth as part of the training objective when fine-tuning on reasoning chains. Our work also motivates the investigation of methods beyond in- ference time scaling for reducing the communication burden of problems. For some problems, pre-processing such as simplifying inputs (45) or retrieval 21 may reduce communication load.
Refining BAPO. Another future direction is in exploring variations of the BAPO model to help align more closely with the behavior of LLMs. For example, the induction heads task [26] 37 is thought to be important mechanism for transformers. but appears challenging for BAPOs. However, we show in Appendix C that a BAPO with multiple layers of score-based attention can perform induction heads, while preserving the MATCHB, This suggests these problems are fundamentally hard, and that others lie between the basic BAPO model and LLM capabilities. Future work can explore how these and other BAPO variants affect BAPO-hardness and which problems are fundamentally high-bandwidth.
of REACHABILITY, MAJORITY, and
Limitations. See Section 2 for discussion of ways in which the BAPO model does not faithfully represent transformer computation. It also does not capture all failure modes of LLMs, such as tokenization-drive errors; thus, BAPO-easiness is not guarantee that LLMs can solve task. We also do not know the root cause of effective bandwidth limits on LLMs. Finally, many of our lower bounds are loose, and there are many problems whose BAPO bandwidths have yet to be explored.
Conclusions
We introduced the BAPO model of handwidth-limiter computation, designed quantify and ana- lyze hypothesized limits on the cross-stream communication of transformer-based I.L.s. On the theoretical side, we categorize variety of problems as BAPO-casy, requiring only constant band- width, and BAPO-hard, requiring super-constant bandwidth. This dividing line aligns well with problems that modern pothesis that they are constrained in their internal communication and indicating that their effective bandwidth for mroblem-solving is a small constant. For practitioners, the BAPO framework offers a new lens through which they can view their LLM tasks, possibly opting for mitigation strate- gies such as tool calling and reasoning in cases where they suspect failures due to BAPO-hardness.. Understanding that limited communication bandwidth is at the heart of why LLMs fail to reason globally also unlocks a new set of directions for future work, such as different architectures, reason- ing algorithms, or training paradigms.
LLMs consistently struggle with, supporting the hy-
10

---

Acknowledgments
We are grateful to Doug Burger, Philippe Laban, Suriya Gunasekar, Daniel Hsu, Besmira Nushi, Clayton Sanford, Siddharth Suri, Dawen Liang. Harald Steck, Chinmaya Kausik, Nathan Kallus, the MSR Al Interaction and Learning group, and the Netflix Machine Learning Inference Research group for helpful discussions and feedback.
References
[1] Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, and Omid Saremi. How far can transformers reason? The globality barrier and inductive scratchpad. In NeurIPS, 2024.
[2] Stefanos Angelidis, Reinald Kim Amplayo, Yoshihiko Suhara, Xiaolan Wang, and Mirella Lapata. Extractive opinion summarization in quantized transformer spaces. TACL, 9, 2021.
[3] Anthropic. The Claude 3 model family: Opus, Sonnet, Haiku.
htw.///w/ccauee-eeee 3- 2024. Accessed: 2025-04-17.
[4] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document trans- former. arXiv preprint arXiv:2004.05 2020.
[5] Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of trans- formers recognize formal languages. In EMNLP, 2020.
[6] Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade, Separations in the representational capabilities of transformers and recurrent architectures. In NeurlPS, 2024.
[7] Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou. Birth of a transformer: A memory viewpoint. In NeurlPS, 2023.
[8] David Chiang and Peter Cholak. Overcoming a theoretical limitation of self-attention. ACL, 2022.
[9] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:/904 10509, 2019.
[10] Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang (Lorraine) Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena Hwang, Soumya Sanyal, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Limits of trans- formers on compositionality. In NeurIPS, 2023.
[11] Mohammad Reza Ebrahimi, Sunny Panchal, and Roland Memisevic, Your context is not an array: Unveiling random access limitations in transformers. COLM, 2024.
[12] Benjamin L Edelman. Surbhi Goel, Sham Kakade, and Cyril Zhang, Inductive biases and variable creation in self-attention mechanisms. In ICML, 2022.
[13] Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Nova DasSarma, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei. Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. A mathematical framework for transformer circuits. Transformer Circuits Thread, 2021.
ormer-rrrr----- circuits orrrranntttsss-rrrrutttsssss putp2021///aeeerr/r/ooo itwiiindxxxiiic
[14] Erwan Fagnou, Paul Caillon, Blaise Delattre, and Alexandre Allauzen. Chain and causal at- tention for efficient entity tracking. In EMNLP, 2024.
[15] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di Hc, and Liwei Wang. Towards revealing the mystery behind chain of thought: A theoretical perspective. In NeurlPS, 2023.
[16] Google. Gemini: a family of highly capable multimodal models.
arXiv preprint
arXiv:2312.1 /1805, 2023.

---

[17] Google. Gemini 2.5 flash. httpss//dapppiiil.gggogoooooooop 2025. Accessed: 2025-05-14.
[18] Michael Hahn. Theoretical limitations of self-attention in neural sequence models. TACL, 8, 2020.
[19] Michael Hahn and Mark Rofin. Why are sensitive functions hard for transformers? ACL, 2024.
[20] Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, and Boris Ginsburg. RULER: What's the real context size of your long-context language models? In COLM, 2024.
[21] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Na- man Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmented generation for knowledge-intensive NLP tasks. In NeurIPS, 2020.
[22] Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang, Trans- formers learn shortcuts to automata. In ICLR, 2023.
[23] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. TACL, 11, 2023.
[24] William Merrill and Ashish Sabharwal. The expressive power transformers with chain of thought. In ICLR, 2024.
[25] Anil Nerode, Linear automaton transformations. Proceedings of the American Mathematical Society, 9, 1958.
[26] Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodde Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse. Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. In-context learning and induction heads. arXiv preprint wwX.v:2209.11892 2022.
[27] OpenAI. GPT-4 technical report. arXiv preprint arxiv:3003.08774,.00 2023.
[28] OpenAl. Introducing o3 and 04-mini. -anpaaiiiii---------------------
2025. Accessed: 2025-05-14.
[29] Binghui Peng. Srini Narayanan, and Christos Papadimitriou. On limitations of the transformer architecture. In COLM, 2024.
[30] Jacob Pfau, William Merrill, and Samuel Bowman. Let's think dot by dot: Hidden compu- tation in transformer language models. In COLM, 2024.
[31] Tim Roughgarden. Communication complexity (for algorithm designers). Foundations and Trends in Theoretical Computer Science, 2016.
[32] Tim Roughgarden, Sergei Vassilvitskii, and Joshua R Wang. Shuffles and circuits (on lower bounds for modern parallel computation). JACM, 65, 2018.
[33] Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. TACI, 9, 2021.
[34] Clayton Sanford, Daniel J Hsu, and Matus Telgarsky. Representational strengths and limita- tions of transformers. NeurIPS, 2023.
[35] Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Hal- crow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. In NeurIPS, 2024.
12

---

[36] Clayton Sanford, Daniel Hsu, and Matus Telgarsky. One-layer transformers fail to solve the induction heads task. arXiv preprint arXiv:2408. 14332, 2024.
[37] Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth. In /CML, 2024.
[38] Uri Shaham, Maor Ivgi, Avia Efrat, Jonathan Berant, and Omer Levy. ZeroSCROLLS: A zero-shot benchmark for long text understanding. EMNLP, 2023.
[39] Lena Strobl. Average-hard attention transformers are constant-depth uniform threshold cir- cuits. arXiv preprint arXiv:2308. 2et.:220800022,,.. 2023.
[40] Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? A survey. TACL, 12, 2024.
[41] Sainbayar Sukhbuatar, Édouard Grave, Piotr Bojanowski, and Armand Joulin. Adaptive atten- tion span in transformers. In ACI., 2019.
[42] Jonathan Thomm, Giacomo Camposampiero, Aleksandar Terzic, Michael Hersche, Bernhard Schölkopf, and Abbas Rahimi. Limits of transformer language models on learning to compose algorithms. In NeurlPS, 2024.
[43] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc Le, and Denny Zhou. Chain of thought prompting elicits reasoning in large language models, In NeurIPS, 2022.
[44] Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In JCML, 2021.
[45] Ke Yang, Yao Liu, Sapana Chaudhary, Rasool Fakoor, Pratik Chaudhari, George Karypis, and Huzefa Rangwala. AgentOccam: A simple yet strong baseline for LLM-based web agents. In ICLR, 2025.
13

---

A Full problem definitions
Definition 3. DISJOINTNESS: [0, X 10, + {0,1] is the problem of finding if two sets represented as bit-strings are disjoint, with DISIOINTNESS(2; y) AeEia (x2, A vi). We encode a DISJOINTNESS instance (z, y) with the string z over Σ {0,
Definition 4. EQUALITY: 13" R {0, 1 + {0, 1 is the problem of finding if two bit-strings are equal, with EQUALITY (z. y) = [x = w/- We encode an EQUALITY instance (ar, y) with the string æ/y over Σ = (0, 1,
Definition 5. INDEX: 10" x [n] + {0, } is the problem of identifying the bit at a given index into the input, with INDEX(x, i) Zz.- We encode an INDEX instance (z, i) with the string æi over
= {0, 1] U [m).
Definition 6. REACHABILITY: ([n] x [xa])T x [n] x [n] + {0. }} is the problem of determining if there is path from to t in directed graph G with n nodes and edges. To encode the problem with perfect tokenization, let Σ = [n] x [n] U [n] where the token (i E E represents edge (i.j) and the integer tokens represent nodes. An instance of REACHABILITY specified by the edge list of G in arbitrary order followed by the nodes s and t.
Definition 7. MAJORITY: {0, 1)" + 10,1) is the problem of determining whether the input has strictly more ones than zeros, with MAJORITY(s) = Eiejni z4 > n/2].
Definition 8. Given input x 2m MATCH3 is the problem of determining whether there are some i.j E [n] such that In + F3 + 2j 0 (mod m)) Additionally, MATCH2,, is the problem of determining whether there is some E [n] such that xn + I3 = 0 (mod m)) We encode instances of these problems with the string x over Σ = Z.n.
Definition 9. UNIQUE: E- + Σ U {0) is the problem of identifying any unique token in the input.
That is, UNIQUE(ZI.... ... xx,) zj s.t. Σ j=1 1|x,- x. 1. or 0 if no such 2; exists.
Definition 10. SETDIFF: E' x Σ- - E U {0) is the problem of identifying any token in the first part of the input that does not appear in the second part. That is, SETDIFF(C, ... Cr. di ......d. ...d))) = o for some i E [nx] such that a * dj for all j E [m], or 0 if no such element exists. We encode a SETDIFF instance (c,d) Σx Ex with the string cld over Σ (I..
B Proofs
zi, the idea is simple: we set g(8k-1 Sn, k 8) = 1 if and only if j = 8n. The suffix oracle returns whatever token is attended un-uss the index is in the suffix (i.e., 8, 2 k + 1), in which case the suffix oracle immediately returns the bit at position 8n, which lies in the suffix and therefore visible without using attention. No output from f is required.
Proof of Theorem For INDEX instances given as
For DISJOINTNESS instance encoded as s = aly. the key is that we only need a single counterex- ample bit where z; Vi = 1 to conclude that æ and are not disjoint. If no such counterexample exists, then they are disjoint. We can construct a (1, -BAPO using this fact. The prefix oracle outputs 0 ("no counterexample found") if (a) the token is not in the prefix or (b) if the token in the prefix and the starting bits of y present in the prefix are disjoint with the corresponding bits of x. If there is a counterexample bit in visible in the prefix, the prefix oracle outputs 1. If the suffix oracle receives a from J, it always outputs indicating æ and y/ are not disjoint. Meanwhile, the attention function attends to any prefix bits that would be a counterexample to the disjointness of æ and y, i.c., g(5k+ ... Sns ls st, i) = 1 if and only if either (a) is not in the suffix and i' = i + (k: + |sk+1 ... Sn - 1)/2 + > k + 1 (i.c., the token we need to compare to is in the suffix) and sy = 8; = 1 or (b) is in the suffix and syr = s; = 1. If the attended token set G is nonempty, then and are not disjoint and the suffix oracle outputs O. If the attended token set is empty and is in the suffix, the suffix oracle can check the portion of x present in the suffix against the corresponding bits of y. If no counterexample bits are found (by f. g, or h), then none exists and the suffix oracle outputs
For EQUALITY, the same idea applies: we only need one counterexample x; * Y: to conclude that x # y- The construction is precisely the same as for DISJOINTNESS, except we look for counterexamples where xa # yı rather than J, = D1 = 1.
D
14

---

+1
M13
M12
M17
811
M12
817
Mg1 M32
W37
B31
Mg2
937
Figure 6: Left: the graph from the proof of Theorem for p c 3, so
p" 27 and
i - 24. Right: P with the permutation = 231 applied to the targets of the second-layer edges. Applying any non-identity permutation to single layer changes the connectivity of least one s-t pair.
Proof of Theorem Suppose such BAPO exists for a contradiction, and let f and be its prefix oracle and attention function, with bandwidths a = o(m!/e log m) and 00==(m=22/ap respectively. We will construct a family of prefixes and suffixes where the prefixes contain the entire graph and the suffixes contain the nodes and t, taking care that the graphs in different prefixes are mostly identical saturate attention.
Let n = pd for some integer p for simplicity (if n not expressible as a eth power an integer, the argument would involve various ceilings or floors, but these do not affect the asymptotics). Let P be the graph consisting of p disjoint directed paths with start nodes $1, $1...., and target nodes ti....,tp. where each path has exactly pf nodes. Then, for each i E [p] and j E [p--1_ 2]. let ui be the unique node at distance from 8,. See Figure 6 for visualization of this graph with ====3: We will keep these node labels fixed but modily P by permuting edges based on the attention function g render attention useless. Note that we can apply permutation E Sp to the target nodes of the edges departing from Wij....,; Upj while maintaining the property that P disjoint collection of length pr-1 paths each starting from an node and ending at a node, although the permutation changes which s-f pairs are connected (see Figure right). To construct our shared prefixes that saturate the attention function 9. we will need to take care to place edges at consistent indices in the prefixes. To this end, fix the edge order to first list the edges departing from $1, ..... Sp, then U11. Up1, then U12,.... Uy2, etc. Call this the canonical edge order and let (u) denote the index in the canonical order where the edge departing is placed. Note that the length of the full edge list is m = pf p. Given these observations, construct the shared prefix graph P follows:
1. Initialize Pa to have the same set of nodes P. Initialize S to be the set of all s; and ui nodes, which will store the current set of nodes that still need an outgoing edge.
2. For each pair (i.j) E [p] x [p]:
(a) For = I.....b:
i. If there is some node u in S and some node v in the layer to the right of u such that g(sztj m, (u, v), [())) = and has in-degree in P*: add (u, v) to P and remove from S.
Check every feasible edge we could add; if g wants to attend to any edge (u, v), add it to P*.
ii Else: exit the inner for loop. If there are no remaining edges would attend to given suffix 851g. then we can stop, as atlention is now saturated for this suffix.
3. Let E* be the set of edges in P* at this point in the algorithm. These will be shared among all prefixes to saturate attention. To complete the paths in Pa arbitrarily, connect each node with out-degree 0 (that is not node) to the first node with in-degree 0 in the next layer.
This procedure produces graph P which can be reached by starting with P and permuting the targets of the edges in each layer by some n, since each edge we add connects a node with current out-degree ( to node in the next layer with current in-degree O. That is, p* is also disjoint collection p paths of length ffー each connecting some 8; to some Ly- We have placed edges in p' such that for any suffix s,yy with j, E [p), there exists some attended token set G where every
15

---

edge in G is in E", so we can modify the other edges in P without alerting the attention. Each iteration of the outer for loop ensures one suffix has its attention masked; we complete b iterations of the for loop, then we have ensured there is some G with |G] = b that contains only edges in E", and if we need to exit early due to the nonexistence of an attended edge in line 2(a)i, then no other edges we end up placing in P will ever be attended to given that suffix (as 2(a)i checks every feasible edge). Moreover, the total number of edges in E" is at most bp² o(m² o(m!-2/op3 p2)pp) o((p")) = o(p") (since there are m = p' - -p < p" edges in P").
Now, since there are pf layers of edges in P there must be some layer with (p)) edges not contained in F otherwise we would be able to find (p²") edges in E", a contradiction. Call this layer j" and let d = (p)) be the number of edges in layer j that not in E". Construct family of graphs p of size d! by taking P and applying each permutation x E Sg to the targets of edges in layer j" that are not in E*. We now have our full collection of prefixes and suffixes: the d! prefixes are the canonical edge lists of each graph in P and the p² suffixes are every sily pair.
@(d d) = O log p). Thus, since f has bandwidth o(m log m) = loplogg1 p). f must have collision on the size d! family of prefixes generated by P (as it takes log, (d!) = (pp logp) bits to distinguish between the prefixes). These two colliding graphs are generated by different permutations on the edges in layer j", so there is some pair of start and target nodes s"-t" connected in one of the graphs but not the other (as the edges in all other layers are identical). Given the suffix s"t", we find that the BAPO fails to distinguish between the colliding graphs: it gets the same output from f and there some attended token set G that contains only edges in E*, which Given this adversarial G containing only attention-saturating edges, the suffix oracle h gets identical inputs: the same output from f. the same G, the same suffi s²t" and the same prefix size m. In this case, the BAPO fails to solve the problem in one of the two graphs, as one has an s -t" path and the other does not.
By Stirling's approximation and the fact that d @(p), log2(d!)
identical in the two graphs.
O
Proof of Theorem 4 First, (flog2 n1, O)-PPP can solve MAJORITY by having f(x output the number of I's in Ir which takes at most [log2 n1] bits and requires no attention tokens.
Now suppose for contradiction that (f.g. h) is a BAPO with prefix bandwidth = ollog n) and attention bandwidth = osn that solves MAJORITY on inputs of length n. Let m be any positive integer and let f = ml(-e)/= (for simplicity assume is an integer; otherwise we could take a ceiling without disrupting the proof). The proof follows three high-level steps: (I) set up the structure of
prefix-sufiix pairs, (2) design the prefixes so that attention cannot distinguish between them, (3) find colliding pair of prefixes and suffixes that the BAPO cannot distinguish between but which have different MAJORITY answers.
Given any π E S. (the {(<(0'=] fm 1010001mmmmmmm 1mmm)mm))))))) 0m= 1 1+ length n = 2 1)m = 2m 0mm1((1-0/+ + 2m, with (E 1)m 1 ones and (E + +)m - zeros; so all of them have a majority of ones. Let s be the suffix in Xx with k + 1 ones and let S = fsx kk mm-1 We will show show to pick x based on g such that X, fools the BAPO, We will give the BAPO O(n 1inn--9 -. as (m) (1l))/////)1----
permutations on [m]). define X= 1== Note that every prefix suffix pair in X, has total
mmm1
é= (1-c)ff attention tokens. Note that (1-
ml
For any suffix s, define [s) = {i E [(2E + 1)m] g(s, (2 + 1,m,, 0, = 1} to be the set of prefix indices where g selects O's given suffix s, and define T₁ (s) similarly to be the set of prefix indices where g selects I's. We will pick и so that for every & E S, л permutes the prefixes so that it places leading zeros and ones in at least indices selected by g (or such that g selects only indices masked by leading zeros and ones) for every suffix in Xx. We construct that π with the following procedure.
1. Initialize To 0 and IT 6. These sets store indices to place leading zeros and ones so that we fool g for all suffixes
2. For k = O.... m - 1:
(a) While [s(())) n Uol + (s)) I <
If this is false, we have succeeded in masking 2 positions selected by g given sy. i. If 3i E To(*k) \ (Tp U IT): add i to No-
Mask a position where g selects a zero.
16

---

ii. Else if Ei (1s)s) \ (IL UT):: add i to III.
Mask a position where g selects a one.
iii. Else: exit the while loop.
There are no unmasked positions selected by g on Sk, so we have succeeded on st.
3. Let i = 1. For each j E Tl. set (ii) = j and increment i.
Make π permute leading zeros into the masking indices we have picked.
4. Let i im + 1. For each j 11, set (i) j and increment i. Make π permute leading ones into the masking indices we have picked.
5. Fill in π where not yet defined with the remaining indices in order.
This procedure terminates, since each iteration of the while loop increases the combined sizes of the intersections in (a) by or exists the while loop. Additionally, it generates valid permutation and Hy and II, are disjoint, since we only ever add indices i which are in neither of them to exactly one of them. Next, for every (T (p),,)) 8) E Xx, either: (1) there are at least E indices selected by g on input (m(p).)) 8) with T C Mo UTT, or (2) on input (p), s), g selects only indices in No U TT, Case (1) occurs if we are able to complete the while loop for s without ever hitting the else in iii, since then we will have l such indices in Ho and 11,. In 3, ensure the indices where g wishes to select zeros are masked with leading zeros; in 4, we ensure the indices where wishes to select ones are masked with leading ones. Case (2) occurs if we hit the else in iii, as in that case, there are prefix indices selected by g which are not already in 1lg U 1l and thus all selected indices will be masked by leading zeros and ones.
This π gives us set X, where the set of attended tokens G is entirely useless over every prefix- suffix combination, in the worst case over adversarial choices of which & tokens are attended to. That is, for any prefix T rpp) and any suffix 8 from X₂ that may be from different pairs, G(r(p).)) (the attended token set for the given prefix-suffix combination) can be identical: an adversary picking which f tokens are attended to can pick all of them to come from indices masked by leading zeros and ones (i.e., indices from 1ig Ull1), which are identical across all m prefixes in X,, as the prefixes only differ in indices not in 1l Ull.
Now, there are m distinct strings in X². Since the prefix bandwidth of f is o(logn) o(log m (1))))))
o(log m), there are fewer than 2 m = m distinct outputs of f, so by the pigeonhole principle there are two elements (a,b), (c, d) E Xx where f(a) = f(c). If (a, b) has k + 1 ones in b and (c, d) has K' + 1 ones in d (without loss of generality assuming k' > k), then the string ab has a majority of ones (fm + m k + k + 1 > (e+1))m + 1 ones total) but ob does not (fm + k + m - k 1 2 (L 1)m zeros total). Thus, consider the inputs b) and (c. b). The prefix oracle f outputs the same thing both cases, and as we have seen that G(a,)) can equal G(e,b). Moreover, the suffix oracle gets the same suffix in both cases, so there exist attended token sets where the suffix oracle outputs the same answer on both input pairs (having received all the same inputs: same prefix oracle output, same suffix, same attended tokens, same split index). But (a. b) and (c, b) have opposite answers to MAJORITY: (a. b) has a majority of ones and (c. b) does not. Thus the BAPO answers one of these instances incorrectly for some attended token set.
While near- linear attention does not help the required asymptotic prefix bandwidth over zero atten- tion, our proof does result in weaker lower bound on prefix bandwidth with even more attention. Corollary 1. No (o(log log n), onn/ log -BAPO can solve MAJORITY length inputs.
Proof. Now we use even more masking bits, m2n zeros and ones, so n = m22+1 + 2m. With 2m = Onn/ log n) attention tokens, using the same argument shows that ollog l) ollog m) prefix bandwidth can cause a collision.
We suspect that this lower bound is loose, and that in fact log n prefix bandwidth is still required even with O(n/ log n) attention. However, we can increase the attention bandwidth even more (all the way to (nn), but still less than n) so that we do lower the asymptotic prefix bandwidth requirement. For instance, with n log n attention tokens, we only need 2(log log n) prefix bandwidth.
Proposition For any 1 S a(n) = o(n), there is a (Mog, a(n)], n a(n))-BAPO solving MA- JORITY on length n inputs.
17

---

Proof. The BAPO is simple: attends to the first n a(n) tokens of the prefix and f passes on the ones count in the remaining part of the prefix, which takes at most flog, a(n)] bits. This information suffices to allow the suffix oracle to solve the problem.
The hardness of MAJORITY immediately implies at least the same degree of hardness for MEDIAN, the problem of finding the median of input sequence of integers, and MODE, the problem of finding the most frequent item in a stream. We believe these bounds are very loose.
Corollary 2. No (o(logn), n), ())-PPOs solve MEDIAN or MODE on length n inputs for any 0 <<<l
Proof. On bit-strings, the median and mode are if and only if the string has a majority of I's.
For proving MATCH3, is BAPO-hard, the following lemma helps us find 2;-ry pairs that form a match with some particular suffix Tn, but such that and xú do not form matches with any suffix E S and other prefix integer 2 E Z, where Z is the set of integers we have already decided to place in prefixes.
Lemma 1. Let S, Z C. Zm with m > 100, max,ss S Vm, |S| S mm/2, and |Z| S vm/22. For every s E S, there exist x, y. E Zm Z s.t.:
1. x + +++ 0,
2. for all E 7. and all s' E S, + + s' #m 0 and y + 2 + 8 =m 0.
Proof. Condition is satisfied as long as x. y E Zmn Z are not in
mod m m/4. This leaves least 3m/4 mm/2
S, Z}. which has size at most (vm/2)² admissible values in Zm \ Z. We will show that there are enough z-y pairs with distinct values and y satisfying Condition that they cannot all be disallowed by Condition 2 and the requirement that v; y & Z.
Consider all pairs x, y E 7.m such that r + y + & =m 0: for each E Z.m. we can set x = i mod m and y = - i mod m. If we consider < S m/4+ /m/2 + 1, the values x and y take on all distinct (since S /m and m/4 > 2/m, every y value is larger than every value). Since there are only m/4 + mi/ /2 disallowed values for æ and y, there must be some x, y pair in this range of more than m/4 + v /m/2 values of i where both and y admissible.
Proof of Theorem 5 First, consider MATCH2,. The attention function g can select any prefix ele- ments 2y such that Fn + I, 0 (mod m), since Tn is always in the suffix. The suffix oracle only needs single such example to confirm that this is yes instance. If the set of attended tokens is empty, then the suffix oracle can check if there are any matches in the suffix. If not, this no instance. We do not need f at all.
Now show that MATCH3,, is BAPO-hard. Suppose for a contradiction that (J,g. h) is BAPO solving MATCH3, with prefix bandwidth o(n/b(n)) and attention bandwidth b(n). We will con- struct collection of prefixes and suffixes that fools the BAPO with total input length Let > 10 and pick m = n²?
Consider the set of suffixes S = {i O(n/b(m) is growing with n. For a suffix 8, let G(s) = {(z, i) : [n i 11, (na,g(s, 1, 1, 1) 1} be the set of integer indeeinddxxxxxx pairs that g attends to given suffix
0 < < n/(Sb())) Note than since b(n) o(n), |S|
1. Initialize p = =[(n²/ /22//33))) (31)) and I = {1}
We will use [n2 nn233] as filler: placing it in p here ensures it does not match any prefix integen.
2. For s S:
(a) While IP* n G(s)] b(n):
i. If there exists some (I, E znz x ([n - 1)\ ([--1]/]
for which (1) (x, E G(s) and
(2) x + y + s' #,o for all s E S and all (g. Pt: add (a, i) P and add
to I
18

---

Add a masking integer to the prefix. but only allow masking integers that do not form a match with existing masking integers and any suffix.
ii. Else: break out of the while loop
If there are no integers that wants to attend to (among those not forming matches with existing masking integers), then we are done with this suffix.
After the procedure, P contains at most b(n)]S] + +15 n/8 + 1 occupied indices. Let Z be the set of values in P*. with |Z| I n/8 + 1. Moreover, we have ensured that no pair of integers in P can form a match with any suffix integer s, since we only add to Pa if for every y in P and E S, a + y + 8 # O. Lastly, for some suffix 8, we were unable to saturate attention and hit the else in 2(a)ii, then no other integers we add to a prefix can be attended to, since we will only be adding integers to prefixes that do not form matches with any integer P and any suffix (and therefore were already checked for attention in 2(a)i).
Now, for each s E S, we find some I, and ya using Lemma | such that H. + Us + s=s=,, ,,, 0, but I, and y/ do not form matches with any other 2 E Z (recall that we have initialized Z to contain all values in P*). Add each x, and ys to Z before the next application of Lemma [ to ensure that we do not create any matches across z-y pairs. After doing this for each s E S. the final size of Z is < n/8 + 1 + n/ (4b(n)) I 3n/8- + 1, so the size limit on Z required by Lemmal I namely |Z| S vm/2 = n/2,, is always satisfied (since we picked n > 10, n/2 > 3n/8 + 1). Let P P= (= us) )ES be the x-y pairs we find using this procedure.
For every subset R S P. construct a prefix of length n - by first filling in all of the masking integers in lx (filling most n/8
positions) and then adding in the x and y values in R in arbitrary indices (filling at most 2|5] = r2/(4b) additional positions). Fill the remaining indices with [n3/3], which cannot form a match with itself and any suffix integer (since the suffix integers are at most n (4)())))), and which we already ensured cannot form a match with any integer in P or p' by placing it in Z. This gives us 2| distinct prefixes, each of which has matches with distinct set of suffixes. That is, for any two prefixes p1 * p2. there exists some suffix integer where pıs and p2s have opposite answers to MATCH3,, since there is some pair (æ,, Vs) (Z,) in one prefix, but not the other, which forms a match with s, while no other pair of integers forms a match with s. But with prefix bandwidth ((n/b(n)) = o([S)), there is some prefix oracle collision (as there are 20(181) distinct outputs of f, too few for the 21 distinct prefixes). Moreover, these colliding prefixes indistinguishable to attention for all suffixes, since we have ensured that for every suffix, attention can be saturated by integers in pr, which are identical across all prefixes. Therefore the BAPO fails to solve the problem.
Proof of Theorem 6 For the (2k, -B-PO the prefix oracle transmits two bit-strings of length k one indicating which elements of Σ appear exactly once in the prefix and one indicating which elements of Σ appear in the prefix one or more times. The suffix oracle outputs (a) any element that appears exactly once in the prefix but not in the suffix, which it finds from the first bit-string; (b) any element that appears exactly once in the suffix but not in the prefix, which it can find from the second bit-string; or (c) 0 otherwise. This allows the suffix oracle to correctly solve UNIQUE [
For the lower bound, suppose for contradiction that (S,g, h) is an (o(k//(k))) b(k)) solving UNIQUE. We will first construct a set of partial prefixes P for which the attention mechanism cannot distinguish all following suffixes. This leads to pair of fooling prefixes with different answers that the BAPO cannot distinguish.
Fix an arbitrary order over the symbols in = (E Ex). For any A C E, let cat(A) denote the string consisting of each token Σ, E A concatenated in order. Let = 4b))).. We will construct collection of k//b' suffixes (for convenience, assume k/b/ is an integer; otherwise, the construction would involve ceilings and floors, but this this would not affect the argument): let o, = cat(E) \ //// k/t'
As Figure 7 shows, the partial suffix d; is missing the ith block of b' contiguous tokens in E, so each full suffix s; = oj0; has length 2(k - b') and |S| k/U by construction. Note that we have duplicated each to ensure that no suffix token is unique.
(Eo(s- 1)) and S )
'Additionally, there is clever (flog, 1=1 0)- -APO for the special case of UNIQUE where every element appears an even number of times, except a single unique item: with this restriction, taking the bit-wise exclusive over binary encodings of the tokens solves the problem- but this fails in general.
19

---

block
block (omitted)
block k/U
Σ1
Σ2
Ey
11-1044 De-1)/42
Egs
EE-8+1
2k-
Σ
Figure 7: Constructing oi by leaving out the ith block from the vocabulary 2, leaving k b' tokens.
Now, perform the usual overloading procedure start building up prefixes of length that saturate the attention function for every suffix. Let G(s) {(2, i) E E x [k] I(8 k, = 1}. Perform the following procedure to construct partial prefix P 6, I
Initialize P for E S do while P n G()) < b(k) do if 3 E E, i [k] \ such that () E G(s) then
Add (x, i) P"; add to
else
break
This procedure results in at most b(k)]s] = b(k) b(k) Ib(R] = k/4 positions in P being filled with masking symbols. Let Z be the set of unique symbols in P", with |Z| S |P*| < k/4. To ensure none of these are unique, fill another I k/4 arbitrary indices in P with an additional copy of each symbol in Z. As in the previous proofs, attention has now been rendered useless for every suffix, regardless of what additional symbols we add in remaining prefix indices. Consider the blocks we used to construct the suffixes, namely (E +)+ 16' j= for E [k/b]] (Figure 7). It must be the case that more than half of the blocks have element not in Z (suppose this was not the case and > /S//2 blocks have all of their elements Z, then /2| > // find a collection of tokens Y {y1,- - // such that each y, is in different block and Y n Z 0, as well as one extra filler token yo from yet another different block.
k/2, contradicting that
|Z| < k/4). ). Thus,
each subset R C Y. construct a prefix Pæ by starting with P*, placing each y R an arbitrary unfilled index (so that the prefix now has < k/2 + SS//2 filled indices) and filling the remaining indices with copies of yoo This gives us 2|51/2 bandwidth, we only have 20(k/b(k)) distinct outputs of f. so there are two prefixes pR and prv that collide. These two prefixes have different subsets R and R' of Y values, so there some y, one prefix but not the other (say y E R, y1 R.). Consider the suffix s-j that is missing the block of tokens to which y/ belongs.
2 distinct prefixes. With o(k/b(k)) prefix
We observe that:
8- has no unique tokens due to its construction
, 8-1] has no unique tokens, since all of its Y values in the prefix appear in the suffix due to the fact that every element of Y comes from different suffix block. Thus, every element of Y except ys appears in s-1-
[pR: s-i] only has yi as unique token, since (a) all other tokens in Y have copy in the suffix due the above fact, (b) the masking and filler tokens in the prefix are all duplicated at least twice
Since the BAPO can observe the same attention set G' given both of these strings and receives the same output of f from the two prefixes, it gets one of these instances wrong for some G.
Proof of Theorem 7 For the (k: -A-PO the prefix oracle sends a bit-string denoting all elements of Σ appearing in but not (as far as it can tell). The suffix oracle can then remove all elements of in the suffix and compute an answer.
For the lower bound, as usual, suppose for contradiction that (S.g. h) is an (o(k/ ((k))/())).oooom b(k))- BAPO solving SETDIFF. We will use the similar collection cmitted-block suffixes as we did for UNIQUE As we did in that proof, order the elements of Σ and define cat( Let b' = b(k)/4 /4. We
20

---

will construct a collection of k/b suffixes (again assuming for convenience that k/b is an integer): 1k/6' (E and = ( (recall Figure note that in contrast with UNIQUE, there is no need to duplicate the suffixes).
let o; = cat(E) \
Now, we perform the usual overloading procedure start building up prefixes of length 3k + that saturate the attention function for every suffix. The prefixes we build up will be of the form C1 c1...cx/d1 ... d2g. That is, the prefix-sufiix split occurs somewhere in the middle of the d input to SETDIFF. Let ((r) {(x, i) E Σ x [3k + 1] g(a, kt, i) = 1}. Perform the following procedure to construct a partial prefi P*, which we initialize to already contain the divider token
Initialize P + {() k + 1)). I + { + +
for S do while PM n (()) | < b(k) do
a E, i [3k + 1] 7 such that (Ir E G(o) then
Add (z, i) to P"; add to I
else
break
A = k/4 positions in P being filled This procedure results in at most b(k)s) = (()) = b(k) 161k)
with symbols that saturate g. Let Z be the set of unique symbols in P", with |Z] P S k/ /4. For each symbol in Z. place another copy of it in P on the opposite side of the divider as its first copy. This ensures that symbols in Z can be SETDIFF answers, while leaving at least 3k/4 open positions in P before the divider and more than & open positions after the divider.
Now, consider the blocks we used to construct the suffixes, namely {) for i E [k/6]] (Figure 7. Just as before, it must be the case that more than half of the blocks have element not in Z. Thus, we can find a collection of tokens Y = {y1..... M/sl/2) such that each yi is in a different block and Y Z 0, as well as one extra filler token yo from yet another different block. Let X Σ \ (Z U Y). Place every E X in unfilled index of p after the divider (i.e., in the d portion) and fill all remaining empty spots of p after the divider with the filler you
For each subset R C Y, construct a prefix Pn by starting with P* (which is now full after the divider, but has at least 3k/ /4 open positions before the divider), placing each r E an arbitrary unfilled index before the divider, and then filling in all remaining indices with yo- As before, this gives us 2|S1/2 2²/(25') distinct prefixes. With prefix bandwidth o(k//(k))), we only have 20(k/b(k) distinct outputs of f, so there are two prefixes which have identical f outputs, call them pn and pr=- These contain different sets R and R' of Y values; thus, there is some yi E Y in one prefix but not the other. Suppose without loss of generality that y E R. y/4 & H.. Consider the suffix o; that is missing the block of tokens to which yi belongs. Notice that:
PRo; has only single SETDUFF answer, which is ye we ensured that every Y element only appears in a prefix before the divider, and yi does not appear in o, Every other symbol in the missing block of o; is in pR after the divider by construction, and thus is not valid answer.
a has SEFDIFF answer 0: the only symbol not appearing after the divider in pr is Vi. which is not before the divider.
Thus these instances have different SETDIFF answers, but they are indistinguishable to the BAPO (for some adversarially chosen G) due to the saturation of attention and the collision. LI
Proof of Theorem 8 Let M (Q, (0, 1),A, 6, go, Inccopt 4rejoss) be Turing machine deciding L using space snn).
A slight wrinkle arises due to the fact that BAPOs cannot attend to the last instance of token, which would enable the efficient "tape diff Turing machine simulation used by Merrill and Sabharwal (24]. As such, our construction requires fixed maximum tape size, which means different BAPO- CoTs are needed for larger problem instances-bv but crucially, their bandwidths are identical. This is analogous to the requirement of Merrill and Sabharwal (24) that the precision of the transformer grows with the problem instance (although in our case, the scaling increases the number of chain- of of-thought steps).
21

---

D = L
Vj-2
q'
yj-1
X
yj+2
21-2
Y/j
X
Vj+2
j j-2
2 j
j
j+1
j+2
D = R
yj
Vj-1
X
q'
Vj+2
Figure 8: The tape head contents around the previous tape head's chunk offset after a step of the Turing machine M. All indices before j 1 and after j + 1 are identical in the new chunk. For simplicity, the indices are shown relative to the start of the chunk.
Given n, we will construct a (2,3) 3----BBOO that simulates M on inputs of size at most n. Let T= T=EUAUQU(= J be the token set for the BAPO-COT. The BAPO-CoT will simulate M by writing out the contents of the tape at each step of M, along with the current state, which will be written to the left of the tape cell where the tape head is currently positioned. Since only s(n) tape cells are required, the BAPO-CoT will simulate a tape with exactly s(n) cells. So, on input .1... the first state the BAPO-COT will write out is 90 ... Fn ..... with total length c s(n) + 1, which we will call the chunk size. Let chunk(i) = lí/c]. We use m to denote the current length of the BAPO-CoT's input (with
at the first step) and y 01..... Um the current BAPO-CoT input itself (with y1 Vn = x).
The prefix oracle f is defined follows:
00 the last symbol of y1 ... yk is some g E Q
the symbol to the right of the last E Q in y1 yk is 10 if the symbol to the right of the last E Q in 1/1 ... yv is
f(y.... =
11
otherwise (y/1 ... yk contains symbols in Q: every q is followed by 0 1).
Thanks to this the suffix oracle always knows the symbol to the right of the state from the previous chunk. The attention function is defined as follows:
if i =
if n ni=n-c-1
g ... Mm. k, Vi, i)
chunk(i) = chunk(m) - 1 and yı E Q
otherwise
Thanks to this g. the suffix oracle always knows (a) the symbol at the current chunk offset index in the previous chunk, (b) the symbol before the one from (a), and (c) the state the previous chunk and its chunk offset index (i.e., the tape head position). If any of these positions are in the suffix, they are directly observed by the suffix oracle and they are in the prefix, then they are contained in the attended set G.
The suffix oracle h performs the following procedure given f() ... yk), G, ki and yk+1 ... Pm
1. If chunk(m) = 0, return
2. If chunk(m) = 1:
(a) If m = c 1: return
(b) Else: return Vm-c-1 (1m-a-1 is either in the suffix or in G)
3. Else: let i = m mod Let j be the head position in the previous chunk and let g be the state in the previous chunk. Note that q, j. Vm-cx and 3m-c-1 are all known to h, since they are either included in the suffix in G (j is computable from the positional encoding q). Moreover, À (abuunk(m-c)---j--
(the symbol under the tape head in the previous chunk) is either in the suffix or can be inferred given the suffix and f(y ... yz). The suffix oracle can thus compute the step of the Turing machine 8(g, A) = (q' D). where E Q is the next state, X' is the symbol written to the tape, and E (T., R} is the direction the tape head moves.
22

---

First, we check to see if M has halted. If q' qaceepi if Im is not 1. return 1, otherwise return C. If q' Preject if ym not O, return O, otherwise return D. This ensures we output the answer and then terminate. Otherwise, we proceed to simulate M. To output the next symbol given a step of the Turing machine M applied to the previous chunk (see Figure R):
if D L, return d': if D = R. return ym-c (b) Else if j: if D = L, return 9m-e-11 if D = R, return X
(a) If
(c) Else if i = j 1: if D L. return X; D R, return o'
(d) Else: return Dm--c
This procedure results in the updated tape of M being written out symbol-by-symen into the next chunk. Since M decides I, it will eventually halt, at which point the above BAPO-CoT outputs the answer (0 or 1) and then outputs D terminate.
C BAPO generalizations
We consider three generalizations of our model, score-BAPO, multi-layer BAPO, and full-attention BAPO. We show that these variants (even in combination) do not affect the BAPO-hardness of REACHABILITY, MAJORITY, or MATCH3,. However, they do enable solving the (multi-hop) in- duction heads task, which appears hard under the original BAPO definition. This suggests multiple degrees of hardness, with our set of three BAPO-hard tasks appearing fundamentally hard even as we make the model align with more details of the transformer architecture.
C.1 Score-BAPO
A score- score-BAPO has an attention function that outputs a real number in [0, 1] rather than only 0 or 1. The attended set G' then consists of the (up to) b tokens with highest non-zero attention scores (if there are multiple such sets, the score-BAPO must be robust to an arbitrary attended set, as with the original BAPO). This is strict generalization, as a score attention function simulate binary one by outputting scores 0 or 1.
Definition 11. An (a, besss))e--BAPP-S.
is defined by a prefix oracle : + {0. 10. an
attention function g Σ" N x E x N 7 [0. 1]. and a suffix oracle h {0, x O x N)¹ Σx X N
+ E. An (a, scoor--POO solves a computational problem if h([() ... Fx), G, TR+1 T.. k) = p(r) ....))) for all k < n and all G
Ini arg maxsC ((..))aikk... Σ (x. 9s. where 9i ... 22,
|5|56
A constant-bandwii score-BAPO can solve some problems that otherwise appear to be BAPO-E- hard possibly even BAPO-hard. Two problems that score-BAPO can solve that seem hard for BAPOs are MAX and RIGHTMOST (and their symmetric variants), defined as follows.
Definition 12. MAX: Z; - Zm is the problem of finding the maximum of list of integers between 0 and m - 1. MIN is defined analogously.
Definition 13. RIGHTMOST: Σ. x Σ + [- is the problem of finding the index of the rightmost instance of a token in a list, or -1 if the item is not in the list. The token to search for is provided in the input after the list. That is, RIGHTMOST(2) ... In 11, (n) max([-1)
[n 11-11 24 ). LEFTMOST is defined analogously.
Proposition There are (0, 1)-sccor--BAOOS for MAX, MIN, LEFTMOST, and RIGHTMOST.
Proof. For MAX, the attention function Q(Ix+1....2 In. k,, = Iz/m ensures G contains the largest element in the prefix (or G 0 if the prefix is all Os), which h can in combi- nation with the suffix to identify the largest element of the sequence. The attention function g(xx+1 ... Fn, k F4, i) (m s;)/m performs the same function for MIN. For RIGHTMOST, the attention function is:
i/k if = Fn
g(xx+1 Iny k. 11, =
(0
otherwise
23

---

This ensures G contains the rightmost occurrence of In in the prefix (or G = 0 if nn does not occur in the prefix), which, combined with the suffix, allows h to solve the problem. Using (k: + 1) k instead of i/k provides a solution to LEFTMOST.
C.2 Multi-layer BAPO
A d-layer BAPO has constant number of attention functions 91..... .d that operate sequentially, with each having access to the attended tokens from the previous layer. The suffix oracle h then solves the problem using the last attended set Gd- This allows d-layer BAPO to perform multi-hop tasks as a multi-layer transformer would. The original BAPO model is just a 1-layer BAPO, and a BAPO with any number of layers can simulate one with fewer layers by having some initial number of attention functions act as no-ops. Note that the total number of attended tokens / has access to in an (a, b) d-layer BAPO is bd, still constant when b O(1) and d 0(1).
Definition 14. An (a, d-layer BAPO is defined by a prefix oracle f Σ- + {0, 13" d attention x U - Ny {0,1] for i 1, ....., d, and suffix oracle - (Σ x N)* x Σ x + Σ. Given an instance Ii ... Un Σn of computational
functions 9i Σ" x N E N
h: {0, 1) 0 problem p Σ" + Σ and a split index k < an atlended set sequence Gi...., Ga is some SSis k. 91 (#x+11...... k;, Z4. 0) = 1} k, 9)+1 ....1...0
sequence of sets where G1 C G1 = {xx,1)
.ett1..IInhhh In,k, 24, G,) = 1}. with each [GyL= = (b, |G,]] for {(T,,) I....,, d An (a. b)-d-lyyer BAPO solves a computational problem p: Σ" + if h(f(((((..) (k)...Tkk Ga, Fx41 ... Fn, p(1111111))) ... Ina) for all k < n and all attended set sequences G1, GI,...,GA Ga.
and Gj+1 S G/41
1 <
C.3 Full-attention BAPO
A full-attention BAPO is a minor variant where the attention function 9 may attend to all to- kens in the input, not just those in the prefix. That is, we now use G {(z,,)) 1 S S n. g[ Ix k Iz. i) = 1} (rather than 1 S i S k), with no other changes. A full-attention BAPO can act just like standard BAPO by having ( ......... .n,, k Fy i) This modification provides no increase in expressive power, as h has access to all suffix tokens anyway, and a pure convenience measure for combining with multi-layer BAPO.
whenever > k.
C.4 Combining variants to solve the induction heads task
These extensions can be combined. For instance, we can define a fulllaettull score- -BPP- where each of d attention functions outputs score over all input tokens. We show that this BAPO variant can solve the multi-hop induction heads task (37). while still leaving REACHABILITY, MA- JORITY, and MATCH3,, BAPO-hard. (This also implies that each of the three variants alone leaves these problems hard, as the capabilities enabled by any of the variants can be ignored.) The require- ment of a second layer of processing for one-hop induction heads is analogous to known results that the problem is efficiently solvable by two-layer but not one-layer transformers 7 36).
Definition 15. d-HOP INDUCTION HEADS: Σ' + EUUL {r} is the problem of iteratively finding the token that follows the rightmost previous occurrence of the last token. Formally, the solution on input Φ is given by Tn)pg(m) if hop, (z) * 0 clse 1. where
hop, (x) = max ( (0) [j E [m] xz-1 = = hop (z) max((0) U E (x)] 1z-1 Shop,(x)))
(for i 1,..., 1)
Theorem 9. For any d 2 1, there is a (0, 2d- full-ateenio score-BAPO for d-HoP INDUC- TION HEADS.
Proof. The idea behind the construction is that the 2d attention functions alternate between attending to the rightmost instance of the current token being searched for (i.e., attending the rightmost previous instance of the token at index hop, 1) and attending to the token to the right of that rightmsst instance (i.e., attending to the index hop, (r)).
More precisely, each gj is defined as follows:
24

---

1. For j = 1, the first attention layer finds the rightmost previous occurrence of the last token, using:
fi/m if n and x; Zin
91 (1 ... Fnz : le Iz. 2.
0
otherwise
This ensures G1 contains the rightmost instance of the token Zn (or (1 I. does not appear earlier in the input). Note that since this is a full- aull-attention BAPO, G contains this rightmost instance even if appears in the suffix. (How convenient!) Using induction heads notation, G contains the token at index hop, (2).... F.. - 1 (or G₁ = @ if hop, (I) (II... z,) 1).
2. For even j. we have the invariant that Gý-1 (provided to gj) contains the rightmost instance of the current token being searched for (or 0 no instance of the token was found). (When defining 9j for larger odd j, we will maintain this invariant.) We then define 9j as follows:
{
if G ((1e, Q) and i +++1 otherwise
99 (x(4+1 .. Zn. k 24, G3-1)
This ensures Gj contains the token appearing to the right of the one identified in the previous layer (or 0 if the induction heads chain has been broken). Using the notation of induction heads, G5 contains the token at index /0 .... (or Gj = 0 if //2 (x) 1).
3. For odd j 1, the above definition ensures Gÿ-1 contains the token index hop
(or is M). The next attention function 9j thus needs to look for the rightmosteerllie earlier occurrence of that token, which is accomplished by:
rightmost
(f(xx+1 ... Eng k Fz, i, = {
fi/n G ( (),, < l, and 2; = De
(o
otherwise
This ensures G5 contains the token at index hop ..p - 1, or is empty no such token exists (or G5-1 was empty).
As each layer of attention maintains the needed invariants for the next layer, an inductive argument shows that G24 contains the token index hop,(11 ... ..,) (or is empty if the chain was broken at any point). Thus h can return this token (or L) and solve d-Hop INDUCTION HEADS.
C.5 Our BAPO-hardness proofs are robust to these variants
Given these variants and their ability to solve problems that appear difficult for the standard BAPO model, one question is whether the model is too powerful and trivializes our hardness results. How- ever, show that REACHABILITY, MAJORITY, and MATCH3, remain hard for d-layer full- attention score-BAPO with constant d. The proof technique we use for BAPO-hardness extends naturally to these variants, so any problem shown be BAPO-hard using our approach is also hard under these variants.
Theorem 10. For any d = 0(1), there no constant-bandwidh d-layer full-attention -AAP for REACHABILITY, MAJORITY, or MATCH3,.
Proof. The proof structure and constructions remain the same as in Theorems to we only need to change the way masking tokens are selected to account for the new structure of the attention functions (and we will need to use more masking tokens as the effective number of tokens attended to is bd rather than 6, but this is only constant factor). The idea is that when placing masking tokens in the shared prefixes, we need to iterate through each attention function, masking the attention of each one in turn. In this iterative process, we the constructed attended token set containing only masked tokens as the input to the next attention function. Additionally, at each step, we select the masking tokens that have the b highest attention scores (rather than an arbitrary set of attended tokens, as we did in the binary attention case). The fact that suffix tokens may be attended to only helps, as this can never help h distinguish between fooling instances (as they share the same suffix).
We provide the updated prefix construction for REACHABILITY as an example (the other two are analogous transformations of the original proofs). Refer to the proof of Theorem 3 for full notation.
25

---

We need few additional definitions for the proof extension. Let sr,t,, PP) be the 8th largest attention score that 9- outputs on any edge in P (positioned at their canonical indices given by I())) or on the suffix tokens 8; and 1j- If there are fewer than b candidate tokens between P and the suffix, then (r, (r, sit;, P*) = O. Given a non-target node u, let (ex P") be the set of nodes in the layer to the right of u that have in-degree 0 in P".
1. Initialize P to have the same set of nodes as P. Initialize S to be the set of all and Mij nodes, which will store the current set of nodes that still need an outgoing edge.
2. For each pair (i.j) [p] lp]:
(a) Initialize Go = 0
(b) r l....d
i. While add the maximizing edge (u, v) to P and remove u from S.
(8 m. (u, u), Gr-1, > (r,8,, PT):
Ensure the top b still-feasible edges that have highest attention scores under 9r are in P": thus, no edge we add later will have a higher attention score for gr on suffix s,tz-
ii Let G,, be set of b tokens in P (and 8,4y, since we are using full attention) with highest score under Gr on suffix s,tj. If there are fewer than such tokens with non-zero score, take all tokens with non-zero score.
This G+ is one possible attended set at this step, regardless of how the prefix is completed (or, without attention score ties, the unique attended set), since we have ensured the ggghest-scoring feasible edges are added to P For adding masking tokens in the next attention layer, will assume this is the attended set.
3. Let E" be the set of edges in P at this point in the algorithm. These will be shared among all prefixes to saturate attention. To complete the paths in P arbitrarily, connect each node with out-degree 0 (that is not f node) to the first node with in-degree in the next layer.
The total number of edges we add to P is at most bdp² (compared to bp² in the original construc- tion). Thus, as long as bd 0mm2)2/s) (which is certainly true with b = O(1) and d = O(1)), we have enough edges in the graph mask attention for every layer and for every suffix. Given these masking edges, we have found some sequence of attended sets GI...., GJ (those used in the construction) for every suffix that only contain tokens shared among all prefixes, so the rest of the proof remains the same. On a pair of fooling instances as described in the original proof, the suffix oracle sees the same final attended set Ga regardless of the prefix, the output of S, and the same suffix-thus making a mistake.
The same approach (picking the masking tokens with the b highest values of Jr for each = .d) allows us to generalize the BAPO-hardness proofs of MAJORITY and MATCH3, with only additional constant factor d of masking tokens. Since this only requires constant factor of additional masking tokens, any BAPO-hardia proof using the same structure can be extended to d-layer full-attention wore-BBAO.
D Experiments
D.I Implementation Details
All models were forced to output a pre-set JSON schema, shown in the tables below, The model versions and API settings were as follows:
Family
Model
Version Specifier
Temperature
Other Params
GPT
4o
gpt-4o-2024-11-20
0
4o mini
gpt-4o-mini-222--0--1
26

---

03
03-2025-04-16
n/a
{effort: medium)
Claude
3.5 Sonnet
claude-3-5-oomme--222411
3.5 Haiku
cleude------aaaix-22221222
0
Gemini
1.5 Pro
gemini-1..5prro-022
0
1.5 Flash
gemini-1.5-flash-002
2.5 Flash
The experiments took < 1 day and ~$400 of API credits to (S93 of which were for o3 alone), with preliminary experiments taking an additional ~$15 of API credits.
D.1.1
Base Experiments
Below the instructions used for each task, illustrated using example instance:
Experiment
Example Prompt
Example Output
INDEX
Output the element at the specified index (starting at of the list: List: [["index";
{"el ement_value": 117]
0, "value": 117). ("index": 1,
"value": 30), {"index": 2,
"value": 169). ("index": 3,
"value": 113), ("index": 4,
"value" 52), ("index": 5,
"value": 168]] Index:
EQUALITY
Output true if the left and
("equals": false)
right lists are identical:
Left: [1, 1, 0, 1, 0, 1, 1,
O, 1] Right: [o, 1, 0, 1, o,
1, 1, 0, 1, 1]
MATCH2
You given list of numbers and a number x. Determine whether list[i] + x for some i. List: [-300, 62, 144, -490, 469] x: -144
['found i": true)
REACHABILITY
You are given an directed graph with nodes as list of edges (i, j). An edge (i,j) means that node points to j. The edges in G are: [[5, 4], [2, 0], [4, 1], [3, 2]] Is there a path from node to node 1? Output true if the majority of elements of this list are 1,
{"path exists" true)
MAJORITY
("majority 1s": true)
else false: [o, 1, 0, 0, 1, 1,
1]
MATCH3
You are given a list of numbers and number Determine whether list[i] + [js + x
"'found_i.and.j""
true)
= for some i, j. List: [508,
567, -178, 382, -240] x: -890
27

---

DISIOINTNESS
These left and right lists represent sets using binary indicators for each item.
{"is disjoint"; true)
Output true if these sets are disjoint and false if they have a non-empty intersection. That is, output true if and only if there is no index where both lists contain 1. Left: [0, 1, 1, 1, 0, 1] Right: [o, 0, 0, o, 1, 0]
INTDISIOINTNESS
Output true if left and right lists disjoint (share elements) and false otherwise: Left: [73, 290, 133, 342, 142,
{"is disjoint": false)
279] Right: [236, 16, 306, 144, 279, 242]
UNIQUE
Output the element in the list that occurs only once: [4, 4, 4, 4, 6]
{ ("unique": 6)
SETDIFF
You are given two sets numbers A and B. Output the element set that is not in set B. If there is no such element, output -1. Set A: [3, 5] Set B: [5, 2, 3]
("element": -1}
To generate the problem instances, we used the procedures below. We use grid of n {6, 50, 100, 200} but resulting list lengths might deviate slightly if problem requires odd num- bers. We generated an equal number and positive and negative instances where applicable.
INDEX: For each run, sample a permutation π of {O...., 199]; set x = T Tim-1 choose Unif(0,
EQUALITY: Sample E {0, 13" uniformly, Let x for positives. For negatives, choose + j with v; f J,, swap Ve V/-
* MATCH2: Generate permutation π ~ Perm(0, 999). Set x Winz- Then, to generate
Poositives: inject =x, into - a random position
Negatives: ensure rr, & xin by replacing with random element from æ.
REACHABILITY: Construct A: = 2 node-disjoint paths of length & = n/k-1.
1. Let graph G union paths, map node names to integers via random bijection a. Choose (s, t) such that:
Positives: s, on same path = path exists Negatives: 8, on different paths + no path
MAJORITY: Generate (0, 1 such that majority bit occurs [(n 1)/2] times.
Shuffle x.
MATCH3: Sample Perm(- -200, 1000). Reject if Mi.m has triplet that satisfies I,t +., 0 (negative). For positives, generate negative instance and then select 3 j. set Fn (x, 2z)).
DISJOINTNESS: Sample (z,, yi) uniformly from {(0, (1,00)
Possitive:: already disjoint
Negaatives: pick j. set 0 b; 1
INTDISIOINTNESS: This is slightly different from DISJOINTNESS to avoid shortcuts from varying set sizes. Generate permutation æ Perm(0,339)) Set J Ti:n22 and nn/2nn For negatives, set z y₁ for random index j.
28

---

1001
INDX
EquaciTY
Marcn2
model
raiorinng tokens
102
1000
100
Maxweryy
Marcol
rensening tokcnns
10k-
100
Figure 9: Number of reasoning tokens used by o3 and Gemini 2.5 Flash for each problem. The models perform well on BAPO-hare tasks in line with our BAPO-CoT result, but they use thousands or even tens of thousands of CoT tokens to do so.
UNIQUE: Generate permutation Perm(0, 1). Then, place unique element and fill remaining with elements of frequency 2 2 by drawing from iim/44
SIFFIFF: Generate permutation π ~ Perm(0, 1). Sample unique element u. Split into parts and recombine:
A= S U (u), Bpos = SUV fu). Buey = SUVU
where S = shared, V = unique-to-Be v randomly sampled replacement element from S.
S +1
D.1.2 CoT Experiments
For the chain of thought variants, we pre-pended the following instructions:
Think step by step the CoT, but stay under 250 words.
The output JSON object then contained a cot field before the actual answer, e.g.,
{"cot": "To determine if there exist indices i and ...", "found_i_and_j" true}
experiments with two reasoning models that also supported structured outputs, OpenAl's o3 and Google's Gemini Flash 2.5. Model version and parameters can be found above. Figure shows the number of reasoning tokens the models used.
Additionally,
D.1.3 Real-World Experiments
Experiment
Example Prompt
Example Output
29

---

VARIABLETRACKING
In the Python code below, "a" the end of execution?
{"is equal": true}
" python
x6 = "a"
x4 "b"
x0 = x6
x2 x4
x3 = x0
x8 x2
x9 = x3
x7 = x3
x1 x8
x5 = x8
MAJORITYREVIRE
Output true if the majority of the following reviews is positive, else false.
i"majority. true]
[{ "id": 0, "review": "I loved the grand entrance hall with two impressive chandeliers and player grand piano. I took advantage of the exercise room basement and loved getting a coffee from the bar to take up to my room. The cleaning staff were particularly pleasant, greeting me every time we happened to pass. The lift [...]
FINDNEGATIVEREVIEE
Return the id of the most negative review.
("most.negative": 8)
[ "id": 0, "review": "Lovely hotel and great location.
recommend this hotel, the location is great for tourist attractions and the airport. Very friendly staff and worth every penny." " "id": 1, "review": "We stayed at the Boston Park Plaza Hotel in April and couldn't have been happier. The hotel is centrally located near the Public Gardens, Theater District and Boston Commons which [...]
Dataset Processing Details, We used hotel reviews from the SPACE datase 2 rating 5f get positive label, reviews with rating of get negative label to ensure clear separa-
Reviews with
Available http://tttbbb.cccsssttagll///// under MIT License.
30

---

tion between classes. We annotate the resulting reviews with GPT4,1 to check for consisteney and only keep the ones where the original label agrees with the LLM annotation. Finally, we only keep hotels with at least 101 positive and 53 negative labels to make sure we have a large enough set to subsample from.
VARIABLETRACKINGG Follow the same process as for REACHABILITY construct graph with ào = paths. Let these two paths be and p'.
Then choose j with j < and insert a cross path edge from Pj - p/, erasing P/-1 -> p/--
Map nodes to variable names 20, #1,... via random bijection and initialize all nodes with no incoming edges to a letter from the alphabet.
Choose and as with REACHABILITY
Finally, generate assignment statements via sampling random topological ordering of the overall graph.
For each label y E {True, False), sample n// + reviews of label y, and n/2 of the opposite label, where 3 is slack variable to help reduce any remaining noise in the reviews. Shuffle the combined list of reviews.
MAJORITY REVIEW:
FINDNEGATIVEREVIIEE We iterate through hotels in round-robin fashion. Sample n positive and 1 negative review to generate data for one task instance. Shuffle those in random order.
D.2 Additional Results
DESOININ
model
0.8-
GPT-oo
securacy
GPT-4o mini
0.0
Claude Sounet
0.4
Clank 3.5 Hakka
0.2
Genini 1.5 Flaah
50
100
150
700
90
100
150
200
Figure 10: Additional results on BAPO-easy problems. INTDISJOINTNESS is variant of DIS- JOINTNESS where sets are represented by the indices of elements they contain instead of binary vectors to show that positional encodings rather than for the poor performance on this task.
are likely to be responsible
DiscesTness (wr CoT)
INDrSsoNNTNS (wi CoT)
model
0.8-
GPT-4o
aocuracy
GPT-4e mini
0.6
0.4-
Claude Haka
0.2
Genini 1.5 Flash
0
50
100
150
200
50
100
150
200
Figure 11: Adding CoT to BAPO-easy problems provides boost larger models DISJOINT- NESS, especially Gemini 1.5 Pro, while performance remains high on the other problems.
31

---

UNaqUr
model
GPT40
accurtt
GPT-4o mini
0.-
0.4
Chude 3.5 Holks
Genini 1.5
0.2
Gemmi 1.5 Plash
200
410
600
800 1000
200
400 610
500
1000
Figure 12: The hardness of UNIQUE and SETDIFF scales with the vocabulary size which we to increase via input length n here. Drops still occur, but appear to be less pronounced, perhaps because pre-trained LLMs have fixed token representations and scaling input length is only proxy for increased vocabulary size.
Unaqus (wi CoT)
Se (wi CoT)
model
GPT-to
accuncy
4PT40
Claude 3.5 Sounet
Halks
Gemini 1.5 Pro
Figure 13: Adding CoT to BAPO-E-hard problems does not result in substantial changes. We conjecture that this is again due to the static nature of the underlying vocabulary representations.
32

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly state in the abstract and introduction what our hypotheses are, what our theoretical results state, and what our experiments indicate.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
Section 6 discusses the limitations of our work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificatton, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [es]]
33

---

Justification:
All results are stated precisely and have proofs in Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Appendix D.I includes experimental details, including exact models, prompts, and data generation procedures.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data also be provided via
often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models. it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
34

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: All of code is available httpss:/ coom/iccrosoff/bap The code includes instructions for downloading public data and for running the experi- ments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (nttps://nips.co
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
//nips.co.
ississsionn coemisssoonool.. onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer:
[Yes]
Justification:
All details are available in Appendix D.I
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: As described in Section 4 all of our plots show 95% t-test confidence inter- vals across n 100 runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
35

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix D.I states that the experiments reproducible in under day with ~$400 of API credits, with preliminary experiments taking an additional ~S150 of
API credits.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics /tttps://neurips: Bttnghtttt//////poss....///////t
Answer: [Yes]
Justification:
We see no potential for societal harm or other ethical concerns in this research.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: As our work proposes and analyzes a mathematical model LLM capability, broader societal impact.
Guidelines:
36

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negatíve societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper does not provide data or models (in the sense an LLM; we do introduce mathematical model).
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite authors of the SPACE dataset, link to the data source, and explicitly mention the MIT License under which is released in Appendix D.I.3
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
37

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the pack- age should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification: Our code and accompanying documentation are available at https:/ // gi github.cco/miccrrree. ctt.://ooo/mmccoooooooo/o/////
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not concern research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, cura- tion, or other labor should paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not concern research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
38

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: LLMs are our object of study, but they are not a part of our research method- ology.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
39


Reviews:
[{"review_id": "ogF8uzHBEl", "reviewer": "Reviewer_21nW", "summary": "This work introduces BAPO, a framework to reason about when LLMs can solve decision problems. BAPO is centered around communication bandwidth which is used to differentiate between BAPO easy and hard problems. The BAPO framework is able to predict if Transformers will successfully solve problems based on if they require constant or super-constant bandwidths.", "questions": "An experiment that I think would be very interesting: Consider the problem of finding the kth larger element in an array and the problem of sorting. If I understand correctly, the former is BAPO-easy (for constant k) while the latter if BAPO-hard. How well do you perform on these problems for different values of k, and different sequence lengths. Do the LLMs successfully solve this problem for different values of k?", "limitations": "Yes, the authors have clearly listed out assumptions but could expand a bit more on how these assumptions directly translate to limitations on their theory.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths.** I find the framework to be simple yet elegant for predicting how Transformers perform on certain decision problems. While the idea of using communication complexity / bandwidth has been explored in prior works, the new contribution of this work is to split up the input into a prefix and suffix in order to reason about decision problems.\n\n**Weaknesses.** While the authors have presented the results in 6 different problems, I think this set is very limited. For example, it would be interesting to see if the predictions still hold if we consider problems where the communications bandwidth isn't just 0 or 1. Also, some of the results of CoT also don't seem to hold in practice, i.e., experiments in figure 4 do not show a significant benefit from using chain-of-thought.\n\nI worry that some of the assumption are too strong to clearly make predictions about problems beyond the ones considered in this work. By assuming that the prefix and suffix have infinite computational power, the predictive power of this theory may be a lot weaker.", "was_revised": true, "final_justification": "I've increased my score because the authors did a great job of addressing some concerns in the rebuttal. In particular, the authors justified why tasks seems to have small communication bandwidths, why a limited set of tasks were covered and ran a couple quick experiments. After the rebuttal, I am a lot more excited about the papers contribution.", "rebuttal": "Thank you for the good questions! Please see our responses below.  \n\n> some of the results of CoT also don't seem to hold in practice, i.e., experiments in figure 4 do not show a significant benefit from using chain-of-thought\n\nOur CoT theorem says that some low-bandwidth solution exists using sufficiently many reasoning tokens. This is consistent with the results in Figure 4: the low performance of CoT for models aside from o3 and Gemini 2.5 Flash is likely due to the soft limit of 250 words we set, which appears to be insufficient for $n > 50$. Meanwhile, o3 and Gemini 2.5 Flash, without this limit of 250 words (since their reasoning is internal), do show excellent performance on BAPO-hard problems. They do this by using far more reasoning tokens, in some cases 10k+ (Figure 9). Overall, these experiments confirm that CoT can allow models to solve BAPO-hard problems, but that they are not guaranteed to follow a correct CoT procedure and may require a large number of reasoning tokens.  \n\n> it would be interesting to see if the predictions still hold if we consider problems where the communications bandwidth isn't just 0 or 1 \n\nIn trying out various problems, we found that natural BAPO-easy problems tend to have very small constants for their bandwidth requirements. The largest constants we have encountered are (2, 3) for simulating a Turing machine step (Theorem 7), which does correctly predict that CoT can let LLMs solve BAPO-hard problems (as o3 did). This is analogous to the observation that most problems we encounter in P tend to have algorithms whose runtime is a very low-degree polynomial (e.g., we often see algorithms with runtime $n^2$ or $n^3$, but not $n^{15}$). It would be possible to construct problems with higher bandwidth requirements (e.g., rather than Equality, we could consider HammingDistanceAtMostk, which can be solved by a (0, k)-BAPO), and this is a nice suggestion! \n\n> While the authors have presented the results in 6 different problems, I think this set is very limited \n\nAs hardness proofs are very challenging, it is common for papers in this area to only consider a small number of problems. For instance, [16] only provides results for two problems (parity and 2Dyck) and the NeurIPS paper [6] analyzes only four problems and presents experiments on two (Index and Dyck). Another closely related NeurIPS paper [30] only considers Match2, Match3, and q-sparse averaging. These papers are still important and valuable, as so little is understood about transformer capabilities that even limited theory is enlightening. Judging by comparable papers, we feel that our problem set is sufficiently broad to be of significant use to the community. This is especially true since we include analysis and results for graph reachability, a broadly applicable problem that naturally connects to deductive reasoning and planning. \n\n> I worry that some of the assumption are too strong to clearly make predictions about problems beyond the ones considered in this work. By assuming that the prefix and suffix have infinite computational power, the predictive power of this theory may be a lot weaker.  \n\nWe'd like to clarify that our theory predicts only that if a task isn't BAPO-easy, LLMs will fail as input size grows due to limited bandwidth. In practice, LLM failures can happen due to many other factors beyond limited bandwidth, such as limited prefix/suffix compute. By making no assumption about compute, our BAPO framework elegantly isolates this inability to track a large amount of information as a particular mechanism for problem-solving failures. (Since submitting the paper, we have begun using an analogy to “working memory.”) This provides some useful insight: based on this understanding, it’s unlikely that simply scaling the MLPs in a transformer or adding more layers will improve these failings (equivalent to adding “more compute”). Rather, the issue occurs when residual streams communicate with each other through attention (as this is where information tracking and combining occurs).  \n\n> Do the LLMs successfully solve [kth largest and sorting] for different values of k? \n\nWe ran some additional experiments to check these problems. LLMs have no problem with maximum (k = 1), but struggle for larger k as the input grows, even k = 5 or 10. They also struggle with sorting when the list to be sorted has duplicate items. We believe that k-th largest (for constant k) is BAPO-$\\Sigma$-hard, as the number of bits required to communicate the k largest elements in the prefix scales with $|\\Sigma|$. We also conjecture that sorting is BAPO-hard, although depending on the input distribution (e.g., with no duplicates when sorting contiguous numbers) there may be shortcut solutions that models can employ in practice."}, {"review_id": "LJSnP7jrfq", "reviewer": "Reviewer_mvyW", "summary": "In this paper, the authors argue that failures in LLM on tasks requiring global reasoning are due to capacity limits on their internal information flow. They introduce the Bounded Attention Prefix Oracle (BAPO) model, a new computational framework that models these communication bandwidth constraints. The authors use this framework to classify problems as \"BAPO-hard\" if they require high bandwidth . Their experiments show that major LLMs succeed on BAPO-easy tasks but fail on BAPO-hard ones, corroborating their theoretical predictions.", "questions": "Suggestion:\nThe paper compellingly identifies that a key unanswered question is why modern LLMs, despite their immense scale, exhibit such a limited effective bandwidth. I suggest training small transformer models from scratch specifically on BAPO-hard problems. By systematically varying the models' depth and width during this process, it might be possible to isolate the specific architectural factors that contribute to these communication limits and gain crucial insights into this fundamental issue.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The development of a novel and principled theoretical framework (BAPO) is a valuable contribution, and the BAPO-hardness classification serves as a practical diagnostic tool.\n2. The paper successfully bridges the gap between theory and practice by aligning with the actual performance of state-of-the-art models.\n\nWeaknesses:\n1. The BAPO model is a significant abstraction of a real transformer as the authors acknowledge.", "was_revised": true, "final_justification": "The single weakness I initially noted—that the BAPO model is a significant abstraction of a real transformer—was intended more as a point of clarification on the scope of the model rather than a fundamental flaw. The authors acknowledged this limitation and framed the investigation of specific architectural components as a promising direction for future work inspired by their framework. I find this response to be both appropriate and constructive.\nIn summary, this paper makes a strong and well-supported contribution to our understanding of LLM limitations. I have no unresolved issues and believe the work is ready for publication.", "rebuttal": "We appreciate the positive feedback! Regarding the suggestion to train small transformers on BAPO-hard tasks to isolate which architectural components contribute to limited bandwidth, this is a great idea and exactly the type of research we hope our paper will inspire. For additional discussion about the simplifying assumptions in the model, please see our responses to reviewers 21nW and FeZc (1st and 3rd reviews)."}, {"review_id": "8DsBYlagnB", "reviewer": "Reviewer_FeZc", "summary": "This paper delves into the challenges LLMs face when handling tasks that require global reasoning, attributing these difficulties to bandwidth limitations in their internal information transmission. To formalize this issue, the research introduces the Bounded-Attention Prefix Oracle (BAPO) model, which simulates the communication constraints of an LLM's attention heads. This model classifies problems into \"BAPO-hard\" (requiring high bandwidth) and \"BAPO-easy.\" Experimental results validate that LLMs falter on BAPO-hard tasks. Furthermore, the study demonstrates that Chain of Thought (CoT) can effectively mitigate these bandwidth limitations by decomposing complex tasks into BAPO-easy steps.", "questions": "1. How would the BAPO model's theoretical framework and bandwidth requirements change if problems with multi-token, structured outputs were directly modeled, rather than just single-token solutions?\n2. How can the hypothesized trade-off between an LLM's \"generalization ability\" (for natural language tasks) and its \"effective bandwidth\" (for exact global reasoning tasks) be empirically isolated and quantified?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. Novel Computational Framework (BAPO Model): The paper introduces the Bounded Attention Prefix Oracle (BAPO) model, a new computational framework that formalizes and quantifies communication bandwidth constraints within LLMs' attention heads. This model offers principled explanations for why LLMs struggle with complex global reasoning tasks, abstracting away lower-level transformer details to focus on information flow.\n2. Theoretical Explanation for Chain of Thought (CoT) Effectiveness: The research provides a strong theoretical basis for the success of Chain of Thought (CoT), proving that CoT can decompose BAPO-hard problems into a sequence of BAPO-easy steps. It further demonstrates that constant-bandwidth BAPOs become Turing-complete with CoT, theoretically enabling them to solve any decidable problem, albeit potentially requiring a large number of output tokens.\n3. Empirical Validation and Practical Implications: The paper's experiments consistently corroborate its theoretical predictions: LLMs perform well on BAPO-easy tasks but systematically fail on BAPO-hard ones, even for relatively small instances across various models like GPT-4o, Claude, and Gemini. This alignment provides practitioners with actionable insights into LLM limitations and suggests mitigation strategies, such as inference-time scaling or hybrid architectures, or even optimizing for low bandwidth requirements during training.\n\nWeaknesses:\n\n1. Simplifying Assumptions in BAPO Model (**Too simple to evaluate the validity**): The BAPO model incorporates several simplifying assumptions that do not fully capture the complexities of real transformer computation. For example, it assumes problems have **single-token** solutions for simplicity, posits unbounded computational power for prefix/suffix streams** (though tempered by the requirement to work for all splits), allows the attention function `g` to base decisions on the **entire suffix** (unlike real causal attention, which communicates across layers), and assumes **perfect positional encoding** and attention only on the token layer. These simplifications might limit its direct applicability to all nuances of LLM behavior.\n2. Unidentified Root Cause of Limited Effective Bandwidth: Although the paper hypothesizes that LLM failures stem from limited effective bandwidth, it explicitly states that the \"root causes of this severely limited bandwidth\" are not fully understood. The authors acknowledge this as a limitation, suggesting it might even be a beneficial feature for generalization rather than a flaw, indicating an incomplete understanding of the underlying mechanism.\n3. Loose Theoretical Lower Bounds and Unexplored Problem Space: The paper acknowledges that \"many of our lower bounds are loose\" and there are \"many important problems whose BAPO bandwidths have yet to be explored\". This implies that the theoretical characterization of problem hardness in terms of bandwidth is not yet fully refined or comprehensive, leaving gaps in precisely understanding the communication requirements for various computational problems.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the questions! \n\n> How would the BAPO model's theoretical framework and bandwidth requirements change if problems with multi-token, structured outputs were directly modeled, rather than just single-token solutions?  \n\nOnce enough output tokens are allowed, this effectively becomes chain of thought, which as we show can reduce bandwidth requirements. And if the number of output tokens is small, then we can theoretically model outputs as a single compound “token” with a larger token vocabulary. \n\n> How can the hypothesized trade-off between an LLM's \"generalization ability\" (for natural language tasks) and its \"effective bandwidth\" (for exact global reasoning tasks) be empirically isolated and quantified?  \n\nThis is a great question, and one that the follow-up experiments suggested by Reviewer mvyW (2nd review) would help answer. If transformers trained to do a task can accomplish it, but LLMs trained for next-token prediction can’t, this indicates that the limitation is due to language modeling rather than architectural capabilities. This will be an interesting direction of future work for the community. \n\nRegarding the listed weaknesses: \n\n- We view the simplicity of the model as a strength: it allows us to explain and isolate a particular failure mechanism without having to account for every detail of the architecture. It also keeps mathematical analysis tractable so we can exactly characterize bandwidth requirements.  \n- Identifying the cause of limited bandwidth is a great direction for future work, but we feel that proposing the model, analyzing it theoretically, and testing it empirically is already a significant contribution. \n- Our bandwidth bounds do not need to be tight to be useful; they already provide significant separation between easy and hard problems."}, {"review_id": "OkI4JGRvHj", "reviewer": "Reviewer_qUKG", "summary": "Reasoning across the global input context is important to boosting accurate task performance. This paper introduces a theoretical model to bound the communication constraints due to causal attention in transformer-based large language models (LLMs): bounded attention prefix oracle (BAPO). The authors use the framework to outline 3 classes of problems: BAPO-easy, BAPO-hard, BAPO-$\\sum$-hard. They provide upper and lower bounds on the (prefix, attention) bandwidth. They then empirically show that these hardness classes are indicative of actual LLM performance on the analyzed problems. They further extend the empirical results to include real-world problems in the area of sentiment analysis and code tracing.", "questions": "- Can you include the theoretical lower and upper limits of BAPOs with COT similar to what was provided in table 1 for BAPO with no COT?\n- You only consider production-grade language models in your empirical analysis. At what point during model training do LLMs become well trained enough to fit the BAPO framework. Presumably, randomly initialized LLMs would not perform well on any task.\n- I am curious to see if adding in-context examples to the real-world tasks, as is suggested in the discussion (lines 324-330), empirically improves performance?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Quality:**\n\nThe theoretical model proposed (BAPO) is both analyzed via proof and empirical experiments which support the authors main arguments.\n\n**Clarity:**\n\nThe paper is well organized, and the experiments are well motivated by the theoretical analysis.\n\nWeakness: \n- In figures 3, 4, and 5, the theoretical lower and upper bound should be included to allow for quick comparison. \n- When trying to compare figure 3 vs. 4 I found myself having to quickly flip between the two figures to compare w/ and w/o COT. It would be helpful if you could summarize the COT vs. no-COT results in a table side-by-side to allow for easier comparison.\n\n**Significance:**\nIt is interesting to study the theoretical bounds on if/how transformers are able to complete different types of problem formulations as this analysis can directly be applied to many real-world LLM problem formulations. It informs humans on the limits of LLM abilities and their failure modes. \n\n**Originality:**\nThis work builds on an area on a line of work which studied LLM communication complexity. They contribute a new framework (BAPO) for reasoning about communication problems which are bounded by causal attention.", "was_revised": true, "final_justification": "- The strengths outlined in my initial review outweighed the weaknesses. \n- In the discussion period, the authors were able to clarify a misunderstanding about when BAPO framework can be applied to a model.\n- Therefore, I maintain my positive score.", "rebuttal": "Thank you for the positive feedback! It’s helpful to hear how the figures could be made more legible; we’ll work on an easier-to-parse comparison of the CoT and no CoT results. The theoretical bounds on bandwidth do not translate into accuracy bounds, they just separate the easy (top row in Figs 3&4) and hard (bottom row) problems. \n\nTo address the questions: \n\n> Can you include the theoretical lower and upper limits of BAPOs with COT similar to what was provided in table 1 for BAPO with no COT?  \n\nWith enough CoT tokens, the upper bound for bandwidth requirement is (2, 3) for all decidable problems by Theorem 7. We will add this to the table caption. \n\n> You only consider production-grade language models in your empirical analysis. At what point during model training do LLMs become well trained enough to fit the BAPO framework. Presumably, randomly initialized LLMs would not perform well on any task.  \n\n Indeed, models need a certain level of capability to solve even BAPO-easy tasks. As such, we focus on pre-trained LLMs. When capabilities emerge during training is a great question but out of scope for this work. \n\n> I am curious to see if adding in-context examples to the real-world tasks, as is suggested in the discussion (lines 324-330), empirically improves performance? \n\nWe don’t expect variable tracking and majority review to be helped by in-context examples. For majority review, we make sure that LLMs can (almost) perfectly classify individual reviews, so adding more examples are unlikely to help. We conjecture that when in-context examples allow for a low-bandwidth shortcut solution (e.g. nearest-neighbor heuristics like we suggest in the discussion) they could improve LLM performance, but that is not the case for the BAPO-hard problems we tested on."}]

Author rebuttal:

Meta-review: The paper introduces the Bounded Attention Prefix Oracle (BAPO) model, a simple but expressive abstraction that captures bandwidth limits in the attention mechanism of transformers. Using this framework, the authors (1) demonstrate that advanced LLMs can succeed on BAPO-easy instances but fail on relatively small BAPO-hard ones, and (2) provide an explanation for the empirical success of CoT prompting.

Overall, reviewers praise the novelty and elegance of the model, the clear theoretical–empirical connection, and the improved explanation of several long-standing LLM failure modes. Meanwhile, they are concerned that: 1) this abstraction may be overly simplistic; 2) the explored task set is small; 3) the lower bounds provided are loose; and 4) certain sections require further clarification and better presentation.

The rebuttal is considered. While reviewers acknowledge the modeling limitations of this framework, they generally agree that the paper makes a clean and valuable theoretical contribution to understanding LLMs. The only negative reviewer does not identify any fatal errors and is okay with acceptance.

Taking these factors into account, the AC recommends acceptance, given the importance of better understanding LLMs and the potential of this work to stimulate follow-up research in both theory and practice.
Decision: Accept (spotlight)