Diffusion On Syntax Trees For Program Synthesis: Mutation Algorithm

Table of Links

Abstract and 1. Introduction

2. Background & Related Work

3. Method

   3.1 Sampling Small Mutations

   3.2 Policy

   3.3 Value Network & Search

   3.4 Architecture

4. Experiments

   4.1 Environments

   4.2 Baselines

   4.3 Ablations

5. Conclusion, Acknowledgments and Disclosure of Funding, and References

   
   

Appendix

A. Mutation Algorithm

B. Context-Free Grammars

C. Sketch Simulation

D. Complexity Filtering

E. Tree Path Algorithm

F. Implementation Details

A Mutation Algorithm

Here we provide additional details on how we sample small mutations for tree diffusion. We will first repeat the algorithm mentioned in Section 3 in more detail.

Our goal is to take some syntax tree and apply a small random mutation. The only type of mutation we consider is a replacement mutation. We first collect a set of candidate nodes that we are allowed to replace. If we select a node too high up in the tree, we end up replacing a very large part of the tree. To make sure we only change a small part of the tree we only select nodes with ≤ σsmall primitives. In Figure 8, if we set σsmall = 2, we get all the green nodes. We sample a node, m, uniformly from this green set. We know the production rule for m 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 an angle. If we selected node 11, we can replace it with any subexpression. When we sample a

replacement, we ensure that the replacement is ≤ σsmall, and that it is different than m. Here we show 4 random mutation steps on a small expression,

During our experiments we realized that this style of random mutations biases expression to get longer on average, since there are many more leaves than parents of leaves. This made the network 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, we add a slight modification to the algorithm mentioned above and in Section 3.

For each of the candidate nodes, we find the set of production rules for the candidates. We then select a random production rule, r, and then select a node from the candidates with the production rule r, as follows,

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).