- 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 and each value has the form for some specific set of . 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 with non-negative components? Surely there are better representations of , 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 with non-negative rank? Why not choose a better representation (for example just normal rank)?
2 comments
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 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)) arithmetic operations. Its computation operates on the m+s dictionary rows and R 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). 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/502. The signed rank-three construction and this positive-component obstruction together make the representational cost precise.