Diverse In-Context Example Selection After Decomposing Programs and Aligned Utterances Improves Semantic Parsing

Mayank Kothyari, Sunita Sarawagi, Soumen Chakrabarti, Gaurav Arora, Srujana Merugu · 2025

Read Diverse In-Context Example Selection After Decomposing Programs and Aligned Utterances Improves Semantic Parsing by Mayank Kothyari, Sunita Sarawagi, Soumen Chakrabarti, Gaurav Arora, Srujana Merugu (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-2504-03541.txt.

Introduction

Mayank Kothyari and co-authors improve in 2025 how language models turn questions into programs. The model learns from examples shown in the prompt, but whole programs are big, tree-shaped objects. Their idea is to break example programs into fragments and show only the useful pieces.

The system first splits example trees, then uses a prompted model to write matching fragment questions. A diversity-seeking selector then picks a varied set of whole and broken examples for each new question. On standard tests the method raised accuracy visibly. Gains were largest for smaller models, bigger example trees, and languages with little training data.

Catalog record

CREATORMayank Kothyari, Sunita Sarawagi, Soumen Chakrabarti, Gaurav Arora, Srujana Merugu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-03541

Browse the full library · About the Tower of Babel

Full text

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

Diverse In-Context Example Selection After Decomposing Programs and Aligned Utterances Improves Semantic Parsing Mayank Kothyari, Sunita Sarawagi, Soumen Chakrabarti, Gaurav Arora, Srujana Merugu Abstract LLMs are increasingly used as seq2seq translators from natural language utterances to structured programs, a process called semantic interpretation. Unlike atomic labels or token sequences, programs are naturally represented as abstract syntax trees (ASTs). Such structured representation raises novel issues related to the design and selection of in-context examples (ICEs) presented to the LLM. We focus on decomposing the pool of available ICE trees into fragments to minimize interference from irrelevant content and improve generalization on test instances. Next, we propose how to use (additional invocations of) an LLM with prompted syntax constraints to automatically map the fragments to corresponding utterances. Finally, we adapt and extend a recent method for diverse ICE selection to work with whole and fragmented ICE instances. We evaluate our system, SCUD4ICL 1 1 1 The code and dataset for the paper are available at https://github.com/iMayK/SCUD4ICL , on popular diverse semantic parsing benchmarks, showing visible accuracy gains from our proposed decomposed diverse demonstration method. Benefits are particularly notable for smaller LLMs, ICE pools having larger labeled trees, and programs in lower resource languages. 1 Introduction Large language models (LLMs), being proficient program generators ( Yan et al., 2023 ) , are well-suited to solving semantic interpretation tasks: translating natural language utterances \mathbf{x}_{0} (which could be questions or instructions) into executable code \mathbf{y}_{0} (interchangeably called program, or query) in a structured language, such as Python, SQL or SPARQL, possibly even invoking libraries ( Hsieh et al., 2023 ) such as PyTorch or Pandas ( Ye et al., 2024 ) . Here we characterize code using their abstract syntax trees (ASTs). Figure 1: An example of how decomposed queries help avoid interference. On the left are three whole ICEs selected by an existing method. On the right are SCUD4ICL’s ICEs. Note that two of these are decompositions of training examples, after removing irrelevant clauses. Removing the irrelevant clauses reduces interference during ICL leading to a correct prediction from the LLM. Pretraining corpora of LLMs include diverse public schema, structured data and utterances, e.g., in the field of text2sql or knowledge graph question answering (KGQA). When applied to less popular domains like calendar management ( Andreas et al., 2020 , SMCalFlow) or inspecting geographical databases ( Zelle and Mooney, 1996 , GeoQuery) , pretrained LLMs perform less impressively. This can be a serious impediment to exploiting LLMs for structured interpretation in settings where the schema and data are private, e.g., in case of enterprise data that were not part of the pretraining corpus. Given the enormous size of the best LLMs, continued training or fine-tuning may be impractical for most users. LLMs are also known to be effective in-context learners (ICL) ( Brown et al., 2020 ; Lu et al., 2023 ) . This capability may be particularly beneficial ( Levy et al., 2023 ) when in-context examples (ICEs) involve the same (possibly private) schema and task. Formally, given test utterance \mathbf{x}_{0} , the input to the LLM includes M in-context examples represented in the form \bm{p};\mathbf{x}_{1},\mathbf{y}_{1};\ldots;\mathbf{x}_{M},\mathbf{y}_{M};\mathbf{x}_{0} with suitable delimiters. Here, \bm{p} is an optional instruction prefix, and the LLM has to decode \hat{\mathbf{y}}_{0} , the translation of \mathbf{x}_{0} . A common challenge for ICL is to select S=\{(\mathbf{x}_{m},\mathbf{y}_{m}):m\in[M]\} 2 2 2 [M] refers to the set \{1,2,…M\} from a larger corpus of instances to maximally assist the LLM, the guiding principles being: 1. M should be small to reduce forward inference cost. 2. \mathbf{x}_{m} should be strongly related to \mathbf{x}_{0} . 3. S should be suitably diverse, in an attempt to provide adequate coverage of possible target ASTs. Our point of departure is to bring a new desirable criterion into the above picture of ICL. ASTs \{\mathbf{y}_{m}:m\in[M]\} , as well as the target \mathbf{y}_{0} are complex structured outputs. The ideal \mathbf{y}_{0} may have only partial overlap with ASTs in the ICEs \{\mathbf{y}_{m}:m\in[M]\} , but the non-overlapping parts may distract in-context learning. This motivates our first contribution: select ICEs from not only ‘whole’ ASTs, but also decompose them into meaningful fragments (typically, subtrees) and make them available for the ICE subset selector. This is in sharp contrast to all existing methods that choose whole examples for ICL demonstration. The enhancement proposed above raises the issue that even if (\mathbf{x}_{m},\mathbf{y}_{m}) pairs are provided for complete utterances \mathbf{x}_{m} and corresponding complete ASTs \mathbf{y}_{m} , and if the decomposition of \mathbf{y}_{m} into useful fragments \mathbf{y}_{m,k} were possible to automate, these AST fragments do not come with corresponding sub-utterances \mathbf{x}_{m,k} . Our second contribution is to employ an LLM for this translation task, but with a twist that turns out to be critical: we instruct the LLM to regard the utterances \mathbf{x}_{m,k} to be generated as sub-utterances of \mathbf{x}_{m} . Our third contribution is, given \mathbf{x}_{0} , to select, from the available pool of whole- and fragmented ICEs, a suitable subset to include in the LLM input. This is also a delicate step, because inclusion of ICEs irrelevant to \mathbf{x}_{0} (including cases with complete ASTs) have the potential ( Liu et al., 2023a ; Chen et al., 2023 ) to interfere with the generation of the correct parse \mathbf{y}_{0} . We show examples of such in-context interference for a semantic parsing task in Figure 1 . We extend a recent diverse demonstration method ( Levy et al., 2023 ) to handle complete and decomposed ICEs seamlessly. Our system, SCUD4ICL (sub code+utterance decomposition for in-context learning), incorporates all the three enhancements above, and will be released publicly on acceptance. We present empirical evaluations with three popular diverse semantic parsing benchmarks: SMCalFlow, GeoQuery, and MTOP. We explore the effects of diverse training sizes, train-test discrepancy, models, decomposition depths, and code languages. Apart from consistent wins at semantic interpretation, we establish that fragmented ICE availability, coupled with our selection criterion, reduces harmful interference. Benefits are particularly notable for smaller LLMs, larger labeled trees, and lower resource languages. Figure 2: An example showing decomposition of a training instance by SCUD4ICL. A complex training utterance-tree pair ( \mathbf{x}_{i} , \mathbf{y}_{i} ) comprising of more than ten clauses is decomposed into ten subtrees of varying complexity. The sub-utterances \mathbf{x}_{i,j} attached to each sub-tree \mathbf{y}_{i,j} are subsumed by \mathbf{x}_{i} while being fluent and relevant to the respective \mathbf{y}_{i,j} . The "Let" clause, which defines \mathbf{x}_{0} , is repeated in subqueries wherever needed, but we omit repetition in the figure to reduce clutter. 2 Related Work Our current work on semantic parsing using LLMs with ICL leverages prior work on selection of ICEs and query decomposition techniques. In-context example selection It is crucial to select ICEs that are highly informative with respect to the test utterance. An intuitive approach is to select the top- K utterances most similar to the test utterance ( Liu et al., 2022 ; Rubin et al., 2021 ) . However, this method often results in redundancy and limited coverage. Gupta et al. (2023) introduce an unsupervised set-selection approach to mitigate this problem. Similarly, Hongjin et al. (2022) propose an unsupervised, graph-based strategy that combines similarity and diversity. However, their work focuses on reducing annotation of ICL examples, rather than query-specific selection. Figure

Read the complete text