acceptodds
Under review as a conference paper at ICLR 2027

When Can Dictionary Reuse Compress a Composable Attention Cache?

Abstract

A compressed attention prefix must save storage while remaining correct when new tokens are appended. Reusing key and value components offers one route, but it also requires preserving which component pairs occur and how much attention mass they carry. We study additive dictionaries with an occupancy matrix and give an exact contraction that avoids expanding all pairs. Under distinct combined keys, the minimum number of fixed positive product components needed for exact composition is the nonnegative rank of occupancy. A full product of unit-norm tokens has an exact state with dictionary rows, whereas every proper raw-value subset has uniform error at least on a specified query ball. Conversely, four-cycle occupancy requires four positive components even on sixteen finite query/tail tests at nonzero tolerance. A joint perturbation bound separates occupancy and dictionary errors. Fixed-dictionary query continuation verifies the predicted covariance derivative. On 540 saved-cache cases, increasing the positive component count reduces error but quickly exhausts the storage saving: exact pair indices cost less and retain exact occupancy. Ordinary clustering still achieves lower output error. The results characterize when dictionary reuse supports composable compression and which information must survive the reduction in storage.

Primary area:
learning theory
Keywords:
KV cache compression, composable attention, dictionary reuse, nonnegative rank, product factorization, attention approximation

Reviews

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

The authors study a specific setting of cache compression: when each key has the form μj+xi\mu_j + x_i and each value has the form νj+yi\nu_j + y_i for some specific set of μj,xi,νj,yi\mu_j, x_i, \nu_j, y_i. In this setting the authors have results that (1) bound the time required to compute attention output of a single query from a compressed cache, (2) a (very restricted) lower bound on cache compression, as well as exhibits some examples where the cache cannot be compressed too well (e.g. either requiring many tokens to be stored, or high-rank representations to be stored). The authors also consider an approximate version of cache compression: i.e. when the keys and values are not exactly additive combinations of the above compressed form, but are approximately close to that form.

Critical strengths

The authors study cache compression, which is a reasonable problem to study and one of practical importance.

Critical weaknesses

The results are not very strong. First of all, the model seems unmotivated: why should we expect all keys and values to have this additive form where each component comes from a fixed set? This seems very unnatural.

Even within this unnatural model, the results are not very strong. Theorem 1 is essentially the trivial reconstruction algorithm. Theorem 2 shows a very weak lower bound: why should we only represent WW with non-negative components? Surely there are better representations of WW, and if not, the authors should obtain a more general lower bound.

The presentation of the paper is very hard to follow for me. The text is filled with jargon and is technically terse. For example, Theorem 1 bounds "prediction cost", a term that is undefined up to that point. With effort, one can infer that this is the time required to compute attention for the query, but the fact that this is undefined by the authors makes the paper unnecessarily difficult to read. This is even the first result of the paper, so the rest of the paper is even harder to read.

Questions for authors

What is the motivation behind representing keys in this way?

Why do we only care about representing WW with non-negative rank? Why not choose a better representation (for example just normal rank)?

2 comments
AuthorsOpenReview ↗

Reviewer B5qX

The motivation for the additive representation is to reuse codebook entries across tokens while retaining the pairings needed for attention. Split each key/value vector into coordinate blocks and fit a codebook to each block. Each token is then represented by the sum of two reusable dictionary entries, with its pair of assignments retained. This is the construction used in the saved-cache study. Theorem 5 quantifies the effect of approximate key and value reconstruction, so the analysis also covers fitted dictionaries. The model makes it possible to ask how much storage the reuse saves and which pairing information is necessary for correct attention.

Pairing information changes the answer even with the same dictionaries. If two left and two right entries occur only in diagonal pairs, multiplying their marginals also assigns mass to the absent off-diagonal pairs. This changes the prefix partition and hence its weight when an exact tail is appended. The occupancy matrix retains the actual pair weights. Theorem 1 contracts these weights through the factors to obtain both the numerator and partition in O((m+s)(d+p+R))O((m+s)(d+p+R)) arithmetic operations. Its computation operates on the m+sm+s dictionary rows and RR factor columns. We will define “prediction cost” at first use as the arithmetic cost of evaluating one query from the stored prefix state and exact tail.

Your question about ordinary rank points to a different representation of the same occupancy matrix. Page 4 gives an exact signed rank-three contraction for the four-cycle, whose nonnegative rank is four. Appendix C.2 supplies the signed factors, and Appendix F checks the exact attainment with rational arithmetic. Thus the choice of representation has a concrete, demonstrated effect on the required component count.

The positive product class has an additional operational property. Every active nonnegative factor column defines a component with positive mass that can be normalized separately and combined through its log mass. Theorem 2 characterizes the exact number of such components. With fixed dictionaries, distinct combined keys and a query domain containing an open set, preserving attention after every exact tail identifies the occupancy coefficients, giving the minimum count rank⁡+(W)\operatorname{rank}_+(W). Theorem 4 strengthens this exact characterization for the four-cycle by giving sixteen fixed query/tail tests on which every three-positive-component representation incurs error greater than 1/5021/502. The signed rank-three construction and this positive-component obstruction together make the representational cost precise.

