- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper asks how much memory a language model must keep about text it has already read in order to answer later questions about it. It treats everything the model carries forward (its "complete persistent state", which the paper calls the cache) as a message from the past to the future, and counts the bits in that message.
The main theoretical result is a lower bound on the memory needed to recall stored records at a given error rate when the question is not known in advance, together with a demonstration that this bound can be approached in some settings. The paper also argues that a compact summary mixing information from many records can do better than keeping a subset of the records, and (not surprisingly) that knowing the question before compressing makes the problem much easier.
Critical strengths
-
The memory taken by the cache is a major cost when serving language models on long contexts, and many recent methods try to shrink it. Asking how much memory is actually needed, rather than proposing yet another compression heuristic, is a valuable direction.
-
The paper offers a formal framework with proven bounds and then examines it empirically, on small formal-language tasks, on a synthetic recall task, and on real Transformer models using existing cache-compression methods (StreamingLLM, SnapKV, KIVI).
-
Some results are easy to grasp. For example, the paper shows that a 64-bit summary of 128 binary records can reach about 86% recall accuracy, compared with 75% when simply keeping half of the records. However, this is for random bits, and the gain diminishes as the size of the alphabet grows, which is expected.
Critical weaknesses
-
The analysis assumes a model with unlimited computation between tokens, update rules that may differ for every input length and position, records that are independent and uniformly random, and questions that are independent of the stored data. One setting also assumes a shared random stream that is available for free. It is therefore hard to tell whether these assumptions describe real language models, or whether they mainly serve to turn the problem into an easier, classical information-theoretic question about streams, for which the tools already exist.
-
Several earlier papers appear to reach similar conclusions about the memory needed for recall and are neither cited nor discussed, for example Arora et al. [1], Jelassi et al. [2], and Bhattamishra et al. [3]. On the empirical side, compression methods designed for questions that are not known in advance, such as KVzip [4], are not compared.
-
The main takeaways are that more memory gives better recall, that frequently requested items deserve more memory, and that knowing the question before compressing helps. These are expected and can be demonstrated using simpler tools.
-
The paper does not propose a new compression method, and the experiments are diagnostic. It is not clear what a practitioner would do differently after reading the paper.
References
[1] Simran Arora, Sabri Eyuboglu, Michael Zhang, Aman Timalsina, Silas Alberti, James Zou, Atri Rudra, and Christopher Ré, "Simple linear attention language models balance the recall-throughput tradeoff," in International Conference on Machine Learning (ICML), PMLR 235, pp. 1763–1840, 2024. https://proceedings.mlr.press/v235/arora24a.html.
[2] Samy Jelassi, David Brandfonbrener, Sham M. Kakade, and Eran Malach, "Repeat After Me: Transformers are Better than State Space Models at Copying," in International Conference on Machine Learning (ICML), PMLR 235, pp. 21502–21521, 2024. arXiv:2402.01032.
[3] Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade, "Separations in the Representational Capabilities of Transformers and Recurrent Architectures," in Advances in Neural Information Processing Systems 37 (NeurIPS), pp. 36002–36045, 2024. arXiv:2406.09347.
[4] Jang-Hyun Kim, Jinuk Kim, Sangwoo Kwon, Jae W. Lee, Sangdoo Yun, and Hyun Oh Song, "KVzip: Query-Agnostic KV Cache Compression with Context Reconstruction," in Advances in Neural Information Processing Systems (NeurIPS), 2025. arXiv:2505.23416.
Questions for authors
Please address the realism of the assumptions, the missing related work, and the significance of the results.
5 comments
Response to Reviewer bggA (2/3)
Relevant Works
We thank the Reviewer for bringing these works to our attention. Although relevant to memory and recall, these papers differ substantially from ours in both scope and theoretical guarantees. However, we agree that these works should be discussed explicitly. We provide the comparisons below and will incorporate this discussion into the revised manuscript.
Arora et al. [1] focus on developing BASED to accelerate generation while maintaining strong recall performance. Their most relevant result is asymptotic lower bound for associative recall using binary-valued records (), where is the retained memory in bits and is the number of records.
Their bound does not explicitly quantify its dependence on alphabet size, recall error, and query distribution. Our analysis makes these dependencies explicit. For example, for independent uniform -ary records and uniform queries, our Thm. 2.2 gives where denotes binary entropy and is the target average query error.
Bhattamishra et al. [3] focus on comparing model-size requirements for Transformers and recurrent architectures. Their most relevant result is the recurrent-state lower bound for index lookup. They show that any recurrent model that exactly retrieves an arbitrarily queried entry from a database of N binary values must retain at least N hidden-state bits, enough to encode the entire database. The relevant result therefore does not capture how memory requirements depend on alphabet size, recall error, or query distribution, and does not cover our comprehensive theoretical analysis.
Jelassi et al. [2] focus on how transformers outperform fixed-state models at copying. Their most relevant result is the finite-state memory lower bound for copying uniformly distributed length-m string with failure probability at most , Their theorem considers whole-string copying, where success requires reproducing every input symbol correctly. We instead study retrieval because it captures a basic aspect of our research question. Retrieval isolates the information needed to answer a later request without requiring reconstruction of the entire input. Our memory lower bounds can also extend to broader tasks through suitable reductions.
KVzip Experiments
We agree with the reviewer that KVzip [4] is a strong baseline. Thus, we have evaluated it in Experiments 3 and 4A and will include the results and discussion in the revised paper.
Experiment 3: KVzip with pre-query compression, m = 128 and q = 16, using frozen Ministral 3 3B, seed 47, and 64 databases with 16 queries per database per query law.
| Retention fraction | Prefix cache (MiB) | Uniform accuracy (%) | Zipf-1.1 accuracy (%) |
|---|---|---|---|
| 3/4 | 70.18 | ||
| 1/2 | 46.78 | ||
| 1/4 | 23.38 | ||
| 1/8 | 11.74 |
Experiment 4A: KVzip on SCBench, using BF16 Ministral 3 8B and the same 90 contexts (30 per task), with five independently evaluated queries per context. KV, PS, and VT denote KV Retrieval, Prefix-Suffix Matching, and Variable Tracking.
| Retention fraction | Cache (%) | KV (%) | PS (%) | VT (%) | Preserve (%) |
|---|---|---|---|---|---|
| 3/4 | 76.1 | 98.9 | |||
| 1/2 | 50.9 | 86.9 | |||
| 1/4 | 25.7 | 50.9 | |||
| 1/8 | 13.1 | 31.0 |
KVzip maintains high accuracy under aggressive compression in Experiment 3, with diminishing gains as retention increases. Experiment 4A reveals stronger task dependence: KV Retrieval and Prefix-Suffix Matching degrade sharply at small budgets, while Variable Tracking remains robust. KVzip may perform well because each KV entry can encode information about other tokens, so selecting original entries that receive high attention from the repeated database can preserve information even about tokens whose own KV entries are removed. These trends also illustrate that retrieval depends on both cache size and the task-relevant information preserved, consistent with our complete-state perspective. These results do not conflict with our theory, because the observed accuracies are compatible by the theoretical bounds at the evaluated cache sizes.
Response to Reviewer bggA (3/3)
Assumptions
We allow unrestricted computation to isolate the information required for recall from the computational cost of encoding and decoding. This strengthens our lower bounds, as they hold even with unlimited computational power and therefore also apply to computationally restricted models. We permit update rules to depend on input length and position to broaden the class of models covered by our analysis, including language models with shared parameters.
We assume independent, uniformly distributed records to isolate the information that must be preserved for later recall: uniformity removes advantages from guessing common values, while independence prevents missing records from being inferred from other records. Under that assumption, record count directly measures the amount of new information. Moreover, we assume that the query index is independent of the database so that the query itself does not reveal information about record values. This separates information recovered from the cache from information supplied by the request. Together, these 2 assumptions provide a hard benchmark for universal recall guarantees, since any method required to succeed on every database-query pair must also succeed under these assumptions.
The free shared random stream is mainly used as a comparison with our default setting to explain why reusable randomness must be counted as part of the persistent cache. Overall, beyond making the theory tractable, our assumptions make the research question precise, define a broad framework covering finite-precision language models, and provide a hard benchmark for worst-case recall guarantees. We agree with the reviewer that this distinction is not yet explicit. We will revise the manuscript to clarify these points.
Response to Reviewer bggA (1/3)
We thank the Reviewer for the insightful comments. We would like to address each of the Reviewer's concerns as follows.
Scope and Contributions
Here, we would like to clarify that the paper is a theoretical study of persistent-memory requirements in causal decoders. The main question we address is how much information must survive from past inputs to support future computation.
The scope of this paper is the theoretical limits and achievable memory-accuracy tradeoffs, and to examine their predictions and implications with experiments. Accordingly, developing a new practical compression method is not the paper's major objective. The experiments are intentionally diagnostic: they investigate how memory budget, representation, query timing, and randomness conventions affect behavior in relation to the theoretical results. Therefore, their diagnostic nature follows directly from the paper's scope.
Although the implications of our theory and experiments are discussed throughout the paper, the introduction could highlight our contributions more explicitly. Thus, we summarize them below, and we will revise the introduction accordingly.
Thm. 2.1 provides a theoretical tool for studying causal-decoder memory requirements. Part (a) formalizes the complete persistent state as a one-way communication message, enabling communication lower bounds to transfer to decoder memory. Part (b) demonstrates the capabilities of this tool by establishing how query timing changes exact boundary-memory requirements. Therefore, Thm 2.1 provides a basis for further studies of persistent memory in causal decoders.
Thm. 2.2 establishes computable memory lower bounds for record retrieval under general query distributions and shows that the lower bound can be approached asymptotically under uniform queries. We focus on record retrieval because it captures a fundamental requirement of context-dependent reasoning and generation: retaining information needed for later answers. Once lost, that information cannot be restored by computation alone. Therefore, Thm 2.2 supports memory lower bounds for broader tasks through suitable reductions and provides quantitative guidance for memory budgeting and accuracy allocation.
Props. 2.3 and 2.4 examine literal-selection caches and coded summaries. Prop. 2.3 quantifies the accuracy limits of literal selection, and Prop. 2.4 derives finite-length memory-accuracy guarantees using classical perfect codes. Together, these results demonstrate how cache representation affects memory-accuracy tradeoffs, informing representation choices and empirical evaluation.
Prop. 2.5 demonstrates how randomness conventions change persistent-memory requirements through equality testing. The separation explains why reusable private seeds must count toward memory budgets, supporting both theoretical modeling and fair empirical comparisons.
Finally, our experiments connect the theory to practical decoder behavior by quantifying how representation, precision, and query timing affect the retrieval task. These findings guide representation and precision choices and support comparisons of existing methods through accounting of query access and persistent memory.
Qualitative Trends and Simpler Tools
We agree with the reviewer that the qualitative trends are expected. However, these trends alone do not fully reflect the precise theoretical guarantees that our paper provides. These include a cache-to-communication transfer which preserve message size, error, and randomness convention, illustrating with exact boundary memory requirements under different query timings; explicit coordinatewise memory-error lower bounds; a query-weighted error constraint and its optimizer; matching asymptotic achievability under uniform and block-constant query laws; the quantified advantage of coded summaries over literal retention; and a quantified separation showing why reusable randomness must be counted. These guarantees not only clarify the relationships but also provide a rigorous basis for understanding what models with limited memory can and cannot achieve. We acknowledge that simpler arguments may find out the qualitative trends, but we cannot tell whether they would yield these quantitative guarantees under the stated assumptions.