acceptodds
Under review as a conference paper at ICLR 2027

OrthoKV: Extreme KV Cache Compression with Exact Orthogonal Sparse Coding

Abstract

The KV cache is a major memory bottleneck in long-context inference. Sparse coding is attractive for extreme KV cache compression, but existing approaches rely on iterative sparse approximation over large overcomplete dictionaries, introducing substantial encoding overhead. We introduce OrthoKV, which replaces layer-wise overcomplete dictionaries with complete orthogonal dictionaries specialized to individual KV heads. Per-head specialization helps compensate for the reduced representational capacity of complete dictionaries, while orthogonality makes sparse coding exact and non-iterative. The best -term approximation under squared reconstruction error is obtained by a single transform followed by selecting the coefficients with the largest absolute values. The same result extends across heads. With a total budget of coefficients, one simply keeps the largest coefficients in absolute value across all heads. We learn the dictionaries with a sparsity-promoting objective that does not depend on the target sparsity, so the same dictionaries can be used at different compression ratios without retraining. Complete dictionaries also enable smaller coefficient indices and more compact sparse codes. In the extreme compression regime, OrthoKV uses less KV cache memory than Lexico while matching or improving its quality in most evaluated settings and substantially reduces sparse coding latency. Compared with full KV caching, OrthoKV achieves higher throughput at larger batch sizes and supports batches that would otherwise run out of memory.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV Cache Compression, Sparse Coding, Dictionary Learning

Reviews

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

OrthoKV replaces layer-wise over-complete dictionaries with per-head complete dictionaries to enable efficient sparse coding of KV cache. This allows smaller coefficient indices and compact sparse codes while orthogonality enables encoding through a single transform followed by topk selection. A fixed coefficient budget is adaptively allocated across heads by retaining the largest-magnitude coefficients, minimizing reconstruction error under that budget. Same dictionaries support multiple compression ratios without retraining by decoupling sparsity-promoting objective from target coefficient budget.

Critical strengths

1] In the line of dictionary-based extreme KV cache compression works represented in Lexico, OrthoKV achieves high efficiency by removing iterative orthogonal matching pursuit, and better compression by using smaller dictionary size. The authors show that replacing OMP with a more efficient orthogonal transform + topk selection, per-head specialization ,and adaptive allocation achieve comparable model accuracy to Lexico.

Critical weaknesses

1] Severe accuracy degradation limits the practical appeal of OrthoKV. KIVI 2bit with similar compression ratio as OrthoKV k=18, shows much higher accuracy retention. While the authors target memory budgets below KIVI-2 configurations, from the rate at which OrthoKV k=6 (7% KV cache size) and k=12 (12% KV cache size) degrades model accuracy, a potentially more appealing alternative would be to use a smaller model, which wouldn't need a custom system backend as well.

2] Latency benefits are limited at batch size 1. While faster than Lexico, it is slower than Full KV and around the same latency as KIVI-2 under similar compression ratio (k=18) despite substantially lower model quality. While throughput improves as batch size increases, the absence of a batched comparison with KIVI-2 makes the advantage less clear. Evaluation of OrthoKV on larger models would have further strengthened the large-batch efficiency benefits, but it is left as a limitation, along with validation on more recent, non-GQA attention architectures.

Questions for authors

1] Can the authors provide a latency breakdown separating KV encoding/compression, cache updates, and attention computation for OrthoKV and Lexico? This will clarify whether the speedup comes from replacing OMP with orthogonal transform and topk selection, or difference in attention kernels and runtime optimizations.

2] With the popularity of "thinking" in LLMs, I think reasoning should be evaluated with workloads such as AIME and MATH in addition to GSM8K. Can the authors use reasoning models like DeepSeek-R1-Distill-Qwen/Llama to validate whether the KV cache compression is effective on long decoding?

3] If KV cache quantization achieves better accuracy at similar compression ratio, why would one use OrthoKV over KIVI?

4] Can the authors compare OrthoKV and KIVI-2 in terms of batched throughput across different input lengths and generation lengths? On top of the provided model accuracy, these measurements would form the quality-memory-throughput tradeoff comparison.

5] Can the authors compare an aggressively compressed 7-8B model using OrthoKV against a smaller model with a less aggressively compressed KV cache, under matched total GPU memory budget and workloads? This would help convince that OrthoKV offers a favorable quality-memory tradeoff. For example a comparison within the Qwen3 family, 8B with OrthoKV versus naive 4B or 1.7B.

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

An extreme KV cache compression method OrthoKV replaces overcomplete dictionaries and iterative sparse coding with per-head orthogonal dictionaries. By using orthogonality, OrthoKV enables exact top-k coefficient selection under squared reconstruction error and adaptive coefficient allocation across KV heads. The dictionaries are learned using a sparsity-promoting objective and can support different compression ratios without retraining.

Critical strengths
  1. While orthogonal dictionaries and hard thresholding are not novel techniques, the authors successfully adapt them for KV cache compression by integrating per-head specialization, adaptive coefficient allocation, and sparse attention. This represents a meaningful KV-specific design.

  2. The proposed method not only reduces the computational overhead of iterative OMP but also demonstrates a 10–14× speedup in end-to-end evaluation compared with Lexico. At a batch size of 16, OrthoKV with k = 6 achieves 2.48× higher decoding throughput than Full KV, showing its practical efficiency benefits.

