Source-linked AI summary

Read What Matters: Query-Adaptive Quantization for KV Caches

Siddharth Bhandari, Lucas Gretta, Krishna Balasubramanian, Shiva Kasiviswanathan

arXiv:2610.11245v1cs.LGcs.CLcs.PF

TL;DR

KV-cache entries are stored before future queries are known, although different queries may need precision in different places. ReadKV stores progressive codes and allocates key and value prefixes query by query. Across six base models, it stays within 0.66% of uncompressed C4 perplexity and improves on fully reading a four-bit cache at the same payload-read budget.

  • Problem

    KV-cache entries are written once but read repeatedly under changing queries, and each query may depend on different key dimensions and value tokens.

    Source: §1 · p. 1
  • Method

    ReadKV separates stored bits from per-query read bits and uses a progressive code with query-selected key prefixes followed by attention-selected value prefixes.

    Source: §1 · p. 1, §7 · p. 14
  • Results

    Across six base models, ReadKV (W = 8, R = 4) stays within 0.66% of uncompressed C4 perplexity and improves over fully reading a four-bit cache at the same payload-read budget.

    Source: §7 · pp. 14–15
  • Takeaways & Limitations

    Retaining more bits than each query fetches targets settings where the cache, rather than the weights, dominates bytes moved per decoding step.

    Source: §1 · p. 1, §7 · p. 15

    The A10G study measures a single-layer workload and does not establish an end-to-end serving advantage.

    Source: §7 · p. 15

Abstract

from arXiv · show

KV-cache entries are stored before their future queries are known, but each decoding query needs precision in different places. We study this mismatch using separate budgets for retained bits and bits fetched per query. ReadKV stores each key and value in a progressive code whose prefixes support different reconstruction precisions. For each query, it allocates key-channel prefixes using the query, computes attention from the reconstructed keys, and then allocates value-token prefixes using that attention. Stored entries remain unchanged. Each stage optimizes a calibrated distortion objective under a fixed budget; we prove exact allocation under diminishing refinement gains and relate these objectives to attention-output error. We also exhibit a finite-dimensional attention family where query-dependent access strictly outperforms every query-independent reader at the same read budget, even with unrestricted competing encoders and decoders. Across six base models, reading four bits on average from an eight-bit cache increases C4 perplexity by at most 0.66%, using about one quarter of the logical reads and half the retained capacity of a 16-bit cache. It is consistently more accurate than storing and fully reading four bits at the same payload-read budget. Retaining more bits than each query fetches is aimed at long-context decoding, where the cache bytes moved per step, rather than the weights, dominate cost. Long-context question answering and retrieval on two instruction-tuned models provide additional quality evidence. On the tested 8K-token, batch-one, single-layer workload on an NVIDIA A10G, a restricted eight-bit ReadKV reader with a two-bit mean payload-read budget has 39% lower latency than the tested TurboQuant codec.

1 Introduction

KV entries are written before future queries are known, yet each query may need precision in different key dimensions and value tokens. ReadKV separates stored precision from per-query reads, using query-adaptive prefixes to reduce payload reads while preserving refinements for later queries.

1 Introduction

  • KV-cache reads recur under changing queries, while a query may depend mainly on some key dimensions and attend to only a few value tokens.This motivates fetching query-specific cache information at each decoding step.Source: §1 · p. 1
  • ReadKV makes scalar reconstruction depth a query-time access decision, unlike approaches that reduce or vary stored precision or select features and tokens for the current query.The introduction identifies precision tiers with selective bit-plane retrieval as the closest systems precedent [Xie et al., 2025].Source: §1 · pp. 1–2
  • Across six base models, ReadKV (W = 8, R = 4) stays within 0.66% of uncompressed perplexity and beats fully reading a four-bit cache at the same payload-read budget.The introduction also reports query-answering and retrieval evidence, plus a separate A10G single-layer comparison against a fused quantized codec.Source: §1 · p. 2
  • ReadKV stores progressive key and value codes, lets each query choose prefixes without rewriting entries, and separates stored bits W from average payload bits read R.The query chooses key prefixes; attention from reconstructed keys then determines value prefixes.Source: §1 · pp. 1–2, Figure 1 · p. 2

