Toward a Sheaf-Theoretic Understanding of Compositionality in Large Language Models

Authors: Ruchira Dhar, Antonia Karamolegkou, Anders Søgaard
Primary area: applications to neuroscience & cognitive science
Keywords: cognition, compositionality, sheaf-theory, language model evaluation

Abstract:
Compositionality has long been considered a fundamental aspect of human cognition -  enabling the learning, manipulation, and generation of natural language. Understanding how this concept applies to Large Language Models (LLMs) and how it can be effectively evaluated remains a key challenge. In this work, we explore the potential of formalizing cognitive notions from theory, such as compositionality, to develop more nuanced evaluation frameworks for LLMs. Using a sheaf-theoretic approach, we define compositionality through four distinct conditions that capture its multifaceted nature. This formalization offers a structured perspective on evaluating LLMs, moving beyond surface-level assessments to uncover deeper insights into their behavior. Our findings suggest that theoretical frameworks like this one can play a crucial role in advancing the understanding and evaluation of LLMs, providing a foundation for more comprehensive and precise performance analyses.

Decision: reject
Reviewer scores: 3, 5, 5

Reviews and discussion:
<thread>
creation date:
1729761774087

thread_type:
official_review

<thread_object>
creator: reviewer_ddyq

<content>
summary:
1. This work proposes a novel way to use sheaf theory for compositionality for Large Language Models (LLMs). Compositionality is a central concept of human cognition that understands complex things through simpler components. This new definition of compositionally contains four distinct conditions: restriction maps, gluing conditions, locality conditions, and natural transformations.

2. The experiments conducted across multiple LLMs (such as Llama2, CodeLlama, and Mistral) show that larger models tend to exhibit better compositional abilities overall. However, instruction-tuned models experience a significant decline in performance, particularly in tasks related to the restriction condition and natural transformations. This suggests that while instruction tuning may enhance generalization, it can degrade the model's ability to handle compositional information.

strengths:
1. The paper introduces a completely new, higher-level definition of compositionality using sheaf theory, which provides a fresh perspective on evaluating the compositional abilities of LLMs. This novel approach broadens the understanding of how complex linguistic expressions are structured and processed by LLMs. Provide a more comprehensive way to measure LLMs' ability.

2. The authors evaluate various LLMs (such as Llama2, CodeLlama, and Mistral) across four different angles, providing a detailed comparison of their compositional performance. This analysis helps identify which models excel in certain tasks and where they fall short, offering useful insights for improving future models.

weaknesses:
1. The paper does not include a dedicated Related Work section, which is critical for situating the proposed framework within the existing literature. This omission makes it difficult to understand how the new approach builds upon it.

2. The paper falls short of the 10-page limit. This space can be used to conduct analysis deeper.

3. While the proposed sheaf-theoretic framework is innovative and offers a high-level definition of compositionality, its real-world applicability remains uncertain. The framework may be too abstract or theoretical for immediate use in practical model development or evaluation, raising questions about its tangible impact.

4. The paper does not provide a better solution for improving compositionality in LLMs.

questions:
1. Are there any situations or specific tasks where the proposed sheaf-theoretic framework might not be applicable?

2. The performance shifts observed in Table 1 indicate differences across various models. What insights can these performance variations provide regarding model architecture, training methodologies, or the training data used?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730472600380

thread_type:
official_review

<thread_object>
creator: reviewer_mmvk

<content>
summary:
Compositionality is a topic on human cognition. 
LLMs appear to show their superior language processing capability and thus evaluating the compositionality become a portal to gain insights into these models.
This paper introduced a sheaf-theoretic framework with 4 different datasets to assess LLMs performance on compositionality.
Key findings include 1) larger models tend to be more performant. 2) instruction finetuned models may behave inconsistently in different tasks.

strengths:
- Paper investigated both query (aka, prompt output) and internal representation in different tasks.
- To reviewer's knowledge, this paper is clear and original in proposing the sheaf-theoretic framework for LLMs compositionality assessment.
- Two orders of relationship are investigated, entity level and relation level.
- Proposed 4 datasets, namely SCAN, ANTAILS, COMPCOMB, PLANE, aim to unveil insights in restriction maps, gluing condition, locality condition, and natural transformation. 
- Appendix provided abundant information about generation process of each dataset.

