Insum: Sparse GPU Kernels Simplified and Optimized with Indirect Einsums

Writing a fast GPU kernel for sparse data (matrices full of zeros you want to skip) is so hard it takes thousands of lines of expert CUDA and spawns whole research papers, and existing sparse compilers mostly target CPUs and mishandle the dense parts; this paper (MIT, Georgia Tech, and NVIDIA — Jaeyeon Won, Willow Ahrens, Joel Emer, Saman Amarasinghe) presents Insum, which rewrites a sparse computation into an "indirect einsum" — dense tensor operations plus gather/scatter indexing — so it can ride the mature dense-tensor GPU compiler, turning thousand-line kernels into one line while running faster.

The argument in one glance

Problem

Fast sparse GPU kernels are brutally hard to write, and the tools do not help

Sparse computations are everywhere — machine learning on graphs, scientific simulations — and they share a defining feature: most of the values are zero. Storing all those zeros, and doing arithmetic on them (anything times zero is zero), wastes memory and compute, so developers use sparse formats like COO or CSR that store only the nonzeros and their coordinates. GPUs are the workhorse of high-performance computing, so there is strong demand to run these sparse workloads fast on GPUs. But writing an efficient sparse GPU kernel is notoriously hard. Unlike dense computation, sparse operations involve indirect memory accesses (you must look up where the nonzeros are), irregular data dependencies, and tricky load balancing, and on top of that the programmer must hand-manage a long list of GPU-specific optimizations — shared memory, vectorization, avoiding memory-bank conflicts, using the Tensor Core matrix units, coalescing memory accesses. The result is specialized, hand-optimized kernels that are enormous and hard to maintain: a state-of-the-art sparse-convolution library runs to over 4,000 lines of CUDA, so intricate that its techniques have spawned at least five separate research papers. That much effort, per operation, is a serious barrier — and it recurs endlessly as new sparse workloads appear.
What people did

Use a sparse tensor compiler to generate the kernel for you

Sparse tensor compilers exist precisely to spare people this pain. They let a developer express a computation as if it were on dense tensors, using a format-agnostic Einsum — a compact notation like "C equals A times B, summed over the shared index" that says what to compute without saying how it is stored — plus a separate declaration of each tensor's sparse storage format (COO, CSR, and so on). The compiler then automatically generates an optimized implementation for that format. This cleanly separates the math from the storage, so in principle a user writes the einsum once and the compiler handles the messy format-specific code.
Why it fell short

Existing sparse compilers are built for CPUs and neglect the dense parts

In practice, existing sparse compilers fall short on GPUs in two ways. First, they were designed mainly for CPUs. Much of their machinery targets sparse-sparse kernels — operations where several sparse tensors interact, requiring the compiler to find nonzeros at intersecting or combined coordinates. That produces complex, branchy control flow that suits a CPU but maps poorly onto a GPU's massively parallel, regular execution model, so these compilers rarely emit high-performance GPU code. Second, and just as important, many real GPU sparse workloads are actually sparse-dense: only one operand is sparse and the rest are dense (think a sparse matrix multiplied by a dense one). The valuable, compute-heavy work in these is the dense part — but existing sparse compilers, focused on the sparse control flow, fail to optimize the dense computation effectively, leaving most of the GPU's performance on the table. So the tools meant to make sparse GPU programming easy either produce slow code or ignore the very part where the speed lives. What was missing was a way to express sparse computation that let the dense, high-performance GPU compilers do what they are already excellent at.
This paper's idea

Rewrite sparse computation as an "indirect einsum" over dense tensors

