Same Logic, Different Clothes: Probing Reasoning Transfer with Conditional Dependencies

Language models are often credited with "general reasoning" when they do well on math, logic or law benchmarks. Two confounds make that credit hard to assign. The test items may have leaked into training data. And the model may have succeeded because the problem looks like ones it has seen, not because it followed the problem's logic. Existing dynamic benchmarks remove the first confound by generating fresh puzzles. They do not remove the second, because they cannot change what a problem is about while provably keeping how it must be reasoned about. We propose to build that missing control from database theory. A conditional functional dependency (CFD) is a data-quality rule that holds only for records matching a pattern, such as "within the UK, the postcode determines the street" or "if the country is US, the currency must be USD." CFDs come with a formal theory of when two rule sets are equivalent, when one implies another, and when a set is contradictory. Checking a table against them reduces to polynomial-time SQL.

The idea is to generate reasoning tasks as small tables plus CFD rule sets, and to render the same rule set into many domains: postal addresses, tax records, drug dosing, visa eligibility, a math-flavored surface, and a nonsense-token surface. The logic is identical across renderings, and the database theory certifies this. We also generate "near-miss" rule sets that read almost the same but differ in one pattern constant, so their logic differs. This gives a factorial instrument in which semantic surface and logical structure are independent, controllable variables. We use it to answer three open questions. Does reasoning learned from math reinforcement learning transfer by structure or by surface? Do "skill-based" demonstration retrievers actually select by logic? Can we detect benchmark contamination behaviourally in exactly the setting where loss-based detectors have been shown to fail?

Core Claim

The claim is that the semantic-structural gap, cross-domain transfer, and contamination are best studied together with one instrument that crosses logical structure against semantic surface under formal equivalence guarantees. CFDs are an unusually good source of that instrument for three reasons.

First, Conditional Functional Dependencies for Data Cleaning defines CFDs as an embedded dependency plus a pattern tableau of constants and wildcards. It gives inference rules for implication and minimal covers, shows that CFD sets can be inconsistent, and compiles violation detection to SQL that runs in time linear in table size. Increasing the Expressivity of Conditional Functional Dependencies without Extra Complexity adds value sets and negations without raising complexity: consistency stays NP-complete and implication stays coNP-complete. Both are cheap to decide at the sizes of a reasoning prompt.

Second, this theory lets us generate provably equivalent rewrites of a rule set, which is the key ingredient, and provably non-equivalent near-misses. A templated generator such as GSM-Symbolic cannot do this. It swaps names and numbers inside one fixed template. It never changes domain, and its equivalence is assumed rather than checked.

Third, CFDs model the context-dependent, exception-laden rules that fill legal, administrative and business reasoning. The resulting tasks sit between abstract puzzles and the unstructured target domains where transfer is claimed.

What is new is the crossed design and what it can measure. It is not "another dynamic benchmark."

The Instrument

A task instance has three parts. The first is a latent logical object: a CFD or extended-CFD set $\Sigma$ over an abstract schema, plus a small relation instance. The second is a rendering that maps abstract attributes and constants to a domain lexicon and states the rules in natural language. The third is a query type. We use four query types, each decided by a solver. Tuple-level violation detection covers single-tuple violations from constant patterns and pairwise violations from wildcard patterns. The other three are consistency of $\Sigma$, implication of a candidate rule, and the minimal edit that repairs a flagged tuple. Repair is NP-complete in general, so it is used only at small sizes, where brute-force search provides ground truth.

Difficulty knobs are the number of rules, tableau rows, the length of implication chains, and the ratio of pairwise to single-tuple violations. These mirror the depth and width axes that DyVal found to matter.

The generator produces three pair types. Structural twins are two renderings of equivalent rule sets, with equivalence verified by the implication test, possibly in different domains. Surface twins are the same domain and near-identical wording with a single-constant logical change, verified non-equivalent. Unrelated pairs are neither.

Rendering runs from symbols to language, the opposite of the translation direction that Open-World LLM Logical Reasoning identified as the source of 78.54% of OpenIKLR's failures. It is therefore easier to make correct. We use per-domain templates first. Any LLM paraphrase is kept only if an independent parser recovers a rule set equivalent to $\Sigma$.