2 Partial-Read Cache Model

The partial-read cache model asks how well a reader can recover a query–key score when the key is stored before the query arrives and the read budget is smaller than the stored record. It formalizes separate storage and read budgets and distinguishes access rules by what may guide bit selection.

2 Partial-Read Cache Model

  • The model treats a cached key as x, a later query as y, and their inner product x⊤y as the unscaled attention score to estimate.The encoder sees x but not y; the reader receives y and requests selected record bits, and the decoder estimates the score from the returned bits.Source: §2 · p. 3
  • Storage rate W and read rate R bound bits per record and fetched bits per query, respectively, as global budgets rather than per-coordinate quotas.For example, W = 8 and R = 2 permit an 8d-bit record but only 2d fetched bits per query.Source: §2 · p. 3
  • Reader classes differ in whether address choices can use the current query, previously returned bits, or both, while sharing the same storage and read budgets.They range from query-oblivious fixed patterns and query-independent branching to staged and fully branching readers.Source: §2 · p. 3, Table 1 · p. 3
  • The model compares complete encoder–reader–decoder protocols under each access class, with protocol randomness averaged for a fixed input pair.The separation results use the same loss on explicit restricted input families.Source: §2 · pp. 3–4

3 Query-Adaptive Cache Design

ReadKV stores progressive codes whose prefixes offer different reconstruction precisions, then uses a two-stage reader to allocate key and value reads for each query. A prefix allocator spends each stage’s fixed budget on the largest positive predicted distortion reductions.

3.2 Two-Stage Query-Adaptive Reading

  • The query selects key-channel prefixes; reconstructed keys produce attention weights that select value-token prefixes in a second read batch.Each batch’s addresses are fixed before its bits are returned, and the final decoder reconstructs values to produce the attention output.Source: Figure 2 · p. 4, §3 · p. 4, §3.2 · p. 5

3.1 Progressive Cache Representation

  • ReadKV stores each scalar as a path in a binary quantization tree, where progressively longer prefixes yield finer reconstructions from the same unchanged code.The implementation uses a Gaussian Lloyd tree, and shared KV bits are counted once even when multiple query heads use them.Source: §3.1 · p. 4

3.3 Prefix Allocation Under a Read Budget

  • For each item, ChooseDepths repeatedly adds the prefix bit with the largest positive weighted reduction in calibrated distortion, stopping at its budget or when no positive gain remains.Key and value stages use separate fixed integer budgets; a key-channel increment reads T bits, while a value-token increment reads dh bits.Source: §3.3 · pp. 5–6
  • The allocator optimizes within each key or value stage, but the K/V budget split is supplied as an input rather than optimized.Its separable objectives omit cross-terms between reconstruction errors.Source: §3.3 · pp. 5–6

4 Performance Guarantees for Partial Reads

The section gives finite examples where query-dependent reading outperforms query-independent access, then analyzes what ReadKV’s allocation optimizes and how its objectives relate to attention-output error. These guarantees are scoped to specified query families and calibrated objectives.

4.1 Key-Score Separation

  • For deployed depth-eight code with w=8d and r=2d, transformed-sparse queries with k≤⌊d/4⌋ yield a certified ratio above 155/k, exceeding 4.85 at d=128 and k=32.The result is scoped to transformed-sparse queries; the code does not dominate every query-oblivious protocol on the full unit ball.Source: §4.1 · p. 7

4.2 Two-Stage Attention Separation

  • For every m ≥1, the two-stage separation factor exceeds 2.40 and exceeds 9.52 at m=128, where W=8 and realized R≈2.004.The comparison is against query-independent readers, even when competing encoders and decoders are unrestricted.Source: §4.2 · p. 8

4.3 Allocation and Attention-Error Guarantee

  • For finite conversion factors, the calibrated objectives bound attention-output error deterministically without assuming independence among queries, keys, values, or quantization.The certificate uses factors for calibration mismatch, residual interactions, and value scale, evaluated at the realized reconstruction.Source: §4.3 · p. 9
  • Under nonincreasing, nonnegative distortion gains, ReadKV finds the best legal integer prefix schedule for keys and, given reconstructed-key attention, for values.This is stagewise optimality for the calibrated objectives, not joint minimization of true attention-output error.Source: §4.3 · p. 9

