Pruning for the Tile, Not the Weight: Clustering-Based Row Grouping for Fast High-Sparsity LLMs

Removing 70–85% of a language model's weights should make it several times cheaper to run. On GPUs it usually does not. The leftover nonzeros sit at scattered positions, and the hardware is built to multiply small dense blocks. Fast sparse kernels such as SMaT get around this by reordering matrix rows so that nonzeros land together in dense 16×8 "tiles" that the GPU's matrix units can consume. SMaT reports beating dense cuBLAS at sparsity as low as 78%. However, SMaT treats the sparsity pattern as fixed and reorders it after the fact with an unguided similarity heuristic. When a model is being pruned, the pattern is not fixed: we choose which weights die. That makes "prune, then reorder" an artificial two-stage split.

This note proposes doing both steps together. We group the rows of each weight matrix into blocks of 16, then keep or drop whole tiles depending on whether the importance they carry is worth their compute cost. This joint problem is a clustering problem with a facility-location-style cost. That matters because the approximation-algorithms literature has learned specific lessons about why simple swap-based search gets stuck on such problems and how to unstick it. The proposal imports two of those lessons. The first is non-oblivious local search, which judges a move with a modified score that also credits good "backup" placements. The second is certified lower bounds, which tell us how far from optimal a solution is. We then test whether these lessons buy real accuracy at a fixed measured latency.

Core Claim

Fix a weight matrix $W$ and a per-weight importance score $s_{ij} = |W_{ij}|\cdot\|X_j\|_2$, the activation-weighted magnitude from Wanda, where $X_j$ is the calibration activation of input $j$. Partition the rows into groups $g$ of 16 and the columns into fixed blocks $b$ of width 8. Let $S_{gb}$ be the total importance inside tile $(g,b)$. Opening a tile costs a latency price $\lambda$ and keeps all of its weights. Closing it loses its importance. For a row grouping $P$, the best tile choice is then immediate, and the objective is

$$\Phi(P) = \sum_{g \in P}\sum_{b} \min(\lambda, S_{gb}),$$

which we minimize over balanced partitions $P$. Sweeping $\lambda$ traces a curve of accuracy against tile count, and tile count is what the kernel's runtime actually tracks.

This is a clustering problem with a concave per-cluster cost. Simple row-swap search on it has a specific failure mode, the same one that capped oblivious $k$-median local search at a factor of 3. Moving one row rarely pushes a tile across the threshold $\lambda$ on its own, so every single move looks useless even when a coordinated regrouping would help a lot. In $k$-median, Cohen-Addad et al. broke the barrier by searching on a surrogate potential that also rewards each client's second-closest facility. That gave a $(2.836+\epsilon)$ ratio without any linear program.

Our claim is in three parts. The analogous surrogate, which credits each row's importance mass in its best alternative group, escapes these traps. It produces measurably fewer tiles than SMaT-style similarity reordering of a Wanda mask at equal retained importance. On LLaMA-3.1-8B and Qwen-2.5-7B, this translates into lower perplexity at matched A100 latency in the 70–85% sparsity regime. That is the regime where hardware 2:4 sparsity, which is fixed at 50%, cannot reach.

Research Program

The work has four parts.

The first part is the formulation and a cheap seed. We start from SMaT's Jaccard-similarity row ordering, applied to the top-importance support of $W$. This gives an initial balanced partition. It is exactly the competitor's solution, so any improvement over it is attributable to what follows.

The second part is the search. The basic move exchanges two rows between groups, which keeps group sizes balanced, and we also allow occasional three-row rotations. The oblivious version accepts a move if it lowers $\Phi$. The non-oblivious version accepts moves that lower an augmented potential. That potential adds, for each row, $\beta\cdot\min\{\text{loss in its second-best group}, \alpha\cdot\text{loss in its current group}\}$, with the capped form taken directly from Cohen-Addad et al.. We will tune $\alpha$ and $\beta$ on one layer and freeze them.

The third part is analysis. We want hand-built families of matrices on which oblivious swaps get stuck far from optimum and the surrogate does not. Our hypothesis is that row-swap locality gaps follow the same backup-placement mechanism; if they do not, that is a reportable negative finding. Proving a general approximation ratio is a stretch goal, not a promise. For balanced partitioning with concave costs, we have no tractable guarantee to lean on.

The fourth part is certification. The compact linear-programming relaxation of this problem is nearly useless because groups are interchangeable. The symmetric fractional solution simply opens each column block once. So instead of relying on it, we solve the exact integer program on 256-row slices of real layers. That gives ground truth for the remaining gap of each search variant.

Once the tile mask is chosen, every method gets the same weight-compensation step. We use the column-wise Optimal Brain Surgeon update of SparseGPT, which handles arbitrary masks. This keeps the comparison focused on mask quality. The row permutation is folded into the next layer's input order, as Pool & Yu do for channels, so it costs nothing at inference time.

