Handling Open-Vocabulary Constructs in Formalizing Specifications: Retrieval Augmented Parsing with Expert Knowledge

Authors: mohammad saqib hasan
sayontan  ghosh
dhruv  verma
geoff  kuenning
erez  zadok
scott a smolka
niranjan  balasubramanian
Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-21 23:44:22

Abstract: We study the problem of Open-vocabulary constructs (OVCs), ones that are not known beforehand, in the context of converting natural
language (NL) specification sentences into formal languages (e.g., LTL or code).  Models tend to fare poorly on such OVCs, since they do
not have the necessary knowledge a priori.  In such settings, a domain expert can provide the correct constructs based on their
preference or domain knowledge at inference time. Our goal is to effectively reuse this inference-time, expert-provided knowledge in future specification sentences without having to retrain the model.  To this end, we first present a new parsing setting---\emph{dynamic knowledge-augmented parsing} (DKAP)---where, in addition to the input sentence, the model is given (dynamically growing) expert knowledge in the form of a key-value lexicon that associates NL phrases with correct OVC constructs.  To address the DKAP problem, we propose ROLex, a retrieval-augmented parsing approach that uses the dynamic expert lexicon.  ROLex consists of a retriever and a generator that are trained to find and use the relevant subset of the key-value store to produce the correct parse. One key challenge in realizing this solution is the lack of training data for the retrieval-augmented parsing.  We show how we can make use of synthetic data generation, along with original task-level training data---i.e., the (NL sentence, FL statement) pairs---to carry out the requisite training for the retrieval-augmented parsing setting. Further, to improve training effectiveness, we have devised multiple strategies for focusing the model on the relevant subset of retrieved knowledge. Finally, we introduce a new evaluation paradigm designed to address the DKAP problem by simulating the dynamic expert-provided knowledge in three different formalization settings (NL2LTL, NL2Code, and NL2CMD). Our evaluations show that DKAP is a difficult challenge, and ROLex helps improve the performance of baseline models by using dynamic expert knowledge effectively.

Main paper: 
 introduction: 
 Formalizing natural language (NL) specifications is a fundamental NLP problem with applications in verification (Chen et al., 2023; He et al., 2022) , code and proof generation (Yin et al., 2018; Wang et al., 2021; Wu et al., 2022) . Modern parsers for these tasks are modeled using Seq2Seq (Hahn et al., 2021; Irving et al., 2016; He et al., 2022) models, which take the specification as input and output a formal representation as a sequence of n-grams.A fundamental challenge in NL formalization is the presence of Open-Vocabulary Constructs (OVCs), phrases in the NL specification for which the formal-language construct is not known a priori. This is due to either poor training data coverage or a lack of the domain knowledge needed to anticipate all possible target constructs. OVC problems are common in formalisms used in verification, such as Linear Temporal Logic (LTL) (Rozier, 2011) and Signal Temporal Logic (STL) (He et al., 2022) . This is due to phrases that cannot be Figure 1 : ROLEX in practice: We show two parsing tasks with OVCs: (i) natural language to linear temporal logic (NL to LTL) and (ii) natural language to code (NL to Code). As shown in (a) and (b), a regular parser cannot generate the expected target constructs because they were not seen in the training data. The phrase IS NOT A REGULAR FILE in NL2LTL input should map to !IS_REGULAR(), but the model generates != REGULAR. Similarly for NL2Code, the model uses SCIPY.LINALG.SOLVE instead of NUMPY.LINALG.SOLVE as the library function for LEAST SQUARES SOLUTION. ROLEX augments models with the ability to use expert feedback to handle these OVC cases. The expert knowledge is designed as a key-value lexicon that maps NL phrases to their expected parses.generalized to a formal construct without prior knowledge about the specific domain (i.e., the software being verified) or expert preferences. Even domain experts cannot anticipate all necessary OVC constructs, since they would have to read (parse) each specification sentence, make decisions about how to represent the constructs and aggregate them into a list, making it a cumbersome process. Such constructs are, in effect, unknown to the model and the experts before they are first encountered when parsing the corresponding specifications. The NL-to-LTL portion of Figure 1 illustrates the use of OVCs with an example from Network File System specifications (Shepler et al., 2003) . OVCs are also prevalent in regular program synthesis (Yin et al., 2018; Wu et al., 2022) , as models may use functions from knowledge that does not meet the downstream runtime environment or user preference. The NL-to-Code portion of Figure 1 illustrates an example where a regular model might use a linear algebra implementation from the SCIPY library, whereas the user would prefer a NUMPY implementation due to its availability or runtime requirements.OVCs present a challenge that is fundamentally different from previously studied outof-distribution settings (Zhou et al., 2023; Yu et al., 2018; Mekala et al., 2023) . OVCs are OOD problems in that the constructs in the test specifications are not seen by the model during training. However, in the settings we consider, the constructs are also not known or enumerable a priori: there is no knowledge available to use about the construct until the first encounter during inference. This means that we cannot apply techniques relying on documentation (Zhou et al., 2023) as a knowledge source for the construct or existing knowledge bases (Krishnamurthy & Mitchell, 2015) that provide the construct vocabulary (e.g., predicates in tables). Other domain-adaptation techniques that use in-domain examplars (Parvez et al., 2021; Pasupat et al., 2021) in retrieval-augmented-generation rely on models' generalization to generate the OVC construct given in-domain examples. This generalization, we argue, is a hard challenge for the types of OVC settings we consider, where deep domain expertise and user preferences impact construct design and choice.To address the OVC issue, a model needs feedback from the user about the correct construct. In traditional feedback-based frameworks, user feedback is provided after every parse. However, in formalization tasks, we find that OVCs, while not known to the models during training, repeat multiple times in specification sentences. Therefore, OVC feedback from the user can be recorded and used in a later parse without any fine tuning. This presents a new knowledge-augmented parsing setup, which we call dynamic knowledge-augmented parsing (DKAP). In regular knowledge-augmented parsing, a static knowledge database (e.g., Wikipedia, Github) is built before inference (Lewis et al., 2020; Yu, 2022) . In DKAP, the knowledge base is dynamic, growing with each parse. DKAP presents a realistic scenario for solving the OVC issue because (i) it is difficult to enumerate all possible OVCs before they are encountered, (ii) an expert can generate knowledge based on errors, and (iii) OVCs repeat across parses so knowledge can be reused.Using DKAP, we propose ROLEX, a retrieval-augmented generation (RAG) framework, to help parse OVCs. ROLEX collects small amounts of feedback from the expert based on the errors made by the parser when translating OVCs. This feedback, designed as a key-value lexicon, represents knowledge from the expert for the model to use in translating an OVC in future parses. The key is a generalized NL phrase or description of an OVC; the value is the correct construct. A retriever module is trained to fetch the relevant set of expert lexicons from the feedback database during each parse, and a generator module is conditioned to use this information when parsing. When an already-seen OVC is encountered in a future parse, the previously stored knowledge is used to generate the correct parse. Figure 1 shows examples of how ROLEX will help resolve OVCs. We outline two mechanisms for training ROLEX: (i) using synthetic data when there is no training data and (ii) using data augmentation techniques when training data exists. We also propose several training methods that let the RAG modules learn the task better. Furthermore, we show how few-shot LLMs can also benefit when modeled via ROLEX.We simulated ROLEX across several benchmarks from various semantic parsing domains: NL-to-Linear Temporal Logic (NL2LTL), NL-to-Bash commands (NL2CMD), and NL-to-Python code (NL2Code). The simulations were done in the DKAP scenario and in the presence of out-of-distribution constructs to emulate OVCs. We observed that ROLEX provides consistent performance gains over baseline seq2seq generation in both fine-tuned and few-shot settings. Further analysis shows how each module of ROLEX is designed to provide optimal performance. In summary, this paper makes the following three key contributions: (1) introduces a new parsing setting called dynamic knowledge-augmented parsing (DKAP) that accounts for growing user-provided inference-time knowledge; (2) presents a retrieval-augmented generation model, ROLEX, and an effective training strategy to address the OVC problem in semantic parsing in the DKAP setting; (3) demonstrates the challenges of the DKAP problem and the effectiveness of the proposed solution (ROLEX) through empirical evaluation and analysis on three different formalization tasks. 
