CS Paper Radar

Hybrid Compression for Memory-Efficient Matrix-Vector Multiplication

Felipe A. Louza, Giovanni Manzini, Guilherme P. Telles

cs.LG ·submitted 2026-11-13 01:27 UTC · v1

Abstract

Iterative machine-learning algorithms repeatedly access large real-valued matrices through matrix-vector products, and their performance is limited by memory bandwidth rather than arithmetic throughput. Lossless compression schemes that support computation directly over the compressed data reduce both the data moved and the memory footprint of these workloads. The mm-RePair framework [11] follows this approach by applying the RePair grammar compressor to the Compressed Sparse Row/Value (CSRV) representation of a matrix and performing matrix-vector multiplications directly on the compressed data. Its effectiveness, however, degrades on matrices that are dense or contain many distinct values. In this paper we present a hybrid strategy for the mm-RePair framework that combines grammar and entropy compression. The CSRV sequence is partitioned into a grammar-compressible component, formed by the entries that mm-RePair can compress effectively, and an entropy-compressible component holding the remaining entries, which is encoded with the ans-fold coder [24]. Compression improves further by sorting and delta encoding the entries of each row in the CSRV representation, and by remapping the alphabet to a contiguous range. Experiments on real-valued machine-learning matrices, including word embeddings and transformer hidden states, show that our hybrid strategy is more compact than the original \mmRepair on every input and reduces the peak memory of multiplication, with the largest gains on dense matrices with many distinct values, at competitive multiplication times. It also outperforms the column-reordering variant of \mmRepair on most of the matrices, and combining the two is even more compact on the sparse ones, at the cost of a much longer compression time. Finally, our strategy scales with the number of threads as well as the original \mmRepair does.

Closest papers

Nearest neighbours by meaning across the whole index.

Computation-Friendly Compression of Matrices: Speeding up Linear and Boolean Algebra

cs.DS ·2026-10-26 ·Gonzalo Navarro
survey similarity 0.62
Abstract

Large sparse matrices---adjacency matrices of web and social graphs, feature matrices of machine-learning pipelines, the relations of graph databases---are routinely compressed to save space. Classical compressors, however, force the matrix to be decompressed before it can be used, so the space savings often yield a computational overhead. A recent line of work studies \emph{computation-friendly} compression: formats that are not only small, but let us carry out matrix--vector products, and in some cases matrix--matrix products, sums and closures, directly on the compressed representation {\em in time proportional to that compressed size}. This survey organizes that literature around the kind of redundancy each format exploits: spatial clustering of the nonzeros ($k^2$-trees and their variants), similarity between rows (Boldi--Vigna-style referencing and set-difference compression), repeated substrings (grammar compression), and dense bipartite substructures (bicliques). For each family we describe the representation, the algorithms, the theoretical guarantees and the empirical performance. Further, we show that the last three families are instances of a single general scheme, which we call a {\em sparse straight-line factorization} of the matrix, whose forward and backward substitutions evaluate right and left products in time proportional to the size of the representation, and that the product of two such factorizations is again one, which gives matrix--matrix products with a compressed output. We also relate the model to linear circuits, give simple recompression steps, and study the size of the smallest factorization: worst-case bounds, separations from each family, and parallelism. We close with a cross-family comparison and a list of open problems.

0.42

Differentiable Bit-Widths: Co-optimizing Pruning and Quantization via SVD for Ultra-Efficient LLM Compression

cs.CL cs.AI ·2026-10-05 ·Hankyul Kang, Jongbin Ryu
top venuecode/datahot direction similarity 0.62
Abstract · Accepted to Advances in Neural Information Processing Systems (NeurIPS 2026)

SVD-based pruning and quantization have recently emerged as a promising strategy for the ultra-efficient compression of large language models. In these methods, compression is performed in two stages: components are first truncated, and the remaining ones are subsequently quantized. Although this decoupled pipeline benefits from both pruning and quantization, it requires separate optimization for each stage and fails to fully exploit their balance, which can lead to suboptimal performance under aggressive compression. To address this limitation, we propose a new LLM compression method that co-optimizes pruning and quantization in a unified framework. Our key idea is a differentiable method for learning component-wise bit-widths, allowing less important components to be assigned 0-bit precision and pruned away. Notably, our method performs favorably against two-stage baselines, even when subjected to extreme quantization settings ($1.61$ bits) designed for ultra-efficiency. Code: https://github.com/MMAI-Laboratory/DBW.

