acceptodds
Under review as a conference paper at ICLR 2027

Persistent-Cache Complexity: A Finite-State And Communication-Theoretic View of Causal Decoders

Abstract

*How much memory does a causal decoder need to retain enough information to answer queries about an input it has already processed?* We study this question by counting all input-dependent information retained for future computation. For independent, uniformly distributed records compressed before an independent query is revealed, we derive memory lower bounds for a target average recall error. Under uniform queries, coding constructions asymptotically match these bounds, characterizing the optimal tradeoff between retained memory and recall accuracy. When queries have unequal frequencies, our bounds explain how memory can favor frequently requested records. We show that encoding a summary can outperform storing a fixed subset of records exactly, although this advantage at a fixed storage fraction decreases as the number of possible record values grows. Our analysis counts selection indices and reusable randomness, and distinguishes memory retained after compression from peak memory and physical cache storage. Experiments with finite-state models and Transformer caches on formal language recognition, synthetic associative recall and string retrieval illustrate these discovered tradeoffs and the importance of query timing.

Primary area:
learning theory
Keywords:
Persistent-cache complexity, KV cache, communication complexity, cache compression

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_bggAOpenReview ↗
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
  1. 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.

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

  3. 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
  1. 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.

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

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

  4. 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
AuthorsOpenReview ↗

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.

AuthorsOpenReview ↗

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 B=Ω(m)B=\Omega(m) for associative recall using binary-valued records (q=2q=2), where BB is the retained memory in bits and mm 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 qq-ary records and uniform queries, our Thm. 2.2 gives B≥m[log⁡2q−h2(eˉ)−eˉlog⁡2(q−1)],B\ge m\left[\log_2q-h_2(\bar e)-\bar e\log_2(q-1)\right], where h2h_2 denotes binary entropy and eˉ\bar e 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 δ\delta, B≥mlog⁡2q+log⁡2(1−δ).B\geq m\log_2q+\log_2(1-\delta). 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 fractionPrefix cache (MiB)Uniform accuracy (%)Zipf-1.1 accuracy (%)
3/470.1899.3±0.499.3 \pm 0.499.9±0.199.9 \pm 0.1
1/246.7899.3±0.499.3 \pm 0.499.9±0.199.9 \pm 0.1
1/423.3899.3±0.599.3 \pm 0.599.9±0.199.9 \pm 0.1
1/811.7497.3±1.197.3 \pm 1.196.9±2.496.9 \pm 2.4

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 fractionCache (%)KV (%)PS (%)VT (%)Preserve (%)
3/476.195.3±3.795.3 \pm 3.774.0±7.074.0 \pm 7.096.1±1.796.1 \pm 1.798.9
1/250.989.3±5.789.3 \pm 5.756.0±7.056.0 \pm 7.095.5±1.995.5 \pm 1.986.9
1/425.736.7±12.336.7 \pm 12.315.3±5.715.3 \pm 5.794.9±1.994.9 \pm 1.950.9
1/813.11.3±1.71.3 \pm 1.70.7±1.00.7 \pm 1.093.3±2.493.3 \pm 2.431.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.

AuthorsOpenReview ↗

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.

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

This paper studies how much persistent memory a causal decoder needs to retain to answer future queries about an input it has already processed. It defines persistent-cache complexity using a classical streaming model and connects cache states to one-way communication. The authors derive memory lower bounds and an asymptotically matching result under uniform queries, with extensions to other query laws. The paper also studies query timing, selection accounting, perfect-code summaries, and randomness conventions. Four experiments investigate these results using formal language recognition, synthetic associative recall, Transformer KV-cache compression, and the String Retrieval tasks of SCBench.

Critical strengths
  1. The approach of viewing the persistent cache as a message in a one-way communication protocol allows lower bounds from communication complexity to be applied to causal decoders. More generally, I think the paper's effort to bring ideas from different theoretical fields to study memory requirements is valuable.

  2. The theory analysis is quite involved, and characterizes different factors that could influence memory requirements: when the query is received, which indices to retrieve, whether the representations are compressed and randomization is private or public. Also, the recall lower bound is shown to be asymptotically achievable under uniform queries, rather than being only a lower bound.

  3. The four experiments are sound and are closely linked to the predictions of the theory and address different aspects of the framework. The formal language experiments recover predicted memory thresholds, and the associative recall experiments compare measured accuracy with the theoretical results. The perfect-code experiment is particularly convincing, with measured accuracy close to the predicted value.

  4. The paper is well written and the notations are clear.