related work: 
 Out-of-Distribution (OOD) and Zero-Shot Semantic Parsing: Works like Spider (Yu et al., 2018) (Text2SQL) and Docprompting (Zhou et al., 2023) introduce out-of-distribution (OOD) semantic parsing benchmarks. Others develop models to handle OODs. For example, SeqZero (Yang et al., 2022) decomposes tasks into subtasks, (Shaw et al., 2021) combine model and grammar, Zheng & Lapata (2021) incorporate entity tags, and Bogin et al. (2021) train LMs to learn syntactic structure parsing. Zero/few-shot parsing is also popular owing to low data requirements. For instance, Zerotop (Mekala et al., 2023) decomposes the problem into subproblems and solves them as zero-shot QA tasks. In Wu et al. (2022) , the authors generate theorem code from NL in zero-shot, while NL2TL (Chen et al., 2023) generates synthetic data using few-shot prompting for fine-tuning. Our work addresses the OVC issue where constructs are not known a priori and thus cannot be resolved before they are encountered. Hence, unlike OOD settings where there are domain shifts but constructs are known, the need to use constructs never seen during training makes our OVC setting much more challenging.Researchers have proposed domain adaptation in semantic parsing via retrieval-augmented generation using exemplars (Pasupat et al., 2021) or metalearning (Chen et al., 2020b) . (Shi et al., 2022) address cross-lingual Text2SQL with RAG using source domain exemplars for solving target domain queries, while Chen et al. (2023) , He et al. (2022), and Jia & Liang (2016) use synthetic data to learn parsing in the target domain. Our work also incorporates ideas of domain adaptation as synthetic data is created to train ROLEX. A key challenge specific to our work is that all the constructs required to generate the output are not known apriori. As such, even with synthetic data, generation models are not exposed to all the possible constructs during training and need the ability to learn to use new constructs on-the-fly during the inference time.Retrieval-Augmented Generation (RAG) for Parsing: One common RAG for parsing involves retrieving examples from training data (Pasupat et al., 2021; Gupta et al., 2022) . Zemlyanskiy et al. (2022) introduce an additional step by doing another retrieval with the input and generated output and using that as the model input for the final parse. Wu et al. (2023) use cyclic training of RAG modules from unsupervised data based on confidence scores. Docprompting (Zhou et al., 2023) uses documentation to resolve queries about code, while REDCODER (Parvez et al., 2021) uses code-comment examples. Our solution is also based on RAG formulation and incorporates expert inputs at inference using a growing knowledge base of lexicons.OVCs in Semantic Parsing: OVCs in parsing previously involved addressing generalization to new words, for instance, using character representations (El Boukkouri et al., 2020; Kawakami et al., 2017) . However, with modern models, the problem domain has shifted to handling unknown labels and constructs before they are encountered during inference. Examples are Jiao et al. (2022) , which introduces OVC arguments in role prediction problems, and Simig et al. (2022) , which introduces the OVC problem in classification problems with a large number of labels. Some other works address OVC predicates in semantic parsing, such as Gardner & Krishnamurthy (2017) , where freebase queries are resolved using knowledge base, and Krishnamurthy & Mitchell (2015) , which proposes predicate matching post generation to handle OVCs. Das et al. (2021) use RAG to address OVC issues by retrieving similar training exemplars and test on out-of-distribution entities in a limited fashion. Dalvi Mishra et al. ( 2022) use a dynamic memory of feedback for open-domain QA. While similar to the above two in using a RAG-based solution to elicit user input, our work differs in terms of the target domain (semantic parsing for specifications versus QA for open-domains), and in its focus on a compact feedback format using key-value lexicons. 
