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

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, some of which may be better suited to solving the test instance. 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, 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.

## introduction large language models (llms), being proficient program generators @xcite , are wellsuited to solving semantic interpretation tasks: translating natural language utterances x 0 (which could be questions or instructions) into executable code y 0 (interchangeably called program, or query) in a structured language, such as python, sql or sparql, possibly even invoking libraries @xcite such as pytorch or pandas @xcite . here we characterize code using their abstract syntax trees (asts). 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 @xcite or inspecting geographical databases @xcite , 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) @xcite . this capability may be particularly beneficial @xcite when in-context examples (ices) involve the same (possibly private) schema and task. formally, given test utterance x 0 , the input to the llm includes m in-context examples represented in the form p; x 1 , y 1 ; . . . ; x m , y m ; x 0 with suitable delimiters. here, p is an optional instruction prefix, and the llm has to decode ŷ0 , the translation of x 0 . a common challenge for icl is to select @xmath4, y m ) : @xmath5, the guiding principles being: (1) m should be small to reduce forward inference cost. (2) x m should be strongly related to 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 {y m : @xmath6, as well as the target y 0 are complex structured outputs. the ideal y 0 may have only partial overlap with asts in the ices {y m : @xmath7, but the non-overlapping parts ## 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 set an appointment for tuesday at 12pm for lunch for an hour and then also set me for busy friday from 12 till 2pm. do do yield createevent and has_subject(lunch) starts_at(nextdow(tue)) starts_at(numberpm(12)) has_duration(tohours(1)) let x0 datetime(@xmath8, @xmath9. has_subject(lunch) set an appointment for lunch. and has_subject(lunch) starts_at(nextdow(tue)) starts_at(numberpm(12)) set an appointment for tuesday at 12pm for lunch. has_duration(tohours(1)) set an appointment for an hour. and starts_at(nextdow(tue)) starts_at(numberpm(12)) set an appointment for tuesday at 12pm. set event for friday from 12. set me for busy. set event to end at 2pm. ends_at(and(ge(@xmath0 x0) and has_status(showasstatus(busy)) starts_at(@xmath1 x0) ends_at(numberpm(2)) ends_at(and(ge(@xmath2 x0) and training utterance ( ) decompositions generated by squad4icl the sub-utterances x i,j attached to each sub-tree y i,j are subsumed by x i while being fluent and relevant to the respective y i,j . the "let" clause, which defines x 0 , is repeated in subqueries wherever needed, but we omit repetition in the figure to reduce clutter. the top-k utterances most similar to the test utterance @xcite . 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. more recently, ye et al. (2023) have formulated icl example selection as subset selection using determinantal point processes (dpps) @xcite ). this approach optimizes example selection through a contrastive learning objective that balances relevance and diversity, using a specially designed kernel. building on this, @xcite propose tise, a tripartite selection method that incorporates contextual relevance, event correlation, and example diversity. for semantic parsing applications, where structure encodes vital information, @xcite ; @xcite propose generating diverse demonstrations by collectively covering the maximal number of local structures in the test utterance. all the above methods, however, treat both x m and y m as monolithic. when the selected ices contain irrelevant sub-parts, there is a high risk of the llm being misled (as we shall establish). while our work builds on the diverse selection method of @xcite , we first generate an enhanced pool of ices obtained by decomposition. this enables the selection step to protect the llm from interference from irrelevant fragments. example decomposition in complex question answering (qa) and semantic parsing, the utterance is often decomposed into simpler subutterances that are mapped to sub-queries, whose responses are later assembled into the final answer. @xcite propose a hybrid complex qa system performs top-down parsing of questions into tree-structured representations (referred to as h-expressions). @xcite present a neural model that hierarchically decomposes complex questions into trees. @xcite propose a novel execution decomposition (exedec) strategy for tackling the broader problem of program synthesis by addressing key forms of compositional generalization. their approach predicts execution subgoals to solve problems incrementally, guided by program execution at each step as well as carefully curated few shot llm prompts. for text2sql, @xcite propose an intermediate query plan language (qpl) more amenable to decomposition that sql. lately, llms @xcite @xcite )suitably prompted with ices and chain-of-thought (cot) reasoning -perform schema linking, query decomposition, sql generation, and refinement for text2sql tasks. these methods rely on static few-shot examples and decomposition of the test utterance, which can incur high latency and computational overhead. in contrast, our approach applies decomposition to the labeled training instances, creating a larger ice pool. we then rely on test-time selection to identify original utterance for sub-tree of the original utterance code generated utterance (dependent on original utterance) generated utterance (independent of original utterance) comment schedule a team meeting tomorrow from 3 : 00 pm to the end of the day createevent( ends_at( endofworkday( ) ) ) schedule event to end at the end of the day schedule an event that ends at the end of the workday. uses function name to add unnatural words to the query i need to book a meeting in the conference room with lynne , howard , rick and myself for friday the 10 th at 9 am please createevent( and( starts_at( nextdayofmonth( today( ) , 10 ) ) , starts_at( numberam( 9 ) ) ) ) book a meeting for friday the 10 th at 9 am schedule an event for the 10th of next month at 9 am. uses function name to add extra/incorrect info into the query put me as busy from 2 pm til 6 pm for lunch tomorrow do( let( x0 , nexttime( @xmath10, createevent( and( starts_at( @xmath3 x0 ) , numberpm( 6 ) ) ) , has_status( showasstatus( busy ) ) ) ) ) put me as busy from 2 pm til 6 pm schedule me as busy from 2 pm to 6 pm next time it's 2 pm. uses function name to add extra/incorrect info into the query let 's make a lunch meeting with ryan and jill at the starbucks cafe on 5 th at 4 pm today createevent( has_subject( lunch ) ) make a lunch meeting what is the subject of the event you want to create? incorrect interpretation of the function let 's make a lunch meeting with ryan and jill at the starbucks cafe on 5 th at 4 pm today createevent( starts_at( nextdayofmonth( today( ) , 5 ) ) ) make event on 5 th today schedule an event for the 5th of next month. uses function name to add extra/incorrect info into the query diverse and relevant ices (often choosing subtrees of the original ices). this approach avoids high latency and computational costs of test utterance decomposition during inference. ## proposed method: scud4icl we are given a training set @xmath11, y i ) : @xmath12, . . . , n }, comprising n pairs of natural language utterances x i and their corresponding programs y i . our goal is to use t to provide an llm acting as a semantic interpreter) a set s of m in-context examples for any test question x 0 . unlike previous methods, where s contained a subset of only the original examples in t , our method scud4icl seeks more focused sub-programs to reduce interference during in-context learning. we achieve this in two steps: (1) we perform a one-time decomposition of each training instance to create an augmented training pool t d , and (2) next, for each test utterance x 0 , we select a focused, diverse set of examples from t d . we describe these steps next. ## experimental setup we experiment with two semantic parsing datasets. smcalflow @xcite ) smcalflow-cs is a dataset of approximately 25 thousand human-generated utterances about calendar management. to mimic realistic settings of limited labeled data, we created two different training sets, t 5 and t 10, as follows. for each test sample, we selected 5 (respectively, 10) closest samples on utterance-level cosine similarity. we retain those of depth greater than three. this yielded 71 unique instances in t 5, and 116 in t 10. after decomposition with our method we obtained 296 and 473 non-leaf decompositions which we treat as the aug geoquery @xcite is a dataset of 880 user utterances seeking geographical information, such as locations of rivers and cities. test splits: for test data we use the iid (standard) and compositional splits created by @xcite as follows: (1) template split where programs output templates instead of grounded values for arguments @xcite ; mtop @xcite is a task-oriented dialogue dataset that maps user commands to complex, nested queries spanning 11 domains. we utilize the english and french subsets in our experiments. the original training sets include 15,667 english and 11,814 french utterances; we retain instances with query depth of at least 5, reducing them to 416 english and 211 french examples. for controlled cross-lingual evaluation, we further filter the data to include only instances with corresponding queries in the other language, yielding a parallel training set of 108 examples. the test set comprises 1,713 parallel examples per language. models and prompts we evaluate our method and baselines on the following llms: gpt 3.5 foot_1 , gpt-4o foot_2 , mistral foot_3 -7b v0.3, and llama3-8b @xcite . the prompt used for decomposition is shown in figure 4 . we use gpt4_0125 to get the decompositions. the prompt used for generating semantic parses is shown in figure 6 . ## results we first present the performance of the proposed algorithm relative to various baselines and then discuss various ablations to dissect the reason for the gains. ## conclusion we introduced scud4icl, a semantic interpreter that incorporates a new paradigm of fragmenting structured programs from the pool of available ices, and instructing an llm to translate these program fragments back to natural language utterances. this forms a larger ice pool including @xcite pairs. test instanceguided diverse ice selection from this enlarged pool improves semantic interpretation accuracy for a number of benchmarks.