Critical weaknesses
  1. The paper discusses relevant work in Appendix A. However, I think the positioning could be improved by more clearly distinguishing the new theoretical contributions from applications of existing results. It would also help to discuss related work on in-context retrieval, such as [1].

  2. Some figures could be improved in terms of readability. Figure 1b combines many variables using colors, marker shapes, and grouped positions, making it difficult to identify the main trends. I think separating some dimensions into subplots and simplifying the visual encodings would make the results much easier to interpret.

[1] Wen et al., RNNs are not Transformers (Yet): The Key Bottleneck on In-Context Retrieval, ICLR25

Questions for authors
  1. Could the authors clarify which parts of Theorem 2.2 and its extensions require new theoretical arguments, and which follow directly from existing results in rate distortion theory?

  2. The main recall results assume independent uniform records and queries independent of the database. What happens when queries depend on the database, or when the query law is unknown or changes over time?

  3. For nonuniform query laws, the Fano frontier is not always known to be achievable. How should we interpret the gap between this frontier and the learned summaries?

  4. How informative are the KV-bit bounds (Remark B.14) for actual Transformers? For example, what lower bound on retained KV positions do they give for the models evaluated in the paper?

2 comments
AuthorsOpenReview ↗

Response to Reviewer cqCE (1/2)

We thank the reviewer for the positive assessment of our results and the helpful presentation suggestion. Following the presentation advice, we will revise Figure 1b by separating dimensions into subplots and simplifying the visual encodings to make the trends clearer and easier to interpret. We address the reviewer's remaining concerns as follows.

Positioning Discussions

We agree with the reviewer that the positioning could be clearer. We will revise the paper to distinguish the new contributions from applications of existing results, including the following clarifications below on rate-distortion theory and Wen et al. [1].

Rate Distortion Theory. Part (a) combines Fano's inequality, which is also used to prove lower bounds in Hamming rate-distortion theory, and our additionally account for the complete cache CC, distinguish persistent from fresh randomness, and use record independence to obtain S≥I(X;C)≥∑ifq(ei)S\ge I(X;C)\ge\sum_i f_q(e_i). MAP postprocessing, monotonicity, and integer rounding give the remaining statements. Part (b) follows directly from (a) by minimizing this bound under ∑iπiai≤eˉ\sum_i\pi_i a_i\le\bar e; standard convex optimization gives the stated optimizer and uniqueness.

Part (c) directly applies the classical rate-distortion coding theorem to obtain the deterministic cache upper bound Sunif⋆(m,eˉ)≤mfq(eˉ)+γmS^\star_{\mathrm{unif}}(m,\bar e)\le m f_q(\bar e)+\gamma m for any γ>0\gamma>0 and sufficiently large mm. Combining this with the lower bound from parts (a) and (b) establishes the asymptotic memory-error characterization.

The extensions apply classical rate distortion theory to obtain block codes. Our proof requires additional arguments to make the coding guarantees uniform over varying distortion targets and choose fixed coordinate permutations to control query-weighted error. Combining these constructions with part (b)'s converse gives Sπ⋆(m,eˉ)=Rπ(eˉ)+o(m)S^\star_\pi(m,\bar e)=\mathcal R_\pi(\bar e)+o(m) for block-constant query laws under the stated assumptions, and a block-restricted upper bound for general query laws.

Wen et al. [1]. They compare the expressive power of RNNs and Transformers, including the effects of chain-of-thought, while we ask how much persistent cache an abstract causal decoder needs to preserve the information required for future computation.

They show that RNNs with sublinear memory cannot perfectly solve associative recall, even with arbitrarily long chain-of-thought, while Transformers with fixed depth and width can. However, their asymptotic retrieval lower bound, written as S(m)=Ω(m)S(m)=\Omega(m) in our notations, is stated for RNN memory and is not formulated for the complete persistent cache of general causal decoders, including Transformers. Moreover, they do not characterize the joint dependence of memory requirements on recall error, alphabet size, and query distribution. Our paper addresses these quantitative requirements and provides asymptotically matching constructions under the stated assumptions.

Bounds for Transformers

