Image generators that "think before drawing" are usually judged by how many objects and relations a prompt contains. We propose to judge them instead by what kind of logic puzzle the prompt actually poses. Some spatial instructions define puzzles that can be solved by repeatedly checking pairs and triples of objects against each other. "A is left of B, B is left of C, C is not left of A" is one of these. Other instructions define puzzles that provably need search. "Seat these seven guests clockwise around a round table so that each listed triple appears in clockwise order" is an example, and so is "put these objects on three shelves so no two rivals share a shelf." The two kinds can look identical on the surface: the same objects, the same number of relations, the same everyday words. Theoretical computer science has sorted such families precisely into easy ones (solvable in polynomial time) and hard ones (NP-complete). Our hypothesis is that this sorting, and not prompt length or whether a relation is directional, predicts where the planning step of reasoning-guided generators fails, and where writing out a chain of thought helps or hurts.
The practical stake is that reasoning-guided generation now depends on text plans and per-constraint rewards. The literature disagrees about whether that reasoning helps. Chain-of-thought planning gives large gains on structured visuals and world knowledge, but it gives little benefit or even degrades accuracy on constraint-governed 3D structures. We give a principled account of that disagreement, and we build a controlled benchmark that tests it.
Core Claim
We make two claims, one about each stage of the pipeline. For the planning stage, where a model writes a layout as text, we predict that accuracy and the gain from chain of thought track whether the underlying constraint family is solvable by local consistency checking. In complexity-theory terms, this means the family has "bounded width." It does not track whether the relations are symmetric ("same shelf as") or asymmetric ("left of"), and it does not track the dependency count $K$. For the rendering stage, where the model draws a correct layout, we predict the opposite: complexity class stops mattering, and asymmetry is what hurts, because directional relations must be rendered with the correct orientation.
This split matters for three reasons. It reconciles the conflicting chain-of-thought findings. It explains why rewards that verify each constraint separately should work for easy families and plateau for hard ones: checking each constraint on its own is itself a form of local consistency. And it tells practitioners which prompts should be handed to an exact solver rather than to a longer chain of thought.
Prior Work and the Gap
The closest work is FormalImG. It writes prompts in first-order logic, scales a dependency parameter $K$ from 1 to 10, and verifies flat-lay ("knolling") images symbolically. It finds that text LLMs write correct layouts at $K=10$ with nearly 97% accuracy while rendering collapses. Its prompts, however, are mostly dependency chains, which are tree-shaped and therefore easy under any constraint language. It also never varies the algebraic type of the relations. FormalImG motivates our work: its conclusion that "rendering is the bottleneck" may hold only because its planning problems were easy.
On the theory side, three papers supply the tools we use to choose constraint families with known complexity:
- Constraint Satisfaction, Databases, and Logic surveys the result that tractability follows from algebraic closure properties called polymorphisms, and Grohe's theorem that bounded-treewidth instances are easy.
- Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom classifies symmetric qualitative spatial algebras. It explicitly leaves asymmetric ones such as the directed point algebra outside its method.
- On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems shows that a local-agreement polymorphism (near-unanimity) is necessary for approximating the cost-minimizing version of these problems. This motivates our prediction that local, per-constraint signals cannot guide global repair in hard families.
A line of asymmetric-signature counting results is a constraint on our design rather than a method we use. These include Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP and The Complexity of Holant Problems over Boolean Domain with Non-negative Weights. They show that breaking symmetry complicates the algebra, but they do not show that asymmetry by itself causes hardness. So we treat "asymmetry causes hardness" as a hypothesis to falsify, not a premise.
On the generation side, two systems supply the planning methods we test:
- T2I-R1 writes a text plan and then draws, trained with reinforcement learning from an ensemble of reward models.
- AlphaGRPO splits a prompt into atomic yes/no rubrics and rewards each one separately.
Two further papers are the contradictory evidence we aim to explain. Factuality Matters reports reasoning-trajectory gains of nearly 30% on editing. Thinking in Structures finds that extended deliberation can amplify an incorrect initial hypothesis.
Two diffusion papers inject constraints directly into sampling and are candidate alternatives to text planning:
- Compositional Diffusion-Based Continuous Constraint Solvers sums the denoising directions of per-constraint models.
- Projected Coupled Diffusion projects each sample back onto the feasible set at every denoising step.
Neither paper asks which constraint families their local dynamics can solve.
Research Program
We will build a benchmark we call the Complexity-Stratified Layout Benchmark. It crosses symmetry with tractability using constraint families whose complexity is classically settled. The benchmark has four cells.
| Cell | Constraint family | Complexity | Local consistency decides it? |
|---|---|---|---|
| Asymmetric, tractable | "Left of / right of / aligned with" on horizontal position (the point algebra) | Polynomial | Yes (path consistency) |
| Asymmetric, hard | "A, B, C appear clockwise" around a round table (cyclic ordering) | NP-complete | No |
| Symmetric, tractable | "Same shelf / different shelf" with two shelves (2-coloring) | Polynomial | Yes |
| Symmetric, hard | "Same shelf / different shelf" with three shelves (3-coloring) | NP-complete | No |
The two symmetric cells use identical wording and differ only in the number of shelves. This is the cleanest control we know of for surface form.
Within each cell, we match the number of objects (6 to 10) and the number of constraints $K$. We generate instances with a planted solution, so every prompt is satisfiable, and we keep the solution unique where possible. We also vary the shape of the constraint network, using trees versus dense cyclic graphs. By Grohe's theorem, hard families become easy on tree-shaped networks, so this variation gives a second, independent prediction.
All scenes are flat-lay or top-down so that, following FormalImG, images can be parsed back into positions and checked exactly. A small natural-scene split, judged by a model-as-judge, tests whether the results transfer.
Every system is evaluated at two points. First, the text plan is checked against the constraints before any drawing happens. Second, rendering is scored given an oracle-correct layout. We also report the difference between the planning gain with and without chain of thought, cell by cell. Finally, we probe per-constraint reward: we train an AlphaGRPO-style decomposed reward and compare it with a global satisfiability reward from an exact checker, at matched training steps.
Baselines
The naive reference point is direct generation with no explicit plan, using open models reported in FormalImG (SDXL, Qwen-Image). FormalImG reports that their success rates "plummet toward zero" for $K$ from 7 to 10, and that Gemini-3-Pro-Image stays above 70% only up to $K=6$ in the natural scenario. We will re-run them on our cells with identical prompts and seeds.
The strongest planning competitor is free-text chain of thought followed by rendering, in the style of T2I-R1, run with the same underlying LLM and renderer in every cell. The planning ceiling it must beat is FormalImG's roughly 97% layout accuracy at $K=10$. Our prediction is that this number holds in the tractable cells and on tree-shaped networks, but falls in the hard cyclic cells.
The strongest reward-training competitor is AlphaGRPO's decomposed verifiable reward. AlphaGRPO reports 83.9% overall on TIIF-Bench, which is not our task, so we will retrain it on our training split with the same compute and number of steps as the global-reward variant. No result reported on Lacuna exists for any system on complexity-stratified layout prompts, so all comparisons will be run by us under matched budgets.
The ablation that isolates the key ingredient is an exact-solver planner. A small search-based constraint solver replaces the LLM plan, and the rest of the pipeline is unchanged. If this closes the hard-cell gap at planning while leaving the rendering gap in the asymmetric cells, it confirms that the two stages fail for different reasons.
We count the complexity-class account as "beating" the alternatives if class membership explains substantially more variance in planning accuracy and chain-of-thought gain than $K$, object count, or symmetry do, in a regression across all instances, with both hardness predictions holding (hard families hard, but easy again on trees).
Why not just…?
Why not just use $K$ as the difficulty measure? FormalImG shows that $K$ correlates with failure, but $K$ and difficulty are confounded in chain prompts. Our matched cells hold $K$ fixed while changing complexity class. If accuracy is flat across cells at fixed $K$, our hypothesis is wrong, and we will report that outcome.
Why not just scale the model or think longer? Thinking in Structures finds that the best proprietary model reaches 33.6% on constraint-governed structures against 91.6% for humans, and that longer deliberation sometimes hurts. Our design tests where that happens: we predict longer chains help in bounded-width cells and plateau or degrade in hard cyclic cells. We will sweep chain-of-thought budgets to check this directly.
Why not just always call a constraint solver? This is a real threat to any claim that the generator itself should become complexity-aware, and it may well work. For that reason we include it as a system rather than argue against it. If it solves planning everywhere, the practical conclusion is to route hard prompts to search and invest model capacity in rendering. The diagnostic value of the benchmark remains, because only the stratification tells you which prompts need routing and shows that rendering failures are driven by asymmetry.
Why not just best-of-N sampling with a verifier? Compositional Diffusion-Based Continuous Constraint Solvers reports that rejection sampling becomes exponentially inefficient as problems grow. We will measure the number of samples needed to reach a fixed success rate, per cell, and expect the growth to be much steeper in the hard cells.
Decisive Experiments
The first check tests planning accuracy. On cyclic networks at matched $K$, planning accuracy should drop sharply in the three-shelf cell relative to the two-shelf cell, even though the wording is identical. It should drop in the cyclic-ordering cell relative to the point-algebra cell. On tree-shaped networks, these gaps should disappear. If the gap instead follows symmetry, meaning both asymmetric cells fail and both symmetric cells succeed, the complexity account is refuted and the asymmetry account is supported.
The second check tests the chain-of-thought crossover. The gain from chain of thought should be positive in tractable cells and near zero or negative in hard cyclic cells. This would reconcile Factuality Matters with Thinking in Structures.
The third check tests reward training. Decomposed per-constraint reward should match global reward in tractable cells and fall behind it in hard ones.
The fourth check tests rendering. With oracle layouts, rendering accuracy should be independent of complexity class and lower for asymmetric relations. Each of these four checks can fail independently, and each failure would be informative.
References
- FormalImG: Evaluating Structural Compositional Generalization for T2I Models
- Constraint Satisfaction, Databases, and Logic
- Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom
- On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP
- The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights
- 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
- Thinking in Structures: Evaluating Spatial Intelligence in Constraint-Governed Spaces
- Compositional Diffusion-Based Continuous Constraint Solvers
- Projected Coupled Diffusion for Test-Time Constrained Joint Generation