Diffusion On Syntax Trees For Program Synthesis
Authors: Shreyas Kapur
Erik Jenner
Stuart Russell
Venue: ICLR 2025 Spotlight (2025)
Keywords: neurosymbolic
search
programming languages
inverse graphics
Primary area: neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
TL;DR: We propose a diffusion based approach on syntax trees to do program synthesis for inverse graphics tasks

Abstract: Large language models generate code one token at a time. Their autoregressive generation process lacks the feedback of observing the program's output. Training LLMs to suggest edits directly can be challenging due to the scarcity of rich edit data. To address these problems, we propose neural diffusion models that operate on syntax trees of any context-free grammar. Similar to image diffusion models, our method also inverts "noise" applied to syntax trees. Rather than generating code sequentially, we iteratively edit it while preserving syntactic validity, which makes it easy to combine this neural model with search. We apply our approach to inverse graphics tasks, where our model learns to convert images into programs that produce those images. Combined with search, our model is able to write graphics programs, see the execution result, and debug them to meet the required specifications. We additionally show how our system can write graphics programs for hand-drawn sketches. Video results can be found at https://tree-diffusion.github.io.

Published as a conference paper at ICLR 2025
DIFFUSION ON SYNTAX TREES FOR PROGRAM SYN- THESIS
Shreyas Kapur, Erik Jenner & Stuart Russell University of California, Berkeley (a (srkp, jenner, russelll } @be kekeyyyy..............eee....k .y.
ABSTRACT
Large language models generate code token time. Their autoregressive generation process lacks the feedback of observing the program's output. Train- ing LLMs suggest edits directly can be challenging due to the scarcity of rich edit data. To address these problems, we propose neural diffusion models that operate on syntax trees of any context-free grammar. Similar to image diffu- sion models, our method also inverts "noise" applied to syntax trees. Rather than generating code sequentially, we iteratively edit it while preserving syntac- tic validity, which makes it easy to combine this neural model with search. We apply our approach inverse graphics tasks, where our model learns to convert images into programs that produce those images. Combined with search, our model able to write graphics programs, see the execution result, and debug them to meet the required specifications. We additionally show how our system can write graphics programs for hand-drawn sketches. Video results can be found at /ttttss:/tteee-dfff fiw.zreeeeeifffiiooooooooo wtt.rfuuiiiiiiiiiiiiio qithub.
INTRODUCTION
Large language models (LLMs) have made remarkable progress in code generation, but their au- toregressive nature presents fundamental challenge: they generate code token by token, without access to the program's 's runtime output from the previously generated tokens. This makes it difficult to correct errors, as the model lacks the feedback loop of seeing the program's output and adjusting accordingly. While LLMS can be trained to suggest edits to existing code (Chakraborty et al. 2020 Zhang al. 2022 Jin et al. 2023). acquiring sufficient training data for this task is difficult.
In this paper, we introduce new approach to program synthesis using neural diffusion models that operate directly syntax trees. Diffusion models have previously been used great success in image generation (Ho et al., 22020; Nichol et al. 2021]] [oong et al. 2020). By leveraging diffusion, let the model learn iteratively refine programs while ensuring syntactic validity. Crucially, our approach allows the model to observe the program's output at each step, effectively enabling debugging process.
In the spirit of systems like AlphaZero Silver et al. 2018). the iterative nature of diffusion naturally lends itself to search-based program synthesis. By training value model alongside our diffusion model, we can guide the denoising process toward programs that are likely to achieve the desired output. This allows us to efficiently explore the program space, making more informed decisions at each step of the generation process.
We implement our approach for inverse graphics tasks, a problem of interest the symbolic program synthesis literature (Ellis al. 2021 2019). This domain is naturally suitable for approach because small changes the code produce semantically meaningful changes in the rendered image. We are further motivated to explore this domain because modern vision- vision-language models (VLMs) struggle to achieve exact pixel matches on these tasks (Figure 4).
Our main contributions for this work (a) novel approach program synthesis using diffusion syntax trees and (b) an implementation of our approach for inverse graphics tasks that significantly outperforms previous methods.

---

Published as a conference paper at ICLR 2025
Input Image
Recovered
Rendered
(Subtract (Rdd
(Suterart
Our Nachod
Circtaloris, s-16, (+18)
Circletae2i, 5-15, 2+363
Compler
guad(or25, yodo, mi22, t-1z, angtensor)
yel6, bot, angtexan)
8
(Sultract
(Aod
Circlefare, yett, r-20) Ctrctetaod, yo15, r-20)
8
Our Mechod
Compler
(Bubtrect
Ctrclela:2, y-16,
Serway px-7
Factiess tx. filterane torann(taae0))
licrrrge gapt
Compleer
betiiee, hil, Fitlnenr, xeders/ttcc.1))
Bati tel, fittegres, (xte)((eed))))
Figure I: Examples of programs recovered by our system. The top row shows hand-drawn sketch of an icon (left), the recovered program (middle), and the compilation of the recovered program (right). The top two rows are for the constructive solid geometry language (CSG2D ck)tch). The last row is an example output from our TinysVe environment that learns to invert hierarchical programs of shapes and colors. Video examples can be found at https: //tree:////eeeeeeeeeeeeeeeeeeee diffusion.. github.io ic
2 BACKGROUND & RELATED WORK
Neural program synthesis Neural program synthesis is prominent area of research, in which neural networks generate programs from input-output examples. Early work, such as Parisotto et al. (2016), demonstrated the feasibility of this approach. While modern language models can be directly applied to program synthesis, combining neural networks with search strategies often yields better results and guarantees. In this paradigm, the neural network guides the search process by providing proposal distributions or scoring candidate programs. Examples of such hybrid methods include Balog a (2016). Ellis al. (202T). and Devlin et al. (2017). . A key difference from our work that these methods construct programs incrementally, exploring vast space of partial programs. Our approach, contrast, focuses on editing programs, allowing us to both grow programs from scratch and make corrections based the program execution.
Neural diffusion Neural diffusion models, class of generative models, have demonstrated im- pressive results for modeling high-dimensional data, such as images (Ho et al. 2020 Nichol et al. 2021 Song al., (020)_ A neural diffusion model takes samples from the data distribution (e.g. real-world images), incrementally corrupts the data by adding noise, and trains a neural network incrementally remove the noise. To generate new samples, we can start with random noise and iteratively apply the neural network to denoise the input.
Diffusion for discrete data
Recent work extends diffusion to discrete and structured data like graphs (Vignac et al., 2022). with applications in areas such molecule design (Hoogeboom al.)
2022 Schneuing et al. 2022 Corso et al.) 2022). Notably, Lou et al. (2023) proposed discrete diffusion model using a novel score-matching objective for language modeling. Another promising line of work for generative modeling structured data is generative flow networks (GFlowNets)
(Bengio et al. 2023). where neural models construct structured data one atom at a time.
Diffusion for code generation Singh et al. (202)) use a diffusion model for code generation. However, their approach is first embed text into continuous latent space, train continuous
2

---