Insum's idea is to stop treating sparse computation as something needing its own special compiler, and instead re-express it as dense tensor operations plus indirect indexing — a form the mature dense GPU compilers already handle superbly. It starts from a format-agnostic einsum over sparse tensors and rewrites it into a format-conscious indirect einsum, which bakes the format information directly into the notation by mapping the sparse data and its metadata (the coordinates) onto dense tensor operations through indirect indexing. For example, an elementwise multiply of a sparse matrix in COO format becomes an indirect einsum that says: take the array of nonzero values, gather the matching elements of the dense operand from the coordinates stored in the sparse tensor's index array, multiply, and scatter the results to the output at those same coordinates. The sparse structure has become gathers and scatters over dense arrays. Insum, the compiler, then lowers these indirect einsums into high-performance GPU kernels by reusing an existing dense tensor compiler — it targets the PyTorch compiler, extended to better support Tensor Core-enabled indirect einsums, with a pattern-matcher that emits direct Tensor Core matrix operations (no hand-written templates) and a codegen technique called Lazy Broadcasting to speed up Tensor Core use. To make the sparse data fit these dense operations cleanly, Insum introduces two fixed-length sparse formats, GroupCOO and BlockGroupCOO, that partition nonzeros into fixed-size groups (padding as needed), striking a balance between COO's irregularity and the heavy padding of fully-padded formats, and extending naturally to block-sparse layouts that Tensor Cores love. The upshot: across a range of sparse GPU applications, Insum achieves 1.14 to 3.81 times speedups over hand-written implementations while cutting lines of code by 202 to 4491 times — often expressing a whole kernel in a single line.

Why this problem is worth solving

Sparse computation is pervasive and GPU performance is precious, so a way to get fast sparse GPU kernels without heroic hand-coding would unlock a great deal of value.

Sparse data shows up across machine learning and science — graph neural networks, recommendation models, physical simulations — and running it efficiently on GPUs is where a lot of real performance is won or lost. But today, getting that performance means either using a narrow, hand-written library that exists only for a specific operation, or writing thousands of lines of expert CUDA yourself. Both are expensive: the hand-written libraries are hard to maintain and do not generalize, and rolling your own kernel is out of reach for most practitioners. This is why new sparse GPU kernels are a continuous stream of research papers rather than a solved problem. A compiler that turns a one-line, high-level description into a kernel that matches or beats those hand-written efforts would collapse that cost dramatically, letting a much wider set of people run sparse workloads fast, and letting experts spend their effort on new algorithms instead of re-deriving the same GPU optimizations. Because the speedups and the code reductions are both large, the payoff is not incremental — it is the difference between sparse GPU programming being a specialist craft and being something a compiler just does.

The key realization is that most of a sparse GPU computation is really dense work wearing an irregular costume.

The reason existing sparse compilers struggle on GPUs, and the reason Insum succeeds, come from the same observation: the hard, valuable part of a sparse-dense GPU kernel is dense arithmetic, and the sparsity is mostly a matter of which elements to fetch and where to put results. Traditional sparse compilers treat the sparsity as the essence and build elaborate control flow around finding and intersecting nonzeros — which is exactly what does not run well on a GPU and exactly what buries the dense computation. Insum inverts this: it treats the computation as dense tensor operations and expresses the sparsity purely as indirect indexing — gathers that pull the right dense elements in and scatters that push results out. Once the computation is in that form, it is no longer a special sparse problem at all; it is a dense tensor program with some indexing, and the enormous, mature investment in dense GPU compilers — loop scheduling, Tensor Core exploitation, memory optimization — applies directly. This is why the reframing is the whole game: it moves sparse computation into the world where high-performance tooling already lives, rather than trying to rebuild that world for sparsity. The fixed-length formats then exist to make the indirect-dense form regular enough that those dense tools, and especially the Tensor Cores, can run at full speed.

What people did before, and where it broke

Hand-write a specialized CUDA kernel per sparse operation. Craft an expert implementation with all the GPU optimizations by hand. Where it broke. It takes thousands of lines (a sparse-convolution library exceeds 4,000), is hard to maintain and generalize, and must be redone for each new workload.
Use a sparse tensor compiler built for CPUs. Express the einsum and format, and let the compiler generate code. Where it broke. Its machinery targets sparse-sparse intersection and union with branchy control flow that fits CPUs, so it rarely produces high-performance GPU code.
Let the sparse compiler handle sparse-dense workloads. Apply the same compiler to operations where only one operand is sparse. Where it broke. Focused on the sparse control flow, it fails to optimize the dense computation — which is where most of the GPU performance actually is.
Store nonzeros in COO, or pad every row to equal length (ELL). Pick a standard sparse format. Where it broke. COO is irregular and scatter-heavy, while fully padding to the longest row wastes huge memory when the nonzero distribution is uneven — neither fits dense GPU execution well.
The gap. No approach expressed sparse computation so that the dense, high-performance GPU compilers could optimize it directly, with a format regular enough to use Tensor Cores.

