Generative Explanations for Program Synthesizers

Amirmohammad Nazari, Souti Chattopadhyay, Swabha Swayamdipta, Mukund RaghothamanarXiv 2024 · DOI · arXiv

Abstract

Program synthesizers generate code that satisfies formal specifications but often lacks human readability due to unidiomatic logic and generic naming. We introduce NomNom, a framework that leverages Large Language Models (LLMs) and a novel "resynthesis" sanity check to generate meaningful names for synthesized subroutines. By combining local behavioral examples with functional verification, NomNom improves naming accuracy from 24% to 79% and significantly enhances human comprehension of synthesized code.

Introduction

The field of program synthesis has seen remarkable progress, enabling the automated generation of code for data wrangling, network policies, and program repair. Despite these functional successes, synthesizers remain "algorithmic black boxes." The code they produce is often "alien"—technically correct but structurally unidiomatic. A major barrier to understanding this code is the absence of meaningful identifiers; synthesizers typically output generic names like g1 or f1. While LLMs like GPT-3.5 are adept at naming human-written code, they often fail when faced with the unconventional logic of synthesized programs, leading to nonsensical suggestions that erode user trust.

The NomNom Framework

NomNom is designed to provide reliable, semantically accurate names for subroutines within synthesized implementations. The framework's architecture, illustrated in Figure 1, centers on three core innovations.

The NomNom workflow for naming and validating synthesized subroutines.

1. Subspecifications (Prompt Expansion)

Rather than presenting the LLM with raw code alone, NomNom instruments the program to record "local" behavior. By capturing specific inputs and outputs for every subroutine during execution, the system provides the LLM with concrete behavioral "hints." These examples often clarify the function's purpose more effectively than the unidiomatic source code.

2. Algorithmic Sanity Checks via Resynthesis

To ensure a suggested name (e.g., findLargestElement) is accurate, NomNom performs a "reverse synthesis" test. It asks a secondary LLM (LM2) to write a new function ($g'$) based only on the proposed name and its type signature ($T$). NomNom then replaces the original "alien" subroutine with this human-like implementation. If the resulting program still satisfies the original global specification ($E$), the name is certified as functionally accurate.

3. Bottom-Up Generation and Retries

Recognizing the stochastic nature of LLMs, NomNom utilizes a retry loop of up to 20 attempts to find a name that passes the sanity check. Furthermore, it adopts a bottom-up strategy, naming the simplest helper functions first. This provides richer context for naming the higher-level functions that call them.

Evaluation

The researchers evaluated NomNom using the DreamCoder Benchmarks, a set of 155 list-processing tasks (e.g., sorting, filtering). The final evaluation set comprised 144 specification-implementation pairs containing 344 subroutines. Reference names were manually created and cross-verified by independent researchers to establish a ground truth.

Key Results

  • Accuracy: NomNom increased naming accuracy from a baseline of 24% (standard LLM) to 79%.
  • Comprehension: In a study with 18 students, those using NomNom-generated names achieved a 76% comprehension score, a massive jump from the 18% score of the baseline group.
  • User Preference: Participants preferred NomNom’s names in 76% of cases, compared to only 2% for the baseline.
  • Efficiency: Validated names are typically produced within 5–10 seconds per subroutine.

Discussion and Insights

The success of NomNom suggests that in synthesized code, behavior is a stronger signal than syntax. A "good" name serves as a proxy for the function's logic; if a name contains enough semantic information for another agent to reconstruct the function, it is deemed successful. This "sanity check" transforms a subjective naming task into a functional verification problem.

Limitations

Despite its performance, NomNom faces challenges. LLMs remain sensitive to prompt engineering, and the current system is focused solely on naming rather than broader natural language explanations. Additionally, serializing behavior for higher-order functions remains technically complex. Future work will explore generating validated comments and testing the system with professional developers in industrial settings.

Summary updated

Abstract

Despite great advances in program synthesis techniques, they remain algorithmic black boxes. Although they guarantee that when synthesis is successful, the implementation satisfies the specification, they provide no additional information regarding how the implementation works or the manner in which the specification is realized. One possibility to answer these questions is to use large language models (LLMs) to construct human-readable explanations. Unfortunately, experiments reveal that LLMs frequently produce nonsensical or misleading explanations when applied to the unidiomatic code produced by program synthesizers. In this paper, we develop an approach to reliably augment the implementation with explanatory names. We recover fine-grained input-output data from the synthesis algorithm to enhance the prompt supplied to the LLM, and use a combination of a program verifier and a second language model to validate the proposed explanations before presenting them to the user. Together, these techniques massively improve the accuracy of the proposed names, from 24% to 79% respectively. Through a pair of small user studies, we find that users significantly prefer the explanations produced by our technique (76% of responses indicating the appropriateness of the presenting names) to the baseline (with only 2% of responses approving of the suggestions), and that the proposed names measurably help users in understanding the synthesized implementation.
BibTeX
@misc{nazari2024generative,
  author = {Amirmohammad Nazari and Souti Chattopadhyay and Swabha Swayamdipta and Mukund Raghothaman},
  title = {{Generative Explanations for Program Synthesizers}},
  year = {2024},
  eprint = {2403.03429},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.03429},
}
Figure