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 Smolka
Niranjan Balasubramanian
Venue: COLM (2024)
Keywords: Open Vocabulary Constructs, Retrieval Augmented Parsing,
TL;DR: We propose a ROLex, a retrieval augmented parsing mechanism, to handle open vocabulary construct (constructs not known before encounter) problem in formalizing specifications such as Linear Temporal Logic, Python code etc.

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.

Published as a conference paper at COLM 2024
Handling Open-Vocabulary Constructs in Formalizing Speci- fications: Retrieval-Augmented Parsing with Expert Knowl- edge
Mohammad Saqib Hasan', Sayontan Ghosh', Dhruv Verma", Geoff Kuenning', Erez Zadok",
Scott A. Smolka' & Niranjan Balasubramanian"
Department of Computer Science, Stony Brook University Department of Computer Science, Harvey Mudd College (mdshasan, sagghosh, dhverma, ezk, sas, niranjan] @cs. stonybrook. edu, geoffêcs hmc. edu
Abstract
We study the problem of Open-Vocabulary Constructs (OVCs) not known beforehand-in the context converting natural language (NL) specifications into formal languages (e.g., temporal logic or code). Mod- els fare poorly on OVCs due to a lack of necessary knowledge a priori. In such situations, domain expert can provide correct constructs at in- ference time based on their preferences or domain knowledge. Our goal is to effectively reuse this inference-time, expert-providee future parses without retraining the model. We present dynamic knowledge- augmented parsing (DKAP), where in addition to the input sentence, the model receives (dynamically growing) expert knowledge lexicon that associates NL phrases with correct OVC constructs. We pro- pose ROLEX, retrieval- -ugiieeel---ugeeeedddde parsing approach that uses this lexicon. A retriever and a generator are trained to find and use the key-value store to produce the correct parse. A key challenge lies in curating data for this retrieval-uugmented parser. We utilize synthetic data generation and the data augmentation techniques annotated (NL sentence, FL statement) pairs to train the augmented parser. To improve training effectiveness, we propose multiple strategies teach models to focus the relevant subset of retrieved knowledge. Finally, we introduce a new evaluation paradigm modeled after the DKAP problem and simulate the scenario across three formalization tasks (NL2LTL, NL2Code, and NL2CMD), Our evaluations show that DKAP difficult challenge, and ROLEX helps improve the performance of baseline models by using dynamic expert knowledge effectively
knowledge for
key-value
1 Introduction
Formalizing natural language (NL) specifications is 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. 20 Wu al. 2022). Modern parsers for these tasks are modeled
using Seq2Seq (Hlh et al. 2021 lrving et al. 2016 He et al., 2022) models, which take the specification input and output a formal representation
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 not known R priori. This is due to either poor training data coverage or 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 (STI.) (He et al. 2022). This is due to phrases that cannot be
Code and data available httpaa/s///gthhtht.///t/t/ere/oe

---

