GEOMETRIC SIGNATURES OF COMPOSITIONALITY ACROSS A LANGUAGE MODEL’S LIFETIME

Could you provide a more thorough characterization of compositionality as it pertains to connectionist models? How does your understanding align with or diverge from foundational perspectives (e.g., Smolensky, Van Gelder, Chalmers) on compositionality in connectionist architectures? How does the definition of compositionality you use set the foundation for your investigation and analyses throughout the paper?

Thanks for this question. The specific perspectives of Smolensky etc on meaning composition in connectionism prescribe how meaning composition and binding occur in distributed representations.

In brief, our work is somewhat unrelated to composition in the connectionist sense; we do not investigate the composition function mapping representations of parts to the meaning representation of the whole. Our question is more simple: does the geometric complexity of representations correlate to the (formal, semantic) compositional complexity of inputs? As a result, we only consider compositionality on inputs, with representational dimension as a dependent variable; the link to connectionism would instead have to consider compositional structure of representations.

Thanks for your valuable feedback! We’ve responded in detail to each of your comments below.

Why did you prioritize the transformer’s residual stream for your analysis? How does it align with or diverge from the representational basis recommended in mechanistic interpretability literature? Have you considered incorporating other components, such as Attention or MLP layers, into your analysis?

Looking at the contribution of attention to ID and MLP could be an exciting and novel direction for follow-up work. But, due to several reasons detailed below (one of them being compute), we did not prioritize it in this project.

Analyzing the residual stream (Elhage, 2021) is a very common paradigm in the interpretability literature. It has a lot of nice interpretations, such as an iterative refinement of vocabulary distributions (Geva et al, 2022; Belrose et al, 2023; Dar et al, 2022) until the next-token prediction; or a communication channel onto which individual layers write (Elhage et al., 2021; Merullo et al., 2024). We prioritize the residual stream over more fine-grained components in this work for several reasons. In particular, mechanistic interpretability, which would analyze individual neurons and circuits, up to attention heads and MLP layers, is not our goal. As we’re looking at dataset-level properties, we are interested in representations that are coarse-grained: this makes the residual stream an ideal candidate compared to, e.g., individual attention heads. We also care about comparability to the existing literature on ID estimation in LMs. The vast majority of existing works (Valeriani et al. 2023; Cheng et al. 2023; Cai et al. 2021; Chen et al. 2020; Antonello et al., 2024; Doimo et al., 2024; Tulchinskii et al, 2023; Yin et al, 2024) compute geometric measures such as ID at the level of the residual stream, and specifically on the last token representation. As such, our work is in line with existing literature.

We will motivate this explicitly in the Methods section.

Could you elaborate on the reasoning behind linking semantic complexity to ID in models, particularly in the absence of a clear semantic complexity metric? Is there a way to quantitatively define or approximate semantic complexity to strengthen claims about its relationship with model representation?

Quantifying semantic complexity is highly nontrivial, as for general text datasets, it cannot be directly inferred from the complexity of the strings, see e.g. the provided example [cat, puma, lion] in line 224. In particular, semantic complexity must be quantified on some meaning representation of the input strings, which would require, e.g., embedding the sentence using a large language model. As we are comparing semantic complexity to dimensionality computed on LM embeddings, this would unfortunately be circular.

Instead, we constructed our grammar such that sentences’ meanings are literal compositions of the meanings of their parts. This guarantees that a dataset with a larger variety of word combinations (smaller $k$) has a larger variety of meanings. That is, semantic complexity, where we consider semantics to be at the sentence-level, monotonically decreases in $k$ for normal text; this is enough as we only care about the relative complexity between datasets. On the other hand, sentence-level semantic complexity should collapse when shuffling sequences, as by construction, destroying syntax removes the possibility of composing phrase-level meaning.

We mention this reasoning in line 228, but will also add the above explicitly in the paper.

Why did you choose Kolmogorov complexity as a metric for form compositionality? What specific advantages does it offer for assessing compositionality, and how does it relate to the core concept of structure discovery?

