Abstract
Modern machine learning performance relies on specialized tensor kernels, yet porting legacy C code to high-performance Domain-Specific Languages (DSLs) like TACO remains a significant manual burden. This paper introduces STAGG (Synthesis of Tensor Algebra Guided by Grammars), a hybrid framework that leverages Large Language Models (LLMs) to generate probabilistic heuristics for formal program synthesis. By treating LLM outputs as a source of likelihoods rather than final answers, STAGG navigates massive search spaces to "lift" legacy code with 99% accuracy, outperforming existing tools in both speed and coverage without requiring hand-written rules.
The Challenge of Legacy Code Lifting
To achieve peak performance on modern hardware, developers often rewrite standard C code into specialized DSLs. This process, known as "lifting," is notoriously difficult due to the search space explosion. Traditional program synthesis tools must explore millions of potential high-level expressions to find a match. To make this tractable, researchers typically rely on "hard-wired heuristics"—manual rules that guide the search engine. However, these rules are brittle, difficult to maintain, and fail to generalize across different DSLs or complex new problems.
The STAGG Framework
STAGG addresses the search space problem by replacing manual heuristics with a probabilistic model learned on-the-fly from an LLM. The pipeline consists of five distinct stages:
- LLM Querying: The system provides legacy C code to an LLM (e.g., GPT-4) and requests multiple candidate translations into TACO notation.
- Probabilistic Grammar Construction: STAGG standardizes these guesses to build a Probabilistic Context-Free Grammar (pCFG). This grammar assigns higher weights to operations and structures suggested frequently by the LLM.
- Dimensional Analysis: Static analysis of the original C code determines tensor dimensionality, further pruning the search space.
- Guided Enumerative Search: A weighted A* search explores the pCFG, prioritizing the most probable solutions.
- Formal Verification: Candidates are tested against random inputs and then formally verified using Bounded Model Checking (CBMC) to ensure mathematical equivalence to the source code.
Key Insights: LLMs as Heuristic Engines
The core innovation of STAGG is the realization that LLMs do not need to be perfectly accurate to be transformative. By treating LLM outputs as a source of likelihoods, the system can define a "neighborhood" of likely solutions.
A critical component of this process is standardization. LLMs often produce syntactically different but semantically identical guesses (e.g., using different variable names). STAGG "templatizes" these outputs, stripping specific variable names and standardizing index variables so they can be effectively grouped into a grammar.
Evaluation and Results
STAGG was evaluated on 77 benchmarks, including real-world problems from the C2TACO dataset and complex kernels from the Llama large language model inference code.
- 99% Success Rate: STAGG successfully lifted 76 out of 77 benchmarks. This significantly outperforms the previous state-of-the-art (C2TACO), which solved 67, and an LLM-only approach, which solved only 34.
- Efficiency: STAGG solved shared benchmarks in an average of 3.19 seconds, compared to 21.15 seconds for C2TACO.
- Zero Manual Heuristics: The system achieved these results without any hand-written rules, demonstrating that learned heuristics can outperform carefully engineered ones.
- Scalability: STAGG successfully handled complex, multi-dimensional tensor problems found in modern LLM architectures that previous tools could not scale to.
Conclusion and Future Work
STAGG demonstrates that combining the creative "guessing" power of LLMs with the rigor of formal verification creates a robust path for legacy code modernization. While currently limited to a search depth of 6 and rational datatypes for verification, future iterations could expand this strategy to other domains, such as lifting code to SQL for data manipulation or specialized string processing languages.
Summary updated