Research map / Image generation / Fast diffusion sampling
Diffusion On Syntax Trees For Program Synthesis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes tree diffusion: a neural denoising model that learns to invert small random mutations on context-free grammar syntax trees, combined with beam search and a value network, applied to inverse graphics program synthesis.
Problem
Autoregressive LLM code generation lacks feedback from program execution and training LLMs to edit code requires scarce edit data; the goal is program synthesis for inverse graphics that can observe outputs and iteratively edit programs while staying syntactically valid.
Approach
Apply image-diffusion-style noising to syntax trees by sampling small grammar-valid mutations, train a conditional vision-language transformer to invert them (with reverse edit paths computed by a tree-diff algorithm), and use the policy plus a learned value network for beam search over edits.
Key results
- Tree diffusion policy rollouts significantly outperform CSGNet and REPL Flow policies on CSG2D and TinySVG (n=256 test images, 5 seeds).
- Adding beam search (beam size 64, budget 5000 nodes) further improves performance, solving problems with fewer renderer calls than all other methods.
- Ablations on Rainbow show removing the current image (no REPL) drastically hurts performance, and reverse mutation paths and a 0.2 mix of random initializations improve results.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use tree-diffusion policy rollouts instead of autoregressive CSGNet or REPL Flow | Tree diffusion · CSG2D | node expansions to find a solution | Helped |
| Use tree-diffusion policy rollouts instead of autoregressive CSGNet | Tree diffusion · TinySVG | node expansions to find a solution | Helped |
| Add beam search to the tree-diffusion policy | Tree diffusion · CSG2D and TinySVG | calls to the renderer | Helped |
| Remove the current compiled image from the policy input (ablation) | Tree diffusion · Rainbow | performance | Hurt |
| Add an explicit reverse mutation path instead of training on only the last noising step (ablation) | Tree diffusion · Rainbow | steps to find a solution | Helped |
| Add a small proportion of pure random initializations (ρ = 0.2) to forward-diffusion training (ablation) | Tree diffusion · Rainbow | performance | Helped |
| Replace forward-diffusion examples with pairs of independently sampled random expressions (ablation) | Tree diffusion · Rainbow | performance | Hurt |
Surprising findings
- Mixing in 20% pure random initializations with forward diffusion gave the best results, versus pure forward diffusion or pure random initialization.
- Naively sampling candidate nodes made expressions grow; a production-rule-first sampling scheme was needed to balance length changes.
Limitations
- Only expressions without variable binding, loops, strings, or continuous parameters are supported.
- Evaluated only on narrow inverse graphics DSLs, not general code tasks.
- Does not yet leverage large-scale internet program data.
Experimental setup
Datasets: randomly sampled CSG2D expressions randomly sampled TinySVG expressions LZ4-filtered hard CSG2D test set
Benchmarks: CSG2D TinySVG CSG2D-Sketch
Metrics: number of nodes expanded (renderer calls) to solve IoU >= 0.99 for CSG2D pixel match within 1/256 for TinySVG
Baselines: CSGNet REPL Flow Autoregressive vision-language transformer with rejection sampling
Builds on: CSGNet Iceberg Lark NF-ResNet REPL-based program synthesis (Ellis et al.)
Closest papers by meaning
- Fast and Fluent Diffusion Language Models via Convolutional Decoding and Rejective Fine-tuning (NeurIPS 2025 · similarity 0.85)
- Scaling Diffusion Language Models via Adaptation from Autoregressive Models (ICLR 2025 · similarity 0.85)
- Image Translation as Diffusion Visual Programmers (ICLR 2024 · similarity 0.85)
- How Compositional Generalization and Creativity Improve as Diffusion Models are Trained (ICML 2025 · similarity 0.85)
- Controlling Language and Diffusion Models by Transporting Activations (ICLR 2025 · similarity 0.85)
- From Next-Token to Next-Block: A Principled Adaptation Path for Diffusion LLMs (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.