On Compositional Generalization in Language Models

• Originality: The idea is somewhat original, in testing LLMs generalization capacity through boolean expressions.

• Significance: The results have minimal to no impact on current understanding of LLMs. The boolean expressions proposed by authors are not some interesting fragment of logic, and neither do they represent any interesting NLP task. This can be simply seen as booleanized and very restricted version of Chain of Thought reasoning, which works for a few steps and then does not work for deeper reasoning tasks, which is what the authors conclude.

I am confused about the underlying tasks. The paper addresses 2 totally different tasks:

1. What can an LLM represent in relation to logic relations

2. What proof properties exist for an LLM.

The main body of the paper lacks a proper theory for the language model and the notion of compositional reasoning in models.

The boolean representation you use should be defined at the beginning, and not in sec. 4.1 (Experiments). It seems like this is a more general representation of formulae, like an abstract syntax tree (AST). Here, the tree represents the abstract syntactic structure of text written in a formal language. Each node of the tree denotes a construct occurring in the text.

I would suspect that using the AST is closest to what an LLM creates. Is this the intention? If so, then this compromises any proof methods.

The claim "The advantage of representing boolean algebra as a tree lies in dividing the boolean algebra set according to its complexity, represented by depth." depends totally on the representation. The proposed representation makes no guarantees of depth-minimality. A lot of work has been done on "optimal" boolean reprsentations, e.g., Binary Decision Diagrams (BDD).

Thee is no precise definition of compositional reasoning in models. Is there a target definition of compositional reasoning? The claim on p. 5 "This phenomenon demonstrates the compositionality of boolean algebra." makes no sense without a precise definition of compositional reasoning.

Problems also arise in task (2), where you "examine the failure points of the model’s proofs".

There is no definition of "proof" or proof method. Hence we cannot understand what you mean by task 2.

There are several recent papers on LLM and Proofs, e.g.,

Xiong, J., Shen, J., Yuan, Y., Wang, H., Yin, Y., Liu, Z., ... & Liu, Q. (2023). TRIGO: Benchmarking Formal Mathematical Proof Reduction for Generative Language Models. arXiv preprint arXiv:2310.10180.

How does your work compare to these?

The experiments on task 2 (proofs) do not address this task. Please see the above cited paper for a more rigorous method.

1. The paper does not contribute to the existing literature on compositional generalization in neural models and language models (see my questions on this and Furrer’s and Kim’s surveys for references); and does not evaluate the advanced techniques developed, for example Drozdov prompting work. The paper can also benefit from using the other length generalization papers. I am attaching some representatives that could have been included:

• Drozdov et al. “Compositional Semantic Parsing with Large Language Models”
• Liu et al. “Learning algebraic recombination for compositional generalization”.
• Anil et al., “Exploring length generalization in large language models”,
• Newman et al., “The EOS decision and length extrapolation”.

References for some other compositional generalization work that I think is not successful at recursive generalization:

• Russin, “Compositional generalization by factorizing alignment and translation”.
• Conklin, “Meta-learning to compositionally generalize”.
• Csordas, “The devil is in the detail: Simple tricks improve systematic generalization of transformers”.
• Akyurek and Andreas, “LexSym: Compositionality as Lexical Symmetry”.

2. The paper refers to the general category of language models, and the paper states in their contribution “This demonstrates that language models struggle to understand and generate compositional structure, which implies that the recent achievements in reasoning are not a result of language models' systematical and structural understanding of tasks.”.

Yet, the paper’s main experiments deal with small and relatively old models on a single fine-tuning setting. Moreover, none of the paper that the phrase “recent achievements in reasoning” refer use Roberta/T5/GPT-2, they instead use Palm and GPT-3. So, I cannot see how the claims you make derived from these results alone.

So, I believe important experiments are needed to validate these claims and strengthen the contribution of the paper.

- How does the increasing size of an LM affect these results? Do we see better generalization with increasing size?   
- What about mid-size, newer models trained with updated datasets  (LLama, Pythia series).  
- What about LLMs with prompting (you have only baseline results in Appendix F4, I suggest moving them to the main body. There are many methods on prompting nowadays gives significantly better results than few-shot prompting, see Drozdov et al., 2023).  
- What about LLMs with fine-tuning (GPT had an API for FT).   

3) I think Table1, 2 and 8 could be summarized in a single plot which makes the presentation nice. My initial thoughts:

• X axis is n where n is maximum training depth
• Y axis include three connected dots per model; first dot is the accuracy at depth<=n test examples, second that is accuracy at depth=n+1 test examples, and the third dot is the accuracy at depth=n+2
• Color can specify the different models
• Style can specify the pre-trained vs non-pretrained

You could play with these settings, but the essence is that you can compress many tables nicely into plots that are more informative about the generalization gap w.r.t function of n, model and pretraining.

• This is only a negative paper: given the finding, there is no solution.

• The paper does not cover an important related part: Memorization