Published as a conference paper at COLM 2024
NL to LTL
Code
lis_ regular)))
np.linalp.sovve
if the current filehandle
AUWAYS | of Inreguoor
the squares solution of matrices
scipy lnnig solve (op a.
[a]
not reguiar file an error is returned.
Regulaar Parser
(b)
Regular Parser
return/erro)
rp.dottaT,
Input
Output
Input
Output
Expert knowledge
Expert knowledge
(regular file re_
[ Solve linear matris equation nimpl. Salve)
(c)
(d)
the current Flehandle regular
A
Find least squares
is_ reguinjff])
np.linala.sohve (rp.dotia,, a), np.dorjaT,
ROLex
solution of
ROLex
erron's retumed.
returneeror)
matrices A and &
Input
Oufput
Input
Output
Figure 1: ROLEX practice: We 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 !rs_ (15_REGULARR but the model generates != REGULAR. Similarly for NL2Code, the model uses SCIPYLIN of NUMPY. LAA.L..INAL..SO....
instead 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 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 list, making it 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 illussraats the use of OVCs with an example from Network File System specifications (Sheller 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- ToggueeTillan Iillustrates an example where a regular model might use linear algebra implementaiion from the SCIPY library, whereas the user would prefer a NUMPY implementation due to its availability or runtime requirements.
Code portion of Figure
OVCs present a challenge that is fundamentally different from previously studied out- of-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 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 documentation (Zhou et al. 2023) as 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 domain-adaptation techniques that use in-domain exam- rely on models' generalization to generate the OVC construct given in-domain examples. This generalization, we argue, is hard challenge for the types of OVC settings we consider, where deep domain expertise and user preferences impact construct design and choice.
plars (Parvez et al. 2021 Passuat et al. 2021) in saweeeallauuggeeeddggeeeeee
To address the OVC issue, model needs feedback from the user about the correct construct. In traditional beedback-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 parsing setup, which we call dynamic knowlledge-augmentee
a new knowledge-auggeenee parsing (DKAP). In regular knowledge-augmented parsing, 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. DK presents a realistic scenario
2

---

Published as a conference paper at COLM 2024
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 retrieool-augmented generation (RAG) framework, to help parse OVCs. ROLEX collects small amounts of feedback from the expert based the errors made by the parser when translating OVCs. This feedback, designed as key-value lexicon, represents knowledge from the expert for the model use in translating an OVC in future parses. The key is generalized NL phrase or description of an OVC; the value is the correct construct. 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 encountered in a future parse, the previously stored knowledge is used to generate the correct parse. Figure 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 acToss several benchmarks from various semantic parsing domains: NL-to-LLiner Temporal Logic (NI.2TTL), NL-to-Bash commands (NI22CMD), and NL-to- Python code (NI.2Code). The simulations were done in the DKAP scenario and in the presence of out-of- -ittiiiiitiiittoonn 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-nugmenter parsing (DKAP) that accounts for grow- ing user-provided
-ime knowledge; (2) presents 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.
2 Related Work
Out-of-Distrbutiion (OOD) and Zero-Shot Semantic Parsing: Works like Spider (Yu et al.
2018) (Text2SQL) and Docprompting (Zhou et al. 2023) introduce out-of-distributio (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 (021) incorporate entity tags, and Bogin et al. (2021)
train LMs to learn syntactic structure parsing. feer/ 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.
Domain Adaptation in Parsing: Researchers have proposed domain adaptation in semantic
parsing via retrieval-augmmened generation using exemplars (Pasupat et al. (001)) or meta- learning (Chnn et al., 2020b). (Shi et al. 2022) address cross-lingual TextZSQL with RAG using source domain exemplars for solving target domain queries, 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
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
3

---

Published as a conference paper at COLM 2024
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-Augmenter 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 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 contidence 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 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 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. (202),, which introduces OVC arguments in role prediction problems, and Simig et al. (2022), which introduces the OVC problem in classification problems with 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 Krishnamurtyy & 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 -ustr--distribution entities in limited fashion. Dalvi Mishra et al. (2022) use dynamic memory of feedback for open-domain QA. While similar the above two in using RAG-based solution 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 compact feedback format using key-value lexicons.
3 Handling OVCs with Dynamic Knowledg--Aumennte 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 (egg,, NL to Linear Temporal Logic (Brunello al. 2 and (ii) text-to-code (e.g., NL to Python code (Yin et al., 2018)).
In formal specifications, the NL constructs are often domain-specinn (i.e., tied to the specific software being verified) and thus a generic fixed list is not particularly useful. Also, for 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 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, user might prefer to use different implementation (e.g., pre- ferred Python library) than what the model was trained on, implement their own method, or use 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 specs require construct encountered at test time.
3.1 Dynamic Knowledge-Augmented Parsing: Problem Definition
To address this challenge, we introduce the Dynamic Knowleedge-Aggeente Parsing Problem (DKAP), which includes the following changes to the standard semantic parsing setup: (i) Dynamic growing knowledge: When parsing given test sentence, the models use dynamically growing knowledge base, which records all knowledge provided by the user for the open vocabulary constructs encountered in previous sentences. (ii) Reuse without
4

---

Published as a conference paper at COLM 2024
Domain
NL
LEX
HL
If the current filehandle is not regular file, an er- ror will be returned to the client.
(current filehandle
cfh), (A regular file
ALWAYS(( regullaal))))))
NL2LTL
is regular(A)), (A
( (eeuurn(error) ))
returned - return(A))
get the dot product of two
{ Dot product of two ar-
np.dot(aI,, (None)], b((None),
NL.2Code one-dimensional numpy ar- rays
rays ... -numpydot)
=])
Table 1: Example of natural language specification (NL), relevant expert lexicons needed for parsing (LEX), and translated formal language statement (FL) from NL to LTL and NL to Code domain.
retraining: To reduce the user's burden, we assume that they provide knowledge about 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 @emprrialll 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 stream of NL sentences X (x,..... XN) In the standard parsing problem, model produces an output yı, conditioning only on the input x,. In DKAP, when parsing the sentence Xt, the model is additionally given access to expert knowledge K the accu- mulated knowledge for all open-vocabulary constructs that appeared in the input sentences (x,,-.. ,t-1). For X,, a model is thus expected to generate the output y/, conditioning on both x; and the expert knowledge K1:-1.
3.2 Representing Dynamic Expert Knowledge Using Lexicons
We designed simple and concise text-to-construct mapping record feedback in the form of an experf lexicon. The keys in the lexicon are generic, idiomatic natural-language phrases; the values correspond Example lexicon entries from two domains, NL2LTTL and NL2Code, are shown in Table [ The NL.2TL example, from the Network File System (NFS) domain (Shepler et al. 2003 shows that the lexicon entry (A IS REGULAR FILE IS REGULAR(A)) designating that
the correct (i.e., desired) formal representations for the OVCs.
any phrase resembling A IS A REGULAR FILE should parsed to construct is [S_RECULAR) with the argument being the entity A. Similarly, for NL2Code, the lexicon ( Dot product of two arrays -ommpy.dot) indicates that the dot-product function from the NUMPY library should be used if the specification requires it. Formally, when parsing Xt, the available knowledge is given by K1 ((k; e;)) "h11 where m,-1 is the total number of unique OVCs seen until x;-1 Each key k; is generalized natural-language phrase representing an OVC, and o, is its corresponding expert- expert-provided formal representation.
4 Retrieval-Augmenter Parsing with Expert Lexicons
To address the DKAP setting, we need models that can take an input NL specification x and the current state of the expert lexicon database K1n-1 at T = f and produce a semantic parse yr that includes the appropriate OVC constructs from K1 simple solution is to fit the entire knowledge K1:-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 NES RFC specifications. Second, adding the entire K1I-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 K1;-1 as input.
Therefore, we propose ROLEX, Retrieval-augmeeted generation parsing with expert- provided OVC lexicons, illustrated in Figure 2 using examples from the NES RFC. We
can fine-tune LMs such as T5 (Raffel et al. 2020 or Code-T5 (Wang et al. 2021), or few-shot
prompt LLMSs like ChatGPT 20penAl/20333 and GPT-4 (ppenAl)20233) for the generator

---

Published as a conference paper at COLM 2024
Dynamic Krowledge Base
esids,
GENERATOR
duplicaeeshhh
domainnsppeee construct pr preference.
cxloestch))
Dynemic
Krowledge Bes
reguler
RETRIEVER
Correctly predicted
construct rousing
previoushy ot
theee steed Iiehandle, then return the ererr ertrr NISSERR, RESTOREHH.
A MAAS (1 NOT laaved Hibhnndl ))
retorsttSSATE RESTODETHE))
Figure 2: Dynamic knowledge-augmentee parsing using ROLEX: Our RAG framework for inference-time knowledge-augmentte parsing through expert lexicons. We start at with an empty lexicon. The generator thus parses the first NI NI. specification with empty retrieved knowledge to produce formal statement. This generates error (highlighted in red): "duplicate exists" is incorrectly parsed DUPLICATE(), whereas the domain expert prefers "exists(X)", This partial-knowledge entry added the dynamic knowledge base and gets reused appropriately later time step T f, as shown the lower block.
module, and use dense retriever models (Gao et al. 2021 Karpukhin et al. 2020) for the re- triever. The main challenge lies in obtaining training data. To address this, we synthetic data generation and data-augmentattio techniques. To develop the retriever and generator modules, experimented with several methods, explained next.
4.1 Dataset Creation and Augmentation
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, Ky), where Ky S 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.
Synthetic Data Generation: In some semantic parsing use cases, such as formalizing RFC speciicattins, manually curating (x, y) pairs and lexicons for OVCs can be difficult. However, due to the restricted nature of the parses, we curate synthetic data via grammar-based generation (He et al. 2022), We do this by developing a synthetic grammar adapted to the target domain. For example, we have shown that such grammar can be used to model LTL statements generated from the NES domain. Details of the grammar are provided in the Appendix Section
Data Augmentation Setting: with the gold lexicon K for each pair. We do this by first defining the OVCs and their formal representations, and then using 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 comprehensive lexicon knowledge base and then use to enumerate each (x,y) pair with the relevant K.
If training data with y) pairs exist, we can augment them
4.2 Developing the RAG Modules
Retrieval Module: We use sentence transformers (Reimers & Gurevych 2019) as our dense retrievers in two ways: off-the-shelf and fine-tuning. For ohe-lle-shelf usage, plug in

---

