Measuring Systematic Generalization in Neural Proof Generation with Transformers

Nicolas Gontier, Koustuv Sinha, Siva Reddy, Christopher Pal

Abstract

We are interested in understanding how well Transformer language models (TLMs) can perform reasoning tasks when trained on knowledge encoded in the form of natural language. We investigate their systematic generalization abilities on a logical reasoning task in natural language, which involves reasoning over relationships between entities grounded in first-order logical proofs. Specifically, we perform soft theorem-proving by leveraging TLMs to generate natural language proofs. We test the generated proofs for logical consistency, along with the accuracy of the final inference. We observe length-generalization issues when evaluated on longer-than-trained sequences. However, we observe TLMs improve their generalization performance after being exposed to longer, exhaustive proofs. In addition, we discover that TLMs are able to generalize better using backward-chaining proofs compared to their forward-chaining counterparts, while they find it easier to generate forward chaining proofs. We observe that models that are not trained to generate proofs are better at generalizing to problems based on longer proofs. This suggests that Transformers have efficient internal reasoning strategies that are harder to interpret. These results highlight the systematic generalization behavior of TLMs in the context of logical reasoning, and we believe this work motivates deeper inspection of their underlying reasoning strategies.

Introduction

The ability of Transformer language models (TLMs) to perform complex reasoning is a central question in modern NLP. While these models demonstrate remarkable performance on standard benchmarks, it remains unclear whether they possess systematic generalization—the capacity to combine known logical rules in novel, increasingly complex ways. This paper investigates this by tasking TLMs with "soft theorem-proving": generating natural language proofs for kinship relations based on provided stories.

Methodology

The researchers employed a Transformer decoder architecture, treating proof generation as a sequence-to-sequence task. Given a set of facts and a query, the model generates a proof followed by an answer. Four distinct proof strategies were evaluated:

  • Short-proof (sp): Forward-chaining from facts to the answer.
  • Short-proof-reversed (spr): Backward-chaining from the answer to the facts.
  • Long-proof (lp): Exhaustive forward-chaining.
  • Long-proof-reversed (lpr): Exhaustive backward-chaining.

The CLUTRR Benchmark

To evaluate reasoning, the study utilizes the CLUTRR (Compositional Language Understanding and Text-based Relational Reasoning) dataset. This benchmark involves inferring kinship relations within family trees based on short narratives.

Figure 1: An example of a kinship graph from the CLUTRR dataset, illustrating the relationships between entities like Betty, Nat, Greg, and Flo.

The complexity of a task is defined by its "level," where Level $k$ requires $k-1$ logical inference steps. Models were trained on specific levels (e.g., 2, 4, 6) and tested on both seen levels (interpolation) and unseen, higher levels (extrapolation).

Key Results and Analysis

Interpolation vs. Extrapolation

The models demonstrated strong performance on interpolation tasks, maintaining high accuracy on levels within the training range. However, a significant "length wall" was observed during extrapolation.

Figure 2: Accuracy across different reasoning levels for various proof strategies on the clean 'facts' template. Note the sharp decline in performance as the level increases beyond the training distribution.

As shown in Figure 2, while models achieve nearly 90% accuracy on levels 2 through 6, performance drops precipitously toward Level 10. This confirms that while Transformers can learn to apply rules they have seen, they struggle to generalize those rules to longer chains of logic.

The Advantage of Backward Chaining

A key finding is that models trained on reversed proofs (backward-chaining) generalized significantly better than those using forward-chaining. The authors hypothesize this is due to "position-dependent exploitation." In backward-chaining, the answer appears earlier in the generated sequence, allowing the model's attention mechanism to focus more effectively on the relevant logical constraints.

The Interpretability Trade-off

Intriguingly, the "no-proof" (np) models—those trained only to provide the final answer without an explanation—often outperformed proof-generating models on longer reasoning chains. This suggests that Transformers may develop efficient internal reasoning strategies that are more robust than the explicit natural language proofs they are forced to generate. This highlights a potential trade-off between a model's reasoning accuracy and the interpretability of its output.

Conclusion

This research highlights the current limitations of Transformers in systematic generalization, particularly regarding length extrapolation. While strategies like backward-chaining can mitigate some issues, the fundamental "length bias" remains a challenge. The superior performance of non-interpretable models suggests a gap between a model's internal logic and its ability to express that logic in human-readable steps, motivating further research into neuro-symbolic architectures and position-agnostic attention mechanisms.

Summary updated

Abstract

We are interested in understanding how well Transformer language models (TLMs) can perform reasoning tasks when trained on knowledge encoded in the form of natural language. We investigate their systematic generalization abilities on a logical reasoning task in natural language, which involves reasoning over relationships between entities grounded in first-order logical proofs. Specifically, we perform soft theorem-proving by leveraging TLMs to generate natural language proofs. We test the generated proofs for logical consistency, along with the accuracy of the final inference. We observe length-generalization issues when evaluated on longer-than-trained sequences. However, we observe TLMs improve their generalization performance after being exposed to longer, exhaustive proofs. In addition, we discover that TLMs are able to generalize better using backward-chaining proofs compared to their forward-chaining counterparts, while they find it easier to generate forward chaining proofs. We observe that models that are not trained to generate proofs are better at generalizing to problems based on longer proofs. This suggests that Transformers have efficient internal reasoning strategies that are harder to interpret. These results highlight the systematic generalization behavior of TLMs in the context of logical reasoning, and we believe this work motivates deeper inspection of their underlying reasoning strategies.
BibTeX
@inproceedings{gontier2020measuring,
  author = {Nicolas Gontier and Koustuv Sinha and Siva Reddy and Christopher Pal},
  title = {{Measuring Systematic Generalization in Neural Proof Generation with Transformers}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=vX03TUhT15u},
}
Figure