Latent Execution for Neural Program Synthesis
LaSynth learns latent execution traces for synthesis, reaching 55.2% behavioral accuracy on restricted C, about 20 points above executor-free baselines.
Key Findings
Methodology
LaSynth jointly trains a program decoder and a latent executor. The decoder uses RobustFill-style double attention over IO examples, attention over generated tokens, and an Operation Predictor; the Latent Execution Trace (LaET) recursively estimates the hypothetical input that the remaining suffix would need to produce the target output. Decoding is conditioned on this estimate and the target output. Training minimizes L=LProg+LExec, with LExec=Loss(ÎT,O).
Key Results
- On a 500K-example restricted-C dataset, evaluated with five specification IO pairs and five held-out cases, LaSynth reaches 55.2% behavioral accuracy. This is roughly 20 percentage points above neural baselines without an execution component, while covering loops, branches, and simple arithmetic.
- On the 1.1M-example Karel training set, LaSynth obtains 83.68% generalization accuracy and 41.12% exact match. It is slightly below interpreter-based Exec at 86.04% generalization, but exceeds Bunel et al.'s 77.12%.
- Iterative regeneration improves sample efficiency: Karel generalization rises from 86.04% on randomly generated programs to 89.28% after one retraining iteration and 89.36% after two. Generated programs are also shorter and more human-like.
Significance
The paper addresses a central barrier in moving programming-by-example from DSLs to real languages: incomplete C programs generally cannot compile or execute, while syntax, variables, and control flow create a large, non-smooth search space. LaSynth learns execution-like guidance from IO supervision alone, without an interpreter or intermediate traces. It also shows that a synthesizer can improve its own training distribution by replacing redundant random programs with concise, behaviorally equivalent code, potentially reducing the cost of collecting human-written datasets.
Technical Contribution
The main contributions are a dual-representation recurrent architecture, the Latent Executor and LaET, a numerical Operation Predictor, and iterative dataset regeneration. Unlike RobustFill-style models that repeatedly encode the original IO examples, LaET dynamically updates the decoding condition as tokens are produced. Unlike Exec and Shin et al., LaSynth does not require an interpreter for partial programs or full execution traces. Its terminal execution loss avoids imposing an undefined stepwise semantics on incomplete C.
Novelty
The work is the first to use learned latent execution traces for IO-only synthesis in a restricted C domain. Its fundamental innovation is not exact simulation of machine states, but a suffix-oriented latent variable: after the generated prefix, what hypothetical input would allow the remaining program to reach the target output? This converts non-executable partial programs into useful guidance for token-level search.
Limitations
- The language is a narrow C subset: integer lists, addition/subtraction, variables, if, for, break, and continue; it excludes libraries, while/do-while loops, and broader C semantics.
- The Operation Predictor relies on a finite arithmetic table and values in [-4,4], limiting extrapolation to larger numbers or open-ended numerical reasoning.
- Behavioral accuracy is emphasized because exact-match accuracy is near zero; latent states are not guaranteed to correspond to interpretable or faithful intermediate execution.
Future Work
The authors propose combining the Operation Predictor with subword tokenization and developing general numerical representations. Broader directions include full C syntax, pointers and libraries, compiler and static-analysis feedback, structured or verifiable execution states, safer search, and testing iterative regeneration on real codebases. A key challenge is preserving latent flexibility while adding semantic guarantees.
AI Executive Summary
Programming by example asks a system to infer code from input-output behavior. DSLs such as Karel have made progress, but C introduces intertwined syntax, variables, arithmetic, branches, and loops. More fundamentally, a partially generated C program usually cannot compile, so conventional execution-guided synthesis cannot inspect intermediate states. The resulting search space is large and jagged, while human-written training data are expensive to collect.
Chen, Song, and Tian propose LaSynth, which replaces a real interpreter with a learned latent executor. A program decoder predicts tokens, while a Latent Execution Trace (LaET) estimates the hypothetical input that the unfinished suffix would need in order to produce the desired output. This estimate, paired with the target output, becomes the decoder's next conditioning signal. An Operation Predictor additionally exposes finite addition and subtraction relations. The system is trained end to end with token cross-entropy and a terminal latent-execution loss.
On 500K restricted-C examples, LaSynth achieves 55.2% behavioral accuracy, about 20 percentage points above executor-free baselines. On 1.1M Karel training examples, it reaches 83.68% generalization and 41.12% exact match. Its beam-search outputs are often shorter than the random ground-truth programs; retraining on verified synthesized programs raises Karel generalization from 86.04% to 89.28% and 89.36%. The results suggest that latent execution can guide search without an interpreter and can improve data quality, although full C semantics, interpretability, and reliable intermediate verification remain open challenges.
Deep Analysis
Background
Programming by example (PBE) searches for a program satisfying multiple IO constraints. RobustFill targets string-manipulation DSLs; Bunel et al. and Shin et al. study Karel; Exec uses an interpreter to execute partial Karel programs. These settings provide restricted grammars or executable intermediate states. Csmith can generate large C corpora, but random programs often contain redundant statements. The paper therefore studies interpreter-free synthesis in a controlled C subset.
Core Problem
Given K IO pairs, synthesize P such that P(I)=O on both specification and held-out examples. The difficulty comes from syntactically incomplete C prefixes, which cannot be executed; a rapidly expanding, non-smooth space involving variables and control flow; and a mismatch between redundant random programs and concise human code. Exact token recovery is also inappropriate when many programs are behaviorally equivalent.
Innovation
- �� LaET learns execution-like latent states without defining partial-C semantics. • Dual recurrent representations separate syntax/history modeling from behavioral guidance. • Operation Predictor uses a finite arithmetic table to improve numerical reasoning. • Data regeneration uses beam search to retain IO-correct, more concise programs and retrain the model, turning synthesis into a data-cleaning process.
Methodology
- �� Encoding: RobustFill-style double attention produces sI and sO for each of K IO pairs; max pooling forms mt. • Decoding: token-history attention produces dt, and Softmax(Vdt) predicts pt. • Latent execution: starting from Î0=I, the executor recursively computes Ît=LatentExecutor(Ît-1,ht); the decoder then uses (Ît-1,O). • Training: LProg is token cross-entropy; LExec constrains ÎT toward O; LOp trains arithmetic operation prediction. • Search: beam search with size 64 generates candidates, retaining programs that pass five specification and five held-out IO tests.
Experiments
Restricted C is generated from Csmith and post-processed: list inputs, integer variables, constants in [-4,4], addition/subtraction only, and programs up to 256 tokens; splits are 500K/1K/1K for train/validation/test, with at least half containing for loops. Karel uses 1.1M/2.5K/2.5K examples. Comparisons include LaSynth, NoExecutor, NoPartialExecutor, NoOpPredictor, NoAttentionInDecoding, RobustFill, Property Signatures, and Exec. Metrics are exact match and behavioral generalization.
Results
LaSynth reaches 55.2% restricted-C behavioral accuracy, approximately 20 points above executor-free models. On Karel it obtains 83.68% generalization and 41.12% exact match, approaching interpreter-based Exec's 86.04% generalization without requiring an interpreter. Removing latent partial execution, the Operation Predictor, or token-history attention harms performance. Regeneration improves Karel from 86.04% to 89.28% and 89.36% after one and two retraining rounds.
Applications
The method can support short data-processing scripts inferred from tests, educational programming assistants, embedded rule-code prototyping, and automatic synthesis-data construction. Deployment requires compilation, sandbox execution, and security checks, especially for pointers, memory access, and external calls. Regeneration is particularly useful where manually written IO-program pairs are scarce.
Limitations & Outlook
The restricted language does not establish applicability to full C, pointers, recursion, complex types, or libraries. Because LaET is latent and supervised mainly at the terminal state, it may not represent faithful intermediate semantics and can hide errors until the end. The arithmetic table limits numerical extrapolation, while beam search and repeated retraining add computational cost. Future systems should combine latent guidance with compiler feedback, static analysis, and verifiable execution.
Plain Language Accessible to non-experts
Imagine a kitchen asked to recreate dishes from ingredient lists and photographs of the final plates. Several examples are provided: given these ingredients, the finished dish looked like this. The kitchen must infer a recipe. Ordinary systems write a recipe one step at a time, but a half-written C program is like a torn recipe: it cannot be cooked or tested yet.
LaSynth adds a planning assistant. The assistant does not actually cook the incomplete recipe. Instead, it estimates what the ingredients would probably look like after the written steps, assuming the remaining steps must still produce the target plate. This estimate changes after every new instruction and helps the main cook choose the next one. A small arithmetic reference table also suggests likely additions and subtractions.
The surprising result is that the system often discovers a shorter recipe than the original randomly generated one, while producing the same dishes. Researchers keep these successful short recipes and train again, making the kitchen better at learning from fewer examples. The approach shows that useful “imagined progress” can replace direct testing of incomplete work.
However, this kitchen is deliberately small: it handles integer lists, simple arithmetic, branches, and loops, not the full complexity of C. It is a promising apprentice, not yet a complete software engineer.
ELI14 Explained like you're 14
Imagine a coding game where you see several before-and-after screenshots and must write the hidden game move sequence. A row of numbers goes in, another row comes out, and your job is to discover the code that transforms one into the other. Easy? Not really! If your code is unfinished, the computer may refuse to run it at all, just like a game level with missing pieces.
LaSynth gives the coder a clever sidekick. The sidekick does not run the unfinished code. Instead, it guesses what the data probably looks like after the part already written, while remembering that the final answer must match the target. That guess helps choose the next word: should it be a loop, an if statement, a plus sign, or a variable? There is also a tiny math cheat sheet for possible additions and subtractions.
The results are exciting! On a small version of C, 55.2% of generated programs passed all behavior tests, about 20 percentage points better than methods without the sidekick. On the Karel robot-coding benchmark, LaSynth reached 83.68% generalization accuracy. It also often wrote shorter solutions than the original random programs.
But it is not a magic universal programmer. It only handles a carefully limited part of C: integer lists, simple arithmetic, loops, and branches. It does not freely use libraries or understand every real software problem. Think of it as a talented puzzle-solving coding apprentice—already useful, but still training for the big leagues!
Glossary
Latent Execution Trace (LaET)
A sequence of hidden representations that approximates execution-related information for a partial program. It need not correspond to actual machine states, but guides future token generation.
LaSynth recursively constructs LaET through the Latent Executor.
Latent Executor
A neural module that maps the current hidden program state and latent input estimate to the next estimate. It provides execution-like guidance without running incomplete C.
Its final estimate is trained toward the true output through LExec.
Programming by Example
A synthesis setting in which input-output examples specify desired program behavior. Several distinct programs may satisfy the same examples.
The paper applies PBE to restricted C and Karel.
Operation Predictor
An associative numerical component that predicts arithmetic relationships between input and output values. In this paper it enumerates finite addition and subtraction operations.
Its embedding enters the pooled IO representation and receives an auxiliary loss.
Beam Search
A decoding strategy that preserves several high-probability partial sequences instead of committing to one greedy path. It improves the chance of finding a behaviorally valid program.
LaSynth uses beam size 64 for decoding and regeneration.
Csmith
A random C-program generator originally designed for compiler testing. It provides scalable program generation before the paper's domain-specific filtering.
The restricted-C corpus is built from Csmith outputs and post-processing.
Open Questions Unanswered questions from this research
- 1 It remains unclear whether latent execution scales to full C with pointers, recursion, libraries, and resource effects. Compiler feedback, types, and sandboxed execution may be necessary.
- 2 Terminal LExec supervision can conceal intermediate mistakes. A central open problem is how to impose verifiable stepwise semantics without losing flexibility on incomplete programs.
- 3 Iterative regeneration may amplify model bias or reduce diversity. Its effects on coverage, distribution collapse, and real-code generalization require systematic study.
Applications
Immediate Applications
Small data-processing code generation
Educators and engineers can provide list-based IO examples and generate short C programs containing arithmetic, branches, and loops. Outputs should be compiled, tested, and sandboxed before use; the method is best suited to prototypes rather than safety-critical deployment.
Automatic synthesis-data improvement
Research teams can generate random programs, use beam search to keep IO-correct candidates, and retrain on the resulting concise code. This reduces manual example construction and can improve sample efficiency in low-data settings.
Long-term Vision
Verifiable general-purpose code assistants
Combined with compilers, static analysis, type systems, and secure execution, latent execution could support code generation from tests with auditability. The major obstacles are complete language semantics, memory safety, resource control, and complex program structure.
Abstract
Program synthesis from input-output (IO) examples has been a long-standing challenge. While recent works demonstrated limited success on domain-specific languages (DSL), it remains highly challenging to apply them to real-world programming languages, such as C. Due to complicated syntax and token variation, there are three major challenges: (1) unlike many DSLs, programs in languages like C need to compile first and are not executed via interpreters; (2) the program search space grows exponentially when the syntax and semantics of the programming language become more complex; and (3) collecting a large-scale dataset of real-world programs is non-trivial. As a first step to address these challenges, we propose LaSynth and show its efficacy in a restricted-C domain. More specifically, LaSynth learns the latent representation to approximate the execution of partially generated programs, even if they are incomplete in syntax (addressing (1)). The learned execution significantly improves the performance of next token prediction over existing approaches, facilitating search (addressing (2)). Finally, once trained with randomly generated ground-truth programs and their IO pairs, LaSynth can synthesize more concise programs that resemble human-written code. Furthermore, retraining our model with these synthesized programs yields better performance with fewer samples for both Karel and C program synthesis, indicating the promise of leveraging the learned program synthesizer to improve the dataset quality for input-output program synthesis (addressing (3)). When evaluating on whether the program execution outputs match the IO pairs, LaSynth achieves 55.2% accuracy on generating simple C code with tens of tokens including loops and branches, outperforming existing approaches without executors by around 20%.