Published as a conference paper at ICLR 2025
50
2
#2
2/
Quadd y=lb wv2e hr? plg"
x-18
Quadf
Quazt
x-16
X-15
Quad(
w0.8
Quadi
yn
Clected
quast x-15
andb
cireter xoza
ye38
Cleected pod8 Se2e px24
Ciretel 2P1A p=15
Circler 7-14
Ciectel y=26 p-12
2124
gen26
hw22
r-12
9445*
Campile
Compile
Compile
Compile
Random Mutation
Random Mutation
Mutation
(
sabillaaus sol
37
2
22
3C3
Figure 2: An overview of our method. Analogously to adding noise in image diffusion, randomly make small mutations to the syntax trees of programs. We then train a conditional neural model invert these small mutations. In the above example, operate in domain-specifie language (DSL) for creating 2D graphics using a constructive solid geometry language. The leftmost panel (zo) shows the target image (bottom) alongside its program syntax tree (top). The y value of the circle gets mutated from 16 to 10 in the second panel, making the black circle "jump" little higher. Between 21 and 22, we see that we can mutate the Subtract (-) node Circle node, effectively deleting it.
diffusion model on that space, and then unembed at the end. This means that intermediate stages of the latent representation are not trained correspond actual code. The embedding tokens latch to the nearest embeddings during the last few steps.
Direct code editing using neural models has also been explored. [hhkrraorrty al. (020)) use graph neural network for code editing, trained on a dataset of real-world code patches. Similarly, Zhang et al. (2022) train a language model to edit code by modifying or inserting [MASK] tokens or deleting existing tokens. They further fine-tune their model on real-world comments and patches. Unlike these methods, our approach avoids the need for extensive code edit datasets and inherently guarantees syntactic validity through pretraining task. ChainCoder (Zheng et al.) (202)) used the abstract-syntax tree structure explicitly for code generation with language models, but do not use execution guidance like our approach.
Program synthesis for inverse graphics We inspired by previous work by Sharma et al. (2018); E et al. (2018) 2019), which also uses the CSG2D language. Shhamma et al. (2018) propose convolutional encoder and a recurrent model go from images programs. EElis al. (2019) propose method to provide a neural model with the intermediate program execution output in read-eval-prin loop (REPL). Unlike our method, the ability to execute partial graphics programs a key requirement for their work. Our system operates on complete programs and does not require custom partial compiler. As mentioned in their work, their policies are also brittle. Once the policy proposes an object, it cannot undo that proposal. Hence, these systems require large number of particles a Sequential Monte-Carlo (SMC) sampler to make the system less brittle to mistakes.
3 METHOD
The main idea behind our method is to develop form of denoising diffusion models analogous to image diffusion models for syntax trees.

---