handling ovcs with dynamic knowledge-augmented parsing: 
 The open-vocabulary construct (OVC) problem refers to the presence of a priori unknown constructs from outside the model's vocabulary space. We motivate OVC in two settings: (i) formalizing specifications for verifying complex systems (e.g., NL to Linear Temporal Logic (Brunello et al., 2019) ) and (ii) text-to-code (e.g., NL to Python code (Yin et al., 2018) ).In formal specifications, the NL constructs are often domain-specific (i.e., tied to the specific software being verified) and thus a generic fixed list is not particularly useful. Also, for a given domain, the full set of needed constructs cannot be enumerated beforehand, since they can be identified and resolved (by experts) only after reading (parsing) the specification sentences. For example, in the Network File Systems domain, there are thousands of network protocol documents (called RFCs), each containing numerous specifications. Experts need to manually parse each such specification with full knowledge of all the possible constructs for building formal models. Experts in our own research group, people with years of experience in formal verification and file systems, struggled to parse these specifications due to the presence of OVCs that they did not know about a priori.In text-to-code settings, a user might prefer to use a different implementation (e.g., a preferred Python library) than what the model was trained on, implement their own method, or use a specific representation. Thus, unlike standard semantic parsing settings, these settings include open-vocabulary constructs, ones that are unseen or unknown during training, and are only resolved when a specs require construct encountered at test time.To address this challenge, we introduce the Dynamic Knowledge-Augmented Parsing Problem (DKAP), which includes the following changes to the standard semantic parsing setup: (i) Dynamic growing knowledge: When parsing a given test sentence, the models use a dynamically growing knowledge base, which records all knowledge provided by the user for the open vocabulary constructs encountered in previous sentences. (ii) Reuse without retraining: To reduce the user's burden, we assume that they provide knowledge about a new construct the first time it is encountered. The models must learn to reuse this knowledge when the same construct reappears later. Appendix Section D empirically motivates the prevalence of OVCs in a real specification modeling scenario and their potential for reuse. Lastly, we want the models to be trained to use the knowledge as it becomes available, without having to retrain every time a new construct is handled.Consider a stream of NL sentencesX = ⟨x 1 , • • • , x N ⟩.In the standard parsing problem, a model produces an output y t , conditioning only on the input x t . In DKAP, when parsing the sentence x t , the model is additionally given access to expert knowledge K 1:t-1 , the accumulated knowledge for all open-vocabulary constructs that appeared in the input sentences ⟨x 1 , • • • , x t-1 ⟩. For x t , a model is thus expected to generate the output y t , conditioning on both x t and the expert knowledge K 1:t-1 .We designed a simple and concise text-to-construct mapping to record feedback in the form of an expert lexicon. The keys in the lexicon are generic, idiomatic natural-language phrases; the values correspond to the correct (i.e., desired) formal representations for the OVCs.Example lexicon entries from two domains, NL2LTL and NL2Code, are shown in Table 1 .The NL2LTL example, from the Network File System (NFS) domain (Shepler et al., 2003) , shows that the lexicon entry ⟨A IS A REGULAR FILE → IS_REGULAR(A)⟩ designating that any phrase resembling A IS A REGULAR FILE should be parsed to construct IS_REGULAR() with the argument being the entity A. Similarly, for NL2Code, the lexicon ⟨ Dot product of two arrays ... →numpy.dot⟩ indicates that the dot-product function from the NUMPY library should be used if the specification requires it. Formally, when parsing x t , the available knowledge is given by K1:t-1 = {(k i , v i )} m t-1 i=1, where m t-1 is the total number of unique OVCs seen until x t-1 . Each key k i is a generalized natural-language phrase representing an OVC, and v i is its corresponding expert-provided formal representation. 
