In 1916, Albert Einstein introduced a notation in his paper on general relativity that omitted the indices of tensor operations. If the same index appears twice, the summation over that index is implied. This single convention eliminates lines upon lines of summation symbols. Today, this "Einstein summation convention" is built into PyTorch, TensorFlow, and NumPy as Einsum (Einstein summation), and has become a standard tool for expressing matrix and tensor operations in deep learning with a single line of code.
The advantage of Einsum is its conciseness. Jaeyeon Won, a PhD student at MIT CSAIL, says, "It requires fewer lines of code." But this conciseness comes at a cost. Einsum doesn't know which parts of an array are zero. It dutifully executes operations on every single element. GPUs repeat, billions of times over, a fact every elementary school student knows: anything multiplied by zero is zero.
There are situations where this waste is unacceptable. Much of real-world data is represented as "sparse" arrays, where the vast majority of elements are zero: social network relationship graphs, rating matrices in recommendation systems, interaction matrices in molecular simulations. When Amazon's review data is represented as a tensor, it reaches $1.5 \times 10^{19}$ components (107 exabytes at 8 bytes each), but the number of non-zero components is only $1.7 \times 10^9$ (13 gigabytes). More than 99.99999999% of it is zero.
GPUs Were Built for a "Dense" World
Modern GPUs are optimized for operations on dense matrices—arrays with few zeros. NVIDIA's Tensor Cores process dense matrix multiplication with thousands of multiply-accumulate operations per clock cycle. When a sparse array is fed in as-is, the GPU performs the same operations on all elements including zeros, leaving most of the Tensor Core's capability spinning idle.
There have been previous attempts to solve this problem. In 2017, MIT's Fredrik Kjolstad, Saman Amarasinghe, and colleagues released TACO (Tensor Algebra Compiler). TACO was the first compiler that could automatically generate kernels (the smallest units of computation executed on a GPU or CPU) for arbitrary sparse and dense tensor operations. For sparse-times-sparse operations, its performance matches hand-optimized kernels.
However, TACO had structural limitations. First, it was primarily designed for CPUs and could not generate high-quality code for GPUs. Second, in mixed sparse-and-dense operations, it could not effectively optimize the dense portions. Won points out, "TACO is the best for sparse-times-sparse operations, but it is completely unsuited for sparse-times-dense multiplication."
As a result, in the field of sparse GPU computation, the brute-force approach of experts writing hundreds to thousands of lines of hand-crafted CUDA code has persisted. Such hand-crafted kernels are scattered throughout graph neural network libraries and scientific simulation codebases.
A Three-Stage Transformation from a One-Line Expression to a GPU Kernel
The solution proposed by the four researchers—Won, Ahrens, Amarasinghe, and Emer—was to "rewrite" Einsum itself. Their invention, Indirect Einsum, preserves the conciseness of standard Einsum while explicitly embedding sparse format metadata (positional information about non-zero elements) directly into the expression.
The mechanism operates in three stages. In the first stage, sparse arrays are converted into new fixed-length formats called GroupCOO and BlockGroupCOO. These formats store the values and coordinates of non-zero elements separately and are designed to match the GPU's regular memory access patterns. In the second stage, an Einsum expression that lacks format information is rewritten as a dense tensor operation using indirect indexing. For example, an expression like means: "extract the non-zero elements of A and B via an index array called AI, execute the operation as a dense computation, and write the result back to the designated position in C." In the third stage, the Insum compiler converts this Indirect Einsum into an FX graph (a functional intermediate representation of a PyTorch program) used by the PyTorch compiler, and generates optimized GPU kernels via TorchInductor.
The cleverness of this design lies in the fact that it requires no new hardware mechanism or compiler infrastructure dedicated to sparse computation. It can use existing dense matrix operation compilers (the PyTorch compiler and Tensor Cores) "as-is." The handling of sparsity is concentrated into a preprocessing stage of data transformation and indirect index insertion.
The research team also added extensions to the PyTorch compiler itself: pattern matching that recognizes Indirect Einsum expression patterns and directly generates Tensor Core instructions, and a code generation technique called Lazy Broadcasting that improves performance when using Tensor Cores.
4,491 Lines of Hand-Written Code Reduced to One
The research team evaluated Insum across a wide range of sparse GPU applications, including message passing in graph neural networks, sparse-dense matrix multiplication, and scientific simulation kernels. Here are the results.
| Metric | Hand-Optimized Kernel | Insum |
|---|---|---|
| Execution Speed | Baseline (1.0×) | 1.14×–3.81× faster |
| Lines of Code | Hundreds to thousands | One line of Indirect Einsum expression (202×–4,491× reduction) |
| Target Hardware | Individually optimized for specific GPUs | Any GPU supported by the PyTorch compiler |
| Sparse Format | Manually selected/implemented | GroupCOO / BlockGroupCOO auto-generated |
The maximum 3.81x speedup is the basis for TechXplore's headline describing it as "nearly 4x." The reduction in code lines ranges from 202x to 4,491x. There were cases where 4,491 lines of hand-written CUDA code were replaced with a single line of an Indirect Einsum expression.
Jason Ansel, a computer scientist at Meta, comments: "Sparse computation in graph neural networks and scientific simulations is notoriously difficult to execute efficiently on modern GPUs. Insum mitigates this problem in a way that enables faster execution with less code."
Comparison: Structural Differences Between Existing Approaches and Insum
| TACO (2017) | Hand-Written CUDA Kernel | Insum (2026) | |
|---|---|---|---|
| Primary Target | CPU | GPU | GPU |
| Sparse × Sparse | Strong | Possible but labor-intensive | Under expansion (not yet supported) |
| Sparse × Dense | Weak | Possible but labor-intensive | Strong |
| Tensor Core Utilization | None | Manually implemented | Auto-generated via pattern matching |
| Expertise Required | Medium (format description) | Extremely high | Low (write a one-line expression) |
| Code Volume | A few lines | Hundreds to thousands of lines | One line |
Automation and the "Sparse × Sparse" Wall
Emer states, "Today's computers are so good at dense computation that for this transformation (from standard Einsum to Indirect Einsum) to pay off, the proportion of zeros needs to be sufficiently high." For arrays with only a small number of zeros, the overhead of the transformation could outweigh the computational savings.
A more fundamental constraint is that this transformation is currently manual. Researchers must look at the sparse array's format and the structure of the operation, and hand-write the appropriate Indirect Einsum expression themselves. Amarasinghe says, "Automating this process is an ongoing research challenge."
Another unsolved problem is operations between two sparse arrays. While the transformation into Indirect Einsum can be defined relatively straightforwardly for combinations of sparse and dense, the procedure becomes dramatically more complex when both are sparse. Amarasinghe and Emer are currently working on this problem together with Ahrens and students at Georgia Tech.
Nine years have passed since TACO presented, in 2017, the universal framework that "any tensor operation can be compiled." Insum has filled a practical gap that this framework had missed: "sparse-times-dense operations on GPUs." The next gap to fill is automating the transformation and handling sparse-times-sparse operations. Once these two are addressed, even developers without sparse-computation expertise will be able to extract GPU performance from a sea of zeros.