Kolmogorov complexity (KC), coming from algorithmic information theory, is the length of the shortest program (in bits) needed to produce the dataset. If a dataset is structured, such as in our case, then the program length will be shorter than for a dataset that appears random (without structure). In other words, all else being equal, a less combinatorially complex (in our case “formally compositional”) dataset is more compressible.

Using KC to relate linguistic structure to compression is not that new. Along these lines, recent work has proposed Kolmogorov complexity as a representation-agnostic measure of compositionality (Elmoznino et al., 2024); others have related information-theoretic compression more broadly to language learning in machines (e.g. Deletang et al., 2023) and learning and comprehension in humans (Mollica and Piantadosi, 2019; Levy, 2008), as well as system-level compositionality of languages (Sathe et al., 2024). The throughline in all of these works is that the compositional structure of language permits compression, making KC highly suited to quantify formal compositionality.

We will add the motivation and relevant citations around line 220 in "Measuring formal and semantic complexity".

Could you clarify and justify the distinction you make between compositionality of form and meaning? What theoretical or empirical motivation supports this separation? Could you explain why tracking form (e.g., type-token ratio) should be considered a component of compositionality rather than a separate linguistic metric?

We will be careful to clarify these two notions of compositionality in the manuscript.

Our “meaning compositionality” is the one of Frege, Partee, etc. The familiar definition by Szabo is “the meaning of a complex expression is fully determined by its structure and the meanings of its constituents” or the “bottom-up concatenative notion of compositionality” you refer to. This has been referred to as semantic compositionality in the literature (Baroni, 2019), (Pelletier, 1994) among others.

Our “formal compositionality” is the system-level compositionality described in “Language Use is Only Sparsely Compositional”, (Sathe, Federenko and Zaslavsky, 2024) as well as (Elmoznino et al., 2024). It refers to the extent to which a language realizes its combinatorial possibilities, and is what we control with $k$. The type-token ratio of $k$-grams, in this case, is related. A lower type-token ratio indicates the dataset is “less compositional” according to the system-level definition. We’ll add this interpretation to the manuscript.

We recognize that the more familiar definition of compositionality to readers is semantic compositionality. To avoid confusion, we’d appreciate your feedback on the following changes to the manuscript:

• Either we change the terms “formal compositionality” to “combinatorial complexity”, and “semantic compositionality” -> “semantic complexity” to avoid terminology confusion, adding the above citations and motivation to the Background, or
• Keep the terms as-is, adding the above citations and discussions to Background, around line 084.

Thank you for your thoughtful comments again. As the end of the discussion period is approaching, we are hoping to hear about your opinion and thoughts on our response.

Thanks so much for your comments, especially recommendations on the framing. We'll respond to your suggestions below in more detail:

It might be more intuitive to simply refer to "form compositionality" consistently as "combinatorial complexity". The paper focuses on the intrinsic dimensionality in the models for combinatorial complexity (form, e.g. shuffled sentences) and semantic complexity (meaning, in the unshuffled sentences). The paper doesn't seem to focus much on compositionality itself, i.e. how meaning is constructed from form. Thus, the consistent use of the word "compositionality" could be misleading.

Thanks for the suggestion. The combinatorial complexity of forms is indeed not the type of compositionality put forth by Frege and in the Szabo chapter. Instead, it refers to the extent to which a language realizes its combinatorial possibilities at the system level, which does have precedence in the literature; see for instance the definition for “system-level compositionality” in “Language Use is Only Sparsely Compositional”, (Sathe, Federenko and Zaslavsky, 2024) as well as in Section 3.1 of "A Complexity Theory-Based Definition of Compositionality", (Elmoznino et al. 2024).

Still, we think it’d be prudent to change “form compositionality” to “combinatorial complexity” as suggested, and “meaning compositionality”, which is a binary variable (presence/absence of phrase-level semantic composition), to “semantic complexity”.

We propose to change the framing as follows:

1. Clearly distinguish between phrase-level semantic composition (Frege, Szabo) and system-level compositionality (Sathe et al., 2024) around line 084. Name these terms respectively semantic complexity and combinatorial complexity.