retrieval-augmented parsing with expert lexicons: 
 To address the DKAP setting, we need models that can take an input NL specification x t and the current state of the expert lexicon database K 1:t-1 at T = t and produce a semantic parse y t that includes the appropriate OVC constructs from K 1:t-1 . A simple solution is to fit the entire knowledge K 1:t-1 as additional context to a generative model to produce the output parse. This can be problematic for two reasons. First, the growing knowledge base may exceed the model's size limit. For example, a common input limit for many Seq2Seq models is 512 tokens, which is, for example, exceeded after aggregating expert lexicons from only 25 NFS RFC specifications. Second, adding the entire K 1:t-1 may increase the noise (i.e., irrelevant entries) in the input context for the generator. A retriever helps mitigate this problem by selecting the relevant parts of K 1:t-1 as input.Therefore, we propose ROLEX, Retrieval-augmented generation parsing with expertprovided OVC lexicons, illustrated in Figure 2 using examples from the NFS RFC. We can fine-tune LMs such as T5 (Raffel et al., 2020) or Code-T5 (Wang et al., 2021) , or few-shot prompt LLMs like ChatGPT (OpenAI, 2023a) and GPT-4 (OpenAI, 2023b)) for the generator Figure 2 : Dynamic knowledge-augmented parsing using ROLEX: Our RAG framework for inference-time knowledge-augmented parsing through expert lexicons. We start at T = 1 with an empty lexicon. The generator thus parses the first NL specification with empty retrieved knowledge to produce a formal statement. This generates an error (highlighted in red): "duplicate exists" is incorrectly parsed as IS_DUPLICATE(), whereas the domain expert prefers "exists(X)". This partial-knowledge entry is added to the dynamic knowledge base and gets reused appropriately at a later time step T = t, as shown in the lower block. module, and use dense retriever models (Gao et al., 2021; Karpukhin et al., 2020) for the retriever. The main challenge lies in obtaining training data. To address this, we use synthetic data generation and data-augmentation techniques. To develop the retriever and generator modules, we experimented with several methods, explained next.To train the generator, we need training instances of the form (x, K, y); to train the retriever, we need instances of the form (x, K, K y ), where K y ⊆ K is the subset of relevant key/value pairs for the OVCs that appear in the output y for instance x. Here we describe our approach for generating and augmenting such training data automatically.In some semantic parsing use cases, such as formalizing RFC specifications, manually curating (x, y) pairs and lexicons for OVCs can be difficult. However, due to the restricted nature of the parses, we can curate synthetic data via grammar-based generation (He et al., 2022) . We do this by developing a synthetic grammar G adapted to the target domain. For example, we have shown that such a grammar can be used to model LTL statements generated from the NFS domain. Details of the grammar are provided in the Appendix Section A.If training data with (x, y) pairs exist, we can augment them with the gold lexicon K for each pair. We do this by first defining the OVCs and their formal representations, and then using a suitable pre-defined knowledge source to obtain an idiomatic natural-language description of the OVCs. For example, the first few words from Python documentation serve as OVC descriptions in the NL2Code domain. In this way, we construct a comprehensive lexicon knowledge base and then use it to enumerate each (x, y) pair with the relevant K.Retrieval Module: We use sentence transformers (Reimers & Gurevych, 2019) as our dense retrievers in two ways: off-the-shelf and fine-tuning. For off-the-shelf usage, we plug in a pre-trained retriever. However, this approach does not work well in formalization settings because most retrievers are fine-tuned on general NL tasks, and each parsing domain has its unique language and set of sentences to model. Hence, we opt for fine-tuning the retriever using our curated (x, K, y) data pairs. GivenK = {(k i , v i )} m i=1 ,where k i is the naturallanguage grounding phrase and v i is the OVC's formal representation, we create (x, k i ) m i=1 tuples for each x. This tuple store is then used to fine-tune a retriever R using contrastive learning (Henderson et al., 2017) with in-batch negatives (Karpukhin et al., 2020; Chen et al., 2020a) (see the Appendix Section B, for the training objective). The retriever R is fine-tuned to include all K gold lexicon entries in its top n ranked lexicon entries.The Generator G is a language model that should generate the semantic parse y based on (x, K * ), where K * is the list of top n ranked lexicon entries retrieved by R from the full lexicon. Ideally, the generator should be able to identify K y , the relevant lexicon entries in K * and then use them appropriately to produce the correct semantic parse y. However, in practice, there can be three types of issues that arise when training generators with noisy retrieved lexicon entries. The generator might: (i) entirely ignore K * during generation, (ii) use non-relevant entries in K * , resulting in incorrect parses, and (iii) fail to identify or use all of the relevant lexicon entries. To mitigate these issues, we propose four generator training schemes: (1) BASIC: G is trained by generating y conditioned on x K * . (2) EXTRA SUPERVISION: From each (x, K * , y) training pair, we derive two pairs: (x, K * , y) and (x, K y , y). This causes G to observe y during training twice-once conditioned on x K y and another time on x K * . The idea is to provide an extra supervision signal to G on what are correct lexicons. (3) MULTI-TASK LEARNING: G is trained to generate k y y conditioned on x K * . The motivation lies in workings of language models: they generate the next token based on the input and the prior generation. (4) TRANSFER LEARNING: G is trained first to generate k y conditioned on x K * . Then model is further fine-tuned as in scenario (1). Intuition is that relevant lexicon extraction helps G learn to parse better. 
