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$.
- 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.
- 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$).
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.
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