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

Mohammad Saqib Hasan, Sayontan Ghosh, Dhruv Verma, Geoff Kuenning, Erez Zadok, Scott A. Smolka & Niranjan Balasubramanian · 2025

Read Handling Open-Vocabulary Constructs in Formalizing Specifications: Retrieval-Augmented Parsing with Expert Knowledge by Mohammad Saqib Hasan, Sayontan Ghosh, Dhruv Verma, Geoff Kuenning, Erez Zadok, Scott A. Smolka & Niranjan Balasubramanian (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-08808.txt.

Introduction

Mohammad Saqib Hasan and 6 co-authors study open-vocabulary constructs in turning plain language specs into formal language in a 2025 paper. Some phrases are not known in advance, so models lack the knowledge to parse them. An expert can supply the right construct at run time.

Their system, ROLex, stores expert phrases and their formal meanings in a growing lexicon. A retriever and generator learn to find and use the right entries without retraining. Synthetic data and augmentation help train the parser. Tests cover three tasks, from temporal logic to shell commands. The task proves hard, but ROLex improves baselines.

Catalog record

CREATORMohammad Saqib Hasan, Sayontan Ghosh, Dhruv Verma, Geoff Kuenning, Erez Zadok, Scott A. Smolka & Niranjan Balasubramanian
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-08808

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Handling Open-Vocabulary Constructs in Formalizing Specifications: Retrieval-Augmented Parsing with Expert Knowledge Mohammad Saqib Hasan, Sayontan Ghosh, Dhruv Verma, Geoff Kuenning, Erez Zadok, Scott A. Smolka & Niranjan Balasubramanian Abstract We study the problem of Open-Vocabulary Constructs (OVCs)—ones not known beforehand—in the context of converting natural language (NL) specifications into formal languages (e.g., temporal logic or code). Models fare poorly on OVCs due to a lack of necessary knowledge a priori . In such situations, a domain expert can provide correct constructs at inference time based on their preferences or domain knowledge. Our goal is to effectively reuse this inference-time , expert-provided knowledge for 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 as a key-value lexicon that associates NL phrases with correct OVC constructs. We propose ROLex , a retrieval-augmented 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-augmented parser. We utilize synthetic data generation and the data augmentation techniques on annotated (NL sentence, FL statement) pairs to train the augmented parser. To improve training effectiveness, we propose multiple strategies to teach models to focus on 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 is a difficult challenge, and ROLex helps improve the performance of baseline models by using dynamic expert knowledge effectively. 1 1 1 Code and data are available at https://github.com/StonyBrookNLP/rolex 1 Introduction 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. 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 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 o ut- o f- d istribution 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

Read the complete text