weaknesses:
- A related work section would help readers to better understand the background and prepare readers well to follow the sheaf-theoretic framework.
- While 4 tasks cover distinct aspects, the size of these dataset could be limited to capture the compositionality of LLMs.
- Compositionality is an important in human cognition and investigating it in LLMs is also exciting. The paper would be more complete if authors include the importance of LLMs compositionality in applications. What are the aspects or benefits if LLMs gains better compositionality performance.
- There is limited description of the experiment setup. It would be preferable if there are more justifications for the methodology and choice of prompting.
- (line 908) There is a table or figure missing about the SCAN setup, showing **??**
- Appendix also shows the template used but it would be better to include additional examples in each dataset to help readers gain insights.
- There are many extremely long sentences, which requires a second pass and thus affect the readability of the paper.

questions:
- Is llama2 chat hf an instruction-following checkpoint?
- Would it be possible to include Qwen in the evaluation for additional trends and patterns revealing? Also llama released 3 and 3.1.
- When introducing 4 tasks, the ordering is not consistent, is there any special consideration? 
For example, the order in table 1 or figure 1 (1SCAN, 2ANTAILS, 3COMPCOMB, 4PLANE) is different from the order in section 2 and section 3.3. 
- What is the size of each dataset?
- Could you provide an example for each dataset? 
- Could chain-of-thought prompting apply during evaluations?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730717870687

thread_type:
official_review

<thread_object>
creator: reviewer_swd5

<content>
summary:
The paper introduces a mathematical framework for compositionality in LLMs based on sheaf topology, defining four basic conditions: restriction maps, gluing conditions, locality conditions, and natural transformations. The authors tested each condition with a specific dataset and found that instruction-tuned models have inconsistent performance across different aspects of compositionality.

strengths:
- The paper presents a nice initial effort in defining compositionality with a mathematical framework rigorously
- The paper is well-structured and well-written

weaknesses:
- (Major) Limited novelty and applicability of the findings:
	- The formalization of compositionality via the sheaf-theoric framework is novel, but it is not clear its purpose, how it can be used in practice in the real world and whether it's correct or not (due to a weak experimental part).
	- There is no novelty in the evaluation part since it uses known datasets and results for the literature, except for the introduction of the COMPCOMB dataset.
	- In general, there are very few contributions that justify this paper.