The search runs per layer on 4096-row matrices, and all rows share the same activation statistics. We expect it to take minutes per layer on CPU. That is a direct contrast with the roughly 2.5 hours on 4 GPUs that PermLLM reports for a 7B model.

Baselines

Dense reference. The naive reference point is the unpruned model run with dense cuBLAS. It fixes the latency we must beat and the perplexity ceiling. Any method slower than dense at its sparsity level has failed outright.

Wanda unstructured pruning plus SMaT reordering. This is the strongest competitor on our exact question. We prune each layer with Wanda at a target sparsity, reorder rows with SMaT's Jaccard clustering, pack into 16×8 tiles, and run with SMaT's kernel. It is strong because SMaT is the only cited kernel shown to beat cuBLAS on unstructured matrices, at 78% sparsity and above. To be fair, it uses the same calibration data, the same compensation step, the same kernel and the same GPU. We compare at matched measured latency.

No reported result was found on Lacuna for Wanda or SparseGPT perplexity on LLaMA-3.1-8B at 70–85% unstructured sparsity, so we will produce that number ourselves. Beating this baseline means one of two things across at least two sparsity levels: lower WikiText-2 perplexity at equal kernel latency, or equal perplexity with at least 15% fewer tiles.

Tile-wise sparsity without permutation. This is the approach of Guo et al., which prunes whole rows or columns inside GEMM tiles. They report a 1.95× speedup on V100 tensor cores and a 1–3% accuracy loss at 75% sparsity. It isolates the value of regrouping rows at all.

2:4 reference. At 50% sparsity, PermLLM reports 14.03 WikiText-2 perplexity on LLaMA-3.1-8B, against 23.42 for Wanda 2:4. For speed, ARMOR reports a 1.86× layer speedup for plain 2:4 pruning. We include these as a regime marker, not as a target at higher sparsity.

Ablations isolating the key ingredient. We run three. The first is oblivious swap search on the same objective. The second is the same oblivious search given simulated annealing and random restarts up to the non-oblivious method's wall-clock time. The third is the Jaccard seed alone.

Why not just…?

Why not just prune with Wanda and reorder with SMaT, since both already exist? That pipeline optimizes similarity of nonzero patterns, not importance retained per tile. It also cannot drop a weight that sits alone in a tile and would cost a whole tile to keep. Whether this matters is an empirical question, and the main comparison settles it. If tile counts at equal retained importance differ by less than a few percent, the joint formulation is not worth it, and we would say so.

Why not just run more restarts or simulated annealing on the simple objective? This is the real threat to the approximation-theory ingredient. Pool & Yu already found that greedy channel swaps get trapped and patched this with random restarts. The time-matched annealing ablation, together with exact-solution gaps on 256-row slices, decides it. If annealing closes the gap equally well, the contribution narrows to the formulation and the certified gaps, and we will report it that way.

Why not just use hardware 2:4 sparsity with a good permutation? At 50% sparsity it is likely the better choice: it gets a guaranteed 2× math speedup, and PermLLM-level accuracy is already strong. But 2:4 is locked at 50%. Our method targets 70–85%, where SMaT's evidence suggests tiled execution beats dense. We will plot both on one latency–perplexity curve and state where they cross.

Why not just learn the grouping with Sinkhorn relaxations as PermLLM does? PermLLM needs multi-GPU hours and restricts itself to 64-channel windows. It also offers no measure of how far its rounded result is from optimal. We will run its relaxation on our objective for one model as a comparison point, given its native compute budget.

Proposed Experiments

The models are LLaMA-3.1-8B and Qwen-2.5-7B. These are the sub-13B sizes where pruning hurts most, and the file has reported baselines for them. We measure WikiText-2 perplexity and average zero-shot accuracy on BoolQ, RTE, HellaSwag, ARC and OpenBookQA. Target sparsities are 70%, 78% and 85%, with $\lambda$ tuned per method to hit each target. Latency is end-to-end per linear layer on an A100, using one shared BCSR tile kernel for all tile-based methods. We also report tile count and fill ratio, meaning kept nonzeros divided by tile capacity.

There are three decisive checks. The first concerns tile count. At equal retained importance, non-oblivious search should use measurably fewer tiles than the Jaccard reordering. It should also beat time-matched oblivious annealing on the exact-solved slices, by closing a larger fraction of the gap to optimum. The second concerns accuracy. Fewer tiles must become lower perplexity at matched measured latency, not merely higher retained importance. PermLLM's observation that importance scores can disagree with output loss makes this a genuine risk, so we will also report layer reconstruction error. The third concerns the regime. The method must beat dense cuBLAS latency at a sparsity where its perplexity remains usable. If the crossover sits above the sparsity at which accuracy collapses, the regime does not exist for these models, and that is the headline negative result.