Can sparse segment reduction accelerate ternary GEMM for large language model inference?

Zero weights are the resource SSR exploits

Ternary weight networks constrain each weight to −1, 0, or +1. Compared with FP8 quantization, the paper states that this gives 4x compression and replaces multiplications in GEMM with additions and subtractions. The zero value is not just a storage convenience: a zero weight contributes nothing to the matrix product, so every multiply-add attached to it is wasted work. The paper reports that ternary LLMs and general ternary weight networks frequently exceed 50% sparsity, and that 90–95% sparsity is achievable in practice without notable accuracy loss.

The paper's complaint about prior work follows from that observation. BitNet, redundant segment reduction (RSR), and its improved version RSR++ are built for ternary weights but, in the authors' account, do not exploit the sparsity structure. Conventional sparse formats such as CSR, JDS, and COO do the reverse: they handle sparsity but ignore ternary characteristics. SSR is positioned as the method that uses both properties at once.

SSR groups equal bit patterns before summing

SSR first splits a ternary weight matrix W into two binary matrices, W1 and W2, with W = W1 − W2: W1 marks the +1 entries and W2 marks the −1 entries. Each binary matrix is then cut into consecutive column blocks of L columns. Within a block, rows are reordered so that their L-bit patterns appear in ascending integer order. Rows whose pattern is all zeros are dropped from that ordering, producing a reduced permutation sequence, and a segmentation list records cumulative counts of each remaining pattern.

At inference, the input row vector is summed according to those segments, so that all input elements sharing the same bit pattern in a block are aggregated once. A recursive tree computation then combines these partial sums according to the binary patterns. Because the all-zero pattern is excluded, the segmented sum array is one entry shorter, which the paper says saves at least M·N/L additions per tree level and also shortens the permutation array and segmentation list. Preprocessing runs once for fixed weights, and inference reuses the resulting structures.

The asymptotic advantage begins above 50% sparsity

The paper derives operation counts for three methods. BitNet.cpp is listed at 2MNK/3 operations, RSR++ at 2MNK/log2(K) in the lower-bound form given, and SSR at a bound that includes the factor log2(1/(1−p)) with sparsity p. The key step is that excluding all-zero patterns reduces the additions per row and block from K to K − p^L·K under an independence assumption. Choosing L = ⌊log2 K / log2(1/(1−p))⌋ yields the stated upper bound.

For p > 0.5, the exponent on K becomes strictly smaller than RSR++'s, and the two coincide at p = 0.5. SSR carries a larger constant factor, so the paper gives an explicit crossover: for sparsity in (0.5, 1], SSR is more efficient when K ≥ (2c)^(c/(c−1)) with c = log2(1/(1−p)). This is a statement about asymptotics and matrix dimension, not a guarantee for every concrete shape.

Measured speedups appear at every tested sparsity

The abstract reports 2.1–11.3x speedup over RSR++ on ternary GEMM across 45–95% sparsity. That range is wider than the theoretical threshold: the paper notes that practical evaluations show improvements at all sparsity levels, while the asymptotic advantage is claimed only above 50%. The two statements should not be merged — one is a measured range on the authors' implementation, the other a complexity bound with a crossover condition.

The discussion adds a comparison against a general sparse library: SSR is reported up to 75.8% faster than PyTorch Sparse CSC. The paper also motivates the work with an observation from its own experiments that PyTorch Sparse GEMM based on CSC is slower than PyTorch Dense GEMM at 90% sparsity or lower on CPUs, far from the roughly 10x theoretical sparse speedup. These are CPU measurements from the authors' setup.

End-to-end gains are smaller than kernel gains

On the Llama-3 1B model, the paper reports 3.5–6.3x end-to-end speedup over RSR++ together with 4.9% total memory reduction. The end-to-end range is narrower than the 2.1–11.3x kernel-level range, which is expected when only part of inference time is spent in the ternary GEMM kernel; the paper does not decompose that gap, so the difference should be read as a scope difference between the two measurements rather than as a contradiction.

Memory is reported at two levels as well. The discussion states that SSR's compact data format reduces memory size by up to 15% versus RSR++, while the end-to-end Llama-3 1B result is 4.9% of total memory saving. The 15% figure describes the format; the 4.9% figure describes whole-model inference. They answer different questions and are not interchangeable.

The implementation boundary is CPU only

The paper states that the SSR algorithm, like BitNet and RSR++, is independent of the underlying hardware architecture and could run on CPUs and GPUs. However, benchmarking is provided on CPU only, because the authors cite the high engineering effort required for a GPU implementation. The reported speedups therefore describe a C++ implementation optimized with loop unrolling, AVX2 SIMD, and multi-threading, not a GPU kernel.

The stated limitations are the lack of a GPU implementation and of demonstrations on more LLM architectures. The authors expect further improvements from GPU-specific optimizations given the strong GPU performance of BitNet and RSR++, but that expectation is not measured in this paper. The block size L is also chosen empirically per machine, with optimal values reported as small, strictly below log2 N, decreasing with higher sparsity and increasing with matrix size.

Sparsity level and matrix size decide the payoff

The paper's own decision structure is clear. Below or at 50% sparsity, SSR's asymptotic exponent matches RSR++ at p = 0.5 and the larger constant factor works against it; above 50%, the reduced exponent dominates once K is large enough to satisfy the stated crossover. The measured 45–95% range shows gains even at the low end on the authors' CPU implementation, so the practical threshold is not simply the theoretical one.

For a reader deciding whether this matters, the paper's most useful distinction is between the kernel-level speedup over RSR++ and the end-to-end speedup on Llama-3 1B, and between the format-level memory reduction and the whole-model memory saving. The strongest claim the evidence supports is that exploiting zero patterns in ternary GEMM pays off in the authors' CPU setting across the tested sparsity range; whether it transfers to GPUs or other LLM architectures is explicitly left open.

Sources used in this answer