evaluation setup: 
 Our goal is to evaluate ROLEX for addressing OVC issues in the Dynamic Knowledge-Augmented Parsing (DKAP) setting. We introduce a new evaluation protocol that differs from the standard evaluation for RAG: (i) the knowledge base grows as we parse more specifications and (ii) an expert adds new knowledge to correct OVC errors after each parse.Our evaluation protocol mimics dynamic (growing) knowledge of OVCs at test time by simulating the addition of knowledge about a new OVC after each parse. In this way, subsequent parses can use this accumulated knowledge. Formally, given task T and possible OVCs O, we create train and test sets, D train and D test as per methods in Section 4.1. Each D consists of tuples (x t , K t , y t ) where x t is the NL, y t is the FL and K t are the gold lexicons. ROLEX is trained on D train and then evaluated with an initially empty dynamic knowledge base, KB. At time t, the retriever retrieves relevant lexicons K * from KB, and x K * is given as input to generate y ′ . Comparing y ′ and y, we extract and add a set of new lexicons K new ∈ K t , s.t. K new ∩ KB = ∅ to KB so that they can be retrieved for parsing at time t + 1.We evaluated ROLEX across three formalization tasks. Our evaluation sets were created with constructs in the target output that were not present in the training sets, thus simulating out-of-vocabulary constructs (OVCs). The first task, NL2LTL, was to parse NFS specs into Linear Temporal Logic (LTL); the OVCs are function predicates (verbs) and a subset of variables (nouns). Due to lack of training data, we opted for grammar-based synthetic data generation (outlined in Section 4.1). Details about the grammar are given in Appendix Section A. Our test set consisted of 100 NFS statements taken from SpecNFS (Ghosh et al., 2022) and annotated to LTL by experts. Our second task is NL2Code, which involves formalizing specs to Python code, and the OVCS are function names. We use the CoNaLa dataset from Docprompting as the test set that contains unseen functions to simulate OVCs. We augment the data with lexicons using the database of Python documents provided with Table 2: Performance gains in fine-tuned models across three different benchmark tasks due to ROLEX. Bleu in All was evaluated for the complete model output expression, whereas OVC's F1, Precision & Recall were evaluated only for the subset of OVC constructs in the target expression. the dataset. Our final task, NL2CMD, involves converting statements to bash commands where the OVCs are bash functions. Here, we again use TLDR dataset from Docprompting as the test set that contains OOD commands. To create the lexicon, we utilize tldr2 pages to form lexicon keys. Further details and examples from each dataset, along with information on how the lexicons were designed, are listed in Appendix Section C.We used the different (small, base, large) variants of the BGE sentence transformer from FlagEmbedding (Xiao et al., 2023) as our retriever. For the generator, we used T5 and Code-T5 for the fine-tuned setting and ChatGPT and GPT-4 for few-shot. For evaluation, we calculate BLEU (Papineni et al., 2002) to measure quality of whole parse and precision, recall, and F1-score of the OVCs to measure performance on OVCs. We also calculate the gains ROLEX achieves using reusable feedback compared to traditional feedback by measuring reduction in error. Further details are given in Appendix Section E. 
