Source-linked AI summary
Retrieval-Based Neural Code Generation
Shirley Anugrah Hayati, Raphael Olivier, Pravalika Avvaru, Pengcheng Yin, Anthony Tomasic, Graham Neubig
TL;DR
Natural-language-to-code generation must map between different input and output forms, and ReCode addresses this setting with retrieval-guided AST generation. It retrieves similar descriptions, extracts action subtrees, and reports improved performance over prior state-of-the-art results.
Problem
Natural-language-to-code generation maps descriptions to structured code, with the input and output taking different forms.
Source: §1 · p. 1Method
ReCode retrieves similar descriptions, extracts n-gram action subtrees from their target ASTs, and boosts actions that would produce those subtrees.
Source: §3 · p. 2, §3.1 · p. 2Results
Takeaways & Limitations
The result suggests retrieval-based generation may also apply to other tree-structured prediction tasks.
Source: §7 · p. 5Generated code can still contain partial implementation errors and incorrect variable copying.
Source: §5.2 · p. 4
Abstract
from arXiv · showhide
In models to generate program source code from natural language, representing this code in a tree structure has been a common approach. However, existing methods often fail to generate complex code correctly due to a lack of ability to memorize large and complex structures. We introduce ReCode, a method based on subtree retrieval that makes it possible to explicitly reference existing code examples within a neural code generation model. First, we retrieve sentences that are similar to input sentences using a dynamic-programming-based sentence similarity scoring method. Next, we extract n-grams of action sequences that build the associated abstract syntax tree. Finally, we increase the probability of actions that cause the retrieved n-gram action subtree to be in the predicted code. We show that our approach improves the performance on two code generation tasks by up to +2.6 BLEU.
1 Introduction
Natural-language-to-code generation maps descriptions to structured code, but the input and output forms differ. Tree-based models enforce well-formedness, yet may struggle with code for phrases rarely seen in training; ReCode brings retrieval into this setting.
1 Introduction
- Tree-based approaches enforce well-formed output, but can struggle to generate correct code for input phrases with low training frequency.The code tree can have many more nodes than the natural-language description.Source: §1 · p. 1
- Retrieval of similar training examples is proposed as a way to bring paired natural-language descriptions and AST structures into neural code generation.This proposal follows retrieval-plus-neural approaches used for rare words in machine translation.Source: §1 · p. 1
- ReCode adapts retrieval-based neural machine translation to tree generation, adding sentence alignment for imperfect matches and improving prior state-of-the-art results.The alignment method uses dynamic programming for word substitution between similar sentences.Source: §1 · p. 1
2 Syntactic Code Generation
The syntactic generation model represents code as an AST and produces it through a sequence of actions. It selects the best action sequence conditioned on the input description.
2 Syntactic Code Generation
- Given a natural-language description, the model generates code represented as an AST by selecting the best generated tree.The model builds the tree as a sequence of actions.Source: §2 · pp. 1–2
- The action sequence is scored autoregressively: each action is conditioned on the input and preceding actions, and T is the total number of steps.The notation defines y_t as the action at time t and y_<t as the preceding actions.Source: §2 · p. 2
- APPLYRULE expands a tree node with a grammar production, while GENTOKEN fills terminal nodes with generated or copied variables and values.Actions follow a preorder traversal from the root.Source: §2 · p. 2
3 RECODE: Retrieval-Based Neural Code Generation
ReCode retrieves similar input descriptions, extracts action subtrees from their associated ASTs, and uses them to bias AST-based code generation. Its pipeline aligns copied words and increases the probability of actions that yield retrieved subtrees.
3 RECODE: Retrieval-Based Neural Code Generation
- ReCode uses retrieved action subtrees as templates to bias generation in a neural syntactic code-generation model.The test-time pipeline retrieves similar descriptions, extracts subtrees from their target ASTs, and boosts actions that produce those subtrees.Source: §3 · p. 2
3.1 Retrieval of Training Instances
- The system retrieves the top M training descriptions by normalized edit-distance similarity, then uses their scores to adjust action probabilities.The similarity score is 1 minus edit distance divided by the longer sentence length.Source: §3.1 · p. 2
3.2 Extracting N-gram Action Subtrees
- Retrieved pieces are n-gram subtrees of generation actions, rather than AST nodes, to preserve structural information from the rules used to build the tree.The method limits candidates to successive actions and uses fixed-depth subtrees to avoid overly rigid structures or combinatorial explosion.Source: §3.2 · pp. 2–3
3.3 Word Substitution in Copy Actions
- For retrieved subtrees containing COPY actions, word alignment maps copied tokens to corresponding input words; unaligned words trigger deletion of the subtree.This avoids reusing a retrieved copy action when its token does not match the input description.Source: §3.3 · p. 3
3.4 Retrieval-Guided Code Generation
- At decoding, actions that would include a retrieved subtree receive a score-based log-probability boost scaled by λ, followed by renormalization.Each subtree's score is based on the best similarity score among the instances from which it was extracted.Source: §3.4 · p. 3
4 Datasets and Evaluation Metrics
Evaluation uses the Hearthstone and Django code-generation datasets, with exact-match accuracy and BLEU as metrics.
4 Datasets and Evaluation Metrics
- The evaluation uses Hearthstone Python classes describing cards and Django pairs of Python source code with English pseudocode.Both datasets are preprocessed as in Yin and Neubig (2017).Source: §4 · p. 3
- Performance is measured with exact-match accuracy and BLEU, following Yin and Neubig (2017).Source: §4 · p. 3
- Table 1 summarizes the dataset statistics used in the evaluation.Source: §4 · p. 3
5 Experiments
The experiments compare RECODE with neural code-generation baselines, then examine benchmark results and examples from both datasets. Results favor retrieval overall, while discussion examples show both cases where retrieval helps and errors that remain.
5 Experiments
- Experiments used the YN17 model settings and compared RECODE with YN17 and an implemented attention-based sequence-to-sequence model.The sequence-to-sequence encoder and decoder are bidirectional and standard LSTMs, respectively.Source: §5 · p. 3
5.1 Results
- RECODE outperforms baselines in both BLEU and accuracy, supporting the effectiveness of retrieval in tree-based code generation.Table 2 compares results with YN17 and ASN baselines.Source: §5.1 · pp. 3–4, Table 2 · p. 4
- p < 0.001 for BLEU on both datasets and Django exact match; HS exact match was not significant (p > 0.3), placing RECODE on par with YN17.The authors note that exact match is less reliable for HS because its code is long and complex.Source: §5.1 · p. 4
- RECODE exceeds ASN without extra supervision, while ASN+SUPATT performs slightly better using supervised attention from heuristic exact word matches.RECODE's attention is unsupervised.Source: §5.1 · p. 4
5.2 Discussion and Analysis
- The authors find that matching tree structure and filling terminal tokens applies to both HS and Django, while complex logic can still produce partial implementation errors.Such errors can lower exact-match accuracy.Source: §5.2 · p. 4
- Examples show RECODE generating correct Django code where YN17 fails and handling complex HS code more effectively, though casting and variable-copying errors remain.In one Django example, RECODE fails to cast s to str; incorrect variable copying is another observed error.Source: §5.2 · p. 4, Table 3 · p. 4, Table 4 · p. 4
6 Related Work
Prior work includes sequence and tree-based code-generation models, retrieval-guided translation, and subtree use in structured prediction. ReCode adapts retrieval-guided translation from textual n-grams to subtree n-grams for code structure.
6 Related Work
- Dong and Lapata (2018) generate a low-level sketch, then fill missing information using the natural-language input and sketch.Source: §6 · p. 5
- Zhang et al. (2018) guide neural machine translation with retrieved target-sentence n-grams, which ReCode adapts to n-grams over subtrees [Zhang et al. (2018)].The adaptation is intended to exploit code structural similarity and address complex statements and rare words.Source: §6 · p. 5
- Galley et al. (2006) used input parse-tree subtrees associated with corresponding output words in syntax-based translation models [Galley et al. (2006)].Source: §6 · p. 5
7 Conclusion
The conclusion reports syntactically correct code generation and improved performance over a previously state-of-the-art model, with potential relevance to other tree-structured prediction tasks.
7 Conclusion
- The retrieval component improves the performance of a previously state-of-the-art model for general-purpose code generation.Source: §7 · p. 5
- The AST-driven model's predicted surface code is syntactically correct.Source: §7 · p. 5
- The authors suggest retrieval-based generation may also apply to other tree-structured prediction tasks.Source: §7 · p. 5