Fractal: Joint Multi-Level Sparse Pattern Tuning of Accuracy and Performance for DNN Pruning

Pruning a neural network deletes most of its weights, but the leftover sparse model usually runs no faster on a GPU because the surviving weights are scattered — so people impose regular sparse patterns to keep them tidy, each pattern a hand-built kernel that trades accuracy for speed at one fixed granularity; this work from Shanghai Jiao Tong builds Fractal, which reframes every such pattern as skipping computation at some level of the GPU's tiling hierarchy, opens up skipping at multiple levels at once, and auto-tunes the best pattern for each layer jointly for accuracy and speed — reaching up to 3.16 times the speed of the dense model while barely losing accuracy.

The argument in one glance

Problem

Pruning a network saves work on paper, but not on the GPU

Neural networks are full of redundant weights, so pruning — zeroing the unimportant ones — is an appealing way to shrink a model and cut its computation. But the promise rarely materializes on real hardware: a pruned model with, say, 75 percent of its weights removed often runs no faster than the dense original, sometimes slower. The surviving weights are scattered irregularly, which wrecks the memory locality and predictable access that GPUs need, and finding where the non-zeros are adds its own overhead.
What people did

Force the surviving weights into a regular sparse pattern

To get real speedups, researchers impose structure: prune weights in groups so the survivors form tidy blocks the hardware can process efficiently. These structured sparse patterns come in flavors — block-wise, tile-wise, vector-wise (like the 2:4 pattern a Sparse Tensor Core supports) — each keeping non-zeros in a regular shape at some granularity, and each shipped as its own hand-tuned kernel.
Why it fell short

Each pattern is a fixed, hand-built compromise, and choosing is a huge trade-off

Every pattern is a separate hand-crafted kernel locked to a single tiling granularity, so the libraries do not scale to new operators or hardware. Worse, forcing structure onto the weights is a regularization constraint that costs accuracy, and different operators prefer different patterns — an attention layer wants one shape, a feed-forward layer another. Choosing the right pattern for each operator is an enormous joint trade-off between speed and accuracy, and no system searches it; developers pick by hand.
This paper's idea

See every pattern as skipping loop levels, and auto-tune across all of them

Fractal reframes a sparse pattern as skipping computation at some level of the multi-level tiling that a GPU compiler already uses for dense operators. This unifies every existing pattern as a point in one space — and reveals a new one: skipping at multiple levels at once. It captures this in a loop-based representation, PatternIR, searches the huge space of multi-level patterns while filtering by an accuracy budget, lowers the winners through an existing tensor compiler to reuse dense optimizations, and finds the best pattern for each operator jointly for accuracy and performance.

Why this problem is worth solving

The gap between the theoretical and the real saving comes from what sparsity does to hardware, so it is worth being precise.

When you prune a weight matrix, you set unimportant entries to zero, and in principle you can now skip the multiplications by zero. The trouble is that a GPU is fast only on regular, contiguous work: its memory system and thousands of parallel lanes assume dense, predictable access. Scattered non-zeros ruin that — the hardware must gather them from random locations, decode where they are, and cope with lanes doing unequal amounts of work — so unstructured pruning needs to remove more than 99 percent of weights before it beats the dense version, while real models are pruned to 50 to 90 percent. Structured sparse patterns fix this by constraining where the survivors may sit: you prune in fixed-shape groups so the remaining weights form regular blocks the hardware can stream through efficiently. A block-wise pattern keeps non-zeros in coarse tiles; a vector-wise pattern keeps a fixed ratio of non-zeros in each short vector. The regularity buys speed — but it also over-constrains which weights you may keep, so a more structured pattern generally prunes away more important weights and hurts accuracy more. Every pattern is a chosen point on this trade-off.

The reason no single pattern is right is that the choice is enormous, coupled, and operator-specific.

A sparse pattern has to be decided along several axes at once — the shape of the pruned group, the region over which weights are ranked, the granularity — and the number of combinations is astronomical: for a single one-thousand-by-one-thousand weight matrix there are on the order of hundreds of billions of possible patterns. Two things make navigating this space hard. First, the two goals conflict and are coupled: a pattern that runs fast tends to prune away more important weights, so speed and accuracy trade off, and you cannot optimize one without watching the other. Second, the best pattern differs from operator to operator — a study of a single transformer layer shows the attention-key and attention-output weights each prefer a different pattern orientation, tied to the model’s internal structure like its attention heads and hidden size. Prior work picks one pattern for the whole model by hand and hard-codes a kernel for it, which is both sub-optimal and unscalable. Meeting real accuracy and speed targets across a whole model demands searching this coupled space automatically, per operator — exactly what had been missing.

What people did before, and where it broke