Thanks for the response. It still seems to me that the motivation for the additive representation of data is not particularly strong. I will maintain my score.

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

This paper studies whether reusing additive key/value dictionaries can compress an attention prefix while keeping it correctly composable with an appended exact tail. It uses a nonnegative occupancy matrix to represent the pairing of dictionary components and provides an exact contraction formula. Under explicit assumptions on the fixed dictionaries and query domain, it uses nonnegative rank to characterize the minimum number of positive components. It also provides structured separation results and perturbation bounds. Mechanism checks and 540 saved GPT-2 head/query cases show that restoring exact occupancy can improve the fitted product state. However, with the same dictionaries, exact pair indices require less storage than all tested factor encodings, and ordinary clustering achieves lower aggregate head-output error. The product state is currently evaluated on fixed caches, and has not been tested through end-to-end model generation.

Critical strengths

The paper clearly explains why a prefix summary must preserve both the unnormalized mass and the normalized output to compose correctly with later tokens. The exact contraction and the nonnegative-rank characterization make this requirement precise within the chosen representation class. The full-product separation and the four-cycle obstruction under finitely many queries show both the potential and the limits of this framework. Together, these results provide a useful conceptual understanding of composable dictionary reuse (Sections 2–6).

The perturbation analysis separates occupancy error from key/value reconstruction error, while the fixed-dictionary experiments keep the cross term in the total squared error. These treatments help explain what restoring occupancy can fix and why it cannot remove dictionary reconstruction error (Sections 7–8; Appendices D, E, and H).

Critical weaknesses

These theorems only characterize a restricted representation class, where the dictionaries are fixed and the factors are nonnegative. The construction used for separation from original-value subsets is structured, and its dimension and query radius grow with the problem size. These assumptions leave an open question: how often does such favorable structure appear in real caches? The 540 cases cover only three 30-token contexts and 36 fitted GPT-2 first-layer prefix/head states, rather than 540 independent contexts. Thus, the relevance of this theoretical characterization to a wider range of settings is not sufficiently demonstrated (Sections 5 and 8; Appendix G).

With fixed dictionaries, exact pair indices achieve an RMS error of 0.18584 using 14,374 bytes. In comparison, rank-one factors achieve 0.20828 using 14,456 bytes, and rank-three factors achieve 0.19136 using 14,680 bytes. Therefore, in the reported aggregate storage–error comparison, the exact-index baseline uses less storage and achieves lower error than these fitted factors. Joint centroids also achieve a lower error of 0.1272 within the same budget limit. These experiments verify the mechanism of positive-factor encoding, but do not yet establish a competitive use case for it (Table 1; Appendix H, Table 3).

Questions for authors

Could the authors clarify under what conditions accurate additive dictionaries and a storage-efficient occupancy representation are expected to be achieved at the same time? Could they support this explanation with analysis or a state-by-state breakdown of the existing 36 states? Specifically, what do these results tell us about dictionary reconstruction quality and the achievable level of occupancy compression, respectively?

Why are codebook coordinates that are known to be zero still stored and explicitly counted in the storage cost? If only active coordinates were stored, how would the selected dictionary size change under the 16,392-byte budget? How would this affect the comparison with clustering?

2 comments
AuthorsOpenReview ↗

Reviewer 2q32

Your question about the known zero coordinates changes the storage comparison: storing only active coordinates permits larger dictionaries and substantially improves the measured error under the same 16,392-byte budget. We refitted the original 36 prefix/head states from three contexts with the original deterministic initialization and 20 Lloyd iterations. The indexed representation now fits 15 entries per dictionary and achieves RMS error 0.13473 at 15,398 serialized bytes, compared with 0.18584 for the original seven-entry dictionaries. Its per-state RMS improves in all 36 states, and its error improves on 522 of the 540 individual queries.

RepresentationSerialized bytesOutput RMS
Original m7 dictionaries with exact indices14,3740.18584
Active-coordinate m14 dictionaries with dense occupancy15,9120.14080
Active-coordinate m15 dictionaries with exact indices15,3980.13473
15 joint centroids15,4880.12722

The original accounting used dense codebook arrays, including the embedded zeros. With the fixed coordinate layout, each dictionary entry needs 64 float64 coordinates. Dense occupancy then costs 8(128m+m2)+88(128m+m^2)+8 bytes, giving a maximum m=14 under the budget. Thirty one-byte pair indices and an eight-byte coverage count instead give 1024m+381024m+38 bytes, allowing m=15. We serialized and decoded these layouts and checked their attention outputs against explicit token expansion. The comparison keeps the original convention for shared tail and container costs.

The state-level results help separate dictionary reconstruction from occupancy storage. Across the 36 states, the mean of the key coordinate-RMS values falls from 0.07471 to 0.05098, and the corresponding value reconstruction mean falls from 0.13910 to 0.09455. The m15 states occupy 18–25 of the 225 possible pairs, averaging 20.83. Exact indexing therefore combines the larger dictionaries with inexpensive, lossless occupancy in these short caches. With the original dictionaries held fixed, restoring exact occupancy already improved 464/540 outputs over independence. Enlarging the dictionaries addresses the remaining reconstruction term directly. The full per-state reconstruction, occupancy and output measurements accompany the new results.

