Machine learning has become full of computations where most of the numbers are zero — because models are deliberately pruned to make them smaller, and because data like road-scanner point clouds and social graphs is naturally mostly empty — and processors built for dense arithmetic waste most of their effort multiplying zeros; the usual answer is a purpose-built chip, and those work superbly on the one operation they were designed for and badly on everything else, with measurements showing each specialist reaching near-peak throughput on its own kernel and as little as two percent of peak averaged across the others; this paper (Tsinghua) refuses the accelerator-per-operation approach by asking what all these operations have in common, and finds that if every tensor — dense or sparse — is described as a tree of nested index lists, then every one of these computations becomes the same two operations on trees, matching indices that appear in both and combining those that appear in either; building an instruction set around that gives near-best performance on every kernel rather than best on one.
The argument in one glance
-
Problem
Machine learning is now full of mostly-zero computations, in many different shapes
Two trends made computations where most values are zero central to machine learning. Models are deliberately PRUNED — many weights set to zero to shrink the model, and increasingly the same treatment is applied to intermediate results inside transformers. And a growing share of data is naturally almost empty, such as the point clouds produced by vehicle sensors or the connections in a social or molecular graph. General processors handle this badly, since their arithmetic units assume dense data and their execution model assumes regular access, so they spend effort multiplying zeros and stall on irregular lookups. But the difficulty is not one problem, it is many — multiplying a sparse matrix by a dense one, multiplying two sparse matrices, sparse convolution, sampled dense products — each with a different dataflow, and with densities ranging from a hundredth of a percent to ninety percent.
-
What people did
Build a dedicated accelerator for the operation you care about
The established response is to design purpose-built hardware. Choose the operation that dominates your workload, build datapaths and compute units shaped exactly around its access pattern, and get very large gains over a general processor. This is well-trodden and effective — the literature contains accelerators tuned for sparse matrix multiplication, for sparse-dense products, for tensor decompositions, each excellent at what it was built for.
-
Why it fell short
Each specialist collapses on everything else
The measurements are stark. Comparing several accelerators across four different sparse kernels, each reaches close to peak throughput on its own kernel and far below on the rest, giving averages across the set as low as two percent of the best achievable. The reasons are structural rather than incidental. One sparse-matrix accelerator has a fixed datapath and must feed dense inputs through machinery designed for compressed data, which is pure overhead. A tensor-core design optimized for dense multiplication must read and multiply every value including the zeros. One accelerator aimed at general sparse tensor algebra supports only a single iteration order, which makes it lose to kernel-specific designs. So a system needing several of these operations must carry several accelerators, or accept poor performance on most of its work.
-
This paper's idea
Find the abstraction under which all of them are the same computation
This paper (Tsinghua and Shanghai Jiao Tong — Zhong, Zhu, Dai and colleagues) refuses the accelerator-per-operation approach by asking what these operations share. Two existing ideas combine to answer it. Represent every tensor as a SPARSE FIBER TREE, a nested structure of index lists that expresses dense and compressed formats equally, so one representation covers the whole density range. Then write every operation in EINSTEIN SUMMATION, the compact notation stating which indices are multiplied together and which are summed away. Applying the second to the first shows that all of these computations reduce to the same handful of operations on trees — walking them, JOINING subtrees whose indices appear in both operands, and MERGING subtrees whose indices appear in either. An instruction set is then built around fibers rather than around any particular kernel, with dense and sparse variants of each instruction, and an architecture driven by those instructions. The result is near-best performance on every kernel instead of best on one, with 5.4 times the energy efficiency of a graphics processor.
Why this problem is worth solving
The workload being targeted has grown from a niche into a large share of machine
learning, so it is worth being clear about what it consists of.
A TENSOR is
just a multidimensional array of numbers — a vector in one dimension, a matrix
in two, and more beyond. SPARSE TENSOR ALGEBRA is arithmetic on tensors where
most entries are zero, which reaches machine learning from two directions.
PRUNING deliberately sets many model weights to zero to shrink a model without
much accuracy loss, and the same treatment is now applied inside transformers to
attention and feature maps. Separately, some data is naturally almost empty —
the point clouds produced by vehicle sensors, or the connection patterns in
social, circuit and molecular graphs that graph neural networks operate on. What
makes this hard to accelerate is that it is not one computation but a family.
Multiplying a sparse matrix by a dense one is a different dataflow from
multiplying two sparse matrices, which differs again from sparse convolution or
from taking a sampled subset of a dense product. And the DENSITY varies
enormously across applications, from around a hundredth of a percent to ninety
percent, so what is worth compressing in one setting is pure overhead in
another. Non-zeros are also often distributed unevenly, which unbalances the
work
The way out is a representation general enough to describe all of it.
A SPARSE FIBER TREE describes a
tensor as a nested structure. Expand the tensor along its first dimension into
sub-tensors, expand each of those along the second dimension, and so on, giving
a tree whose levels correspond to dimensions. Each node, called a FIBER, holds a
list of coordinates saying which entries actually exist at that level, plus
either pointers to child fibers or, at the bottom, the values themselves. Its
important property is that it describes DENSE and COMPRESSED storage equally —
a dense fiber simply has every coordinate present — so one representation spans
the whole density range rather than forcing a choice. EINSTEIN SUMMATION is a
compact notation for tensor operations that states which indices are shared
between operands and which are summed away. Written this way, matrix
multiplication says that entries sharing an index are multiplied and the results
summed over that index. The notation describes relationships between DIMENSIONS,
and in a fiber tree the dimensions are exactly the levels — which is what lets
one be applied to the other
What people did before, and where it broke
- General processors. Graphics and central processors run all of these operations, which is their virtue. But their arithmetic units target dense data and their execution model assumes many lanes doing the same thing to regular data, so irregularly placed non-zeros cause wasted multiplications of zero, redundant branching and synchronisation overhead.
- Instruction-set extensions for streams on a central processor. Adding stream operations to a general processor keeps full programmability. But the surrounding architecture offers limited parallelism, and one such design is reported at 2.4 times worse than specialised accelerators.
- Many lightweight threads. Another processor-side approach hides irregular latency with numerous threads, but without dedicated instructions, registers or units for sparse data it needs a great many instructions per unit of work.
- Kernel-specific accelerators. The dominant approach, and genuinely effective — but each is built around one operation. One supports only sparse-dense multiplication; others handle sparse-sparse but not multidimensional tensors or sampled products; one supports several sparse-dense operators but cannot do the others sparsely.
- Generators for streaming accelerators. Recent work describes dataflow abstractly and can express many sparse computations, which is real progress on the modelling side. But it emits a dedicated datapath per kernel, so the inflexibility reappears in the generated hardware.
- The gap. Everyone either kept full generality and paid for it in efficiency, or bought efficiency by fixing one operation into silicon. Nobody had found the abstraction under which the whole family is a single computation, which is what would let one piece of hardware serve all of it. That is the gap FEASTA fills.
How one instruction set covers the whole family
Describe every tensor as a tree, express every operation as index matching, then build for that
-
Each accelerator is excellent at one kernel and poor at the rest
Purpose-built designs reach near-peak throughput on the operation they target and far less on others, averaging as little as two percent of the best across a set of four kernels, because their datapaths encode one dataflow and one assumed density.
-
Represent every tensor the same way new
Describe each tensor as a nested tree of index lists, where each level corresponds to a dimension and each node lists the coordinates present there plus pointers to its children or, at the bottom, values. The same structure expresses dense and compressed storage, so one representation spans densities from a hundredth of a percent to ninety.
-
Express every operation as index relationships new
Write each computation in the notation that states which indices are shared between operands and which are summed away. Because that notation talks about dimensions, and the tree levels are dimensions, applying one to the other reveals what the operations have in common.
-
Discover that everything is joining and merging new
The analysis shows the whole family reduces to walking these trees and performing two operations on them — joining subtrees whose coordinates appear in both operands, which is what multiplication over a shared index requires, and merging subtrees whose coordinates appear in either, which is what summation requires.
-
Build an instruction set around fibers new
Seven kinds of instruction operate on fibers rather than on any particular kernel, held in vector registers that each contain many fiber elements so one instruction processes several at once. Every instruction has variants for dense and compressed data, so the same program shape serves both.
-
Drive configurable units from those instructions new
Rather than a fixed datapath, the architecture is instruction-driven with configurable function units, so the dataflow follows the program rather than the silicon. Instruction packing and multiple threads keep the units busy despite unevenly distributed non-zeros.
The idea
Ask what the diverse things have in common before building hardware for any of them. The field had been answering a question of the form “how do I accelerate this operation”, and getting good answers that did not compose. The reframing here is to ask what sparse matrix multiplication, sparse-sparse multiplication, sparse convolution and sampled dense products all ARE, and the answer turns out to be the same computation viewed through different index patterns. Getting there requires two representational choices working together — a tree description that covers dense and compressed storage alike, and a notation that describes operations purely as relationships between dimensions. Applied to each other they expose the shared structure: matching indices present in both operands, and combining indices present in either. This is precisely the move the sparse-instruction-set page covered elsewhere on this site makes one level lower, where two workloads that look unrelated turn out to reduce to the same set operations on ordered lists — and the resemblance is not coincidental, since joining is intersection and merging is union, lifted from lists to trees.
Choose a representation that removes a decision rather than making it. The fiber tree earns its place by describing dense and compressed storage in the same shape, a dense fiber being simply one where every coordinate is present. That matters because density here spans four orders of magnitude, so any design that picks a format commits to a slice of the workload — which is exactly what makes the specialised accelerators fail outside their range, one of them forced to push dense inputs through machinery meant for compressed data. Because the representation is uniform, each instruction can have dense and sparse variants while the surrounding program keeps its shape, and the hardware need not choose in advance. Selecting a representation so that a distinction stops needing to be made is the same reify-the-right-thing discipline covered elsewhere on this site where changing what a number IS, rather than optimizing the circuits that process it, is what collapses the cost.
Trade peak on one kernel for competence on all of them, and say where you lose. The claim being made is deliberately not dominance. Under equal area the design is measurably WORSE than a tensor-core arrangement on dense matrix multiplication, because that design is simple and buys more parallelism per unit of silicon; it loses to another accelerator on large language models, where parallelism matters more and sparsity is lower; and a graphics processor achieves higher raw throughput on the denser kernels because it has far more resources, though at much greater area and power. What the paper claims is the average across a diverse set, where it is close to the best achievable everywhere rather than the best in one place, and 5.4 times more energy-efficient than a graphics processor overall. Reporting the cases where a design loses, and resting the argument on the aggregate instead, is the honest-evaluation discipline the site rewards throughout.
Multiplying two sparse matrices
One computation expressed as tree operations
How a sparse-sparse product becomes joining and merging. Numbers from the paper's evaluation.
Step 1 of 5
What the operation needs
Multiplying two sparse matrices means that for each output entry, the entries of the two inputs that share an index are multiplied and the results summed over that index. Most entries of both inputs are zero, so most of that work does not exist — the difficulty is finding which parts do.
the same description covers sparse-dense products, sparse convolution and sampled dense products, differing only in which indices are shared and which are summed densities across the evaluated datasets range from well under a thousandth to over half
Why it works
- Sparse tensor operations differ in dataflow and density → a datapath built for one encodes assumptions false for the others → which is why specialised accelerators average as little as two percent of best across a diverse set.
- A fiber tree describes dense and compressed storage in the same shape → so no format decision is baked into the hardware → letting one instruction set span densities from a hundredth of a percent to ninety.
- Einstein summation describes operations as relationships between dimensions, and tree levels are dimensions → applying one to the other exposes what the operations share → revealing that all of them are joining and merging subtrees.
- Multiplication over a shared index needs entries present in both operands, and summation needs entries present in either → those are exactly join and merge → so two tree operations suffice to express the whole family.
- Non-zeros are distributed unevenly, so units would otherwise idle → packing instructions and running multiple threads keeps them fed → which is what turns a flexible design into a fast one rather than merely a general one.
What it costs (trade-offs and scope)
- It gives up peak performance on individual kernels. Under equal area a tensor-core arrangement beats it on dense matrix multiplication, being simpler and therefore able to buy more parallelism per unit of silicon, and another accelerator beats it on large language models where sparsity is lower. The claim is the average, not dominance.
- A graphics processor still wins raw throughput on the denser kernels. It has far more computational resources, though at much larger area and power, which is why the comparison is made on efficiency rather than speed.
- It is a new instruction set, which is an adoption cost. Programs must be expressed in terms of fiber operations rather than existing libraries, and the paper accordingly includes a compilation flow — real work that a drop-in accelerator would not require.
- The advantage depends on the workload being genuinely diverse. A deployment that runs one operation at one density is better served by the specialist built for it; the argument only pays where several operations and densities coexist.
- Everything is evaluated in simulation with area and power models. Results come from modelling rather than fabricated silicon, and the equal-area comparisons in particular rest on those models being fair to competing designs.
The evaluation
FEASTA was compared against a graphics processor, a tensor-core design, several specialised sparse accelerators and a processor instruction-set extension, across dense matrix multiplication, sparse-dense multiplication, sparse-sparse multiplication and sampled dense products. Datasets spanned graph matrices, convolutional network weights and activations, and transformer workloads, with densities ranging from well under a thousandth to over half. Both raw performance and equal-area comparisons were reported, along with energy efficiency, an area breakdown, and model-level results rather than kernels alone.
Running the family of sparse tensor operations
| Property | Graphics processor | Kernel-specific accelerator | FEASTA |
|---|---|---|---|
| Operations supported | |||
| Density range handled | |||
| Average across four kernels | |||
| Energy efficiency | |||
| Where it loses |
Check yourself
Check your understanding
1. Purpose-built sparse accelerators reach near-peak on their own kernel but average as little as two percent of best across four kernels. Predict why the collapse is so severe.
2. The design describes every tensor as a nested tree of coordinate lists rather than choosing a storage format. Predict why that matters so much here.
3. Applying Einstein summation to the fiber tree reveals that every operation is joining and merging. Predict why exactly those two operations.
4. The paper reports being beaten by a tensor core on dense multiplication and by another accelerator on language models. Predict why including that strengthens the argument.
Sources
- FEASTA: A Flexible and Efficient Accelerator for Sparse Tensor Algebra in Machine Learning (ACM DL, DOI 10.1145/3620666.3651336) — ASPLOS 2024; published under a Creative Commons licence.
- Author PDF (NICS-EFC, Tsinghua University) — the full 18-page paper, read in full for this explainer.