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

Recent advances in LLMs, exemplified by GPT-4 and PaLM, have revolutionized NLP tasks, including semantic parsing and code generation. Early methods relied on template-based or supervised learning approaches, limited by data scarcity and poor generalization. Transformer-based models trained on massive corpora demonstrated remarkable zero-shot and few-shot capabilities, but struggled with complex, hierarchical outputs like programs. Prior works such as CodeX and T5 have shown that structured outputs benefit from explicit modeling of syntax and semantics. However, the challenge of selecting effective in-context examples (ICEs) persists, especially for tasks requiring understanding of program structure and multi-turn dialogues. Existing methods often use similarity metrics or random sampling, which fail to capture the nuanced relevance of structured sub-components, leading to interference and suboptimal performance. This gap motivates the development of more sophisticated, structure-aware ICE selection strategies that can leverage program decomposition and alignment to improve model guidance.

The core challenge is to improve the relevance and diversity of in-context examples for structured semantic parsing tasks. Traditional selection methods, based on simple similarity or random sampling, often include irrelevant or redundant information, which can mislead the model. This is particularly problematic when dealing with complex programs represented as Abstract Syntax Trees (ASTs), where irrelevant subtrees or unaligned utterances introduce noise. Moreover, the limited size of demonstration sets constrains coverage of the structural variability inherent in real-world data. The difficulty lies in balancing relevance, diversity, and computational efficiency, especially when the program structures are large and the language data is low-resource or noisy. Addressing this problem requires a method that can decompose programs, generate aligned natural language sub-utterances, and select examples that maximize coverage while minimizing interference.

The paper introduces a three-pronged innovation: (1) program decomposition, which splits complex ASTs into meaningful subtrees; (2) syntax-constrained LLM prompting to generate fluent, aligned sub-utterances for each sub-program; (3) an extended diversity selection algorithm that considers structural relations and relevance to dynamically select a set of diverse, pertinent examples. This approach effectively reduces irrelevant information, enhances the relevance of demonstrations, and improves the model’s ability to generalize to unseen queries. Unlike prior work that treats examples as monolithic, this method leverages the hierarchical structure of programs, creating a richer demonstration pool that better captures the variability of real-world data. The integration of automatic sub-utterance generation and structure-aware selection marks a significant advancement in in-context learning for structured tasks.

• �� Decompose each training program tree into subtrees based on syntax rules, generating a set of sub-programs and associated sub-utterances.
• �� Use a syntax-aware LLM with specific prompts to generate natural, fluent sub-utterances aligned with each sub-program, ensuring relevance and naturalness.
• �� Build an augmented demonstration pool including both full and decomposed examples.
• �� Implement a structured diversity algorithm that, for each test query, iteratively selects examples covering new tokens, structural relations, and maintaining relevance via BM25 similarity.
• �� During inference, dynamically select a subset of examples from the augmented pool based on relevance and structural coverage, minimizing irrelevant interference.
• �� Evaluate the system across multiple datasets, model sizes, and languages, comparing with baseline methods like CoverLS and DPP.

The evaluation encompasses three datasets: SMCalFlow (calendar management), GeoQuery (geographical queries), and MTOP (multi-domain dialogue). Different training splits (T= T5, T= T10, D3, D4) were used to test robustness. Baselines include CoverLS, DPP, and TOPK. Metrics include execution accuracy and exact match. Experiments varied the number of in-context examples (M=5, 10), model types (GPT-3.5, GPT-4, Llama3-8B), and languages. Ablation studies examined the impact of program decomposition, sub-utterance generation, and diversity selection. Results consistently showed that SCUD4ICL outperformed baselines, with accuracy gains of 3-6%, especially in low-resource and small-model settings. The experiments validated the effectiveness of program decomposition and aligned sub-utterance generation in reducing interference and improving generalization.

SCUD4ICL achieved an average accuracy increase of 4.4% on SMCalFlow T= T5, outperforming CoverLS. On GeoQuery, across various splits, it improved accuracy by 3-5%. In MTOP, accuracy increased by 2-4% in both English and French. Ablation results confirmed that program decomposition and sub-utterance alignment are critical for performance gains. The method showed particular strength in small models like Llama3-8B, where accuracy rose by 4%, and in low-resource languages, demonstrating robustness and scalability. These results underscore the importance of structure-aware, diverse demonstration selection in complex semantic tasks.

This approach benefits enterprise data interpretation, low-resource language processing, and multi-turn dialogue systems by providing more accurate and relevant in-context examples. It reduces manual effort in data annotation, enhances model robustness, and supports privacy-preserving applications where private schemas are involved. The automatic decomposition and selection pipeline can be integrated into existing NLP pipelines to improve semantic understanding and code generation tasks, enabling more reliable and scalable AI assistants.

The program decomposition relies on predefined grammar and LLM-generated sub-utterances, which may introduce errors in ambiguous or highly complex programs. The diversity selection algorithm, while effective, can be computationally intensive for large pools, limiting real-time deployment. Additionally, the method's performance depends on the quality of sub-utterance generation, which may vary across languages and domains. Future work should focus on improving robustness, efficiency, and extending the framework to multi-modal and multi-task settings.