Sparse segment reduction speeds up ternary matrix operations in large language models
SSR: Sparse Segment Reduction for Ternary GEMM Acceleration
Machine Learning
Summary
Large language models need a lot of computing power, which makes them hard to run on smaller devices. The paper introduces a method called Sparse Segment Reduction (SSR) that speeds up calculations for models using ternary weights (weights limited to three values), taking advantage of the fact that many of these weights are zeros (sparse). By designing a special data format and algorithm, SSR can perform these operations faster than previous methods, especially when sparsity is high. This leads to significant speedups and memory savings during language model inference.
What this means in practice
- •For machine learning engineers: Accelerate the inference of ternary weight language models by integrating SSR’s optimized sparse ternary matrix multiplication.
- •For hardware accelerator designers: Design hardware that supports SSR’s sparse segment reduction format to improve ternary matrix multiplication performance and energy efficiency.
Authors
Adeline Pittet, Shien Zhu, Valérie Verdan, Gustavo Alonso
Abstract
Large Language Models (LLMs) require substantial computational resources, limiting their deployment on resource-constrained hardware. Ternary LLMs mitigate these demands through weight quantization via ternary values, achieving significant compression often with 50-90% sparsity. However, existing approaches have limitations: methods optimized for ternary weights, such as BitNet, redundant segment reduction (RSR), and its improved version RSR++, do not exploit sparsity structures, while conventional sparse formats neglect ternary characteristics, foregoing dual optimization opportunities. In this paper, we introduce Sparse Segment Reduction (SSR), a ternary matrix multiplication method designed to accelerate the inference of ternary LLMs and general Ternary Weight Networks (TWNs). SSR has a dedicated optimized ternary data format and an algorithm that systematically exploits sparsity patterns through computation trees that scale with the sparsity. SSR provides theoretical gains with asymptotically faster inference than RSR++ for sparsity above 50%, while practical evaluations reveal performance improvements across all sparsity levels. Evaluation results show that SSR achieves 2.1-11.3x speedup over RSR++ on ternary GEMM with 45-95% sparsity. Furthermore, SSR achieves 3.5-6.3x end-to-end speedup and 4.9% of memory saving over RSR++ on the Llama-3 1B model inference.