How Insum works

Turning sparse computation into dense tensor programs with indirect indexing

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

The idea

Choose a sparse format co-designed with how the computation will run. Insum’s GroupCOO and BlockGroupCOO are not generic; they are fixed-length formats built so the sparse data lays out naturally for dense operations and Tensor Cores, trading a little padding for regularity. Co-designing the sparse storage format together with the way the kernel executes, rather than picking a format and a schedule separately, is the same approach the work on workload-aware co-optimization of sparse format and schedule (WACO) covered elsewhere on this site takes, treating the format as part of the performance problem rather than a fixed input. Insum chooses grouping so the resulting indirect-dense form runs well, which is what makes the whole reframing fast rather than merely elegant.

Build on a mature compiler infrastructure instead of a bespoke one. Rather than write yet another sparse code generator, Insum lowers its indirect einsums to an existing dense tensor compiler and inherits all its GPU optimization. Generating high-performance GPU tensor code by targeting a powerful intermediate representation and compiler rather than reinventing that machinery is the same principle the work on an IR for optimized tensor computations on GPUs (Graphene) covered elsewhere on this site is built on, investing in the compilation infrastructure that many computations can share. Insum’s contribution is to bring sparse computation into that infrastructure by reshaping it into a form the dense compiler already handles.

Regularize irregular sparse work so specialized dense hardware can run it. The fixed-length grouping exists to turn the ragged structure of sparsity into uniform blocks that the GPU’s parallel execution and Tensor Core units can chew through efficiently. Restructuring an inherently irregular sparse computation into a regular form suited to the hardware’s execution model is the same idea the work on stream-ISA processor specialization for sparse computation (SparseCore) covered elsewhere on this site develops, reshaping sparse work to fit the machine. Insum does it in software and format design, making the sparse data dense-shaped enough that ordinary dense GPU machinery, including matrix units, applies.

Following an SpMM through Insum

Compiling a sparse-times-dense matrix multiply into a fast GPU kernel

A trace, drawn from the paper, of how Insum turns a one-line sparse einsum into an optimized GPU kernel.

Step 1 of 5

Write the computation as a format-agnostic einsum

The user writes sparse-dense matrix multiply as an einsum — output equals the sparse matrix A times the dense matrix B, summed over the shared index — saying only what to compute, not how A is stored. This is a single high-level line.

The math is decoupled from A's storage format.

Why it works

Indirect indexing turns sparsity into dense operations. Sparse structure normally demands special branchy control flow → but expressing it as gathers and scatters over dense arrays → so the computation becomes an ordinary dense tensor program the GPU compilers handle well.
Reusing a dense compiler inherits its whole optimization arsenal. Building sparse-specific GPU codegen is enormous and perennial → but lowering indirect einsums to a mature dense compiler → so loop scheduling, memory coalescing, and Tensor Core use come for free rather than being reinvented.
Fixed-length grouping makes the data hardware-friendly. COO is irregular and ELL over-pads → but partitioning nonzeros into fixed-size groups with modest padding → so the sparse data is regular enough for parallel dense execution and Tensor Core matrix units.
Pattern-matching to Tensor Cores captures the dense performance. The valuable work in sparse-dense kernels is dense matrix multiply → but recognizing it and emitting direct Tensor Core operations → so Insum optimizes exactly the part existing sparse compilers neglected.
One notation covers many applications. Each hand-written library serves only its one operation → but indirect einsums express elementwise, matrix multiply, tensor products, and convolution alike → so a single compiler-based approach replaces many separate specialized codebases.

What it costs (trade-offs and scope)

