PaperlayerView exact revision on arXiv

Source-linked AI summary

SSR: Sparse Segment Reduction for Ternary GEMM Acceleration

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

arXiv:2610.08403v1cs.LG

TL;DR

Ternary GEMM methods often overlook weight sparsity, while conventional sparse formats do not exploit ternary structure. SSR combines sparsity-aware preprocessing and compact computation trees; it reports speedups over RSR++ on ternary GEMM and Llama-3 1B inference.

  • Problem

    Ternary weights provide compression and often high sparsity, but existing ternary methods do not fully exploit sparsity and conventional sparse formats neglect ternary structure.

    Source: §I · p. 1

  • Method

    SSR uses a compact ternary format and preprocessing that excludes zero-pattern elements to build computation trees that scale with sparsity.

    Source: §I · pp. 1–2, §V · p. 6

  • Results

    SSR achieves 2.1–11.3× speedup over RSR++ on ternary GEMM with 45–95% sparsity, plus 3.5–6.3× end-to-end speedup and 4.9% memory saving on Llama-3 1B inference.

    Source: §I · p. 2

  • Takeaways & Limitations

    SSR is theoretically asymptotically faster than RSR++ above 50% sparsity and shows practical performance gains across low and high sparsity levels.

    Source: §I · p. 2

    The work lacks GPU implementation and evaluation on more LLM architectures.

    Source: §V · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

Ternary weights offer compression and sparsity, but existing approaches do not fully exploit ternary structure and sparsity together. SSR targets efficient ternary GEMM for ternary LLMs and general TWNs, with reported gains from GEMM through model inference.

I. INTRODUCTION

  • Ternary weights {−1, 0, +1} introduce sparsity, and their GEMM replaces multiplication with addition and subtraction; compared with FP8, TWNs provide 4× compression.Ternary LLMs use TWNs with dense activations.Source: §I · p. 1

A. Target Problem

  • Ternary LLMs and TWNs frequently exceed 50% sparsity, with 90–95% described as achievable without notable accuracy loss; zero weights contribute nothing to matrix multiplication.The target computation is the product of dense activations X and ternary weights W.Source: §I · p. 1, A. Target Problem · p. 2

I. INTRODUCTION

  • Conventional sparse formats and libraries do not exploit ternary structure, while BitNet, RSR, and RSR++ do not fully use weight sparsity to reduce computation complexity.The paper reports PyTorch Sparse GEMM based on CSC slower than PyTorch Dense GEMM on CPUs at 90% or lower sparsity.Source: §I · p. 1
  • SSR targets ternary LLMs and general TWNs, using preprocessing to exclude zero-pattern elements and build computation trees that scale with sparsity.Its theoretical performance is asymptotically superior to RSR++ above 50% sparsity, with practical gains across low and high sparsity levels.Source: §I · pp. 1–2
  • SSR achieves 2.1–11.3× speedup over RSR++ on ternary GEMM with 45–95% sparsity, and 3.5–6.3× end-to-end speedup with 4.9% memory saving on Llama-3 1B inference.The implementation uses unrolling, AVX2 SIMD, and CPU multithreading.Source: §I · p. 2

B. Quantized Neural Networks

Prior quantized-network work spans hardware and software optimizations, but ternary GEMM methods such as RSR++ overlook zero weights. SSR uses sparsity-aware preprocessing and block-wise processing to form compact computation structures.

B. Quantized Neural Networks

  • Quantized-network optimizations include specialized low-bit accelerators, configurable FPGAs, in-memory computing, and platform-specific SIMD, GPU, and Tensor Core approaches.The cited work also covers ternary training methods and hardware-friendly implementations.Source: B. Quantized Neural Networks · p. 2

C. Ternary LLM Inference

  • RSR++ achieves logarithmic theoretical complexity improvement but treats zeros as nonzero weights, transfers unnecessary data, performs output-irrelevant computations, and incurs non-linear memory access.The related-work discussion also identifies T-MAC's lookup-table approach and BitNet b1.58's reported speedup and memory reduction.Source: C. Ternary LLM Inference · p. 2

III. METHOD

  • SSR constructs block-wise indices that exclude zero-pattern elements during preprocessing, enabling compact computation trees and direct inference access to nonzero elements.Both preprocessing and inference stages are illustrated in Fig. 1.Source: §III · p. 2

A. Pre-processing

  • SSR decomposes ternary W into binary matrices W1 and W2, where W = W1 − W2, then preprocesses each matrix.Source: A. Pre-processing · p. 2

1) Column Blocking:

  • Column blocking partitions a binary matrix into consecutive blocks of L columns, with a possibly shorter final block.For the Fig. 1 example with L = 3, W2 is partitioned into W2,1 and W2,2.Source: 1) Column Blocking · p. 2

2) Permutation:

Each column block is permuted so its binary row patterns are ordered by their integer keys, then the prefix for all-zero rows is removed to form a reduced permutation sequence.

