Diffusion On Syntax Trees For Program Synthesis

id:: 2405.20519
Authors:: Shreyas Kapur, Erik Jenner, Stuart Russell
Published:: 2024-05-30
arXiv:: https://arxiv.org/abs/2405.20519
PDF:: https://arxiv.org/pdf/2405.20519
DOI:: N/A
Journal Reference:: N/A
Primary Category:: cs.AI
Categories:: cs.AI
Comment:: https://tree-diffusion.github.io
github_url:: _

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.

premise

outline

quotes

notes

summary

1. Brief Overview

This paper introduces a novel approach to program synthesis using neural diffusion models that operate directly on syntax trees. Unlike autoregressive language models, this method iteratively refines programs while preserving syntactic validity and allows the model to observe program outputs at each step, effectively enabling a debugging process. The approach is applied to inverse graphics tasks, where the model learns to convert images into programs that generate those images. The system combines neural diffusion with search to efficiently explore the program space and produce programs meeting specifications, even from hand-drawn sketches.

2. Key Points

Uses neural diffusion models operating on syntax trees for program synthesis.
Iteratively refines programs while maintaining syntactic validity.
Allows the model to observe program outputs at each step for debugging.
Combines neural diffusion with search for efficient program space exploration.
Successfully applied to inverse graphics tasks, generating programs from images and hand-drawn sketches.
Outperforms previous methods in inverse graphics tasks.
Guarantees syntactic validity through the use of context-free grammars.

3. Notable Quotes

No notable quotes were identified in the provided text.

4. Primary Themes

Program Synthesis: The core focus is developing novel methods for automatically generating programs from input data (images in this case).
Neural Diffusion Models: The paper leverages the power of diffusion models, extending their application beyond image generation to the structured data of syntax trees.
Inverse Graphics: The chosen application domain allows for direct feedback and evaluation of the generated programs through visual comparison of the generated image to the target image.
Search-Based Program Synthesis: The iterative nature of diffusion is combined with search algorithms to efficiently navigate the vast space of possible programs.