The Role of Mutation Path Algorithms in Tree-Diffusion Program Synthesis
Table of Links
Abstract and 1. Introduction
-
Background & Related Work
-
Method
3.1 Sampling Small Mutations
3.2 Policy
3.3 Value Network & Search
3.4 Architecture
-
Experiments
4.1 Environments
4.2 Baselines
4.3 Ablations
-
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
E Tree Path Algorithm
Algorithm 1 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 σ(z) ≤ σsmall, then we can simply mutate the source to the target. If the target node is larger, we sample a random small expression with the correct production rule, and 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 1 gives us the full path to convert one expression to another. We note that this path is not necessarily the optimal path, but a valid path that is less noisy than the path we would get by simply chasing the last random mutation.
\ 
\ 
\ 
\
:::info Authors:
(1) Shreyas Kapur, University of California, Berkeley (srkp@cs.berkeley.edu);
(2) Erik Jenner, University of California, Berkeley (jenner@cs.berkeley.edu);
(3) Stuart Russell, University of California, Berkeley (russell@cs.berkeley.edu).
:::
:::info This paper is available on arxiv under CC BY-SA 4.0 DEED license.
:::
\
You May Also Like
Brazil’s largest private bank advises investors to allocate 3% to Bitcoin in 2026
Brazil’s largest private bank says Bitcoin can improve portfolio diversificat
CME Group to launch options on XRP and SOL futures