5 Language-Model Evaluation

ReadKV is evaluated on C4 language modeling and long-context QA, with storage and read budgets varied to compare quality, logical reads, and retained capacity. A separate single-layer GPU test measures latency and traffic under a restricted reader.

5 Language-Model Evaluation

  • The evaluation uses nominal storage/read settings (4, 2), (8, 2), and (8, 4); the flexible reader’s integer K/V split is selected on development data for each model and rate, then frozen before test.For C4 language modeling, each model is evaluated on 32 held-out 2,048-token documents, with separate calibration and development data; tokenizers differ, so comparisons are within each model.Source: §5 · p. 10
  • With the first and last two layers uncompressed, ReadKV (8, 4) has lower perplexity and slightly fewer logical reads than TurboQuant K4/V4 on all six models, while retaining more KV storage.Without those exemptions, it improves over the Full Reader’s 1.34–3.44% PPL increase at the same four-bit payload-read budget.Source: §5 · p. 10
  • Lower-read settings are less consistent across model families: (8, 2) stays within 3.9% PPL increase on Qwen, versus 6.27–11.24% on Yi, DeepSeek, and Mistral.The quarter-capacity (4, 2) setting loses 5.43 F1 points on Qwen 2WikiMultihopQA, while all-layer (8, 2) and (8, 4) QA losses stay below 1.78 and 1.38 points across both prompt limits.Source: §5 · pp. 10, 13
  • 0.7%: ReadKV (8, 4) stays within 0.7% of Dense on C4 across six models, using about a quarter of its logical reads and half its KV capacity.Table 2 reports C4 results on 32 held-out 2,048-token documents per model, with three transform seeds where available.Source: Table 2 · p. 11
  • At a 7,500-token prompt limit, ReadKV (8, 2) loses at most 1.46 F1 points across six QA conditions while using about 13% of Dense logical reads.It scores higher than KIVI in all six conditions and has mixed results against SparQ.Source: Table 3 · p. 12, Figure 3 · p. 13

5.1 GPU Evaluation

  • At an 8,192-token context and batch size one on an NVIDIA A10G, ReadKV (8, 2) latency is 39% lower than the tested TurboQuant codec, while Dense is 45% lower than ReadKV.Profiling shows 62–65% fewer DRAM read bytes and 20–31% less total traffic than TurboQuant; these measurements isolate single-layer decode-time codec costs.Source: §5.1 · p. 13, Table 4 · p. 14

6 Related Work

Related work spans fixed-rate quantization, adaptive retention, and query-dependent cache retrieval. ReadKV combines query-time access with progressive scalar reconstruction depths, building on successive-refinement coding while adapting it to partial-read KV access.

6 Related Work

  • Fixed-rate quantizers reduce the representation retained for every future query, while other methods vary resident precision using attention history or quantization sensitivity.Examples include KIVI, KVQuant, TurboQuant, QAQ, MiKV, ZipCache, PM-KVQ, MixKVQ, and RDKV [Liu et al., 2024, Hooper et al., 2024, Zandieh et al., 2026; Dong et al., 2024, Yang et al., 2024, He et al., 2024, Liu et al., 2026, Zhang et al., 2026b,a].Source: §6 · p. 14
  • Query-adaptive retrieval selects cache content using the current query, whereas ThinK prunes the retained key cache after an observation window.SparQ selects key features before retrieving values, Quest ranks pages, and Loki uses low-dimensional key information to select tokens [Ribar et al., 2024, Tang et al., 2024, Singhania et al., 2024; Xu et al., 2025].Source: §6 · p. 14
  • ReadKV assigns multiple possible reconstruction depths to every stored scalar rather than making only a feature, token, or page inclusion decision.Its closest systems precedent, Xie et al. [2025], retains KV precision tiers and selectively retrieves floating-point bit planes for ranked pages.Source: §6 · p. 14
  • ReadKV uses a nested nonuniform scalar code and allocates each query’s read budget first across key channels, then across value tokens using reconstructed attention.Progressive descriptions and successive refinement provide the coding background [Equitz and Cover, 1991, Rimoldi, 1994]; the paper frames its contribution as their use in a causal partial-read KV protocol with finite separation and attention-error guarantees.Source: §6 · p. 14

