Preference Cycles as a Contamination-Resistant Probe of LLM Reasoning

Benchmarks that generate fresh test problems on the fly were introduced to stop language models from scoring well simply because the test questions leaked into their training data. The best-known such generator builds every problem on a directed acyclic graph, meaning a dependency structure with no loops. Problems with no loops can always be solved by one fixed recipe: sort the variables so that each one comes after everything it depends on, then resolve them in that order. We propose that this recipe is itself something a model can memorize. If so, a model trained on the generator's outputs, or on anything resembling them, would score well on fresh problems without reasoning about them. This is contamination of the generator rather than of individual test items.

The proposal is to build problems whose dependencies form loops, drawn from preference reasoning, where loops are common. A conditional preference network (CP-net) describes how a person ranks options attribute by attribute: "all else equal, I prefer red wine if the main course is meat." It becomes cyclic when, for example, the wine choice depends on the food and the food choice depends on the wine. In a cyclic network no sorting order exists. Even so, the question "is there an outcome that no single attribute wants to change?" has an exact, cheaply checkable answer, which is a satisfiability problem and is solvable in linear time for yes/no attributes. Our central claim has two parts. First, models that do well on loop-free preference and reasoning problems will degrade sharply and measurably on matched cyclic ones. Second, accuracy gained by fine-tuning on loop-free generator outputs will transfer much less to cyclic problems than to new loop-free ones. That second gap measures how much of a dynamic-benchmark score comes from template contamination.

Grounding and what is new

Two lines of prior work motivate this. DyVal generates math, logic and algorithm problems from DAGs at four complexity levels. Its authors found that models with strong static scores, such as phi-1.5 and WizardMath-13B, scored "nearly zero" on its problems. They also found that merely reversing the order in which the DAG is described cost GPT-4 13.6% on reachability. That order sensitivity is a hint that models lean on the sorted presentation. DyVal, however, never removes the existence of a sorting order, which is the variable we manipulate. Separately, Hazra et al. observed that LLM accuracy on 3-SAT craters at the phase transition where familiar templates stop working. This supports the general idea that structural hardness, not surface novelty, separates template use from computation.

Three works supply the method. Brafman and Dimopoulos (2003) gave cyclic CP-nets a "weak semantics," a reading in which a loop is not treated as a contradiction. Under it, a strongly optimal outcome is one where no attribute wants to flip given its parents. They showed that finding such an outcome is a constraint satisfaction problem, reducing to 2-SAT for binary attributes. Prestwich et al. (2005) compiled local preferences into global hard constraints that a standard SAT solver can check for undominated outcomes, uniformly over cyclic networks. We use both as exact answer checkers. Xia et al. (2008) proved that acyclic CP-nets represent a vanishing fraction of possible preference orders, shrinking as $O((2^{0.2})^{-|X|})$ in the number of attributes $|X|$. A benchmark restricted to DAGs therefore samples a structurally narrow corner of the space.

One result constrains the design. Goldsmith et al. (2005) showed that pairwise dominance testing in cyclic CP-nets is PSPACE-complete. We therefore ask dominance questions only on networks small enough to verify by brute force, and we make optimal-outcome questions, which are tractable, the main task.

The closest connecting work is different in kind. Preference Leakage shows that LLM judges inflate the scores of students trained on data from the judge's own model family. Nonparametric LLM Evaluation from Preference Data shows that cycles in leaderboard data break Bradley-Terry rankings. Both treat cycles in judges' pairwise votes. Neither uses cyclic preference structures as the content of test problems, and neither studies contamination of a problem generator.

Research Program

We will build a generator, CycPref, that samples binary-attribute CP-nets and renders them as natural-language scenarios with randomized attribute names and domains. The scenarios cover meals, travel plans, team assignments and abstract tokens. Rendering order is randomized so that no presentation order leaks structure.

Cyclic networks are, conveniently, easier to sample uniformly than acyclic ones. Allen et al. (2016) showed that naive edge addition badly over-represents some shapes; a 5-node star admits over a million CP-nets versus 32 for a chain. Their exact sampler covers only DAGs. Once the acyclicity constraint is dropped, each node's parent set can be chosen independently. Weighting each parent set by its number of conditional preference tables then gives exact uniform sampling over labeled CP-nets with bounded in-degree. We will correct for degenerate tables, in which a listed parent has no effect, by rejection, and check uniformity empirically on small $n$ by enumeration. This sampler also addresses Gap 3 of the file as a side product.

Each instance is tagged by structural knobs: the number of attributes (6 to 30), the size and number of strongly connected components (groups of attributes that all depend on each other through loops), the cycle lengths, and the number of strongly optimal outcomes. That count can be zero, one or many. The zero case is essential: a correct model must say "none exists," which a guesser cannot fake.

The main task is "give an outcome that no single attribute would change, or say none exists." A checker verifies any returned outcome, so all valid answers are accepted, and the 2-SAT reduction gives the existence ground truth. A secondary task on networks with at most 10 attributes asks whether outcome A dominates B, answered by brute-force search of improving flip sequences.

For every cyclic instance we generate a matched acyclic twin. The twin has the same attribute count, in-degree distribution and number of preference-table entries, and its loops are cut by deleting one edge per strongly connected component and re-drawing the affected tables. Its answer distribution is rebalanced to the same share of "none" and multiple-solution cases. Rebalancing is needed because acyclic CP-nets always have exactly one optimal outcome under the standard sweep. To make "none" possible in the acyclic arm, we add hard feasibility constraints in the style of Prestwich et al.