Published as a conference paper at COLM 2024
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, using our curated (x, K, data pairs. Given K = {k, };)] where kj is the natural- language grounding phrase and 8j is the OVC's formal representation, we create )- tuples for each x. This tuple store is then used to fine-tune a retriever using contrastive learning (Henderson et al. (017) with in-batch negatives (Karpukhin et al. 2020 Chen et al.
opt for fine-tuning the retriever
seeeeiiveee.eee 2020a) (see the Appendix Section B for the training objective). The retriever is &inne-tuned
to include all K gold lexicon entries in its top ranked lexicon entries.
The Generator 9 is a language model that should generate the semantic parse y based on (x, K*), where K* is the list of top и ranked lexicon entries retrieved by R from the full lexicon. Ideally, the generator should be able to identify Ky, 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 (ii) 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 conditioned on x ① K* (2) EXTRA SUPERVISION: From each (x, K",y ,y) training pair, we derive two pairs: (x, K" .y and (x, Ky, This causes G to observe y during training twice- once conditioned to provide an extra supervision signal to G on what are correct lexicons. (3) MULTI-TASK LEARNING: G is trained to generate ky ① 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.
Generator Module:
on x ① Ky and another time on ① K*. The idea
(4) TRANSFER LEARNING: G is trained first to generate ky 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) knowl- edge of OVCs at test time by simulating the addition of knowledge about new OVC after each parse. In this way, subsequent parses can use this accumulated knowledge. Formally, given task TT and possible OVCs O, we create train and test sets, D Dmiin and Drest as per methods in Section 4.1 Each D consists of tuples (x,, y:) where xi the NL, y/ the FL and K, are the gold lexicons. ROLEX is trained on Draii and then evaluated with an initially empty dynamic knowledge base, KB. At time t, the retriever retrieves relevant lexicons K* from K.B, and x x K* is given as input to generate y' Comparing y' and y, we extract and add set of new lexicons Knew E K,, s.t. Knew O KBB = to KBB so that they can be retrieved for parsing at time f 1.
DKAP Evaluation Protocol:
5.1 Task and Dataset Details
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
7

---

Published as a conference paper at COLM 2024
NL2CTL
NL2Code
2L2CMD
Model
All
OVCs
All
OVCs
All
OVCs
bleu
Prec.
Rec.
FT
bleu
Prec.
Rec.
FT
bleu
Prec.
Rec.
FT
T5-B
27.94
39.35
43.42
41.28
18.51
4.89
4.84
4.86
13.17
4.%6
7.22
5.88
ROLEX
53.28
68.67
55.75
61.54
23.02
18.85
20.50
19.64
15.44
25.47
37.39
30.30
CT5-S
30.59
34.83
24.75
28.94
16.90
5.68
5.13
5.39
18.10
3.47
5.39
4.22
+ROLEX
42,95
62.42
43.33
51.15
25.81
15.93
16.17
16.05
22.27
29.10
37.18
32.65
CT5-B
25.15
21.33
14.08
16.97
29.30
14.98
14.30
14.63
26.04
2.46
4.31
3.13
+ROLEX
54.01
63.83
48.00
54.80
31.81
17.35
18.85
18.07
27.11
20.83
32.00
25.24
Table 2: Performance gains in fine-tuned models across three different benchmark tasks due to ROLEX. Bleu All was evaluated for the complete model output expression, whereas OVC's 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 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
5.2 ROLEX Benchmarking Setup
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 15 for the fine-tuned setting and ChatGPT and GPT-4 for few-shot. For evaluation, 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
6 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? Tables2[ande a))) (ii) What is the effect of retriever performance on the overall downstream task performance? (Table ())) (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()).. Note all our evaluations are conducted on testbeds containing OVCs unseen during training to reflect the actual nature of the setup.
6.1 Results with fine-tuned LLMs
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 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.
Phttps:/ /tldrs//
8

---

Published as a conference paper at COLM 2024
Retr. R@10
OVCs
Retriever
All
OVCs
Prec.
Rec.
F1
Model
BLEU
Prec.
Rec.
F1
Off-the-shelf
C
42.23
56.70
38.14
45.61
-bm25
2.59
10.88
10.44
10.66
+bm25
51.27
67.18
50.00
57.33
-small
17.91
13.64
13.59
13.62
+ROLEX
53.03
71.43
53.26
61.02
-large
18.81
14.20
14.62
14.40
GPT-4
46.98
61.86
39.60
48.29
Fine-tuned
+bm25
62.10
79.64
70.02
74.52
-small
19.37
15.30
15.33
15.31
+ROLEX
66.38
78.87
75.43
77.11
-large
20.38
17.35
18.85
18.07
(a) Few-shot model performance
(b) Effect of retriever performance downstream task
Table 3: (a) Few-shot model performance on the NL2LTL task. Augmenting with ROLEX showed consistent performance improvements across all of the metrics. (b) Effect of retriever performance (top@k recall) on the NT.2Code task with the best-performing model Code-T5-base.
Training
All
OVCs
Feedback
All BLEU
OVCs
Strategies
BLEU
Prec.
Rec.
Prec.
Rec.
Fl
BASIC (1)
29.94
16.56
17.30
16.92
EXMP
33.33
14.98
15.96
15.46
EXTRA SUP. (2)
27.69
15.77
16.80
16.27
ROLEX
MULTITASK (3)
26.53
18.72
21.21
19.89
-Docs
29.54
15.69
15.30
15.49
TRANSFER (4)
31.81
17.35
18.85
18.07
-LEX
31.81
17.35
18.85
18.07
(a) Effect of training strategies
(b) Evaluating different feedback mechanisms
Table 4: (a) Effect of generator training strategy on the downstream task of NL.2Cod,, with BGF-large as the retriever. (b) Evaluating different feedback mechanisms for RAG.
6.2 Results with Few-Shot LLMs
Table 3a) shows the results of few-shot LLMs as generators in three settings: (i) no external knowled ledge 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 Fl and the overall target generation BLEU for ROLEX against baseline and when using an bm25 retriever. GPT-4 + ROLEX gave the best performance fine-tuned versions. However, we observe that the best fine-tuned ROLEX (T5-base) from Table T performed better than both few-shot LLM baselines. While adding ROLex 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.
the dataset, even against
6.3 Analysis
We analyzed the different components of ROLEX to justify our design choices. All anal- yses were conducted on the NL2Code benchmark using the Code-15 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
Generator Training Strategies: 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, 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

---

Published as a conference paper at COLM 2024
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 4a). From the table we observe that (APPROACH 1, 2) are not up to the mark, whereas mu multi-task and task-transfer learning show substantial improvement over the first two. Based on the experimental results we choose the transfer- learning 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 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). he 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.
Estimated Reduction in Expert Effort In 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 fruitful direction worth pursuing in settings where the OVC problem is prevalent. Please see Appendix Section for more details on these results.
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 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
Error Analysis of OVCs:
7 Conclusion & Future Work
Formalizing specifications requires expert feedback because of OVCs not resolvable a priori without domain knowledge. In this work, we propose new dynamic knowledge- augmented 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 '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.
Acknowledgements
We thank the anonymous reviewers of COLM for their feedback which helped improve the paper. This work was possible thanks to the NSF award CCF-1998225.
10

---

