NeurIPS 2026 · arXiv 2610.25402

When Form Changes but Logic Doesn’t:Building Logic-invariant LLMs through Logical Structure

Xuyuan Liu1, Xinshuai Dong2, Elynn Chen3, Yujun Yan1

1Dartmouth College 2Carnegie Mellon University 3New York University

LoGIST framework: an input question is compiled into a query-centred ROBDD, a logic encoder embeds it, and gated cross-attention injects the embedding into selected LLM layers.
Fig. 1LoGIST gives the LLM the logic of a question, not just its wording. A query-centred ROBDD records which facts and rules decide the query (green: high edge, true; red: low edge, false). A logic encoder embeds it as hlogic, which selected decoder layers read through gated cross-attention.
Logical Consistency 1.8–2.0× fewer decision flips on logically equivalent rewrites under PPO and GRPO.
Unseen Logical Forms +4.6 accuracy points averaged over four rewrites never seen in training (Llama-3.1-8B, GRPO).
Real-World Benchmarks 10 / 10 FOLIO and ProverQA settings improve, with a logic encoder trained only on synthetic data.
Lightweight ≈2% decoding-throughput cost: the logic embedding is computed once, at prefill.
01

Overview

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.

02

The invariance gap

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.

One rule, four surface forms. Same truth table, same label. v: Aurora collects videodisks · h: she appreciates film history · f: she contributes to film preservation
Originalimplication

If Aurora collects videodisks or appreciates film history, then she contributes to film preservation.

(v ∨ h) → f
Material implication(p → q) ⇔ (¬p ∨ q)

It is not the case that Aurora collects videodisks or appreciates film history, or she contributes to film preservation.

¬(v ∨ h) ∨ f
Double negationp ⇔ ¬¬p

If it is not the case that Aurora fails to either collect videodisks or appreciate film history, then she contributes to film preservation.

¬¬(v ∨ h) → f
De Morgan¬(p ∧ q) ⇔ ¬p ∨ ¬q

If Aurora does not both fail to collect videodisks and fail to appreciate film history, then she contributes to film preservation.

¬(¬v ∧ ¬h) → f

Strong 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.

Original problemsMixed rewrite (logically equivalent)Decoding-noise baseline
−17.2 −15.1 −20.1 Accuracy 50 60 70 80 90 100 79.2 62.0 GPT-o3 82.8 67.7 Gemini-2.5Flash-Lite 87.0 66.9 Qwen3-Next80B Logic inconsistency 0 10 20 30 40 20.2 37.5 GPT-o3 10.2 34.6 Gemini-2.5Flash-Lite 2.6 21.1 Qwen3-Next80B Accuracy (%) Predictions that change (%)
Red figures are the accuracy drops. Rewrite-induced flips exceed decoding noise by 17–24 points for every model. The accuracy axis starts at 50, the inconsistency axis at zero.
03

Method

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.

Step 1

Compile the problem into an ROBDD (canonical structure)

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 for the function (x1 or x2) and x3: x1 is the root, its low edge goes to x2 and its high edge to x3; x3's high edge reaches terminal 1.

ROBDD of (x1 ∨ x2) ∧ x3 with order x1 ≺ x2 ≺ x3.

Step 2

Encode the diagram (contrastive logic encoder)

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.

Step 3

Fuse into the LLM (gated cross-attention)

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.

04

Results

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.

Standard trainingWith LoGIST
10% 20% 30% 40% SFT 20.3 15.8 1.3× fewer flips PPO 31.0 15.3 2.0× fewer flips GRPO 35.6 19.8 1.8× fewer flips Logic inconsistency (%), mean over the four rewrites · lower is better
Every rewrite is a logical form unseen in training. The reduction is largest under PPO and GRPO, where the baseline is least consistent.

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.

Standard trainingWith LoGIST
Unseen logical forms 56 60 64 68 ProverQA 56 60 64 68 LLAMA-3.1-8B-INS SFT PPO GRPO QWEN2.5-3B-INS SFT PPO GRPO +1.8 +3.9 +4.6 +2.4 +2.6 +3.0 +4.0 +3.4 +2.6 +4.2 +1.4 +1.6 Accuracy (%) · right is better
All twelve pairs move right. Gains on unseen forms are largest under RL (up to +4.6 for GRPO on Llama-3.1-8B). Per-dataset numbers, including FOLIO, are in the paper.

FOLIO results, per-rewrite tables and ablations are in the paper.

05

Composition as a linear direction

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.

Definition

Compositional residual (what composing a step adds)

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:

delta_i^n equals h_logic up to n minus the sum of h_logic before n and h_logic of rule n

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.

Logic encoder (LoGIST)LLM hidden state of the same input
0% 10% 20% 30% 40% 50% 0.2 0.4 0.6 0.8 1.0 LLM mean 0.363 encoder mean 0.910 Leave-one-out alignment score of the compositional residual · higher means a shared direction Share of instances
Both representations have the same dimensionality. The shared direction is learned by the logic encoder; it is not already present in the LLM.

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.

06

BibTeX

@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}
}