Symbolic Superoptimization: Bridging Formal Verification and Scalable Tensor Program Optimization

Introduction

The efficiency of modern machine learning systems hinges on the quality of their tensor program implementations. Whether executing transformer inference on large language models or training deep neural networks, the underlying GPU kernels must exploit intricate hardware features. Memory hierarchies, thread cooperation patterns, and instruction level parallelism all demand careful orchestration. Historically, this optimization burden has fallen on human experts crafting hand tuned libraries such as cuDNN and cuBLAS, or compiler engineers developing heuristic transformation rules for systems like TVM and TensorFlow.

Recent years have witnessed the rise of superoptimization as an alternative paradigm. Rather than relying on predefined rules, superoptimizers automatically discover equivalent program variants through search. TASO pioneered this approach for tensor programs by enumerating graph substitutions and verifying equivalence through a combination of random testing and formal methods. Mirage extended this to multiple levels of the GPU execution hierarchy, enabling coordinated optimizations across kernels, thread blocks, and individual threads. Yet these enumeration based approaches face a fundamental scalability ceiling. As program size increases, the combinatorial explosion of concrete candidate programs renders exhaustive search intractable.

Concurrently, sampling based methods such as AlphaEvolve have emerged, leveraging large language models to propose optimizations within an evolutionary framework. While these approaches scale to larger spaces, they treat the optimization landscape as unstructured, offering limited guarantees regarding coverage or completeness. The field has thus faced a tension between the rigor of exhaustive search and the scalability required for modern workloads.

The paper Prism: Symbolic Superoptimization of Tensor Programs by Wu et al. proposes a resolution to this tension through symbolic reasoning. Prism introduces sGraph, a symbolic hierarchical representation that encodes entire families of tensor programs rather than individual concrete implementations. By separating symbolic graph construction from concrete instantiation, Prism enables structured pruning of suboptimal regions before materializing specific candidates. This approach achieves up to 2.2 times speedup over existing superoptimizers and 4.9 times over compiler based approaches, while reducing optimization time by up to 3.4 times.

The sGraph Representation and Two Level Search

At the core of Prism lies the sGraph, a symbolic graph representation that fundamentally reimagines how optimization spaces are structured. Traditional superoptimizers like TASO operate on concrete directed acyclic graphs where nodes represent specific operators with fixed execution parameters. In contrast, sGraphs maintain symbolic representations of execution attributes such as grid dimensions, block dimensions, and tensor to thread mappings, while instantiating only the high level computational structure.

This distinction enables a two level search architecture. At the upper level, Prism constructs symbolic graphs that represent broad families of potentially equivalent programs. At the lower level, each sGraph is instantiated into numerous concrete implementations through auto tuning. A single sGraph can encode thousands of distinct concrete programs, allowing the optimizer to reason about massive swaths of the search space simultaneously.

The technical sophistication here lies in how sGraphs capture operator semantics and hardware constraints as symbolic expressions. Rather than testing specific concrete configurations for validity, Prism performs symbolic reasoning about algebraic identities and dimensional compatibility. This enables the system to identify entire regions of the search space as suboptimal or invalid without enumerating the concrete programs within them. For example, symbolic dimension matching can determine that certain operator compositions are incompatible regardless of specific tile sizes or thread mappings, allowing immediate pruning.

Structured Pruning and Equivalence Verification

The efficiency gains of Prism stem not merely from the symbolic representation itself, but from the rigorous pruning mechanisms it enables. The paper identifies two complementary techniques: symbolic dimension matching and equivalence verification via e graph rewriting.

Symbolic dimension matching ensures operator compatibility by reasoning about tensor shapes and access patterns at the symbolic level. When composing operators within an sGraph, the system checks whether dimensions align using symbolic constraints rather than concrete values. This prunes invalid candidates early, before expensive instantiation and profiling occur.

For equivalence verification, Prism employs e graph rewriting, a