A Retrieve-and-Edit Framework for Predicting Structured Outputs

By Tatsunori B. Hashimoto, Kelvin Guu, Yonatan Oren, Percy Liang. 2018

188 citations recorded by the source corpus.

For the task of generating complex outputs such as source code, editing existing outputs can be easier than generating complex outputs from scratch. With this motivation, we propose an approach that first retrieves a training example based on the input (e.g., natural language description) and then edits it to the desired output (e.g., code). Our contribution is a computationally efficient method for learning a retrieval model that embeds the input in a task-dependent way without relying on a hand-crafted metric or incurring the expense of jointly training the retriever with the editor. Our retrieve-and-edit framework can be applied on top of any base model. We show that on a new autocomplete task for GitHub Python code and the Hearthstone cards benchmark, retrieve-and-edit significantly boosts the performance of a vanilla sequence-to-sequence model on both tasks.

Subfields: Information Systems, Natural Language Processing, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Natural Language Processing

In Signal Processing

Citations in the corpus

Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks (2020, background): “These approaches have proved successful in a number of domains including Machine Translation [18, 22] and Semantic Parsing [21].”
REALM: Retrieval-Augmented Language Model Pre-Training (2020, methodology): “Retrieve-and-edit with learned retrieval In order to better explain the variance in the input text and enable controllable generation, Guu et al. (2018) proposed a language model with the retrieve-and-edit framework (Hashimoto et al., 2018) that conditions on text with high lexical overlap.”
SPoC: Search-based Pseudocode to Code (2019, background): “…text descriptions to a one-line program [42, 35, 43, 44, 21, 8], and while recent work explored generating longer programs from text descriptions [22, 40, 29, 15, 16, 14], these programs are mostly evaluated on syntactic metrics (e.g., exact match and BLEU score) rather than functional correctness.”
The adverse effects of code duplication in machine learning models of code (2018, background): “[12] that combine retrieval methods that find similar snippets within a database of code and then perform edits over those examples is an interesting example of such a direction.”
Simple and Effective Retrieve-Edit-Rerank Text Generation (2020, background): “…approaches for many tasks, including dialogue generation (Weston et al., 2018), language modeling (Guu et al., 2018), code generation (Hashimoto et al., 2018), neural machine translation (NMT) (Gu et al., 2018; Zhang et al., 2018; Cao and Xiong, 2018) and post-editing for NMT…”
What Makes Good In-Context Examples for GPT-3? (2021, methodology): “…dialogue generation (Yan et al., 2016; Cai et al., 2018; Song et al., 2016; Pandey et al., 2018; We-ston et al., 2018; Wu et al., 2019), text summarization (Cao et al., 2017; Peng et al., 2019), data-to-text generation (Peng et al., 2019), and text-to-code generation (Hashimoto et al., 2018).”
CodeSearchNet Challenge: Evaluating the State of Semantic Code Search (2019, background): “Although most approaches are usually aimed towards creating an executable representation of a natural language utterance with a domain-specific language, general-purpose languages have been recently considered by Hashimoto et al. [13], Lin et al. [16], Ling et al. [17], Yin and Neubig [25].”
Unifying Human and Statistical Evaluation for Natural Language Generation (2019, background): “Such models are known to perform well in tasks with complex outputs such as program generation (Hayati et al., 2018; Hashimoto et al., 2018) and style transfer (Li et al., 2018).”
Nearest Neighbor Machine Translation (2020, methodology): “xamples and concatenating them to model inputs. Lewis et al. (2020) improve open-domain question answering systems by retrieving relevant contexts from Wikipedia and concatenating them to the inputs. Hashimoto et al. (2018) use a retrieve-and-edit framework to generate structured outputs such as cod”
Coupling Retrieval and Meta-Learning for Context-Dependent Semantic Parsing (2019, methodology): “The strategy is also used in Hashimoto et al. (2018).”
Extract and Edit: An Alternative to Back-Translation for Unsupervised Neural Machine Translation (2019, neutral): “Unlike other studies using the editing to generate more structural sentences (Guu et al., 2018; Hashimoto et al., 2018), here the revised sentences are designed to serve as better pivotal points in the target language space to guide the translation procedure.”
Editing-Based SQL Query Generation for Cross-Domain Context-Dependent Questions (2019, methodology): “Our work is also related to recently proposed approaches to code generation by editing (Hayati et al., 2018; Yin et al., 2019; Hashimoto et al., 2018).”
Retrieval-Augmented Generation for AI-Generated Content: A Survey (2024, unknown): “It filters out lower-quality data to maintain a high standard of information mapping, offering a variety of retrieval system options like TF-IDF, DPR, RAG, and BLINK + flair to support evidence-based predictions or citations according to task requirements.”
Learning to Represent Edits (2018, background): “is “retrieve-and-edit” models for text generation (Hashimoto et al., 2018), where given an input data x, the target prediction y is generated by editing a similar target y′ that is retrieved based on the similarity between its source x′ and the input x.”
Retrieval-Augmented Multimodal Language Modeling (2023, background): “The external memory used is typically a collection of text passages (Hashimoto et al., 2018; Khandelwal et al., 2019; Karpukhin et al., 2020; Guu et al., 2020; Lewis et al., 2020b;a; Yasunaga et al., 2022b; Borgeaud et al., 2022; Shi et al., 2023) or a structured knowledge base (Zhang et al., 2019;…”
Deep Learning for Text Style Transfer: A Survey (2020, background): “…Wang 2019), machine translation (Cao and Xiong 2018; Wu, Wang, and Wang 2019; Gu et al. 2018; Zhang et al. 2018a; Bulté and Tezcan 2019), conversation generation (Weston, Dinan, and Miller 2018; Cai et al. 2019), code generation (Hashimoto et al. 2018), and question answering (Lewis et al. 2020).”
Learning to Recombine and Resample Data for Compositional Generalization (2020, methodology): “To adapt the prototype-based model for conditional prediction, we condition the neighborhood function on the input x rather than the full datum d , as in Hashimoto et al. (2018).”