DynaX: Sparse Attention Acceleration with Dynamic X: M Fine-Grained Structured Pruning

Xiao Xiong, Zhaorui Chen, Yue Liang, Minghao Tian, Jiaxing Shang, Jiang Zhong and 1 other

Transformers spend most of their effort comparing every word to every other word, a cost that explodes on long inputs even though the vast majority of those comparisons turn out to matter very little; this work from Chongqing University builds DynaX, a co-designed chip and algorithm that keeps only a flexible, input-dependent number of the important comparisons in each small group — rather than a fixed number — and then repacks the survivors to exactly fill the chip's grid of multiply units, skipping about 90 percent of the work with under 1 percent accuracy loss and running roughly twice as fast as prior sparse-attention accelerators.

The argument in one glance

Problem

Attention is quadratic, and most of it is wasted work

Self-attention compares every token against every other token, so its cost grows quadratically with sequence length and dominates on long inputs. Most of those comparisons are unimportant, so pruning them (dynamic sparsity) could cut the work — but the surviving patterns are irregular and hard for hardware, and deciding what to keep is itself costly.
What people did

Prune with fixed N:M structured sparsity

Use structured pruning that keeps a fixed number N of every group of M scores (for example, 2 of every 4), giving a regular pattern that specialized hardware can exploit efficiently.
Why it fell short

A fixed density fits neither the data nor the array well

A fixed N applies the same density everywhere, so it over-prunes groups that needed more kept (hurting accuracy) and under-prunes groups where more could be dropped (leaving sparsity unused). And truly dynamic, irregular sparsity wastes the processing-element array, which runs efficiently only on regular blocks that fill it.
This paper's idea

Dynamic X:M pruning plus block scheduling (DynaX)

DynaX is an algorithm-hardware co-design that accelerates attention with dynamic X:M fine-grained structured pruning. Instead of a fixed N, it selects a variable number X of important scores from each group of M via a lightweight 2-step method, reaching higher sparsity with less prediction memory while keeping the pattern regular enough for hardware. It then reorganizes the kept blocks, via block scheduling, into hardware blocks that exactly match the processing-element array for high utilization — achieving about 90 percent sparsity with under 1 percent accuracy loss.

Why this problem is worth solving

The very mechanism that makes transformers powerful is also what makes them expensive on long inputs.

A transformer processes a sequence of tokens using self-attention: for each token it computes a relevance score against every other token, so a sequence of a given length produces a score matrix whose size is that length squared. This means the cost of attention grows quadratically with the sequence length — double the input and the attention work roughly quadruples. For short inputs this is fine, but as models are asked to handle ever-longer sequences, attention becomes the dominant bottleneck. The saving grace is that the score matrix is highly redundant: for any given input, most of those pairwise scores turn out to be small and unimportant, contributing almost nothing to the result. Dynamic sparsity exploits this by computing only the important scores and skipping the rest, with the decision of which to keep made per input at runtime rather than fixed in advance. In principle this can remove the great majority of the work. In practice, dynamic attention sparsity for long sequences runs into two challenges: the patterns of which scores survive are irregular, and the process of deciding which to keep — the prediction step — carries its own overhead.

Turning that redundancy into real speed requires satisfying hardware that wants regularity.

Specialized accelerators are built around a processing-element array: a regular grid of multiply-accumulate units that runs at peak efficiency when it is fed regular, dense blocks of work that fill the grid. Arbitrary, irregular sparsity — where the kept elements are scattered unpredictably — leaves much of the array idle, so the theoretical savings do not materialize. To bridge this, a common technique is structured sparsity, and in particular N:M pruning: within every group of M consecutive elements, keep exactly N of them (for example, keep 2 of every 4). This produces a regular, predictable pattern that hardware can exploit. But the fixed N is a compromise. Because it applies the same density to every group, it over-prunes groups that actually needed more of their scores retained, which hurts accuracy, and under-prunes groups where even more could safely be dropped, which leaves achievable sparsity on the table. What one wants is the regularity of structured pruning combined with the flexibility to keep more where it matters and less where it does not — without paying a heavy price to figure out where that is, and without handing the array irregular work.

What people did before, and where it broke