results & analysis: 
 Our experimental evaluation setup is aimed at answering the following questions: (i) How effective is ROLEX in leveraging expert knowledge to address OVCs? (Tables 2 and 3 (a)) (ii) What is the effect of retriever performance on the overall downstream task performance? (Table 3(b) ). (iii) What is the variation in the overall OVC task performance for different generator training approaches? (Table 4(a) ). (iv) What is the effect of the format of expert knowledge on the OVC task? (Table 4(b) ). Note all our evaluations are conducted on testbeds containing OVCs unseen during training to reflect the actual nature of the setup.Table 2 reports ROLEX's performance when different pre-trained LMs are fine-tuned as generators for the three different OVC tasks. For each model, we compared a baseline generator that parses FL from NL without additional context against the corresponding ROLEX generator. All generators were trained using the TRANSFER LEARNING method, where we first train the model to extract lexicon followed by training it on the downstream task (see section 4.2). For the retriever, we used the large variant of the BGE model, which was fine-tuned for the lexicon retrieval. Without dynamic knowledge, models fare poorly on the OVCs across all three tasks. The results also show that ROLEX yields substantial improvements on the OVCs as well as on the overall generation, when compared to the baseline that does not use any additional knowledge. In NL2LTL, for example, the gains range from 20% to 38% in OVC F1. These improvements show that ROLEX uses the dynamic knowledge during inference to address the OVC issue. Table 3 (a) shows the results of few-shot LLMs as generators in three settings: (i) no external knowledge is provided, (ii) bm25 retriever (Robertson et al., 2009) is used to retrieve external knowledge, and (iii) fine-tuned bge-large retriever (ROLEX) is used to retrieve the external knowledge. We provide three few-shot examples. We observe consistent gains in both OVC F1 and the overall target generation BLEU for ROLEX against baseline and when using an bm25 retriever. GPT-4 + ROLEX gave the best performance on the dataset, even against fine-tuned versions. However, we observe that the best fine-tuned ROLEX (T5-base) from Table 2 performed better than both few-shot LLM baselines. While adding ROLex to GPT-4 performs the best, we find that T5-base with ROLex has similar performance to that of ChatGPT with ROLex. These results suggest the potential of smaller models fine-tuned with ROLEX when compared to significantly larger models.We analyzed the different components of ROLEX to justify our design choices. All analyses were conducted on the NL2Code benchmark using the Code-T5 base as the ROLEX generator. Finally, we studied the potential gains of ROLEX for each benchmark.Retriever Analysis: Table 3 (b) reports the top-10 recall (R@10) performance of different retrievers, and the precision, recall and F1 for the OVCs in the downstream task. We tried bm25, BGE-small and large retrievers, both with and without fine-tuning. We observe that dense retrievers (BGE) outperform BM25 by at least 15% on retriever recall. Fine-tuning and increasing model size also lead to improved performance. We can also see that improved retriever performance translates to better downstream task scores. As the best retriever performance is quite low, improving retriever performance is a direction worth pursing to do well on the OVC parsing task. Further details are given in Appendix Section F.We saw that retrieving the relevant lexicon is challenging, so we want generators that can generate the target based on the noisy retrieved knowledge.For this, we evaluated four different generator training strategies: BASIC Directly using the retrieved knowledge to train the generator. EXTRA SUP. Using extra supervision by mixing in instances with only the gold knowledge. MULTITASK Getting the model to focus on the relevant knowledge via multi-task learning. TRANSFER Getting the model to focus on the relevant knowledge via a transfer learning approach. Model performance on these four approaches is reported in Table 4 (a). From the table we observe that (APPROACH 1, 2) are not up to the mark, whereas multi-task and task-transfer learning show substantial improvement over the first two. Based on the experimental results we choose the transferlearning approach as our go-to generator training approach as it provides the best balance between the OVC F1-score and overall parse quality.How useful is the lexicon based encoding of knowledge?: In Table 4 , we analyze different forms of retrieval context to help models overcome OVC issues. We trained generators to use exemplars (Parvez et al., 2021) (EXEMPLARS) and documentation (Zhou et al., 2023) , the lookup key in our lexicon, (DOCS); (see Appendix Section G for details). The results show that while exemplars have better overall BLEU, ROLEX with lexicons (LEX) gets the best performance on OVCs. This is because the (spec, FL) exemplars only provide generic signals about good parses and not specific information about how to represent the OVCs in the test sentence. Also, lexicons are better than just documentation as context, in part due to the succinct description of the relevant information needed to connect the NL to the corresponding FL construct.In a standard feedback system the expert has to read every output and correct each erroneous OVC. ROLEX aims to reduce this burden on the expert by making the feedback reusable. We calculated the maximum possible percentage gains in saving human effort (treating reading and correcting entries as unit-cost actions) for each of the fine-tuned benchmarks and for the few-shot scenario. We observe 24.3% savings for NL2TL, 5.6% for NL2Code, 11.9% for NL2CMD, and 32.9% for few-shot learning in NL2LTL. These results indicate that dynamic user feedback is a fruitful direction worth pursuing in settings where the OVC problem is prevalent. Please see Appendix Section H for more details on these results.Error Analysis of OVCs: For the NL2LTL task, we analyzed the OVC errors for 25 T-base generations with the lowest BLEU scores. We observed that 23.3% of the errors were due to relevant expert knowledge in the retrieved lexicons not being used for generation. About 23.3% of the errors can be attributed to incorrect lexicon from the set being used. Almost 46.7% incorrectly generated OVCs were due to generator hallucination. For NL2Code we find that 56% are cases where relevant retrieved lexicons are not used, 28% are cases where relevant lexicons are not retrieved and 16% where an incorrect lexicon is used. This analysis shows that ROLEX's ability to use lexicons and not hallucinate are key issues to address for better performance. Further details are given in Appendix Section I. 