7 Discussion

ReadKV addresses the KV cache’s write-once, read-many pattern by preserving detail in a progressive code and letting each query fetch only selected refinements. The paper connects this access pattern to theoretical separations and quality–read tradeoffs, while identifying limits on the current theoretical and systems evidence.

7 Discussion

  • The cache is written once but read repeatedly under changing queries, so preserved detail need not all move on every decode step.ReadKV allocates key precision from the query and value precision from reconstructed attention, and relates stagewise objectives to attention-output error.Source: §7 · p. 14
  • The theoretical separations concern explicit input families, and the attention certificate depends on calibration and residual-correlation factors.The A10G study shows lower single-layer latency and DRAM traffic than the tested fused quantized codec, but does not establish an end-to-end serving advantage.Source: §7 · p. 15

AI Use Statement

The authors describe generative-AI assistance with research and manuscript tasks, while retaining responsibility for the final work. The appendices map technical topics to supporting material, including a separate accounting of cache capacity, writes, and reads.

AI Use Statement

  • Generative AI tools assisted with theoretical analysis, proof checking, experiment design and implementation, result interpretation, literature searches, and manuscript preparation.The authors state that they are responsible for the final text, claims, code, and other artifacts.Source: AI Use Statement · p. 15

Appendix Organization

  • The appendix map directs readers to proofs, allocation results, quality controls, and GPU timing and traffic measurements.It identifies Appendix E for allocation and attention-error proofs, Appendix F for quality evaluation, and Appendix G for GPU measurements.Source: Appendix Organization · p. 18

A Storage and Traffic Accounting

A.1 Task-Table Cost Accounting

The accounting separates cache capacity, logical reads, and physical traffic, while the reuse model shows when additional retained precision can be offset by reduced reads. ReadKV’s query-adaptive access is positioned against related coding, precision-allocation, and retrieval approaches.

A.1 Task-Table Cost Accounting; A.7 Capacity and Physical Traffic

  • Task tables report persistent-cache capacity and logical reads separately; neither includes temporary workspace, and logical counts do not determine physical traffic.Capacity uses fixed reference cache states, while logical reads include payload and fetched supporting state; actual traffic also depends on implementation and device effects.Source: §A.1 · pp. 18–19, §A.7 · p. 21

A.2 Payload-Only Cache-Reuse Model; A.3 Equal Read Budgets

  • With equal read budgets, storing extra bits cannot reduce total logical traffic, but its added writes can be small relative to repeated reads.For W=8, W0=R=4, N=8192, and L=128, added write traffic is approximately 0.79% of common payload-read traffic; reuse, not prompt length alone, amortizes writes.Source: §A.2 · p. 19, §A.3 · p. 20

A.4 Reduced Read Budgets

  • When storage exceeds the fixed-rate baseline and ReadKV also reads fewer bits, it has lower total logical traffic above a decode-length crossover.For an empty-cache sequence, the condition is L > 1 + 2(W − W0)/(W0 − R); the derivation sums each entry’s actual reuse count.Source: §A.4 · p. 20

A.5 Equal Storage

  • At equal storage, reducing the read budget lowers repeated-read traffic, but the acceptability of the resulting approximation depends on the downstream task.The allocation theorem does not claim that a partial prefix reproduces the full-depth reconstruction.Source: §A.5 · p. 20

A.6 Capacity, Bandwidth, and Batching

  • In the bandwidth-bound throughput model, fetched bits affect throughput directly, while retained bits matter through the weight-to-cache-memory ratio.The model favors reading less than is retained when caches dominate bytes moved per step, as in long contexts and large batches.Source: §A.6 · pp. 20–21
  • Modeled throughput relative to Dense is 4.9 for all-layer ReadKV (8, 2), versus 3.3 for all-layer ReadKV (8, 4), under the stated bandwidth-bound model.The (8, 4) configuration is within 0.66% of Dense PPL; these are model outputs, not measurements.Source: §A.6 · p. 21

