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

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.

To address the 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?

With 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.

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.

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.

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?

We 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.

Thank you for the questions!

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?

Once 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.

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?

This 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.

Regarding the listed weaknesses:

• 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.
• 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.
• Our bandwidth bounds do not need to be tight to be useful; they already provide significant separation between easy and hard problems.

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).

Thank you for the good questions! Please see our responses below.

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

Our 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.

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

In 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!

While the authors have presented the results in 6 different problems, I think this set is very limited

As 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.

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.

We'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).

Do the LLMs successfully solve [kth largest and sorting] for different values of k?

We 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.