Research map / Large language models / Agents, code and math
LibAMM: Empirical Insights into Approximate Computing for Accelerating Matrix Multiplication
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Empirical benchmark of twelve approximate matrix multiplication (AMM) algorithms plus two exact MM baselines across real-world matrices, memory-stall profiling, dataset attributes, and four downstream tasks, released as the LibAMM toolkit.
Problem
Existing AMM literature gives contradictory guidance on which approximation strategy to use, relies on synthetic data, and uses inconsistent implementations and baselines, so practical AMM selection is unclear.
Approach
A unified static-compiled C++ (LibTorch) implementation of twelve AMM algorithms benchmarked under a common protocol on real MatrixMarket matrices, with micro-architectural stall analysis and downstream-task evaluation, plus an open-source toolkit.
Key results
- CRS reduces latency by 56.3% vs LTMM on ECO and by 99.9% on BUS, with pruning-based methods outperforming extraction-based ones on large data.
- Memory stalls dominate AMM and MM cycles on large inputs, e.g., FASTJLT spends nearly all cycles in memory stalls on BUS.
- On GPU, LTMM gains up to 95% latency reduction while SMP-PCA only gains 18%, with CPU-GPU data transfer often ~50% or more of time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CRS instead of LTMM | Matrix multiplication · ECO | processing latency: 0.10 -> 0.10 | No clear effect |
| Use CRS instead of LTMM | Matrix multiplication · BUS | processing latency: 60.60 -> 1.88 | Helped |
| Use CRS instead of LTMM | Matrix multiplication · BUS | AMM error: 0.0000 -> 1.0000 | Hurt |
| Use INT8 instead of LTMM | Matrix multiplication · ECO | processing latency: 0.10 -> 0.01 | Helped |
| Use SMP-PCA instead of LTMM | Matrix multiplication · BUS | processing latency: 60.60 -> 6.97 | Helped |
| Use CRS instead of LTMM | Unitary Transformation · UT | processing latency: 213.36 -> 10.93 | Helped |
| Use COOFD instead of LTMM | Machine Learning Inference · MLI | Approximation Impact Factor: 0 -> 0.6799 | Hurt |
| Enable GPU mode | CRS · ECO | processing latency: 0.13 -> 3.29 | Hurt |
| Enable GPU mode | SMP-PCA · BUS | processing latency: 4.5 -> 3.69 | Helped |
| Increase tuning parameter ω (ablation) | Most AMM algorithms · Synthetic 2500 × 2500 matrices | AMM error | Helped |
| Increase tuning parameter ω (ablation) | Most AMM algorithms · Synthetic 2500 × 2500 matrices | processing latency | Hurt |
| Increase numeric-value skewness (ablation) | AMM algorithms · Synthetic matrices | AMM error | Hurt |
Surprising findings
- Contrary to common belief, pruning-based and hybrid AMM are more practically useful than extraction-based AMM.
- AMM accuracy degrades sharply under high numeric skew (Zipf factor above 1.6) for most algorithms, while biased non-zero regions matter less except for WEIGTHEDCR.
Limitations
- Only in-memory single-threaded evaluation on CPU; out-of-memory and distributed settings left for future work.
- Excludes algorithm-specific optimizations (e.g., MADDNESS hash, Bernoulli CRS) to keep comparison fair, which may understate some methods.
- Does not evaluate transformer LLMs; incorporating most AMM methods into such models is left to future research.
Experimental setup
Datasets: MatrixMarket ECO MatrixMarket DWAVE MatrixMarket AST MatrixMarket UTM MatrixMarket RDB MatrixMarket ZENIOS MatrixMarket QCD MatrixMarket BUS SIFT10K MNIST CIFAR100 synthetic torch::rand and Zipf matrices
Benchmarks: MatrixMarket matrices SIFT10K PCA MNIST MLP training CIFAR100 inference quantum unitary transformation
Metrics: processing latency Frobenius AMM error application error impact factor processor stall cycle proportion
Baselines: NLMM LTMM INT8 CRS CS COOFD BLOCKLRA FASTJLT VQ PQ RIP SMP-PCA
Builds on: CRS count sketch product quantization SMP-PCA MADDNESS
Closest papers by meaning
- QiMeng-GEMM: Automatically Generating High-Performance Matrix Multiplication Code by Exploiting Large Language Models (AAAI 2025 · similarity 0.89)
- ShiftAddLLM: Accelerating Pretrained LLMs via Post-Training Multiplication-Less Reparameterization (NeurIPS 2024 · similarity 0.86)
- CodeGEMM: A Codebook-Centric Approach to Efficient GEMM in Quantized LLMs (NeurIPS 2025 · similarity 0.86)
- IM-Unpack: Training and Inference with Arbitrarily Low Precision Integers (ICML 2024 · similarity 0.86)
- LUT-GEMM: Quantized Matrix Multiplication based on LUTs for Efficient Inference in Large-Scale Generative Language Models (ICLR 2024 · similarity 0.84)
- Learning from Students: Applying t-Distributions to Explore Accurate and Efficient Formats for LLMs (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.