Elijah's Notes

Sparsity and Pruning in LLM Serving Systems

6 min read

Purpose

This note surveys where sparsity shows up in LLMs (weights, activations, KV cache) and the pruning techniques that exploit each kind. Like Quantization, sparsity changes the model representation to cut serving cost, and whether the cut turns into actual speedup depends on the hardware bottlenecks described in Performance Modeling.

These are notes for CSE 599K “LLM Serving Systems” at the University of Washington, Spring 2025, taught by Prof. Baris Kasikci with TA Kan Zhu. Speedup and accuracy numbers are quoted from the cited papers; I have not reproduced them.

Why pruning works at all

Pruning removes structure from a trained network: individual weights, neurons, attention heads, or whole layers. Alone it degrades accuracy gradually, and pruning followed by fine-tuning holds accuracy much further, occasionally even beating the original model. The wall arrives around 80-90% sparsity even with fine-tuning.

The theoretical grounding starts with Optimal Brain Damage (LeCun et al., 1989), which shows the optimal weights to remove are the ones whose removal least increases the loss, measured through the Hessian. The Hessian is too expensive at scale, so weight magnitude serves as the standard cheap proxy.

The Lottery Ticket Hypothesis explains why good sparse subnetworks exist to be found: a large randomly initialized network contains small subnetworks (“winning tickets”) that, trained in isolation from their original initialization, match the full model. Over-parametrization amounts to running many initialization lotteries in parallel, and pruning after training uncovers a winner that was there from the start.

Weight sparsity

Three structural regimes, trading flexibility against implementability:

  • Structured: remove whole rows, columns, channels, heads, or layers. Easy to execute efficiently since the dense kernels just shrink.
  • Semi-structured: fixed patterns like 2:4 (two nonzero out of every four weights), which NVIDIA Ampere and later accelerate in hardware.
  • Unstructured: remove any weight anywhere. Highest quality at a given sparsity, and hard to turn into wall-clock speedup because the access pattern is irregular.

Wanda

Wanda prunes per output, scoring each weight by the product of its magnitude and the L2 norm of its input activation. The activation term matters because LLM activations have a few large-magnitude features (the same outlier phenomenon that drives quantization design), so a small weight multiplying a large activation can still be important. No retraining, no weight updates.

def prune(W, X, s):
    metric = W.abs() * X.norm(p=2, dim=0)      # Wanda pruning metric
    _, sorted_idx = torch.sort(metric, dim=1)  # sort per output
    pruned_idx = sorted_idx[:, :int(C_in * s)] # indices to prune
    W.scatter_(dim=1, index=pruned_idx, src=0) # zero out weights
    return W

The paper reports accuracy comparable to SparseGPT at 50%, 4:8, and 2:4 sparsity while being much simpler, since SparseGPT performs expensive weight updates during pruning.

Deja Vu: contextual sparsity

Static pruning commits to one sparsity pattern for all inputs. Deja Vu observes that for a given input, only a small input-dependent subset of heads and MLP neurons matters, and predicts that subset on the fly. Small lookahead predictors run ahead of the main computation: the attention input at block predicts the MLP sparsity at block , and the MLP input predicts attention sparsity at block , so prediction overlaps with computation. The paper reports no accuracy drop up to around 75% contextual sparsity and 1.8-6x latency improvement over strong baselines, with hardware-aware sparse kernels doing the realization work.

KV cache sparsity

Attention weights at inference are extremely sparse in practice; the lecture cites attention matrices over 95% sparse with under 1% of weights carrying meaningful mass. That makes the KV cache (the memory-bound side of decoding, see Memory Management) a natural target.

Quest

Eviction-based methods drop “unimportant” KV entries based on history, and the failure mode is that a token evicted now may matter for a future query. Quest keeps the entire KV cache in memory and instead reduces movement: it tracks per-page metadata (elementwise min and max keys), estimates each page’s maximum possible attention score for the current query, and computes attention only over the top-K pages. Query-awareness is the point, since importance is decided per query rather than from history. The paper reports 7.03x self-attention speedup at 32K context with a 2K token budget, with accuracy holding on long-dependency tasks.

Multi-Head Latent Attention

DeepSeek-V2’s MLA compresses the KV cache at the architecture level: instead of caching full per-head keys and values, cache one learned low-rank latent vector per token and expand it on the fly. The paper reports a 93.3% KV cache reduction and 5.76x generation throughput improvement over DeepSeek 67B.

Attention mechanismKV cache per tokenCapability
Multi-Head Attention (MHA)Strong
Grouped-Query Attention (GQA)Moderate
Multi-Query Attention (MQA)Weak
MLAStronger than MHA per the paper

Here is the latent dimension ( in the paper) and the decoupled RoPE head dimension (). RoPE needed the decoupling trick because position-dependent rotations do not commute with the low-rank compression, so MLA keeps a small rotated component concatenated beside the compressed part.

Activation sparsity

LLM activation distributions concentrate around zero across MLP projections and attention weight matrices. When an activation is (near) zero, the weight columns it multiplies contribute nothing, so the corresponding weight reads can be skipped entirely. In the memory-bound decode regime, skipped weight movement converts directly to latency.

TEAL applies this training-free: during decoding, threshold low-magnitude activations to zero and skip loading the associated weight channels. Reported results: around 25% sparsity costs little accuracy for a 1.2-1.3x speedup, and 50% sparsity costs a small degradation for 1.6-1.8x, holding across model sizes from 8B to 70B.

Making sparsity pay

The recurring lesson is that sparsity only helps when the hardware can skip the zeros. 2:4 patterns get dedicated tensor core support; unstructured sparsity mostly does not pay off; activation and KV sparsity pay off in the memory-bound decode regime because the saved work is memory traffic. Zero-shot methods (Wanda, TEAL) trade a little accuracy for deployment simplicity, and fine-tuning buys the accuracy back when the budget allows. Weight and activation sparsity compose, which is where the aggressive efficiency work is heading.

Graph View