Two Lotteries: What It Takes to Make Sparsity Fast

Suppose you remove 80% of a neural network’s weights and recover its original accuracy after some additional training. Most of the connections are gone. The remaining model gives you results of the same quality. You might reasonably expect it to run much faster.

Then you put it on a GPU, and the improvement is small. Sometimes it runs slower.

To understand the result, we have to follow what happens after pruning. Pruning tells us that a model can get by with fewer connections. Turning that into a faster program requires a way to store the remaining weights, get them to the right places, and distribute the work across the chip. Each of those steps has a cost.

My PhD research sits in this gap between the computation an algorithm needs and the work a machine actually performs. It is also where two ideas about “lotteries” become useful. One concerns the smaller networks we can find inside larger ones. The other concerns the machines on which we judge them.

Jonathan Frankle and Michael Carbin’s lottery ticket hypothesis gave the first idea a precise form. In their experiments, they identified sparse subnetworks that could be reset to their original initial weights and trained in isolation to reach accuracy comparable to the full network, within a similar training budget. The connections and their starting values together made a “winning ticket.” Their paper appeared at ICLR in 2019. The Lottery Ticket Hypothesis

“dense, randomly-initialized, feed-forward networks contain subnetworks (‘winning tickets’) that — when trained in isolation — reach test accuracy comparable to the original network in a similar number of iterations.”

Frankle & Carbin, The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks, ICLR 2019

That result deserves some care. It does not establish that every large model contains an easily discoverable replacement, or that the larger network was unnecessary throughout training. Finding the subnetwork can itself require substantial training and pruning. What it does give us is evidence that, in the settings studied, a much smaller set of connections can learn the task successfully. Whether that smaller network executes efficiently is a separate question.

Sara Hooker’s hardware lottery helps explain why the answer can be disappointing. Her argument is that the success of a research idea depends partly on its compatibility with available hardware and software. An idea that fits the existing tools can be developed, tested, and scaled more easily. Another may look unpromising because the tools are poorly suited to it. That difference can influence which research gets pursued in the first place. The Hardware Lottery

“…when a research idea wins because it is suited to the available software and hardware and not because the idea is superior to alternative research directions.” Such lotteries, she writes, “can delay research progress by casting successful ideas as failures.”

Sara Hooker, The Hardware Lottery, CACM 2021

Taken together, these ideas explain a recurring problem in sparsity research: we can find a network that needs fewer connections, yet struggle to run it efficiently on the machine we have. This is especially frustrating because the dense alternative benefits from precisely the regularity that pruning removes.

Consider an ordinary matrix multiplication. With dense matrices, the program knows where each value lives from its position. It can fetch rectangular blocks, reuse them across many operations, and assign predictable amounts of work to parallel processing units. GPUs and their software libraries are built to make this process extremely efficient.

Setting some entries to zero leaves that execution plan intact. If the program still calls the same dense multiplication, it generally performs the scheduled operations, including those involving zeros. A zero can affect switching activity and energy, but its presence alone does not make the instruction finish sooner. To reduce execution time, the implementation has to avoid issuing the unnecessary work.

That starts with representing what remains. A sparse format can omit zero values, but it must also describe the positions of the values it keeps. Those positions take space. For a simple example, suppose each weight occupies two bytes and each surviving weight needs a two-byte column index. Keeping half the weights then uses as many bytes for values and indices as the original dense array, before any additional row information. Other formats make different tradeoffs, but a smaller count of stored values does not automatically mean a smaller representation.

The indices also have to be used. The surviving weights may be packed next to one another in memory, while referring to input values scattered across many locations. Fetching those inputs can require more memory transactions and reduce reuse. The processor may spend less time multiplying and more time locating and moving the operands.

Even when the data arrives quickly, there is still the question of who does the work. Imagine four processing units that initially receive 100 operations each. After pruning, three have ten operations left and the fourth has ninety. Seventy percent of the total work has disappeared. But if those assignments stay fixed and the units must finish together, the completion time is still set by the unit doing ninety operations. Redistributing the work can help, at the cost of additional scheduling and communication.

These costs explain why two matrices with the same percentage of zeros can have very different runtimes. Their nonzero entries may be arranged differently, require different metadata, or leave different parts of the machine idle. The sparsity percentage describes how much arithmetic could be removed. It says much less about the cost of performing what remains.

Researchers have been addressing these problems for years. EIE, presented at ISCA in 2016, designed an inference engine around compressed neural networks. SCNN, presented at ISCA in 2017, kept sparse weights and activations compressed and designed their movement and accumulation around that representation. Both demonstrated that sparsity could deliver real benefits when the architecture supported it. They also showed how much design work was required to obtain those benefits. EIE, SCNN

Another approach is to make the sparse pattern more regular. Instead of removing individual weights wherever they seem least important, we can remove entire blocks or channels. The remaining work is easier to describe and organize. The restriction, however, changes what the model is allowed to remove: a block may contain several dispensable weights alongside a few useful ones. Ease of execution and preservation of model quality have to be considered together.

NVIDIA’s 2:4 sparsity support is a concrete example of this tradeoff. In the supported arrangement, each group of four values contains at most two nonzero entries. The hardware stores the retained values with compact position information and uses that information to select the corresponding operands. This restricted pattern allows supported Sparse Tensor Core operations to achieve twice the effective arithmetic throughput of their dense counterparts. NVIDIA’s explanation of 2:4 sparsity

The restriction matters as much as the throughput number. A matrix with half its entries removed at arbitrary positions does not necessarily qualify. The model must satisfy the particular grouping the hardware supports, and the software must invoke a compatible implementation. Nor does twice the arithmetic throughput imply that an entire application runs twice as fast; memory traffic, other layers, and execution overhead remain.