Published as a conference paper at COLM 2024
References
Ben Bogin, Sanjay Subramanian, Matt Gardner, and Jonathan Berant. Latent compositional representations improve systematic generalization in grounded question answering. Transactions of the Association for Compulational Linguistics, 9:195-210, 2021. doi: 10.1162/
tacl_a_00361. URL BtLLitttpss/aalaanthoooog.
t tac1-1.12,
Andrea Brunello, Angelo Montanari, and Mark Reynolds. Synthesis of LTL formulas from natural language texts: State of the art and research directions. In 26th International symposium on temporal representation and reasoning (TIME 2019). Schloss Dagstuhl-Leibniz: Zentrum für Informatik, 2019.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple frame- work for contrastive learning of visual representations. In International Conference on Machine Learning, pp. 1597-1607. PMLR, 2020a.
Xilun Chen, Asish Ghoshal, Yashar Mehdad, Luke Zettlemoyer, and Sonal Gupta. Low- resource domain adaptation for compositional task-oriented semantic parsing. arviv preprint arii::2010.03446 2020b.
Yongchao Chen, Rujul Gandhi, Yang Zhang, and Chuchu Fan. NL2TL:
Transforming natural languages to temporal logics using large language models. ar preprint arXiv:2305.07766, 2023.
Bhavana Dalvi Mishra, Oyvind Tafjord, and Peter Clark. Towards teachable reasoning systems: Using a dynamic memory of user feedback for continual system improvement. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 9465-9480, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi:
10.18653 http//222.emlppmmaee 644. URL TRKUhttps://cclaattolloo org/ /2222202222222 e0n2.emmlppppp...mmmmmmmmmmmpppp emnlp- main
644
Rajarshi Das, Manzil Zaheer, Dung Thai, Ameya Godbole, Ethan Perez, Jay Yoon Lee, Lizhen Tan, Lazaros Polymenakos, and Andrew McCallum. Case-based reasoning for natural language queries over knowledge bases. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 9594-9611, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 10.18653/v1, 2021 2021.emmlp-main7755 URL https::/aallanthologg) wrg.orggg/22222 2021 emnnp-main...... 755
Hicham El Boukkouri, Olivier Ferret, Thomas Lavergne, Hiroshi Noji, Pierre Zweigenbaum, and Jun'ichi Tsujii. CharacterBERT: Reconciling ELMo and BERT for word-level open- vocabulary representations from characters. In Donía Scott, Nuria Bel, and Chengqing Zong (eds.), Proceedings of the 28th International Conference on Computational Linguistics, pp. 5903-69155 Barcelona, Spain (Online), December 2020. International Committee on Computational Linguistics. doi:
htwp:/200..ooiii-mmmm...00... URL https://
aclanthology org/ cowlng-maallloooooo main. 609
Tianyu Gao, Xingcheng Yao, and Danqi Chen. SimCSE: Simple contrastive learning of sentence embeddings. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 6894-6910, 2021.
Matt Gardner and Jayant Krishnamurthy. Open-vocabulary semantic parsing with both distributional statistics and formal knowledge. In Proceedings of the AAAI Conference Artificial Intelligence, volume 31, 2017.
Sayontan Ghosh, Amanpreet Singh, Alex Merenstein, Wei Su, Scott A. Smolka, Erez Zadok, and Niranjan Balasubramanian. SpecNFS: A challenge dataset towards extracting formal models from natural language specifications. In Proceedings of the Thirteenth Language Resources and Evaluation Conference, pp. 1166-2176, 2022.
11

---

