DiBS: 扩散信息引导的支路选择

# DiBS：扩散引导的分支选择
来源：https://arxiv.org/html/2606.06518
Bo Liu1, Yuan Xie2, Yuan Gao2, Xiaolong Luo3, Peng Ye4,5, Tao Chen6, Fujun Han2

###### 摘要

数独是一种代表性的约束满足问题，需要严格的离散约束下的全局结构推理。现有的数独解法工作主要集中于两种主流方法，即传统启发式方法和深度学习求解器。然而，它们存在互补的局限性：基于学习的求解器缺乏硬正确性保证，而完整的符号求解器仍然可能陷入长尾搜索。为了解决这些不足，我们提出了一种新颖的扩散模型引导方法，称为DiBS，用于分支选择搜索过程。具体地，DiBS保持符号求解器的完整性，并使用扩散模型作为分支顺序的引导。核心思想是在当前部分赋值和轻量级一致性信号下对候选值进行排序。此外，我们提供了深入的理论证明，以揭示其工作原理及有效性。在具有挑战性的Royle 17线索数独基准上的实验表明，相对于强大的启发式基线，我们的DiBS显著降低了搜索成本，尤其是在节点数、回溯次数和长尾百分位数方面。此外，这些结果证实了学习到的全局引导在分支顺序错误代价最高的困难实例上是有效的。所有代码可在https://github.com/shanxierdan/DiBS获取。

## 引言

