acceptodds
Under review as a conference paper at ICLR 2027

EinSort: Sorting is All We Need for Tensorizing LLM

Abstract

Tensor networks provide efficient representations for compressing large neural networks, but identifying useful low-rank structure in foundation-model tensors remains challenging. We propose Einstein sorted sum (EinSort), an adaptive tensorization method that exposes low-rank structure through reversible index ordering before tensor decomposition. We prove that, under stated regularity assumptions, row-wise sorting of i.i.d. entries converges to a rank-one quantile template with relative Frobenius error ; sliced or shared permutations then limit metadata overhead in practical settings. We evaluate EinSort in two deployment regimes: KV-cache compression for language models and weight compression for vision-language and vision-language-action models. Across WikiText-2 language modeling, GSM8K mathematical reasoning, TextVQA visual reasoning, and LIBERO robot manipulation, EinSort consistently improves downstream quality relative to unsorted tensor decomposition and the practical low-rank baselines evaluated in each setting.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Tensor decomposition, LLM, Compression

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_JdqHOpenReview ↗
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
AuthorsOpenReview ↗

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:

Projection (rank)Input tokensPyTorch dense BF16 (μs)Packed CUDA (μs)Speedup
MLP gate (r=2)12897.343.02.26×
MLP up (r=7)12897.347.12.07×
MLP down (r=2)1663.535.81.77×

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.

AuthorsOpenReview ↗

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.

MethodRankEncoded bytesEncoding (ms) ↓Decoding (ms) ↓Total (ms)↓
EinSort (grouped)8340,800169.6934.85204.54
SVD (same rank)8248,640161.871.86163.73
SVD (same bytes)11340,800177.191.73178.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.

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

Authors introduce EinSort compression mechanism based on value-dependent index permutations for enabling almost lossless decompositions of original LLMs weights. EinSort combines sorting with magnitude transformations, separates sign information gauge fixing and activation preconditioning to reduce effective ranks of weight matrices and enhance the compression/reconstruction results compared to other competitros. The manuscript is well-written with rigorous theoretical derivations and wide experimental comparisons, covering visual question answering and robot manipulation tasks. Authors acknowledge, that the algorithm utilizes an additional storage for permutation, and provide a relatively fair comparison: not only in terms of perplexity but also in terms of downstream evaluations on different tasks.

Critical strengths
  • Experimental design is well-structured, broad and shows the effectiveness of the proposed EinSort algorithm.
  • Theoretical justification is accurate. It also has a useful discussion of practical implementation details, which allows to reproduce the experiments.
Critical weaknesses
  • The reported compression rates are still difficult to interpret as memory savings due to additional storage of permutation matrices. In recent work [1] authors provide the byte-wise comparison of the state-of-the-art compression methods, which show significant mismatch with the numbers provided in the original articles. Moreover, the comparison of the compression methods is provided only in the decompressed setting, while some of the mechanisms can work with compressed scenarios. The comparison with quantization baselines will also improve the quality of experimental section.
  • Baseline adaptations also matter: Palu [2] performs offline weight decomposition, while SVD-LLM [3] has materially different whitening-only and updated variants. Equal calibration sizes do not resolve these differences.
  • Right now sorting is confounded with other compression mechanisms. The best configurations combine sorting, magnitude mapping, sign separation, gauge fixing, and activation statistics. Table 5 lacks an unsorted magnitude/sign-separated control at equal total bytes. Search spans folds, axes, maps, reductions, topology, and ranks without a reported search budget or selection split.

[1] Zagitov A. et al. Rethinking the Role of Tensor Decompositions in Post-Training LLM Compression //arXiv preprint arXiv:2606.03465. – 2026.

[2] Chang C. C. et al. Palu: KV-cache compression with low-rank projection //International Conference on Learning Representations. – 2025. – Т. 2025. – С. 50222-50249.

[3] Wang X. et al. Svd-llm: Truncation-aware singular value decomposition for large language model compression //International Conference on Learning Representations. – 2025. – Т. 2025. – С. 19299-19319.

Questions for authors
  • Сan you please provide the missing comparisons and answer the question about the possibility of using the proposed mechanism in its decomposed form will substantially strengthen the paper?
  • Full metric/configuration recipes, cache update/re-compression rules, baseline variants, selection budgets, and raw outcome counts will improve the quality of the comparison.
  • Can you add fixed-configuration unsorted/random/sorted controls and separately tuned baselines?
2 comments
AuthorsOpenReview ↗

Storage cost and index ordering impact

Thank you for asking us to isolate the contribution of index ordering and account for its storage cost. In our paper, we included all required metadata storage in the compression analysis. As detailed in our response to hTYe, we now explicitly report total codec bytes for both model weights (SmolLM2-135M backbone: 212,336,640 BF16 bytes to 31,843,029 codec-accounted bytes with EinSort) and KV caches (1,474,560 BF16 bytes to 274,640 with KIVI + EinSort or 206,472 with TurboQuant + EinSort). The KV representations were physically serialized; the weight figure is an accounted codec size.

To isolate sorting, we hold tensor layout, factor rank, BF16 factor precision, gauge, sign handling, and the metadata budget fixed, and compare non-sorting (identity ordering) with EinSort sorting. We evaluate SmolLM2-135M on 128 WikiText-2 test windows (8,064 scored tokens):

Factor rankEncoded bytesNo sorting (identity) PPL ↓EinSort PPL ↓
4347,68349.17047.873
8596,38348.86646.617
11781,66443.42841.523
181,209,79623.00222.988

Sorting reduces PPL by 2.64%, 4.60%, and 4.39% at ranks 4, 8, and 11, respectively; the rank-18 difference is negligible. Thus, the gains at lower ranks cannot be explained by changes in rank, factor precision, or gauge. We also acknowledge that sorting is not always beneficial: the selected sorting statistic matters. These ablations support an index-ordering benefit in selected low-rank regimes.

I thank authors for a detailed reply. However, I am still not convinced about the index-ordering benefit, thus after rank-18 authors claim that there is more negligeable difference compared to the results for lower factors. Moreover, I highly doubt the results for inference, where the reported speedup mathes the results of quantization mechanisms and diffusion-LLM approaches. Even if the optimal CUDA kernels for matrix multiplication were created by authors, such a speedup looks magical due to several matrix multiplications instead of one and storing additional information for each layer of the network. Therefore, I maintain my score as is.

Reviewer_hTYeOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes EinSort, which inserts a reversible permutation of tensor entries before a tensor decomposition. The decomposition is applied to the sorted tensor, and the inverse permutation is applied after reconstruction. To keep permutation storage manageable, the authors share one permutation across slices. The sort key is a reduction of a power-mapped score, optionally combined with a stored sign bit and gauge fixing. On the theory side, Lemma 2.1 shows that row-sorting an i.i.d. matrix gives a matrix close to a rank-one quantile template, with relative error O_p(N^{-1/2}). Experiments cover KV-cache compression and weight compression for VLMs and VLAs. They report large gains over SVD-based baselines at equal nominal compression rates.

Critical strengths
  1. Treating index ordering as a design dimension of tensor networks is an interesting idea in some senses, and the einsum-based framing is general.

  2. The experiments span several modalities: language modeling, math reasoning, TextVQA, and robot manipulation.

Critical weaknesses
  1. The method is effectively a quantizer, but quantization baselines are missing. The appropriate baselines are KV-cache quantization (KIVI, QJL, TurboQuant) and weight quantization (GPTQ, AWQ),

  2. The theory is narrower than claimed and does not explain the empirical results. The lemma only shows that sorted i.i.d. rows look alike. All the information has moved into the permutation, and the lemma says nothing about why the compressed models still perform well.

Questions for authors
  1. What is the total memory per element (cores + permutation + sign bits + any preconditioner) at each reported point? How do the results look when plotted against total bits?

  2. How does EinSort compare with KIVI, QJL, or TurboQuant (KV cache) and GPTQ or AWQ (weights) at matched total bits?

  3. The title overclaims. The writing of this paper should be significantly improved. The paper relies too heavily on pseudocode, including in the main content.

4 comments
AuthorsOpenReview ↗

# Response to Reviewer hTYe: Theory and approximated-sorting reconstruction error

We thank the reviewer for questioning the scope of Lemma 2.1. We agree that the original i.i.d. row-sorting result does not, by itself, establish accuracy or model-memory savings. We could extend the theory to derive the upper bound for approximated sorting when we use rank-1 decomposition. We specifically consider grouped sorting, evaluated alongside row-wise sorting on pretrained Qwen3-0.6B weights in Fig. 2; more detail spectra analysis in Appendix C and Fig. 8.

As specified, each row is sorted in descending value order to identify rank groups of g entries, then the original column indices are restored to ascending order within each rank group. Thus group membership is sorted, but within-group order is not. Let S_g be the resulting matrix and B its row-wise group-mean matrix (one mean for every consecutive group of g columns). We obtain the following finite-sample upper bound:

\leq \|W\|_F^2-g\sigma_1(B)^2,$$ where $\sigma_1$ denotes the largest singular value. The bound holds for **arbitrary matrices**: it does not require i.i.d. entries or a particular weight distribution. It follows by projecting onto the subspace constant within each group and using the best rank-one approximation of `B`. Exact inverse permutation preserves the Frobenius reconstruction error. **New validation on the actual Fig. 2 weight matrix.** Using the first-layer Qwen3-0.6B `v_proj` matrix (`1024 x 1024`) analyzed in Fig. 2, we compared this upper bound with the optimal rank-one SVD reconstruction error. The table reports **unnormalized squared Frobenius errors**, consistent with Fig. 2. | Group size `g` | Theoretical upper bound | Measured rank-1 error | Gap | |---:|---:|---:|---:| | **1 (row sorting)** | 2.3380 | 2.3380 | 0.00% | | 8 | 3.5110 | 3.5087 | 0.07% | | 16 | 5.3624 | 5.3568 | 0.11% | | 32 | 9.8203 | 9.8055 | 0.15% | | **64** | **20.5207** | **20.4749** | **0.22%** | | 128 | 46.7959 | 46.6316 | 0.35% | | 256 | 112.6016 | 111.9234 | 0.61% | | 512 | 281.3024 | 278.0123 | 1.18% | | **1024 (unsorted original)** | 742.7932 | 739.8503 | 0.40% | At **`g=64`**, the group size used in Fig. 2, the bound is **20.5207**, compared with an actual optimal rank-one error of **20.4749**, a gap of only **0.22%**. The unsorted original matrix has rank-one error **739.8503** as in Fig. 2, whereas row sorting (`g=1`) gives **2.3380** as in Fig. 2. Therefore, the finite-sample certificate accurately characterizes the empirical group-sorting rank-one error in this pretrained weight matrix, including the substantial improvement relative to the original index order. When we assume i.i.d. `Uniform[-1,1]` entries, we can additionally derive an explicit group-size-dependent expectation bound for `N` columns: $$\frac{\mathbb{E}[E_1(S_g)]}{\mathbb{E}[\|W\|_F^2]} \leq \frac{2}{N+1}+\frac{g^2-1}{(N+1)^2},$$ showing how approximation error trades against more economical approximated permutations: tensor storage will be reduced from $MN$ to $M+N$ with rank 1 representation, while permutation storage can be reduced with $g$ as $\lceil M\log_2(N!/(g!)^{N/g})\rceil$ bits. For $N=1024$ and $g=64$, it is less than 4 bits per element. These results strengthen the theoretical basis of grouped sorting without claiming that an $L_2$ weight-reconstruction bound alone guarantees downstream accuracy. We will clarify total stored bits (including permutations and signs) and quantization baselines in separate responses.
AuthorsOpenReview ↗

Additional experiments: Low-rank decomposition versus AWQ/GPTQ quantization

Thank you for requesting direct quantization baselines. Following our earlier responses concerning permutation storage, we added model-wide weight-compression experiments comparing the official llm-compressor AWQ/GPTQ implementations. We compress all linear projections in the SmolLM2-135M transformer backbone (originally 212,336,640 BF16 bytes) and evaluate WikiText-2 validation negative log-likelihood (NLL). AWQ/GPTQ use group size 64 and mixed 2/3/4-bit weight allocation.

MethodBackbone retentionBackbone bytes (incl. metadata)WT2 NLL ↓
EinSort (BF16 factors)10%21,228,7828.5204
EinSort (BF16 factors)15%31,837,3096.6398
GPTQ (mixed 2/3/4-bit)15%31,826,2089.7367
AWQ (mixed 2/3/4-bit)15%31,826,20816.9389

At around 15% backbone retention, EinSort yields lower NLL than both AWQ and GPTQ at essentially the same total storage. Moreover, 10% EinSort outperforms 15% GPTQ (8.5204 vs. 9.7367 NLL) even with 10,597,426 fewer backbone bytes. The llm-compressor's AWQ/GPTQ configurations cannot meet a 10% storage budget: even all-2-bit weights require 29,863,200 bytes (14.06%) including metadata, and no 1-bit option was available in the official configuration.

Please note that EinSort is a low-rank tensor decomposition method, not a quantizer. Sorting exposes low-rank structure, enabling adjustable rank and factorization geometry while the retained factors remain BF16. Decomposition, quantization, and pruning are complementary techniques, and our decomposed factors may be further quantized or pruned. All byte totals in this paper account for stored tensor data and required metadata: BF16 factors, permutation, sign/gauge information, and codec headers for EinSort; packed weights, scales, and offsets for AWQ/GPTQ.

These weight-compression experiments demonstrate the advantage of EinSort over the AWQ/GPTQ quantization for model compression.

AuthorsOpenReview ↗

KV cache reduction: decomposition and quantization

We thank the reviewer for requesting comparisons with practical quantization methods. We agree that low-rank decomposition is not always superior to quantization. Our core contribution is instead to improve decomposition-based compression by exposing low-rank structure through reversible index ordering. Importantly, this mechanism can also complement quantization.

New comparison with KV cache quantization:

We evaluated pretrained SmolLM2-135M on the WikiText-2, comparing KIVI, TurboQuant, EinSort, and their hybrids. Storage accounting includes all packed quantized values, scaling parameters, EinSort factors, permutations, sign information, and hybrid routing metadata.

KV-cache methodPacked bytesBF16 retentionTest PPL ↓
Uncompressed BF161,474,560100.00%21.9405
KIVI (2-bit)276,48018.75%25.4565
EinSort273,40318.54%26.8607
KIVI + EinSort274,64018.63%25.2160
TurboQuant (2-bit)207,36814.06%34.3054
EinSort205,48313.94%55.8626
TurboQuant + EinSort206,47214.00%30.9237

At essentially matched storage around 14%, TurboQuant + EinSort reduces perplexity by 9.86% relative to TurboQuant alone. Its paired block-bootstrap interval for the hybrid-minus-quantizer NLL is [−0.1305, −0.0777], favoring the hybrid. At around 19% packed bytes, KIVI + EinSort reduces PPL by 0.94%, although it is not statistically significant.

These results indicate that quantization and decomposition are complementary. Standalone decomposition is not always better than quantization but competitive, and hybrid quantization & decomposition can be advantageous.

EinSort's advantage over existing decomposition methods

More importantly, our primary contribution should be evaluated within the family of low-rank decomposition methods. The manuscript already demonstrates substantial improvements over SVD, LoRC, xKV, and Palu.

For example, on Phi-4-mini/GSM8K, the reported decomposition accuracy gives:

Method40% retained KV20% retained KV
SVD1.44%0.61%
LoRC0.53%0.08%
xKV0.83%1.21%
Palu58.61%2.96%
EinSort72.93%76.04%

At 20% retained KV factors, EinSort achieves 76.04 ± 1.18% accuracy, compared with 2.96 ± 0.47% for Palu and 1.21 ± 0.30% for xKV. These results demonstrate substantial robustness under aggressive decomposition.

The manuscript further demonstrates EinSort's effectiveness for model-weight decomposition in VLMs and VLAs, including Qwen3-VL on TextVQA and multiple robotic policies on LIBERO.

We emphasize:

  1. EinSort substantially improves low-rank decomposition by exposing structure through reversible index ordering, outperforming the evaluated decomposition baselines.
  2. Decomposition and quantization can be combined. Hybrid quantization with EinSort demonstrates additional compression-quality gains over standalone quantization in some regimes.

Thus, EinSort should not be viewed as a replacement for quantization but as an additional, broadly applicable compression mechanism that can complement quantization, pruning, and other model-compression techniques.

AuthorsOpenReview ↗

Title, Presentation, and Reproducibility

We thank the reviewer for the constructive suggestions on the title and presentation.

Title. While we believe the current title captures the central insight of our work, we agree that “Sorting Is All We Need” may suggest a broader claim than intended. We therefore propose a more precise title:

“EinSort: Permutation-Guided Tensor Decomposition for Model Weights and KV-Cache Compression.”

This title more directly communicates both our methodological contribution and its applications.

Presentation. We will improve the paper's readability by streamlining the main text, reorganizing the discussion around the core idea and experimental findings, and moving secondary technical details and extended discussions to the appendix. We will also clarify the connections between the theoretical motivation, practical algorithm, and empirical results.

Pseudocode and reproducibility. We appreciate the reviewer's concern about the extensive use of pseudocode. We intentionally provide implementation-oriented examples because we believe reproducibility and accessibility are important. Most of our pseudocode uses actual PyTorch operations and can be executed directly or with minimal adaptation, allowing readers to experiment with the proposed methods. We will reorganize these examples, keeping the essential algorithms in the main text and moving more detailed implementations to the appendix. This will improve the narrative flow while preserving the practical information needed to reproduce and extend our work.

We appreciate these suggestions and believe the proposed revisions will make the paper clearer and more accessible to a broader audience.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.