Unstructured (element-wise) pruning. Rank every weight independently and prune the least important, keeping maximum accuracy for a given sparsity. Where it broke. The survivors are scattered, so GPUs need over 99 percent sparsity to see any speedup, far beyond the 50 to 90 percent real models use.
A single structured pattern with a hand-crafted kernel (block-wise, tile-wise). Constrain non-zeros to regular blocks at one granularity and hand-tune a fast kernel for it. Where it broke. Each pattern and hardware needs its own kernel, so the libraries do not scale, and one fixed pattern is sub-optimal for the diverse operators of a real model.
Hardware-supported vector sparsity (2:4 on Sparse Tensor Cores). Use a dedicated hardware unit that accelerates a fixed fine-grained pattern. Where it broke. It is limited to that one pattern and to 50 percent sparsity, and only where the special hardware exists.
Dense auto-compilers reused as-is. Let a tensor compiler like TVM auto-generate and tune code. Where it broke. These formulate a tiling space for dense operators; there was no way to formulate the multi-level sparse tiling space, so they could not tune sparse patterns.
The gap. Every approach either fixed the pattern at one level and hand-wrote its kernel, or could not represent the sparse design space at all, and none jointly tuned pattern choice for accuracy and speed per operator. What was missing was a representation that unifies sparse patterns and a system that searches them automatically — which is exactly what practical DNN pruning needs.

How Fractal works

Reframing patterns as loop skipping, then auto-tuning the multi-level space

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Unify every sparse pattern as skipping iterations of a tiling loop. The insight that opens the whole design space is that a GPU already compiles a dense operator into a nest of tiling loops — coarse tiles containing finer tiles — to fit its memory hierarchy and parallel lanes, and that every existing sparse pattern is nothing more than skipping the iterations of one of those loops. Prune a coarse loop and you get a block-wise pattern; prune a fine one and you get a tile-wise pattern. Fractal makes this literal with PatternIR, a loop-based representation borrowing the perforation idea from approximate computing, where a loop is annotated to iterate only over its non-zero indices, and it gives that representation the same composable split, reorder, and join primitives a tensor compiler uses. Turning a grab-bag of hand-built patterns into composable operations over one loop-based representation, so that a single search space replaces a fixed menu, is the same move the scheduling-language work covered elsewhere on this site makes, expressing transformations as composable primitives over loops so users can reach a whole space rather than a handful of built-ins.

Reuse the dense compiler, so sparse code generation comes for free. Once patterns are just perforated loops, the hard part — generating a fast kernel for each of the countless patterns and each piece of hardware — need not be redone. Because PatternIR is a thin layer of dense loop structure with holes, Fractal lowers it into an existing sparse tensor compiler and inherits that compiler’s mature machinery for tiling, scheduling, and auto-tuning dense loops, adding only the sparse-specific pieces (a multi-level storage format, and a primitive that gathers scattered values into aligned storage). Building on an existing compiler’s infrastructure and contributing only the genuinely new parts, so its optimizations and portability transfer without re-implementation, is the same strategy the compute-in-memory compiler work covered elsewhere on this site follows, extending a proven flow so that new capability rides on top of established code generation rather than replacing it.

Search the coupled accuracy-performance space automatically, guided by cheap estimates. With the space defined, the remaining problem is that it is astronomically large and its two objectives conflict, so hand-picking is hopeless. Fractal turns it into a joint search: it first scores each candidate pattern by how much important weight it would remove and throws out anything worse than unstructured pruning at the same sparsity, cheaply enforcing an accuracy budget before any code is generated; then it ranks the survivors with a learned latency predictor and actually compiles and times only the top few. Auto-searching a huge configuration space to jointly balance two goals that trade off against each other, using cheap predictions to avoid paying the full cost of every candidate, is the same discipline the serverless GPU-scaling work covered elsewhere on this site applies, profiling to navigate a large space toward a configuration that satisfies two coupled objectives at once.

Following a GEMM operator through Fractal

Tuning a matrix-multiply operator

Tracing one operator shows the reframing, the multi-level search, and the joint filter.

Step 1 of 5

Start from the dense tiling

The operator is a dense matrix multiply, which a GPU compiler already splits into a multi-level nest of tiling loops chosen to fit the hardware. Fractal's key observation is that every sparse pattern is just skipping some of these loop iterations.

Coarse and fine tile loops give coarse and fine sparse granularities.

Why it works

