1Dartmouth College 2Carnegie Mellon University 3New York University
Rewrite the rules of a reasoning problem into a logically equivalent form, and the answer should not change. For today’s LLMs, it often does.
When only the surface form of the rules changes (material implication, double negation, De Morgan’s laws), GPT-o3, Gemini-2.5-Flash-Lite and Qwen3-Next-80B lose up to 20 accuracy points and change 21–38% of their decisions, far beyond decoding noise. Stating the equivalence rules in the prompt does not close the gap.
LoGIST gives the model what a rewrite cannot change: the logical structure. Each problem is compiled into a canonical reduced ordered binary decision diagram (ROBDD), so equivalent formulations yield the same graph. A contrastively trained logic encoder embeds it, and gated cross-attention lets the LLM read it while reasoning. Across SFT, PPO and GRPO, LoGIST nearly halves logic inconsistency under RL and improves accuracy on unseen logical forms, FOLIO and ProverQA.
If a model reasons over logic, rewriting a rule into an equivalent form should be invisible to it. We keep the facts, query and label fixed and rewrite only the rules.
If Aurora collects videodisks or appreciates film history, then she contributes to film preservation.
(v ∨ h) → fIt is not the case that Aurora collects videodisks or appreciates film history, or she contributes to film preservation.
¬(v ∨ h) ∨ fIf it is not the case that Aurora fails to either collect videodisks or appreciate film history, then she contributes to film preservation.
¬¬(v ∨ h) → fIf Aurora does not both fail to collect videodisks and fail to appreciate film history, then she contributes to film preservation.
¬(¬v ∧ ¬h) → fStrong LLMs are sensitive to how the logic is written
Left: accuracy on the original problems and their Mixed rewrite, which applies a different rule of replacement at each step. Right: how often a prediction changes between the two, next to run-to-run decoding noise.
Equivalent rewrites change the words, not the truth table. LoGIST compiles each problem into a canonical graph of that truth table and lets the LLM attend to it.
An ROBDD is a rooted DAG for a Boolean function: each internal node tests one fact, with a high edge for true and a low edge for false.
Under a fixed variable order, logically equivalent formulas compile to the same ROBDD, so every rewrite of a problem gets an identical logic input.
ROBDD of (x1 ∨ x2) ∧ x3 with order x1 ≺ x2 ≺ x3.
Starting from the token embeddings of each node’s facts, the encoder passes gated messages along high and low edges in topological order. Contrastive pretraining on structure-only signatures teaches it logical form rather than topic.
At selected decoder layers, the LLM’s hidden states attend to the logic embedding, and a learnable tanh gate sets how much of it enters the residual stream.
Trained only on implication-form problems, LoGIST is more consistent under rewrites and more accurate on unseen forms and ProverQA, for every training recipe.
Fewer decision flips under every training recipe
Share of problems whose prediction changes between the original and a rewrite, averaged over the four rewrites. Llama-3.1-8B-Ins, three runs each.
Higher accuracy on logical forms never seen in training
Left: mean accuracy over the four rewritten evaluation sets. Right: accuracy on ProverQA with the same synthetic-trained encoder.
FOLIO results, per-rewrite tables and ablations are in the paper.
Why does structure learned on implications transfer to rewritten forms? In the logic encoder’s space, composing one more reasoning step is close to adding the same vector every time.
At reasoning step n we embed three ROBDDs: the rules before the step, the n-th rule alone, and all rules up to and including it. The residual is what the composed embedding holds beyond the sum of its parts:
If composition follows a shared pattern, residuals from different problems point the same way. The leave-one-out alignment score tests this: it compares one problem’s whitened, normalised residual with the mean direction of all the others.
In the logic space, composing a step is close to adding one shared vector
Leave-one-out alignment score of each instance’s compositional residual. Llama-3.1-8B-Ins, 100 instances.
The direction is also stable across depth: mean directions estimated at different reasoning steps have an average pairwise cosine similarity of 0.90, so the same pattern is reused from one step to the next.
@inproceedings{liu2026logist,
title = {When Form Changes but Logic Doesn't: Building Logic-invariant
{LLMs} through Logical Structure},
author = {Liu, Xuyuan and Dong, Xinshuai and Chen, Elynn and Yan, Yujun},
booktitle = {Advances in Neural Information Processing Systems},
year = {2026}
}