Our main derived quantity is surface sensitivity. For a model $M$ and a structure $s$ rendered in domains $d \in D$,

$$ \mathrm{SS}(M) = \mathbb{E}_{s}\big[\max_{d \in D}\mathrm{Acc}(M,s,d) - \min_{d \in D}\mathrm{Acc}(M,s,d)\big], $$

where $\mathrm{Acc}(M,s,d)$ is accuracy on instances of structure $s$ rendered in domain $d$. A model that reasons by structure has $\mathrm{SS}$ near zero after sampling noise. A model that reasons by topic does not. This generalizes the within-template spread that GSM-Symbolic reported, 12% for Gemma2-9b, from name swaps to domain swaps.

Research Program

Study 1: is transfer structural? The literature disagrees. AbstRaL, Maohao Shen et al. and Yiping Wang et al. report that narrow math reinforcement learning, a regime of training on problems with automatically checkable answers, improves unrelated tasks. BeyondBench finds math-specialized models doing worse than their base versions on algorithmic tasks. Our design splits a model's change in accuracy after math training into two parts: change on the math-flavored surface and change on distant surfaces (clinical, legal, nonsense tokens), holding structure fixed. We predict three possible outcomes. If math training raises accuracy mainly on the math-flavored rendering and increases $\mathrm{SS}$, the transfer is surface transfer, which supports BeyondBench's reading. If gains are flat across surfaces, the transfer is structural. If gains concentrate at particular structural knobs, such as implication depth but not pairwise violations, we learn which meta-skill transfers. Unlike BeyondBench, this separates "the model got worse at algorithms" from "the model got worse at non-math-looking text."

Study 2: do logic-aware retrievers retrieve logic? Skill-Based Few-Shot Selection for In-Context Learning (SKILL-KNN) chooses examples to put in the prompt by having an LLM rewrite queries into skill descriptions. SALA aligns induced operation sequences with dynamic time warping. Both are judged only by downstream accuracy, because their benchmarks have no ground-truth notion of logical similarity. Our pair types supply one. For each query we measure how often a retriever ranks a structural twin from another domain above a surface twin from the same domain. We also measure whether downstream accuracy follows that ranking. SALA's sequence alignment is one-dimensional, and CFD sets are not sequences. This directly tests the representational limitation noted for SALA.

Study 3: behavioral contamination audit. On The Fragility of Benchmark Contamination Detection in Reasoning Models shows that clean GRPO after contaminated fine-tuning, and chain-of-thought contamination of reasoning models, drive ten loss-based detectors to 50–58% AUROC while inflated scores persist. We deliberately contaminate models with a held-out set of CFD instances and their solutions, then apply GRPO. We then test on three variants of the contaminated instances: the seen rendering, structural twins in new domains, and surface twins. If the inflation is memorization of surface, it appears only on the seen rendering. If it is memorization of the logical instance, it also appears on structural twins. If it appears on surface twins too, the model is pattern-matching wording, answering the memorized question even when the logic changed. This gives an audit statistic, the gap between seen-rendering and structural-twin accuracy, that does not depend on log-probabilities.

Baselines

For Study 1, the naive reference is each base model without math training, evaluated on identical instances. The strongest existing comparison is the matched pair of general and math-specialized checkpoints of the same family, such as a Qwen2.5 base and its Math variant, which BeyondBench used to report the paradox. The file gives no reported number for that gap, so no reported result was found on Lacuna for the base-versus-math difference on BeyondBench. We add AbstRaL-trained models because AbstRaL is the most direct claim of structural abstraction transfer. It reports AIME24 rising from 13.3% to 16.7% for Qwen2.5-Math-7B, and GSM-Symbolic accuracy rising from 34.0% to 44.6% for Qwen2.5-0.5B. All models get the same prompts, the same decoding budget and tools-off and tools-on conditions. BeyondBench found disabling tools cost GPT-5 models up to 43%, so tools cannot be left uncontrolled. The claim of structural transfer is supported only if a model's post-training gain on distant surfaces is within noise of its gain on the math-flavored surface, measured over enough structures to bound $\mathrm{SS}$ tightly.