The contamination experiment comes next. We fine-tune open models on a large pool of acyclic CycPref instances with step-by-step sweep solutions, which simulates generator leakage. As a second leakage source, we use DyVal outputs from PromptBench. We then measure inflation on three held-out sets: fresh acyclic instances, fresh cyclic instances, and rephrased acyclic instances. The rephrased set follows Yang et al. (2023), who showed that rephrased test items lifted Llama-2-13B on MMLU from about 55 to about 86 while evading n-gram filters.

We define the template-transfer ratio

$$\rho = \frac{\Delta_{\text{cyc}}}{\Delta_{\text{acyc}}},$$

where $\Delta_{\text{acyc}}$ and $\Delta_{\text{cyc}}$ are the accuracy gains from fine-tuning on fresh acyclic and fresh cyclic held-out instances. A $\rho$ near 1 means the cyclic set is just as contaminable as the acyclic one. A $\rho$ near 0 means the acyclic gains came from a recipe that loops defeat. As an honest control, we also fine-tune on cyclic instances with a fixed solver-trace format. This tells us whether any structure is merely harder to contaminate or whether the effect is specific to the existence of a sorting order.

Baselines

The naive reference point is a format-aware guesser. It outputs a uniformly random assignment, or "none" at the empirical base rate, and it locally repairs violations for one pass. This sets the chance floor for each structural bin. Because the checker accepts any valid outcome, the floor is not trivial on instances with many optima, and we report it per bin.

The strongest existing evaluation method is DyVal itself (Zhu et al. (2023)), run through PromptBench on the same models with the same sampling temperature, prompt budget and 500 instances per setting as in that paper. For reference, the paper reports that GPT-3.5-Turbo arithmetic accuracy drops 23% from level D1 to D4, and that GPT-4 reachability drops 13.6% under reversed description order. For LLMs on CP-net preference reasoning specifically, no reported result was found on Lacuna. CycPref beats DyVal as a contamination probe if two things hold. Its cyclic arm must show a significantly smaller template-transfer ratio than DyVal's fresh instances after fine-tuning on DyVal outputs, with the same fine-tuning compute and data volume. And its cyclic-versus-acyclic accuracy gap must exceed DyVal's D1-to-D4 depth gap at matched input length.

The ablation that isolates the key ingredient, the presence of loops, is the matched acyclic twin. It shares size, density, answer distribution and rendering, so any gap between twins is attributable to the absence of a sorting order. A second ablation presents the identical 2-SAT instance as a raw logical formula instead of a preference story. This separates "loops are hard" from "preference language is hard." Exact solvers using the Brafman–Dimopoulos 2-SAT encoding and the Prestwich Hard-Pareto constraints serve as the 100% ceiling and as the source of ground truth, not as competitors.

Why not just…?

Why not just make DyVal graphs deeper or reverse their order? Depth and order perturbation stress models while leaving the sorting recipe valid, so a memorized sweep still applies once the model re-sorts internally. The 13.6% reversal drop that DyVal reports is consistent with this, since it is far from collapse. Our matched-twin design tests the question directly. If deep DAGs at matched length produce the same accuracy loss and the same transfer ratio as cyclic networks, the loop hypothesis fails, and we will report that.

Why not just give models 2-SAT formulas, since the cyclic task reduces to 2-SAT anyway? This is the most serious threat. If raw 2-SAT and the cyclic CP-net instances behave identically, the preference framing adds nothing beyond a familiar logic puzzle. The raw-formula ablation settles it. We expect a difference in both directions: the story framing may help by offering commonsense structure, or hurt by inviting models to resolve loops by intuition. We treat either outcome as informative, and we present CycPref's value as instances that stay fresh and structurally controlled rather than as an inherently different problem.

Why not just rely on fresh-data benchmarks like LiveBench or rephrase-robust detection? LiveBench and MMLU-CF guard against instance leakage. Yang et al. show that detection catches rephrasings. None of these addresses a model that has learned the solving procedure for a generator family, which is the failure mode we target. Our rephrased-acyclic held-out set reproduces instance-level contamination, so the experiment shows directly whether cyclic structure adds protection beyond freshness.

Why not just use the cycles in judge votes as a leakage detector? It is tempting to read intransitivity in LLM-judge tournaments as a signal of preference leakage. But the nonparametric ranking work shows such cycles arise from ordinary context dependence. When provenance is known, the Preference Leakage Score measures leakage directly. We therefore do not build on that signal.

Proposed Experiments

We evaluate open models of several sizes, plus API models where available, on 500 instances per structural bin, with checker-verified accuracy and F1 on detecting "none exists." The first decisive check is the twin gap. Accuracy on cyclic instances should fall below accuracy on matched acyclic twins, with the gap growing in the size of the largest strongly connected component rather than in the attribute count. The second is the transfer ratio after fine-tuning on acyclic sweep traces, with an expected $\rho$ clearly below the value from fine-tuning on DyVal and testing on fresh DyVal. The third is the cyclic-trace control: if fine-tuning on cyclic traces yields full transfer, cyclic problems are contaminable too, and the benchmark's protection lasts only until its generator family leaks. That would be a useful and publishable bound in its own right. Finally, a qualitative audit of model reasoning on zero-solution instances will measure how often models assert circular justifications, for example "food is meat because wine is red because food is meat." This connects to the "unsubstantiated response" failure category that DyVal found in 33.8% of GPT-4 errors.