conclusion & future work: 
 Formalizing specifications requires expert feedback because of OVCs not resolvable a priori without domain knowledge. In this work, we propose a new dynamic knowledgeaugmented parsing setup and a RAG model to tackle the OVC problem. We show how our approach addresses the OVC issue by accumulating small, reusable expert feedback as a lexicon. Furthermore, we analyzed different training schemes to develop our model. Evaluations on multiple benchmarks highlighted the challenge of our new parsing setting and demonstrated our approach's ability to address it. However, there is further room for improvement, especially in developing models that can better utilize expert knowledge, and are generalizable to more domains both in terms of generation and retrieval. We also hope our new problem setup spurs future research not only on improved modeling but also on user-centric evaluations of feedback-based parsers. 
 
 Appendix: The details about each dataset are given below:NL2LTL: The task was to parse specifications of NFS operations into Linear Temporal Logic (LTL) statements. Obtaining training data is expensive, so we used the synthetic data generation process outlined in Section 4.1. We describe the grammar (Figure 3 ) and generation process above, in Section A. The OVCs in this task were names of function predicates (verbs) and a subset of variables (nouns), as indicated in red in our grammar. We evaluated the model (trained on synthetic data) on a test set of 100 real NFS requirement statements sampled from Ghosh et al. (2022) and annotated with their LTL expression by a group of experts (three university professors and two graduate students).The task was to parse natural-language specifications to Python code. Here, Python function names were the OVCs. We used the CoNaLa training and test cases from Zhou et al. (2023) for data augmentation. To add expert knowledge, we used the documentation database provided with the dataset. The expert lexicon was designed such that the keys were the first 200 characters from the documentation of the corresponding function, and the values were the function names. We used the pre-defined test sets, as they contained functions unseen during training, thereby simulating OVCs.The task was to parse natural-language queries into Bash statements. Command names such as cat, ls, etc., were used to simulate OVCs. We used the TLDR dataset from Zhou et al. (2023) for our experiments. As training data is available, we augmented it with expert lexicons to train ROLEX. The lexicon key was a concise natural-language statement describing the command, created by taking the first line from the tldr page for the command. The lexicon's value was the command name. We tested with the predefined test sets from the TLDR dataset, as it contains the OOD command names needed to simulate OVC.Table 5 shows examples of natural-language input, formal-language output, and the gold expert-knowledge lexicon from each task dataset that was used in our simulations. Table 6 shows further details about the number of data rows available/used for training and testing ROLEX.TASK 1 -NL2LTL Further details of the evaluation setup are given below:Retriever Training: We utilize the small, base, and large variants of FlagEmbedding models (Xiao et al., 2023) , which are sentence transformers (Reimers & Gurevych, 2019) trained by BAAI. The dense retrievers are trained in an in-batch constrastive fashion using the loss function in Section B. The retriever was trained for 5 epochs using a batch size of 32 and a learning rate of 1e-5.We have two types of generators: fine-tuning and few-shot. For fine-tuning, we train T5 and Code-T5 models. Each model was trained for 1 to 10 epochs with learning rates of 1e-4 and batch size of 16 to 64. The models were trained on an NVIDIA A6000 GPU for a total of approximately 24 hours. For few-shot learning, we used ChatGPT and GPT-4 in an incontext learning setup by providing three incontext examples and generation temperature of 0.01.Following are further details of the metrics used for evaluation:BLEU: For measuring the quality of the overall parse by the models, we EVALUATE the BLEU metric of the parse. We utilize the evaluate library of Huggingface and calculate the Sacrebleu (Post, 2018) metric for the NL2LTL and NL2CMD datasets. For the NL2Code dataset, we use the BLEU metric system and tokenization in the Docprompting paper. The formula for BLEU is as follows:Code and data are available at https://github.com/StonyBrookNLP/rolexhttps://tldr.sh/ 


Decision: The authors examine parsing problems where the parser must utilize constructs not known at training time, such as the use of API not know during training. They assume access to user feedback in the form of a lexicon (e.g., NL expresssion -> function name), which accumulates over time from previous model iterations and is accessed in a RAG / non-parametric manner.

The apporach, though not ground-breaking, is is sufficiently novel, even if the problem is somewhat niche, as acknowledge by reviewer. The paper is well-written, with no concerns about the evaluation or reliability of the findings. Several suggestions for improvement are provided, including better positioning with respect to previous non-parametric metrics, such as the work by Das et al. (2021), which also considers an online/dynamic setup and extending the discussion of RAG.

Reviews: review: paper_summary: paper_summary: This paper presents a method to insert open-vocabulary constructs i.e. constructs such as names of methods/functions at inference time to a LLM during generation. The goal is to do a more controllable generation where practitioners can correct mistakes or change behavior (e.g. asking it to use np.linalg.solve when the default gen is scipy.linalg.solve). The paper advocates storing these feedback/expert knowledge in a key-value store and trains a retriever to retrieve from the store and a generator that uses these retrievals to produce generations with the desired behavior. The memory grows as an expert keeps updating the memory and the retriever can retrieve from the growing knowledge. The basic idea being that an error once fixed because of edits will not be made again as the edits can be retrieved from the memory. The retriever is based on standard sentence-transformers (BGE) and for generators T5-based models as well as ChatGPT is used. 

The paper evaluates on three semantic parsing/program synthesis tasks and shows impressive performance gains with the retrieval from feedback memory.
strength_weakness: strength_weakness: 1. Novelty: The proposed solution is not novel and this approach is known to the community. Having a memory of feedback and using them with a RAG-based approach is a nice solution but it has been explored before (e.g. Mishra et al 2022 and Das et al 2021). It would be nice if the author clearly differentiates their work from other existing work.
2. The paper is motivated with a human-in-the-loop set up but the experiments are done by deriving data synthetically. While it was enough to show that the idea works but it would have been nice to do some actual human-in-the-loop experiments. I am guessing there are other practical considerations which gets left out when the experiments are conducted in a simulated scenario. 
3. The paper has considered fine-tuning the retriever on the knowledge stored in the feedback memory. Do you have a sense if the retriever become specialized for this domain and loses it general ability to retrieve from general documents? In other words, does fine-tuning in general have any adverse effects on generalizability?


References
* Das et al 2021: Case-Based Reasoning for Natural Language Queries over Knowledge Bases (refer to Sec 3.4)
* Mishra et al 2022: Towards Teachable Reasoning Systems: Using a Dynamic Memory of User Feedback for Continual System Improvement
paper_summary: paper_summary: The paper presents an approach to handling open-vocabulary constructs in semantic parsing, based on gathering expert feedback provided at inferene time. In particular, the paper presents (i) a semantic parsing setting called dynamic knowledge-augmented parsing, where said expert feedback needs to be taken into account, and (ii) a retrieval-augmented generation model to tackle the task via a key-value lexicon where keys are descriptions of OVCs and values are the desired responses. Experiments on a range of tasks show that the proposed approach provides good performance.
strength_weakness: strength_weakness: The problem is somewhat niche - one does not often have high-quality expert feedback at inference time.
questions: questions: A few typos:

