🤖 machine learning

DiBA: Diagonal and Binary Matrix Approximation for Neural Network Weight Compression

This paper introduces DiBA, a compact matrix factorization method that approximates dense neural network weights using diagonal and binary matrices to significantly reduce storage and computation costs, along with DiBA-Greedy and DiBARD algorithms that achieve high accuracy and efficient downstream adaptation without retraining binary components.

Original authors: Nobutaka Ono

Published 2026-05-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nobutaka Ono

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, incredibly detailed library of books (a neural network). Most of these books are written on heavy, thick paper (dense matrices) that takes up a lot of shelf space and is slow to flip through. The author of this paper, Nobutaka Ono, wants to shrink these books down so they fit in a backpack without losing the story.

Here is the simple breakdown of their solution, DiBA, and how it works.

The Problem: Heavy Books

Modern AI models are full of "dense matrices." Think of these as giant spreadsheets where every single cell has a specific, precise number. These spreadsheets are huge. They take up a lot of memory and make the AI slow to run on phones or small devices.

The Solution: DiBA (The "Diagonal and Binary" Trick)

Instead of trying to shrink every single number in the spreadsheet, DiBA breaks the big spreadsheet into two types of simpler parts:

The "Binary Mixing" (The Blueprint): Imagine a stencil or a cookie cutter made of 0s and 1s. It doesn't hold any numbers; it just decides which ingredients get mixed together. It's like a switchboard that says, "Connect this wire to that wire," or "Leave this one alone." Because it only uses 0s and 1s, it takes up almost no space (like a tiny sketch).
The "Diagonal Scaling" (The Volume Knobs): Imagine three rows of volume knobs. One row controls the input, one controls the middle, and one controls the output. These knobs are the only places where the actual "loudness" or precise values live.

The Analogy:
Think of the original heavy spreadsheet as a full-color, high-definition painting.

DiBA doesn't try to save every pixel. Instead, it saves a black-and-white stencil (the binary part) that tells you where the paint goes.
Then, it saves a list of paint colors and amounts (the diagonal part) to apply to those spots.
By mixing the stencil with the color list, you can recreate the painting very closely, but the "file size" is tiny because the stencil is just black and white dots, and the color list is just a few numbers.

How They Found the Best Mix (DiBA-Greedy)

The authors needed a way to figure out the perfect stencil and the perfect volume knobs. They created a tool called DiBA-Greedy.

The Process: It's like a game of "Hot and Cold."
1. They start with a random stencil and random knobs.
2. They adjust the knobs (the numbers) to make the picture look as close to the original as possible. This is easy math.
3. Then, they look at the stencil. They ask, "If I flip this one dot from 0 to 1, does the picture get better?" If yes, they flip it. If no, they leave it.
4. They repeat this, adjusting knobs, then flipping dots, over and over, until the picture is as good as it can get.

The "Fine-Tuning" Trick (DiBARD)

Here is the clever part. Sometimes, when you shrink a book, the story feels a little "off" when you read it in a new context (like a different language or a specific task). Usually, you'd have to rewrite the whole book to fix it.

But with DiBARD, the authors found a shortcut:

They keep the stencil (the binary part) exactly the same. It's frozen.
They only turn the volume knobs (the diagonal part) again, but this time they listen to the specific task (like answering questions or recognizing speech) to adjust the knobs.

The Metaphor:
Imagine you have a radio that was tuned to a specific station (the original AI). You shrink the radio to fit in your pocket (DiBA), but now the signal is a bit fuzzy.

Old way: You'd have to rebuild the whole radio circuit.
DiBARD way: You just twist the tuning dial (the diagonal knobs) until the music sounds clear again. You don't touch the internal wiring (the binary stencil) at all.

What the Paper Actually Proved

The authors tested this on 40 different "spreadsheets" from real AI models and two specific tasks:

Reading/Writing (DistilBERT): They replaced the word-embedding part of a language model. After just turning the "volume knobs" (DiBARD), the model's ability to predict missing words improved significantly, beating standard compression methods.
Listening (Audio Spectrogram Transformer): They replaced the parts of an AI that listens to voice commands. After the "knob turning," the AI's accuracy jumped from about 77% back up to nearly 98%, almost as good as the original, huge model.