For Study 2, the naive references are random selection and raw-text nearest neighbours with Sentence-BERT. The strongest existing methods are SKILL-KNN, which reports 78.3% versus 74.6% execution accuracy for raw KNN on Spider with text-chat-davinci-002, and SALA, which reports an 85.23% average on Qwen2.5-7B versus 83.09% for PSL and 81.78% for random. All retrievers draw from the same demonstration bank, with the same number of shots, the same target model, and the same LLM for any rewriting step. The ablation that isolates our key ingredient is an oracle retriever that selects by verified logical equivalence of the latent rule sets. It shows how much accuracy logical matching could buy, and how much of that SKILL-KNN and SALA recover. A retriever beats the existing methods only if it closes a statistically significant share of the gap between SKILL-KNN or SALA and the oracle.

For Study 3, the baselines are the loss-based detectors studied in the fragility paper, LiRA, Min-K% and Loss. They are run on the same contaminated and clean models, and their post-reasoning-model AUROC was reported at 50–58%. Our audit beats them if the rendering gap separates contaminated from clean models with clearly higher AUROC in that same post-GRPO regime.

Why not just…?

Why not just use BeyondBench or DyVal, which are already contamination-resistant? They remove leakage, but each task family has one fixed abstract surface: Sudoku is always Sudoku, and DyVal's DAGs are always rendered as arithmetic or reachability. So they cannot tell whether a model fails because of the logic or because of the domain it is dressed in. We keep one BeyondBench suite as a sanity anchor, since model rankings should correlate on the abstract rendering. The questions in Studies 1–3 need the surface axis, which only a certified-equivalence generator provides.

Why not just extend GSM-Symbolic-style templates across domains? This is the most serious alternative. Hand-writing one template per domain for each problem would vary the surface. The weakness is that equivalence across hand-written domain templates is asserted, not checked, and near-misses must be built by hand. The CFD implication test makes both mechanical at scale. It also lets us sample structures rather than inherit ones from a public, possibly contaminated source item. If a pilot shows that template-level variation yields the same $\mathrm{SS}$ estimates, the practical case weakens to cost and scale, and we will report that honestly.

Why not let the model write SQL and call it solved? Violation detection does compile to SQL, so a tool-using model might simply translate and execute. We treat this as a condition, not a threat. Tool-on accuracy measures translation from language to rules. Tool-off accuracy measures reasoning. The gap between the two, split by surface, shows whether the translation step itself is surface-sensitive, which is the bottleneck OpenIKLR reported.

Why not just improve contamination detectors? The fragility paper traces their failure to reinforcement learning's importance-ratio clipping erasing the loss gap between seen and unseen items. Better loss statistics face the same erasure. A behavioral test on re-rendered items does not rely on loss at all.

Proposed Experiments and Decisive Checks

We will generate about 2,000 latent structures across four difficulty tiers. Each is rendered in eight domains, and each has at least two surface-twin near-misses. Ground truth comes from SQL violation queries in the style of the CFD paper and from brute-force implication and consistency checks. Open models are evaluated in general, math-specialized, AbstRaL and one-example-RL variants, with a few closed models in tools-on and tools-off modes. Metrics are tuple-level F1 for violation detection and accuracy for consistency and implication, along with $\mathrm{SS}$, the twin-ranking rate for retrievers, and the rendering-gap AUROC for contamination.

Two checks are decisive. The first is whether math-trained models' gains shrink as the rendering moves away from math. A clear yes resolves the conflict between AbstRaL-style transfer claims and BeyondBench's paradox in favor of surface transfer. The second is whether, after GRPO, deliberately planted contamination remains visible as a seen-versus-twin gap when loss detectors are at chance. A yes gives a practical audit tool for the models that current detectors cannot inspect.

We will also validate the instrument itself. Human annotators solve a sample of renderings, to confirm that domain changes do not change human difficulty. Otherwise a nonzero $\mathrm{SS}$ could reflect harder wording rather than surface-bound reasoning.