p.1: an linear -> a linear

p.3: problem,s -> problems,

p.9: the for OVC errors for -> extra "for"
paper_summary: paper_summary: The paper presents a study on the problem of Open-Vocabulary Constructs (OVCs) in the context of converting natural language (NL) specifications into formal languages. The authors propose a dynamic knowledge-augmented parsing (DKAP) problem, where a model receives input sentences and a dynamically growing expert knowledge lexicon that associates NL phrases with correct OVC constructs. The proposed approach, ROLEX, is a retrieval-augmented parsing method that uses this lexicon. The authors also introduce a new evaluation paradigm modeled after the DKAP problem and simulate the scenario across three formalization tasks: NL2LTL, NL2Code, and NL2CMD. The evaluations show that DKAP is a challenging problem, and ROLEX helps improve the performance of baseline models by effectively using dynamic expert knowledge.
strength_weakness: strength_weakness: 1.	Potential Overfitting: The paper mentions that the proposed method is trained to use the knowledge as it becomes available, without having to retrain every time a new construct is handled. However, this could potentially lead to overfitting, as the model might become too specialized in handling the constructs it has seen before, and perform poorly on new, unseen constructs. The paper could benefit from discussing this potential issue and proposing ways to mitigate it.
questions: questions: 1.	The RAG part is not described in detail. How is the lexicon built? How big is it? Are all lexicons OOV? When retrieving, how to deal with the situation that contains multiple lexicons?

Comments: title: A gentle ping on our response to your feedback.
Thank you for the detailed comparison
A gentle ping on the above clarification with respect to Das et al., 2021
Thank you.
Thank you for the comment
Thanks for the clarification
comment: Dear reviewer,

We thank you for your constructive feedback. We hope our clarifications above address your concerns. We are happy to answer any additional questions you may have. 

Thanks for your time in helping us improve the paper.
Dear authors,

Thank you for the detailed comparison. Yes, this makes sense and I understand the differences clearly. Please update the paper accordingly. I have updated my score as well.
Dear reviewer

We were wondering if you had a chance to look at the clarifications regarding Das et al. 2021. 

We believe our work shares similarities with the experiment in Das et al., 2021, but our work mainly focuses on OOV problem and addresses the important distinctions that arise in the problem settings we consider. As mentioned above we will add these discussions to the related work in the final version. We hope this addresses your concern in this regard. Thanks again for your constructive feedback on our work.
Thanks for your constructive suggestions. We will add these to final version.
In Das et. al 2021, the general methodology proposed in Section 2.2 (specifically in “Details of Input”) proposes their RAG solution in a static database setting. However, in Section 3.4.2, they motivate a HIL setup where they acquire example cases for unseen entities to improve upon the OOD test cases only. These examples are obtained from another dataset (SimpleQuestions) and users with knowledge about the KB. Their main motivation is to show that their method can improve performance without retraining by just expanding the database with relevant examples. We could not add these details in the main response due to the character limit. However note that their method and evaluation are still significantly different from ours:
* Our whole setup and evaluation assume a dynamic memory that grows from zero as new out-of-vocabulary constructs are seen and corrected with streams of test inferences to address the out-of-vocabulary scenario explicitly. This is unlike Das et. al 2021 who did an added HIL experiment to show that their idea can be expanded to dynamic memory. 
* Their HIL feedback requires writing whole train cases whereas ours requires the expert to add a small idiomatic description and the construct value as a lexicon. This is more efficient and effective in our use case, as shown in our results in Table 4(b).
* Das et. al 2021 generator incorporates a Kullback–Leibler loss function to reduce the difference between when cases are provided and when they are not. This loss, while suitable for their setting, is inappropriate for ours. This is because, in our case, we want the target formalism to explicitly use the open-vocabulary constructs defined in the lexicon feedback, even if it means that there is a significant deviation from baseline (models which do not use feedback). Hence, we formulate training schemes that teach the model to use feedback/knowledge more effectively (detailed in Section 4.2 of our paper).
* Das et. al 2021 also propose a revise step when modeling to specifically address the issue of domain mismatch when parsing NL to LF. They do this by aligning generated relations with relations present in the local neighborhood of the query entity in the KG, discovered via proximity between sentence embeddings. Hence, this modeling step is only suitable for their problem setting due to the nature of knowledge graphs. It is not ideal for our setting.

We thank the reviewer for pointing out the HIL setting, present in Section 3.4.2, in Das et. al 2021. We also thank them for engaging in this conversation which helped make our paper stronger.
Thank you for the response. Please address them in the paper as well and try to clearly differentiate from the aforementioned related work. Also I revisited Das et al 2021 recently, and I am not sure that their experiment is in a static setting.

I have decided to keep my scores the same. Thank you.
Thank you for the clarification. I do think making this more explicit in the final version, if accepted, should make the motivation of the paper clearer.

I am not updating my score at this point, since it was already quite positive.