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

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 $N$ independent binary constraints from a shared internal and external memory configuration with at most $2^B$ distinguishable states. Under this abstraction, we prove the tight phase law $p^{\star }(N,B)=\min \{1,2^{B-N}\}$, 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.