Compute dense attention. Compute the full score matrix between all token pairs. Where it broke. The cost grows quadratically with sequence length and dominates long-sequence models, even though most of the scores are unimportant.
Prune with fixed N:M structured sparsity. Keep a fixed number of scores per group so the pattern stays regular and hardware-friendly. Where it broke. A single fixed density over-prunes informative groups (losing accuracy) and under-prunes uninformative ones (wasting potential sparsity).
Use fully dynamic, unstructured sparsity. Keep exactly the important scores wherever they fall. Where it broke. The resulting irregular pattern wastes the processing-element array, and the prediction needed to find the important scores adds heavy compute and memory overhead.
The gap. No approach combined high, input-adaptive sparsity with cheap prediction and hardware-friendly regularity, and matched the result to the accelerator array. Providing exactly that is what DynaX does.

How DynaX works

From a dense quadratic score matrix to array-matched dynamic sparsity

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

The idea

Skip the vast majority of comparisons that do not matter. DynaX’s premise is that attention’s quadratic cost is mostly spent on pairwise scores that contribute almost nothing, so the path to speed is to compute only the important ones and skip the rest, reaching around 90 percent sparsity. Spending effort only on the small fraction of the data that is relevant and fast-forwarding past the irrelevant majority is the same strategy the streaming-JSON-query work covered elsewhere on this site is built on, skipping over the large portions of the input that do not matter to the query so that work is spent only where it counts.

Adapt how much to keep, instead of a fixed budget. Rather than the fixed N of traditional N:M pruning, DynaX chooses a variable X per group of M, keeping more scores where a group is informative and fewer where it is not, which reaches higher sparsity at the same accuracy and less prediction memory than a one-density-fits-all scheme. Replacing a single fixed, worst-case-uniform setting with a decision that adapts to what each case actually needs, so the common easy cases run leaner while the few important ones keep what they require, is the same move the secure-undervolting work covered elsewhere on this site makes, tailoring its treatment to the small set of cases that genuinely need more rather than applying one conservative margin everywhere.

Repack the survivors so the array is never idle. Variable-density pruning leaves blocks of differing sizes, which would waste a regular hardware grid, so DynaX performs block scheduling to reorganize the kept scores into uniform blocks that exactly fill the processing-element array, keeping every multiply unit busy. Arranging and sizing the computation so that it precisely matches the shape of the processing array and keeps it fully utilized is the same discipline the tinyML accelerator work covered elsewhere on this site follows, structuring and scaling the compute to fit the array so that hardware is spent on useful work instead of sitting idle on a poor fit.

Following a long-sequence attention through DynaX

Computing attention for a long input under DynaX

A high-level trace of the approach as described in the abstract; the exact 2-step pruning and block-scheduling algorithms are beyond the abstract this page is based on.

Step 1 of 5

A long sequence, a huge score matrix

A transformer processes a long input. Naively it would score every pair of tokens, a matrix whose size is the sequence length squared, most of whose entries turn out to be unimportant.

The quadratic cost is the bottleneck for long sequences.

Why it works

Most attention scores do not matter. Because attention cost grows quadratically with sequence length while only a small fraction of token pairs are actually important → computing the full dense matrix wastes most of the work → so pruning to the important scores is where the speedup comes from.
A variable budget beats a fixed one. Because different groups of scores carry different amounts of information → keeping a fixed number per group over-prunes some and under-prunes others → so choosing a variable number per group reaches higher sparsity at the same accuracy.
Cheap prediction keeps the win. Because deciding which scores to keep itself costs compute and memory → a lightweight two-step method with little prediction memory keeps that overhead small → so the savings from sparsity are not eaten by the cost of finding it.
Regularity keeps the hardware efficient. Because a processing-element array runs efficiently only on regular blocks that fill it → maintaining pattern regularity and scheduling blocks to match the array size keeps it fully utilized → so the sparsity translates into real hardware speedup rather than idle units.
Co-design compounds the gains. Because the pruning algorithm and the accelerator are designed together → high sparsity, low prediction overhead, and full array utilization reinforce one another → so DynaX beats prior sparse-attention accelerators on both speed and energy.

What it costs (trade-offs and scope)