Fixed-length grouping pays some padding. GroupCOO and BlockGroupCOO add padding to make groups uniform; the design keeps this far below ELL’s full-row padding, but on very unevenly distributed nonzeros the padding is real overhead, and the group size is a parameter that must be chosen for the data.
It leans entirely on a dense compiler’s reach. Insum’s performance is bounded by what the underlying dense tensor compiler (here the PyTorch compiler) can do; computations it cannot express as indirect-dense programs, or that the dense compiler optimizes poorly, fall outside the sweet spot.
It targets sparse-dense, not the hardest sparse-sparse cases. The approach shines where the heavy work is dense and the sparsity is indexing; fully sparse-sparse kernels, whose essence is intersecting nonzero patterns, are the traditional compilers’ domain and are not the focus here.
Tensor Core benefits assume block structure. The largest wins come when the computation maps to Tensor Core matrix operations, which BlockGroupCOO is built to enable; sparse patterns that do not form usable blocks get less from that path.
Reported gains are application- and data-dependent. The 1.14 to 3.81 times speedups and 202 to 4491 times code reductions span specific applications (matrix multiply, tensor product, convolution) and inputs; the exact numbers depend on the operation, the sparsity pattern, and the hardware.

The evaluation

Producing high-performance sparse GPU kernels

Property	Hand-written CUDA	CPU-oriented sparse compiler	Insum
Effort per kernel
GPU performance
Dense-part optimization
Tensor Core use
Generality across operations

A comparison of ways to produce sparse GPU kernels. By rewriting a format-agnostic einsum into an indirect einsum (dense tensor operations plus gather/scatter indexing), lowering to a dense tensor compiler with Tensor Core support, and using the fixed-length GroupCOO and BlockGroupCOO formats, Insum matches or beats hand-written kernels — 1.14 to 3.81 times speedups — while reducing code by 202 to 4491 times across sparse matrix multiply, tensor product, and convolution. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (the authors’ arXiv copy, 2510.17505, of the ASPLOS 2026 paper). The described system is the paper’s: Insum expresses sparse computations by starting from format-agnostic einsums over sparse tensors and rewriting them into format-conscious indirect einsums, which encode format information by mapping sparse data and metadata onto dense tensor operations through indirect indexing (for example, an elementwise multiply in COO becomes a gather of the dense operand at the sparse tensor’s stored coordinates, a multiply with the nonzero values, and a scatter to the output). The Insum compiler lowers these indirect einsums to GPU code by reusing a dense tensor compiler — targeting the PyTorch compiler, extended to better support Tensor Core-enabled indirect einsums — with pattern matching to emit direct Tensor Core operations (removing hand-written templates) and a codegen technique called Lazy Broadcasting. It introduces two fixed-length sparse formats, GroupCOO and BlockGroupCOO, that partition nonzeros into fixed-size groups (with padding), balancing COO against ELL and extending to block-sparse layouts. The paper reports 1.14 to 3.81 times speedups across a range of sparse GPU applications (including sparse matrix multiply, tensor product, and convolution) while reducing lines of code by 202 to 4491 times compared with hand-written implementations, and provides source code at github.com/nullplay/IndirectEinsum. The einsum and format background above is standard sparse-computation context provided to make the approach intuitive. The step-by-step walkthrough is an illustration of the described mechanism. Exact rewriting rules, the Tensor Core and Lazy Broadcasting techniques, the format details, and the full evaluation should be read from the paper.

Background

Why so much systems progress comes from reframing a hard problem into an easy one's shape

It helps to see Insum within a broad pattern: some of the most effective systems work does not build a better tool for a hard problem, but reshapes the hard problem until an existing, powerful tool applies. Sparse computation on GPUs looked like it needed its own dedicated compiler, because its irregularity is so unlike the regular, dense math that GPUs and their compilers are built for. The traditional response was to construct elaborate sparse-specific machinery — which is exactly why it kept underperforming on hardware designed for dense regularity. Insum’s move is the reframing: recognize that a sparse-dense computation is dense arithmetic plus indexing, express it that way, and inherit the entire mature ecosystem of dense tensor compilation instead of rebuilding it. This is a recurring and underrated strategy — the leverage comes from choosing a representation that connects your problem to where the tooling already is, rather than porting the tooling to your problem. The fixed-length formats are the finishing touch that makes the reframed problem not just expressible but fast, by keeping it regular enough for the dense machinery to run at full tilt. This effort to raise sparse and tensor computation to a high-level notation and let a compiler deliver hardware performance is the same terrain the work on a task-mapping programming paradigm for deep-learning tensor programs (Hidet) covered elsewhere on this site occupies, closing the gap between a clean abstraction and low-level speed. Insum’s contribution is to show that, with indirect einsums and fixed-length formats, sparse GPU kernels can be written in a single line and still match or beat thousand-line hand-tuned code — by borrowing the dense world’s power rather than reinventing it for sparsity.

