The Mystery of Compositional Generalization in Graph-based Generative Commonsense Reasoning (2024)

Abstract: While LLMs have emerged as performant architectures for reasoning tasks, their compositional generalization capabilities have been questioned. In this work, we introduce a Compositional Generalization Challenge for Graph-based Commonsense Reasoning (CGGC) that goes beyond previous evaluations that are based on sequences or tree structures – and instead involves a reasoning graph: It requires models to generate a natural sentence based on given concepts and a corresponding reasoning graph, where the presented graph involves a previously unseen combination of relation types. To master this challenge, models need to learn how to reason over relation tupels within the graph, and how to compose them when conceptualizing a verbalization. We evaluate seven well-known LLMs using in-context learning and find that performant LLMs still struggle in compositional generalization. We investigate potential causes of this gap by analyzing the structures of reasoning graphs, and find that different structures present varying levels of difficulty for compositional generalization. Arranging the order of demonstrations according to the structures’ difficulty shows that organizing samples in an easy-to-hard schema enhances the compositional generalization ability of LLMs.

## introduction reasoning @xcite has been widely explored and extended to a wide variety of situations involving logical or commonsense reasoning @xcite @xcite . recently, llms such as gpt-3 @xcite and llama2 @xcite have demonstrated astonishing performance on reasoning tasks @xcite . however, existing works found that llms are limited in scenarios that require generalization abilities, such as out-of-domain (shen and kejriwal, 1 code & data: https://github.com/heidelberg-nlp/cggc 2021; @xcite , low-resource @xcite and complex compositional @xcite tasks. @xcite concluded that inferior performance of models in such cases originates from a lack of compositional generalization ability -the ability to infer, from known components, a potentially infinite number of novel combinations suitable to solve the given task. with this ability, llms are expected to generalize to unseen and more complex reasoning scenarios without relying on large amounts of training instances. to explore the compositional generalization abilities of llms in reasoning, existing works introduce benchmarks across various domains involving different data representations, such as natural language @xcite @xcite and tree-based structures @xcite @xcite . these works facilitate the compositional generalization exploration in reasoning and have shown that llms are able to generalize to some extent, while being limited in specific circumstances. however, to date, we note a gap regarding the evaluation of compositional generalization abilities in the context of graph-based reasoning. graphs, as commonly used in real-world applications, offer flexible and diverse reasoning paths. recent evidence @xcite suggests that graphs enhance llm reasoning by enabling the use and combination of diverse reasoning paths. our work fills this gap by proposing cggc, a compositional generalization challenge for graph-based commonsense reasoning. cggc builds on the generative commonsense reasoning task commongen @xcite , which tasked models to generate a coherent natural language sentence from a set of given concepts. cggc extends this task by requiring models to reason over a set of concepts presented in a connected graph structure. cheese pizza in an oven' from a knowledge graph that contains the set of target concepts {cheese, oven, pizza}. for this task, we design the compositional generalization test cggc: the core idea of the cggc challenge is to probe models on specific relationship compositions that have not previously been seen in the learning sets. fig. 1 illustrates how an unseen combination of relations types must be jointly verbalized in a sentence, whereas each of the primitives has been seen in combination with other relation types. in the example, the model is required to reason over an unseen relation combination, here, atlocation&hasa -while each of these primitive relations has been seen in combination with other relation types, here: atlocation in at-location&usedfor, and hasa in hasa&usedfor. with the cggc challenge, we systematically measure a model's compositional generalization ability in graph-based commonsense reasoning in an in-context learning (icl) regime @xcite . empirical results for seven well-known llms reveal challenges in compositionally generalizing to novel subgraph configurations. we analyze the factors that impact compositional generalization in such cases by examining error trends that change as a function of: i) compositions. focusing on the structure of compositional reasoning graphs, we identify different schemas that result from composing primitive relations. experiments show varying performance across different graph structures. e.g., relation compositions with uniform directionality seem more straightforward compared to compositions that end in a common target node, or that start from a common node but end in distinct nodes (fig. 3 ). ii) primitives. we analyze performances based on the distribution of primitives according to different relation types. we find that llms more easily generalize to compositions involving common and frequent primitive relations. given the observed performance variations, we arrange the order of presentation of graph structures in icl demonstrations according to their degree of difficulty. results indicate that ordering icl demonstrations in an easy-first manner enhances the models' compositional generalization ability. ## related work analyzing commonsense reasoning existing analyses of commonsense reasoning focus on representation @xcite , interpretability @xcite , bias @xcite and consistency @xcite . further, @xcite ; @xcite ; @xcite probed language models for commonsense knowledge. others construct complex reasoning scenarios such as logical queries on commonsense knowledge graphs @xcite and geometric knowledge reasoning @xcite . commonsense reasoning has also been analyzed with downstream tasks, such as machine translation @xcite , temporal question answering @xcite , etc. beyond these perspectives, generalization is another important research direction. existing works have shown that language models suffer from overfitting and are limited in generalization to out-ofdomain examples @xcite , novel answers @xcite , and various tasks @xcite . in addition, @xcite found that llms tend to overestimate and amplify biases in training data. our work extends the research and analyses of generalization in commonsense reasoning, from the perspective of compositional generalization. compositional generalization despite the success of llms on downstream tasks, their compositional generalization abilities are poorly understood @xcite @xcite . prior works have evaluated aspects of compositionality in plms in semantic parsing @xcite @xcite , machine translation @xcite , image caption generation @xcite , etc., concluding that state-of-the-art plms are still not able to perform compositional generalization. to solve the issue, many approaches have been proposed, including data augmentation @xcite , specialized architectures @xcite @xcite , meta-learning @xcite , etc. recently, the exploration of compositional generalization in reasoning has attracted increasing attention. existing works measure the compositional generalization abilities of models on reasoning tasks such as question answering @xcite , deductive reasoning @xcite , natural language inference @xcite , and arithmetic reasoning @xcite . our study differs from prior work in terms of representation types. we focus on the compositionality of reasoning on graph-based representations, which could facilitate complex reasoning by offering diverse reasoning paths @xcite . unlike prior work we conduct detailed analyses of compositional graph structures, hence our findings can facilitate future reasoning tasks. generative commonsense reasoning the commongen task proposed by @xcite , aims to advance machine commonsense towards generative reasoning abilities. based on this benchmark, prior works have improved generation quality by incorporating explicit knowledge @xcite and visualizing relational scenes @xcite . more recent work focused on enhancing diversity @xcite @xcite and robustness @xcite . the task has also been extended to other domains, such as testing negative knowledge @xcite and visual commonsense generation @xcite . we complement these studies by providing a new perspective on the generalization ability of llms. commongen and cggc are grounded in the same dataset, but differ in motivation and research fields: commongen tasks a model to generate a natural language sentence based on a set of given concepts. it advances machine commonsense toward generative reasoning abilities. we extended this dataset with reasoning graphs, and split it elaborately to test for the compositional generalization abilities of models, in a generative graph-based commonsense reasoning task. our benchmark cggc offers the first graph-based compositional generalization evaluation benchmark, enriching the compositional generalization research field. ## defining a new cggc challenge our new challenge cggc, aiming to test for compositional generalization abilities in graph-based generative commonsense reasoning tasks, extends the existing commongen task of @xcite . cggc asks systems to generate a plausible natural language sentence given a set of concepts and a reasoning graph that connects these concepts, showing how they can relate to each other. the sentence is expected to serve as a description covering commonsense relations between given concepts. given the novel task, we aim to explore whether and to what extent llms can perform compositional generalization -which consists in understanding and verbalizing novel compositions of previously seen primitive relation types, presented in a graph-structured representation. in our work we define a relation type in the reasoning graph as a primitive, and a compound that requires several relation types in the reasoning graph as a composition. using {oven, pizza, cheese} in fig. 1 as example, the relation compound atlocation&hasa is regarded as a composition; its constituent relation types atlocation and hasa are seen as primitives. ## datasets in this section we introduce the benchmark for our novel cggc challenge. it relies on the common-gen dataset @xcite and the commonsense resource conceptnet @xcite (section 4.1). with these resources, we extend samples with reasoning graphs (section 4.2), and further split the constructed data based on the compositional generalization features for evaluation (section 4.3). ## error analysis in this section we investigate potential causes of limitations in compositional generalization, by analyzing error trends in relation to compositions (section 7.1) and primitives (section 7.2). 12 ## difficulty-based demonstrations we conclude from the analyses in sec. 7 (see especially ## conclusion we propose a compositional generalization challenge for graph-based commonsense reasoning that extends commongen to a compositional generative commonsense reasoning task from graphstructured inputs. extensive experiments on seven llms using in-context learning indicate that they struggle with compositional generalization settings. we investigate potential causes of the limitations, and find that the topology of the graph structures is a significant factor. we show that arranging the order of demonstrations in an easy-to-hard schema enhances the compositional generalization ability.