B Related KV-Cache Methods; B.1 Nested Codes; B.2 Attention-Guided Precision Allocation; B.3 Query-Adaptive Cache Access

  • ReadKV applies progressive nested codes to KV entries and adapts read depth per query, unlike methods that change resident precision or retrieve selected features or tokens.Prior work includes progressive weight representations, attention-guided retained precision, and query-adaptive retrieval; ReadKV uses the current query for key prefixes, then reconstructed attention for value prefixes.Source: B Related KV-Cache Methods · p. 21, §B.1 · p. 22, §B.2 · p. 22

B.4 Fixed-Rate Quantization

  • Fixed-rate quantization baselines require method-specific accounting, and matching read budget and matching storage test distinct comparisons.KIVI and KVQuant use different quantization and auxiliary-state choices; TurboQuant comparisons must identify the variant and count auxiliary data.Source: §B.4 · p. 23

B.5 Bit-Allocation Methods

The paper treats bit allocation as a finite-prefix scheduling problem and formalizes access protocols under a common storage and probe budget. Its hierarchy results relate the available query dependence and batching to worst-case risk.

B.5 Bit-Allocation Methods

  • ReadKV’s allocation schedule applies classical diminishing-return selection to query-weighted key channels and value tokens over finite code prefixes.The paper identifies what is allocated, how the current query defines weights, and which prefixes are available as the problem-specific elements.Source: §B.5 · p. 23

C.2 Formal Access Model

  • The formal access model charges stored one-bit cells and probes, while preprocessing and decoder computation are free.Object-specific information belongs in the record; public layout state is fixed independently of the input pair.Source: §C.2 · p. 23
  • Query-independent branching may use previously returned payloads to select later addresses, but its access path and stopping rule cannot use the query.A staged reader instead chooses batches using the query, and later batches may also use earlier returned values.Source: §C.2 · p. 25
  • For at least r stages, staged and branching readers have the same optimal risk; with zero reads, all access classes have risk one.The access hierarchy orders minimax risks in the reverse direction as protocol classes expand.Source: §C.2 · p. 25

C.3 Full-Read Limit

When the read budget covers the entire stored record, access constraints no longer distinguish reader classes. The following section introduces the finite progressive scalar codec used in analysis and experiments.

C.3 Full-Read Limit

  • If r ≥ w, every access class has the same risk as full-message decoding, including for randomized protocols.The paper notes that no further information is gained by allowing R > W in the matched cell model.Source: §C.3 · p. 26

D Progressive Codec and Distortion Model

  • The next section records finite properties of the progressive scalar codec used by Algorithm 1 in analysis and experiments.This is the stated scope of the codec and distortion-model section.Source: D Progressive Codec and Distortion Model · p. 26

D.1 Progressive Scalar Codec

This section specifies a progressive scalar codec and develops calibrated allocation objectives for query-adaptive key and value prefix reads, including exact allocation guarantees and connections to attention-output error. It also examines finite-dimensional separations and limits on query-adaptive superiority, distinguishing idealized comparisons from guarantees for the measured codec and testing allocation scores in language-model experiments.

D.1 Progressive Scalar Codec

  • The deployed scalar code uses nested binary-tree prefixes whose shared centroid tables provide coarser reconstructions, with depth-eight standardized distortion 0.00004795.Each split reduces probability-weighted squared reconstruction error, and each child stores its conditional mean.Source: §D.1 · p. 26

The positive depth-one centroid and the depth-two endpoint reconstruction satisfy

  • The deployed gains satisfy Δ1 > ··· > Δ8 > 0, and the depth-eight pointwise error is below 0.0097; (Q2(1) − 1)^2 lies between 0.26052610 and 0.26052612.The inequalities are verified from the finite stored table; the pointwise error bound is for the standardized interval.Source: The positive depth-one centroid and… · p. 27, §D.1 · p. 27

