Efficient 1-bit tensor approximations

We present a spatially efficient decomposition of matrices and arbitrary-order tensors as linear combinations of tensor products of -1, 1-valued vectors. For any matrix A ∈ ℝm × n, A - Rw = Sw Cw Tw^top = sumj=1w cj · sj tj^top is a it w-width signed cut decomposition of A. Here Cw = "diag"(cw) for some cw ∈ ℝw, and Sw, Tw, and the vectors sj, tj are -1, 1-valued. To store (Sw, Tw, Cw), we may pack w · (m + n) bits, and require only w floating point numbers. As a function of w, |Rw|F exhibits exponential decay when applied to #f32 matrices with i.i.d. mathcal N (0, 1) entries. Choosing w so that (Sw, Tw, Cw) has the same memory footprint as a textitf16 or textitbf16 matrix, the relative error is comparable. Our algorithm yields efficient signed cut decompositions in 20 lines of pseudocode. It reflects a simple modification from a celebrated 1999 paper [1] of Frieze and Kannan. As a first application, we approximate the weight matrices in the open textitMistral-7B-v0.1 Large Language Model to a 50% spatial compression. Remarkably, all 226 remainder matrices have a relative error <6% and the expanded model closely matches textitMistral-7B-v0.1 on the it huggingface leaderboard [2]. Benchmark performance degrades slowly as we reduce the spatial compression from 50% to 25%. We optimize our open source textitrust implementation [3] with textitsimd instructions on textitavx2 and textitavx512 architectures. We also extend our algorithm from matrices to tensors of arbitrary order and use it to compress a picture of the first author's cat Angus.