Published as a conference paper at COLM 2024
Vivek Gupta, Akshat Shrivastava, Adithya Sagar, Armen Aghajanyan, and Denis Savenkov. RetroNLU: Retrieval augmented task-oriented semantic parsing. In Bing Liu, Alexandros Papangelis, Stefan Ultes, Abhinav Rastogi, Yun-Nung Chen, Georgios Spithourakis, Elnaz Nouri, and Weiyan Shi (eds.), Proceedings of the 4th Workshop on NLP for Conversatinal AI, pp. 184-19,, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10. 18653/v1 1B66//11/222nn/tcoovva- 15
URL hntpss://aclanthologyy http://cllannoolooooor////////// org.oogg///// wtwpo22a2aooccoiiiia1aa
Christopher Hahn, Frederik Schmitt, Jens U. Kreber, Markus Norman Rabe, and Bernd Finkbeiner. Teaching temporal logics to neural networks. In International Conference on Learning Representations, 2021.
Jie He, Ezio Bartocci, Dejan Ničković, Haris Isakovic, and Radu Grosu. DeepSTL: From English requirements signal temporal logic. In Proceedings of the 44th International Conference on Software Engineering, pp. 610-622, 2022.
Matthew Henderson, Rami Al-Rfou, Brian Strope, Yun-Hsuan Sung, László Lukács, Ruiqi Guo, Sanjiv Kumar, Balint Miklos, and Ray Kurzweil. Efficient natural language response suggestion for smart reply. ar Xiv preprint ar
2017.
Geoffrey Irving, Christian Szegedy, Alexander A. Alemi, Niklas Eén, François Chollet, and Josef Urban. DeepMath- deep sequence models for premise selection. Advances in Neural Information Processing Systems, 29, 2016.
Robin Jia and Percy Liang. Data recombination for neural semantic parsing. In Katrin Erk and Noah A. Smith (eds.), Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 12-22, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/ 10.18653//1//11111 /1/111-000 URL
https://accaatthooogy.orrs 1902
Yizhu Jiao, Sha Li, Yiqing Xie, Ming Zhong, Heng Ji, and Jiawei Han. Open-vocabulary argument role prediction for event extraction. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Findings of the Association for Computational Linguistics: EMNLP 2022, pp. 5404-5418, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10.18653/ v1 /0222..finnnngg-eennl2.... //aclanthology.orgg org/
https
mem.inngggeenl.... 395
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question an- swering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 6769-6781, 2020.
Kazuya Kawakami, Chris Dyer, and Phil Blunsom. Learning to create and reuse words in open-vocabulary neural language modeling. In Regina Barzilay and Min-Yen Kan (eds.), Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1492-1502, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10.1863//11PP17-1137. URL https:://aclantho...o org/P17-1137
Jayant Krishnamurthy and Tom M. Mitchell. Learning a compositional semantics for Freebase with an open predicate vocabulary. Transactions of the Association for Compulational Linguistics, 3:257-270, 2015. doi: 10.1162 (t12//tacl/ a 00137. URL htttps://ccaatthhhh Q15-1019
org/
Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmented generation for knowledgg-intensive NLP tasks. Advances in Neural Information Processing Systems, 33:9459-9474 2020.
Dheeraj Mekala, Jason Wolfe, and Subhro Roy. ZEROTOP: Zero-shot task-oriented semantic parsing using large language models. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference Empirical Methods in Natural Language Processing,
12

---

Published as a conference paper at COLM 2024
pp. 5792-5799, Singapore, December 2023. Association for Computational Linguistics. doi: 10.18653/v1
URL/ntsss//acannntoooyy.ooo// wwt.:rrrr//..me..ppppmm.... emmlp-mminn
354
OpenAl. Introducing ChatGPT, httts::/ww..pppaaa.cc//cccaatae 2023a. Accessed: 2023- 12-16.
OpenAI. GPT-4 technical report. ArXia, abs/2303.08774, 2023b.
URL https://api
semanticscholar. Corprtttsssssoooooooooooooooooo 257532815
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-ling Zhu. Bleu: method for
automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pp. 311-318, 2002.
Md. Rizwan Parvez, Wasi Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang.
Retrieval augmented code generation and summarization. In Findings of the Association for Computational Linguistics: EMNLP 2021, pp. 2719-2734, 2021.
Panupong Pasupat, Yuan Zhang, and Kelvin Guu. Controllable semantic parsing via retrieval augmentation. Xiv preprint ar Xi1::1110008858, 2021.
Matt Post. A call for clarity in reporting BLEU scores. In Proceedings of the Third Conference Machine Translation: Research Papers, pp. 186-191, Brussels, Belgium, October 2018. URL https
Association for Computational Linguistics. doi:
//aclanthollgg.oorg/BBB.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with unified text-to-text transformer. The Journal of Machine Learning Research, 21(1):5485-555) 2020.
Nils Reimers and Iryna Gurevych. Sentence-BENG Sentence embeddings using Siamese BERT-networks. Xiv preprint arXiv:1908. 1000444, 2019.
Stephen Robertson, Hugo Zaragoza, et al. The probabilistic relevance framework: BM25 and beyond. Foundations and Trends@ in Information Retrieval, 3(4):333-389 2009.
Kristin Y. Rozier. Linear temporal logic symbolic model checking. Computer Science Review, 5(2):163-203, 2011.
Peter Shaw, Ming-Wet Chang, Panupong Pasupat, and Kristina Toutanova. Compositional generalization and natural language variation: Can semantic parsing approach handle both? In Chengqing Zong, Fei Xia, Wenjie Li, and Roberto Navigli (eds.), Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 922-938, Online, August 2021. Association for Computational Linguistics. doi: (0.18653/v1/202// 75. URL https:://cclatthooggy org/2021 acl - -ong. 75
Shepler, B. Callaghan, D. Robinson, R. Thurlow, C. Beame, M. Eisler, and D. Noveck. Network file system (NFS) version 4 protocol. RFC 3530, Network Working Group, April 2003.
Peng Shi, Rui Zhang, He Bai, and Jimmy Lin. XRICL: Cross-lingual retrieval-augmeeted in-context learning for cross-lingual text-to-SQL semantic parsing. In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.), Findings of the Association for Computational Linguistics: EMNLP 2022, pp. 5248-5259, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10.18653/v 20/5///vv//22//// wiwdiiinnninnnnnneee 384. URL
orgh 2022. winiiiinnnnenllpp 384
Daniel Simig, Fabio Petroni, Pouya Yanki, Kashyap Popat, Christina Du, Sebastian Riedel, and Majid Yazdani. Open vocabulary extreme classification using generative models. In Smaranda Muresan, Preslav Nakov, and Aline Villavicencio (eds.), Findings of the Association for Computational Linguistics: ACL 2022, pp. 1561-1583, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 10.18653 v1/202222222222// findiiinnnngaccc ac3.123. URL
www..orrg//222..idnnn-------a findings-acl. 123
13

---

Published as a conference paper at COLM 2024
Yue Wang, Weishi Wang, Shafiq Joty, and Steven C.H. Hoi. CodeT5: Identifier-aware unified pre-trained encoder-decoder models for code understanding and generation. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, Pp. 8696-8708, 2021.
Shan Wu, Chunlei Xin, Hongyu Lin, Xianpei Han, Cao Liu, Jiansong Chen, Fan Yang, Guan- glu Wan, and Le Sun. Ambiguous learning from retrieval: Towards zero-shot semantic parsing. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 14081-14094, Toronto, Canada, July 2023, Association for Computational Linguistics. doi: 10.18653 1112023.acl-lorgg 777... URL https: https:://cclanthology /r2/2023 acl - dell-oog.788 787
Yuhuai Wu, Albert Qiaochu Jiang, Wenda Li, Markus Norman Rabe, Charles E. Staats, Mateja Jamnik, and Christian Szegedy. Autoformalization with large language models. In Advances in Neural Information Processing Systems, 2022.
Shitao Xiao, Zheng Liu, Peitian Zhang, and Niklas Muennighof. C-pack: Packaged resources to advance general chinese embedding. Xiv preprint ar xrXiv:2009.07597, 2023.
Jingfeng Yang, Haoming Jiang, Qingyu Yin, Danqing Zhang, Bing Yin, and Diyi Yang. SEQZERO: Few-shot compositional semantic parsing with sequential prompts and zero- shot models. In Marine Carpuat, Marie-Catherine de Marneffe, and Ivan Vladimir Meza Ruiz (eds.), Findings of the Association for Computational Linguistics: NAACI, 2022, pp. 49-60, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10. 18653 18653/v1/2022/ http:/2222..ining---aaaaee 5
URL httshttss:// http:://aalaathhllgg/oooooo org/ 2022. findings-naacl
Pengcheng Yin, Bowen Deng, Edgar Chen, Bogdan Vasilescu, and Graham Neubig. Learning to mine aligned code and natural language pairs from Stack Overflow. In International Conference on Mining Software Repositories, MSR, pp. 476-486. ACM, 2018. doi: https:
//doi.org/ 1ooo.orgg10.114533 10.1/1/11/////1 //1.111///1669881119999 3196398.3196408.
Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Trene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir Radev. Spider: A large-scale human-labeled dataset for complex and cross-domain semantic parsing and text-to-SQI. task. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 3911-3921, 2018.
Wenhao Yu. Retrieval-augmenner generation across heterogeneous knowledge. In Proceed- ings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Student Research Workshop, pp. 52-58, 2022.
Yury Zemlyanskiy, Michiel de Jong, Joshua Ainslie, Panupong Pasupat, Peter Shaw, Linlu Qiu, Sumit Sanghai, and Fei Sha. Generatee-nd--reriiew Use your predictions to improve retrieval for semantic parsing. In Nicoletta Calzolari, Chu-Ren Huang, Hansaem Kim, James Pustejovsky, Leo Wanner, Key-Sun Choi, Pum-Mo Ryu, Hsin-Hsi Chen, Lucia Donatelli, Heng Ji, Sadao Kurohashi, Patrizia Paggio, Nianwen Xue, Seokhwan Kim, Younggyun Hahm, Zhong He, Tony Kyungil Lee, Enrico Santus, Francis Bond, and Seung- Hoon Na (eds.), Proceedings of the 29th International Conference on Computational Linguistics, pp. 4946-4951 Gyeongju, Republic of Korea, October 2022. International Committee on Computational Linguistics. BuRLLhttpss:/aaaantholoo .rg 2822. coling- 1.lll.g-1144 1.438
Hao Zheng and Mirella Lapata. Compositional generalization via semantic tagging. In Marie-Francine Moens, Xuanjing Huang, Lucia Specia, and Scott Wen-tau Yih (eds.), Findings of the Association for Compulationall Linguistics: EMNNPP 2021, pp- 1022-1032, Punta Cana, Dominican Republic, November 2021. Association for Computational Linguis- wwwpe/....gg/22///
tics. doi: 10.18653/ /v/05//vl// htt.://2...ninnsseeeeeee www..finngneennl....... URL findings-emnlp.
Shuyan Zhou, Uri Alon, Frank F. Xu, Zhengbao Jiang, and Graham Neubig. DocPrompting: Generating code by retrieving the docs. In International Conference on Learning Representa- fions (ICLR), Kigali, Rwanda, 2023.
14

---

Published as a conference paper at COLM 2024
Appendix
A
Grammar for synthetic generation
Tigure3 the custom grammar designed to model and generate the synthetic NL2LTL dataset. We can generate example statements in the language defined by this synthetic CFG by stochastically chaining the production rules beginning with the start symbol. Since the natural-language phrases are also attached to the grammar, the process simultaneously yields the corresponding NL statement for the generated formal statement y. We can create large number of such (x, y) pairs by sampling from this grammar. To simulate the expert-provided knowledge, we augment each pair with knowledge set K that contains random collection of key / /value pairs as distractors, and also the relevant key /value pairs that correspond to specific OVCs appearing in the output y. We can thus control patroo/vaag /vary how the distractors are created.
1.
<start>
G(<phrase>)
G(<phrase> =
<phrase>)
3.
G(<phrase> <phrase> V
<phrase> = <phrase>)
<phrase>
5.
<a> <con> <a>
<a> <con> <a>
<con> <a>
<
<pred>
8.
<b_pred>
<act_preds
10.
<pred>
x xlxox x1 0
11.
+ - 1
- (x1 o x2)
12.
<b ppreed>
x x2 12 A U2
13.
X1 2 X
14.
<<uV U2
15.
x1 < X2 V1 > X3
16.
<act pred>
verb(E) WITH E.<pred>1 E.<pred>
17.
<con>
V
18.
X
var
19.
get ger_ (var2)
20. var
variable
21.
noun
Figure 3: The grammar used to generate the synthetic dataset. Many constructs from general LTL have been reduced for use our problem domain. Constructs created for our domain are highlighted in red. The verb predicate consists of all verbs in the SpecNFS dataset whose operations cannot be defined by any Boolean operation and thus require special functions. get_VAR VAR consists of constructs that capture the "X of Y" statements in the SpecNTS and NFS RFC domains.
B Retriever Loss Function
From Xiao et al. 2023 given p and q are the paired texts, 9 E Q' is a negative example and T is the temperature and represents encodings.
exp exp /pplg//
L = min. Σ
- log
(1)
exp (epa))/ Eg exp lepe,)/T
(1-4)
15