2) Permutation:

  • Rows in each column block are keyed by concatenating their binary entries and sorted in ascending key order by the permutation sequence.For W2,1, the patterns 000, 001, and 101 yield row permutation {2, 1, 0}.Source: 2) Permutation · p. 2
  • Fig. 1 shows reduced permutation sequence lengths of 2 for W2,1 and 1 for W2,2, matching their counts of nonzero patterns.Source: Figure 1 · p. 3
  • The reduced permutation sequence removes the prefix of indices corresponding to all-zero rows.In Fig. 1, removing the all-zero row from W2,1 shortens its permutation sequence.Source: 2) Permutation · p. 3

3) Segmentation:

Segmentation uses boundaries between distinct sorted binary keys to represent grouped patterns compactly. Its cumulative counts encode occurrences, while preprocessing produces reusable structures under a machine-selected block size.

3) Segmentation:

  • Boundary indices mark transitions between distinct binary keys in sorted column blocks, enabling efficient aggregation of grouped patterns.Source: 3) Segmentation · p. 3
  • A segment stores cumulative pattern counts, whose consecutive differences give the number of occurrences of each nonzero binary pattern.For W2,1, s = [0, 0, 0, 0, 1, 2, 2, 2] represents one occurrence each of 100 and 101, with no other nonzero patterns.Source: 3) Segmentation · p. 3
  • Preprocessing combines three steps for fixed ternary weights and block size L, and inference repeatedly reuses the resulting structures.Source: 3) Segmentation · p. 3
  • L is selected empirically per machine; optimal values are small, below log2 N for the theoretical bound, decrease with sparsity, and increase with matrix size.Source: 3) Segmentation · p. 3

B. Inference

Inference computes the product row by row, applying each input row to preprocessed weight blocks. Each row-wise multiplication uses segmented sums followed by tree computation.

B. Inference

  • The matrix product is computed as row-wise vector–matrix multiplications of input rows with the weight matrix.The input matrix X has M rows, each denoted x_j.Source: B. Inference · p. 3
  • Each row is multiplied by the preprocessed weight blocks W_i^[L], for i from 1 to ⌈N/L⌉.Source: B. Inference · p. 3
  • Each row-wise multiplication has two steps: segmented sum and tree computation.Source: B. Inference · p. 3

1) Segmented Sum:

Segmented sums aggregate input contributions sharing a binary pattern in a weight block. Tree computation recursively reduces those sums and concatenates even-indexed sums in reverse level order.

1) Segmented Sum:

  • Each entry of the segmented sum aggregates input-row contributions whose positions share a binary pattern in a weight block.The segmented sum uses the reduced permutation and segmentation sequence associated with the block.Source: 1) Segmented Sum · p. 4

2) Tree Computation:

  • Tree computation recursively reduces contributions according to the binary patterns of their positions.Source: 2) Tree Computation · p. 4
  • The tree output concatenates the even-indexed sums from the vectors in reverse order.Source: 2) Tree Computation · p. 4
  • At each level, the tree forms the next vector by taking every second element from positions 2 through the penultimate position, roughly halving its length.The initial vector is the segmented sum vector, of length 2^L − 1.Source: 2) Tree Computation · p. 4

C. Theoretical Computation Complexity Analysis

SSR exploits zero-valued ternary patterns to reduce inference operations and memory accesses. Its asymptotic advantage over RSR++ applies above 50% sparsity, while preprocessing retains the same stated complexity.

C. Theoretical Computation Complexity Analysis

  • For sparsity p > 0.5, SSR has asymptotically better operational complexity than RSR++ and requires fewer additions and memory accesses.SSR’s preprocessing complexity remains O(K · N), like RSR++.Source: C. Theoretical Computation Complexity… · p. 4
  • For p in (0.5, 1], SSR has strictly better asymptotic performance than RSR++, but its larger constant factor means the reduced exponent dominates only for sufficiently large K.At p = 0.5, the methods coincide.Source: C. Theoretical Computation Complexity… · p. 4
  • Excluding the all-zero bit pattern removes one segmented-sum entry, saving one addition per row and column block at each tree level.This also shortens the permutation array and segmentation list, reducing processed indices and corresponding memory accesses.Source: C. Theoretical Computation Complexity… · p. 4
  • SSR is hardware-independent and can be implemented on CPUs and GPUs, but the reported benchmarks are CPU-only because of engineering effort.Source: C. Theoretical Computation Complexity… · p. 4

IV. EVALUATION

The evaluation benchmarks an optimized C++ SSR implementation at GEMM, layer, and model levels. Experiments use a Windows laptop and report average times across ten runs.

IV. EVALUATION

  • The C++ implementation uses loop unrolling, blocking, AVX2 SIMD intrinsics, and multithreading.Source: §IV · p. 4
  • Benchmarks cover ternary-weight GEMM, Llama MLP blocks, and Llama models at GEMM, layer, and model levels.Source: §IV · p. 4
  • Experiments ran on a Windows 11 Home 23H2 laptop with an AMD Ryzen 7 8845HS@3.8GHz, using Microsoft Visual Studio 2022 v143; reported times average 10 runs.Source: §IV · p. 4

A. Ternary Matrix Multiplication Evaluation

The evaluation compares SSR with RSR/RSR++ and sparse-library baselines in single- and multi-threaded ternary GEMM. SSR’s speedup over RSR++ varies with sparsity and matrix size, while fixed L values constrain the reported performance curves.

