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