Efficient LLM Inference

Matrix-vector multiplication is the central computational bottleneck in inference for binary and ternary neural networks, including low-bit large language models. Although quantization reduces model size, the resulting inference pipelines often remain limited by memory movement and inefficient execution, preventing the full benefit of low-bit representations from being realized in practice.

This paper introduces Redundant Segment Reduction (RSR) and RSR++, the first algorithmic framework for accelerating low-bit matrix-vector multiplication without sacrificing exactness. Instead of trading accuracy for efficiency, the method preprocesses fixed weight matrices after training and builds compact index structures that reduce redundant computation during inference.

The result is a logarithmic-factor improvement in both time and effective memory complexity. For an n × n weight matrix, the method achieves O(n² / log n) time complexity, improving on standard multiplication while preserving exact computation.

Beyond the theoretical guarantees, the method delivers strong practical gains. Experiments show up to 30× faster matrix multiplication, up to 6× lower memory usage, up to 6× faster LLM inference on CPU without system-level optimization, and up to 2.5× faster LLM inference on GPU. The design also exposes substantial parallelism, since computations across column blocks are independent and can be executed concurrently.

More broadly, this work shows that efficient on-device inference can be advanced not only through model compression, but also through better exact algorithms for the core operations that dominate runtime. In that sense, it provides an algorithmic foundation for making capable neural models more practical, affordable, and accessible on commodity hardware.

Citation: Mohsen Dehghankar, Mahdi Erfanian, and Abolfazl Asudeh. 2025. An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks. In Proceedings of the 42nd International Conference on Machine Learning, Vol. 267, pp. 12969-12986.

Paper Page PDF

Matrix-vector multiplication is a core operation in neural networks, vector databases, and large language models, especially at inference time. As low-bit quantization becomes increasingly important for efficient deployment, binary and ternary weight matrices offer strong opportunities for acceleration, but practical gains depend on whether the underlying multiplication can be executed efficiently at the kernel level.

This paper presents RSR-core, a high-performance engine that brings the algorithmic ideas of Redundant Segment Reduction into optimized low-level kernels for both CPU and CUDA environments. While prior implementations of RSR operated mainly at the application level, RSR-core closes the gap between theory and practice by enabling efficient integration into real inference systems.

The engine supports matrix-vector multiplication for binary and ternary weight matrices with general vectors, and is designed for production use. It also includes Hugging Face integration for preprocessing low-bit models and running accelerated inference within existing workflows.

Experimentally, RSR-core delivers substantial performance improvements over baseline Hugging Face PyTorch multiplication. The results show up to 62× speedup on CPU and up to 1.9× faster token generation on CUDA for popular ternary LLMs, demonstrating that low-bit acceleration can translate into meaningful end-to-end gains when paired with a systems-oriented implementation.

More broadly, this work advances the project’s goal of making efficient on-device inference practical by turning a theoretically grounded algorithm into a deployable engine. In doing so, it strengthens the systems foundation for low-bit LLM inference on both commodity CPUs and modern GPUs.

Citation: Mohsen Dehghankar and Abolfazl Asudeh. 2026. RSR-core: A High-Performance Engine for Low-Bit Matrix-Vector Multiplication. CoRR abs/2603.27462.

Paper

Matrix multiplication is the main computational bottleneck in deep neural networks, creating a fundamental challenge for training and personalization on low-resource machines. As demand grows for running capable models, including LLM-based systems, on commodity CPUs, it becomes increasingly important to understand whether approximation techniques can meaningfully reduce this cost without undermining learning quality.

This paper studies sampling-based approaches for accelerating multilayer perceptron training by approximating matrix multiplication. We identify two main families of methods in the literature: those that activate only a sampled subset of hidden-layer nodes at each iteration, and those that sample nodes from the previous layer to approximate the current layer’s activations. In both cases, the matrix products are computed using only the selected samples.

Through theoretical analysis and comprehensive experiments, the paper shows that these techniques face important scalability limitations. The central issue is that even small approximation errors can propagate across layers, leading to an exponential growth in estimation error as network depth increases.

While the work does not yet resolve this limitation, it provides an important negative result and clarifies the boundaries of currently available sampling-based methods. This makes the paper valuable not only as an evaluation of prior ideas, but also as a foundation for future research on more robust approaches to efficient neural network training.

More broadly, the paper complements the project’s focus on efficient inference by examining a related algorithmic question at training time: when approximation can help, and when it breaks down. In doing so, it helps sharpen the research agenda for efficient neural computation on resource-constrained devices.

Citation: Sana Ebrahimi, Rishi Advani, and Abolfazl Asudeh. 2025. Evaluating the Feasibility of Sampling-Based Techniques for Training Multilayer Perceptrons. In EDBT 2025.

Paper Slides