The 2500 UUID key-value pairs in SCBench KV retrieval admit a compact binary representation of approximately 74 KiB, including keys. Under an illustrative model of independent uniform values and uniform queries, combining Theorem 2.2 with the KV accounting in Remark B.14 gives a necessary memory budget of approximately 36 KiB for error at most 1%. Both quantities are smaller than one full BF16 KV position across all layers of the evaluated Ministral 3 8B model, which occupies about 136 KiB. This does not establish that one retained position suffices for the actual Transformer. Our bound isolates the information required by the task while allowing unrestricted encoding and decoding. KV caches additionally retain intermediate representations from earlier computation for subsequent reuse. Thus, the gap can reflect the storage cost of supporting efficient computation within a fixed architecture, beyond the information that must be preserved.

For larger databases, the information requirement becomes more substantial. Under the assumptions of Thm. 2.2 with uniform queries, the pre-query retained-cache lower bound S≥mfq(eˉ)S\ge m f_q(\bar e) grows linearly with the database size mm at fixed alphabet size and target error below chance. Combining this information requirement with architecture-specific memory requirements for computation would provide a fuller view of the cache needed by a practical decoder.

AuthorsOpenReview ↗

Response to Reviewer cqCE (2/2)

Query Law Information

Database Depending Query. We assume query independence to separate information preserved in the cache from information supplied by the request. This makes the question of required persistent memory precise.

If the encoder can infer the actual query from the database before compression, it can retain only the requested answer. For that request, compression is effectively query-aware, analogous to the post-query scenario in Thm. 2.1(b).

If only the conditional query distribution can be inferred, the probabilities Pr⁡(I=i∣X)\Pr(I=i\mid X) may vary with the database instance. The query-weighted frontier in Thm. 2.2(b) does not directly apply in this setting. For example, consider two independent uniform binary records. If their values differ, query the record containing 11; otherwise, choose either index uniformly. The marginal query probabilities remain uniform, yet a zero-memory decoder always answering 11 achieves 75% accuracy, exceeding the 50% permitted with independent queries. Thus, knowing the marginal query law is insufficient. This case requires a further extension accounting for the joint database-query distribution and the information supplied by query selection.

Unknown or Changing Query Law For an unknown but fixed query law, Theorem 2.2(b) does not require the encoder or decoder to know the law; the law is needed to evaluate the bound. If the law changes over time, the converse applies to the current law, provided the query remains independent of the database and the pre-query cache.

We additionally derive the following extension when the query law is estimated rather than known exactly and will include this result in the revised paper.

Result. Under the source and independence assumptions of Theorem 2.2, let π\pi be the true query law and π^\widehat\pi an estimate learned independently of the database. Fix the estimate and the resulting encoder-decoder. Suppose

=\frac12\sum_i|\pi_i-\widehat\pi_i|\le\delta.$$ If the cache achieves population error at most $\varepsilon$ under $\pi$, then, writing $c_q=1-1/q$, $$S\ge\mathcal R_{\widehat\pi}(\varepsilon+c_q\delta),$$ where $\mathcal R_{\widehat\pi}(u)=0$ for $u\ge c_q$. **Proof.** The coordinatewise Bayes errors from Theorem 2.2(a) satisfy $0\le e_i^\star\le c_q$ and $\sum_i\pi_i e_i^\star\le\varepsilon$. Hence, $$\sum_i\widehat\pi_i e_i^\star \le\sum_i\pi_i e_i^\star+c_q\operatorname{TV}(\pi,\widehat\pi) \le\varepsilon+c_q\delta.$$ This error vector is feasible for the estimated-law variational problem. Applying the coordinatewise converse gives $$S\ge\sum_i f_q(e_i^\star) \ge\mathcal R_{\widehat\pi}(\varepsilon+c_q\delta).$$ ### The Gap of the Fano Frontier and the Learned Summaries **From the Theoretical Side.** The Fano frontier gives a necessary information constraint, but its optimal error profile may not be realizable with a finite cache. Consider two independent uniform binary records, $X_1$ and $X_2$, queried with probabilities 3/4 and 1/4. The cache contains one bit and is constructed before the query arrives. | View | Information terms for $(X_1,X_2)$ | Recall accuracies for $(X_1,X_2)$ | Weighted accuracy | |---|---|---|---| | Optimal actual cache | (1, 0) bits | (100%, 50%) | 87.50% | | Fano frontier | Approximately (0.7982, 0.2018) bits | Approximately (96.85%, 75.81%) | 91.59% | The actual optimal strategy stores $X_1$ and guesses $X_2$, giving $(3/4)\times1+(1/4)\times(1/2)=87.5$%. A deterministic one-bit cache permits only two reconstructed pairs among four equally likely databases. Randomization cannot improve this optimum. The frontier instead permits the displayed error profile because its Fano information terms, $1 - h_2(e_i)$, sum to one bit. No one-bit encoder-decoder can realize this profile, so the gap reflects looseness of the converse in this example, independently of learning limitations. **From the Empirical Side.** The gap may reflect limited encoder-decoder expressiveness, suboptimal memory allocation across records, insufficient training data, and imperfect optimization. Finite test samples introduce further uncertainty in the measured gap.
Reviewer_XFA7OpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper defines and studies the persistent cache complexity a causal decoder need to retain to answer later queries. The concept of this paper looks interesting but the writing lacks clarify and is full of unfamiliar terminologies without explanation.