2. Make the appropriate changes to the text throughout.

As we don’t want terminology to distract from the contribution of our paper, we’d greatly appreciate your feedback on the current proposal (or if it suffices to keep the current terms while better defining them and motivating them in the literature).

Thank you for the responses! I've decided to keep my score unchanged, but I appreciate the work put into the additional experiments. I still feel that the paper does not tie the results to many questions specifically around compositionality, how meaning representations are constructed from form.

Thanks for your valuable feedback! We respond to each comment in detail below.

What does this collapse represent? Does it indicate that the phase transition for encoding meaning occurs earlier than for encoding structure?

Signature of encoding structure was given by a relative difference between sane/shuffled, not the absolute value of either individually. Around $10^4$ the profiles across the layers for both sane/shuffled settings looks the same. Therefore the formal complexity between normal and shuffled text is not differentiated . The differential coding is what signifies learning of formal complexity. If we look around $10^2$-$10^3$ there is indeed a first dip, where the differential encoding between coherent and shuffled text can first be seen.

Thank you for your comment and feedback again!

As the end of the discussion period is approaching, we would like to hear your opinion on our response and additional results which are coherent with our previous results and additional insight on emergence of complexity as a function of sequence length, as summarized in a global response on the top: https://openreview.net/forum?id=q5lJxCXjiY&noteId=KZEbFhTUaV

Why use the last token as the representation? Did the authors evaluate how well that reflects the earlier tokens in the string? Could, for instance, the original string be reconstructed with reasonable likelihood given this representation?

Thanks for this question-- it is an interesting point that not only applies to our work, but to that of an entire line of research. We’ll extend our justification in line 244 with the following reasoning.

Given variable sequence lengths due to the tokenization scheme, it is custom in the literature to take the last token representation as a sequence embedding. The literature consensus is that the last token representation in GPT-like models (similar to the [CLS] token in BERT) acts as a sentence embedding, as it is the only to attend to the whole context, and is the one eventually used for next-token prediction– see (Geva et al., 2022; Dar et al., 2022; Elhage et al., 2021). The last token, residual stream representation also has a privileged interpretation as an iterative refinement of vocabulary distributions (Geva et al, 2022; Belrose et al, 2023; Dar et al, 2022) until the next-token prediction; or a communication channel onto which layers write (Elhage et al., 2021; Merullo et al., 2024).

Importantly, it's also the default in the existing literature on ID estimation in LMs. The vast majority of existing works (Cheng et al. 2023; Cai et al. 2021; Chen et al. 2020; Antonello et al., 2024; Doimo et al., 2024; Tulchinskii et al, 2023; Yin et al, 2024) compute geometric measures such as ID at the level of the residual stream, on the last token representation.

On representational faithfulness of the last token embedding: This is a great question. We, along with the many works that consider the last-token representation, did not attempt an explicit reconstruction of the original string from the last-token embedding. This would be highly nontrivial as the loss landscape would be nonconvex; any neural approach is likely to find local minima. An entirely standalone line of research is dedicated to inverting LMs, see, e.g. Zhang et al., 2024, Morris et al., 2023.

But, an explicit reconstruction of the inputs is actually unnecessary, as it’s reasonable to assume an injective mapping from our inputs to last-token embeddings. That is, given two different inputs, it is highly unlikely that their last-token embeddings are exactly the same, even under quantization; this is due to the small size of our input set compared to the (much larger) representational capacity of a hidden layer. Injectivity is attested empirically in our experiments. The TwoNN estimator fails when there are duplicates in the point cloud (the $\mu_i$ would be $\infty$ under the presence of duplicates), and this happened for 0 cases.

Finally, if we want to look at a representation for which there is ``no information leakage", we can consider the last-layer, last-token representation, whose invertibility is highly likely according to the above sources. When only considering this representation, all of our results hold.

We will add this justification in an Appendix section in the paper. Let us know if you have more questions!

The first dataset is a very limited Controlled Grammar – much weaker than even a probabilistic context free grammar.

