用数独测试连续时间生成模型能否处理全局约束的离散问题
Can Continuous-Time Diffusion Models Generate and Solve Globally Constrained Discrete Problems? A Study on Sudoku
- 在连续空间中训练流匹配与得分模型，模拟数独解空间
- 随机采样比确定性方法更有效，得分模型最可靠，DDPM式采样精度最高
- 模型可转为概率求解器，适合研究生成模型的约束满足能力
标准连续时间生成模型能否表示支持集为极度稀疏且全局约束的离散分布？我们以完整数独网格为受控测试基准，将其视为连续松弛空间的子集。沿高斯概率路径训练流匹配与得分模型，并比较确定性（ODE）采样、随机（SDE）采样以及基于相同连续训练的DDPM式离散化方法。无条件生成中，随机采样显著优于确定性流；得分模型在连续方法中最为可靠，而DDPM式祖先采样整体有效性最高。进一步表明，相同模型可重用于引导生成：通过反复在固定提示下采样完成解，直至满足约束，模型即成为概率数独求解器。尽管远不如经典求解器及离散几何感知扩散方法高效，但实验表明经典扩散/流模型能为全局约束组合结构分配非零概率质量，并可通过随机搜索实现约束满足。
原文摘要 · Abstract (English)
Can standard continuous-time generative models represent distributions whose support is an extremely sparse, globally constrained discrete set? We study this question using completed Sudoku grids as a controlled testbed, treating them as a subset of a continuous relaxation space. We train flow-matching and score-based models along a Gaussian probability path and compare deterministic (ODE) sampling, stochastic (SDE) sampling, and DDPM-style discretizations derived from the same continuous-time training. Unconditionally, stochastic sampling substantially outperforms deterministic flows; score-based samplers are the most reliable among continuous-time methods, and DDPM-style ancestral sampling achieves the highest validity overall. We further show that the same models can be repurposed for guided generation: by repeatedly sampling completions under clamped clues and stopping when constraints are satisfied, the model acts as a probabilistic Sudoku solver. Although far less sample-efficient than classical solvers and discrete-geometry-aware diffusion methods, these experiments demonstrate that classic diffusion/flow formulations can assign non-zero probability mass to globally constrained combinatorial structures and can be used for constraint satisfaction via stochastic search.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。