- (Critical) The experimental part is extremely weak and not convincing:
	- In Table 1 there is a significant drop between base models and instruction-tuned models like a huge ~40% (0.82 vs 0.42) on SCAN. The authors provide an explanation that  L402 "instruction tuning likely leads to a loss in the development of restriction maps, which could be explained by the fact that while the model retains its most important generalizations, it loses some local information to accommodate instruction tuning, leading to loss of restriction mapping". This is in contrast with results in the literature where instruction-tuned models perform generally better. I believe there is not enough empirical evidence to sustain this statement and the huge performance drop might be due to issues in the evaluation setup. The authors mention the use of "computing the model’s log probabilities for two possible completions" but this has been shown to be problematic, especially in instruction-tuned models that might lose the calibration in their logits after RLHF (https://arxiv.org/abs/2402.14499 , https://arxiv.org/abs/2303.08774). I suggest using a different eval strategy (e.g., comparison with the ground truth and exact match metric) and distinguishing results between instruction-tuning and models tuned via RLHF.
	- In general, I don't think the experiments are thorough enough to convince me without any doubt that an increase/decrease of the score on a specific dataset (e.g., SCAN) means an increase/decrease of a compositional condition defined in the framework (e.g., Restriction Condition). There are several other factors involved in the evaluation that might lead to spurious correlations and an increase/decrease in the score. I think the author should definitively pay more attention to the evaluation of the components defined in the framework.
- (Minor) The presentation of the results is not optimal:
	- The results proposed (Figures and Tables) are never referenced from the text. This creates ambiguity in the text because it's not clear what results you are commenting on. 
	- The proposed plots lack clarity. The rationale for using a radar plot to compare accuracies in Figure 1 is unclear, and both the scale and raw values in the plot are difficult to interpret.
- (Minor) There is a minimal discussion of related works. Missing related papers (e.g., [A Complexity-Based Theory of Compositionality](https://arxiv.org/abs/2410.14817))

questions:
N/A
</content>
</thread_object>

</thread>
<thread>
creation date:
1732555122204

thread_type:
official_comment

<thread_object>
creator: area_chair_oker

<content>
title:
To reviewers: please discuss

comment:
The rebuttal was submitted late in the discussion period, so there isn't much time left to discuss with them directly. If they have addressed your concerns or if you have further questions, please let them know.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733303659356

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Official Closing Comment from Authors

comment:
We would like to sincerely thank the reviewers for their detailed feedback and engagement, which has significantly improved the quality and clarity of our work. Below is a summary of the changes made in response to critiques and comments.

## Purpose and Scope Clarifications
- In light of the comments from all reviewers, we felt that one of the primary issues was the lack of clarity behind the need for our proposed approach to studying compositionality.
- We have now revised the **Abstract** and **Introduction** sections to clarify the lack of any existing framework for studying an important cognitive phenomenon like compositionality and thus a need for an attempt at formalizing compositionality. We now explicitly highlight in our work that our primary contribution is providing a first-of-its-kind theoretical framework for evaluating compositionality in LLMs, rather than claiming experimental or dataset novelty. The paper now explicitly emphasizes the importance of formalizing compositionality as a multi-faceted phenomenon and explains how our framework addresses both local and global structures. We elaborated on how the framework formalizes typically ill-defined cognitive notions like compositionality and provides structured evaluations that complement existing, often ad hoc, approaches.
- We have also added a new **Related Work** section to contextualize our contributions in the literature better, referencing works like *“A Complexity-Based Theory of Compositionality.”*
- We enhanced the **Discussion** section to elaborate on the practical implications of improved compositionality, particularly for reasoning-based tasks and systematic generalization.
- The **Limitations** section now highlights that our datasets and tasks are validation tools for the framework rather than claims of experimental innovation.

## Experimental Setup and Results
- **Evaluation Justifications:** We clarified why certain evaluation strategies (e.g., avoiding CoT prompting and using log probabilities) were chosen, discussing their strengths and limitations in **Section 4.2**.
- **Performance Trends:** Added references to recent studies (e.g., instruction-tuning effects) to contextualize observed performance drops in instruction-tuned models and acknowledge the need for further empirical validation in future work.
- **Dataset Size and Examples:** We included dataset sizes and representative examples in the appendix, improving transparency and readability.

## Presentation Improvements
- All tables and figures are now explicitly referenced, and a missing table label was corrected.
- Examples of dataset tasks were added in the appendix, and the text was revised to improve readability by shortening long sentences.
- We retained radar plots for comparative summaries but are open to simpler visualizations for the camera-ready version.

## Additional Clarifications
- **Model Usage and Links:** We clarified model details and included relevant links in the appendix. While resource constraints limit the inclusion of additional models, we plan to extend this in future work.

We appreciate your valuable feedback, which has helped us refine and improve our paper. Our primary goal remains to provide a formal framework that advances understanding and evaluation of compositionality in LLMs, encouraging more nuanced approaches in this area. We hope these revisions meet your expectations and address your concerns.

Thank you once again for your time and insightful comments!
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a new sheaf theoretic framework for reasoning about compositional generalization. They use this framework to define a taxonomy of different facets of compositionality.

The presentation is clear and well structured; the authors have made further presentation improvements during the discussion phase. Reviewers praised the originality of the chief theoretic framework for compositionality.

However, reviewers remained unconvinced about the advantages of this theoretical framework over alternative ways of thinking about compositionality. They were unconvinced by both the correctness and by the possibility of new applications of this theory. The paper would be improved by showing how sheaf theory can be used to make novel predictions or explain phenomena around compositionality better than alternative theoretical models like Bayesian reasoning about possible automata, or better than alternative taxonomies of compositionality such as Hupkes et al. 2020.