---

Published as a conference paper at COLM 2024
C Task Dataset Details
The details about each dataset are given below:
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 group of experts (three university professors and two graduate students).
NL2LTL:
NL2Code:
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, 1s, 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 with expert lexicons to train ROLEX. The lexicon key was a concise natural- natural-language statement describing the command, created by taking the first line from the tldr page for the command. The lexicon's '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.
NL2CMD:
Table 5 shows examples of natural-language input, formal-language output, and the gold knoweeekn lexicon from each task dataset that was used in our simulations. Table shows further details about the number of data rows available/ used for training and testing ROLEX.
TASK 1 NL2LLL
NL (NFS-RFC specification) If the current filehandle is not a regular file, an error will be returned to the client.
Expert Knowledge (current filehandle + cfh), (A is a regular file + regulla) (A
returned - return (A))
(L Temporal Logic): ALWAYS(C ((is_regularrcfh)) ) ( (return(error) )
TASK NL2CD
NL (Instruction/Querr)) Delete shared memory segment by id
Expert Knowledge: (Delete IPC (Inter-process Communication) resources, -ipcrm
FL (Bash statement) iperm -shmem- id shmem_ic id
TASK NLodde
NL (Instruction/Query)::: divide the values with same keys of two dictionary 'dl' and 'd2' Expert Knowledge: (class float([x]) Return a floating point number constructed from a number or string If the argument is a string, it should contain decimal number, optionally preceded by sign, and optionally e - python. library. functions#float Python: [k: (float
di[k]) for in d2)
Table 5: Evaluation Task Examples: This table illustrates the NL input, target FL output, task example, and expert knowledge from the datasets for each task.
D Reusability in Semantic Parsing
Figure shows the potential for reusing expert knowledge lexicons in an inference-time knowledge setting in the NES RFC domain. The diagram highlights the repetition of knowledge and the potential of reusability of knowledge about parsing OVCS.
16

---

Published as a conference paper at COLM 2024
Retriever Train Set
Generator Train Set
Dataset
Test Set
NES RFC
120k
120k
100
TLDR
8260
8260
928
Conala
2135
2135
543
Table 6: Size of the different training and test sets for each the datasets used in evaluating the tasks.
0.7
0.6
wmw
0.5
PK (%)
150
0.4
Frequency
0.3
0.2
0.1
50
0.0
20
40
60
80
100
switch
cache
prevent consider
(a) Reusability of partial knowledge.
Action construct
(b) Distribution of actions in NFS-RFC
Figure Observing reusability: Analyses of the NFS specifications provides empirical support for the importance modeling semantic parsing in an inference-time left half (a) shows the percentage of reuse that can happen when we collect the formal constructs in the expert knowledge base. As we collect constructs from more sentences, the potential for reuse grows quickly. The right half shows the frequency of action-denoting words (possible OVCs) in specification sentences. There is long tail of words that occur multiple times. Knowledge learned about these once will likely useful multiple times later.
expert-knowlede setting. The
E Evaluation Setup and Metrics
Further details of the evaluation setup are given below:
Retriever Training: We utilize the small, base, and large variants of FlagEmbedding mod- els (Xiao et al., 2023), which sentence transformers (Reimers & Gurevych] 2019) trained by BAAI. The dense retrievers are trained in an in-batch constrastive tashion using the loss function in Section B The retriever was trained for epochs using a batch size of 32 and
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 le-4 and batch size of 16 to 64. The models were trained on an NVIDIA A6000 GPU for 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.
Generator Training:
Following are further details 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 follows:
17

---