0.52

COBALT: Column-swapping Optimized Bit-serial Accelerator for LSTM Tasks

eess.SP ·2026-08-19 ·Mohd Tasleem Khan
similarity 0.59
Abstract

Long Short-Term Memory (LSTM) networks continue to be widely deployed for real-time sequential tasks on edge devices, yet their computational demands challenge deployment on resource-constrained hardware. This work introduces COBALT, a bit-serial compressed LSTM accelerator built on a matrix (input)-vector (weight) reformulation of the standard circulant matrix-vector multiplication (MVM) with offset-binary coding. A novel column-swapping scheme operates on partial products at the bit level when generated in pairs, systematically exposing redundancy across output rows to reduce the number of PP generators and selectors. This redundancy is further exploited using a lightweight correction unit that derives a row's output directly from its paired row. Additionally, for block-circulant MVMs, relocating the shift-accumulate and correction units of each sub-MVM further reduces resource usage. The compressed network achieves weight compression of up to 93.6% while maintaining accuracy on the TIMIT and LibriSpeech-100h benchmarks. On a field-programmable gate array, COBALT achieves superior overall efficiency relative to state-of-the-art LSTM accelerators.

0.12

Bit-Sparsity Aware Acceleration with Compact CSD Code on Generic Matrix Multiplication

cs.AR ·2026-11-11 ·Zixuan Zhu, Xiaolong Zhou, Chundong Wang, Li Tian, Zunkai Huang +1 more
top venuehighly cited similarity 0.58
Abstract · Accepted for publication in IEEE Transactions on Computers (TC)

The ever-increasing demand for matrix multiplication in artificial intelligence (AI) and generic computing emphasizes the necessity of efficient computing power accommodating both floating-point (FP) and quantized integer (QINT). While state-of-the-art bit-sparsity-aware acceleration techniques have demonstrated impressive performance and efficiency in neural networks through software-driven methods such as pruning and quantization, these approaches are not always feasible in typical generic computing scenarios. In this paper, we propose Bit-Cigma, a hardware-centric architecture that leverages bit-sparsity to accelerate generic matrix multiplication. Bit-Cigma features (1) CCSD encoding, an optimized on-chip sparsification technique based on canonical signed digit (CSD) representation; (2) segmented dot product, a multi-stage exponent matching technique for long FP vectors; and (3) the versatility to efficiently process both FP and QINT data types. CCSD encoding halves the cost of CSD encoding while achieving optimal bit-sparsity, and segmented dot product improves both accuracy and throughput. Bit-Cigma cores are implemented using 65 nm technology at 1 GHz, demonstrating substantial gains in performance and efficiency for both FP and QINT configurations. Compared to state-of-the-art Bitlet, Bit-Cigma achieves 3.2\texttimes{} performance, 6.1\texttimes{} area efficiency, and 15.3\texttimes{} energy efficiency when processing FP32 data while ensuring zero computing error.

0.68

AdaBool: Sparse Boolean Matrix Processing with Adaptive Data Representation

cs.DB cs.DC ·2026-10-15 ·Xiangrui Yang, Yifan Lei, Jiawei Yang, Yekang Zhan, Yuxin Zheng +4 more
top venue similarity 0.58
Abstract · Accepted to ACM SIGMOD 2027 (Proceedings of the ACM on Management of Data). 16 pages, 21 figures, 7 tables

Many data processing tasks revolve around determining whether logical relationships exist between two sets of entities, a pattern that can be naturally modeled as Sparse Boolean Matrix Multiplication (SpBMM). Under Boolean semantics, matrix representations no longer need to store numerical values and instead focus on encoding the positions of non-zero elements, making it highly amenable to data compression for substantially lower memory access overhead. The key challenge, however, is that the most effective compression depends heavily on sparsity distribution: different methods perform best at different sparsity levels, while real-world matrices often contain sharply varying sparsity across regions. Consequently, forcing the entire matrix into any fixed, monolithic representation leaves considerable optimization opportunities untapped. We present AdaBool, a SpBMM framework designed to reconcile this tension through an adaptive data representation. AdaBool partitions matrices into fine-grained element blocks and represents each block with the encoding best matched to its local sparsity. On top of this adaptive encoding, AdaBool introduces a heterogeneous GPU execution model that groups blocks by encoding type and maps them to matching processing paths, enabling efficient execution and scheduling across GPU resources. We implement AdaBool end to end with low-level system optimizations, evaluate it on both production and public workloads, and show that it outperforms representative baselines by over an order of magnitude.

0.71

Algebraic Integer Quantization for Machine Learning Applications

cs.LG ·2026-09-25 ·Anthony Kostal-Vazquez, Vassil Dimitrov, Branden Butler
similarity 0.57
Abstract

In this article, we propose algebraic integer number formats (AINF) as a framework for highly configurable and accurate compressed computation. A key property of AINF is its straightforward reduction to purely integer arithmetic, enabling error-free multiply-accumulate operations. We develop a matrix multiplication engine that exploits this property, obtaining performance within a predictable factor of the most efficient numerical counterparts on modern hardware accelerators. Another key advantage of AIQ is the freedom to select algebraic integers tailored to the numerical characteristics of a given use case, offering optimization opportunities that are fundamentally unavailable in floating-point or fixed-point formats. Motivated by these properties, we introduce algebraic integer quantization (AIQ), a lossy compression format for large language model (LLM) inference, and provide results demonstrating that AIQ achieves competitive accuracy compared to the industry-standard MX format across a diverse set of models and benchmarks at equivalent bit-per-parameter budgets. The experiments presented in this article employ algebraic integers of degree two (quadratic integers); generalizations to higher-order and, in particular, multidimensional algebraic integers promise even greater computational advantages and remain a promising direction for future work.

0.28

Residual Sparsification via Output Importance for Compressing Mixture-of-Experts LLMs

cs.AI ·2026-09-01 ·Seungwoo Jung, Dohyeok Kwon, Seungmin Cha, Junseok Lee, Yeonho Yoo +2 more
top venuecode/data similarity 0.57
Abstract · Accepted to EMNLP 2026 (Main Conference)

Mixture-of-experts (MoE) architectures scale large language models efficiently, but they demand massive GPU memory. To cope with such demand, models are commonly compressed to reduce their memory footprint. Residual sparsification is a representative compression technique that decomposes each projection matrix of an expert into a shared base matrix and per-expert residual matrix, and then compresses the residuals. Existing sparsification methods compress each residual matrix independently by minimizing its compression error, thereby minimizing the error of each projection matrix. However, our analysis shows that this objective is misaligned with preserving model accuracy after compression. In an expert, the final output is produced through computations coupled across multiple projections and hidden representations. Therefore, even small errors in individual matrices can propagate through hidden representations and projection interactions, leading to large expert output errors and accuracy degradation. To address this misalignment, we propose PARSER, a new residual sparsification method that shifts the compression objective from minimizing isolated matrix errors to preserving the expert output error. PARSER achieves this by introducing output importance, which measures the actual contribution to the expert output error. Our experiments show that, compared with existing methods, PARSER narrows the accuracy gap to the uncompressed model by 1.41$\times$ on Qwen and 1.44$\times$ on DeepSeek, while achieving the same peak memory reduction. Our code is available at https://github.com/OSSS-KU/PARSER.

0.43

Trainable Vector Quantization for Large Language Models

cs.LG ·2026-10-30 ·Anastasiia Prutianova, Alina Bogdanova, Mikhail Shutov, Dmitrii Poimanov, Anatoly Gorkov +1 more
published similarity 0.55
Abstract · ECML PKDD 2026, Research Track

Vector Quantization (VQ) is a rapidly evolving technique for compressing Large Language Model (LLM) weights, reducing memory usage, and speeding up inference. However, extreme compression deteriorates model performance, which is challenging to recover due to the discrete nature of VQ parameters. Existing methods employ training-free approaches that are limited to layer-wise reconstruction loss minimization. To address this limitation, we propose TVQ, a novel method that leverages straight-through estimation to enable gradient descent-based optimization of vector-quantized LLMs. By reformulating VQ LLM optimization with trainable latent weights, TVQ enables arbitrary objective minimization. We constitute our approach by applying TVQ in a block-wise knowledge distillation paradigm, which balances quality and training efficiency, and propose several practical solutions to accelerate training. In experiments on modern LLMs, we demonstrate that TVQ is compatible with modern VQ schemes. As a result, TVQ achieves state-of-the-art quality in low-bit post-training quantization settings with a modest training budget and straightforward PyTorch implementation. For instance, TVQ achieves near-lossless 2-bit quantization for LLaMA2-70B with only 1% accuracy drop on popular Question-Answering benchmarks.

0.23