Image generators that "think before they draw" still fail on pictures whose correctness is a matter of logic rather than looks. Unified models that understand a concept almost perfectly often cannot draw it. On structured visuals such as charts, figures and puzzles, even the best systems stay below 50% accuracy. A large part of the problem is training signal. Almost every reward these models are trained on comes from another neural judge, and almost no training set lets you turn difficulty up one controlled notch at a time.
We propose to get both properties from an unexpected source: complexity theory's proofs that board games are hard. A PSPACE-completeness reduction is a recipe that compiles a logic formula with alternating "there exists / for all" quantifiers into a game board, so that the first player wins exactly when the formula is true. Read in reverse, that recipe is a data generator. It produces boards of any size whose winner, and whose correct move at each decision point, is known for certain from a small formula. Its difficulty is set by one knob, the number of quantifier alternations. Symmetric boards supply the easiest rung of the ladder: there the correct reply is simply the mirror image of the opponent's move.
We use these boards to train and test an image editor. The editor sees a picture of a game position and must draw the next position with the correct move made. We train it with an easy-to-hard curriculum ordered by alternation depth, and reward it with an exact checker instead of a neural judge.
Core Claim
Our claim is that alternation depth is the right difficulty axis for curriculum reinforcement learning of reasoning-guided image editing. The baselines are two other ways of spending the same compute: graph size, which is the obvious difficulty axis, and a uniform mixture of difficulties. With an exact verifier, a depth-ordered curriculum should push a unified model further along the "draw the winning move" task. It should also transfer better to existing structured-visual editing benchmarks than an equal amount of generic code-rendered structured data.
A secondary claim targets shortcut learning. We will include "mirror-trap" boards: boards that are almost symmetric, where copying the mirror move loses. These separate a model that has learned to reason about the game from one that has learned to copy reflections.
Background and What Is Different
Four bodies of work meet here, and each plays a different role.
Two papers supply both the hard boards and the mirror tier. The Complexity of Two Colouring Games proves that orthogonal colouring on a pair of graphs is PSPACE-complete for three or more colours, using a reduction from Alternating QSAT. The same paper shows that when the graph has a "strictly matched involution", a self-inverse pairing of vertices that preserves adjacency, the second player draws by mirroring. In the same spirit, The Largest Connected Subgraph Game proves PSPACE-completeness via a reduction from POS CNF and identifies "reflection graphs" on which mirroring forces a draw. Both papers are purely theoretical. We reuse their constructions as instance generators and never ask a model to prove anything.
Both papers also show that recognising these symmetries is hard in the worst case: NP-complete in the first, GI-hard in the second. One tempting story is that a visual model could "beat" this hardness. We reject that story. We plant the symmetry ourselves and certify it with a graph-automorphism tool, as in Symmetry Detection in General Game Playing. The hardness results matter to us only as a warning that mirror tasks must be constructed, not mined. Computing Game Symmetries and Equilibria That Respect Them shows that respecting symmetry can be strictly worse than breaking it in coordination games. That result motivates the mirror-trap boards: symmetry is a heuristic the model must learn when to drop.
The training method comes from the reasoning-guided generation line. T2I-R1 writes a textual plan before generating image tokens and optimises with GRPO. GRPO is a reinforcement learning method that scores a group of samples for the same prompt against each other. AlphaGRPO breaks prompts into checkable rubrics scored by a multimodal verifier, and applies a correction for false positives during iterative editing. Both rely on neural verifiers and on a fixed mix of task categories. We replace the verifier with an exact pixel-level parser plus a game oracle, and we replace the fixed mix with a difficulty schedule. Factuality Matters supplies StructBench and a 1.3M-pair corpus of code-rendered structured visuals. Its three training stages are about aligning modalities, not about task difficulty, and its corpus serves as our "just add more structured data" control. GIR-Bench motivates the work: unified models score 0.99 on understanding but 0.20–0.68 on generating the same concepts, and its Edit split already contains Sudoku-style visual logic.
The curriculum logic comes from A Task-centric Theory for Iterative Self-Improvement with Easy-to-Hard Curricula. That paper proves easy-to-hard training beats a fixed mixture when three conditions hold: the model can already solve the first stage, successive stages are only moderately harder, and the sample budget is large enough. Its proofs assume a noise-free binary verifier, which multimodal work rarely has and we do. Its experiments use only single-agent problems (shortest path, GSM8K). Our setting is therefore a clean test of the theory on adversarial, alternating-quantifier problems. OpenVLThinker shows that medium-to-hard staged GRPO prevents collapse in vision-language reasoning, but only for understanding, never for generation.
Research Program
The board compiler. We will reimplement the two cited reductions as programs. The orthogonal colouring reduction from Alternating QSAT is the primary game, because one game then contains both the mirror tier and the hard tier. The Largest Connected Subgraph reduction from POS CNF is a second game used to check generality. Each program takes a quantified formula and outputs a graph with fixed drawing coordinates and a rendered image. For each position it also labels which moves at variable-gadget decision points keep the winning branch.
These labels are exact even when the board is far too large to search, because the truth of a formula with four to six variables is trivial to evaluate. We score only gadget decision points, since moves elsewhere may have many equally good options. On small boards we cross-check every label by exhaustive retrograde search, in the style of Material Symmetry to Partition Endgame Tables. This check catches implementation errors in our reductions, which we consider the main engineering risk.
The difficulty ladder. Stage 0 asks the model to copy a board and apply a specified move. This tests rendering fidelity alone and guarantees that the model can solve the first stage, as the theory requires. Stage 1 gives boards with a planted strictly matched involution or reflection, where the correct reply is the mirror of the opponent's last move. Stage 2 gives mirror-trap boards, built by perturbing one edge of a symmetric board so that the mirror move provably loses. Stages 3 through k use gadget boards compiled from formulas with alternation depth 1 through k.
Training. The base model is Bagel, an open unified model used in the WISE, PRISM-Bench and AlphaGRPO evaluations. A short supervised phase teaches it to write a textual plan (whose move it is, which gadget is live, what is reflected) before editing. Curriculum GRPO follows. The reward is computed by sampling pixel colours at the known vertex coordinates. It is positive only if exactly one vertex changed, the change was a legal move, and the move is oracle-correct. A penalty applies to any changed pixels outside the moved vertex, which targets the drift problem AlphaGRPO reports. The model advances to the next stage when its pass rate on held-out boards crosses a threshold.
Baselines
The naive reference point is the base Bagel model, prompted zero-shot with and without its built-in thinking mode, on our game boards and on the transfer benchmarks. On transfer, the file reports BAGEL at a WiScore of 0.52 without CoT and 0.70 with CoT on WISE, and 65.1 on PRISM-Bench (FLUX-Reason-6M). We will re-measure these numbers under our own evaluation harness rather than rely on reported figures.
The strongest existing method is AlphaGRPO-style training: GRPO with decompositional neural-verifier rewards over a uniform mixture of task categories. AlphaGRPO reports 83.9% overall accuracy on TIIF-Bench, 5.8 points over Bagel. To compare fairly, we run that recipe on our exact board data, from the same initial checkpoint, with the same number of GRPO steps, the same group size and the same hyperparameter search budget. The only differences are the schedule and the reward. Beating it means three things. First, higher oracle move accuracy at depths 3 and above. Second, higher mirror-trap accuracy. Third, a StructBench StructScore gain that is statistically separable across three seeds. For StructBench, Factuality Matters reports that all evaluated models, proprietary ones included, stay below 50%, and that test-time reasoning gives open models a gain of roughly 30%.
For our own game-board benchmark there is no prior number: no reported result found on Lacuna for image-based play of orthogonal colouring or largest-connected-subgraph positions. For GIR-Bench-Edit we likewise found no reported per-model number on Lacuna. GIR-Bench's T2I numerical split tops out at 0.362 accuracy.
Three ablations isolate the key ingredient. The first, a size curriculum, matches our schedule's sequence of vertex counts and image complexity but samples alternation depth uniformly. If it matches the depth curriculum, our central claim is wrong. The second, a skip curriculum, jumps from stage 1 straight to depth 4. It tests the moderate-separation prediction, under which this schedule should stall. The third removes the mirror tiers, measuring whether symmetry tasks are a useful stepping stone or just noise.
Why not just…?
Why not just use nauty and a QBF solver? For playing these games, they win outright, and we use both inside the data generator. The object of study is not game solving. It is whether an image editor can carry out a logically constrained edit faithfully. Symbolic solvers produce no image, so they bound the label quality and do not compete as a method.
Why not just have a vision-language model pick the move and render it with code? This is the real threat, so we run it. The "decoupled" pipeline is the same model's understanding head choosing a move, with our renderer drawing it. It is the practical ceiling on our game benchmark, and the distance between it and end-to-end editing is a direct, exactly measured version of the understanding–generation gap documented by GIR-Bench. The proposal earns its keep only through two results. One is that curriculum training closes most of this gap. The other is that it improves benchmarks such as StructBench, where no renderer is available to fall back on. If neither result holds, we will report that rendering via tools is the better path.
Why not just train on more generic structured visuals? Factuality Matters already gives 1.3M code-rendered pairs. Our control spends the same GRPO compute on those pairs, with code-derived exact rewards, and the transfer comparison on StructBench and GIR-Bench-Edit settles whether game-derived, depth-controlled data adds anything beyond volume.
Why not just run uniform GRPO, since strong models discover strategies on their own? The task-centric theory and the 1B-model regression it reports suggest that uniform mixtures fail when hard instances are out of reach. But that evidence comes from text math, not image editing. The uniform-mixture baseline described above tests this directly. A tie would mean our verifier, not our schedule, was doing the work.
Proposed Experiments
The main experiment trains the depth curriculum, the size curriculum, the skip curriculum, uniform GRPO and the generic-structured-data control, each with three seeds and equal compute. All are evaluated on held-out boards from both games at depths 1–6, where we measure oracle move accuracy and the fraction of off-target pixels changed. All are also evaluated on StructBench, GIR-Bench-Edit, GIR-Bench-T2I, WISE and TIIF-Bench. The last two check that general text-to-image ability does not regress.
We expect the decisive evidence from three checks. The first is a depth-generalisation curve: accuracy at depth k+1 after training through depth k, compared between the depth and size curricula. The second is mirror-trap accuracy compared against mirror-board accuracy. A model that is high on mirror boards but at chance on traps has learned a reflection shortcut. The third is cross-game transfer: training on colouring and testing on Largest Connected Subgraph positions, which separates game-specific pattern matching from transferable visual reasoning.
A final analysis relates the observed stall points to the theory's separation condition. We vary the depth increment between stages and check whether a threshold exists beyond which self-improvement stops. Such a threshold would extend the theory's predictions from single-agent problems to alternating-quantifier ones.
References
- The Complexity of Two Colouring Games
- The Largest Connected Subgraph Game
- Symmetry Detection in General Game Playing
- Computing Game Symmetries and Equilibria That Respect Them
- T2I-R1: Reinforcing Image Generation with Collaborative Semantic-level and Token-level CoT
- AlphaGRPO: Unlocking Self-Reflective Multimodal Generation in Unified Multimodal Models via Decompositional Verifiable Reward
- Factuality Matters: When Image Generation and Editing Meet Structured Visuals
- GIR-Bench: Versatile Benchmark for Generating Images with Reasoning
- A Task-centric Theory for Iterative Self-Improvement with Easy-to-Hard Curricula
- OpenVLThinker: Complex Vision-Language Reasoning via Iterative SFT-RL Cycles
- Material Symmetry to Partition Endgame Tables
- WISE: World Knowledge-Informed Semantic Evaluation for Text-to-Image Generation
- FLUX-Reason-6M & PRISM-Bench: A Million-Scale Text-to-Image Reasoning Dataset and Comprehensive Benchmark