Linear Computation Coding

Ralf R. Müller, Bernhard Gäde, Ali Bereyhi

Abstract

Inference in deep learning models is often constrained by the computational cost of matrix-vector multiplication (MVM). This paper introduces "linear computation coding," a framework that treats MVM as a lossy compression problem. By decomposing a target matrix into a codebook and a sparse wiring matrix composed of powers of two, the authors achieve high-precision results using only bit-shifts and additions. This approach reduces computational costs by up to 80% compared to standard 16-bit arithmetic, with efficiency increasing as matrix dimensions grow.

Introduction

In the world of Deep Learning, the "inference phase"—running a trained model—is where the rubber meets the road. While training typically occurs on massive GPU clusters, inference often happens on low-power edge devices. The primary computational bottleneck in these environments is matrix-vector multiplication (MVM). Unlike matrix-matrix multiplication, which benefits from sub-cubic algorithms like Strassen’s, MVM is notoriously difficult to optimize without making restrictive assumptions about the matrix, such as sparsity.

Linear Computation Coding (LCC) addresses this challenge by applying principles from rate-distortion theory to the computation itself. The authors propose that we can treat the multiplication of an arbitrary known matrix by an unknown vector as a lossy compression problem, allowing for significant hardware simplifications with negligible loss in precision.

Methodology

The core of LCC is the decomposition of a target matrix $T$ into the product of two matrices: $T \approx B \times W$.

  1. The Codebook ($B$): This matrix contains "representative" columns or codewords. These can be pre-defined, such as a "Mailman" codebook, or "self-designed" based on the specific distribution of the target matrix to ensure the codewords are optimally suited for the task.
  2. The Wiring Matrix ($W$): This is a sparse matrix that selects and scales columns from the codebook. Crucially, the entries in $W$ are restricted to zero or signed integer powers of two (e.g., $\pm 2^k$).
Geometric interpretation of approximating a target vector using a scaled codeword from the codebook.

Because the entries of $W$ are powers of two, "multiplication" by $W$ is reduced to simple bit-shifts and additions in hardware. To find the best wiring matrix, the authors utilize a greedy sparse recovery algorithm. This algorithm breaks the problem down column-by-column, iteratively picking the codebook entries that best approximate the target matrix's columns, as visualized in the geometric diagram above. The process can be further refined using multiple wiring matrices ($W = W_1 W_2 ... W_L$) to improve approximation accuracy with minimal additional computational cost.

Key Insights

  • Computation as Lossy Compression: The most profound idea in this work is the analogy to Information Theory. Just as we accept a small amount of "distortion" to compress a video, we can accept a tiny amount of "computation error" to drastically simplify the underlying math.
  • The Logarithmic Advantage: The authors demonstrate that the number of rows in the codebook should scale logarithmically with the number of columns. This exploits the "extreme-value statistics" of high-dimensional space, where a "close enough" vector can be found in a large enough random codebook with high probability.
  • Vanishing Marginal Cost: Unlike standard methods where the cost per matrix entry is constant, in LCC, the computational cost per entry actually decreases as the matrix gets larger. This makes the technique increasingly valuable for the massive layers found in modern transformer models.

Results and Performance

The authors evaluated LCC using IID Gaussian random matrices as a theoretical benchmark for unstructured data, as well as synthetic 4k-vectors to demonstrate scaling for modern neural network layer sizes. The quantitative gains are significant:

  • Multiplier-Free Hardware: The algorithm completely eliminates the need for hardware multipliers, which are significantly more expensive in terms of silicon area and power than adders.
  • High-Precision Efficiency: To match the precision of 16-bit signed integer arithmetic for 4096-dimensional vectors, the method requires only 1.5 adders per matrix entry—an 80% reduction in cost compared to standard benchmarks. For 8-bit accuracy, the cost drops further to roughly 1 addition per entry.
Distortion (log D) vs. number of additions (s) for various matrix dimensions (N).

As shown in the figure above, for a fixed number of additions $s$, the approximation error (distortion $D$) decreases as the dimension $N$ increases. This empirical result confirms the "vanishing marginal cost" property, demonstrating that LCC becomes more efficient as the problem size scales.

Conclusion and Future Work

Linear Computation Coding offers a significant leap in inference efficiency for fixed-weight matrices. While the current implementation is designed for inference (where weights are static), the authors acknowledge that the $B \times W$ decomposition is computationally expensive to re-calculate if weights change frequently. Future work may address memory access bottlenecks and explore non-linear extensions, potentially "coding" entire layers of a neural network at once to further push the boundaries of edge device performance.

Summary updated

Abstract

We introduce the new concept of computation coding. Similar to how rate-distortion theory is concerned with the lossy compression of data, computation coding deals with the lossy computation of functions. Particularizing to linear functions, we present an algorithm to reduce the computational cost of multiplying an arbitrary given matrix with an unknown column vector. The algorithm decomposes the given matrix into the product of codebook wiring matrices whose entries are either zero or signed integer powers of two. For a typical implementation of deep neural networks, the proposed algorithm reduces the number of required addition units several times. To achieve the accuracy of 16-bit signed integer arithmetic for 4k-vectors, no multipliers and only 1.5 adders per matrix entry are needed.
BibTeX
@inproceedings{muller2021linear,
  author = {Ralf R. Müller and Bernhard Gäde and Ali Bereyhi},
  title = {{Linear Computation Coding}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  doi = {10.1109/icassp39728.2021.9414317},
}
Figure