数独是一个约束满足问题（CSP），经典求解器依赖于深度优先回溯、约束传播（CP）和最小剩余值（MRV）等启发式方法。这些求解器是完备的，即如果存在解，它们就能找到。然而，在困难实例上，求解器的性能由两个相互作用的因素决定：约束传播的强度以及搜索树的结构。早期的一些错误分支决策可能导致巨大的失败子树，这些子树只有在搜索深处才揭示矛盾，从而产生长尾运行时间 (Mackworth1977 (https://arxiv.org/html/2606.06518#bib.bib1); Haralick and Elliott1980 (https://arxiv.org/html/2606.06518#bib.bib2); Régin1994 (https://arxiv.org/html/2606.06518#bib.bib3); Simonis2005 (https://arxiv.org/html/2606.06518#bib.bib4))。

参见图注图1：三种不同求解器范式的比较。我们可以看到，与传统的启发式求解器和其他深度学习求解器相比，我们的DiBS是一种新的范式。最近，循环关系网络和可微求解器等学习模型已被探索用于捕获数独的全局结构，但它们采用端到端生成，绕过了经典求解器的精确搜索机制 (Palmet al.2018 (https://arxiv.org/html/2606.06518#bib.bib6); Wanget al.2019 (https://arxiv.org/html/2606.06518#bib.bib7))。这引发了一个关键问题：生成模型能否引导精确搜索以提高效率，同时不牺牲完备性？离散扩散模型 (Hoet al.2020 (https://arxiv.org/html/2606.06518#bib.bib12); Austinet al.2021 (https://arxiv.org/html/2606.06518#bib.bib13); Weilbachet al.2023 (https://arxiv.org/html/2606.06518#bib.bib14)) 提供了一种有前途的工具，因为它们编码了候选赋值的全局兼容性，即使仅靠局部传播无法暴露这些兼容性。然而，现有的基于扩散的组合求解器专注于完整解生成，而不是在分支选择过程中提供引导 (Sun and Yang2023 (https://arxiv.org/html/2606.06518#bib.bib15); Yeet al.2025 (https://arxiv.org/html/2606.06518#bib.bib16))。

与这些面向生成的方法不同，我们认为学习模型在精确求解器中的主要价值不在于直接产生解，而在于在完备搜索过程中具有高影响力的决策点上引导分支顺序。直觉是，如果一个学习模型能评估哪个候选值更有可能导致解，那么先尝试那个分支可以避免探索错误选择可能带来的巨大失败子树。这使得学习引导在困难实例上最具影响力，在这些实例中，错误分支可能在出现矛盾前许多步内保持局部一致，从而产生不成比例的高搜索成本——这正是经典启发式方法最困难的长尾区域。

在本文中，我们通过以下方式解决这两个挑战：使用扩散模型不是为了生成解，而是为了在完整的CP+MRV求解器中的高影响力决策点上引导分支顺序。与学习分支 (Khalilet al.2016 (https://arxiv.org/html/2606.06518#bib.bib9); Gasseet al.2019 (https://arxiv.org/html/2606.06518#bib.bib10)) 或基于模型的规划 (Schrittwieseret al.2020 (https://arxiv.org/html/2606.06518#bib.bib17); Janneret al.2022 (https://arxiv.org/html/2606.06518#bib.bib18)) 不同，我们仅对候选值进行重新排序，而不进行剪枝或学习完整策略，从而保持完备性。关键洞察是，如果 \(p_s\) 是在状态 \(s\) 下首先选择引导解的分支的概率，而 \(T(s_w)\) 是探索错误子树的成本，那么更好的引导带来的节省与 \(\Delta p_s \cdot T(s_w)\) 成正比——使得分支顺序在错误子树代价高昂的困难实例上最具影响力。基于这一原则，我们提出了DiBS（扩散引导的分支选择）。DiBS使用离散扩散模型在当前部分赋值下对候选值进行评分，并结合一个轻量级的同伴一致性项，仅在二元MRV状态时调用模型以限制开销。我们提供了一个理论框架，证明了为什么更好的分支顺序能减少搜索成本，并展示了DiBS如何逼近最优策略。在Royle 17线索基准上的实验表明，搜索成本显著降低，尤其是在长尾百分位数方面。

总之，我们的贡献可总结如下：

- •**新颖范式**。DiBS是首个将扩散模型应用于完备CSP算法中分支选择的方法，在搜索成本上优于启发式基线。我们进一步在布尔可满足性上证明了其通用性。
- •**理论框架**。我们形式化了一个概率分支顺序框架，证明了更好的顺序能节省与错误子树成本成比例的开销，并刻画了DiBS所逼近的最优策略。
- •**全面实验**。在Royle 17线索基准和3-SAT上的广泛评估验证了DiBS，消融研究考察了评分组件、调用策略、谜题难度和去噪行为。

## 相关工作

### 从生成式建模到基于扩散的结构知识

生成式建模已从VAE和GAN (Kingma and Welling2013 (https://arxiv.org/html/2606.06518#bib.bib19); Goodfellowet al.2014 (https://arxiv.org/html/2606.06518#bib.bib20)) 经由Transformer (Vaswaniet al.2017 (https://arxiv.org/html/2606.06518#bib.bib21)) 发展到扩散模型，后者已成为学习高维结构的主要范式。从DDPM开始，后续变体如DDIM、基于分数的SDE、潜在扩散和DiT (Hoet al.2020 (https://arxiv.org/html/2606.06518#bib.bib12); Songet al.2020 (https://arxiv.org/html/2606.06518#bib.bib22),2021 (https://arxiv.org/html/2606.06518#bib.bib23); Rombachet al.2022 (https://arxiv.org/html/2606.06518#bib.bib25); Peebles and Xie2023 (https://arxiv.org/html/2606.06518#bib.bib26)) 将扩散确立为条件生成和可控推理的通用框架。除了图像合成，生成式模型越来越多地支持规划和决策：世界模型学习策略学习的潜在动力学 (Ha and Schmidhuber2018 (https://arxiv.org/html/2606.06518#bib.bib28); Hafneret al.2023 (https://arxiv.org/html/2606.06518#bib.bib29))，基于扩散的规划将去噪重新视为轨迹优化 (Janneret al.2022 (https://arxiv.org/html/2606.06518#bib.bib18))，视觉-语言-动作模型捕获与动作相关的规律性 (Bruce and others2024 (https://arxiv.org/html/2606.06518#bib.bib30); Brohan and others2023 (https://arxiv.org/html/2606.06518#bib.bib31))。这些工作激发了一个关键视角：生成式模型的价值可能在于它为另一个算法系统提供的结构化先验知识，而不仅仅在于其样本本身。

### 用于数独、推理和规划的生成式模型

离散扩散模型如D3PM (Austinet al.2021 (https://arxiv.org/html/2606.06518#bib.bib13)) 以及连续时间或掩码变体 (Campbellet al.2022 (https://arxiv.org/html/2606.06518#bib.bib24); Kimet al.2025 (https://arxiv.org/html/2606.06518#bib.bib34); Garget al.2025 (https://arxiv.org/html/2606.06518#bib.bib35)) 将扩散扩展到分类状态空间，这对于数独尤其相关，因为其状态是离散的、全局约束的且部分观察的。几项工作将生成式模型应用于类似数独的推理：GSDM编码稀疏变量交互以进行条件推理 (Weilbachet al.2023 (https://arxiv.org/html/2606.06518#bib.bib14))，Beyond Autoregression报告了使用离散扩散进行推理和规划的强大结果 (Yeet al.2025 (https://arxiv.org/html/2606.06518#bib.bib16))，自适应token顺序研究明确评估了数独推理 (Kimet al.2025 (https://arxiv.org/html/2606.06518#bib.bib34); Wewer and others2025 (https://arxiv.org/html/2606.06518#bib.bib33))。尽管取得了这些进展，大多数方法将数独视为生成问题：模型直接产生完整解。我们的方法有根本不同——我们使用扩散模型作为条件先验，在完备符号求解器内部对候选值进行排序，引导精确推理而不是绕过它。

### 约束满足、精确求解与学习搜索引导

数独是一个经典的CSP，其精确求解方法植根于约束规划。一致性、传播和搜索控制的基础概念 (Mackworth1977 (https://arxiv.org/html/2606.06518#bib.bib1); Haralick and Elliott1980 (https://arxiv.org/html/2606.06518#bib.bib2); Freuder1982 (https://arxiv.org/html/2606.06518#bib.bib36)) 通过弧一致性和AllDifferent过滤得到加强 (Bessiere1994 (https://arxiv.org/html/2606.06518#bib.bib38); Régin1994 (https://arxiv.org/html/2606.06518#bib.bib3))，现在已成为CSP教材的标准内容 (Apt2003 (https://arxiv.org/html/2606.06518#bib.bib40); Dechter2003 (https://arxiv.org/html/2606.06518#bib.bib41); Rossiet al.2006 (https://arxiv.org/html/2606.06518#bib.bib42); Russell and Norvig2010 (https://arxiv.org/html/2606.06518#bib.bib43))。CSP技术广泛应用于调度、验证和配置 (Bartáket al.2010 (https://arxiv.org/html/2606.06518#bib.bib45); Gotlieb2012 (https://arxiv.org/html/2606.06518#bib.bib47); Benavideset al.2010 (https://arxiv.org/html/2606.06518#bib.bib48))，因此保留完备性同时提高搜索效率的方法具有广泛的适用性。对于学习搜索引导，循环关系网络和可微可满足性层捕获数独的全局约束 (Palmet al.2018 (https://arxiv.org/html/2606.06518#bib.bib6); Wanget al.2019 (https://arxiv.org/html/2606.06518#bib.bib7))，但其目标在于直接解预测而非改进完备搜索。分支定界的学习分支策略 (Khalilet al.2016 (https://arxiv.org/html/2606.06518#bib.bib9); Gasseet al.2019 (https://arxiv.org/html/2606.06518#bib.bib10); Scavuzzoet al.2022 (https://arxiv.org/html/2606.06518#bib.bib44)) 表明，学习模型可以减少搜索工作而不替换符号主干。DiBS遵循这一理念，但机制不同：它在CP式搜索的高影响力分支状态使用扩散模型进行值顺序，桥接了生成式建模和精确CSP求解。

## 预备知识

### 数独与约束满足问题

我们将数独视为约束满足问题（CSP）的一个特例。一个CSP由三元组指定

\[\mathcal{P} = (V, \mathcal{D}, \mathcal{C}),\]

其中 \(V\) 是有限的变量集合，\(\mathcal{D} = \{D_v\}_{v \in V}\) 为每个变量 \(v\) 分配一个有限域 \(D_v\)，\(\mathcal{C}\) 是一组关于变量子集的约束。

在标准的 \(9 \times 9\) 数独中，我们取 \(V = \{1, \dots, 81\}\)，每个单元格一个变量。每个变量 \(v \in V\) 取值于 \(\{1, \dots, 9\}\)，因此初始时 \(D_v \subseteq \{1, \dots, 9\}\)，给定的线索编码为单元素域。我们用部分赋值表示部分网格：

\[x: V \rightarrow \{0,1,\dots,9\},\]

其中 \(x(v)=0\) 表示单元格 \(v\) 未赋值，\(x(v) \in \{1,\dots,9\}\) 是已赋值的数字。

数独约束要求每行、每列以及每个 \(3 \times 3\) 块中的所有数字互异。为方便，我们使用两两不等约束。令 \(N(v) \subseteq V\) 表示 \(v\) 的邻居集合，即所有与 \(v\) 共享行、列或块的变量（不包括 \(v\) 自身）。令

\[A(x) = \{v \in V: x(v) \neq 0\}\]

表示在（部分）赋值 \(x\) 下已赋值的变量集合。那么 \(x\) 的可行性意味着没有两个已赋值的相邻单元格共享相同的数字：

\[x(u) \neq x(v) \quad \forall\, v \in A(x), \; \forall\, u \in N(v) \cap A(x).\]

一个完整解是满足上述约束且 \(A(x^\star) = V\) 的赋值 \(x^\star\)。

### 用于数独推理的离散扩散

离散扩散模型 (Yeet al.2025 (https://arxiv.org/html/2606.06518#bib.bib16)) 将完整的数独解表示为 token 序列 \(x_0 \in \{1,\dots,9\}^{81}\)，并通过在时间步 \(t \in \{1,\dots,T\}\) 上的吸收态噪声过程构建损坏版本 \(x_t\)。模型学习逆向去噪分布 \(p_\theta(x_{t-1} \mid x_t)\)，通过最小化关于损坏 token 的加权交叉熵损失：

\[\mathcal{L}_{\mathrm{DM}} = \mathbb{E}_{q(x_0)} \sum_{n=1}^{N} \sum_{t=1}^{T} w(t) \, \mathbb{E}_{q(x_t \mid x_0)} \, u(x_0, x_t, n; \theta), \tag{1}\]

其中 \(N\) 是序列长度，\(w(t)\) 是时间步权重，\(u(x_0, x_t, n; \theta) = -\mathbf{1}[x_{t,n} \neq x_{0,n}] \, \mathbf{e}(x_{0,n})^\top \log f_\theta(x_t)_n\) 是 token 级交叉熵，\(\mathbf{e}(\cdot)\) 表示独热编码。这个目标训练模型从部分观察的全局上下文中预测缺失的数字，这适合数独，因为单元格的有效性依赖于长程的行、列和块交互。

### CP 与 MRV

标准的完备数独求解器使用约束传播（CP）、深度优先回溯和最小剩余值（MRV）(Freuder1982 (https://arxiv.org/html/2606.06518#bib.bib36))。CP 维护候选域 \(\{D_v\}_{v \in V}\)，并在每次赋值后移除不一致的值。如果任何域变空，求解器立即回溯。当仅靠传播无法完成谜题时，MRV 选择具有最小域的变量：

\[v^\star \in \arg\min_{v: x(v)=0} |D_v|. \tag{2}\]

这遵循了“优先失败”原则。