More generally, accurate additive reconstruction and economical pairing storage are jointly favorable. A positive factorization with RR components costs R(m+s)R(m+s) occupancy scalars, and beats dense occupancy when R(m+s)<msR(m+s)<ms. Its cost must also be compared with the indexed or sparse encoding of the observed pairs. Dense, highly repeated occupancy with a small positive rank is a favorable regime for factors. The full-product construction realizes it exactly with one component. The observed short-cache occupancies favor exact indexing, which the updated comparison uses to improve the dictionary representation at the same budget.

Thanks for your rebuttals. I choose to maintain my score.

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

The paper studies when additive dictionary representations can compress attention caches while preserving correct composition with newly appended tokens. It represents keys and values as sums of dictionary components and uses an occupancy matrix to record the observed component pairings. The authors conducted experiments on 540 saved GPT-2 head/query cases to validate the proposed mechanisms.

Critical strengths

While the paper provides theoretical results for a restricted dictionary representation, I do not find sufficient evidence that this representation offers meaningful advantages for realistic KV cache compression.

Critical weaknesses

The practical evidence is limited. The saved-cache evaluation uses only three short GPT-2 contexts and first-layer attention heads. The product representations are substantially less accurate than the stronger clustering and local-summary controls. The positive factorization also loses most of its storage advantage as the component count increases, while explicit pair indices provide a cheaper exact occupancy representation in the evaluated setting. The current experiments do not establish a practical advantage for the proposed method.

The evaluation does not measure whether the compressed representation is useful for actual language model inference. The experiments mainly measure attention head-output error on 540 saved cases from three short GPT-2 contexts, without evaluating downstream task performance or generation quality. Head-output error alone does not show whether the model's inference ability is preserved or not. The error could accumulate and affect the inference significantly.

The paper motivates dictionary reuse as a storage-efficient representation and derives an arithmetic complexity bound, but provides no latency or throughput evaluation.

The theoretical results rely on a restricted representation class, and the connection to realistic KV caches is insufficiently established. The strong separation in Theorem 3 uses a highly structured construction with exact additive keys and values. The paper does not establish how frequently comparable structure occurs in actual model caches or under what conditions this advantage is likely to be useful.

Questions for authors
  1. How does the quality of additive dictionary reconstruction vary across different models, layers, and prefix lengths? Is there evidence that real KV caches contain sufficient additive structure to make the theoretical compression advantage practically relevant?
  2. Can the authors identify realistic occupancy patterns or operating regimes in which positive factorization is preferable to explicit pair-index or sparse occupancy encoding, considering both prediction storage and output error?
  3. Can the authors provide latency or throughput evaluation? My main concerns relate to the significance and practical applicability of the proposed method, while the author didn’t provide enough experiment results to justify the efficiency they claimed. Addressing them would likely require substantial additional evidence beyond clarification during rebuttal.
1 comment
AuthorsOpenReview ↗

Reviewer 6gdU

Whether dictionary reuse is useful depends on how much reconstruction error it introduces and how much storage its pairings require. The paper characterizes when dictionary reuse yields an exact composable attention state and what can prevent that compression. Theorem 2 identifies occupancy nonnegative rank as the exact positive-component complexity under its dictionary and query assumptions. Theorem 3 constructs an exact state for r2r^2 tokens using 2r2r dictionary rows, while every proper original-value subset has uniform error at least 1/41/4 on the specified query ball. Theorem 4 gives a finite-query obstruction caused by dependent occupancy. These results identify both the structure that enables reuse and the pairing information that must survive compression.

To examine reconstruction under a storage budget, we use saved caches from three short contexts, comprising 36 first-layer GPT-2 prefix/head states and 540 queries. In these caches, packing the fixed active coordinates and refitting 15 entries per dictionary reduces RMS error from 0.18584 to 0.13473 at a serialized indexed payload of 15,398 bytes. The 15-centroid control gives 0.12722 at 15,488 bytes. The refitted dictionaries improve per-state RMS in all 36 states and improve 522 of the 540 individual queries over the original dictionaries. This directly shows how the physical dictionary layout changes the quality achievable within the stated budget.

Positive factors require R(m+s)R(m+s) stored scalars, so small positive rank and sufficiently many repeated pairings can make this cheaper than dense occupancy or token-by-token pair indices. The full-product construction has R=1R=1 and realizes that saving exactly. In the saved 30-token prefixes, the refitted dictionaries occupy only 18–25 pairs per state, and one-byte exact indices provide an economical occupancy representation. The paper's representation analysis supports this choice of encoding as well as the positive-factor case. Theorem 1 gives the per-query arithmetic bound O((m+s)(d+p+R))O((m+s)(d+p+R)) for the factorized representation, complementing the measured storage and output error. We have not measured latency or throughput, or generation quality for the product state.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.