Prism: Symbolic Superoptimization of Tensor Programs
Mengdi Wu, Xiaoyu Jiang, Oded Padon, Zhihao Jia · 2026
Read Prism: Symbolic Superoptimization of Tensor Programs by Mengdi Wu, Xiaoyu Jiang, Oded Padon, Zhihao Jia (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-15272.txt.
Introduction
Wu and three colleagues build Prism, a symbolic superoptimizer for tensor programs, which encode machine-learning workloads as operator graphs. Prism builds symbolic graphs covering whole program families, cuts surely wasteful regions using algebra and hardware rules, then tunes real versions. On five language-model workloads it runs up to 2.2 times faster than the best superoptimizers and 4.9 times faster than compiler methods.
Catalog record
| CREATOR | Mengdi Wu, Xiaoyu Jiang, Oded Padon, Zhihao Jia |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65429 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.15272
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Prism: Symbolic Superoptimization of Tensor Programs Mengdi Wu, Xiaoyu Jiang, Oded Padon, Zhihao Jia Abstract . This paper presents Prism, the first symbolic superoptimizer for tensor programs. The key idea is sGraph, a symbolic, hierarchical representation that compactly encodes large classes of tensor programs by symbolically representing some execution parameters. Prism organizes optimization as a two-level search: it constructs symbolic graphs that represent families of programs, and then instantiates them into concrete implementations. This formulation enables structured pruning of provably suboptimal regions of the search space using symbolic reasoning over operator semantics, algebraic identities, and hardware constraints. We develop techniques for efficient symbolic graph generation, equivalence verification via e-graph rewriting, and parameter instantiation through auto-tuning. Together, these components allow Prism to bridge the rigor of exhaustive search with the scalability required for modern ML workloads. Evaluation on five commonly used LLM workloads shows that Prism achieves up to 2.2 × 2.2\times speedup over best superoptimizers and 4.9 × 4.9\times over best compiler-based approaches, while reducing end-to-end optimization time by up to 3.4 × 3.4\times . 1. Introduction Efficient execution of ML models on GPUs is fundamental to modern AI applications. Today’s ML systems generally express computations as tensor programs , typically represented as directed acyclic graphs (DAGs), where nodes correspond to tensor operators and edges denote tensors (i.e., multi-dimensional arrays). Most existing ML systems optimize tensor programs through transformation rules and scheduling templates manually designed by domain experts. Systems such as TensorFlow, TensorRT, and TVM incorporate hand-crafted graph rewrite rules and operator fusion heuristics ( 1 ; 25 ; 5 ) , while vendor-provided kernel libraries such as cuDNN and cuBLAS offer highly optimized implementations for a fixed set of operators ( 7 ; 8 ) . Although effective for widely used operations and models, this paradigm has two fundamental limitations. First, it requires substantial engineering effort to support new operators or hardware targets. For example, adapting optimized kernels such as FlashAttention ( 9 ) to a new GPU architecture generally requires months of manual tuning and engineering. Second, manually designed rules explore only a limited portion of the optimization space. Human intuition is inherently insufficient to capture the combinatorial interactions among algebraic transformations, data layouts, and hardware-specific scheduling decisions. Superoptimization has emerged as a promising paradigm for automatically discovering fast tensor programs without relying on manually specified rules. Originating from the compiler literature, superoptimization explores (exhaustively or heuristically) a search space of candidate programs and retains those that are both functionally equivalent to the original and empirically faster. TASO ( 14 ) pioneered this approach for tensor programs by automatically generating graph substitutions and then applying them to optimize tensor programs: it enumerates small computation subgraphs over a predefined operator set, identifies equivalent pairs via a combination of random testing and formal verification, and applies the generated transformation to optimize the target program using a cost-guided search. Mirage ( 33 ) applies superoptimization across multiple levels of the GPU execution hierarchy through \mu Graphs, a unified representation that captures optimizations at the kernel, thread-block, and thread levels. This multi-level search enables coordinated algebraic and scheduling transformations, including the synthesis of entirely new custom kernels beyond the reach of single-level approaches. Recently, large language models (LLMs) have been used to generate optimized GPU kernels ( 30 ; 29 ) . More broadly, AlphaEvolve has been proposed as a general-purpose superoptimizer that leverages LLMs to guide the search ( 19 ) . It uses an evolutionary framework in which LLMs iteratively propose and refine code candidates that are validated by automated evaluators. In a variety of well-defined tasks, AlphaEvolve demonstrates that LLM-guided search can discover optimizations surpassing both human-engineered and prior automated solutions. However, its applicability to optimizing tensor programs has not been explored yet. While enumeration -based superoptimizers like TASO and Mirage achieve strong performance, their reliance on exhaustive search introduces a fundamental scalability bottleneck: the number of candidate programs grows combinatorially with the number of operators and levels in the execution hierarchy, making exhaustive enumeration impractical for large or deeply nested programs. On the other hand, sampling -based superoptimizers such as AlphaEvolve use learned priors to guide the search, enabling exploration over substantially larger spaces. However, these methods treat the optimization landscape as largely unstructured, which can lead to unstable search behavior and provides limited guarantees on coverage or completeness of the explored program space. We introduce Prism, the first symbolic superoptimizer for tensor programs. Rather than enumerating concrete candidate programs via brute-force enumeration or stochastic sampling, Prism organizes the search space into a two-level hierarchy. At the upper level, it constructs a symbolic graph representation, called sGraph, which compactly encodes entire families of tensor programs; at the lower level, each sGraph is instantiated into many concrete implementations. This symbolic formulation enables Prism to explore substantially larger search spaces and discover higher-quality optimizations compared to prior enumeration- and sampling-based approaches for two key reasons. First, sGraph encodes operator semantics, algebraic identities, and hardware constraints as symbolic expressions, allowing Prism to prune provably suboptimal regions of the search space before materializing concrete programs. This structured pruning enables scalability to optimization problems that are intractable for exhaustive enumeration. Second, Prism preserves optimality guarantees: the pruning process is sound and does not eliminate optimal solutions. This property fundamentally distinguishes symbolic superoptimization from prior sampling-based approaches. Overall, Prism bridges the rigor of exhaustive search and formal verification with the scalability requirements of modern ML workloads. Symbolic graph representation. A key idea of Prism is sGraphs, a symbolic, hierarchical graph representation of tensor programs. Unlike conventional representations that fix execution parameters (e.g., grid dimensions, block dimensions, and tensor-to-thread mappings) to concrete values, Prism encodes these attributes symbolically while instantiating only the high-level computational structure. This design allows a single sGraph to represent a large class of related programs, enabling symbolic reasoning over the optimization space and more efficient exploration. sGraph generation. Given an input tensor program, Prism enumerates candidate sGraphs whose instantiations may be functionally equivalent to the target program. A key challenge is to prune the search space both effectively (i.e., eliminating a large fraction of invalid candidates) and efficiently (i.e., with minimal overhead). To this end, we introduce two complementary pruning techniques. Symbolic dimension matching ensures compatibility of operator dimensions when expressed as symbolic expressions, while symbolic expression pruning extends the abstract expression checking from previous work ( 33 ) to the symbolic setting. Together, these techniques significantly reduce the search space and enable Prism to scale to workloads where concrete enumeration becomes intractable (§ 3 ). sGraph verification. For each candidate sGraph, Prism must verify functional equivalence with the input program without committing to concrete parallelization parameters. Prior work relies on random testing, which requires fixed tensor shapes and is therefore incompatible with symbolic representations. Instead, Prism encodes both the input program and the candidate sGraph as expressions over a set of predefined operators and performs equivalence checking using e-graphs ( 31 ) under a set of algebraic axioms. These axioms capture the mathematical properties of supported operators and their interaction with parallelization, enabling verification of symbolic graphs independent of concrete parameter values (§ 4 ). sGraph instantiation. For each verified sGraph, Prism instantiates the remaining symbolic parameters to produce optimized