When a language model scores well on an old public benchmark, two explanations compete. It may have learned the skill, or it may have seen the test during training. The usual check compares the old benchmark against fresh problems, such as items written after the training cutoff or generated on the fly. That comparison is only fair if the fresh problems are exactly as hard as the old ones, and in practice nobody can certify this. We propose to close that gap for one well-defined skill: inferring a classification rule from labeled examples. For this skill, intrinsic difficulty can be computed exactly. Exact optimal decision-tree solvers, meaning algorithms that find the provably smallest tree consistent with the data, tell us the minimum depth and number of leaves any correct rule needs. That number is a certified measure of how hard the induction problem is.
The idea is to pair each famous public dataset with "twins." Monk's problems, Tic-tac-toe, Mushroom, and Nursery are all likely to appear in pretraining text together with their known rules. A twin is a freshly generated dataset with a new hidden rule that an exact solver certifies has the same optimal-tree complexity: the same number of features, arity, row count, class balance, minimal depth, and minimal leaf count. A model that solves Monk's-2 in context but fails its certified twins is showing memorization, and difficulty is no longer a confound. Adding a third arm, the original data with symbols remapped, separates token-level memorization from memorization of the dataset's structure.
Core Claim
Contamination estimates built on "old versus fresh" comparisons are biased by uncontrolled difficulty differences. Scalable exact tree solvers remove that bias for rule-induction tasks. The claim is new in two ways. First, the difficulty measure is certified rather than nominal. Generator-based dynamic benchmarks such as DyVal control the depth of the structure they generate, but a randomly generated depth-4 tree often has a much shallower equivalent on the sampled data. Its nominal depth therefore overstates its real difficulty. Second, the three-arm design (original, remapped, certified twin) splits a model's score on a public dataset into a skill component, a token-memory component, and a structural-memory component. We expect the structural component to be large for famous UCI datasets. If it is large, symbolic remapping alone cannot remove it.
Research Program
The method comes from the tree-scalability literature. Branches searches for optimal sparse trees as an AND/OR graph using best-first AO* search with an admissible "purification" bound. It handles multi-way categorical splits natively and converges on Mushroom in 0.15 seconds, where binarized branch-and-bound baselines time out. This is what makes certification cheap enough to run on tens of thousands of candidate tasks. For continuous features we use Quant-BnB, which decomposes split candidates into quantiles. Where we need depth-indexed optimal regression or classification profiles, we use the dynamic-programming approach of Piecewise Constant and Linear Regression Trees.
The generator works as follows. It samples a feature schema matched to a target public dataset, samples a hidden rule (a random tree, optionally with redundant branches), and draws rows from it. It then runs the exact solver to compute the task's complexity profile: the best achievable accuracy at each depth budget, together with the minimal depth and leaf count at which accuracy reaches 100%. A candidate becomes a twin only if this profile matches the target dataset's profile, which is computed by the same solver. The known memory cost of AO* on deep targets limits certification to roughly depth 6 on small categorical tables. That range covers the public datasets of interest, and we treat it as a stated scope rather than a weakness to hide.
On the evaluation side, models see a serialized table of labeled rows and must label held-out rows. In a second format, they must also output a rule, which we execute and check, so the verification is symbolic rather than judged by an LLM. The remapped arm follows the symbolic-remapping diagnostic of A²RBench: it renames features and values while keeping the rows. A²RBench supplies the remapping idea. Its rules, however, are free-form Python with no complexity bound, and its authors report a generative ceiling where the LLM author simplifies hard rules. Our generator has no LLM in the loop, so that ceiling does not apply.
We validate with controlled injection. Following Contamination Budget, which fine-tunes with LoRA on benchmark items at controlled repetition counts and finds that hard items need roughly 60 to 100 or more repetitions while general task logic degrades, we fine-tune open models on chosen public datasets at known doses. We then check whether the twin gap recovers the dose. This setup also answers a question the Contamination Budget paper leaves open: whether repetition helps on structurally deep rules or only on shallow ones. We test this by stratifying injected datasets by certified depth.
Baselines
The naive reference is raw in-context accuracy on the public datasets, taken at face value as a skill score. Any contamination method must show this number is inflated.
The strongest existing competitor is symbolic remapping alone, as in A²RBench, which reports a 17.7% performance drop when familiar tokens are remapped. Remapping preserves difficulty exactly and needs no solver, so it is the most serious threat. We run it on the same datasets, models, prompts, and row orderings as our twin arm. Our method beats it if, on models with injected contamination, the twin gap tracks the injected dose significantly better than the remapping gap does. We would measure this with rank correlation across doses and datasets. A second sign of beating it is a significant remapped-versus-twin gap on public datasets.
The second competitor is a DyVal-style dynamic benchmark: fresh tasks matched only on nominal generator depth. We run it from the same generator, with certification switched off. This ablation isolates the key ingredient. If nominal-depth matching yields the same contamination estimates as certified matching, the exact solvers are unnecessary. The 23% accuracy drop DyVal reports for GPT-3.5-Turbo across its difficulty levels shows how much these levels move scores, which is why mismatched difficulty can plausibly swamp a contamination signal.
The third competitor uses greedy CART depth as the matching criterion instead of exact optimal depth. We use the same candidate pool and the same matching tolerance. The comparison asks whether greedy over-estimation of depth, documented in Branches and A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees, actually changes which twins get selected.
Finally, we compare against black-box detectors run on identical prompts. These are perturbation sensitivity from PEARL and the anomalous-response flags of item-response adaptive testing from Efficiently Measuring the Cognitive Ability of LLMs. No reported result was found on Lacuna for LLM in-context rule induction on Monk's, Tic-tac-toe, Mushroom, or Nursery, nor for PEARL on tabular inputs. The baseline numbers on these tasks will therefore be ours.
Why not just…?
Why not just remap the symbols of the public datasets? This is the real threat, and the design tests it directly instead of dismissing it. Remapping removes memory of tokens but keeps every row and the hidden rule. A model that has absorbed "the Monk's-1 pattern" as a structure could still recognize it. If, under controlled injection, the remapped arm recovers the dose as well as the twin arm, we will report that remapping suffices for this task family. The solver's contribution then shrinks to providing the difficulty curve. We expect the opposite, because the A²RBench drop shows models lean on surface familiarity, and structural familiarity is the natural next layer down.
Why not just generate fresh tasks at a target depth without solving anything? Nominal depth is not difficulty. A sampled depth-d rule can collapse to a shallower optimal tree on finite data, and different samples collapse by different amounts. We will report the fraction of DyVal-style candidates whose certified depth differs from their nominal depth. We will also show whether contamination estimates computed under the two matchings disagree. If the disagreement is negligible, the certification step is overhead, and we will say so.
Why not just use CART, or a general MIP or SAT solver, to measure complexity? Greedy trees are deeper than necessary, so they would match twins on a biased statistic. General solvers are slow at this scale: Branches reports 5-minute timeouts for binarized branch-and-bound on UCI data where AO* finishes in a fraction of a second. Generating thousands of certified twins makes solver speed a practical requirement. The CART-matching ablation measures how much the bias matters.
Why not just use PEARL-style perturbation or IRT anomaly detection? PEARL itself reports that its detection weakens sharply outside verbatim completion. Neither PEARL nor the IRT approach says what was memorized. Both are run as baselines under the injection protocol, which gives a common ground truth for comparing them.
Proposed Experiments
The first experiment builds the certified twin set: 50 twins per public dataset for Monk's 1–3, Tic-tac-toe, Mushroom, and Nursery, drawn from the UCI collection used by Branches. We report solver time and acceptance rates. The second experiment runs the three-arm evaluation (original, remapped, twin) on open and closed models in both answer formats, alongside a fresh-task accuracy curve plotted against certified depth. On this curve, the public datasets should lie above the line if contaminated and on it if not.
The decisive check is controlled injection. We fine-tune open models on subsets of the public datasets at repetition doses ranging from 1 to more than 100, mirroring Contamination Budget. We then measure how well each detector recovers the dose: raw accuracy, remapping, nominal-depth twins, CART-matched twins, certified twins, PEARL, and IRT flags. We treat the work as successful if certified twins give the highest dose recovery and a significant remapped-versus-twin gap appears on injected models. Stratifying injected datasets by certified depth then shows whether repeated exposure teaches deep rules or only patches shallow ones. A null result on either check is still informative. It would show that cheaper remapping or nominal-depth tests are adequate for this task family.
References
- DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
- Branches: Efficiently Seeking Optimal Sparse Decision Trees via AO*
- Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features
- Piecewise Constant and Linear Regression Trees: An Optimal Dynamic Programming Approach
- A²RBench: An Automatic Paradigm for Formally Verifiable Abstract Reasoning Benchmark Generation
- Contamination Budget: Trade-offs Between Breadth, Depth and Difficulty
- A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees
- Memorization or Interpolation ? Detecting LLM Memorization through Input Perturbation Analysis
- Efficiently Measuring the Cognitive Ability of LLMs: An Adaptive Testing Perspective