Structured pruning is still a constraint. Dynamic X:M keeps the pattern only regular “to a certain extent,” so it is more flexible than fixed N:M but less flexible than fully unstructured sparsity. It trades a little of the ideal sparsity for the regularity that hardware needs.
Prediction is cheaper, not free. The two-step method reduces prediction memory and overhead, but predicting which scores matter still costs some computation and memory; the net benefit depends on that cost staying well below the savings.
It requires custom hardware. DynaX is an algorithm-hardware co-design with a processing-element array and block scheduling. Its gains depend on the specialized accelerator, not just a software change, so realizing them requires building the hardware.
Accuracy is preserved, not guaranteed everywhere. The reported under-one-percent accuracy loss holds for the evaluated tasks and models; aggressive sparsity on other models or tasks could affect accuracy differently, and the right sparsity level may need tuning.
The gains are workload- and baseline-specific. The reported sparsity levels and the speedups and energy improvements over prior accelerators are measured on specific tasks and models (including BERT-base) against specific baselines; other settings would shift the numbers.
This page is written from the abstract. The full text was not available when this explainer was prepared, so the exact two-step pruning algorithm, the block-scheduling details, and the full evaluation are summarized only at the level the abstract states, without invented specifics.

The evaluation

Three ways to compute transformer attention

Property	Dense attention	Fixed N:M sparsity	DynaX (dynamic X:M)
Skips unimportant scores		Yes, fixed density
Adapts pruning to each group	Not applicable	No, fixed number kept
Prediction overhead		Some
Processing-array utilization		Reduced by irregularity
Outcome	Quadratic cost	Regular but rigid	High sparsity, under 1 percent accuracy loss

Three ways to compute transformer attention, as framed by the paper's abstract. Dense attention computes the full score matrix between all token pairs, a cost quadratic in sequence length. Fixed N:M structured sparsity keeps a fixed number of scores per group, giving a hardware-friendly regular pattern but a single density that fits neither the data nor the array ideally. DynaX uses dynamic X:M pruning: it keeps a variable number of important scores per group via a lightweight two-step method, reaching higher sparsity with less prediction memory while staying regular enough for hardware, then reorganizes the kept blocks to exactly match the processing-element array. The abstract reports average sparsity of 89.54 percent for short-sequence tasks and 91.77 percent for long-sequence tasks, with less than 1 percent accuracy loss, and, compared to the prior accelerators Sanger and SALO2, a 1.99 times and 1.50 times speedup on the BERT-base model with a 5.16 times and 4.20 times energy-efficiency improvement, respectively. These figures are from the abstract; the full paper was not available for this explainer.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

DynaX targets a central and growing cost in modern AI: the quadratic price of self-attention on long sequences. Its framing is clean, and the core idea is a genuine refinement of a popular technique. Fixed N:M structured pruning gives hardware the regular sparsity it needs but wastes flexibility by keeping the same number of scores in every group; DynaX instead keeps a variable number per group, so it can prune harder where a group is uninformative and keep more where it is not, reaching higher sparsity at the same accuracy and with less prediction memory. Crucially, it does not stop at the algorithm: it reorganizes the resulting variable-sized blocks, through block scheduling, into blocks that exactly fit the processing-element array, so the sparsity actually keeps the hardware busy rather than leaving multiply units idle. That algorithm-hardware co-design is what lets the reported sparsity — about 90 percent, with under one percent accuracy loss — turn into real speedups and energy savings, a reported 1.99 and 1.50 times faster and 5.16 and 4.20 times more energy-efficient than two prior sparse-attention accelerators on BERT-base. Read the specifics with care. This explainer is written from the abstract, so the exact two-step pruning method, the block-scheduling algorithm, and the full evaluation are not reproduced here. As trade-offs, the approach still constrains sparsity to a hardware-friendly structure, its prediction is cheaper but not free, it depends on custom hardware, and the accuracy and speedup figures are specific to the evaluated models, tasks, and baselines. The durable idea is that structured sparsity does not have to mean a fixed density, and that letting the amount of pruning vary — while carefully repacking the result to fit the accelerator — captures more of attention’s redundancy without giving up the regularity that hardware demands.

Background

Why matching irregular data to a regular array keeps recurring

It helps to see DynaX within a broad theme in AI acceleration: the biggest workloads are full of redundancy that could be skipped, but the hardware built to run them fast is a rigid, regular grid that punishes irregularity, so the central challenge is turning irregular savings into regular, array-friendly work. Attention is mostly unimportant scores, but a processing-element array only runs efficiently on dense blocks that fill it; DynaX’s answer is to prune in a semi-structured way and then repack the survivors to match the array exactly. The encrypted-computation acceleration work covered elsewhere on this site reflects the same instinct from a different corner, reshaping the algorithm itself — down to its numeric representation and its operation ordering — so that a heavy AI-adjacent workload maps cleanly onto what the accelerator does efficiently rather than fighting the hardware. The common thread is that raw algorithmic savings are not enough on their own: they must be delivered to the hardware in the shape it wants, or the theoretical speedup evaporates into idle units and wasted bandwidth. Co-designing the algorithm and the accelerator together — pruning in a way the array can use, scheduling blocks to fit it, keeping the deciding-what-to-skip step cheap — is what converts redundancy into real, measured efficiency. As sequence lengths and model sizes keep growing, this ability to exploit sparsity without surrendering hardware regularity is likely to remain one of the most important levers for making attention affordable.