Critical strengths
  • The paper offers comprehensive theoretical justification.
  • The paper provides experiments covering formal-language recognition, synthetic associative recall, and Transformer KV-cache retrieval to justify proposed theory.
Critical weaknesses
  • The writing in this paper lacks clarity. For example, the paper does not provide a clear background introduction and does not seem to formally define many terminologies, like "cache states". The wording in this paper seems unfamiliar to AI/LLM researchers, which makes it difficult for the reviewer to connect the proposed theory to language models. Examples include "streaming model" (ln 43), "control parameters" (ln 95), and "fresh randomness" (ln 100).

  • The proposed theoretical framework treats causal decoding (such as LLM Transformer inference) as a task of retrieving answers from prefix tokens, which is not exactly how LLMs work.

Questions for authors
  • Can the authors provide formal definitions of those terminologies includinng "states", "cache states", and "fresh randomness" mentioned in the paper, as well as a background section of the formulation?

  • To help potential readers understand the paper from the perspective of LLM researchers, can the authors explain which specific components or data structures could be used to represent cache states and persistent states and whether the choice of data structures impacts the cache complexity?

  • Could the authors explain how the proposed theory could benefit the design of KV caching strategies for LLMs?

4 comments
AuthorsOpenReview ↗

Response to Reviewer XFA7 (1/2)

We thank the reviewer for the insightful comments. We would like to address the reviewer's concerns as follows.

Definition of states, cache states, and fresh randomness.

The beginning of Sec. 2 defines these objects formally. We agree that the definitions are hard to connect to LLMs as written. The revision will explain them as follows and use the single term cache state throughout, since "state" and "persistent state" refer to the same object.

  • Cache state. All input-dependent information and reusable private randomness carried from token tt to token t+1t + 1. In a Transformer, this is the KV cache at its stored precision, together with any metadata kept by a compression method (e.g., retained-position indices, quantization scales). In an SSM or RNN, it is the hidden state. Activations which are recomputed and discarded within one forward step are excluded. Formally, Ct∈Cn,tC_t\in\mathcal C_{n,t} denotes the cache state after processing tt tokens, where Cn,t\mathcal C_{n,t} is the finite set of possible cache states. The update Un,t:Cn,t−1×Σ→Cn,tU_{n,t}:\mathcal{C}_{n,t-1}\times\Sigma\to \mathcal C_{n,t} is one forward step that writes into the cache, and the output map AnA_n plays the role of the LM head.

  • Cache size and cache complexity. SD(n,t)=⌈log⁡2∣Cn,t∣⌉S_D(n,t)=\lceil\log_2|\mathcal{C}_{n,t}|\rceil is the number of bits needed to write down the cache. A KV cache with kk positions, LL layers, hh KV heads, head dimension dhd_h, and bb bits per scalar has at most 2Lhdhbk2Lhd_hbk bits (Rem. B.14). The cache complexity of a task is the smallest peak cache size over all decoders that solve it.

  • Control parameters (to be renamed public position parameters). These are the input length nn and the current position tt. Information computable from them, such as a RoPE position index, is free. For example, StreamingLLM keeps attention sinks plus a recent window, a set fixed by tt alone, so its identity costs nothing. SnapKV and H2O choose positions from attention scores, so the record of surviving positions depends on the input and is charged as metadata.

  • Fresh randomness. Random bits that one step uses and then discards are free, such as the draw that samples a token at nonzero temperature. A random value reused by a later step, such as a hash seed sampled per request, must be stored in the cache and is charged. If all steps can read a shared random tape for free, we call this the public-coin convention. Prop. 2.5 explains why reusable private randomness must count toward the cache budget: equality at fixed error requires Θ(log⁡m)\Theta(\log m) bits under the private-state convention, whereas freely accessible public coins permit O(1)O(1) bits.

  • Streaming model. Symbols arrive one at a time, and the algorithm can later use only what it chose to remember. Autoregressive inference with a bounded cache is a streaming algorithm whose memory is the cache itself.

  • One-way communication. Alice holds the prefix and sends one message to Bob, who holds the suffix. Theorem 2.1 shows that the cache after token tt plays the role of this message, because all later computation sees the prefix only through the cache.

