Do Reasoning Paradoxes Survive Shortcut Removal? Tier-Wise Adversarial Filtering of Program-Generated Benchmarks

Several recent results seem to show that large language models (LLMs) reason in incoherent ways. Models solve a hard multi-step problem and then fail its strictly easier sub-problem. They also know every fact a task needs yet cannot combine those facts. These findings are usually read as flaws in the model's reasoning, described as "carelessness" or a "knowledge versus application" gap. There is a simpler explanation that nobody has ruled out. The hard version of a problem may contain a surface cue, such as a word or slot value that happens to correlate with the answer, and that cue may be absent from the easy version. A model that "solves" the hard problem through such a cue was never reasoning. Its failure on the easy problem is then no paradox at all.

We propose to test this directly. We will build reasoning benchmarks from small programs, so that every hard question comes with machine-generated, exactly labeled sub-questions at each level of a hierarchy: fact retrieval, then pairwise relations, then multi-step composition. We will then remove shortcuts separately at each level. The removal uses the program to state which partial views of an input cannot determine the answer, and changes slot values until cheap probes given only those views fall to chance. The goal is not mainly a new leaderboard. The goal is a controlled intervention showing how much of the documented hard-to-easy inconsistency and "complexity cliff" is shortcut use rather than reasoning failure.

Core Claim

The claim is narrow. Two published paradoxes rest on benchmarks that were never checked for shortcuts at the hard tier. The first comes from Can Large Language Models Always Solve Easy Problems if They Can Solve Harder Ones?, which builds easy/hard pairs from GSM8K, HumanEval and IFEval and reports consistency scores near 92% for frontier models. The second comes from Around the World in 24 Hours, whose templated GEOTEMP benchmark shows Llama 3-70B retrieving UTC offsets at about 90% and doing pure time arithmetic at near 100%, yet reaching only 25.4% on the joint task.

Do Large Language Models Perform Latent Multi-Hop Reasoning without Exploiting Shortcuts? estimates that 85.3% of an earlier multi-hop dataset was solvable through co-occurrence shortcuts. Avoiding Reasoning Shortcuts found single-hop shortcuts in 52% of HotpotQA bridge questions. Contamination of the hard tier is therefore a live possibility, not a pedantic one.

We expect one measured quantity to fall once shortcuts are removed at the composition tier while the logic of each item is held fixed: the "unsupported success rate," meaning the fraction of hard items answered correctly while some prerequisite sub-question is answered wrongly. If it does not fall, the paradoxes are real properties of the models, and we will have established that with a much stronger control than before. Either outcome is informative.

The methodological novelty is in what gets filtered. AFLite, from WinoGrande, scores each whole instance by how predictable its final label is from pretrained embeddings, and prunes the most predictable ones. That reduced 77,000 crowdsourced problems to 44,000. On the Limitations of Dataset Balancing argues that such balancing eventually strips away legitimate signal, because every combination of features cannot be balanced without making the data unlearnable. Our generator avoids this trap. Because it is a program, it can list "insufficient views": parts of the input that by construction cannot determine the answer. Examples are only the target city, only the template identifier, or the entity mentions with the bridging relation removed. We balance only against those views, tier by tier. Predictability from an insufficient view is by definition an artifact. Predictability from the full input is the signal we keep.

Research Program

The work has three stages. Each stage answers a question the previous one cannot.

Stage 1: correlational audit of existing benchmarks. This stage needs no new data. On ConsisEval, GEOTEMP and the released facebook/ExploreToM data, we will train cheap probes on insufficient views of each hard item: bag-of-slot-values classifiers, AFLite-style linear ensembles over frozen embeddings, and a small LM given the question with key entities masked. We will also compute SOCRATES-style pretraining co-occurrence between the head and tail entities. We then ask whether items in the "hard correct, easy wrong" cell carry higher shortcut predictability than items in the "both correct" cell. A positive correlation motivates the rest of the program. It cannot settle the question alone, because predictable items may also simply be easier.

Stage 2: tier-wise generation with shortcut repair. We will write generators in three domains. Each domain has a formal executor that labels every tier.

The first domain is geotemporal conversion, reusing GEOTEMP's cities and offsets. Level 1 retrieves an offset, Level 2 performs one conversion, and Level 3 chains conversions across locations.

The second domain is relational chains over knowledge triples, in the style of SOCRATES but extended past two hops. Level 1 asks for a single fact, Level 2 for a bridge entity, and Level 3 for the full chain at lengths two to four.

The third domain is ExploreToM's story language, whose state machine already exposes intermediate states. Level 1 asks where an object is, Level 2 who observed an event, and Level 3 a nested belief.

Every Level-3 item is emitted together with the Level-1 and Level-2 items that its program execution passes through. Its "easy" counterparts are therefore exact subsets in the ConsisEval sense, but guaranteed by construction rather than by semi-automatic prompting.

Repair proceeds tier by tier. For each tier and each insufficient view, we fit the probe ensemble and compute an instance-level predictability score. We then resample the slot values of high-scoring items within the same program, keeping the same operations, chain length and arithmetic. Resampling continues until the probe's held-out accuracy on that view is within a small tolerance of chance. Items are pruned only when no resample succeeds, and the pruning rate is reported per tier. Holding the program fixed is what makes this an intervention: filtered and unfiltered items have identical logical difficulty and differ only in their surface statistics.

Stage 3: measuring the paradoxes before and after repair. Writing $A_k$ for the event that tier $k$ is answered correctly, we report the unsupported success rate

$$U = P(A_3 \wedge \neg(A_1 \wedge A_2)),$$

and the tier-wise consistency

$$C = P(A_1 \wedge A_2 \mid A_3).$$

