acceptodds
Under review as a conference paper at ICLR 2027

The Shared Memory Bottleneck: Capacity Limits of Constraint Satisfaction with External Scratchpads

Abstract

Chain-of-thought prompting and scratchpads are often viewed as external memory for reasoning, but this interpretation becomes incomplete when the final answer must be generated from a bounded, jointly retained state. We formalize this limitation through a minimal constraint-satisfaction model in which an agent must exactly reconstruct independent binary constraints from a shared internal and external memory configuration with at most distinguishable states. Under this abstraction, we prove the tight phase law , showing that once the independent information required by the task exceeds the retained memory budget, each additional bit of information exponentially halves the optimal probability of exact success. We further extend this result to worst-case coverage and non-uniform inputs through a min-entropy formulation, separating nominal prompt length from effective independent information. To test the qualitative predictions of the theory, we introduce a two-call retention protocol in which a language model first observes a complete constraint set and produces a bounded written representation, after which the original constraints are removed and the model must reconstruct them solely from the retained representation. Experiments across modern long-context and reasoning models reveal sharp, model-dependent retention cliffs as effective information increases. Structured key-value and compressed symbolic scratchpads shift these boundaries by improving coding efficiency, while redundancy and latent structure shift them by reducing effective entropy. Answer-time external access moves the boundary differently by supplying information beyond the retained state. These results show that long-context and scratchpad reasoning are fundamentally constrained not by nominal context length alone, but by the amount of independent information jointly available when the final answer is generated.

Primary area:
learning theory
Keywords:
Large Language Models, Chain-of-Thought Reasoning, External Scratchpads, Memory Capacity Limits

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_PdG7OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates the capacity limitations of internal and external memory in language model reasoning. The authors formulate a finite-state constraint reconstruction problem and derive a theoretical bound on exact reconstruction success under a shared memory budget. They further extend the analysis to non-uniform information distributions and answer-time external access. To examine these theoretical predictions, the paper introduces a two-call retention protocol and evaluates several language models under different memory representations, information entropy levels, and external access conditions.

Critical strengths
  1. Interesting theoretical perspective. The paper provides a clear formulation of memory capacity constraints and highlights the distinction between nominal context length and information that remains recoverable during answer generation.

  2. Useful empirical observations. The experiments investigate multiple language models and analyze how scratchpad representations, information redundancy, and external access affect reconstruction performance. These observations provide useful insights into memory retention behavior.

Critical weaknesses
  1. Limited theoretical novelty. The central Joint Memory Budget Theorem is essentially derived from a standard finite-state counting argument. The exponential decay of exact reconstruction probability follows directly from the number of distinguishable memory states. Although the formulation is clear, the theoretical contribution appears relatively incremental compared with established information-theoretic capacity bounds.

  2. Insufficient connection between theoretical assumptions and empirical validation. The theoretical analysis considers the joint capacity of internal and external memory, whereas the empirical two-call protocol primarily measures information recoverable from explicitly written representations. This protocol does not directly characterize the internal memory capacity of an LLM during continuous reasoning. Moreover, the experiments focus on synthetic constraint reconstruction rather than realistic reasoning tasks, limiting the evidence for the broader claims about LLM reasoning and external scratchpads.

Questions for authors
  1. What is the fundamental theoretical novelty of the Joint Memory Budget Theorem compared with classical finite-state counting and information-theoretic capacity bounds? Could the authors clarify which conclusions are not already implied by these established results?

  2. How can the theoretical joint memory budget be meaningfully related to the internal states of real LLMs? Since the two-call protocol resets the model's internal state and retains only the written representation, how does the experiment validate the claimed joint internal-external memory bottleneck? Would additional experiments on realistic multi-constraint reasoning tasks provide stronger evidence?

Reviewer_khmoOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper argues that chain-of-thought traces and scratchpads should not be treated as unlimited external memory when the final answer must be decoded from a bounded, jointly retained state. It models this as a "card game": an agent sees N independent binary constraints and must reproduce all of them from a final configuration M, which includes both internal state and scratchpad and has |M| <= 2^B. The main result (Theorem 1, the "Joint Memory Budget Theorem") is that the optimal exact-success probability is p* = min{1, 2^(B-N)}. The paper extends this to adversarial hands, arbitrary distributions and min-entropy (Eq. 6, Eq. 9), and answer-time external information (Corollary 2 / Theorem 5, bound 2^(B+Q-kappa)). Empirically, a two-call protocol has an LLM write a memory of at most 512 tokens from a key-value "hand" (call 1) and then rebuild the hand from that memory alone (call 2). Across five models, the paper reports drops in exact success with fitted 50% crossings between about 180 and 310 bits (Table 1). Structured KV and compressed symbolic formats shift the boundary by about 60-70 bits relative to free-form CoT (Table 2). The paper also reports boundary shifts from redundant or structured generators (Fig. 6a) and from answer-time queries (Fig. 6b).