Reframing patterns as loop perforation unifies a scattered design space. Every prior sparse pattern was a separate hand-built kernel at a fixed granularity → but seeing each as skipping iterations of a tiling loop expresses them all in one loop-based representation → so a single search space contains the block, tile, and vector patterns and the hybrids between them.
Skipping at multiple levels beats skipping at one. Prior libraries prune at a single tiling level, leaving the rest of the hierarchy unexploited → but a GPU needs multiple tiling levels for locality and parallelism, and perforating several at once matches that → so a multi-level pattern gains both performance, from hardware-fit tiling, and accuracy, from richer pattern diversity.
Lowering to a dense tensor compiler inherits its optimizations for free. Writing a fast kernel for every pattern and every chip by hand does not scale → but expressing patterns as perforated loops lets them lower to a tensor compiler that already optimizes dense loops → so sparse operators get automatic, portable code generation across backends.
An accuracy proxy prunes the search before the expensive step. Measuring a pattern’s true accuracy by retraining would make the search impossibly slow → but scoring how much important weight each pattern removes, and rejecting any worse than unstructured pruning, filters candidates cheaply → so only accuracy-viable patterns reach the costly compile-and-measure stage.
A learned cost model tames a combinatorial space. There are hundreds of billions of possible patterns for one large tensor, far too many to compile → but a model trained to predict a pattern’s latency from its loop structure ranks them, so only the top few are actually built and timed → so the joint search converges in a couple of hours instead of never.

What it costs (trade-offs and scope)

Auto-tuning is slow and per-hardware. A search converges in roughly two hours per configuration, each candidate’s operator tuning can take twenty minutes, and the latency cost model must be retrained on thousands of profiled operators for every new backend; the system works without the model but more slowly.
The gains depend heavily on sparsity and shape. The large speedups appear at high sparsity — four times at 93.75 percent — while at 50 percent sparsity with large inner dimensions the dense baseline wins and only hardware-supported vector sparsity beats it; real models often sit at 50 to 90 percent.
Accuracy is guided by a proxy, not measured per candidate. Tuning filters patterns by an importance-score proxy (how much weight magnitude they remove, bounded by unstructured pruning), and the actual model accuracy is evaluated separately, so the proxy can misrank a pattern’s true effect.
Restoring accuracy is out of scope. Fractal chooses the pattern; the retraining or fine-tuning that recovers accuracy after pruning is a separate, orthogonal concern it assumes rather than solves.
The search space is heuristically bounded. Limits on tiling depth, minimum loop length, and pattern size cut the space to make search tractable, so the found pattern is optimal only within those bounds, and multi-level pruning uses a greedy coarse-to-fine heuristic.
It rests on an existing sparse tensor compiler. Fractal builds on SparseTIR, TVM, and their auto-tuner, inheriting their capabilities and limits, and correctness depends on the low-level compiler.
Evaluated mostly on matrix multiplies from a handful of models. The benchmarks are matrix multiplies and convolutions converted to them from BERT, VGG, and ResNet on a few GPUs and a CPU, not the full breadth of DNN operators.

The evaluation

Accelerating pruned sparse DNN operators

Property	Dense (cuBLAS)	Fixed pattern	Hardware vector
Sparse pattern	None
Kernel generation	Dense library		Vendor, hardware unit
Backends	All	Specific	Sparse Tensor Core only
Tunes for accuracy and speed	Not applicable	No	No
Speedup versus dense	Baseline	Modest, if any	At 50 percent sparsity only

Ways of accelerating pruned DNN operators, evaluated on NVIDIA A100 and RTX-1080Ti GPUs and a CPU across matrix multiplies and convolutions from BERT, VGG, and ResNet. Fractal averages 1.62, 2.52, and 4.00 times the dense speed at 50, 75, and 93.75 percent sparsity (up to 3.16 times on CUDA cores and 2.52 times on Tensor Cores at 75 percent), with a better accuracy-speed frontier than fixed-pattern libraries, and it runs on all backends via automatic code generation.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Fractal is an elegant reframing with a practical payoff: by seeing every sparse pattern as skipping iterations of a tiling loop, it unifies the scattered zoo of hand-built patterns into one loop-based representation, opens the previously-unexplored space of skipping at multiple levels at once, and auto-tunes the best pattern per operator jointly for accuracy and speed — reaching up to about 3 times the dense speed at 75 percent sparsity with a better accuracy-speed frontier than fixed patterns, and generating code automatically across GPUs and CPUs by reusing a dense tensor compiler. Read the numbers with their conditions. The tuning is slow (a couple of hours per configuration) and needs a per-backend cost model; the biggest speedups are at very high sparsity, while at low sparsity the dense baseline can win; accuracy during tuning is judged by a proxy, not measured, and recovering accuracy by retraining is left to a separate step; and the search space is heuristically bounded, built atop an existing sparse compiler. The durable idea is the unification: recognizing that sparse patterns and dense tiling are the same thing seen from two sides collapses a hand-crafted design problem into a search problem, and search is something a system can do far better than a person.

Background

Why cutting the math rarely cuts the time

