Guided Tensor Lifting

Yixuan Li, José Wesley de Souza Magalhães, Alexander Brauckmann, Michael F. P. O'Boyle, Elizabeth Polgreen

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:

  1. LLM Querying: The system provides legacy C code to an LLM (e.g., GPT-4) and requests multiple candidate translations into TACO notation.
  2. 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.
  3. Dimensional Analysis: Static analysis of the original C code determines tensor dimensionality, further pruning the search space.
  4. Guided Enumerative Search: A weighted A* search explores the pCFG, prioritizing the most probable solutions.
  5. 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.
The STAGG pipeline: from legacy C code to LLM-guided search and formal verification.

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.

Expression standardization: transforming diverse LLM guesses into a common template to build an effective pCFG.

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

BibTeX
@article{li2025guided,
  author = {Yixuan Li and José Wesley de Souza Magalhães and Alexander Brauckmann and Michael F. P. O'Boyle and Elizabeth Polgreen},
  title = {{Guided Tensor Lifting}},
  journal = {Proc. ACM Program. Lang.},
  year = {2025},
  doi = {10.1145/3729330},
}

Loading related content...

Figure