Published as a conference paper at ICLR 2025
Consider the example task from Ellis al. (2019) of generating constructive solid geometry (CSG2D) program from an image. In CSG2D, we can combine simple primitives like circles and quadrilaterals using boolean operations like addition and subtraction to create more complex shapes, with the context-free grammar (CFG),
- ++S+2 + +
circle x.y Quadd w.A
2.y.8"
In Figure 2 Zg our larget program, and 2o is the rendered version of z0- Our task is to invert æo to recover Zg. Our noising process randomly mutates y= 6 to y=10. O. It then mutates the whole e sub-tree with two shapes with a new sub-tree with just one shape. Conditioned on the image zo, and starting at 23, 23, we would like to train neural network to reverse this noising process to get to
In the following sections, we will first describe how "noise" is added syntax trees. Then, we will detail how we train neural network to reverse this noise. Finally, we will describe how we use this neural network for search.
3.1 SAMPLING SMALL MUTATIONS
Let 2 be program at time t. Let px(22+122) be the distribution over randomly mutating program 2, to get 2++1- We want PAr mutations be: (1) small and (2) produce syntactically valid 2441 's.
To this end, we turn to the rich computer security literature on grammar- grammar-based fuzzing (Zeller et al., 2023 Godefroid al. 2008 /rriastavaa Payer 2021] Wang et al., 2201)). To ensure the mutations are small, we first define function (=) that gives us the "size" of program z. For all our experi- ments, we define set of terminals our CFG to be primitives. As an example, the primitives in our CSG2D language are {Quad, Circle). In that language, use (z)) Oprimitive(2). which counts the number of primitives. Other generic options for (2) could be the depth, number nodes, etc.
We then follow Luke (2000) and Zeller et al. (0023 to randomly sample programs from ((2)
our CFG under exact constraints, mmin <
< Fmax- We call this function
Constraing aedSammleeemmus mmax). Setting small value for Fmax allows us to sample small programs randomly. We set max = small when generating small mutations.
To mutate given program 2, we first generate set of candidate nodes in its tree under some smalls
C {n E SyntaxTreess) (n)) S Jmmall.
Then, we uniformly sample mutation node from this set,
Uniform[C].
Since we have access to the full syntax tree and the CFG, we know which production rule produced m, and can thus ensure syntactically valid mutations. For example, if m were number, we know to replace it with number. If m were a general subexpression, we know we can replace with any general subexpression. Therefore, we sample m', which is m's replacement as, (m),, small).
m' Constrttaaa aoo.asttaainneaaaappaaoorroddoee
3.2 POLICY
3.2.1
FORWARD PROCESS
We cast the program synthesis problem as an inference problem. Let p(z[z) be our observation model. where x can any kind of observation. For example, we will later use images produced by our program, but x could also be an execution trace, version of the program compiled to bytecode, or simply syntactic property. Our task is to invert this observation model, i.e. produce program a given some observation x.
We first take some program 2p. either from dataset, D (20,21,.. .) or in our case, randomly sampled program from our CFG. We sample 2n 's such that a (=0)) < max. We then add noise to 20 for 8 Uniform[1, 11, 8max], steps, where Smax is syper-parameter, using,
2t-1 (2 (z))
We then train conditional neural network that models the distribution, (0(211122, 21;
where & are the parameters of the neural network, 2, is the current program, 2, is the current output of the program, and 2o is the target output are solving for.
4

---

Published as a conference paper at ICLR 2025
3.2.2 REVERSE MUTATION PATHS
Since we have access the ground-truth mutations, we can generate targets train a neural network by simply reversing the sampled trajectory through the forward process Markov- Chain,, 2u - - > 2r. At first glance, this may seem reasonable choice. However, training to simply invert the last mutation can potentially create much noisier signal for the neural network.
Consider the case where, within a much larger syntax tree, color was mutated as,
Red Blue Green.
The color in target image, Ho. is Red, while the color in mutated image, 22, is Green. If we naively teach the model to invert the above Markov chain, we are training the network to turn the Green to a B1 Blue, even though we could have directly trained the network go from Green to Red.
Therefore, to create better training signal, we compute an edit path between the target tree and the mutated tree. We use tree edit path algorithm loosely based on the tree edit distance introduced by Pawlik Augsten (2016) 2015). The general tree edit distance problem allows for the insertion, deletion, and replacement of any node. Unlike them, our trees can only be edited under an action space that only permits small mutations. For two trees, 2 and 2B, we linearly compare the syntax structure. For changes that are already I Smaall add that to our mutation list. For changes that are > small, we find the first mutation that reduces the distance between the two trees. Therefore, for any two programs, 2 and zB, we can compute the first step of the mutation path in O(IzAl (#BB)) time.
3.3 VALUE NETWORK & SEARCH
We additionally train value network, (,) which takes as input two rendered images, IA and nn. and predicts the edit distance between the underlying programs that generated those images. Since we have already computed edit paths between trees during training, we have direct access to the ground-truth program edit distance for any pair of rendered images, allowing to train this value network in supervised manner.
Using our policy, (0(= (2, = my; 27),, and our value, Vo( Teg), a given target image, Zo. and a randomly initialized program 2t- At each iteration, we maintain a collection of nodes in search tree with the most promising values and only expand those nodes.
perform beam-search for
3.4 ARCHITECTURE
Figure 3 shows overview of our neural architecture. We use a vision-language model described by Tsimpoukelli et al. 1 as our denoising model, go 22 2/,,, zy; zg). We use an off-the-shelf implementation (Wightman 2019) of NF- ResNet-22 as image encoder, which is normalizer- free convolutional architecture proposed by Brock et al. (2021) to avoid test time instabilities with Batch-Norm (Wu et al., (023). We implement custom tokenizer, using the terminals of our CFG as tokens. The rest of the edit model is small decoder-only transformer Vaswann et al., 2017 Radford et al. 2019), with a total model size of 10 million parameters.
We add two additional types of tokens: an <EDIT> token, which serves as a start-of-sentence to- ken for the model; and <POS x> tokens, which allow the model reference positions within its context. Given a current image, target image, and current tokenized program, we train this trans- former model predict the edit position and the replacement text autoregressively. While making predictions, the decoding is constrained under the grammar. We mask out the prediction logits to only include edit positions that represent nodes in the syntax tree, and only produce replacements that are syntactically valid for the selected edit position.
We set small = 2, which means the network is only allowed to produce edits with fewer than two primitives. For training data, we sample an infinite stream of random expressions from the CFG. We choose a random number of noise steps, E [1, 5]. to produce mutated expression. For some percentage of the examples, P. instead sample a completely random expression as mutated expression. We trained for 3 days for the environments we tested on a single Nvidia A6000 GPU.
5

---

Published as a conference paper at ICLR 2025
Target Image
Current Image
Program
Circle
8
8
Circle
6
a
<EDIT>
Image Encoder hel (x)
Token Embedder
Transformer Decoder
Sp
<PO5
<EOS>
Position
Constrained Autoregressive Decoding
Figure 3: We train (0(2 22, Ir; as decoder only vision-language transformer following Tsimpoukelli et al. (2021). We use an NF-ResNet as the image encoder, which is a normalizer free convolutional architecture proposed by Brock al. (2021). The image encoder encodes the current image, It, and the target images, 2 The current program is tokenized according to the vocabulary in our context-free grammar. The decoder first predicts edit location in the current program, and then tokens that replace what the edit location should be replaced by. We constrain the autoregressive decoding by our context-free grammar by masking only the valid token logits.
4 EXPERIMENTS
4.1
ENVIRONMENTS
We conduct experiments on four domain-specift graphics languages, with complete grammar spec- ifications provided Appendix B
CSG2D 2D constructive solid geometry language where primitive shapes are added and sub- tracted to create more complex forms, explored in our baseline methods (Ellis et al. 2019 Sharma al. 2018). also create CSG2D Sketch, ch, which has an added observation model that simulates sketches using the algorithm from Wood et al. (2012).
TinySVG A language featuring primitive shapes with color, along with Arrange commands for horizontal and vertical alignment, and Move commands for shape offsetting. Figure portrays example program. Unlike the compositional nature of CSG2D, TinySVG is hierarchical: sub- expressions can be combined into compound objects for high-level manipulation. We also create, Rainbow, simplified version of Ti nynVV without Move commands for ablation studies due to its reduced computational demands.
We implemented these languages using the Lark (Lark Contributors 2014) and Iceberg (IceBerg Contributors (023) Python libraries, with our tree-diffusion implementation designed to be generic and adaptable any context- grammar and observation model.
4.2 BASELINES
use two prior works, Ellis et al. (2019) and the vision-language model (VLM) suggested by Tsimpoukelli al. 2021 in the spirit of Sharma al. (2018) as baseline methods.
Sharma al. (0018) employed a convolutional and recurrent neural network to generate program statements from an input image. For fair comparison, we re-implemented CSGNet using the same vision- vision-language transformer architecture (VLM) method, representing the mod- em autoregressive approach to code generation. We use rejection sampling, repeatedly generating programs until match is found.
VLM

---

Published as a conference paper at ICLR 2025
REPL VLM Ellis al. (2019) proposed method to build programs one primitive time until all primitives have been placed. They also give policy network access to a REPL, i.., the ability to execute code and see outputs. Notably, this current image is rendered from the current partial program. As such, we require a custom partial compiler. This is straightforward for CSG2D since it is a compositional language. We simply render the shapes placed so far. For Ti TynV,, it is not immediately obvious how this partial compiler should be written. This is because the rendering happens bottom-up. Primitives get arranged, and those arrangements get arranged again (see Figure T. Therefore, we only use this baseline method with CSG2D.
Tree Difftusion We split our approach into two. The first, Tree Diffusion Search, uses the beam search method previously described, that leverages both policy network and value network. This allows us to explore the possible program solutions more effectively, guided by the output generated at each step of the program's execution. The second part, Tree Diffusion Rollouts, relies solely on the policy network. It repeatedly samples potential edit actions from the policy's s distribution until it arrives at a program that satisfies the given specification.
Test tasks For TinySVG we used held-out test set of randomly generated expressions and their images. For the CSG2D task, we noticed that all methods were at ceiling performance on an in- distribution held-out test set. In Ellis et al. (2019). the authors created a harder test set with more objects. However, simply adding more objects in environment like CSG2D resulted in simpler final scenes, since sampling a large object that subtracts a large part of the scene hecomes more likely. Instead, to generate hard test set, filtered for images the 95th percentile more on incompressibilityy with the LZ4 (Collet et al. 2013
Welch 1984) compression algorithm.
Evaluation In CSG2D, we accepted a predicted program as matching the specification if it achieved an intersection-over-uiio (IoU) of 0.99 or more. In TinySVG, we accepted an image I
if 99% of the pixels were within 0.005 x 256 It is notably very challenging to pass this strict requirement to match almost all the pixels. In Appendix D. Figure IT] we show the complexity of these test tasks.
All methods were trained with supervised learning and were not fine-tuned with reinforcement learn- ing. The training data was generated by using our Const constrriine rainedSamp function, which ran- domly samples programs from grammars. All methods used the grammar-based constrained decod- ing method described in Section (.4] which ensured syntactically correct outputs. While testing, we measured performance based on the number of nodes the method needed to expand to com- plete the task. For each method, node expansion is call to the neural network and rendering step to check the answer. Since all methods tested use an identical neural architecture and param- eter counts, "number of nodes expanded" is comparable metric of total amount of computation required by each of the methods.
Figure 4 shows the performance of our method compared to the baseline methods. In both the CSG2D and TinySVG environments, our tree diffusion policy rollouts significantly outperform the policies of previous methods. Our policy combined with beam search further improves performance, solving problems with fewer calls to the renderer than all other methods. Figure/6 shows successful qualitative examples of our system alongside outputs of baseline methods. We note that our system can fix smaller issues that other methods miss. 7shows some examples of recovered programs from sketches in the CSG2D-Sket ch language, showing how the observation model does not necessarily need to be deterministic rendering: it can also consist of stochastic hand-drawn images.
4.3 ABLATIONS
To understand the impact of our design decisions, we performed ablation studies on the simplified Rainbow environment using a smaller transformer model.
First, we examined the effect of removing the current image (no REPL) from the policy network's 's input. As shown in Figure aaa, this drastically hindered performance, confirming the importance of REPL-like interface observed by Ellis al. 2019).
Next, we investigated the necessity of our reverse mutation path algorithm. While training on the last mutation step alone provides valid path, it introduces noise by potentially targeting subopti-
7

---

Published as a conference paper at ICLR 2025
Performance the CSG2D Environment
Performance on the TinySVG Environment
Fraction of Problems Solved
Fraction of Problerns Solved.
0.20
0.7
0.36
0.4-
0.30
0.2
0.06
0.1
1000
2000
4000
500D
3000
2000
5000
Number of Nodes Expanded
Number of Nodes Expanded
Tree Diffusion Sourch (Ours)
Troe Diffusion Rollouts (Ours)
REPL VLM
VLM
Figure 4: Performance of our approach in comparison to baseline methods in CSG2D and TinysvG languages. We give the methods 256 images from the test set and measure the number of nodes expanded to find solution. The auto-regressive baseline was queried with rejection sampling. Our policy outperforms previous methods, and our policy combined with search helps boost performance further. All neural networks here have the same architecture and number of parameters. Error bars show standard deviation across 5 random seeds.
Ablutione Tie DiEusion
Effecti Expressoon Initiolicatioe
Poottdon Prollene Sabed
Frandion of Prokiene Staved
03-
0.3
0.2
0.2
Chatrol
0.1
Puch
0.1
Nowdin
No Cureett Image
Number of Nodes Expardee
Number Nodes Dependol
(a)
(b)
Figure 5: Effects of changing several design decisions of our system. We train smaller models on the Rainbow environment. We give the model n 256 test problems solve. (a), for Reverse Path, we train the model without computing an explicit reverse path, only using the last step the noising process as targets. For No Current Image, we train a model that does not get to see the compiled output image of the program it is editing. For No Nois Noising nig, instead of using our noising process, we generate two random expressions and use the path between them as targets. In (b) examine the effect of training mixture between forward diffusion (p 0.0) and pure random initialization (p = 1.0) further. Error bars show standard deviation across random seeds.
8

---

Published as a conference paper at ICLR 2025
The Dilhiioo Soarch Troe Diflusion Rolkoat (Ours)
Ground Truth
(Ohms)
VLM
REPL VLM
Figure 6: Qualitative examples of our method and baselines two inverse graphics languages, CSG2D (top two rows) and T TinySvG (bottom two rows). The leftmost column shows the ground- truth rendered programs from our test set. The next columns show rendered programs from various methods. Our methods are able to finely adjust and match the ground-truth programs more closely.
mal intermediate states. Figure aaa demonstrates that utilizing the reverse mutation path improves performance, particularly in finding solutions with fewer steps. However, both methods eventually reach similar performance levels, suggesting that noisy path, while less efficient, can still lead to solution.
Finally, explored whether the incremental noise process is crucial, given tree edit path al- gorithm. Couldn't we directly sample two random expressions, calculate the path, and train the network imitate it? We varied the training data composition between pure forward diffusion (p = 0.0) and pure random initialization (p = 1.0) as shown in Figure 5)b). We found that small proportion (p 0.2) of pure random initializations combined with forward diffusion yielded the best results. This suggests that forward diffusion provides richer training distribution around target points, while random initialization teaches the model navigate the program space more broadly. The emphasis on fine- ane-grained edits from forward diffusion proves beneficial for achieving exact pixel matches in our evaluations.
5 CONCLUSION
In this work, we proposed a neural diffusion model that operates syntax trees for program syn- thesis. We implemented our approach for inverse graphics tasks, where our task is find programs that would render given image. Unlike previous work, our model can construct programs, view their output, and in turn edit these programs, allowing
fix mistakes in a feedback loop. quantitatively showed how approach outperforms baselines at these inverse graphics tasks. We further studied the effects key design decisions via ablation experiments.
Limitations There are several significant limitations to this work. First, we operate on expressions with variable binding, loops, strings, continuous parameters, etc. While we think approach can be extended to support these, it needs more work and careful design. Current large-language models can write complicated programs in many domains, while focus very narrow task.

---

Published as a conference paper at ICLR 2025
Inpast Skott
1
4
5
Out Molhool
1
4
5
Figure 7: Examples of programs recovered for input sketches in the CSG2D- language. The input sketches are from our observation model that simulates hand-drawn sketches (top-row). The output programs rendered (bottom row) are able to match the input sketches by adding and subtract- ing basic shapes. Video results for these sketches can be found at afttoss//tre-ddffuui.ooo githus. i0
Additionally, the task of inverse graphics might just particularly suited for inverse graphics where small mutations make informative changes in the image output.
Future Work In the future, we hope to be able to leverage large-scale internet data on programs to train our system, making small mutations to their syntax tree and learning to invert them. We would also like to study this approach in domains other than inverse graphics. Additionally, we would like to extend this approach to work with both the discrete syntax structure and continuous floating-poin constants.
Impact Given the narrow scope of the implementation, don't think there is direct societal impact, other than to inform future research direction in machine-assisted programming. We hope future directions of this work, specifically in inverse graphics, help artists, engineering CAD model- ers, and programmers with tool to convert ideas to precise programs for downstream use quickly.
ACKNOWLEDGMENTS
We would like to thank Kathy Jang. David Wu, Cam Allen, Sam Toyer, Eli Bronstein, Koushik Sen, and Pieter Abbeel for discussions, feedback, and technical support. Shreyas was supported in part by the AI2050 program at Schmidt Futures (Grant G-22-63471), Erik was supported by fellowships from the Future of Life Institute and Open Philanthropy.
REFERENCES
Jason Ansel, Edward Yang, Horace He, Natalia Gimelshein, Animesh Jain, Michael Voznesensky,
Bin Bao, Peter Bell, David Berard, Evgeni Burovski, Geeta Chauhan, Anjali Chourdia, Will Constable, Alban Desmaison, Zachary Vito,o Elias Ellison, Will Feng, Jiong Gong, Michael Gschwind, Brian Hirsh, Sherlock Huang. Kshiteej Kalambarkar, Laurent Kirsch, Michael Lazos, Mario Lezcano, Yanbo Liang, Jason Liang, Yinghai Lu, CK Luk, Bert Maher, Yunjie Pan, Chris- tian Puhrsch. Matthias Reso, Mark Saroufim, Marcos Yukio Siraichi, Helen Suk, Michael Suo, Phil Tillet, Eikan Wang, Xiaodong Wang. William Wen, Shunting Zhang. Xu Zhao, Keren Zhou, Richard Zou, Ajit Mathews, Gregory Chanan, Peng Wu, and Soumith Chintala. PyTorch 2: Faster Machine Learning Through Dynamic Python Bytecode Transformation and Graph Compilation. In 29th ACM International Conference on Architectural Support Programming Languages and Operating Systems, Volume (ASPLOS 24). ACM, April 2024. doi: 14111445//620066536444666 URL https::/
/ http:/hh.....aasssss////tttooooo 2.
Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. arXiv preprint arXiv:/61 1.01989, 2016.
10

---

Published as a conference paper at ICLR 2025
Yoshua Bengio, Salem Lahlou, Tristan Deleu, Edward J Hu, Mo Tiwari, and Emmanuel Bengio. Gflownet foundations. Journal of Machine Learning Research, 24(210):1-55, 2023.
Andy Brock, Soham De, Samuel L Smith, and Karen Simonyan. High-performance large-scale image recognition without normalization. International Conference on Machine Learning, pp- 1059-1077 PMLR, 2021.
Edwin Catmull and Raphael Rom. A class of local interpolating splines. Computer aided geo- metric design, pp. 317-326. Elsevier, 1974.
Saikat Chakraborty, Yangruibo Ding, Miltiadis Allamanis, and Baishakhi Ray. Codit: Code editing with tree-based neural models. IEEE Transactions Software Engineering, 4885):1385-1199, 2020.
Yann Collet al. Lz4: Extremely fast compression algorithm. code. google. com, 2013.
Gabriele Corso, Hannes Stärk, Bowen Jing, Regina Barzilay, and Tommi Jaakkola. Diffdock: Dif- fusion steps, twists, and turns for molecular docking. arXiv preprint arXiv:2210.0177 2022.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel rahman Mohamed, and Pushmeet Kohli. RobustFill: Neural program learning under noisy VO.. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 990-998. PMLR, 06-11 Aug 2017.
Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Josh Tenenbaum. Learning to infer graph- ics programs from hand-drawn images. Advances neural information processing systems, 31, 2018.
Kevin Ellis, Maxwell Nye. Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama, Write, execute, assess: Program synthesis with repl. Advances in Neural Information Processing Systems, 32, 2019.
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua Tenenbaum. Dreamcoder: Bootstrapping ductive program synthesis with wake-sleep library learning. In Proceedings of the 42nd acm sigplan international conference on programming language design and implementation, pp. 835-
850, 2021.
Patrice Godefroid, Adam Kiezun, and Michael Y Levin. Grammar-based whitebox fuzzing. In Proceedings of the 29th ACM SIGPLAN conference programming language design and imple- mentation, pp. 206-215, 2008
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.
Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling, Equivariant diffu- sion for molecule generation in 3d. In International conference on machine learning, pp. 8867- 8887. PMLR. 2022.
IceBerg Contributors. IceBerg - Compositional Graphics and Diagramming. github, July 2023.
URL httph:ttttt:thhhhe comc aeeevallocebbee
Matthew Jin, Syed Shahriar, Michele Tufano, Xin Shi, Shuai Lu, Neel Sundaresan, and Alexey Svyatkovskiy. Inferfix: End-to-end program repair with llms. In Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pp. 1646-1656, 2023.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 141.66940 2014.
Lark Contributors. Lark a parsing toolkit for Python. github, August 2014. URL https //github.com// lark arr--aaser//ark

---

Published as a conference paper at ICLR 2025
Haotian Liu, Chunyuan Li, Yuheng Li, and Yong Jae Lee. Improved baselines with visual instruction tuning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recogni- tion, pp. 16296-26306, 2024.
Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion language modeling by estimating the ratios of the data distribution. arXiv preprint arXiv:2310. 16834, 2023.
Sean Luke. Two fast tree-creation algorithms for genetic programming. IEEE Transactions on Evolutionary Computation, 4(3):274-20) 2000.
Alex Nichol, Prafulla Dhariwal, Aditya Ramesh, Pranav Shyam, Pamela Mishknn, Bob McGrew, Ilya Sutskever, and Mark Chen. Glide: Towards photorealistic image generation and editing with text-guided diffusion models. arXiv preprint arXiv: /2. 10741, 2021.
Emilio Parisotto, Abdel rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. scuro-symbolic program synthesis, 2016.
Mateusz Pawlik and Nikolaus Augsten. Efficient computation of the tree edit distance, ACM Trans- actions on Database Systems (TODS), 40( 1):1-40, 2015.
Mateusz Pawlik and Nikolaus Augsten. Tree edit distance: Robust and memory-efficient. Informa- fion Systems, 56: 157-173, 2016.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, lly Sutskever, et al. Language models are unsupervised multitask learners. OpenA/ blog, 1(8):9, 2019.
Arne Schneuing, Yuanqi Du, Charles Harris, Arian Jamasb, Ilia Igashov, Weitao Du, Tom Blun- dell. Pietro Lió, Carla Gomes, Max Welling, al. Structure- drug design with equivariant diffusion models. arXiv preprint 2tt::22100116955 2022.
Gopal Sharma, Rishabh Goyal, Difan Liu, Evangelos Kalogerakis, and Subhransu Maji. Csgnet: Neural shape parser for constructive solid geometry. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 5515-5523, 2018.
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1140 1144, 2018.
Mukul Singh, José Cambronero, Sumit Gulwani, Vu Le, Carina Negreanu, and Gust Verbruggen. Codefusion: pre-trained diffusion model for code generation, 2023.
Yang Song, Jascha Dicc--iicst,in, Diederik Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.134455 2020.
Prashast Srivastava and Mathias Payer. Gramatron: Effective grammar-aware fuzzing. In Pro- ceedings of the 30th acm sigsoft international symposium on software testing and analysis, pp- 244-256, 2021.
Maria Tsimpoukelli, Jacob L Menick, Serkan Cabi, SM Eslami, Oriol Vinyals, and Felix Hill. Mul- timodal few-shot learning with frozen language models. Advances in Neural Information Pro- cessing Systems, 34:200-212, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209. 14734, 2022.
Junjie Wang. Bihuan Chen, Lei Wei, and Yang Liu. Superion: Grammar-aware greybox fuzzing. In 2019 JEEE/ACM 41st International Conference on Software Engineering (ICSE), pp. 724-735. IEEE, 2019.
12

---

Published as a conference paper at ICLR 2025
Terry A. Welch. A technique for high-performance data compression. Computer, 17(06):8-19, 1984.
Ross Wightman. Pytorch image models.
http:://githab..commm/..t/
pytorch-image-model 2019.
Jo Wood, Petra Isenberg. Tobias Isenberg, Jason Dykes, Nadia Boukhelifa, and Aidan Slingsby. Sketchy rendering for information visualization. IEEE transactions visualization and computer graphics, 18(12):2749-273 2012.
David Xing Wu, Chulhee Yun, and Suvrit Sra. On the training instability of shuffling sgd with batch normalization. In International Conference Machine Learning, pp. 37787-37845. PMLR, 2023.
Andreas Zeller, Rahul Gopinath, Marcel Böhme. Gordon Fraser, and Christian Holler. Efficient grammar fuzzing. In The Fuzzing Book. CISPA Helmholtz Center for Information Security, 2023. URL https: :/ www. fuzzingbook org/html/ html/ GrammarFuzzez. html Re- trieved 2023- 18:18:06+01:00.
Jiyang Zhang, Sheena Panthaplackel, Pengyu Nie, Junyi Jessy Li, and Milos Gligoric. Coditt5: Pretraining for source code and natural language editing. In Proceedings of the 37th IEEE/ACM International Conference Automated Software Engineering, pp. 1-12, 2022.
Wenqing Zheng, SP Sharan, Ajay Kumar Jaiswal, Kevin Wang, Yihan Xi, Dejia Xu, and Zhangyang Wang. Outline, then details: Syntactically guided coarse-to-fine code generation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scar- lett (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 42403-42411 PMLR, 23-29 Jul 2023. URL https::/prrocediin
w.esss..ss.p...mmmm...om v20 wttpprsssv22222heee22233333 html
APPENDIX
A MUTATION ALGORITHM
CuPcla
11
16
36
40
A1
Circle
Figure 8: An example expression from CSG2D represented as tree to help illustrate the mutation algorithm. The green nodes candidate nodes with primitives count ((2) < 2. Our mutation algorithm only mutates these nodes.
Here provide additional details on how we sample small mutations for tree diffusion. We will first repeat the algorithm mentioned Section in more detail.
Our goal is to take some syntax tree and apply small random mutation. The only type of mutation we consider is a replacement mutation. We first collect set candidate nodes that we are allowed to replace. If we select node too high up in the tree, end up replacing very large part of the tree. To make sure we only change a small part of the tree we only select nodes with & 7 primitives. In Figure 8 if Ssmall we get all the green nodes. We sample node, m,
13

---

Published as a conference paper at ICLR 2025
uniformly from this green set. We know the production rule for from the CFG. For instance, if we selected node 15, the only replacements allowed are + or - If we selected node 46, we can only replace it with any subexpression. When
replace it with angle. If we selected node 11, we sample replacement, we ensure that the replacement is v smalll and that it is different than m. Here show random mutation steps small expression,
(+ (+ (+ (Circle A 4) (Quad E 6 K)) (Quad C 2 M)) (Circle 2 1)) **о0ллон***** w.w.............................
--> (Circle 0 8 A)
(+ (+ (Circle 0 8 A) (Quad 3 C M) (Circle C 1))
(Quad 0 H)
(+ (Quad 1 A (Circle C 1
(+ (Quad 1 A B) (Circle 4 --> 1))
-->
(Quad
H) (Cirele 8 1
During our experiments we realized that this style of random mutations biases expression to longer on average, since there are many more leaves than parents of leaves. This made the net- work better at going from very long expressions to target expressions, but not very good at editing shorter expressions into longer ones. This also made our model's context window run out frequently when expressions got too long. To make the mutation length effects more uniform, add slight modification to the algorithm mentioned above and Section
For each of the candidate nodes, find the set of production rules for the candidates. We then select random production rule, r, and then select a node from the candidates with the production rule follows,
C {n SyntaxTree(:) [n) S amalll
R (ProductionRule(m)) n E C} Uniform[/[]
M (n C ProductionRule(()) = =r}
Uniform[M]
For CSG2D, this approach empirically biased our method to make expressions shorter 30.8%, equal 49.2%, and longer 20.0% of the times (n 10,000 000).
B CONTEXT-FREE GRAMMARS
Here provide the exact context-free grammars of the languages used in this work.
B. CSG2D
s: binop | circle quad
binop: (ep s)
op: +
number: [0 to 15]
angle: [0 to 315]
(Circle radius x y)
circle: (Circle r=number x=number y=number)
// (Quad
angle)
quad: (Quad x=number y=number
w-number h-number
theta=angle)
B.2 TINYSVG
arrange rect el ellipse
move
14

---

Published as a conference paper at ICLR 2025
(b)
Figure 9: Examples of images drawn with the (a) CSG2D and (b) TinySVG languages.
Figure 10: Examples of the being called multiple times by sketch observation model.
direction: v h
color: red green blue yellow
purple
orange
black
white
none
number: [0 9]
sign:
rect:
(Rectangle w=number h#number fill=color stroke=color border=number)
ellipse: (Ellipse w-number h-number fill-color stroke=color border=numbez)
// Arrange direction left right gap
arrange: (Arrange direction gap=number)
move: (Move dx=sign number dy=sign number)
C SKETCH SIMULATION
As mentioned in the main text, implement the CSG2D-Sket environment, which is the same as CSG2D with a hand-drawn sketch observation model. We do this to primarily show how this sort of generative model can possibly be applied to real-world task, and that observations do not
15

---

Published as a conference paper at ICLR 2025
(b)
Figure 11: Examples of thresholding scene images using the LZ4 compression algorithm. The left
represents test set, the right represents training distribution.
need to be deterministic. Our sketch algorithm can be found in our codebase, and is based off the approach described Wood et al. 2012).
Our compiler Iceberg (IceBerg Contributors 2023) and Google's 2D Skia library to perform boolean operations on primitive paths. The resulting path consists of line and cubic bézier com- mands. We post-process these commands to generate sketches. For each command, we first add Gaussian noise to all points stated in those commands. For each line, we randomly pick a point near the 50% and 75% of the line, add Gaussian noise, and fit Catmull & Rom (1974) spline. For all curves, we sample random points at uniform intervals and fit Catmull-Rom splines. We have special condition for circles, where we ensure that the start and end points are randomized create the effect of the pen lifting off. Additionally we randomize the stroke thickness.
Figure shoss the same program rendered multiple times using our randomized sketch simulator.
D COMPLEXITY FILTERING
As mentioned in Section 4 while testing our method alongside baseline methods, we reached ceiling performance for all our methods. Ellis al. (2019) got around this by creating "hard" test case by sampling more objects. For us, when we increased the number of objects to increase complexity, that increased the probability that large object would be sampled and subtract from the whole scene, resulting in simpler scenes. This is shown by Figure [T]b), which is our training distribution. Even though sample large number of objects, the scenes don't look visually interesting. When we studied the implementation details of EElis et al. (2019), we noticed that during random generation of expressions, they ensured that each shape did not change more that 60% or less than 10% of the pixels in the scene. Instead of modifying our tree sampling method, we instead chose rejection sample based the compressibility of the final rendered image.
E TREE PATH ALGORITHM
Algorithm shows the high-level pseudocode for how we find the first step of mutations to transform tree A into tree B. We linearly walk down both trees until we find a node that is different. If the target node is small, i.e., its ((2) S Osmalls then we can simply mutate the source to the target. sample random small expression with the correct production rule, and
the target node is larger, compute the path from this small expression to the target. This gives us the first step to convert the source node to the target node. Repeatedly using Algorithm garithmmggivsssss us the full path to convert one
16

---

Published as a conference paper at ICLR 2025
Algorithm 1 TreeDiff: Find the first set of mutations to turn one tree to another.
Require: treeA: source tree, treeB: target tree, max mex.primitive maximum primitives
Ensure: List of mutations to transform treeA into treeB
1: if (tree,, treeB)
(treeA,
then
2: mutati ons f- []
3: for each (childA, childB) in zip
BreeB.childzee. do
4: mutations + mutations + TreeDiff (childA, childB,
max.primitives)
5: end for
6: return mutations
7: else
8: if iftresk.prmiitive.com
max.primitives and treeB. prree...rmiiiiecount I max.primitives then
9:
return
Mutation(treek) start pos, treeA. end pos, C.reeR.exreession
else
11:
new.expression max.primitives)
GenerateaNewExpreesiiooo oorp://sssss.trr...e..orooooooao
12:
tightening..iiffs
TreeDiff (new.expression, treeB, ApplyAllMutation (new nnewexxpression
max.primitives)
13:
new eew.expressoo
tightening diffs) return
14:
Mutation (treeA. start.pos, BreeA.end_pe
neweexpression)]
end if
16: end if
24
21
23
Figure 12:
A conceptual illustration of why we need tree path-finding. The red path represents the naive target for the neural network. The green path represents the path-finding algorithm's target.
expression to another. We note that this path is not necessarily the optimal path, but valid path that less noisy than the path we would get by simply chasing the last random mutation.
Figure 12 conceptually shows why computing this tree path might be necessary. The circle rep- resents the space of programs. Consider a starting program 2n- Each of the black arrows repre- sents random mutation that kicks the program to slightly different program, 22 + 23 ... we provide the neural network the supervised target to go from 25 to 24. we are teach- ing the network take inefficient path to 2g. The green path is the direct path from 25 2g-
2g - 21, then
17

---

Published as a conference paper at ICLR 2025
Method
% Test Tasks Solved
Our Approach
32.18%
LLaVA (Base)
0.00%
LLaVA (Base+SVG Prompt)
0.00%
LLaVA (Fine-Tuned)
1.17%
Table 1: Performance of LLaVA on CSG2D test tasks. Note that both approaches were given budget of 100 samples from the model to complete these tasks, which is lower than the evaluation results reported earlier. This is because the LLaVA model has considerably more parameters and much slower to run.
F COMPARISON WITH LARGE PRETRAINED MODELS
We perform some additional experiments to compare the performance of modern large vision- language models that are pretrained on internet scale data with our approach. Specifically eval- uate the performance of LLaVA (Liu et al., 2024) on the CSG2D task. The base model performs 0% on our test set (100 rejection samples), and this makes sense since not fair comparison, it has not seen something that has been trained on. This is because passing requires the output image to be very close to the required specification.
DSL. Interestingly, LLaVA gets 0% even when asked to write SVG programs,
To make it more fair for LLaVA, we fine-tuned it using the author's original finetune.te ask script alongside the default suggested hyperparameters. To test LLaVA, we provide it with the test image and rejection sample its output 100 times. We used LLavA-1.0 1.-a- and trained on a single A100 graphics card. Our model was also given 100 node-expansions in the tree search.
The LLaVA model has 7B parameters, and our model uses approximately 700x fewer parameters. Because of this, node expansion count is longer equivalent metric for computation. If we let our method use the same wall-clock time on the same GPU, our method reaches the ceiling performance of 84.68%.
Figure T1 shows just how hard our task is, the left are examples from the test set, the right are examples from the training distribution. Having a strict requirement of matching the specification makes it a very demanding task.
G IMPLEMENTATION DETAILS
We implement our architecture in PyTorch (Ansel et al. 2024 For our image encoder we use the Ne-Res (Brock et al., 2021) implementation from the open-sourced library by Wightman (201)). Images are of size 128 x 128 x for CSG2D and 128 x 128 x 3 for TinySVG. We pass the current and target images
stack of image planes into the image encoder. Additionally, provide the absolute difference between current and target image as additional planes.
Our decoder-only transformer (Vaswani al. 2017 Radford al. 2019) uses 8 layers, 16 heads, with an embedding size of 256. We use batch size 32 and optimize with Adam (Kingma & Ba 2014) with learning rate of 3 x 10-4, All models, including baselines were trained for million steps. The image embeddings are of the same size as the transformer embeddings. We use 4 prefix tokens for the image embeddings. We used a maximum context size of 512 tokens. For both environments, we sampled expressions with at most 8 primitives. Our method and all baseline methods used this architecture. We did not do any hyperparameter sweeps or tuning.
For the autoregressive (VLM) baseline, we trained the model to output ground-truth programs from target images, and provided blank current image. For tree diffusion methods, we initialized the search and rollouts using the output of the autoregressive model, which counted expansion. For our re- implementation of Ellis et al. (2019), we flattened the CSG2D tree into shapes being added from left right. We then randomly sampled position in this shape array, compiled the output up until the sampled position, and trained the model to output the next shape using constrained grammar decoding.
single node
18

---

Published as a conference paper at ICLR 2025
This is departure from the pointer network architecture in their work. We think that the lack of prior shaping. departure from a graphics specific pointer network, and not using reinforcement learning to fine-tune leads to performance difference between their results and re-implementation. We note that our method does not require any of these additional features, and thus the comparison is fairer. For tree diffusion search, used beam size of 64, with maximum node expansion budget of 5000 nodes.
The value network is small 2-layer MLP with 128 units in each layer that takes in the output of the vision encoder, and outputs single scalar predicting the edit distance in program space between two images. We train this for 100, 000 steps.
19


Reviews:
[{"review_id": "47gavgaNRT", "reviewer": "Reviewer_JiwH", "summary": "The authors propose a program synthesis method based on \"tree diffusion\". They randomly corrupt programs (with some constraints) and learn to invert the corruptions, conditioned on the output of the corrupted program and the target output (an image rendering in their case).", "questions": "Fig 3 is confusing. v(x) is the value function or the pre-trained image encoder? if its pretrained, why is there a _phi subscript?\n\nWhere do the initial problems come from? It seems like they are generated randomly, but how? \n\nDo the fuzzing and edit algorithms generalize easily to non-context-free grammars (e.g. general programming languages)?\n\nHow many steps did you train for? I don't think this is covered in the appendix.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The method is simple but non-obvious\nThe more general problem of program synthesis conditioned on desired outputs is very relevant\nThe authors use randomly generated programs as a dataset which sidesteps dataset curation in favor of just a specification of the language\nThe paper is well-written, easy to understand, and has nice and (mostly) clear figures", "weaknesses": "The paper is somewhat limited in scope (simple problem setup) in ways that make it not entirely obvious how the method \"scales\" to more complex relevant tasks like code generation.\n\nSome minor things covered in Questions", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Y0do2ksz0U", "reviewer": "Reviewer_6hsj", "summary": "The paper introduces an innovative approach to inverse graphics tasks by combining diffusion models with transformers. The authors present the first application of diffusion to program synthesis using explicit syntax tree updates, validating their method on CSG2D and TinySVG environments.", "questions": "- In the limitations section, you mention that your syntax tree currently supports only a limited set of operators. What are the bottlenecks in expanding support to other operators and generalizing to broader coding problems?\n- What is the cost of training the value network that predicts the edit distance?\n- Given the recent advances in vision-language models, how does your approach compare against contemporary models like VILA or LLaMA? The current baselines only include older models (4+ years old), and evaluating against recent state-of-the-art would provide a more helpful comparison.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Innovative Approach: The paper presents a novel combination of autoregressive, diffusion, and search methodologies, which, despite being applied to a specific domain, holds potential for broader applications. The reverse mutation path algorithm also provides an efficient way to generate training targets. \n- Clarity and Replicability: The manuscript is well-written and easy to follow, providing sufficient detail to enable replication of the experiments.\n- Comprehensive Ablation Studies: The authors conduct thorough ablation studies on key hyperparameters and the impact of integrating search, enhancing the understanding of their method's efficacy.", "weaknesses": "- Literature Coverage: The authors should consider citing \"Outline, Then Details: Syntactically Guided Coarse-To-Fine Code Generation\" in the Neural program synthesis section since this work also takes multiple passes of the program and edits the program. \n- The value network (vϕ) training and effectiveness aren't thoroughly evaluated. Alternative approaches to edit distance estimation, including direct calculation from syntax trees, are not explored or compared.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "p7FpRYz8Fc", "reviewer": "Reviewer_4cr6", "summary": "This paper proposed a program synthesis framework using mutations on syntax trees via a neural diffusion model for inverse graphic tasks. These tasks aim to convert images that can contain free hand-sketches of shapes or a set of computer-generated colored shapes into images depicting a computer-generated rendering matching the input. The authors defend the claim that the approach presents the ability to edit trees generated using a base model as opposed to incrementally autoregressive approaches that fail to narrow down the search space. The authors apply their method to inverse graphics tasks and present results in two settings (CSG2D and TinySVG) and show improved performance in the number of problems solved compared to baselines (REPL VLM and VLM) along with an ablation study to investigate the individual contributions of constituent components.", "questions": "Here are some of the main points I would like to make:\n\n1. The edit distance introduced by Pawlik & Augsten is narrowed to allow only small changes. If there are big changes, the change that reduces the distance between the trees the most is chosen. While this can be used as a training signal, it is assumed and was mentioned in section 3.3.2 that access to the ground-truth mutations is available. However, access to this ground truth may not be readily available in most cases. How is this ground-truth data obtained? If not automated, the authors must comment on the limited scalability of the approach.\n\n2. In section 4.2 under evaluation, it is not clear what the criteria for considering a match between the synthesized and true plan is. Re: “In TinySVG, we accepted an image if 99% of the pixels were within 0.005 ≈ $\\frac{1}{256}$.” Is this “within 0.005” a tolerance on the 8-bit pixel color intensity? If so, please state explicitly and explain how this metric is applied to the RGB images in TinySVG.\n\n3. The difference between tree diffusion search and tree diffusion rollouts is not explicitly stated or defined in section 4.\n\n4. There were references to computational demand and efficiency, yet no time-related metrics were reported to demonstrate gains in this regard, despite claims about improving performance efficiency. It is unclear as to just how much improvement the proposed approach affords.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The main strength of this paper is the design of a neurosymbolic framework to evaluate the automated (i.e. diffusion-based) conversion of images into context-free grammar. This formal evaluation ensures that the desired specifications are met through iterative observation of the execution results and verification.\n\n2. The authors extend the approach to accept hand-drawn sketches and illustrate examples in the appendix confirming the applicability of the approach in several real-world settings.\n\n3. The supplementary videos illustrate the overall problem that the authors are attempting to solve and showcases the \"edits\" made by the framework.", "weaknesses": "There are three main weaknesses I would like to bring up. The authors are encouraged to rebut and provide legitimate explanations, if any, against these and the review decision may be adjusted accordingly.\n\n1. A claim made by the author states that the proposed method focuses on editing the program synthesized from the image, unlike prior works that autoregressively generate programs that are incrementally better. In doing so, the authors propose adding random noise to modify a base syntax tree generated from CSG2D. Despite the illustrative example shown in Figure 2, enabling the approach to modify node types rather than shape, the base syntax tree structure is governed by the initial generated program. It remains unclear (at least it has not been proven) that diffusion + base tree always yields the optimal syntax tree (a statement regarding suboptimal steps in section 4.3 is thus not justified). An analysis and example to demonstrate this is lacking and should be included.\n\n2. The overall architecture presented in Figure 3 is difficult to understand at first glance. In addition, the descriptions provided in section 3.4 (the model architecture) do not present enough detail to understand Figure 3.  Specifically, it is not clear how replacing the \"(\" denoted by the edit position token and replacing it with the grammar constrained autoregressive decoding yield valid syntax (i.e. are there low-level implementations in play that ensure that entire blocks from “(“ to “)” are parsed out during replacing? How are varying input lengths handled? ). Replacing \"(\" with \"(Quad 8...\" seems to break the pairing of parenthesis. In addition, it is not clear what the purpose of \"EOS\" is in this context.\n\n3. The fraction of problems solved by the method trained with \"no reverse path\" is nearly the same as that of the control after about 60 expanded nodes. The control reaches the same performance at about 50 nodes. Is this a \"significant\" efficiency gain when the maximum node expansion budget was two orders of magnitude higher (i.e. 5000)? There are no computational or time-related metrics presented which help put this into context.\n\n4. Overall the presentation of section 3, especially 3.4, requires careful rework.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VEh7inEWaS", "reviewer": "Reviewer_GpLx", "summary": "The paper presents an algorithm to train a diffusion model on the abstract syntax tree (AST) of programs written in a simple procedural language. That language produces 2D images by combining geometric shape primitives, and the resulting image is used to guide the denoising process.\n\nUsing an additional network estimating the distance from a rendered image to the target image, beam search is applied to generate a sequence of AST edits (node replacements) that produce a predicted program, approximating the target image. That approach transfers to generating geometric images from noisy sketches.", "questions": "1. In the ablations, there is one about training only on the last mutation step. It's illustrated by Fig. 12 by only showing the transition from z_5 to z_4. Do I understand correctly that the other reverse transitions (e.g., z_4 -> z_3, ..., z_1 -> z_0) are not used for training?\n2. If so, why not use that (training on all denoising steps) as a baseline?\n3. Can you define the \"Rollout\" method, and the differences with the \"Search\" one?\n4. What's the relationship between \"Number of nodes expanded\" and the \"number of compilations needed\"?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality\n-------------\nThe paper takes inspiration from existing ideas and benchmarks, but they are clearly cited, and the novel aspects are well described. For instance, a backward edit path that's better than reversing the corruption path, removing the need of a partial renderer, and relying on beam search rather than full-fledged reinforcement learning.\n\nQuality\n----------\n\nExperiments demonstrate the advantages of the proposed approach, and properly ablate the different aspects and contributions.\n\nClarity\n---------\nThe paper is overall clear and straightforward to follow. With the additional details of the appendix, the approach should be re-implementable by a different team.\n\nSignificance\n-----------------\nUsing ML models to directly manipulate and modify programs, rather than either generate a whole program autoregressively, or emit edition instructions (which could be invalid or result in an invalid program) could make iterative program generation better or easier.\nThe fact that no reinforcement learning is required, but observation of the output of intermediate programs can simply be combined with beam search is also an interesting result.", "weaknesses": "Originality\n-------------\nNo major weakness here, the work is in the continuation of previous cited work.\n\nQuality\n----------\nComparison with baselines might have been more extensive, specifically the RL-based algorithms from previous work, which could have better shown how \"brittle\" they were.\n\nClarity\n---------\nA few things were not clearly defined in the experiments and ablation sections (see \"questions\" below).\n\nSignificance\n----------------\nOverall, the CSG2D and TinySVG languages are a small-scale benchmark, but it's unclear whether the proposed approach would scale to large, structured programs in general purpose languages.\nFor instance, it might not be possible to find a sequence of valid programs created by short mutations between two relatively close programs. For instance, going from recursion to a loop, from an implicit lamda to a declared function, or from a for loop to a list comprehension. Even splitting a function into smaller pieces may require either large edits, or intermediate unparseable states.\n\nAfter discussion\n----------------------\nThe authors provided clarifications, other reviewers raised a few additional concerns, overall I'm maintaining my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "01aRX4Hynz", "reviewer": "Reviewer_ZXAr", "summary": "This paper addresses the edge of visual symbolic reasoning and code generation. It addresses the important task of generating code (symbolic sequence) to depict images with visual feedbacks. It applies diffusion model-like approaches to permute the program syntax tree and guarantee the correctness of the generated code. Through iterations, the model is able to recover the image with high fidelity using discrete preset symbols.", "questions": "See discussions above.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper proposed a novel solution to the reverse CG field, to synthesis programs for visual symbolic reasoning. The proposed method address the hard task through the unique lens of syntax tree, and achieves notably better results.\n\n- The idea of permuting on syntax tree allows for more efficient model, with better performance.\n\n- The efforts to make demo video makes the paper easier to understoand and spread.", "weaknesses": "This is a good paper, with minor weakness points below.\n\n- It is better to mention the size of the decoder model in the architecture section rather than in the appendix, so that readers with LLM background can quickly understand the edge of the model on this task.\n\n- It is better to discuss the number of steps in the diffusion procedure, and the model's potential ability limit in terms of output sequence length or number of symbols.\n\n- Two highly related work should be cited and discussed:\n\n\"Outline, Then Details: Syntactically Guided Coarse-To-Fine Code Generation\" in ICML 2023, which explore the possibility of syntax tree to generate code, and via coarse-to-fine multi-round generation approach.\n\n\"Symbolic Visual Reinforcement Learning: A Scalable Framework with Object-Level Abstraction and Differentiable Expression Search\" in TPAMI, which also learns visual symbolic programs, not to depict the image but to interact with the environments. Rainbow environment is also leveraged in their experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)