Large language models (LLMs) have achieved strong performance across diverse reasoning tasks, yet it remains unclear whether this performance reflects an understanding of underlying logical structure or a reliance on shallow semantic cues. A key indicator of such understanding is whether models treat logically equivalent inputs consistently, producing the same predictions despite differences in expression. Through systematic evaluation on curated data, we show that even strong LLMs often fail this test: they do not consistently preserve predictions across logically equivalent inputs and generalize poorly to unseen logical forms. To address this limitation, we propose LoGIcal STructure-guided reasoning (LoGIST), a framework that guides LLM reasoning with explicit logical structure. LoGIST maps each input instance to a decision diagram, a directed acyclic graph that captures the underlying logical structure, and encodes this graph into a logical embedding that conditions the LLM's reasoning process. Across multiple training settings, LoGIST reduces inconsistency under logical equivalence and improves generalization to unseen logical forms, suggesting that logical invariance is a useful target for building more robust and generalizable logical reasoning in LLMs.
Figures & tables
Figure 1: ROBDD example for function F:(x1∨x2)∧x3 with variable order x1≺x2≺x3 .
Figure 2: Pipeline for generating logically equivalent data. We instantiate reasoning problems from rule templates and apply rules of replacement to the premise rules while keeping the fact set and query fixed. This produces surface-form variants that are logically equivalent and share the same ground-truth label.
Figure 3: Accuracy ( 3(a) ) and Logical Inconsistency rates ( 3(b) ) of LLMs under logically equivalent transformations. Even advanced models exhibit substantial performance drops and instability on the transformed inputs, revealing a fundamental limitation in capturing the underlying logical structure.
Model
Mixed
Gemini-2.5-flash-lite
67.7
Gemini-2.5-flash-lite(w.Prompt)
70.4
Qwen3-Next-80B
66.9
Qwen3-Next-80B(w.Prompt)
66.1
Table 1: Mixed reasoning performance (by %): explicitly prompting LLMs to consider logical equivalence yields little to no improvement.
Figure 4: Framework of LoGIST. LoGIST maps each question to an ROBDD that captures its logical dependency structure, then encodes the ROBDD into a logic embedding that conditions selected LLM layers via gated cross-attention. This lets the LLM attend to explicit logical-structure information while reasoning.
Methods
Mat.Impl.
Double Neg.
De Morgan
Mixed
SFT
25.7%
18.4%
17.9%
19.0%
SFT(LoGIST)
20.1 %
14.2 %
13.1 %
15.8 %
PPO
31.5%
29.7%
32.0%
30.6%
PPO(LoGIST)
15.3 %
15.9 %
15.9 %
13.9 %
GRPO
38.1%
32.5%
34.7%
37.1%
GRPO(LoGIST)
19.9 %
20.1 %
22.4 %
16.6 %
Table 2: Logic Inconsistency rate across logically equivalent transformations on Llama-3.1-8B-Ins . A lower score indicates more coherent reasoning.
LLM
Methods
Synthetic
FOLIO
ProverQA
Base
Mat.Impl.
Double Neg.
De Morgan
Mixed
Llama3.1-8B-ins
+ SFT
0.683
0.588
0.625
0.631
0.635
/
0.598
+ SFT( LoGIST)
0.693
0.604
0.650
0.647
0.651
/
0.638
+ PPO
0.710
0.614
0.621
0.590
0.618
0.606
0.568
+ PPO( LoGIST)
0.708
0.655
0.657
0.645
0.642
0.645
0.602
+ GRPO
0.702
0.608
0.612
0.600
0.627
0.621
0.626
Table 3: Performance on the evaluation set for Llama-3.1-8B-Ins and Qwen2.5-3B-Ins , with and without LoGIST, across different training strategies. “/” indicates unavailable SFT results on FOLIO due to missing CoT labels. Colored cells indicate better performance. LoGIST consistently improves performance across settings.
Method
Base
M.I.
D.N.
D.M.
Mixed
SFT
0.683
0.588
0.625
0.631
0.635
SFT + Linear ROBDD
0.674
0.594
0.642
0.615
0.639
SFT + LoGIST
0.693
0.604
0.650
0.647
0.651
Table 4: Performance comparison across different strategies incorporating ROBDD information. LoGIST achieves better performance than using Linearized ROBDD.
Figure 5: Distributional comparison of the per-instance LOO alignment scores for Llama-3.1-8B-Ins and its logic encoder.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Model
Llama-3.1-8B-Ins
Qwen2.5-3B-Ins
w/o LoGIST
58.20 (token/s)
56.76 (token/s)
w/ LoGIST
56.99 (token/s)
55.70 (token/s)
Appendix
Table 5: Inference-speed comparison between the original models and their LoGIST-enhanced variants. LoGIST introduces minimal additional overhead compared with the base model.
Table 6: Training configurations for the three training paradigms (SFT, PPO, GRPO) on Llama-3.1-8B-Ins .
Figure 6: An example of SFT training data, where the reasoning response is used as the training label to explicitly teach the LLM the dependency structure required for reasoning.
Rule of Replacement
Tautology
Material implication
(p→q)⇔(¬p∨q)
Double negation intro
p⇔¬¬p
De Morgan’s law 1
¬(p∧q)⇔(¬p)∨(¬q)
De Morgan’s law 2
¬(p∨q)⇔(¬p)∧(¬q)
Appendix
Table 7: Rules of replacement used in our transformations and their corresponding tautologies.
Method
Base
M.I.
D.N.
D.M.
Mixed
GRPO + LoGIST (Gold FOL)
0.730
0.654
0.661
0.647
0.668
GRPO + LoGIST (Constructed FOL)
0.722
0.649
0.650
0.645
0.656
Vanilla GRPO
0.702
0.608
0.612
0.600
0.627
Appendix
Table 8: Performance comparison across different settings.
Methods
Base
Mat.Impl.
Double Neg.
De Morgan
Mixed
w/ Contrastive
0.655
0.604
0.607
0.598
0.620
w/o Contrastive
0.651
0.571
0.584
0.578
0.595
GRPO Baseline
0.645
0.570
0.577
0.572
0.590
Appendix
Table 9: Performance comparison with and without contrastive learning for Qwen2.5-3B-Ins trained with GRPO.
Figure 16
Figure 7: Linearized ROBDD prompt template for logical reasoning.
Figure 8: Prompt template used for prompting equivalent logical learning.
Figure 9: An example of logically equivalent transformations applied to a fact set and its associated rule sets. The fact set is kept fixed, while the rule set is rewritten under different equivalence transformations. The De Morgan case requires an implicit Double Negation Introduction step before De Morgan’s Law can be applied, since De Morgan’s Law strictly rewrites a negated conjunction or disjunction.