D.2 Diagonal Surrogate

  • The key surrogate approximates conditional residual second moments diagonally, while the value surrogate neglects cross-token terms; experiments use standardized value units rather than physical scales.The allocation theorem optimizes these declared surrogates, while the complete causal language-model experiment tests their behavior.Source: §D.2 · p. 28

E Proofs of the ReadKV Performance Guarantees

  • The proof sequence establishes finite-dimensional separations, exact stagewise prefix allocation under diminishing gains, attention-output bounds, and a guarantee for the complete ReadKV procedure.Continuous allocation and integer rounding are auxiliary comparisons, not ingredients in the three main guarantees.Source: E Proofs of the ReadKV Performance… · p. 28

E.1 Finite-Dimensional Separations

  • The finite-dimensional converse proofs use an entropy–MMSE inequality to bound estimation error from a mutual-information limit.The stated bound applies to a uniform source on [−1, 1]^n and an observation with information at most b_info log 2.Source: §E.1 · p. 28

E.1.1 Key-Stage Separation

  • The bound permits payload-dependent branching and early stopping, does not use the write budget, and remains valid for every fixed finite binary record length under the same at-most-r probe limit.Source: §E.1.1 · p. 30

E.1.2 Two-Stage Attention Separation

  • In the two-stage attention construction, query-adaptive reading identifies the high-attention token and yields normalized squared error at most (pϵ8 + ρ)^2, while the converse bounds query-independent transcripts by r bits.The value schedule reads all eight levels of the high-attention token before any level of the other token; the converse applies an entropy–MMSE bound to the value vectors.Source: §E.1.2 · p. 31
  • For m ≥ 1, the lower bound exceeds 2.285 × 10^-4 and the ratio exceeds 2.40; at m = 128, the ratio is bounded below by (3.142)(2.719)(0.0097 + 1/22001)^2 > 9.52.I(V; O | B) = I(V; Λ | B, C) ≤ H(Λ | B, C) ≤ r log 2.Source: §E.1.2 · pp. 32–33

E.1.3 Full-Unit-Ball Obstruction

  • On the full unit ball, deployed deterministic ReadKV (8, 2) cannot strictly dominate all query-oblivious protocols: its squared error exceeds 0.26052610, while a simple protocol’s worst-case error is 1/9.The simple protocol independently stochastically rounds each original coordinate between neighboring levels among four levels.Source: §E.1.3 · p. 33

E.2.1 Exact Integer Allocation

  • With unit-cost refinements and nonnegative, nonincreasing gains for each item, repeatedly selecting the largest available weighted gain exactly minimizes the integer allocation objective.The deployed reader uses this rule; the geometric continuous and rounding results are auxiliary comparisons, not assumptions in a ReadKV guarantee.Source: §E.2 · p. 33, §E.2.1 · p. 34

E.2.2 Continuous Geometric Allocation

  • For geometric distortion, the continuous optimum clips depths between zero and W according to item weights and a threshold; positive-weight depths are unique when 0 < B < W|P|.Zero-weight items receive depth zero; when B ≥ W|P|, every positive-weight item receives depth W.Source: §E.2.2 · p. 35

E.2.3 Integer Rounding for Geometric Distortion

  • For geometric distortion, integer rounding bounds the integer optimum by a factor of 1.263740721 over the continuous optimum.This comparison applies only to the idealized geometric curve; implementation applies the exact integer rule to the measured codec curve.Source: §E.2.3 · p. 36

E.3.1 Attention-Output Error Decomposition

  • The deterministic attention-output bound separates key-induced attention-weight error from value reconstruction error weighted by attention, but it does not guarantee that reducing the surrogate improves perplexity.The softmax probability change is bounded by half the logit-error norm.Source: §E.3.1 · p. 37