Critical strengths
  • The conceptual separation the paper argues for is useful and clearly stated: visible context, retained information and newly retrieved information are distinct resources. Fig. 6b gives a clean qualitative illustration: queries help a lot at kappa=384 (about 1.2% -> 61.2%) and barely at kappa=224/288.
  • The theory is correct and stated carefully in the appendix. It gives necessity and sufficiency for integer K (Theorem 4), the exact optimum for an arbitrary distribution (Eq. 9), a randomized-policy argument and side information.
  • The authors are commendably candid that the B_point normalization is algebraically circular (Sec. 3.2, App. D.2). They also report malformed, truncation and refusal rates separately from wrong-value errors (Fig. 5, App. D.3).
  • The prompts, parser rules and failure-label priority are documented in detail (App. E), which helps reproducibility.
Critical weaknesses
  1. The theoretical contribution is a standard pigeonhole/counting fact. A decoder reading a state with at most 2^B values can output at most 2^B strings, so it is exactly right on at most 2^B hands. The min-entropy and side-information versions follow directly, as do Theorem 5 and the "adversarial robustness" claim (some hand is never output). These are textbook facts from source coding and communication complexity, so calling them a "tight phase law" and a "Theorem" overstates the novelty. The paper cites Cover & Thomas and Alon et al. but does not say clearly what is new relative to these classical results. The one-way communication / source-coding framing that the two-call protocol directly instantiates is not discussed.

  2. The experiments do not test the quantitative law. They only show a qualitative decline that many other mechanisms would also produce. (a) B is never manipulated. The writing budget is fixed at 512 tokens in every condition (Table 4). A compressed symbolic memory (hex/base64 is explicitly allowed, App. E.2) of 512 tokens can carry far more than the roughly 180-310 bits at which the models fail (Table 1). The observed boundaries therefore cannot be the information-theoretic limit of M. They most likely reflect the models' errors in encoding, transcribing or decoding, which the theorem does not model.

Questions for authors
  1. How do the observed boundaries (about 180-310 bits) relate to the information capacity of a 512-token compressed memory? Did you inspect call-1 outputs at the boundary? Were failures caused by memories that were too short or lossy, or by decoding/transcription errors in call 2?
  2. Can you show how the kappa-hat_0.5 crossing changes when the call-1 budget is varied (even for one model and one format)?
  3. How exactly is B_eff in Fig. 3a computed? How can points have negative kappa - B_eff and p_all < 1 at the same time?
  4. How do success values of about 0.003 arise with n <= 100 hands per condition?
  5. Which models were used for Fig. 6? Do thinking tokens count toward the 512-token writing budget?
Reviewer_DhDiOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper examines the assumption that large context windows and long reasoning traces provide LLMs with effectively unlimited working memory. The authors argue that, when producing a final answer, the relevant information must ultimately be available through a bounded retained state. They show theoretically and empirically that exact success declines sharply when the amount of independent information exceeds what the model can reliably retain. Structured memory formats and answer-time external access can shift this boundary, but do not remove the underlying limitation. Overall, the paper provides a useful perspective on why models can still struggle with tasks involving many simultaneous constraints despite having long contexts and reasoning traces.

Critical strengths
  • The paper provides a clear theoretical account of memory limitations using a simple counting argument. The resulting phase law gives a useful way to interpret the empirical retention behavior.

  • The distinction between context length and retained information is important. The experiments show that having more context does not necessarily mean that all relevant information remains available at answer time.

  • The scratchpad and external-access experiments are useful additions. They show that better memory formats and external information can shift the retention boundary, while the underlying limitation still remains.

Critical weaknesses
  • The theory is clean, but the empirical setup is highly simplified, relying mostly on exact reconstruction of independent information. It is unclear whether the same phase behavior carries over to realistic reasoning, where models can select relevant information, exploit semantic dependencies, and tolerate partial information.

  • The link between the theoretical memory budget (B) and actual LLM behavior remains indirect. An independent capacity estimate that predicts performance at unseen entropy levels would provide stronger evidence.

  • The scratchpad gains may not come from coding efficiency alone. Retrieval difficulty or familiarity with the format could also affect the results.

  • The analysis is mainly behavioral. It shows when retention fails, but gives limited insight into whether information is lost during encoding, retention, or reconstruction.

  • The model coverage is limited, with no matched comparison between base/instruct and reasoning-post-trained models, making the effect of post-training on the retention boundary unclear.

Questions for authors

1-Can retained capacity be estimated independently and then used to predict performance at unseen entropy levels?

2- How does the framework extend to tasks where only a subset of the input is relevant to the final answer?

3- Can models learn which information to retain when memory is limited, rather than being required to reconstruct the full input?

4- In Figure 4b, are the gains from structured and compressed scratchpads mainly due to better coding efficiency, or could retrieval difficulty and familiarity with the format also explain the differences?

5- How does reasoning-oriented post-training affect the retention boundary compared with a matched base or instruct model?

6- Can the authors distinguish information lost during encoding from failures during retrieval or reconstruction?

7- How sensitive are the measured retention boundaries to prompt wording, few-shot examples, or memory-writing instructions?

8- Do the same retention cliffs appear in more natural reasoning tasks with semantic dependencies and selective information use?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.