MC^2 : A Minimum-Coverage and Dataset-Agnostic Framework for Compositional Generalization of LLM s on Semantic Parsing (2025)

Abstract: Compositional generalization is one of the important abilities that large language models (LLMs) need to have for semantic parsing. Previous research typically relies on dataset-specific designs or a large number of samples in demonstrations to improve the compositional generalization of LLMs on semantic parsing. We revisit this issue and find that when the number of samples in a demonstration is limited to a theoretical lower bound for achieving compositional generalization (minimum-coverage), current advanced LLMs cannot arbitrarily achieve good compositional generalization generically on different semantic parsing datasets without dataset-specific designs. To solve this problem, we propose Multi-level Component Composition (MC^2), a minimum-coverage and dataset-agnostic framework based on input primitives, which aims to generically help LLMs achieve compositional generalization by selecting and organizing samples from multiple compositional levels that satisfy the primitive coverage. Experiments and analysis show that MC^2 can effectively improve the compositional generalization of LLMs on different semantic parsing datasets in the minimum-coverage setting.

## introduction compositional generalization @xcite refers to the ability to correctly handle unseen or rare combinations formed by known primitives. it is one of the inherent linguistic abilities of humans @xcite . due to the potentially infinite number of combinations in languages @xcite , language models often encounter new combinations formed by known primitives in realworld tasks and require the ability of compositional generalization to cope with them. therefore, compositional generalization of language models has been studied on many natural language processing tasks @xcite . semantic parsing @xcite is one of the fields that have received the most attention in the research on compositional generalization. tasks in this field aim to transform natural language into a more formal language to express its meaning more precisely, such as syntactic structure generation @xcite ), text-to-sql @xcite , etc. since target languages typically have a strong compositionality, language models intuitively require the ability of compositional generalization for semantic parsing tasks. the emergence of large language models (llms) drives the emergence of the in-context learning @xcite paradigm for compositional generalization research on semantic parsing. in this paradigm, llms are asked to achieve the correct processing of test samples containing unseen combinations after seeing the demonstrations formed by samples drawn from the training corpus. many research works have considered how compositional generalization of llms on semantic parsing tasks can be improved under the in-contextlearning paradigm @xcite @xcite . limited by the performance of llms at the time, the methods used for improvement often rely on task-specific designs or a large number of samples in demonstrations, and thus have drawbacks in terms of generalizability or consumption. as the performance of llms improves, the question of whether llms can generically achieve compositional generalization on different semantic parsing datasets with a rather limited number of samples in demonstrations and without dataset-specific designs becomes a question worth revisiting. to revisit this question, we introduce the minimum-coverage setting. this setting requires llms to achieve compositional generalization on semantic parsing tasks when the number of samples in a demonstration is limited to a lower bound for achieving compositional generalization. we test set test sample input: jump right twice demonstration input: jump output: jump input: turn right output: right input: run left twice output: (left run) * 2 subset for each provided to llm training set -compositional gap -primitive coverage find that existing advanced llms cannot arbitrarily achieve good compositional generalization on various semantic parsing datasets generically in the minimum-coverage scenario without datasetspecific designs. this suggests that despite the continued development of llms, achieving datasetagnostic compositional generalization on semantic parsing in the minimum-coverage setting remains a challenge currently. to solve this problem, we propose multilevel component composition (mc 2 ), which is a minimum-coverage and dataset-agnostic framework based on input primitives. by three steps of chunking-matching-ordering, the framework selects samples from multiple compositional levels for llms and organizes the samples in a way that potentially exhibits compositional paths, while satisfying the basic requirement of the minimumcoverage scenario. we show the effectiveness of the mc 2 framework through experiments on a variety of compositional generalization datasets of different types of semantic parsing tasks in the minimum-coverage scenario. we also experimentally analyze (1) the importance of introducing multiple compositional levels, which is the core idea of the mc 2 framework, (2) the effect of steps in the framework, and (3) the impact of choices on method components and implementation rules in the framework. the experiments and analysis further confirm the design motivation of the mc 2 framework and demonstrate the room for improvement of the framework. ## preliminaries in this section, we first introduce the concept of compositional generalization. then, we introduce the minimum-coverage and dataset-agnostic settings, describe the motivation for introducing the settings, and estimate the difficulty of the settings. ## mc 2 framework in this section, we introduce the multi-level component composition (mc 2 ) framework for helping llms achieve compositional generalization on semantic parsing. the core idea of the design is to (1) compartmentalize the inputs of the test samples into compositional levels, (2) select the appropriate demonstration samples for the components of different compositional levels, and (3) demonstrate the path of thinking from low to high in the compositional levels. the design of the framework satisfies that (1) it is minimum-coverage and taskagnostic, and (2) it always satisfies the primitive coverage requirements. the framework consists of three steps: chunking, matching, and ordering. figure 2 shows an illustration of the mc 2 framework. ## main experiment in this section, we conduct the main experiment to verify the effectiveness of the mc 2 framework on different semantic parsing tasks in the minimum coverage scenario and to verify the effect of the core idea of the framework and steps in it. ## analytical experiments in this section, we conduct analytical experiments on deepseek-2.5 and qwen-plus on choices in the mc 2 framework, including the choice of method components and the choice of implementation rules. the purpose of the experiments is to analyze the impact of various choices on performance and to provide insight into the room for further improvement of the framework. ## related work for compositional generalization of llms on semantic parsing in the in-context learning paradigm, many works have proposed different methods for improvement. @xcite proposes cover-ls. this method first defines the task-specific local structure that the output has. then, pairs of (input, output local structures) in the training set are used to train a prediction model. finally, the prediction model predicts the local structures corresponding to the test input and selects the demonstration samples that cover more of the predicted local structures. @xcite consider improvement based on the parsing tree on cogs. they consider structural similarity, diversity, and complexity to select the demonstration samples with the best matching parsing tree for the test sample. @xcite utilizes dataset-specific examples to enable llms to generate descriptions for sample selection. @xcite proposes least-to-most prompting to improve the performance of llms on scan. they divide the task into two subproblems, decomposition and mapping, provide llms with manually written samples of decomposition and mapping, and then ask llms to solve the two subproblems sequentially. on cogs and cfq, which are more difficult to decompose subproblems, @xcite proposes dynamic last-to-most prompting. they manually write specific decomposition rules and examples for cogs and cfq, and ask llms to decompose the problem. then, they perform the selection of demonstration samples for the decomposed subproblems and ask llms to solve the subproblems step-by-step. as distinct from related work, the mc 2 framework does not rely on dataset-specific design such as guidance from manual annotations, and can always satisfy the requirement of the minimum-coverage setting. ## conclusion in this work, we revisit the question of whether llms can achieve dataset-agnostic compositional generalization on semantic parsing in the minimumcoverage setting, and find that achieving this remains a challenge for current advanced llms. we propose a minimum-coverage and dataset-agnostic framework, mc 2 , to improve the compositional generalization of llms on semantic parsing. we illustrate the effectiveness and room for improvement of the framework and confirm the validity of the design ideas through experiments and analysis.