- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes EinSort, which applies reversible index ordering before tensor decomposition to compress model weights and KV caches. It combines sorting with shared permutations and optional sign-preserving non-negative mappings to balance approximation quality and storage overhead.
Critical strengths
- Sorting provides a simple and intuitive way to expose low-rank structure.
- Evaluation spans language modeling, reasoning, visual question answering, and robot manipulation.
- Ablations cover sorting metrics, nonlinear mappings, gauge fixing, and tensor topologies.
Critical weaknesses
- Reported compression ratios are not clearly linked to total stored bytes, including permutations and sign bits; measured peak-memory savings are missing.
- Decoding is slower than the uncompressed baseline, and sorting/decomposition construction costs are not quantified.
- KV-cache experiments use short sequences, leaving long-context quality and incremental cache-update costs unclear.
- The rank-one theorem relies on restrictive distributional assumptions and does not directly justify the practical shared-permutation scheme.
Questions for authors
What are the actual memory savings after including permutation metadata and sign bits?
2 comments
KV-Cache Latency, GPU Memory, and Extended Theoretical Analysis
We thank the reviewer for the constructive feedback. Following our earlier response on direct CUDA execution and GPU-memory savings, we conducted additional experiments to quantify KV-cache encoding and decoding latency. We also wish to highlight our extended theoretical analysis of practical grouped sorting.
1. KV-cache encoding and decoding latency
We benchmarked EinSort against truncated SVD using a fixed BF16 KV cache of shape [30 layers, 2 (K/V), 1 batch, 3 heads, 64 tokens, 64 dimensions] on an NVIDIA RTX 5090. The original cache occupies 1,474,560 bytes. We measure the complete encoding and decoding procedures, including factor serialization and metadata processing, using 10 timing repetitions.
| Method | Rank | Encoded bytes | Encoding (ms) ↓ | Decoding (ms) ↓ | Total (ms)↓ |
|---|---|---|---|---|---|
| EinSort (grouped) | 8 | 340,800 | 169.69 | 34.85 | 204.54 |
| SVD (same rank) | 8 | 248,640 | 161.87 | 1.86 | 163.73 |
| SVD (same bytes) | 11 | 340,800 | 177.19 | 1.73 | 178.92 |
At identical storage of 340,800 bytes (23.11% of the original), EinSort encoding is approximately 4.2% faster than SVD. The current implementation has higher decoding overhead, associated with metadata processing and inverse permutation. Nevertheless, the total latency is comparable to plain SVD.
We further investigated torch.compile and CUDA Graph replay for GPU-resident reconstruction. With max-autotune-no-cudagraphs and CUDA Graph replay, EinSort's GPU-only decoding latency decreases from 64.45 to 10.96 μs (5.88× speedup).
These experiments show that EinSort's encoding cost is comparable to SVD and that its GPU reconstruction operations can benefit substantially from compilation and CUDA Graph replay.
2. Actual GPU-memory savings and compressed execution
As reported in our previous response, our compression accounting includes tensor factors, permutation indices, sign information, and required codec metadata.
We additionally measured GPU memory during compact-weight execution on Qwen3-0.6B. Resident GPU memory decreases from 1,136.9 to 513.2 MiB, while peak memory decreases from 1,197.4 to 573.7 MiB (52.1% reduction). These measurements directly demonstrate memory savings without retaining a dense-weight copy.
Our native CUDA experiments also demonstrate that executing compressed factors can be faster than dense BF16 operations. Across 700 tested module/token configurations on an NVIDIA A40, packed CUDA execution outperformed dense PyTorch BF16 in 572 cases, with representative operator-level speedups up to 2.26×.
3. Extended theoretical justification for grouped sorting
We agree that our original rank-one theorem, based on row-wise sorting of i.i.d. entries, does not directly justify the practical shared-permutation scheme.
As explained in our response to reviewer hTYe, we have extended the theory to establish a finite-sample upper bound on rank-one reconstruction error under grouped sorting, applicable to arbitrary matrices without distributional assumptions.
This extension is practically relevant because EinSort evaluates grouped sorting as one approach to balancing reconstruction accuracy against permutation-storage overhead. For the pretrained Qwen3-0.6B weight matrix in Fig. 2, grouped sorting with g=64 gives a squared rank-one reconstruction error of 20.4749, compared with the theoretical upper bound of 20.5207 (0.22% gap) and 739.8503 for the unsorted matrix.
Thus, the new bound closely characterizes the reconstruction behavior of a practical grouped-sorting configuration. Although it does not directly establish a guarantee for shared permutations across slices, it extends our theoretical understanding to a storage-efficient sorting mechanism used within the EinSort framework.
4. Longer-context deployment and incremental updates
We appreciate the reviewer's concern about longer KV-cache sequences and incremental updates. Our new latency experiment provides a concrete measurement of construction and reconstruction costs for a fixed cache size. Longer-context compression quality and efficient incremental updates remain important areas for further evaluation. We will clarify the experimental scope and these deployment considerations in the revised manuscript.
We hope these additional results strengthen the practical and theoretical understanding of EinSort, particularly its measured memory savings, achievable GPU acceleration, and reconstruction guarantees for grouped sorting.
Direct packed CUDA execution and GPU memory
We thank the reviewer for highlighting practical inference efficiency. As discussed in our responses to hTYe and ZQgV, we have added full codec-byte accounting for both model weights and KV caches. We also implemented native CUDA kernels that operate directly on compact EinSort representations, using compact resident parameters and bounded temporary workspace rather than maintaining a persistent decoded dense-weight copy.
We conducted an NVIDIA A40 microbenchmark tournament across 100 eligible factor modules and 700 module/token configurations. Of these, native rank-space CUDA execution was faster than PyTorch dense BF16 in 572 configurations by median latency. Representative qualified speedups are:
Kernel performance depends on tensor geometry, token count, rank, and codec configuration. Separately, on Qwen3-0.6B, CUDA Graph replay improved the packed 128-token decoder from approximately 1,440 to 787 ms (1.83× versus packed eager inference).
We further measured end-to-end GPU memory on a Qwen3-0.6B model with 196 compressed projections at a selected weight retention. Packed execution reduced resident GPU memory from 1,136.9 to 513.2 MiB and peak GPU memory from 1,197.4 to 573.7 MiB, without retaining a full dense-weight copy.
These experiments demonstrate that practical compact-resident execution is achievable and that native CUDA kernels can deliver computational gains for suitable configurations.