Published as a conference paper at COLM 2024
N
BLEU = bp.exp Σ
n log Px)
where by is the brevity penalty, Wn is the weight of each n-gram precision and pn is the precision of each n-gram and N the total number of n-gram precisions considered in calculating BLEU.
To measure ROLEX's ability to use expert knowledge to parse the OVCs, we exclusively calculate metrics related to the OVCs. This is done by first extracting the OVCs from the generated text via pattern matching with the OVCs in the gold lexicon. Then we calculate the unordered precision, recall and F1-score using the following formulas.
OVC metrics:
True Positive
Precision
(3)
True Positive + False Positive
True Positive
Recall
(4)
True Positive + False Negative
Precision x Recall
Score = 2
(5)
Precision + Recall
Note that all OVCs in our evaluation sets are by definition and construction unseen during training and the evaluation metrics above focus only on the OVC performance. Thus all gains observed on these metrics will primarily reflect on the models' abilities to handle ex- pert knowledge effectively during inference time and not affect any knowledge memorized during training.
Gains: ROLEX is designed to be an improved form of feedback system. In regular feedback systems for handling ÓVCs, an expert sits the output helm, reads through each parse, and then provides corrective feedback for each erroneous OVC in the output. ROLEX reduces this amount corrective feedback by reusing feedback from the expert. this way, manual effort is reduced. We formulate automatic way to measure this effort in the following manner: for each parse, the expert needs to spend unit work to read through the whole parse. Then the expert needs to spend unit for each wrong OVC in the output. This number can easily be calculated by measuring the number of false negatives, i.e., OVCs missed in the output. The sum of these two numbers measures the total amount of human effort theoretically required to correct the OVCs. Hence the cost is:
Cost Reading_Coss + Error_Cost
(6)
Retriever Analysis
Table shows the top-k recall on each benchmark dataset for five different set of retrievers: bm25 [Robertson et al. 22099), off-the-shelf small and large BGE sentence transformers from FlagEmbeddings (Xiao et al. 2023), and the fine-tuned versions of the aforementioned two models. We observe that bm25, being lexical retriever, has lowest performance on all tasks. Off-the-shelf dense retrievers perform better, with the large variant doing better than the smaller one except in the case of NL2LTL dataset. However, the best performance is obtained with the fine-tuned retrievers. This indicates the necessity of retriever training for our task.
G Feedback Methods
Table compares ROLEX using lexicons with two other methods: exemplar and ROLEX using docs.
18

---

Published as a conference paper at COLM 2024
Downstream
Dataset
Retriever
Ree
Re05
Re01
Re220
bm25
1.92
9.13
12.50
17.79
Off-the-shelf
-bge-small
7.21
15.38
23.56
40.38
N12L
-bge-large
6.25
17.79
24.52
36.54
Fine-tuned
-bge-small
11.54
30.77
43.75
47.12
-bge-large
14.42
36.06
44.71
50.00
bm25
1.72
5.28
11.53
24.25
Olf-the-shelf
-bge-small
40.19
57.97
63.25
68.64
NL2CMD
-bgesmmal((FT)
46.34
63.69
68.75
72.84
Fine-tuned
-bge-lrge
41.27
59.27
65.30
69.94
bge-large(FT)
52.59
68.86
72.20
75.32
bm25
0.34
1.35
2.59
5.29
Off-the-shelf
-bge-small
9.57
16.22
17.91
19.59
NL2Code
bge-small(FI)
11.15
18.13
19.37
21.51
Fine-tuned
-bge-large
9.23
16.67 18.69
18.81 20.38
20.27
-gge-large(FT)
11.37
22.18
Table 7: Top-k recall performance (R@k) for different sets of retrievers each benchmark dataset.
Examplar refers to training the generator to use retrieved pairs of input-output context during retrieval augmented generation. The idea comes from Pasupat et al. (2021) where the authors retrieved similar input-output pairs for semantic parsing, In our case, an off- the-shelf BGE large retriever used retrieve (specification, code) pairs from the training
set of NL2Code to augment the training data with relevant context for training. Afterwards, during testing, the test input is augmented with these examples retrieved from the original training data.
The ROLEX with docs idea comes from the paper Zhou et al. 2023 where the models are conditioned to learn to documents to overcome the OOD problem. For the NL2CCde task in Table we simply used the key of our lexicon as the document. The retriever used is the fine-tuned BGE large used in ROLEX + lexicons use-case. The generator conditioned only upon NL @ key.
H Gains Analysis
Table the gains calculated per our metric defined in 5..2ion55.21anm and elaborated in Section E. For each dataset in the fine-tuned setting, we select the model with the highest difference in performance on OVCs. Then we calculate the reading cost and feedback cost. Reading cost is equal to the size of the dataset while feedback cost is equivalent to the false negative among the OVCs. This then added to find the total. The percentage reduction between baseline and ROLEX is then calculated. We see 24.3% savings for NL2LTL, 5.6% for NL2Code, 11.9%for NL2CMD, and 32.9% for few-shot learning NL2LTL. This shows the potential of ROLEX in reducing human effort.
I Error Analysis
Table/]shows the detailed error analysis on the OVCs for the NL2LTL and NL2Code datasets. We selected the best models for each dataset, T5-Base and Code-T5 Base respectively, and analyzed the 25 most erroneous outputs. Four categories were identified as common emrors: expert lexicon is available but not used, incorrect expert lexicon is used, expert lexicon is
19

---

Published as a conference paper at COLM 2024
Dataset
Model
Reading
Error
Total
Reduction
CT5-B
100
180
280
NL2LTI.
+ROLEX
100
112
212
-24.3%
15-B
543
345
888
NL2Code
+ROLEX
543
295
838
-5.6%
CT5-S
928
631
1559
NL2CMD
+ROLEX
100
59
159
-11.9%
GPT-4
100
137
237
Few-shot
+ROLEX
100
59
159
-32.9%
Table 8: Cost analysis of ROLEX compared to a regular feedback system using our defined "gain" metric. Each model is selected based the maximum possible gain. This gain is shown as reduction in this table for each corresponding ROLEX.
available in the partial knowledge for retrieval but not retrieved, and OVC was hallucinated even though there were corresponding expert lexicon in the input.
From the NL2LTL portion of the analysis, we observe that most errors corresponded to "hallucinating expert knowledge". This shows that the model tries to generalize without expert lexicon, which is against our intended use case. The model also has high probability of not using an expert lexicon using incorrect one.
For the NL2Code analysis, we omitted the "hallucinated EK" due to the large number of possible functions that the model generate that may be an OVC. Also, due to the sparsity of OVCs in the dataset, we only select instances where an OVC is present. We observe that large portion of the errors are when the model is not using an expert lexicon. This hints at the difficulty of using lexicons to resolve OVCs on this benchmark.
Percentage
Error Class
N..LTT
NL.2Code
EK not used
23.3
56.0
Incorrect EK used
23.3
16.0
not retrieved
28.0
Hallucinated EK
46.7
Table 9: Error analysis of ROLEX.
20


