When a language model scores well on a logic benchmark such as FOLIO or FraCaS, we cannot tell whether it reasoned or remembered. The usual contamination detectors look for memorization in the model's confidence: they check whether the model assigns suspiciously high probability to test items. Recent work shows that reinforcement-learning post-training erases exactly that signal while keeping the inflated score. This note proposes a detector that never looks at probabilities. For each benchmark item, we generate fresh "twins": new problems that a symbolic prover has labeled, built from a different logical skeleton, but matched to the original on the structural features that make formal reasoning hard. These features include the number of quantifier alternations, the number of variables, Horn versus non-Horn rules, abduction graph topology, proof depth, and the presence of higher-order constructs like most or almost. If a model is right on the original but wrong on its difficulty-matched twins far more often than a clean model would be, the score on that item is not evidence of reasoning ability.
The complexity theory of logic supplies the matching variables. That literature has spent decades cataloguing the syntactic "triggers" that move a problem from easy to hard. The contamination literature supplies the need: it shows that behavior, not loss, is the signal that survives post-training. In two sentences: contamination inflates a model's accuracy on specific items without inflating its accuracy on fresh items of equal formal difficulty. We measure that gap with solver-verified twins, so the measurement survives reinforcement learning that hides loss-based evidence.
Core Claim
The work starts from a validity question: does a model's score on a logic benchmark equal its accuracy on a fresh sample drawn from the same formal-difficulty stratum? The per-item gap between original and twin accuracy is a contamination statistic. Three properties distinguish it from existing detectors. It does not depend on log-probabilities, so it should survive the clipping effect that On The Fragility of Benchmark Contamination Detection in Reasoning Models proves collapses loss gaps. It is controlled for difficulty, so a gap cannot be explained by twins simply being harder. And it separates memorized answers or templates from generalizable reasoning, because twins change the logical skeleton rather than only the words.
The central empirical bet is twofold. First, formal structural features predict language-model difficulty well enough to serve as matching variables. Second, matching on them yields a much cleaner detector than matching on step depth alone, which is FOLIO's current difficulty proxy.
Relation to Prior Work
Two papers motivate treating formal complexity as the relevant difficulty axis. Can Large Language Models Reason? A Characterization via 3-SAT generates random propositional formulas and finds that GPT-4 collapses to about 10% at the satisfiability phase transition. DyVal generates reasoning tasks from graphs and shows that depth and premise order strongly govern accuracy. Both build fresh benchmarks. Neither audits existing benchmark scores, and neither goes beyond propositional or tree-shaped logic.
The complexity literature supplies candidate matching features but also constrains how we use them. The two-versus-three-variable boundary in Weighted model counting beyond two-variable logic, the role-chaining triggers in Tractable Concept Languages, and the tied-chain condition for tractable abduction in A Tractable Class of Abduction Problems are worst-case results for specific reasoning problems. They are not claims about neural difficulty. We therefore treat them as hypothesized features and test empirically which ones actually predict model accuracy, rather than importing complexity classes wholesale.
Our methods for labeling twins come from automated higher-order reasoning. Higher-order logical inference with compositional semantics pairs a grammar-based parser with the Coq proof assistant and targeted axioms for generalized quantifiers and intensional modifiers. Extending SMT Solvers to Higher-Order Logic makes higher-order goals practical for automated solvers by lifting λ-terms (anonymous functions) into fresh named symbols. These systems give us ground-truth labels for twins without an LLM judge. That matters because A²RBench shows LLM-authored generators silently simplify hard items.
Finally, Beyond Memorization shows that rewriting items into multi-step reasoning removes signs of memorization. That result motivates why twins must change structure and not only surface text, but that paper offers no difficulty control and no formal verification.
Research Program
The first component is a twin generator. It parses each benchmark item into a formal skeleton: the gold FOL annotations for FOLIO, the Coq/HOL representations from the Mineshima pipeline for FraCaS, and the rule theories for ProofWriter. It then computes a complexity profile for the skeleton. The profile records quantifier prefix and alternation count, the number of distinct bound variables, the Horn/non-Horn status of the rules, whether the connection graph contains tied chains for abduction items, proof depth, premise order, and which higher-order operators appear (generalized quantifiers, intensional adverbs, attitude verbs).
The generator samples new skeletons with the same profile but a different predicate structure and a fresh vocabulary. It labels each one with a prover: an FOL prover for first-order items, and the Coq-with-axioms pipeline or a higher-order SMT solver for HOL items. It keeps only items whose label is certified within a time budget, and we report the discard rate by stratum. English is produced by grammar templates plus paraphrase. Each paraphrase must round-trip back to the same formula through a parser; otherwise it is discarded. We also produce lexical twins (same skeleton, renamed entities) as a weaker control.
The second component is a difficulty model. On models whose training data provably excludes our generated items, we fit accuracy as a function of the complexity profile using fresh generated items. This tells us which formal triggers matter for language models, which is itself a finding at the intersection of the two directions. The fit also defines matching tolerances. If a trigger such as the two-to-three-variable boundary has no predictive effect, it is dropped from matching and reported as a negative result.
The third component is the audit statistic. For item $i$ with original correctness $c_i \in \{0,1\}$ and mean accuracy $\bar t_i$ over $K$ structural twins, the contamination score is
$$s_i = c_i - \bar t_i - \hat\delta(\text{profile}_i),$$
where $\hat\delta$ is the expected original-minus-twin gap for clean models in that stratum. Subtracting $\hat\delta$ absorbs any residual difficulty mismatch introduced by the generator. We report per-item AUROC for separating contaminated items (members) from uncontaminated ones, and a benchmark-level estimate of score inflation computed as the mean of $s_i$.
Baselines
The naive reference point takes the benchmark score at face value, which is equivalent to assuming zero inflation. A second naive variant compares the original against unmatched fresh logic items, in the style of DyVal. This variant shows how much of any gap is merely a difficulty difference. Beating it means our inflation estimate is close to the known injected inflation, while the unmatched gap is large even on clean models.
The strongest existing competitor is reference-model likelihood-ratio membership inference (LiRA), together with the other loss-based detectors studied in On The Fragility of Benchmark Contamination Detection in Reasoning Models. That paper reports LiRA at 89.1% AUROC after contaminated supervised fine-tuning, a drop of roughly 14 points after one epoch of GRPO, and averages of 50–58% AUROC across all ten detectors when reasoning-trace data is injected into DeepSeek-R1-Distill-Llama-8B. No reported result was found on Lacuna for any of these detectors on logic benchmarks. We will run all of them on exactly the same contaminated checkpoints and the same member and non-member splits, giving each the same reference-model and tuning budget. Our method gets the same number of model queries. We claim to beat LiRA only if twin-gap AUROC exceeds LiRA's by a clear margin after reinforcement learning and in the reasoning-trace setting, while roughly matching it after fine-tuning alone.
Two ablations isolate the key ingredient. Lexical twins test whether changing the skeleton matters. Twins matched only on proof depth, FOLIO's proxy, test whether the full complexity profile matters. For context on task accuracy: FOLIO reports GPT-4 8-shot at 64.2% and the Logic-LM translate-then-prove pipeline at 78.1% (FOLIO). The HOL system reaches 69% on FraCaS (Higher-order logical inference with compositional semantics).
Why not just…?
Why not just rename entities or remap symbols? This is the most serious threat, and it may suffice for some contamination types. A²RBench finds a 17.7% drop under symbol remapping, so surface probes do detect something. Renaming, however, preserves the logical skeleton. FOLIO's HybLogic items come from 24 syllogism templates, so a model exposed to them can carry template-to-answer shortcuts straight through a rename. Our experiments include both twin types across three contamination regimes: verbatim answers, reasoning traces, and template-only exposure. If lexical twins match structural twins in all three, we will adopt the simpler method and report it as the finding.
Why not just fix loss-based detectors, for example by using intermediate checkpoints? Auditors of released models rarely have those checkpoints. The fragility paper's analysis says the log-probability gap is suppressed by the clipping step in the RL objective itself, not by an artifact that better calibration fixes. A behavioral test sidesteps the issue because the same paper reports that inflated accuracy persists after the loss gap is erased.
Why not just retire static benchmarks for dynamic generators like DyVal? Dynamic generation is the right long-term fix, and our generator is one. However, published claims on FOLIO, FraCaS and ProofWriter keep being made and need auditing. In addition, DyVal's logic tasks lack higher-order constructs and formal difficulty control. The difficulty model we fit is also exactly what a dynamic HOL benchmark would need to calibrate its difficulty tiers.
Why not just translate to a solver, so model memorization does not matter? Translation is where the model's own competence enters. On FOLIO, 93% syntactically valid translations still yield only 78.1% end-to-end accuracy. We therefore also audit translate-then-prove pipelines, applying the twin gap to translation accuracy.
Proposed Experiments
In controlled contamination, following the fragility paper's two stages, we inject a random half of the FOLIO, FraCaS and ProofWriter test items into an open model. Stage I adds them through supervised fine-tuning followed by clean GRPO. Stage II injects reasoning traces directly into DeepSeek-R1-Distill-Llama-8B. A third regime exposes the model only to HybLogic-style templates filled with different entities. The decisive checks are these. On clean models, twin-gap AUROC must stay near 50%, with estimated inflation near zero. After RL, and in Stage II, twin-gap AUROC must stay well above the 50–58% loss-based range. The benchmark-level inflation estimate must track the known injected gain. We must also see a gap between structural and lexical twins in the template regime.
A difficulty-model study runs before any auditing. We measure how much variance in clean-model accuracy is explained by the full profile versus depth alone, and we report which complexity triggers are actually predictive. This analysis also bears on the tension between ProofWriter's depth robustness (97.2% at depth 5) and FOLIO's depth degradation. Finally, we apply the audit to publicly released reasoning models on these three benchmarks, reporting per-benchmark inflation estimates with bootstrap intervals over twin samples.
A clear negative outcome would be informative. If profile-matched twins do no better than depth-matched or lexical twins, then formal complexity theory does not describe what makes logic hard for these models.
References
- On The Fragility of Benchmark Contamination Detection in Reasoning Models
- Can Large Language Models Reason? A Characterization via 3-SAT
- DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
- Weighted model counting beyond two-variable logic
- Tractable Concept Languages
- A Tractable Class of Abduction Problems
- Higher-order logical inference with compositional semantics
- Extending SMT Solvers to Higher-Order Logic
- A²RBench: An Automatic Paradigm for Formally Verifiable Abstract Reasoning Benchmark Generation
- Beyond Memorization: Reasoning-Driven Synthesis as a Mitigation Strategy Against Benchmark Contamination
- FOLIO: Natural Language Reasoning with First-Order Logic