Thank you for this comment. We kindly point out that our grammar is a special case of a PCFG, that generates sentences of fixed length so that we don’t have to control for it in our experiments. The synthetic dataset is strictly necessary for fine-grained control over the degree of compositionality while keeping all else equal: all sentences are constrained to be semantically coherent, to be the same length, preserve the same unigram distribution, and to be extremely unlikely to have been seen during training. These are key features of our setup that required careful design. Moreover, important confounds such as "seen during training" would be impossible to disentangle if we were to construct stimuli from data in-the-wild. Furthermore, we do test inputs the other end of this spectrum with naturalistic in-distribution data, The Pile (see upcoming responses for more details), replicating our key findings with high generality.

We are currently replicating experiments on 3 new grammars, producing different (fixed-)length sentences (will ping once finished). We've already replicated our main results for Llama-3-8B and Mistral-7B, showing these models, like Pythia, differentially code formal complexity and meaning compositionality, see Figs G.2., I.2, and Table 1 in the updated manuscript.

Thanks so much for your careful review of our paper! You raised some great questions and we hope to have resolved them below.

Thank you for your comments and feedback again. As the end of the discussion period is approaching, we would like to hear your further thoughts on our response and additional results summarized on the top as a global response.

Thank you for your feedback again, this is our last reminder again for your further thoughts and comments. We hope our response addressed your questions and concerns and we would greatly appreciate it if you were willing to consider increasing your score if you are satisfied with our response.

The phase transition in figure three seems to explain performance for only a few tasks such as SciQ, ArcEasy, Lambada, and PIQA but not for other tasks. Why do you think that is?

Great question! This is likely because the other tasks are too hard. If you take a look at Fig 3, in all plots, the tasks that don’t improve stay at baseline performance (e.g., Logiqa, orange). In addition, if you compare the performance of the bigger/better models to the smaller ones (right -> left), there are tasks like ArcChallenge (red) and WinoGrande (blue) for which performance remains at baseline for the smallest model, and increases for the biggest model starting at the ID phase transition.

We’ll include this discussion in an Appendix.

...a danger that the results come from "data fishing" by slicing and dicing a fairly complex dataframe.

Thanks for raising this concern. It is unfortunately highly nontrivial to cover all possible syntactic structures, but to alleviate this, we’re expanding the experiments by introducing new grammars that generate sentences of different lengths, still with tunable complexity via $k$. Stay tuned for those results.

To strengthen our result, so far we’ve reproduced the current experiments on two different LMs, Llama-3-8B and Mistral-7B. We replicated the tendency for (1) $I_d$ and $d$ to decrease as $k$ increases; (2) $I_d$ to collapse to a narrow range upon shuffling, while $d$ increases to a narrow range; (3) formal complexity (gzip) to highly correlate to $d$, but not to $I_d$.

We will soon post a new version of the pdf where the analogue to Fig 4 for Mistral and Llama is found in Fig G.2, and the new Kolmogorov complexity correlations per layer in Fig. I.2.

...one of the claims is that shuffling words destorys any semantic information and therefore the TwoNN dimensionality is lower when we shuffle words, compared to when we do not. But this phenomenon is observed for 3 out of 4 settings, and the red curves in figure 2 where words coupled are 4 do not show that behavior.

Thanks for this comment; we agree and we will reformulate our claim to be weaker as follows:

Shuffling, which destroys sentence-level semantics, collapses the ID to a narrow range. Now, the only differentiator between the ID curves is formal, and not due to sentence-level semantics. For datasets of higher semantic complexity in the normal/sane case (k=1..3), the ID is lower upon shuffling.

We’ll change the text throughout the manuscript to reflect this.

Thanks so much for your careful review. We’re glad you found the insights in our paper to be interesting, and thanks for your constructive suggestions for improvement. We’re responding to each comment below (with more experiments to come, stay tuned).

Thank you for your comment and feedback again! As the discussion period is approaching to its end, we are writing a reminder that we added additional experiments that strenghthen our claim and looking forward to your further thoughts.