cs.LGOct 6, 2026

SSR: Sparse Segment Reduction for Ternary GEMM Acceleration

Authors: Adeline Pittet, Shien Zhu, Valérie Verdan, Gustavo Alonso

Organizations: Systems Group, ETH Zurich, Switzerland

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

Fig. 1 : Pre-processing of the binary matrix W2W_{2} and inference with the row vector x⃗j\vec{x}_{j} of the input matrix XX for L=3L=3 . The length of the reduced permutation sequence equals the number of nonzero patterns in the column blocks: 22 for W2,1W_{2,1} and 11 for W2,2W_{2,2} . Row indices of all-zero rows are deleted and shown in red, while the remaining row indices are shown in blue.
BitNet.cppRSR++SSR
2MNK3\displaystyle\frac{2MNK}{3}2MNKlog⁡2K\displaystyle\frac{2MNK}{\log_{2}K}log⁡2 ⁣(11−p)⋅4MN⋅K−1/log⁡2(1−p)log⁡2K\displaystyle\log_{2}\!\left(\frac{1}{1-p}\right)\cdot\frac{4MN\cdot K^{-1/\log_{2}(1-p)}}{\log_{2}K}
TABLE I : Operation counts of SSR and related works.
Fig. 2 : Execution time of single-thread ternary GEMM (X: 512 ×\times 1024, W: 1024 ×\times 4096, L=6).
Fig. 3 : Execution time of multi-thread ternary GEMM (X: 256 ×\times 1024, W: 1024 ×\times 4096, L=4).
Fig. 4 : Execution time of multi-thread ternary GEMM (X: 512 ×\times 2048, W: 2048 ×\times 8192, L=6).
Fig. 5 : Execution time of one small Llama MLP block (X: 256 ×\times 1024, up_proj: 1024 ×\times 4096, L=6).
 After InitializationDuring Inference
RSR++129-146 MB177-259 MB
SSR122-124 MB160-213 MB
TABLE II : Memory usage of one Llama-3 1B MLP block
Fig. 6 : Execution time of one Llama-3 1B MLP block (X: 512 ×\times 2048, up_proj: 2048 ×\times 8192, L=6).
Sparsity50%70%90%
RSR++36.23 s36.30 s36.19 s
SSR10.49 s8.80 s5.71 s
TABLE III : Time-To-First-Token of one Llama-3.1 1B model (Sequence Length = 512)

Explore similar work

CardsList

  1. TWLA: Achieving Ternary Weights and Low-Bit Activations for LLMs via Post-Training Quantization

    Jun 11, 2026Zhixiong Zhao, Zukang Xu, Zhixuan Chen +3Large Language Model QuantizationPost-Training Quantization

    Houmo AI, China · 2Southeast University, Nanjing, China

  2. Breaking the 1.58-bit Barrier for Ternary LLMs

    Sep 14, 2026Evangelos Georganas, Alexander Heinecke, Pradeep DubeyLarge Language Model QuantizationModel Weights

    Intel Corporation

  3. CAT-Q: Cost-efficient and Accurate Ternary Quantization for LLMs

    Jun 25, 2026Shigeng Wang, Chao Li, Yangyuxuan Kang +2Large Language Model QuantizationQuantization-Aware Training

    1Intel Labs China