acceptodds
Under review as a conference paper at ICLR 2027

CheeSe : Channel Permutation for Semi-structured KV Cache Pruning

Abstract

The KV cache is the memory-bandwidth bottleneck in long-context LLM inference. Element-wise unstructured pruning preserves quality best but obtains no compute acceleration, and its storage overhead keeps the effective compression ratio below the nominal one; structured methods accelerate computation but lose accuracy quickly as compression grows. 2:4 pruning offers both acceleration on sparse tensor cores and a high effective compression ratio, yet prior work rejected it for the KV cache because of its quality loss, and subsequent work accelerated it with dedicated kernels while leaving that loss in place. We propose CheeSe, which recovers this loss with two techniques. First, we show that the loss arises almost entirely on the key cache and stems from how channels are grouped rather than from which elements are removed: removing the same number of key elements costs under unstructured pruning but under 2:4, because important channels cluster within the same group. A sorting-based channel permutation, computed once during calibration and transferable across tasks, recovers most of this loss, whereas more elaborate permutation searches from the weight pruning literature cost up to four orders of magnitude more compute and bring no further gain. Second, output-aware selection, which is harmful for 2:4 alone, becomes beneficial once the permutation is in place. Across five models, CheeSe stays within 0.21 points of unstructured pruning and recovers more of the 2:4 loss than keeping sink tokens and the recent context dense, at no cost in compression. It improves the effective compression ratio by 9.2 percentage points and accelerates decode attention by with an existing 2:4 kernel at a runtime overhead of 2.5%, and it composes with token eviction and quantization.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV cache compression, 2:4 sparsity, semi-structured sparsity, N:M sparsity, channel permutation, efficient LLM inference

Reviews

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

This paper proposes CheeSe, a channel permutation method for improving the accuracy of 2:4 semi-structured KV cache pruning. The authors observe that conventional 2:4 pruning suffers from significant accuracy degradation because important key channels tend to be grouped together. By rearranging channels according to their importance, CheeSe reduces this degradation while preserving the hardware efficiency of 2:4 sparsity. The method also incorporates output-aware selection to further improve pruning quality.

Experiments across five language models show that CheeSe achieves accuracy comparable to unstructured pruning, while offering better effective KV cache compression and a 1.80× speedup in decode attention using an existing sparse kernel.

Critical strengths
  1. Simple and practical approach. The proposed method is straightforward and does not require model retraining. The permutation can be computed offline and reused across different inputs, with relatively low runtime overhead.

  2. Consistent experimental improvements. The method substantially reduces the accuracy degradation of conventional 2:4 pruning across five models. The results suggest that channel permutation is an effective way to make semi-structured KV cache pruning more practical.

  3. Hardware compatibility. By preserving the 2:4 sparsity pattern, CheeSe can leverage existing GPU sparse computation support, providing benefits in both memory efficiency and attention computation.

Critical weaknesses
  1. Limited novelty. Channel permutation has already been explored in previous work on semi-structured weight pruning. The main contribution of this paper is adapting an existing technique to the KV cache setting and demonstrating its effectiveness. While this application is useful, the algorithmic novelty is relatively limited.

  2. Insufficient end-to-end efficiency evaluation. The paper reports a 1.80× speedup for decode attention and a relatively small overhead from permutation. However, it does not provide a comprehensive end-to-end inference evaluation. Since improving inference efficiency is a central motivation of the paper, it would be valuable to demonstrate the actual benefits in overall generation latency and throughput.

Questions for authors
  1. Could the authors provide end-to-end inference latency or throughput measurements that account for the permutation and pruning overhead? It would be particularly helpful to evaluate different context lengths and batch sizes.

  2. How much additional practical benefit does output-aware selection provide beyond channel permutation alone? The reported gains appear relatively small and are not statistically significant for individual models. Could the authors further clarify its importance in the overall method?

4 comments
AuthorsOpenReview ↗

Response to Reviewer 6QFZ

We sincerely appreciate the reviewer's time and effort in providing thoughtful and constructive feedback. Please find our responses to each point below.

W1. Novelty

As the reviewer noted, channel permutation itself was proposed for weight pruning, and we agree that the algorithmic novelty is limited. The contribution we intended to emphasize is the observation that the loss of 2:4 pruning on the KV cache largely comes from how channels are placed on the key side, rather than being an inherent cost of the structural constraint, which prior work (MUSTAFAR, HieraSparse) reasonably took as a given. We also observed that a single sort was sufficient, with more elaborate search providing only marginal additional gain, and that the permutation can be fixed in advance with little sensitivity to documents, tasks, or calibration data. In practice, this brings a 2:4 pattern close to the accuracy of unstructured pruning (within 0.3 points on LongBench) while being 1.21× faster than dense end-to-end at a 32K context with batch size 8 (please see our response to W2 & Q1).

W2 & Q1. End-to-end efficiency across context lengths and batch sizes

As you suggested, we measured end-to-end time across context lengths and batch sizes, including the permutation and pruning overheads (NVIDIA A100 80GB, Llama-3.1-8B-Instruct (fp16), generation length 4,096). The compared methods are dense (FlashAttention-2), unstructured (MUSTAFAR's official kernel), and CheeSe (including permutation and OA).

Prefill is nearly the same across the three methods; the gain appears in decode, which reads the entire KV cache for every token. The gain grows with the KV cache: at 32K × 8 the total time is 1.21× shorter, while at 8K × 1, where the KV cache is small, CheeSe does not provide a speedup (0.94×). We would like to add that CheeSe accelerates only the attention over the KV cache during decode, while prefill and the remaining decode operations (e.g., the MLP) are shared with dense. The 1.80× speedup of decode attention in Figure 2(b), measured at 32K × 8, therefore corresponds to 1.26× in decode and 1.21× end-to-end. The overhead added by CheeSe (permutation, OA, pruning, packing) is 1.5% of the total time and is included in the numbers below.

In terms of end-to-end throughput, CheeSe reaches 219 tok/s at 32K × 8, compared with 181 tok/s for dense.

Context × batchPrefill (s): dense / CheeSe / unstructuredDecode (s): dense / CheeSe / unstructuredTotal (s): dense / CheeSe / unstructuredCheeSe speedup (decode / total)
8K × 10.74 / 0.75 / 0.9360.0 / 63.7 / 174.760.7 / 64.4 / 175.60.94× / 0.94×
32K × 14.04 / 4.03 / 4.3768.9 / 69.2 / 472.673.0 / 73.3 / 476.91.00× / 1.00×
32K × 416.30 / 16.08 / 17.59103.2 / 91.6 / 751.2119.5 / 107.6 / 768.81.13× / 1.11×
32K × 832.85 / 32.10 / 35.32148.0 / 117.6 / 1,104.5180.8 / 149.7 / 1,139.81.26× / 1.21×

Q2. Practical benefit of output-aware (OA) selection

As the reviewer noted, the overall gain of OA is small (+0.01 to +0.23 on the 16-task average). Most of CheeSe's recovery of the 2:4 loss comes from the channel permutation, and OA is a component added on top of it. On specific tasks, however, the gain was consistent across the evaluated models.

On the LongBench code-completion tasks (average of Lcc and RepoBench-P), the five models improve.

Model16-task avg. (permutation)+OAΔCode (permutation)+OAΔ
Llama-342.3842.61+0.2355.3457.31+1.97
Llama-3.144.8645.07+0.2157.6158.14+0.53
Mistral38.1638.28+0.1252.4352.98+0.55
Phi-442.2542.34+0.0965.7366.03+0.30
Qwen346.2946.30+0.0165.2765.31+0.04

On the RULER word-frequency aggregation task (cwe), the three evaluated models also improve. cwe is the subtask where the largest gap to dense remains after the permutation, and OA closes more than half of that gap.

Model6-subtask avg. (permutation)+OAΔcwe (permutation)+OAΔ
Llama-390.5791.80+1.2391.4595.80+4.35
Llama-3.194.4295.07+0.6590.8595.35+4.50
Qwen393.9494.03+0.0991.5092.70+1.20

OA adds only 0.5% to the total generation time, so we suggest using it as an optional component for tasks such as code completion and aggregation, where we observed a consistent gain. We will clarify this in the revised manuscript.

Thank you again for the helpful review.

AuthorsOpenReview ↗

Follow-Up to Your Review

Dear Reviewer 6QFZ,

We are sincerely grateful for your careful review. We have already posted our responses to each point you raised.

If your schedule permits, we would be truly thankful if you could let us know whether any concerns remain. We would be more than happy to provide further explanation.

With our sincere appreciation, The Authors of Submission 48

Thank you for the detailed response and the additional experiments.

The new end-to-end efficiency results address my main concern regarding the practical speedup of CheeSe. In particular, the 1.21× end-to-end speedup at 32K context length with batch size 8 provides stronger evidence of its practical value. I also appreciate the clarification of the role of OA selection and its benefits on specific tasks.

Although the algorithmic novelty remains relatively limited, I believe the simplicity of the method, its consistent accuracy improvements, and the additional efficiency results make a meaningful contribution.

Overall, the rebuttal has adequately addressed my major concerns, and I will maintain my original rating of 3/4 (Weak Accept).

AuthorsOpenReview ↗

Thank You to Reviewer 6QFZ

Dear Reviewer 6QFZ,

We appreciate your careful reading of our response and your thoughtful comments throughout the discussion. It is good to hear that the end-to-end results at 32K context resolved your main concern about practical speedup.

Your review helped us make the paper stronger, and we are grateful for it.

Best regards, Authors of Submission 48

Reviewer_eX3ROpenReview ↗
Rating
4(+2)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

CheeSe seeks to retain model accuracy in leveraging 2:4 sparsity in KV cache pruning. Since semi-structured sparsity pattern retains a fixed ratio of elements in each consecutive element-window, they perform channel permutation to make sure that each window retains important elements. They further observe that output-aware pruning improves accuracy post-permutation. Leveraging existing GPU kernel for 2:4 semi-structured attention, they achieve speedup compared to dense attention.

Critical strengths

The paper addresses an important gap in KV cache pruning. Semi-structured sparsity can leverage existing systems and hardware support for compute efficiency, pruning the KV cache as-is damages accuracy. By borrowing the permutation algorithm from the weight pruning works, they show an effective way to retain model accuracy while applying KV cache semi-structured sparsity. Authors are thorough in comparing different permutation algorithms, showing that a minimal overhead algorithm is sufficient to retain model accuracy, and that the precomputed calibration data extends to different tasks.

Critical weaknesses

1] The main limitation of CheeSe is the same inherent limitations of 2:4 semi-structured sparsity, that it is confined to 50% sparsity. Mustafar, the main baseline of this paper, highlights that the benefit of unstructured sparsity is being able to map any sparsity value, showing model accuracy retention at 70% sparsity. While the authors control sparsity by overlaying token eviction method (table 5), I think a fairer comparison would be leveraging existing works in semi-structured sparsity patterns (please see questions for authors), comparing solely on the KV cache pruning dimension.

2] The second half of CheeSe, output-aware pruning shows little benefit nor insight. The authors observe that with channel permutation is what gives output-aware pruning the benefit, yet does not give a clear analysis behind this observation. The accuracy improvement with output-awareness also seems small (shown in Table 3 and 4). It is also unclear whether output-aware pruning is applied to Value cache as well, and if so, whether it requires materialization of attention score.

Questions for authors

Dear authors, thank you for submitting to ICLR. I enjoyed reading CheeSe, and am willing to raise my scores once the following are addressed:

1] While Appendix Section B shows the effectiveness of LongBench calibration data on RULER, both are long input-short output tasks. Please show that CheeSe is also effective in long decode benchmarks, such as AIME and MATH. For these harder benchmarks, I recommend using reasoning models such as DeepSeek-R1-Distill-Qwen/Llama. Also, please include the full evaluation results for RULER, showing the accuracy for each subtask.  

2] As stated in the "Critical Weakness" section, the main limitation of 2:4 sparsity is the confinement to 50% sparsity. While this is stated in the manuscript, the impact of this paper will be significantly increased if CheeSe can show that accuracy is preserved for 1:4 sparsity (75% sparsity) as well. Notably, there exists GPU kernel support for 1:4 sparsity as well, (nmSparse [1], VENOM[2] - 2:8 sparsity, NM-SpMM[3]), so supporting attention operation for 1:4 sparsity could also be addressed in a future work. Showing accuracy for 75% sparsity and comparing that to unstructured sparsity is sufficient for CheeSe.