Here $C$ generalizes ConsisEval's two-level $P(\text{easy}\mid\text{hard})$ to three tiers. Each model is evaluated in three modes:

  • direct answer, with no intermediate tokens;
  • chain-of-thought, where the model writes out intermediate steps;
  • divide-and-conquer prompting, where sub-questions are answered in separate contexts, as in When Splitting Makes Stronger.

This also lets us test the open question from SOCRATES of whether direct-answer collapse (5% direct versus 70% with chain-of-thought on Year bridges) partly reflects chain-of-thought helping models avoid misleading cues, rather than only giving them working memory.

A secondary question is whether naturalness can be restored. We will apply an LLM paraphrase pass, verified by re-executing the parsed program, and then re-run the probes. Templates are criticized for rigid phrasing in COVR and Automatic Generation of Contrast Sets from Scene Graphs. Paraphrasing may reintroduce artifacts, and we will measure whether it does rather than assume it.

Baselines

Do nothing. The naive reference point is the original benchmarks and our unrepaired generator output, evaluated with the same models and prompts. Published anchors on the original data are the following:

We will reproduce these figures on our runs before comparing, because prompt and parsing differences matter.

End-to-end AFLite. This is the strongest existing filtering method: AFLite applied as in WinoGrande, scoring only final-answer predictability from full-input embeddings and pruning at the same overall rate our method prunes. It is the most natural competitor because it is the standard way shortcut-free benchmarks are built. It receives the same embedding model, the same ensemble size and split count, and the same number of tuning trials for its threshold. Our method beats it if, at a matched data budget, it achieves lower residual probe accuracy on insufficient views at Levels 1 and 2 while keeping the item distribution over program types closer to the original. AFLite is known to skew which programs survive. We measure this with a divergence between program-type histograms.

Corpus co-occurrence filtering. This is the SOCRATES method: pruning any item whose head and tail entities co-occur in a pretraining proxy corpus. It applies only to the relational domain. It is the strongest specific competitor there, because it targets exactly the memorization shortcut. We will run it on the same candidate pool and compare $U$ under each filter.

Matched random resampling. This ablation isolates our key ingredient. Slot values are resampled and items pruned at exactly our rates, but chosen at random rather than by predictability score. Any drop in $U$ that random resampling also produces is not due to shortcut removal.

Final-tier-only repair. A second ablation repairs only Level 3. It tests whether per-tier filtering matters, or whether Level-1 and Level-2 shortcuts are irrelevant to the paradox.

Why not just…?

Why not just run the Stage 1 correlation on existing benchmarks and stop? This is the most serious threat. If shortcut predictability strongly separates the "hard correct, easy wrong" cell from the rest, a reviewer could call the case made. But predictability is confounded with intrinsic ease: items with cue words may also be shorter, involve smaller numbers, or name more frequent entities. Only Stage 2's resampling, which holds the program fixed, separates "has a shortcut" from "is easier." We will report the Stage 1 result on its own. If the Stage 2 intervention merely reproduces it, the intervention adds confirmation rather than discovery, and we will say so.

Why not just use chain-of-thought or divide-and-conquer prompting on GSM8K or HotpotQA? Prompting changes how the model reasons, not what the benchmark rewards. Correct final answers often sit on top of unsound intermediate steps (Evaluating Intermediate Reasoning of Code-Assisted Large Language Models for Mathematics, Beyond Code). GEOTEMP reports that chain-of-thought hurt accuracy on simple tiers. We include all three prompting modes as conditions. The prediction is that the gap between direct answering and chain-of-thought shrinks after repair if chain-of-thought mainly helps models resist misleading cues.

Why not have a frontier LLM write diverse problems directly? That approach loses exact labels at the intermediate tiers, which are the whole point of the study. ExploreToM needed a formal story language to produce verifiably valid belief states. We keep an LLM only as a paraphraser whose output is checked by re-executing the program, and we measure whether it reintroduces artifacts.

Why not just balance unigrams or build contrast sets? Balancing single features leaves combinations of features exploitable, as the XOR argument in On the Limitations of Dataset Balancing shows. Contrast sets probe only the perturbations someone thought to write. Our insufficient-view probes are learned, so they capture combinations of features, but they are restricted to views the program proves uninformative. This avoids both residual shortcuts and loss of genuine signal. The comparison with matched random resampling tests whether that restriction matters.

Proposed Experiments and Decisive Checks

The models will be Llama-3.1-8B and Llama-3.1-70B-Instruct, together with GPT-4o and Claude 3.5 Sonnet through their APIs. Each runs in all three prompting modes on the original benchmarks, on our unrepaired generator output, and on each filtered variant. We will draw roughly 2,000 Level-3 items per domain, plus their sub-items, and report bootstrap confidence intervals on $U$ and $C$.

The decisive check is the change in $U$ from unrepaired to tier-wise-repaired data, compared with the change under matched random resampling. Two other outcomes would each be informative:

  • A drop in $U$ significantly larger than under random resampling would support the shortcut account of the paradoxes.
  • No difference would mean the hard-to-easy inconsistency and complexity cliff hold up under shortcut control. They would then deserve the mechanistic explanations currently proposed for them.

Three further checks guard the interpretation:

  • Resampling must not change logical difficulty. The program executor solves 100% of items in both versions, and a human sample on 200 items per domain should show no accuracy difference.
  • The filter must leave real signal. Probes on full inputs, as opposed to insufficient views, should still learn the task when trained on repaired data, which answers the concern that filtering makes data unlearnable.
  • Paraphrasing must not undo the repair. After the paraphrase pass, insufficient-view probe accuracy should stay near chance.

Finally, on the relational domain, comparing our filter against SOCRATES co-occurrence pruning will show whether distributional artifacts inside the templates matter beyond memorized pretraining co-occurrence, a distinction no existing benchmark can draw.