Programmatic Synthesis for Scalable Execution

This direction is split into other directions: programmatic test generation. Its last version stays readable and citable here.

Version 1 of 145 papers58 conceptsfrozen 2026-10-04

When faced with a massive dataset or a complex software testing task, the instinctive approach is to use a Large Language Model (LLM) as a direct worker: feed it a row of data to clean, or ask it to generate a single test case. However, this "direct inference" model hits a wall of high latency, prohibitive costs, and strict context window limits.

A growing body of research suggests a more powerful paradigm: Programmatic Synthesis. Instead of asking an LLM to perform the task, researchers are asking the LLM to write the code that performs the task. By shifting the model's role from a "worker" to an "architect," these systems achieve orders-of-magnitude improvements in speed and reliability.

The Efficiency Gap: From $O(N)$ Inference to $O(1)$ Synthesis

The fundamental intuition behind programmatic synthesis is a shift in computational complexity. In a traditional LLM pipeline, processing $N$ records requires $N$ expensive API calls. In a programmatic pipeline, the LLM is invoked once to synthesize a deterministic script (e.g., Python or SQL), which is then executed locally on all $N$ records.

Lei Cao and colleagues demonstrate this in systems like PALIMPZEST and SEED. By treating the LLM as a compiler that transforms natural language descriptions into optimized data pipelines, they achieve up to a 90x speedup. The LLM's reasoning is captured in the logic of the generated code, allowing massive datasets to be processed at native execution speeds without further reliance on the model. Similarly, Jinyang Liu and Domenico Bianculli apply this to anomaly detection in CodeAD, where synthesized Python rules monitor high-volume log streams with sub-millisecond latency.

Solving the Validity Problem in Testing

In software testing and fuzzing, generating valid inputs is notoriously difficult for LLMs. Asking a model to output a raw binary file or a complex nested JSON often results in "hallucinated" syntax that the system under test immediately rejects.

The programmatic approach bypasses this by generating test generators rather than test cases.

Because the LLM is writing code—a domain where it has high proficiency—the resulting scripts are syntactically valid and can use programmatic constraints to ensure the final data adheres to strict format specifications. This "meta-programming" approach ensures a 100% valid input rate in frameworks like SORT, developed by Yan Song, which uncovers thousands of bugs that single-API testing misses.

Scaling Verification for Code Intelligence

For training LLMs to code, the quality of the "reward signal" is paramount. If a model passes a weak test case with a "brute-force" or incorrect solution, it learns the wrong lessons.

Researchers like Jiabao Ji and Yifei Liu are using programmatic synthesis to create "hard" verifiers. In HARDTESTGEN and rStar-Coder, the pipeline doesn't just generate static input-output pairs. Instead, it synthesizes:

  1. A Data Generator: A script to produce high-volume, complex inputs.
  2. A Constraint Validator: A script to verify that the code's output meets the problem's logical requirements.

This allows for the creation of massive, verified datasets (like the 418K problems in rStar-Coder) that test algorithmic efficiency and edge cases. As Yujian Liu notes in HarnessLLM, these executable test harnesses are far more effective at finding deep logical bugs than static pairs because they can employ randomized, diverse testing logic.

Tool Generators vs. Code Scanners

Finally, this shift redefines how LLMs interact with massive codebases. In KNighter, Chenyuan Yang and Lingming Zhang argue that LLMs should not be used as direct "code scanners" for vulnerabilities, as they cannot ingest the millions of lines of code in a kernel. Instead, they use the LLM to synthesize static analysis checkers. These checkers, written in a specialized language, are then executed at native speeds to scan the entire Linux kernel, discovering long-latent bugs that the LLM could never have seen directly.

By moving from direct inference to programmatic synthesis, the research community is finding a way to harness the reasoning of LLMs while maintaining the scale, speed, and precision of traditional software execution.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_programmatic_synthesis_for_scalable_exec_f1a86b15,
  title = {Programmatic Synthesis for Scalable Execution},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/programmatic-synthesis-for-scalable-execution/rdr_f1a86b1571184eb18b43f6f92b6f26d6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_programmatic_synthesis_for_scalable_exec_f1a86b15_v1,
  title = {Programmatic Synthesis for Scalable Execution},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/programmatic-synthesis-for-scalable-execution/rdr_f1a86b1571184eb18b43f6f92b6f26d6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}