Multi-Solution Constraint Satisfaction

Multi-solution constraint satisfaction refers to a class of problems defined by a set of constraints where multiple distinct configurations satisfy all constraints simultaneously. Unlike single-solution problems where any valid configuration is unique, multi-solution problems require a reasoning system to explore the space of valid configurations rather than converging to a single attractor. Classic examples include the N-Queens problem (92 solutions for 8-Queens), graph coloring (many valid colorings exist for most graphs), and Sudoku puzzles (multiple valid completions are possible in underconstrained instances).

Multi-solution problems are particularly challenging for deterministic reasoning systems because these systems, when run repeatedly, collapse to the same attractor solution regardless of initialization. A deterministic Recursive Reasoning Model trained on N-Queens will learn to find one valid solution efficiently but will fail to produce diverse solutions when queried multiple times. This is not a training failure — the model is behaving optimally under a single-solution objective — but it limits the model's usefulness in domains where solution diversity matters.

For probabilistic systems like GRAM, multi-solution problems are natural testbeds because the stochastic latent trajectory naturally explores different paths through the solution space. Running GRAM multiple times produces genuinely different trajectories, and with sufficient trajectory sampling, multiple distinct valid solutions can be recovered from a single model. The N-Queens problem in the GRAM paper demonstrates this: GRAM produces both solutions in a single inference run with parallel trajectories, while deterministic HRM and TRM produce the same solution regardless of trajectory initialization.

The challenge for multi-solution problems is evaluation: standard metrics like fraction of problems solved obscure whether a system finds one solution or all solutions. The GRAM paper introduces solution coverage metrics that measure what fraction of all valid solutions a system can find given a time or compute budget. This reveals that inference-time scaling via trajectory sampling provides monotonic improvement in coverage — more trajectories reliably find more solutions — even when depth scaling has plateaued. The tradeoff is that solution counting becomes computationally expensive for problems with exponentially many valid configurations.