To give readers a clearer understanding of the field, we will add the background subsection (KV caching, streaming, one-way communication), the terminology table, unified terms, and the KV-design paragraph.

Does the framework assume that LLMs retrieve answers from prefix tokens?

The framework allows any task and any per-token computation. A task TnT_n is an arbitrary function of the full input, and Un,tU_{n,t} may compute anything. We analyze associative recall (Secs. 2.2-2.4) because it isolates long-context lookup. Thm. 2.1(a) and Cor. B.2 apply to arbitrary finite-valued tasks, while Prop. B.3 and Experiment 1 cover non-retrieval tasks: regular languages, equality, and Dyck-(2).

The framework relies on one property that every causal LM has at inference: after token tt, earlier tokens affect later outputs only through the cache. Our model grants the decoder more power than a Transformer has, including unbounded computation per step and free knowledge of nn. Therefore, every real LLM is a special case, and each lower bound applies to it directly. Query processing, chain-of-thought, and multi-token generation all occur after the boundary, so none of them can recover discarded prefix information from the cache alone. Exps. 3 and 4 test these predictions on Ministral KV caches under SnapKV, StreamingLLM, and KIVI.

AuthorsOpenReview ↗

Response to Reviewer XFA7 (2/2)

Which data structures represent cache states, and does the choice matter?

Any per-request memory that persists across tokens is a cache state. For Transformers, examples include a full BF16 KV cache, an evicted cache with its retained-position indices, and a quantized cache with its codes and scales (as in KIVI). Learned summary tokens, an SSM's recurrent state, and raw prompt tokens kept for later recomputation also count.

The data structure leaves the task's cache complexity unchanged, because cache complexity is a minimum over all decoders. Cor. B.2, Thm. 2.2, and Rem. B.15 therefore bound every representation at once. For example, Cor. B.13 requires at least m(1−h2(ε))m(1-h_2(\varepsilon)) bits from any pre-query cache that answers every query on mm binary records with error at most ε\varepsilon, regardless of what those bits encode.

The data structure does determine how close a design comes to that bound. Total persistent bits are the invariant quantity, and caches with equal position counts can differ widely. In Experiment 4, 4-bit KIVI keeps every position in 31.1% of the Full-KV memory and preserves 96% of Full-KV-correct answers. At 2 bits, it keeps the same positions in 18.7% of the memory and preserves 37.1%. In Experiment 2, a grouped codebook that encodes records jointly beats literal retention at equal bit budgets for binary records under uniform queries, at every tested ρ<1\rho<1.

How can the theory inform KV-cache design?

We give three implications here and will include them in the revised manuscript.

  1. Budget and compare caches in bits. Rem. B.14 converts a task requirement into a lower bound on the required number of KV slots. given the model shape (L,h,dh)(L,h,d_h), precision bb, and metadata MM. Eviction, quantization, and merging should be compared at equal persistent bits, metadata included.

  2. Allocate bits by query probability. For binary records, Thm. 2.2 profile ai∗=1/(1+2λπi)a_i^{\ast}=1/(1+2^{\lambda\pi_i}) gives lower error to more probable queries. For fixed literal retention, Cor. B.10 proves that keeping the ss most probable records is optimal and gives its accuracy in closed form. Heavy-hitter and attention-based eviction can be read as heuristic estimates of π\pi, and these results quantify what such skew can buy.

  3. Measure headroom. Under the assumptions of Thm. 2.2, The Fano ceiling (App. C.2.1) bounds the accuracy any query-independent cache can reach at a given budget and query law, so a method's gap to it is its remaining headroom. For binary records under uniform queries, Thm. 2.2 requires m(1−h2(eˉ))m(1-h_2(\bar e)) bits for average error eˉ\bar e, so no query-independent cache reaches a fixed error below 1/2 with sublinear memory.

Additionally, our results can inform further theoretical research and empirical evaluation. We respectfully invite the reviewer to read the "Scope and Contributions" section of our response to Reviewer bggA.

My concerns are addressed. I have raised my rating to 3. Since I don't have enough expertise to check the correctness of every piece in the paper, my confidence remains 1.

We thank the reviewer for the thoughtful feedback and positive response to our rebuttal.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.