Research map / Architectures and efficiency / RNNs and normalization
An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
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.
Proposes RSR and RSR++, preprocessing-based algorithms that replace vector-ternary/binary matrix multiplication with block-wise permutation and segmented sums, achieving O(n^2/log n) inference time and up to 29x matmul speedup and 5.24x LLM CPU speedup.
Problem
Inference of DNNs and LLMs with binary and ternary weight matrices is bottlenecked by vector-matrix multiplication, which costs quadratic time and memory on standard hardware.
Approach
Since weights are fixed after training, preprocess each binary column block into row-permutation and segmentation indices so that inference reuses partial sums over identical row patterns, reducing time to O(n^2/log n) and storage by a logarithmic factor; ternary matrices are split into two binary matrices.
Key results
- RSR++ achieves up to 29x inference-time speedup over the standard vector-matrix multiplication in native C++ for n = 2^16.
- Storage reduced to under 17% of the original matrix size (5.99x) for n = 2^16 with the NumPy implementation.
- 1.58-bit LLM CPU inference improves by up to 5.24x; GPU inference on Llama3-8B-1.58bit drops from 392 to 225 microseconds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use RSR instead of Standard for GPU inference | 1.58-bit Llama3-8B · GPU LLM inference | inference time (μs): 392 $\pm$ 20 -> 225 $\pm$ 29 | Helped |
| use RSR instead of Standard for GPU inference | 1.58-bit Falcon3-3B · GPU LLM inference | inference time (μs): 560 $\pm$ 24 -> 206 $\pm$ 21 | Helped |
| use RSR instead of Standard for GPU inference | 1.58-bit Falcon3-10B · GPU LLM inference | inference time (μs): 364 $\pm$ 82 -> 210 $\pm$ 24 | Helped |
| use RSR or RSR++ instead of Standard | binary vector-matrix multiplication · Native C++ | speedup over Standard: 29x | Helped |
| use RSR instead of NumPy matrix multiplication | binary vector-matrix multiplication · NumPy | speedup over NumPy: 24x | Helped |
| store permutations and segmentation lists instead of the weight matrix | RSR · matrix storage, n = 2^{16} | memory reduction: 5.99x | Helped |
| replace fully connected layer matrix multiplications with RSR | 1.58-bit Llama3 and Falcon3 · LLM inference on CPU | speedup over Standard: 5.24x | Helped |
| replace fully connected layer matrix multiplications with RSR | 1.58-bit Llama3 and Falcon3 · LLM inference on GPU | speedup over Standard: 2.5x | Helped |
| replace RSR's standard block-product step with the structured RSR++ computation (ablation) | RSR · native C++ vector-matrix multiplication | inference-time improvement: 25\% | Helped |
Surprising findings
- Speedup in full LLM inference is reduced relative to isolated matmul because the application-level implementation bypasses PyTorch low-level optimizations.
- Method yields no benefit for small matrices (below roughly 2^10), where constants and overhead dominate.
Limitations
- Application-level implementation does not use hardware-specific kernels, limiting speedups on real LLMs.
- Overheads dominate for small matrices below about 2^10.
- Evaluated on only a single-token generation setup and a single hardware configuration.
Experimental setup
Datasets: ShortQuestions (synthetic, GPT-4 generated) SimpleQuestions TREC QA
Benchmarks: SimpleQuestions TREC QA ShortQuestions
Metrics: inference time memory usage speedup
Baselines: Standard vector-matrix multiplication NumPy np.dot PyTorch BitLinear baseline
Builds on: Four Russians algorithm
Closest papers by meaning
- Search for Efficient Large Language Models (NeurIPS 2024 · similarity 0.87)
- LUT-GEMM: Quantized Matrix Multiplication based on LUTs for Efficient Inference in Large-Scale Generative Language Models (ICLR 2024 · similarity 0.87)
- HADAMRNN: BINARY AND SPARSE TERNARY ORTHOGONAL RNNS (ICLR 2025 · similarity 0.86)
- ShiftAddLLM: Accelerating Pretrained LLMs via Post-Training Multiplication-Less Reparameterization (NeurIPS 2024 · similarity 0.86)
- SS1: Accelerating Inference with Fast and Expressive Sketch Structured Transform (NeurIPS 2024 · similarity 0.86)
- QBB: Quantization with Binary Bases for LLMs (NeurIPS 2024 · similarity 0.86)
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.