3] Authors claim that because of RoPE, permutation cannot be folded into the projection weights. However, since the channel permutation information is fixed before runtime, can't a custom RoPE implementation operate on top of permutation-folded-projection weights?

4] CheeSe performs online pruning, including output-aware score computation, as well as compression of the pruned KV cache to the compact 2:4 representation. Figure 2 only shows the breakdown of channel permutation, and groups other operations together. Please provide further breakdown of said "Decode + attention + 2:4 pruning".

[1] Lin et al., EFFICIENT GPU KERNELS FOR N:M-SPARSE WEIGHTS IN DEEP LEARNING, MLSys 2023

[2] Castro et al., VENOM: A Vectorized N:M Format for Unleashing the Power of Sparse Tensor Cores, SC23.

[3] Ma et al., NM-SpMM: Accelerating Matrix Multiplication Using N:M Sparsity with GPGPU, IPDPS 2025

6 comments
AuthorsOpenReview ↗

Response to Reviewer eX3R (1/2)

We sincerely appreciate the reviewer's time and effort in providing detailed and constructive feedback, and the concrete suggestions that helped us extend the paper. Please find our responses to each point below.

W1 & Q2. Evaluation at 75% sparsity

Thank you for pointing us to these kernels, which allowed us to extend the study. As suggested, we evaluated 1:4 at 75% sparsity, and also 2:8, the pattern supported by VENOM (Llama-3-8B-Instruct, 16 LongBench tasks). In these experiments, the gain from CheeSe was larger than at 2:4 (+6.16 points for 1:4 and +3.91 points for 2:8, versus +1.50 points for 2:4). As you noted, we leave a 75% kernel for KV cache attention to future work.

ConditionPruning rate16-task avg.Gap to unstructured
MUSTAFAR (unstructured)74.22%39.84–
1:4 (original order)75.00%28.73−11.11
1:4 + CheeSe75.00%34.89−4.95
2:8 (original order)75.00%33.26−6.58
2:8 + CheeSe75.00%37.17−2.67

W2. Output-aware (OA) pruning

W2-1. Why OA needs the permutation. As you suggested, we analyzed why OA benefits from the permutation. Our analysis suggests that OA is more effective after the channel permutation because, in the original channel order, channels with similar query weights tend to be adjacent. Before the permutation, the query weights within a group differ little (median max/min ratio 1.85×), so multiplying by them rarely changes the ranking. After the permutation, channels of very different magnitude are spread more evenly across the groups, and accordingly the query weights within a group differ more (median max/min ratio 2.57×), so the query changes the selection more often (the fraction of groups where OA selects differently from magnitude rises from 19.8% to 23.7%). We will add this analysis to the revised manuscript.

W2-2. Why OA is not applied to the Value cache. Thank you for raising this point, which we did not explain sufficiently in the paper. OA is applied only to the Key cache. Every Value element of a token is multiplied by the same single attention score, so the ranking of their impact on the output equals the ranking of their magnitudes. For Values, the magnitude criterion is therefore already the output-aware criterion, and MUSTAFAR uses magnitude for Values for the same reason. Keys, in contrast, are multiplied element-wise by different query values, which is where OA can help. Regarding the concern about the attention matrix, OA on Keys uses only the absolute query values rather than attention scores, so we believe that the attention matrix does not need to be materialized.

W2-3. Where OA helps. As the reviewer noted, the overall gain of OA is small (+0.01 to +0.23 on the 16-task average). On specific tasks, however, the gain was consistent across the evaluated models: on the LongBench code-completion tasks the five models improve, and on RULER cwe the three evaluated models improve (Llama-3 +4.35, Llama-3.1 +4.50, Qwen3 +1.20; please see the RULER table under Q1). OA adds only 0.5% to the total generation time, so we suggest using it as an optional component for tasks such as code completion, where we observed a consistent gain. We will clarify this in the revised manuscript.

Model16-task avg. (permutation)+OAΔCode (permutation)+OAΔ
Llama-342.3842.61+0.2355.3457.31+1.97
Llama-3.144.8645.07+0.2157.6158.14+0.53
Mistral38.1638.28+0.1252.4352.98+0.55
Phi-442.2542.34+0.0965.7366.03+0.30
Qwen346.2946.30+0.0165.2765.31+0.04

Code is the average of Lcc and RepoBench-P.

AuthorsOpenReview ↗

Response to Reviewer eX3R (2/2)

Q1. Long-decode benchmarks and per-subtask RULER results

Q1-1. AIME and MATH. As you suggested, we evaluated MATH-500 with DeepSeek-R1-Distill-Llama-8B (T = 0.6, top-p = 0.95, up to 32K generated tokens). Due to the limited time window of the rebuttal, we were only able to evaluate 100 problems sampled with stratification by difficulty level, and the AIME 2024 evaluation is still in progress. We will include the AIME 2024 results and MATH-500 results with more problems in the revised manuscript.

ConditionMATH-500 accuracy (%)
Dense90.0
Unstructured (MUSTAFAR, KV 0.5)91.0
2:483.0
CheeSe89.0

On MATH-500, 2:4 is 7 points below dense and the CheeSe recovers 6 of them, reaching a level that is not statistically distinguishable from unstructured pruning in a per-problem paired comparison.

Q1-2. RULER per-subtask results. Following your suggestion, we provide the per-subtask RULER results below. The permutation calibrated on LongBench documents is applied without recomputation, and we added Llama-3.1 to extend the evaluation to three models.

ModelConditioncweniah_multikey_1niah_multivalueniah_single_1qa_1vtAvg.
Llama-3Dense98.1099.5097.25100.0059.0098.0091.98
Llama-32:461.5095.0092.6295.5056.5094.4082.59
Llama-32:4 + permutation91.4599.0095.75100.0059.0098.2090.57
Llama-32:4 + permutation + OA95.8098.5095.38100.0062.5098.6091.80
Llama-3.1Dense97.50100.0095.62100.0083.0099.9096.00
Llama-3.12:448.0599.5089.5094.5073.5094.4083.24
Llama-3.12:4 + permutation90.85100.0094.88100.0081.0099.8094.42
Llama-3.12:4 + permutation + OA95.35100.0094.25100.0081.0099.8095.07
Qwen3Dense93.60100.0099.00100.0070.50100.0093.85
Qwen32:460.0099.5094.38100.0060.5082.0082.73
Qwen32:4 + permutation91.50100.0099.12100.0073.00100.0093.94
Qwen32:4 + permutation + OA92.70100.0099.00100.0072.50100.0094.03

The permutation recovers 85.0%, 87.6%, and 100.8% of the 2:4 loss on the three models. The 2:4 loss is concentrated on cwe (e.g., 97.5 → 48.1 on Llama-3.1); the permutation brings it back above 90, and OA raises it further. We will add these results to the revised manuscript.

Q3. Folding the permutation into the projection weights

Thank you very much for this insightful suggestion. The reviewer is right, and our statement in the paper was not accurate. Following your suggestion, we folded the permutation into the q/k projection weights and implemented RoPE to operate in the permuted coordinates. We confirmed that the output is bit-identical to the original implementation, and the time the permutation adds to a decode step dropped from 1.4–3.0% to 1.0–2.2% (the range over nine settings combining context lengths of 8K/16K/32K and batch sizes of 1/4/8). We will correct the statement in the paper that the permutation "cannot be folded into the weights" to "cannot be folded under the standard RoPE implementation," and add this implementation and its measurements to the revised manuscript.

Permutation implementationAdded time per decode step (vs. no permutation)Output
Gather after RoPE (implementation in the paper)+1.4–3.0%Reference
Folded into the weights (as suggested)+1.0–2.2%Bit-identical to gather

Q4. Breakdown of "Decode + attention + 2:4 pruning"

Following your suggestion, we broke down "Decode + attention + 2:4 pruning" in Figure 2(c) (NVIDIA A100 80GB, Llama-3.1-8B-Instruct (fp16), input length 32K, batch size 8, generation length 4,096).

StepPrefill (of 32.10 s)Decode (of 117.6 s)Total (of 149.7 s)
Channel permutation0.01 s1.31 s1.32 s
OA statistics collection0.0004 s0.62 s0.62 s
OA score computation0.001 s0.14 s0.14 s
Pruning0.023 s0.007 s0.03 s
Sparse packing0.069 s0.020 s0.09 s
Total0.10 s (0.3%)2.10 s (1.8%)2.20 s (1.5%)

The steps added by CheeSe account for 1.5% of the total generation time, which includes the OA score computation and the 2:4 compression mentioned in your question. The remaining time is spent on operations shared with dense, such as attention and the MLP. In the revised manuscript, we will replace Figure 2(c) with this breakdown.

Thank you again for the helpful review.

AuthorsOpenReview ↗

Response to Reviewer eX3R (AIME 2024 results)

Follow-up: AIME 2024 results

As promised, we report the remaining AIME 2024 conditions (DeepSeek-R1-Distill-Llama-8B, all 30 problems, two samples per problem).

ConditionAIME 2024 accuracy (%)
Dense55.0
Unstructured (MUSTAFAR, KV 0.5)53.3
2:420.0
CheeSe (2:4 + permutation)45.0
CheeSe (2:4 + permutation + OA)50.0

CheeSe recovers 30 of the 35 points lost by 2:4, and is 3.3 points below unstructured pruning. Because of the limited rebuttal time, we used two samples per problem; the final version will report results with more samples.

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

The paper studies the quality degradation of 2:4 KV cache pruning relative to unstructured pruning. On Llama-3-8B-Instruct, the authors prune K and V separately and find that the degradation primarily comes from the key cache: at approximately the same sparsity, pruning only K with 2:4 sparsity causes a substantially larger drop in the average LongBench score than unstructured pruning. They attribute this phenomenon to important channels clustering at adjacent positions, which forces some important elements to be removed under the within-group constraints of 2:4 pruning. To address this issue, they apply the existing HCR channel permutation method to KV cache pruning, ensuring that the four channels in each group come from four different importance quantile intervals, and combine it with a query-weighted, output-aware element selection criterion. Across comparisons on 16 tasks using five models, the method's average score for each model differs from that of the unstructured pruning baseline by no more than 0.21 points. After accounting for metadata, the effective compression rate of the 2:4 storage format is 43.8%.

Critical strengths
  1. The problem is clearly defined, and the mechanistic analysis is convincing. The method is also simple and inexpensive: it constructs the permutation through sorting, requires calibration only once for reuse across tasks, and incurs low additional runtime overhead.
  2. The experimental coverage is broad, spanning 5 models, 4 architecture families, and 16 LongBench tasks. The experiments further investigate permutation granularity, cross-domain transfer, and combinations with SnapKV/KIVI.
Critical weaknesses
  1. Treating unstructured pruning as a performance upper bound is not logically justified. The feasible set of optimal unstructured masks is indeed larger, but the actual comparison is against MUSTAFAR's magnitude-based heuristic pruning, not an optimal mask obtained for the downstream task. The inclusion relationship between feasible sets does not imply that the task score of this particular baseline is an upper bound.
  2. The novelty is limited, placing greater weight on the strength of the empirical evidence. The main contribution is to apply an existing permutation method to KV cache pruning, identify the conditions under which it is effective, and validate its combinations with other methods. Why is this transfer important? How much of the lost performance can a random permutation recover? If a random permutation already recovers most of the loss, the central finding is closer to “breaking up clusters of adjacent channels.”
Questions for authors
  1. Could you check whether the manuscript follows the required template? The spacing around figures, tables, and paragraphs becomes noticeably larger on the later pages.
  2. Does the effectiveness depend on the specific calibration documents? Is the finding that the gap to unstructured pruning is no more than 0.21 points stable?
  3. Please compare the original channel order + 2:4 pruning, random permutation + 2:4 pruning, and HCR permutation + 2:4 pruning. Do the gains come from simply disrupting the original channel clustering, or specifically from HCR's importance-balanced grouping?
  4. Under the same hardware, input length, batch size, and generation length, please compare the dense baseline, the unstructured pruning approach, and the complete CheeSe method, including OA. Please report end-to-end generation latency or generation throughput; prefill and decode times; actual peak GPU memory usage; and a breakdown of the overhead from permutation, OA statistics collection, pruning, and sparse packing.
3 comments
AuthorsOpenReview ↗

Response to Reviewer BkbY (1/2)

We sincerely appreciate the reviewer's time and effort in providing careful and constructive feedback on our manuscript. Please find our responses to each point below.

W1. Treating unstructured pruning as an upper bound

Thank you for this valuable comment. As the reviewer noted, what we compare against is not an optimal unstructured mask but MUSTAFAR's magnitude-based heuristic, so its task score is not necessarily an upper bound. We used MUSTAFAR as the reference because, to the best of our knowledge, it is the representative unstructured pruning method for the KV cache and gives the accuracy closest to dense at the same sparsity. However, we agree that describing it as an "upper bound" is not accurate. In the revised manuscript, we will describe MUSTAFAR in the introduction, Section 3.3, and the conclusion as a reference for the recoverable loss rather than as an upper bound.

W2. Novelty

We agree with the reviewer that channel permutation itself was proposed for weight pruning, and our method builds on that line of work. The contribution we intended to emphasize is the observation that the loss of 2:4 pruning on the KV cache largely comes from how channels are placed on the key side, rather than being an inherent cost of the structural constraint, which prior work (MUSTAFAR, HieraSparse) reasonably took as a given. We also observed that a single sort was sufficient, with more elaborate search providing only marginal additional gain, and that the permutation can be fixed in advance with little sensitivity to documents, tasks, or calibration data. In practice, this brings a 2:4 pattern close to the accuracy of unstructured pruning (within 0.3 points on LongBench) while being 1.21× faster than dense end-to-end at a 32K context with batch size 8 (please see our response to Q4). The random-permutation comparison suggested by the reviewer is provided in our response to Q3.

Q1. Template

Thank you for reading the paper so carefully, and we apologize for the confusion caused by the layout. We used the official ICLR 2027 style file without modification, and we have re-checked that the style file is unchanged. The larger spacing on the later pages arises because two figures and a table did not fit on one page: the table moved to the next page, and LaTeX automatically distributed the remaining space around the figures. In the revised manuscript, we will adjust the figure sizes and placement to remove this spacing.

Q2. Dependence on calibration documents and stability of the 0.21-point gap

Following your suggestion, we examined whether the results depend on the calibration documents. We rebuilt the permutation using four WikiText-2 documents, for which we found no 13-gram overlap with the 16 LongBench tasks, and re-evaluated CheeSe (permutation + OA) on the five models of Table 4. Changing the calibration changes the score by −0.08 to +0.11 points across the five models. With the new calibration, the gap to unstructured pruning is at most 0.29 points (Mistral), slightly larger than the 0.21 points reported in the paper. These results suggest that the effect is not sensitive to the specific calibration documents. In the revised manuscript, we will report the results under both calibrations.

ModelUnstructuredCheeSe, calibration in the paperCheeSe, WikiText-2 calibrationChange from calibration
Llama-342.6242.61 (−0.01)42.72 (+0.10)+0.11
Llama-3.145.2245.07 (−0.15)45.06 (−0.16)−0.01
Mistral38.4938.28 (−0.21)38.20 (−0.29)−0.08
Qwen346.4146.30 (−0.11)46.24 (−0.17)−0.06
Phi-442.2842.34 (+0.06)42.29 (+0.01)−0.05

Values in parentheses are the gap to unstructured pruning (16-task LongBench average). The last column is the WikiText-2 score minus the score with the calibration in the paper.

AuthorsOpenReview ↗

Response to Reviewer BkbY (2/2)

Q3. Original order vs. random permutation vs. HCR permutation

We appreciate this suggestion, which helped us better understand where the gain comes from. As you suggested, we evaluated random permutations (Llama-3-8B-Instruct, 16 LongBench tasks). A random permutation shuffles the channels independently for each (layer, head), and we evaluated three different seeds on the 16 tasks. The variation across the three seeds was small (41.59, 41.65, and 41.71).

A random permutation alone closes 44% of the gap between 2:4 and unstructured pruning. As the reviewer noted, this indicates that a substantial part of the gain (about half of that of HCR) comes from breaking up the clusters of important adjacent channels, which is consistent with the diagnosis in Section 3.1. HCR additionally places importance evenly across the groups and closes 86% of the gap (+0.73 over the random permutation), at the cost of a single sort, which is comparable to that of a random permutation.

Permutation16-task avg.Gap to unstructuredRecovery
2:4 + original channel order40.88−1.740%
2:4 + random permutation (mean ± std over 3 seeds)41.65 ± 0.06−0.9744%
2:4 + HCR permutation42.38−0.2486%
2:4 + HCR permutation + OA42.61−0.0199%

Recovery is the fraction of the gap to unstructured pruning (42.62) that the permutation closes.

Q4. End-to-end efficiency under identical settings

Following your suggestion, we measured efficiency under the same hardware, model, and input settings (NVIDIA A100 80GB, Llama-3.1-8B-Instruct (fp16), input length 32K, batch size 8, generation length 4,096). The three methods are dense (FlashAttention-2), unstructured (MUSTAFAR's official kernel), and CheeSe (the full method on HieraSparse's 2:4 kernel, including channel permutation and OA).

MetricDenseUnstructuredCheeSe (+OA)
End-to-end generation latency (s)180.81,139.8149.7 (1.21×)
End-to-end generation throughput (tok/s)18129219
Prefill time (s)32.8535.3232.10
Decode time (s)148.01,104.5117.6
Peak GPU memory (GB)66.052.850.4
KV cache (GB)36.023.620.3

In this setting, CheeSe showed a 1.21× shorter end-to-end latency than dense and a 44% smaller KV cache. Unstructured pruning also reduced memory substantially, while its latency was approximately 6.3× that of dense. We would like to add that CheeSe accelerates only the attention over the KV cache during decode, while prefill and the remaining decode operations (e.g., the MLP) are shared with dense. The 1.80× speedup of decode attention in Figure 2(b), measured at the same context length and batch size, therefore corresponds to 1.26× in decode and 1.21× end-to-end. The overheads of permutation, OA statistics collection, pruning, and sparse packing are listed below and are included in the latency above.

StepPrefill (of 32.10 s)Decode (of 117.6 s)Total (of 149.7 s)
Channel permutation0.01 s1.31 s1.32 s
OA statistics collection0.0004 s0.62 s0.62 s
OA score computation0.001 s0.14 s0.14 s
Pruning0.023 s0.007 s0.03 s
Sparse packing0.069 s0.020 s0.09 s
Total0.10 s (0.3%)2.10 s (1.8%)2.20 s (1.5%)

Regarding the unstructured baseline, MUSTAFAR is an important prior work that our study builds on, and we used its official kernel as faithfully as we could. We confirmed that it reproduces the speedup trend reported in the MUSTAFAR paper when the dense baseline is HuggingFace’s default attention, as in the released measurement script. When the dense baseline is changed to FlashAttention-2, the comparison becomes the one shown in the table above. We chose FlashAttention-2 because, to the best of our knowledge, it is widely used and efficient.

Thank you again for the helpful review.

AuthorsOpenReview ↗

Follow-Up to Your Review

Dear Reviewer BkbY,

We are sincerely grateful for your careful review. We have already posted our responses to each point you raised.

If your schedule permits, we would be truly thankful if you could let us know whether any concerns remain. We would be more than happy to provide further explanation.

With our sincere appreciation, The Authors of Submission 48

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Revision

We thank the reviewers for their comments. We have uploaded a revised paper, with the changes marked in blue. The new results are collected in Appendix E.

  • Efficiency: end-to-end latency, throughput, and memory for dense, unstructured, and CheeSe, across context lengths and batch sizes, with a breakdown of the overhead (E.1).
  • Permutation: a comparison with random permutations (E.3), a re-evaluation of the five models with calibration documents that do not overlap with LongBench (E.4), and an implementation that folds the permutation into the projection weights (E.2).
  • Other settings: 75% sparsity (E.5), MATH-500 and AIME 2024 with a reasoning model (E.6), and per-subtask RULER results on three models (E.7).
  • Output-aware selection: where it helps and why it works better after the permutation (E.8).

In the main text, we now describe unstructured pruning as a reference rather than an upper bound, and we report that CheeSe stays within 0.3 points of it. Details are in our responses to each reviewer.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.