A. Ternary Matrix Multiplication Evaluation

  • 4.9–20.2× speedup over RSR++ is reported for AVX2-optimized SSR at 45–95% sparsity in the single-threaded evaluation.The evaluation also reports that SSR Naive is 2.9%–189.0% faster than RSR++.Source: Figure 2 · p. 5, A. Ternary Matrix Multiplication… · p. 5
  • RSR and RSR++ execution times are nearly unchanged across sparsity levels, while SSR and Eigen Sparse GEMM times decrease as sparsity increases.These trends are reported for the single-threaded matrix evaluation.Source: A. Ternary Matrix Multiplication… · p. 5
  • The INT8 comparisons are excluded because PyTorch and Eigen INT8 implementations ran slower than their FP32 versions; Eigen Sparse GEMM INT8 is shown only for reference.The experiments were conducted in both float and INT8 precision.Source: A. Ternary Matrix Multiplication… · p. 5
  • 2.6–11.3× speedup over RSR++ is reported for the smaller multi-threaded matrix as sparsity varies.Fig. 3 evaluates X: 256×1024 and W: 1024×4096 with L=4.Source: Figure 3 · p. 5, A. Ternary Matrix Multiplication… · p. 5
  • 2.1–8.4× speedup over RSR++ is reported for 45–95% sparsity with the larger multi-threaded matrix.Fig. 4 evaluates X: 512×2048 and W: 2048×8192 with L=6.Source: Figure 4 · p. 5, A. Ternary Matrix Multiplication… · p. 5
  • SSR beats some sparse-library baselines at lower sparsity but can become slower at higher sparsity, with the reported trade-off varying by baseline and matrix size.For Fig. 3, SSR is up to 35% slower than PyTorch Sparse CSC at very high sparsity; Fig. 4 reports that it becomes slower than PyTorch Sparse CSC and Eigen Sparse INT8 at higher sparsity.Source: A. Ternary Matrix Multiplication… · p. 5
  • The Fig. 3 and Fig. 4 curves use a fixed L, although the optimal L varies with matrix size and sparsity; profiling-based selection may overcome this limitation.The authors state that dynamically selecting L based on performance profiling can overcome the fixed-L limitation.Source: A. Ternary Matrix Multiplication… · p. 5

B. Layer-Level Evaluation

SSR is faster than RSR++ on both evaluated Llama MLP block sizes, while its compact format also reduces MLP-block memory usage. The evaluation covers small and Llama-3 1B blocks and reports stored-format and inference memory separately.

B. Layer-Level Evaluation

  • The layer-level evaluation uses MLP blocks with up, gate, and down projections and omits GeLU or SiLU to isolate ternary GEMM performance.The evaluated block dimensions scale with the up projection.Source: B. Layer-Level Evaluation · p. 5
  • 2.6–7.5× speedup over RSR++ on the small Llama MLP block.The block contains one up, one gate, and one down projection; the reported comparison is for execution time.Source: B. Layer-Level Evaluation · p. 6, Figure 5 · p. 6
  • 1.8–7.5× speedup over RSR++ on the Llama-3 1B MLP block.This block is about 8× as large as the small MLP block.Source: B. Layer-Level Evaluation · p. 6, Figure 6 · p. 6
  • SSR reduces MLP-block memory by 5.4–15.1% after initialization and 9.6–17.8% during inference versus RSR++.The first measure is the stored ternarized-weight format; the second is dynamic memory during execution.Source: B. Layer-Level Evaluation · p. 6, Table II · p. 6

C. End-to-End Evaluation

For 512-token queries, SSR reduces end-to-end latency relative to RSR++, with a smaller sparsity-related speedup than the theoretical figure because attention layers are not ternarized. The conclusion also reports reduced model memory, attributes the gains to sparse computation and a compact format, and identifies GPU implementation and broader architecture coverage as limitations.

C. End-to-End Evaluation

  • 3.45–6.34× speedup over RSR++ for 512-token queries; the 90%-versus-50% sparsity speedup is 1.84×, below the 5× theoretical figure because attention layers are not ternarized.The evaluation uses sequence length 512; the authors note possible further improvements from ternarizing Multi-Head Attention and dynamically selecting L.Source: C. End-to-End Evaluation · p. 6
  • At sequence length 512, SSR reduces full-model memory from up to 3113 MB with RSR++ to 2960 MB, a 4.9% reduction.The authors attribute the smaller reduction than for MLP blocks to the addition of attention functions.Source: C. End-to-End Evaluation · p. 6, §V · p. 7

V. CONCLUSION

  • The conclusion attributes SSR’s gains to a compact format and a sparse GEMM algorithm with a further log-scale improvement in computation complexity.The format removes redundant all-zero indices; the conclusion reports up to 15% less memory than RSR++ for the format.Source: §V · p. 6
  • The work lacks GPU implementation and evaluation on more LLM architectures.GPU implementation and inference demonstration on open-weight ternary LLMs are identified as future work.Source: §V · p. 7

Related papers

Loading 2610.08403v1…