E.3.2 Diagonal Approximation

  • The diagonal approximation drops cross-channel residual terms to form key and value allocation scores; language-model experiments set the value head factor to one and optimize standardized residual error.The key score sums channel contributions across cached tokens and sibling query heads; the value score uses a physical-scale estimate.Source: §E.3.2 · p. 38
  • The expansions square query coordinates for keys and attention probabilities for values, but calibration may misestimate residual second moments and cross terms may matter.Neither expansion assumes independent keys and queries.Source: §E.3.2 · p. 38
  • A deterministic Lloyd codec does not make the cross terms vanish.The expansions do not rely on keys and queries being independent.Source: §E.3.2 · p. 38
  • The exact allocation theorem concerns the resulting separable objective, and language-model experiments test the quality obtained from it.Source: §E.3.2 · p. 38

E.3.3 Deterministic Attention-Error Bound

The section gives a deterministic bound connecting calibrated key and value allocation objectives to attention-output error. Its strength depends on calibration mismatch and residual-correlation factors, which can be bounded under coherence assumptions but cannot generally be removed.

E.3.3 Deterministic Attention-Error Bound

  • The deterministic attention-output error bound scales the key and value objectives by calibration and residual-correlation factors.It applies to each fixed query, cache, selected depth schedule, and admissible finite calibration factors.Source: §E.3.3 · pp. 39–40
  • Under bounded normalized-Gram coherence and residual-envelope assumptions, the bound uses coherence factors 1 + (mK − 1)µK and 1 + (mV − 1)µV.These conditions also bound the calibration ratios by one.Source: §E.3.3 · pp. 39–40
  • Both exact-to-diagonal residual ratios can equal m, so no dimension-independent constant can replace the correlation factors.The section gives constructions for both key and value residuals.Source: §E.3.3 · p. 40
  • The γ factors measure calibration mismatch and the κ factors amplify omitted cross terms; the proposition does not claim these factors are uniformly small for every language-model cache.Source: §E.3.3 · pp. 39–40

E.4 Stagewise Allocation and Attention-Error Certificate

ReadKV’s stagewise allocations minimize calibrated key and value objectives under diminishing refinement gains, and those objectives support a deterministic attention-output error certificate. The appendix also specifies evaluation protocols and comparison baselines for its expanded experiments.

E.4 Stagewise Allocation and Attention-Error Certificate

  • Diminishing refinement gains make the key allocation optimal, then the reconstructed-key attention fixes weights for an optimal conditional value allocation; together, their objectives bound attention-output error.The certificate’s coefficients account for calibration mismatch, residual correlation, and the centered-value operator norm; the deployed depth-eight tree satisfies the diminishing-gain condition.Source: §E.4 · p. 41

F Experimental Details and Results

  • Appendix F specifies protocols and comparison methods, then adds C4 controls, shorter-prompt QA, passkey retrieval, and experiments on current-query information, intermediate precision, surrogate quality, and GPU-reader restrictions.Mistral uses a 12-candidate pure-SparQ sweep over the same r, k grid on eight development documents, frozen before testing; this is a bounded development search, not a claim of global optimality.Source: F Experimental Details and Results · p. 42, §F.2 · p. 43

F.1 Evaluation Protocol

  • C4 evaluation uses disjoint calibration, development, and test documents, while QA pairs the same questions at 3,500- and 7,500-token prompt limits.Passkey retrieval tests 200 five-digit keys per context length; paired bootstrap intervals resample documents or task examples rather than tokens, layers, or heads.Source: §F.1 · p. 42

F.2 Baselines and Controls

  • Compared methods include fixed-depth quantization, KIVI, TurboQuant, and SparQ; configurable settings are selected on development data and frozen before testing.The stated search is bounded and does not establish global optimality.Source: §F.2 · p. 43

F.3 Complete Quality Results

The expanded experiments compare quality, retrieval, allocation choices, and GPU-reader constraints. Results show that quality depends on operating point and model family, while the GPU timing advantage over TurboQuant is limited to the tested longer contexts and batch settings.

F.3 Complete Quality Results

  • Across Qwen2.5, ReadKV (4, 2) stays within 4.5% of Dense perplexity; at 3,500 tokens, ReadKV (8, 2) has ∆F1 from −1.65 to 1.78 points at 12.6% of Dense reads and 50.1% capacity.At the same prompt limit, the largest loss for ReadKV (8, 4) is below 1.38 points.Source: §F.3 · pp. 44–45, Table 6 · p. 44, Table 7 · p. 45

F.4 Passkey Retrieval

  • ReadKV (8, 2) recovers all 200 passkeys at 4K and 8K while using 12.5–12.6% of Dense logical reads and retaining about half of Dense KV capacity.The quarter-capacity ReadKV (4, 2) recovers all keys using about half the logical reads of the matched-storage Full Reader (4, 4).Source: Table 8 · p. 46, §F.4 · p. 46

F.5 Current-Query Allocation

  • Replacing current-query key allocation with calibration-only allocation raises Qwen3B PPL from 11.789 to 12.011 at the same (3, 1) split.Thirty-one of 32 documents favor current-query keys; the experiment does not assign a fixed share of total gain to either allocation stage.Source: §F.5 · pp. 46–47

F.6 Intermediate Precision Levels

  • At ReadKV (8, 2), restricting keys to {1, W} raises NLL by 0.227, 0.159, and 0.275 nats per token on Qwen3B, Qwen7B, and Yi6B, respectively.Restricting both stages produces substantially larger increases, showing the multilevel benefit is not explained solely by selecting items for one high-precision reconstruction.Source: §F.6 · p. 47

F.7 Allocation Scores and Attention Error

  • For attention-weighted value error, cross-token terms contribute 64.6% on Qwen3B and 72.6% on Qwen7B; multilevel reading worsens output error less often than two-depth restrictions.The value objective can guide placement without accurately estimating error magnitude.Source: §F.7 · p. 47

F.8 GPU Reader Constraints

  • At R = 2, the restricted GPU reader recovers 100–101 Qwen passkeys versus 200 for flexible ReadKV (8, 2); at R = 4, restricted ReadKV recovers all 200.The study identifies equal K/V rates as the main target for improving the low-rate GPU policy.Source: §F.8 · p. 48, Table 10 · p. 48

G GPU Latency and Memory Traffic

  • GPU measurements cover one attention layer during decoding from an existing cache, using a restricted reader with per-head budgets, minimum depth one, equal K/V rates, and paired value tokens.They exclude cache construction and the rest of the model; the quality experiments instead use a flexible reader that pools budgets and permits depth zero.Source: G GPU Latency and Memory Traffic · p. 48

G.1 Latency Across Workloads

  • ReadKV is faster than tested TurboQuant at 8K and 32K for both batch sizes, while TurboQuant is faster at 2K batch one and Dense is fastest throughout.The comparisons use the same timing boundary, including ReadKV’s final bf16 conversion.Source: Table 11 · p. 49, §G.1 · p. 49

G.2 Memory and Physical Traffic

This section measures physical memory traffic and execution costs for ReadKV in an 8K-token, batch-one workload. At a two-bit read budget, ReadKV reduces DRAM reads versus TurboQuant, while total traffic and storage costs qualify the comparison.

  • At 8K and batch one, ReadKV's four- and eight-bit payloads occupy 4.00 and 8.00 MiB, and each call uses 3.87 MiB workspace.TurboQuant retains 4.19 MiB and uses 0.45 MiB of workspace; the uncompressed K/V cache occupies 16.00 MiB.Source: §G.2 · p. 49
  • Physical counters cover the complete eager attention call, including intermediate and output accesses; graph-replay latency is measured separately from logical read counts.The evicted condition displaces prior GPU-cache contents before the measured call.Source: §G.2 · p. 49
  • ReadKV (4, 2) and ReadKV (8, 2) both read two payload bits per scalar and take 0.092–0.093 ms, despite retained payload increasing from 4 to 8 MiB.On this fixture, the added stored precision has little effect on execution time but consumes more memory capacity.Source: §G.2 · p. 49
  • ReadKV (8, 2) cuts DRAM reads 62–65% versus TurboQuant (2.80/2.74 vs 7.28/7.92 MiB), while total traffic falls 20–31% (7.47/7.47 vs 9.38/10.84 MiB).Entries report warm / cache-evicted traffic for the 8K-token, batch-one NVIDIA A10G single-layer benchmark.Source: §G.2 · p. 49, Table 12 · p. 50
Loading 2610.11245v1…