If you remember only three things

1. Sparse computations (graph ML, scientific simulation) store only nonzeros to avoid wasting memory and compute on zeros, and there is strong demand to run them fast on GPUs — but writing efficient sparse GPU kernels is notoriously hard, requiring indirect memory access, irregular dependencies, load balancing, and hand-managed GPU optimizations (shared memory, Tensor Cores, coalescing). Hand-written kernels run to thousands of lines of CUDA (a sparse-convolution library exceeds 4,000, spawning five research papers). Existing sparse compilers do not fix this on GPUs: they are built for CPUs and their intersection/union control flow, rarely emit fast GPU code, and neglect the dense portions of the sparse-dense operations that dominate real GPU workloads.
2. Insum re-expresses sparse computation as dense tensor operations plus indirect indexing. It rewrites a format-agnostic einsum into a format-conscious indirect einsum that maps the sparse values and coordinate metadata onto dense operations via gather and scatter (for example, elementwise multiply in COO gathers the dense operand at the sparse tensor's stored coordinates, multiplies, and scatters back). Because the result is a dense tensor program, Insum lowers it to a mature dense compiler (the PyTorch compiler), inheriting its GPU optimization, and extends it to emit direct Tensor Core operations via pattern matching plus a Lazy Broadcasting codegen technique. To keep the data regular enough for dense execution and Tensor Cores, it adds two fixed-length formats, GroupCOO and BlockGroupCOO, that partition nonzeros into fixed-size groups with modest padding.
3. Across a range of sparse GPU applications (sparse matrix multiply, tensor product, convolution), the paper reports Insum achieves 1.14 to 3.81 times speedups over hand-written implementations while reducing lines of code by 202 to 4491 times — often a single line versus hundreds or thousands. The trade-offs: fixed-length grouping pays some padding and needs a group-size choice, performance is bounded by the underlying dense compiler, the approach targets sparse-dense rather than the hardest sparse-sparse kernels, and the biggest Tensor Core wins assume usable block structure. The reported numbers depend on the operation, sparsity pattern, and hardware; the source code is public.

Check yourself

Check your understanding

1. Why do existing sparse tensor compilers produce poor GPU code for common sparse workloads?
2. What is an "indirect einsum," and how does it let Insum reuse dense compilers?
3. Why does Insum introduce the fixed-length GroupCOO and BlockGroupCOO formats?
4. What does Insum achieve, and what should be kept in mind about its scope?

Sources

The paper is “Insum: Sparse GPU Kernels Simplified and Optimized with Indirect Einsums” by Jaeyeon Won, Willow Ahrens, Joel S. Emer, and Saman Amarasinghe (Massachusetts Institute of Technology, Georgia Institute of Technology, and NVIDIA), published at ASPLOS 2026, DOI 10.1145/3779212.3790176. It is available on arXiv as 2510.17505, and the source code is public at github.com/nullplay/IndirectEinsum.

This explainer is written from the paper’s full text (the authors’ arXiv copy). Insum expresses sparse computations by rewriting format-agnostic einsums over sparse tensors into format-conscious indirect einsums, which encode format information by mapping sparse data and metadata onto dense tensor operations through indirect indexing (gather-multiply-scatter). The Insum compiler lowers these indirect einsums to GPU code by reusing a dense tensor compiler (targeting the PyTorch compiler, extended for Tensor Core-enabled indirect einsums), with pattern matching that emits direct Tensor Core operations and a Lazy Broadcasting codegen technique. It introduces two fixed-length sparse formats, GroupCOO and BlockGroupCOO, that partition nonzeros into fixed-size groups (with padding), balancing COO against ELL and extending to block-sparse layouts. The paper reports 1.14 to 3.81 times speedups across sparse GPU applications (sparse matrix multiply, tensor product, convolution) while reducing lines of code by 202 to 4491 times versus hand-written implementations. Numbers are the paper’s own; exact mechanisms and full results should be confirmed in the paper.