Critical weaknesses
  1. OrthoKV with k = 18 uses approximately 18% less KV cache memory than KIVI (16.62% vs. 20.30%), but its LongBench average score is 6.51 points lower. More importantly, on GSM8K, OrthoKV with k = 18 uses more KV cache memory than KIVI (24.61% vs. 19.38%), yet its accuracy is 10.01 percentage points lower. Although the authors demonstrate extreme compression, they do not sufficiently justify whether the additional memory savings are worth the substantial loss in downstream accuracy.

  2. Orthogonality ensures optimal sparse approximation under squared reconstruction error for a fixed dictionary and coefficient budget, but this does not necessarily preserve attention-relevant information or minimize attention output error. This might be the issue to the observed degradation in downstream accuracy, but the paper does not provide sufficient analysis for this case.

Questions for authors
  1. Can the authors explain why OrthoKV with k = 18 uses more KV memory than KIVI but achieves lower accuracy On GSM8K and in which settings OrthoKV would be more beneficial than KIVI?

  2. Have the authors measured attention output errors to see whether they are related to the drop in downstream accuracy?

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

This paper proposes OrthoKV, a KV cache compression method that represents each key and value vector using a small number of coefficients from a learned orthogonal dictionary. It learns separate dictionaries for each KV head and replaces the iterative sparse coding used by Lexico with an orthogonal transform followed by coefficient selection. It also dynamically allocates coefficients across heads and supports different compression ratios using the same dictionaries. Experiments on two models show comparable or better quality than Lexico in most tested settings, with smaller KV caches and significantly lower evaluation time. The method also improves throughput over full KV caching at larger batch sizes.

Critical strengths
  • The method is simple and addresses a practical problem. Replacing iterative sparse coding with an orthogonal transform and coefficient selection makes the encoding process simpler and more efficient.

  • The method shows promising results compared with Lexico. Tables 2 and 3 show that OrthoKV generally achieves comparable or better quality while using slightly less KV cache memory. Table 4 also shows significantly lower evaluation time compared with Lexico.

  • The paper demonstrates inference efficiency improvements at larger batch sizes. Table 5 shows that OrthoKV can improve decoding throughput and reduce peak GPU memory compared with full KV caching, especially at larger batch sizes.

  • The dictionary training is relatively inexpensive. The same dictionaries can be used for different compression ratios without retraining, which makes the method easier to use in practice.

Critical weaknesses
  • The initial KV cache compression overhead is not clearly evaluated. As mentioned in Section 2.5, OrthoKV compresses the prompt's KV cache after prefill and before decoding. However, the paper does not report how long this initial compression takes or how it affects time to first token (TTFT). It is also unclear whether this overhead is included in the end-to-end evaluation time reported in Table 4. Since the method needs to compress the entire prompt prefix, this overhead could be significant for long input sequences. Without this measurement, it is difficult to fully assess the practical inference efficiency of OrthoKV.

  • The efficiency evaluation lacks comparisons with other competitive baselines. Table 5 only compares OrthoKV with full KV caching. It would be helpful to include KIVI-2 in the batch-scaling experiments to better understand the benefits of OrthoKV in terms of overall throughput, decoding throughput, and peak memory.

  • The quality and memory tradeoff is not always competitive with KIVI-2. Although OrthoKV generally achieves comparable or better performance than Lexico, some configurations perform significantly worse than KIVI-2 while using similar or even more memory. For example, on Llama GSM8K, KIVI-2 achieves 71.19% accuracy with 19.38% KV cache memory, while OrthoKV with k=12 achieves only 53.90% accuracy with 20.43% memory. This raises concerns about the practical benefit of the method outside the extreme compression regime. The different buffer configurations should also be considered when interpreting these results.

  • The evaluation on long-context workloads is limited. The LongBench experiments truncate input sequences to 8K tokens, and the batch-scaling experiments also use 8K input tokens with only 128 generated tokens. Since the method targets extreme KV cache compression for long-context inference, experiments with longer sequences, such as 32K or 64K, would make the evaluation more convincing. The experiments are also limited to two 7B–8B models with similar attention configurations.

  • The comparison with other sparse KV compression methods is limited. While the paper discusses CSR as a related method, the experiments mainly focus on comparisons with Lexico. Including CSR at similar compression ratios would help better establish the contribution of OrthoKV.

Overall, I find the proposed approach interesting, and the improvement over Lexico is promising. However, my main concern is that the inference efficiency evaluation is not sufficiently complete, particularly regarding the initial KV cache compression overhead and its impact on latency. Together with the limited efficiency comparisons against other baselines and the quality degradation under aggressive compression, I am leaning toward weak reject.

Questions for authors
  • Initial KV cache compression overhead: Section 2.5 mentions that the KV cache is compressed after prefill and before decoding. Does the end-to-end evaluation time in Table 4 include this initial compression? How much latency does it introduce, and what is its impact on TTFT? It would be helpful to report the initial compression time separately, especially for longer input sequences.

  • Batch-scaling comparison with KIVI-2: Could the authors include KIVI-2 in the batch-scaling experiments in Table 5? Comparing overall throughput, decoding throughput, and peak GPU memory at the same batch sizes would help demonstrate the practical efficiency benefits of OrthoKV.

  • Long-context evaluation: How does OrthoKV perform with longer input sequences, such as 32K or 64K tokens? Does the quality and efficiency advantage remain consistent as context length increases?

  • Ablation and additional baselines: How much improvement comes from learning the orthogonal dictionaries compared with using a fixed or random orthogonal basis? Could the authors also provide a comparison with CSR under similar memory budgets?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.