Reviews:
[{"review_id": "cp3KsT4391", "reviewer": "Reviewer_wWrJ", "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. \n\nThe paper evaluates on three semantic parsing/program synthesis tasks and shows impressive performance gains with the retrieval from feedback memory.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback and related work suggestions.\n\n# Reponse to \"Reasons to Reject\":\n\n**Point 1**: Approaches in referred papers have similarities (using RAG to model feedback) but differs in tasks and training methods.\n* (Mishra et. al 2022) , while using the concept of dynamically growing feedback database, differs in downstream domain task (QA vs Semantic Parsing). They also utilize free-form feedback compared to our lexicon-based feedback, which is more efficient for addressing constructs ( Table 4(b) ). We also train our retrievers for domain adaptation, compared to using off-the-shelf retrievers like them, due to the non-generalizability of our domains. Secondly, they use a trick called ``forced generation’’ which generates multiple inputs with each retrieved feedback using off-the-shelf generators.  We propose different unique training schemes that teach the model to use feedback effectively (Section 4.2 for details). \n* (Das et. al 2021) uses training examples/cases as feedback and have a static database of such examples. Whereas, our feedback is designed as a dynamic database of lexicons growing with each inference parse.\n\n\n\n**Point 2**:  We agree that actual HIL experiments can showcase practical considerations ( HCI aspects etc.). However, semantic parsing problems we consider require domain knowledge and trained users. Hence, testing using such expert users can be difficult and expensive. This is especially true for our NL2LTL setting, in Network File Systems domain, where the target formalism is niche and our test set required many iterations and months of input from formal verification experts. Hence, we settled for the middle ground of using simulated environments common across the literature. \n\nWe assume “deriving data synthetically” refers to how human feedback data was simulated and not test datasets themselves, as all of them are real-world datasets.\n\n**Point 3**: Fine-tuning retrievers can affect generalizability. However, our test domains are specialized and models require domain-specific knowledge. Hence, fine-tuning, compared to off-the-shelf RAG, yields significant performance gains, as shown in results in Table 3(b) and 7.  Building generalized retrievers that can work across domains (e.g. from NL2LTL to the NL2Code domains) can be interesting future work in this space.\n\nIn the final camera-ready version of the paper, we will add discussions to these points.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The paper tackles a practical problem of generalizing your RAG model to unseen constructs and presents a practical and usable solution.\n2. The paper is written clearly and was easy to understand\n3. The proposed solution works well.", "reasons_to_reject": "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.\n2. 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. \n3. 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?\n\n\nReferences\n* Das et al 2021: Case-Based Reasoning for Natural Language Queries over Knowledge Bases (refer to Sec 3.4)\n* Mishra et al 2022: Towards Teachable Reasoning Systems: Using a Dynamic Memory of User Feedback for Continual System Improvement", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4Xx8UVxCej", "reviewer": "Reviewer_2rdn", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback.\n\n# Response to \"Reasons to Reject\":\n\n**Point 1**: We agree that the problem setting is not typical in open-domain NLP problems, including standard semantic parsing application areas such as Text-to-SQL or Knowledge-based QA. \n\nHowever, as we argue in the paper (beginning paragraph of Section 3), the setting we introduce is especially well-suited for formal verification, where there are a large number of problem domains in which translating text specifications to formal statements is a serious burden preventing progress in verification and slowing the development of protocol implementations. For example, there are thousands of RFCs out there and, for each of them, the expert needs to parse the specification to formal language manually. Also, this project and associated datasets were developed from collaborations with formal verification researchers who want to verify Network File Systems but are unable to do so due to the difficulty of parsing specifications into formal models. Hence, their difficulty further necessitates the need for our solution.\n\nWe will add text to the paper to better highlight this motivation and the broader potential for impact in the final version.\n\n# Response to \"Questions to Author\":\n\nWe thank the reviewers for pointing out these typos/errors. We will fix them in the final camera-ready version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The paper addresses an interesting practical problem, that of open-vocabulary constructs in semantic parsing.\n\nThe paper is clear, well-structured and easy to follow; and has sufficient substance.\n\nThe proposed approach provides good empirical results across a range of tasks.\n\nThe paper features detailed analysis of the results, including ablations in a component by component basis.", "reasons_to_reject": "The problem is somewhat niche - one does not often have high-quality expert feedback at inference time.", "questions_to_authors": "A few typos:\n\np.1: an linear -> a linear\n\np.3: problem,s -> problems,\n\np.9: the for OVC errors for -> extra \"for\"", "extra_scores": {}}, {"review_id": "QJvTAlwsg6", "reviewer": "Reviewer_1xv4", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful feedback.\n\n# Response to \"Reasons To Reject\":\n\n**Point 1**: We agree that the RAG model can potentially overfit to the retrieved constructs in the lexicon seen during training time. However, our experimental evidence shows this is not the case. Firstly, open-vocabulary constructs are by definition those not seen before. Our evaluations duly reflect this as gains are all seen using unseen constructs in feedback during inference. Secondly, the difference in performance between the validation and test sets is quite small indicating there is very little overfitting. For instance, for the Code-T5 base model trained via RoLex, the difference in BLEU performance between validation and test performances is a mere 0.2 BLEU score! For the NL2LTL domain, note that the training set is synthetic and has no overlap with the test set. The overall large gains in all of the settings indicate that the overfitting, if any, is small. \n\n# Response to \"Questions to Authors\":\n\nSome of these questions are addressed in the paper’s Appendix, which the reviewer may read for further clarification. To take each question in turn:\n\n* The lexicon is built using small snippets of text/documentation describing the construct.  For each evaluation testbed, the lexicons are constructed differently. Please see Appendix Section 8.3 for further details. \n* All of the lexicons in our testbeds are OOV compared to the training sets. This is accomplished by explicitly making sure that none of the test OVCs are seen in training examples.\n* Our retriever is designed to retrieve the top-k relevant lexicon entries (k=10 in our experiments). If a parse requires multiple lexicon entries, our fine-tuned retriever is trained to retrieve all of them within the top-k. Our generator is fine-tuned and conditioned upon the retrieval such that it identifies all of the relevant lexicon entries and uses them during generation. This is accomplished through specific training strategies during fine-tuning, such as teaching the models to learn to extract relevant lexicons first and then teaching them to do the semantic parsing task. These training strategies are highlighted in Section 4.3 of the paper.\n\nWe will add discussions about reviewer's points in the final camera-ready version of the paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1.\tNovel Approach to Dynamic Knowledge Augmentation: The paper presents a novel task setup called Dynamic Knowledge-Augmented Parsing (DKAP) to address the OVC problem. DKAP allows models to learn from and reuse dynamic, growing knowledge bases that record all knowledge provided by the user for OVCs encountered in previous sentences. \n\n2.\tRetrieval-Augmented Generation Model (ROLEX): The paper introduces a retrieval-augmented generation model called ROLEX, which collects small amounts of feedback from experts based on errors made by the parser when translating OVCs. This feedback is designed as a key-value lexicon, representing knowledge from the expert for the model to use in translating OVCs in future parses. The retriever module in ROLEX is trained to fetch relevant lexicons from the feedback database during each parse, while the generator module is conditioned to use this information when parsing. This approach helps improve the performance of baseline models by using dynamic expert knowledge effectively.", "reasons_to_reject": "1.\tPotential 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_to_authors": "1.\tThe 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?", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept