Hybrid Models for Natural Language Reasoning: The Case of Syllogistic Logic

Technical Summary: Hybrid Models for Natural Language Reasoning

Problem Statement
Despite significant advancements in neural models, their ability to generalize remains a critical bottleneck for logical reasoning applications. Current literature often conflates two distinct aspects of generalization: compositionality and recursiveness.

• Compositionality is defined here not as the standard "bottom-up" construction of meaning, but as an analytical "top-down" capacity: the ability to abstract atomic logical rules from complex structures and apply them to simpler components.
• Recursiveness is the ability to construct complex representations through the iterative application of a finite set of rules (e.g., extending a transitive chain).

The authors argue that while models may be recursive (processing long chains by mimicking surface patterns), they often lack true compositionality (understanding the structural combination of individual links). This deficiency prevents robust logical reasoning, particularly when models trained on complex inferences fail to identify underlying simpler components.

Methodology
To investigate these capabilities, the authors utilize syllogistic logic as a controlled benchmark. This fragment of natural language reasoning is expressive enough to be non-trivial yet computationally tractable, unlike full first-order logic.

1. Formal Framework: The study adopts a syllogistic proof system based on Smiley (1973), featuring four quantifier types (A, E, I, O) and allowing derivations from arbitrary premises. The system is proven sound and complete.
2. Symbolic Component: A non-deterministic automated prover was implemented. It attempts to derive a hypothesis $H$ from a knowledge base $KB$ using:
   • Direct rule-based proofs (trivial and rule-based).
   • Proof by contradiction (finding a formula $F$ such that $KB \cup \{H\} \vdash F$ and $KB \vdash \neg F$).
3. Connectionist Component: Two pre-trained Large Language Models (LLMs)—FLAN-T5-base (encoder-decoder) and GPT-4o-mini (decoder-only)—were fine-tuned on synthetic data to act as assistants. The data consists of knowledge bases represented as graphs, converted to natural language using pseudowords to avoid content bias.
   • Task 1 (Premise Selection): Predict a minimal subset of premises $P \subseteq KB$ such that $P \vdash H$.
   • Task 2 (Proof by Contradiction): Predict a refutation formula $F$ to facilitate a contradiction proof.
4. Generalization Evaluation: The authors operationalized compositionality and recursiveness by manipulating training and testing sets based on A-chain lengths (the length of transitive inclusions):
   • Compositional (COM): Models trained on long chains are tested on short chains (deconstruction).
   • Recursive (REC): Models trained on short chains are tested on long chains (construction).
   • Overall (OVE): Models trained and tested across all lengths.

Key Contributions

1. Empirical Distinction: A rigorous demonstration that LLMs possess reasonable proficiency in recursiveness but struggle significantly with compositionality. Models trained on complex inferences fail to generalize to their simpler constituent parts.
2. Structural Constraints: A theoretical finding that generalization in neural models is constrained by logical structure. Performance varies systematically across different syllogism types (e.g., Type $\tau_2$, the simplest inference, is mastered, while complex combinations like $\tau_1$ and $\tau_5$ remain challenging).
3. Hybrid Architecture: The proposal and evaluation of a neuro-symbolic framework where neural components assist a symbolic prover. The neural models narrow the search space by predicting candidate premises and contradiction formulas, while the symbolic prover guarantees logical completeness and correctness.

Results

• Generalization Disparity: In the Recursive setting, models performed comparably to the overall baseline, suggesting they can extend patterns to longer chains. However, in the Compositional setting, performance dropped substantially (e.g., GPT accuracy on premise selection dropped from ~94% in OVE-short to ~76% in COM).
• Type-Dependent Variability: Performance was highly dependent on the specific syllogism type. Type $\tau_2$ (single A-chain) achieved near-perfect accuracy across settings, whereas types requiring multiple chains or mixed quantifiers showed significant degradation in compositional tasks.
• Error Analysis:
  • Unnecessary Premises: Models often included extra premises that were not minimal but still valid, allowing the symbolic prover to succeed.
  • Fabricated Premises: In cases of true failure, models generated well-formed but semantically incorrect premises, often confusing syllogism types with similar hypothesis structures (e.g., attempting to construct a $\tau_3$ proof for a $\tau_1$ hypothesis).
• Hybrid Efficiency: The hybrid models significantly reduced the computational cost of the symbolic prover.
  • The pure symbolic prover required an average of $\approx 10^{5.7}$ steps.
  • Hybrid models with Overall or Recursive assistants reduced this to $\approx 10^{2.4}$ steps (a reduction of three orders of magnitude).
  • Even with Compositional assistants (which had lower accuracy), the hybrid system remained robust, requiring only slightly more steps ($\approx 10^{2.7}$ to $10^{3.1}$) than the best-performing assistants, without compromising the soundness or completeness of the final proof.

Significance and Claims
The paper claims that the observed limitations in neural reasoning are not merely a matter of scale but stem from a fundamental inability to perform structural decomposition (compositionality) versus pattern repetition (recursiveness). The authors posit that transformer attention mechanisms may naturally support the latter but not the former.

The significance of the work lies in demonstrating that hybrid models offer a viable path forward. By leveraging neural networks for efficient search-space reduction and symbolic reasoning for logical guarantees, it is possible to overcome the generalization barriers of pure neural systems. The study suggests that this modular approach is essential for developing reliable logical provers, even when the neural components are imperfect or trained on limited data. The authors conclude that while syllogistic logic is a simple fragment, it already reveals non-trivial boundaries for neural generalization, motivating further research into richer logical fragments and the structural reasons behind learnability.