If you remember only three things

1. Transformers rely on self-attention, which compares every token in a sequence against every other token, so its cost grows quadratically with sequence length and becomes the bottleneck on long inputs. Most of those pairwise scores are unimportant, so dynamic sparsity — computing only the important ones, chosen per input at runtime — can remove most of the work. But it faces two obstacles: the surviving sparse patterns are irregular, and specialized accelerators (built around a regular grid of multiply-accumulate units, the processing-element array) run poorly on irregular data; and deciding which scores to keep requires a prediction step that itself costs compute and memory.
2. DynaX is an algorithm-hardware co-design that accelerates attention via dynamic X:M fine-grained structured pruning. Unlike traditional N:M pruning, which keeps a fixed number N of every group of M scores, DynaX keeps a variable number X per group, chosen by a lightweight two-step method — reaching higher sparsity with less prediction memory while keeping the pattern regular enough for hardware, by adapting the density to how informative each group is. It then performs block scheduling to reorganize the kept, variable-sized score blocks into uniform hardware blocks that exactly match the size of the processing-element array, so the array stays fully utilized rather than idled by irregular sparsity.
3. The abstract reports that DynaX achieves average sparsity of 89.54 percent for short-sequence tasks and 91.77 percent for long-sequence tasks with less than 1 percent accuracy loss, and, compared to the prior accelerators Sanger and SALO2, a 1.99 times and 1.50 times speedup on the BERT-base model with a 5.16 times and 4.20 times energy-efficiency improvement. Scope: it still constrains sparsity to a hardware-friendly structure, its prediction is cheaper but not free, it depends on custom hardware, and the accuracy and speedup figures are specific to the evaluated models and baselines. Note: this explainer is written from the abstract, as the full text was not available, so the exact algorithms and full evaluation are summarized only at the level the abstract states. The durable lesson is that structured sparsity need not mean a fixed density, and that repacking variable-density results to fit the accelerator captures more redundancy without giving up hardware regularity.

Check yourself

Check your understanding

1. Why does self-attention become a bottleneck for long sequences, and what makes it addressable?
2. How does DynaX's dynamic X:M pruning differ from traditional N:M pruning, and why does it help?
3. Why does DynaX perform block scheduling after pruning?
4. What do DynaX's reported results indicate about its approach?

Sources

The paper is “DynaX: Sparse Attention Acceleration with Dynamic X:M Fine-Grained Structured Pruning” by Xiao Xiong, Zhaorui Chen, Yue Liang, Minghao Tian, Jiaxing Shang, Jiang Zhong, and Dajiang Liu, published at ASPLOS 2025, DOI 10.1145/3676641.3715991. The authors are at Chongqing University.

This explainer is written from the paper’s abstract, because the full text was not available at the time of writing: the publisher’s copy was behind automated-access protection, no preprint was found, and no separately hosted open-access copy could be retrieved. The problem framing (self-attention’s quadratic cost with sequence length, dynamic sparsity as a remedy, and the two challenges of irregular sparse patterns and heavy prediction overhead), the description of the approach (dynamic X:M fine-grained structured pruning that selects a variable number of important scores from each group via a two-step pruning method, in contrast to fixed N:M pruning, achieving high sparsity with less prediction memory while maintaining pattern regularity to a certain extent; and the block scheduling that reorganizes score blocks into hardware blocks matching the size of the processing-element array for higher utilization), and the results (average sparsity of 89.54 percent for short-sequence tasks and 91.77 percent for long-sequence tasks with less than 1 percent accuracy loss, and, compared to Sanger and SALO2, a 1.99 times and 1.50 times speedup on the BERT-base model with a 5.16 times and 4.20 times energy-efficiency improvement, respectively) come directly from the abstract. The surrounding explanation of transformer self-attention, structured and N:M pruning, processing-element arrays, and algorithm-hardware co-design is standard, widely-known background provided to make the abstract’s claims understandable, and is not specific to this paper. The exact two-step pruning method, the block-scheduling algorithm, and the detailed evaluation are not reproduced here because they were not available.