The Catch (What the Paper Doesn't Claim)

The paper is very honest about what it hasn't done yet:

Theory vs. Reality: They calculated how much space this should save (theoretical storage), but they didn't actually build the super-fast computer chips to prove it runs faster in real life.
Local Optima: Their "Hot and Cold" game (DiBA-Greedy) finds a good solution, but not necessarily the perfect mathematical solution.
Scope: They only tested on specific parts of models, not the entire model at once, and only on a few specific tasks.

In summary: DiBA is a new way to compress AI brains by separating the "structure" (a tiny, simple binary map) from the "values" (a few adjustable knobs). It allows you to shrink the model massively and then quickly "tune" just the knobs to make it work perfectly again, without having to relearn the whole structure.

Technical Summary: DiBA (Diagonal and Binary Matrix Approximation)

Problem Statement
Dense matrices constitute a dominant storage and computational unit in modern neural networks, appearing in linear layers, token embeddings, attention projections, and $1 \times 1$ convolutions. While techniques like pruning, quantization, and low-rank decomposition have been developed to compress these weights, they face specific trade-offs. Quantization, while hardware-friendly, introduces intrinsically discrete optimization problems that are difficult to solve, often requiring complex mixed-integer formulations or straight-through estimators. Low-rank factorizations often lack the specific structural constraints needed for efficient bit-level storage and arithmetic. The paper addresses the need for a compact matrix representation that balances theoretical storage reduction, approximation accuracy, and the feasibility of downstream task adaptation without re-optimizing discrete components.

Methodology
The paper proposes DiBA (Diagonal and Binary Matrix Approximation), a structured matrix factorization that approximates a dense target matrix $A \in \mathbb{R}^{m \times n}$ as:
$\hat{A} = D_1 B_1 D_2 B_2 D_3$
where:

$D_1, D_2, D_3$ are real-valued diagonal matrices of sizes $m \times m$ , $k \times k$ , and $n \times n$ , respectively.
$B_1 \in \{0, 1\}^{m \times k}$ and $B_2 \in \{0, 1\}^{k \times n}$ are binary matrices.
$k$ is an intermediate dimension controlling the trade-off between storage and accuracy.

Theoretical Properties:

Storage: The binary factors are stored at 1 bit per entry, while diagonal factors use standard floating-point precision ( $Q$ bits). The theoretical storage ratio relative to a dense $Q$ -bit matrix is $\rho_{\text{DiBA}} = \frac{k(m+n) + Q(m+k+n)}{Qmn}$ .
Computation: Matrix-vector products are decomposed into three element-wise scaling operations (diagonal) and two binary mixing operations (selection and summation), reducing floating-point multiplications from $mn$ to $m + k + n$ .
Structure: The approximation is a superposition of $k$ scaled rank-one binary patterns, corrected by row and column diagonal scales.

Optimization: DiBA-Greedy
To fit DiBA factors to a pretrained weight matrix, the authors introduce DiBA-Greedy, an alternating solver:

Diagonal Updates: With binary factors fixed, the diagonal matrices are updated via closed-form least-squares solutions.
Binary Updates: With diagonal factors fixed, the binary matrices are updated by evaluating the exact change in squared Frobenius error for flipping a single bit. A flip is accepted only if the improvement exceeds a tolerance $\tau$ .
This approach avoids the non-convexity of simultaneous optimization by separating continuous and discrete updates, though it is a local greedy solver and does not guarantee a global optimum.

Downstream Adaptation: DiBARD
Recognizing that minimizing reconstruction error does not guarantee downstream task performance, the paper proposes DiBARD (DiBA with Retuning only Diagonal factors). In this protocol:

The binary matrices $B_1$ and $B_2$ are frozen after the initial DiBA-Greedy fitting.
Only the diagonal entries of $D_1, D_2, D_3$ are retuned on downstream training data using standard gradient-based optimization.
This transforms the adaptation phase into a small continuous optimization problem, avoiding the need for discrete search during fine-tuning.

Key Contributions

Formulation: The definition of DiBA as a diagonal-and-binary factorization for dense weight compression, including its theoretical storage accounting.
Algorithm: The development of DiBA-Greedy, combining closed-form least-squares updates with exact one-bit greedy updates.
Empirical Evaluation (Matrix Level): An evaluation on 40 dense weight matrices extracted from public pretrained models (NLP and Vision). Results show consistent Signal-to-Noise Ratio (SNR) improvements as the theoretical storage ratio increases, with embedding matrices showing particularly high SNR.
Adaptation Protocol: The introduction of DiBARD and its validation in two component-replacement studies:
- DistilBERT/WikiText: Replacing the tied embedding/output projection. DiBARD improved masked-token accuracy from 0.4447 (DiBA pre-retuning) to 0.5210, surpassing Int4-scale-RT (0.5110) and approaching the original model (0.4906) despite a lower theoretical storage ratio.
- AST/Speech Commands: Replacing 48 attention projection matrices in an Audio Spectrogram Transformer. DiBARD recovered test accuracy from 0.7684 to 0.9781 (original was 0.9837), recovering 97.4% of the performance gap induced by the initial compression.

Significance and Claims
The paper claims that DiBA offers a compact weight representation that effectively combines fixed binary mixing with lightweight diagonal retuning. The primary significance lies in demonstrating that:

Dense weights can be approximated by interleaving diagonal scaling and shared binary mixing without element-wise quantization.
Downstream performance can be recovered after aggressive compression by retuning only the diagonal factors, thereby avoiding the computational difficulty of re-optimizing discrete binary variables within a nonlinear network loss.

Limitations and Modesty
The authors explicitly note several limitations:

Theoretical Storage: Storage ratios are theoretical, assuming bit-packed binary matrices; no measured memory or bit-packed kernel speedups are provided.
Scope: Experiments 2-1 and 2-2 report compression ratios relative to the replaced components only, not the full model.
Solver: DiBA-Greedy is a local greedy solver, not a global optimizer.
Evaluation: Downstream evaluations use fixed data splits and limited seeds.
The paper does not claim measured inference speedups or end-to-end runtime reductions, focusing instead on approximation quality, theoretical storage, and the feasibility of diagonal-only recovery.