Every contamination-resistant benchmark still keeps an answer key somewhere. That key can leak into training data, or it limits the benchmark to problems its authors could already solve. This proposal removes the key. We build two-player games over integer counters, where one player tries to reach a target configuration and the other tries to avoid it forever. A model is scored only on a certificate it produces for its claimed winner. If it says the avoiding player wins, it must give a closed-form invariant. If it says the reaching player wins, it must give a strategy plus a ranking function, a quantity that strictly decreases until the target is hit. A program then checks the certificate in linear integer arithmetic, which is mechanically decidable. Deciding who wins such games is undecidable in general, but checking a proposed proof of the winner is not. That asymmetry lets the benchmark include instances that no solver, and no benchmark author, has resolved. A model cannot have memorized an answer that does not exist.
The theory of integer-valued games gives the hardness knob. Alur and Raghothaman show that reachability games on additive register automata are decidable (EXPTIME-complete) when counters stay non-negative. With general integers they become undecidable, because the games can simulate two-counter Minsky machines, a simple universal model of computation (Decision Problems for Additive Regular Functions). Faella and Parlato show that when the avoiding player has only finitely many choices per move, these games reduce to constrained Horn clauses, a logic format that off-the-shelf solvers (Z3's SPACER engine) handle quickly, solving hard Cinderella-Stepmother instances in about 2 seconds (Reachability Games Modulo Theories with a Bounded Safety Player). We use the first result to define instance families and the second as the strongest symbolic competitor.
Core Claim
Certificate-graded integer games give a reasoning test with four properties no benchmark in the file combines. First, there is an unbounded supply of fresh instances with no published answers. Second, every claimed solution is checked soundly. Third, hardness is set by structural parameters rather than by what an author model can write. Fourth, a built-in contamination probe compares famous games to disguised but provably equivalent copies.
One honest qualification shapes the design. Undecidability is a property of a class of games, not of a single instance. Any particular instance either has a certificate or does not. What matters for each instance is how complex its shortest certificate is: the number of linear constraints in the invariant, or the form of the ranking function. We therefore use the non-negative versus general-integer split to generate families, but report results against certificate complexity and solver status. We do not claim that models "fail at undecidability."
Research Program
Instance generator. The generator builds turn-based games over $m$ integer counters. Moves apply additive updates $x := y + c$ under linear guards. The avoiding player picks from $k$ choices per turn. The reaching player may pick an integer parameter within linear constraints, which matches the asymmetric setting of Faella and Parlato.
The parameters are $m$, $k$, guard depth, whether counters may go negative, and the size of an embedded Minsky machine. For the general-integer family, we also compile small two-counter machines into games. Machines whose halting status is known (from enumeration of tiny machines) give labelled anchors. Fresh random machines give instances that are genuinely open.
Solver labelling. Each instance is run through the Horn-clause reduction with SPACER under a fixed timeout. Instances are labelled reach-wins, avoid-wins, or unknown. The unknown items stay in the benchmark because a correct certificate can still be checked for them.
Certificate checker. For an avoid-wins claim, the model supplies an invariant $I$ over the counters. The checker confirms three Presburger-arithmetic facts: the start state lies in $I$, $I$ contains no target state, and from every state in $I$ some avoider choice keeps every reaching-player response inside $I$. Presburger arithmetic is the first-order theory of integers with addition, and its validity is decidable.
For a reach-wins claim, the model supplies a strategy term and a ranking function $V$ mapping states to the naturals. The checker confirms that, under the strategy, $V$ strictly decreases outside the target against all $k$ avoider responses.
Contamination probe. Classic integer games such as Nim, subtraction games, Euclid's game and Cinderella-Stepmother are presented in two forms. One is canonical. The other is transformed by renaming, counter offsets, sign flips and invertible affine maps. Each transformation carries a known mapping of certificates, so ground truth is preserved exactly.
We call the accuracy difference between the two forms the familiarity gap. It is our direct measure of memorization. It plays the same role as the symbol-remapping drop of 17.7% in A²RBench, but here it is backed by a formal isomorphism rather than surface renaming.
Related work and how this differs. Three lines of prior work motivate this design. GAMEBOT evaluates intermediate reasoning in dynamic finite games and reports GPT-4o at 0.52 on subproblems, but every game is finite-state. DyVal generates reachability tasks on acyclic graphs, with no loops or counters. The 3-SAT study shows GPT-4's search accuracy collapsing to about 10% at the hardness phase transition, but stays within single-agent NP problems.
P⁴Bench is the closest relative in spirit. It also separates the problem from the answer, using zero-knowledge proofs. It is limited to NP relations, and it still assumes some valid answer exists and is known to be checkable. Our certificates certify infinite-horizon properties, invariants and termination, that no NP witness expresses.
Two further papers set constraints on the design. The A²RBench "generative ceiling" shows that author models quietly simplify hard rules, which is why our generator and checker are purely symbolic. The Turing-completeness constructions for Magic show that undecidable mechanics arise naturally in real games. We use their counter-machine style of encoding but not their rule sets, which are too large to state in a prompt.
Baselines
Do-nothing reference. This baseline outputs the majority winner label, plus a classifier trained on surface features of the prompt: length, number of counters, and presence of negative constants. This mirrors the length heuristic the 3-SAT study found models exploiting. Under certificate grading it scores zero by construction. Under answer-only grading it tells us how much a win/lose label can be guessed. Our grading must show a large gap between these two numbers, or certificates add nothing.
Strongest existing method. The strongest competitor is the "LLM-modulo" pipeline: the model translates the game into Horn clauses and SPACER solves them. This is the best available because translation to MiniSAT gave nearly 100% accuracy on 3-SAT word problems (Can Large Language Models Reason? A Characterization via 3-SAT). The solver side is also proven on this exact game class, at about 2 seconds on Cinderella-Stepmother where CabPy, SimSynth and MSO-D timed out at 10 minutes (Reachability Games Modulo Theories with a Bounded Safety Player). No reported result was found on Lacuna for any LLM on games modulo theories, by direct solving or by translation.
The pipeline gets the same instances and the same token budget as direct solving. The solver gets the same timeout used for labelling. Its certificate is extracted from the solver's model or refutation and checked by the same checker. Direct model reasoning counts as beating it only on the unknown-status items, and only by producing checked certificates there. On solver-resolved items we do not expect direct reasoning to win.
Isolating ablations. The first ablation grades identical model outputs by final answer only versus by certificate. It isolates how much apparent skill is unverified guessing; DyVal found 33.8% of GPT-4 failures were unsubstantiated answers. The second ablation compares canonical and disguised versions of famous games, which isolates memorization.
Why not just…?
Why not just use random 3-SAT or P⁴Bench's SAT and discrete-log instances? They are contamination-resistant, and their hardness is controlled. But a satisfying assignment is the only certificate they offer, and unsatisfiable instances have no short witness. They also cannot express "this player can avoid the target forever," which requires an inductive invariant.
This is a real threat if the two kinds of hardness turn out to be one ability. We test it directly by running the same models on the 3-SAT benchmark and on our suite, then correlating per-model scores. If the scores are near-perfectly correlated, our suite is redundant, and we will say so.
Why not just grade the win/lose answer against a solver label? Labels exist only for solved instances. They form a fixed key that can leak. And binary answers are guessable at about 50%. The answer-only versus certificate ablation measures exactly how much this inflates scores.
Why not just have the model translate to Horn clauses and call Z3? This is the strongest alternative, and it may dominate everything the solver can decide. We include it as a full track rather than arguing it away. The benchmark's distinct claim rests on two things this pipeline cannot cover. One is the solver-unknown items. The other is the familiarity gap, which measures memorization in either track.
Why not just refresh items monthly from post-cutoff sources, as LiveBench does? LiveBench works, with o1-preview at 64.7% overall. But it needs ongoing curation, replacing a sixth of its tasks each month, and its items are not ordered by any controlled hardness parameter. Our items are fresh by random seed and ordered by structure.
Proposed Experiments
We will generate about 10,000 instances, stratified by counter count, choices per turn, non-negative versus general-integer updates, and solver status. A held-out set of the unknown-status items is never solved by us. A probe set covers four classic games, each in canonical form and in five transformed forms.
Open and frontier models are evaluated by direct certificate generation and by the translation pipeline. The metrics are certificate validity rate, answer-only accuracy, the familiarity gap, and validity as a function of the size of the solver's own certificate.
Three outcomes decide the project's value. First, if the familiarity gap is large on canonical Nim-like games but near zero on fresh instances, that is direct evidence of memorized game knowledge. GAMEBOT- and DyVal-style tests cannot show this, because they lack exact isomorphisms. Second, the answer-only score must exceed certificate validity by a wide margin, or certificate grading is unnecessary. Third, the critical result is whether any system produces checked certificates on solver-unknown items. Even a few would show the benchmark can measure reasoning beyond its authors' tools. Zero across all systems would mean the open tier currently measures only a ceiling, which is still a useful, leak-proof reference point.
References
- Decision Problems for Additive Regular Functions
- Reachability Games Modulo Theories with a Bounded Safety Player
- A²RBench: An Automatic Paradigm for Formally Verifiable Abstract Reasoning Benchmark Generation
- GAMEBoT: Transparent Assessment of LLM Reasoning in Games
- DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks
- Can Large Language Models Reason? A Characterization via 3-SAT
- $\text{P}^4$Bench: Contamination-Proof, Publicly Verifiable, and Privacy-Preserving LLM Evaluation via Zero-Knowledge Proofs
- Magic: The Gathering Is Turing Complete
- LiveBench: A Challenging, Contamination-Limited LLM Benchmark