# Matrix-Free Butterfly Compression - ID: 1771 - Canonical URL: https://synthcore.org/idea/1771/matrix-free-butterfly-compression - API JSON: https://synthcore.org/api/idea/1771.json - API Markdown: https://synthcore.org/api/idea/1771.md - Verification status: mech_ok_no_baseline - Source: [arXiv:2607.29361](https://arxiv.org/abs/2607.29361) - Category: memory - Solves: memory, speedup, accuracy - ML areas: transformer, mlp, inference-speedup, memory, distillation - Math tags: linear-algebra, probability, tensor-decomposition, approximation-theory - Ratings: usefulness 7/10; difficulty 7/10; novelty 6/10 ## Idea description Compress an existing dense neural-network weight matrix into a recursive butterfly operator using Gaussian sketches of complementary blocks. This is useful for deployment or distillation: the dense model provides an oracle for matrix-vector products, while the compressed model stores only recursive transfer bases and small cores. The generalized Nyström identity gives exact reconstruction for rank-k blocks and a principled approximation route for numerically low-rank blocks. ## Mathematical statement For a rank-at-most-k matrix A in R^{2k x 2k}, draw Gaussian test matrices Omega and Psi in R^{2k x alpha k}, where alpha>1 is an oversampling factor. Let U be the top k left singular vectors of A Omega. The paper states that, almost surely, A=U(Psi^T U)^dagger Psi^T A, where dagger is the Moore-Penrose pseudoinverse. For a general neural-network weight W, apply this identity approximately to complementary blocks W(I_{i,ell},I_{j,L-ell}) at each dyadic level, retain k singular directions, and recursively share the resulting bases through B=UXV^T with X_{s,t} in BF(L-2,k). The Gaussian sketches recover the relevant column and row subspaces with probability one in the exact rank-k setting; for real weights, the discarded singular values determine the approximation error. ## Key formulas - $$U=\operatorname{top}_k\!\operatorname{svd}(A\Omega),\qquad \Omega\sim\operatorname{Gaussian}(2k,\alpha k),$$ - $$A=U(\Psi^{\mathsf T}U)^\dagger\Psi^{\mathsf T}A\quad\text{almost surely},\qquad \Psi\sim\operatorname{Gaussian}(2k,\alpha k),$$ - $$B=UXV^{\mathsf T},\qquad X=\begin{bmatrix}X_{1,1}&X_{1,2}\\X_{2,1}&X_{2,2}\end{bmatrix},\quad X_{s,t}\in\operatorname{BF}(L-2,k).$$ ## Implementation notes Use this as an offline conversion pass for a trained dense Linear layer W, or for a black-box linear operator exposing matvec(W,v) and matvec(W^T,v). Choose L and k, construct dyadic row and column partitions, and process levels ell=L,L-2,...,2. For each required complementary block, draw Gaussian sketches with alpha*k columns: Y_block=W_block Omega_block and Z_block=W_block^T Psi_block. Compute rank-k orthonormal bases U_block=QR_k(Y_block) and V_block=QR_k(Z_block). Estimate the small core by least squares, C=(Psi^T U_block)^dagger(Psi^T W_block), or, when explicit subblocks are available, C=U_block^T W_block V_block. Fold these bases into the block-diagonal outer factors U and V and recurse on the four cores X_{s,t}; at level zero, use the generalized Nyström formula directly on each 2k-by-2k core. The exact identity applies when a block has rank at most k; for real weights, estimate quality using fresh random test vectors and explicit Frobenius error on small layers. Begin with a ViT-Tiny or 4-layer Transformer, compress MLP weights to achieve 4x fewer parameters, and compare dense inference, standard truncated SVD, and butterfly compression. Evaluate operator relative error, validation accuracy, latency, peak memory, and serialized model size. Success means lower latency and memory at the same accuracy, with random-vector operator error predicting downstream accuracy degradation. ## Verification - Status: mech_ok_no_baseline - Mechanism evidence: yes - Mechanism confirmed: yes - Practical verdict: inconclusive - Verdict: Built a readable generalized Nyström MVP with a true matrix-free matvec/rmatvec API plus an explicit blockwise compression experiment. Recovery switched from large error at k=3; exact-rank error stayed near 1e-15 across alpha=1 to 4; and perturbation error scaled linearly with noise magnitude with origin-fit R²=0.999999998. The toy block matrix achieved 1.02e-15 relative error with 2x storage reduction, but the prototype was slower than dense copying and global SVD at this tiny scale. ### Mechanism check - Verdict: Built a readable generalized Nyström MVP with a true matrix-free matvec/rmatvec API plus an explicit blockwise compression experiment. Recovery switched from large error at k=3; exact-rank error stayed near 1e-15 across alpha=1 to 4; and perturbation error scaled linearly with noise magnitude with origin-fit R²=0.999999998. The toy block matrix achieved 1.02e-15 relative error with 2x storage reduction, but the prototype was slower than dense copying and global SVD at this tiny scale. - Confidence: 9/10 - Limitations: The prototype implements matrix-free generalized Nyström and independent dyadic-style blocks, not the paper's complete recursive basis folding into BF(L-2,k) cores. It did not test a trained Transformer or MLP, downstream accuracy, GPU inference latency, serialized formats, adaptive ranks, or realistic noisy neural weights; timing at this tiny scale is not representative. ### Practical benchmark - Paired seeds: 8 - Baseline mean: 0 - Idea mean: 0 - p-value: 0.7246 - Paired wins: 5/8 - Benchmark verdict: no significant win ## Artifacts - [bench_report.json](https://synthcore.org/code/663/bench_report.json) - [matrix_free_butterfly.py](https://synthcore.org/code/663/matrix_free_butterfly.py) - [report.md](https://synthcore.org/code/663/report.md) - [report_bench_2026-08-31T212027.md](https://synthcore.org/code/663/report_bench_2026-08-31T212027.md) - [results.json](https://synthcore.org/code/663/results.json) - [run_experiment.py](https://synthcore.org/code/663/run_experiment.py) - [stage2_butterfly_bench.py](https://synthcore.org/code/663/stage2_butterfly_bench.py) - [Download all files as ZIP](https://synthcore.org/download/663) ## Disclaimer AI-generated research hypothesis, automatically tested. Not peer-reviewed.