I find 2:4 interesting because it makes the negotiation between algorithms and hardware explicit. The hardware offers an efficient way to execute a particular structure. Pruning and training methods then try to produce a model that fits that structure while preserving quality. The resulting model reflects both what can be removed without unacceptable damage and what the machine can exploit economically.

This negotiation becomes more complicated when we move from pruned weights to the kinds of sparsity used in language models. The word now covers several mechanisms, and treating them as interchangeable obscures where the savings come from.

In a mixture-of-experts model, a router sends each token to a small subset of the available expert networks. The unselected experts still have weights, and the selected experts can perform dense matrix multiplications internally. The saving comes from activating only part of the model for each token. Routing, uneven demand for experts, and communication between devices become central costs. Switch Transformers

Sparse attention makes a different choice: it limits which token interactions are computed. Ordinary attention does not generally produce a table full of exact zeros. A sparse method imposes a pattern or selects a subset of interactions, accepting a modeling constraint or approximation in exchange for less work. Likewise, selectively reading entries from a KV cache—the stored keys and values used to attend to earlier tokens—can reduce traffic without necessarily removing those entries from memory. A later token may still need them.

Graph workloads add another case. Their sparse connectivity often comes directly from the input: each vertex is connected to only a fraction of the other vertices. Here, the task may require processing the given edges. The architecture has to organize that existing structure, with whatever irregularity it contains. There may be no training procedure that can conveniently reshape it into the chip’s preferred pattern.

Across these examples, two properties keep becoming decisive: the size and arrangement of the work we can omit, and how early we know what that work is. A fixed weight pattern can be compressed and scheduled ahead of repeated inference. An expert assignment or an attention selection may depend on the current input and must be handled during execution. Even a graph known in advance may be worth preprocessing only if it will be reused enough times.

Dynamic selection creates an especially demanding requirement. The system must decide what to skip cheaply enough to benefit from skipping it. A predictor is one option; a learned router or a fixed attention window is another kind of mechanism. Their costs differ. If a method must compute all the expensive attention scores before deciding which ones to discard, it has already paid for that part of the calculation. The decision needs to arrive early enough to avoid meaningful work.

Language-model inference makes these distinctions consequential because its bottlenecks change with the workload. During token generation at small batch sizes, moving weights and cached data from memory can limit performance. Larger batches allow more reuse and can shift the balance toward computation. Processing a long prompt also differs from generating its continuation one token at a time. A technique that removes multiplications may help little when those multiplications are already waiting on memory. FlashDecoding++

This gives sparsity several opportunities, each with a different condition for success. Avoiding weight reads can help when weight traffic dominates. Selecting fewer cached tokens can help when attention reads dominate. Reducing token interactions can help with the growing arithmetic cost of long prompts. In every case, the omitted work has to relieve the actual bottleneck, and the selection and data movement must leave enough of the saving intact.

DeepSeek and Peking University’s Native Sparse Attention, published at ACL in 2025, illustrates how these concerns can shape an algorithm from the beginning. It combines compressed representations of token blocks, selected blocks, and a local attention window. Its design considers GPU execution alongside the information the model needs, and it supports training with the sparse attention mechanism in place. Native Sparse Attention

The significance, to me, is that the attention pattern, training procedure, and implementation are developed together. Selecting the mathematically smallest set of interactions would be of limited use if collecting them required expensive, scattered accesses. Working with blocks gives the implementation more regular work, while the other attention paths help preserve information. It is a concrete attempt to find a structure that serves both the model and the machine.

I expect more sparse models to be trained with these execution constraints built in. Hardware support will increasingly influence which connections and token interactions a model learns to use. Choosing the patterns a chip supports therefore has consequences for model design as well as execution speed. That is a substantial responsibility for architecture researchers.

It also calls for careful evidence. A good result should establish which work can be removed, what it costs to identify and organize the remainder, and how the complete application benefits at a stated level of model quality. An isolated operation count cannot establish that. Neither can a fast sparse kernel whose inputs require an expensive conversion excluded from the measurement.

The evaluation should also reflect how the system will be used. Preprocessing that is worthwhile for a graph reused thousands of times may be a poor choice for a graph processed once. A method that helps one request may behave differently under a large batch. Latency, throughput, memory capacity, and energy are related, but a gain in one does not guarantee the same gain in the others. These distinctions tell us whether a proposed saving survives deployment.

There is a longer-term concern here too. Once a hardware platform makes one sparse pattern easy to use, researchers have a practical reason to concentrate on that pattern. Software improves, training recipes accumulate, and the pattern becomes easier to justify in the next chip. Other structures become harder to evaluate fairly. This is the risk I take from Hooker’s argument: the tools can gradually narrow the alternatives we are able to explore.

For architecture research, I think that makes selective flexibility worth pursuing. An accelerator might support several block sizes, programmable selection, or a scheduler that adapts to uneven workloads. Each feature consumes area, energy, and control effort, so flexibility needs a specific justification. The aim is to support meaningful variation in models and inputs while retaining enough regularity to execute efficiently.

I organized awesome-sparse-acceleration around these connections because they are easy to miss when pruning, sparse execution, attention, and graph processing are studied separately. Reading across them brings the same questions into view: what can be omitted, when that becomes known, and what the machine must do to turn the omission into a saving.

amir-ghz / awesome-sparse-acceleration Awesome list

Sparsity in deep learning from pruning theory to silicon, arranged by mechanism so you can read across pruning, sparse execution, attention, and graph processing in one place.

590 papers 11 sections every link verified Open on GitHub

Those questions are what I want to work on. Finding a smaller network is already a substantial achievement. Making it useful requires following the consequences all the way through memory, scheduling, and execution. I want to build hardware that can make more of those smaller computations practical, while leaving room for the next model to need a different structure. That is how I think we can improve the odds in both lotteries.