It is worth stepping back to see why pruning so often disappoints, because it is an instance of a lesson that recurs across systems. It is tempting to equate the amount of arithmetic a model performs with how long it takes to run, so removing three quarters of the weights should make it four times faster. But a modern accelerator is not a machine that charges by the multiply; it is a machine optimized for dense, regular, predictable streams of work, and it can be idled just as easily by irregular memory access or poor locality as by too much computation. Delete weights at random and you save multiplications on paper while making the access pattern so ragged that the hardware sits waiting — a net loss. This is why the whole field of structured sparsity exists: the goal is not merely to remove work but to remove it in a shape the hardware can still stream through. The deep-learning-on-GPUs retrospective covered elsewhere on this site reaches the same conclusion from measuring real applications, finding that theoretical reductions in computation routinely fail to become real speedups because data movement and hardware fit, not arithmetic, govern the clock. Fractal matters because it aligns the shape of the saving with the shape of the hardware, which is what turns a paper reduction into a real one.

If you remember only three things

1. Pruning a neural network removes redundant weights to cut computation, but the resulting sparse model usually runs no faster (or slower) on GPUs because scattered non-zeros wreck memory locality and add decoding overhead; the fix is structured sparse patterns that keep survivors in regular blocks (block-wise, tile-wise, vector-wise), but each is a separately hand-crafted kernel locked to one tiling granularity, imposing structure costs accuracy, and different operators prefer different patterns — so choosing is a huge, coupled, per-operator trade-off between speed and accuracy that no system automated.
2. Fractal reframes every sparse pattern as computation-skipping at some level of the multi-level tiling a GPU compiler already uses for dense operators, capturing this in a loop-based IR (PatternIR) with composable tiling and perforation primitives — which unifies existing patterns as points in one space and reveals a new one, skipping at multiple levels at once; it then auto-tunes the huge space per operator by filtering candidates against an accuracy budget (an importance-score proxy bounded by unstructured pruning), ranking survivors with a learned latency cost model, and lowering the top few through an existing sparse tensor compiler (reusing dense optimizations and its auto-tuner) to measure real latency and keep the best.
3. On A100 and RTX-1080Ti GPUs and a CPU across matrix multiplies and convolutions from BERT, VGG, and ResNet, Fractal averages 1.62, 2.52, and 4.00 times the dense speed at 50, 75, and 93.75 percent sparsity (up to 3.16 times on CUDA cores), with a better accuracy-speed frontier than fixed-pattern libraries and automatic code generation across all backends — but tuning is slow (about two hours per configuration) and needs a per-backend cost model, the biggest gains are at high sparsity while dense can win at low sparsity, accuracy during tuning is a proxy rather than measured, retraining to restore accuracy is out of scope, and the search space is heuristically bounded atop an existing compiler.

Check yourself

Check your understanding

1. Why does pruning a neural network often fail to speed it up on a GPU?
2. What is Fractal's central reframing of sparse patterns?
3. How does Fractal make searching the enormous pattern space tractable?
4. Which statement best reflects the limits of Fractal?

Sources

The paper is “Fractal: Joint Multi-Level Sparse Pattern Tuning of Accuracy and Performance for DNN Pruning” by Yue Guan, Changming Yu, Yangjie Zhou, Jingwen Leng, Chao Li, and Minyi Guo, published at ASPLOS 2024, DOI 10.1145/3620666.3651351. The authors are at Shanghai Jiao Tong University and the Shanghai Qi Zhi Institute.

This explainer is written from the full 15-page text. Everything above comes from the paper’s own sections: the introduction and background on pruning, the acceleration gap of irregular sparsity, structured sparse patterns and their hierarchy (element-wise, column-wise, block-wise, tile-wise, vector-wise, hybrid), the mask-diversity accuracy proxy, and the observation that sparse patterns are instances of computation-skipping after multi-level tiling; the motivation establishing diverse operator-level pattern preferences, the need for automatic code generation, and the enormous joint accuracy-performance search space; the loop-based PatternIR built on loop perforation with its split, reorder, join, perforate, and condense primitives and the Fractal-ELL storage format; the Fractal system with its code-generation pipeline lowering PatternIR to the SparseTIR/TVM tensor compiler and MetaSchedule operator tuner, the accuracy-aware pruning via importance-score thresholds bounded by unstructured pruning, the greedy coarse-to-fine multi-level pruning, and the auto-tuner driven by a bidirectional-LSTM latency cost model; and the evaluation on A100 and RTX-1080Ti GPUs and a CPU across BERT, VGG, and ResNet operators, reporting average speedups of 1.62, 2.52, and 4.00 times at 50, 75, and 93.75 percent sparsity and improved accuracy-speed Pareto frontiers over fixed-pattern sparse libraries.