The Fragile Compiler

Sparse tensor compilers translate high-level mathematical specifications — Einstein summation notation, tensor expressions — into optimized code that exploits sparsity patterns. The compiler synthesizes complex control flow: loop nesting, index transformations, storage format conversions. The specification is simple. The generated code is not.

TENSURE fuzzes two major sparse tensor compilers, TACO and Finch, with semantically valid test cases. The validity guarantee matters: a constraint-based generation algorithm ensures that 100% of synthesized kernels are well-formed (baseline grammar fuzzers achieve 3.3% validity). Every input is a legitimate program the compiler should handle.

TACO crashes or silently miscompiles on a majority of the valid test cases.

Not a few edge cases. Not obscure corner conditions. A majority. The compiler that produces code from valid specifications produces wrong code more often than right code under adversarial but legitimate inputs. The fragility is not at the edges but in the core.

The structural problem is that sparse tensor compilers are compilers that generate programs they do not verify. The compilation process is a complex synthesis: take a mathematical identity, choose a storage format, derive loop bounds, insert guards. Each step is locally reasonable. The interaction between steps is where correctness breaks down — a loop bound derived from one storage format assumption, applied under a different format’s iteration order, produces silent wrong answers.

The gap between specification simplicity and compilation complexity is where bugs live. The simpler the input language, the more the compiler must infer — and the more places inference can quietly go wrong.