Discrete Flow Matching: Convergence Guarantees Under Minimal Assumptions¶

会议: NeurIPS 2026
arXiv: 2605.08882
OpenReview: https://openreview.net/forum?id=DnD9EjVFG3
领域: 图像生成
关键词: 离散流匹配, 连续时间马尔可夫链, 非渐近收敛界, 全变差距离, 离散生成模型

一句话总结¶

针对有限离散状态空间上的流匹配模型（DFM），本文基于最近邻与均匀随机游走参考过程及离散马尔可夫概率模型（DMPM）时间离散化采样方案，在仅依赖神经网络得分逼近误差的极简假设下，首次推导出早停目标分布的非渐近 KL 散度界以及真实目标分布的全变差（TV）距离收敛上界。

研究背景与动机¶

基于随机过程的生成建模在连续域（如扩散模型与连续流匹配）中已建立起扎实的非渐近理论体系，凭借简洁的回归训练目标与确定性/随机概率流插值，流匹配展现出与经典扩散相当甚至更优的采样效率与经验性能。然而，将连续流匹配拓展到离散状态空间 \(\mathbb{Z}_m^d\)（离散流匹配，Discrete Flow Matching, DFM）时，理论收敛保证却显著滞后。离散流匹配依赖跳跃马尔可夫桥与连续时间马尔可夫链（CTMC）的马尔可夫投影构造概率流，但由于真实转移速率（即离散得分）解析不可计算且生成过程必须借助时间离散化采样，其动力学性质远比连续域复杂。

现有针对离散流匹配的理论分析存在多重严重局限：一方面，已有工作要么依赖均匀化（uniformization）精确无离散化仿真采样，其计算开销在离散词表维度较高时剧烈膨胀；要么在离散化分析中强行引入对待估转移速率或真实得分的严格有界性假设，使得理论假设脱离实际神经网络训练范式。另一方面，先前的步长复杂度分析对词表大小 \(m\) 与特征维度 \(d\) 的依赖次优，且绝大多数仅能给出早停分布的相对熵分析，缺乏直接面向真实数据目标分布 \(\mu_1\) 的显式全变差（Total Variation, TV）距离收敛保证。

面对连续时间转移速率在终止时刻 \(t=1\) 发散、离散得分缺乏扩散模型传递恒等式（transitive identity）等理论困境，本文的核心切入点在于深入挖掘跳跃马尔可夫桥在特定随机游走结构下的代数与分析性质，通过早停截断与得分函数的固有稳定性分析隔离离散化与逼近误差。核心 idea：基于最近邻与均匀随机游走两种离散参考过程，采用 DMPM 分段常数转移核离散化生成动力学，在仅假定经验得分匹配损失有界（逼近误差假设）的极简条件下，严格证明了离散得分的内在有界性与积分熵演化方程，首次建立了早停截断下的非渐近 KL 散度界与真实目标分布下的全变差距离收敛保证，使均匀随机游走的步长复杂度达到对词表大小 \(m\) 无关的 \(\tilde{O}(d^2/\varepsilon^2)\)。

方法详解¶

整体框架¶

离散流匹配的目标是在有限状态空间 \(\mathbb{Z}_m^d = \{0, 1, \dots, m-1\}^d\) 上，从已知先验源分布 \(\mu_0\) 出发，在有限时间步内构造概率流精准模拟目标数据分布 \(\mu_1\)。整个框架分为三个关键阶段：首先选取齐次稳定的基础跳跃 CTMC 生成元 \(q\)（最近邻随机游走 NNRW 或均匀随机游走 URW），借助预定耦合 \(\pi(\mu_0, \mu_1)\) 与条件跳跃马尔可夫桥构造混合插值过程；其次求解该非马尔可夫插值过程的唯一边际保持马尔可夫投影，显式导出其时间非齐次生成元 \(q_t^\mathrm{M}(x,y) = q(x,y) u_t^\mathrm{M}(x,y)\) 并基于可处理的离散得分熵损失与均方误差损失训练参数化神经网络得分；最后基于学得的得分，在时间区间 \([0, 1-\eta]\) 上运行分段常数离散马尔可夫概率模型（DMPM）跳跃动力学进行采样生成。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["源分布与目标分布耦合 (X0, X1) ~ π<br/>状态空间 Z_m^d"] --> B["离散随机插值与马尔可夫投影<br/>定义 NNRW / URW 桥与投影得分 u_t^M"]
    B --> C["参数化离散得分匹配训练<br/>联合离散得分熵损失与二阶回归损失"]
    C --> D["DMPM 时间离散化生成动力学<br/>几何递进网格采样与早停截断 t_K = 1-η"]
    D --> E["生成分布 Law(X_{1-η}^θ*)<br/>输出离散生成样本"]

关键设计¶

1. 离散随机插值过程与其马尔可夫投影：构建保边际跳跃桥动力学

为了在离散环面或超立方体拓扑上架起从 \(\mu_0\) 到 \(\mu_1\) 的概率桥梁，论文首先引入两类核心齐次转移发生器 \(q(x,y)\)。第一类为最近邻随机游走（NNRW），粒子每次只能沿某一坐标轴正向或负向跳跃一步，单步转移速率为 \(1/2\)（自转移对角元为 \(-d\)）；其位移差遵循 Skellam 分布，一维坐标转移概率由修正第一类贝塞尔函数 \(I_b(t)\) 精确给出。第二类为均匀随机游走（URW），粒子以等概率速率 \(1/m\) 随机跳转到汉明距离为 1 的任意相邻状态，其转移核具有完备的全图连通性解析闭式。基于参考生成元 \(q\) 与端点条件跳跃马尔可夫桥测度 \(\mathbb{B}^q(\cdot \mid X_0^\mathrm{I}, X_1^\mathrm{I})\)，构造出的混合插值过程 \(X_t^\mathrm{I}\) 通常是非马尔可夫的。为此，作者证明了定理 1：存在唯一的（依分布意义下）连续时间马尔可夫链 \(X_t^\mathrm{M}\)，其时间非齐次生成元为 \(q_t^\mathrm{M}(x,y) = q(x,y) u_t^\mathrm{M}(x,y)\)（\(x \neq y\)），其边际分布与混合插值过程严格一致（\(\mathbb{P}(X_t^\mathrm{M}=x) = p_t^\mathrm{I}(x)\)）。离散得分函数由桥得分对终点后验的条件期望给出：

\[u_t^\mathrm{M}(x,y) = \mathbb{E}\left[\frac{p_{1|t}(X_1^\mathrm{I} \mid y)}{p_{1|t}(X_1^\mathrm{I} \mid x)} \middle| X_t^\mathrm{I} = x\right]\]

2. 极简假设下的联合训练损失：规避离散得分的真实解析难解性

由于目标分布不可知且公式中的边际分母 \(p_t^\mathrm{I}(x)\) 涉及高维全状态空间求和，直接计算真实得分 \(u_t^\mathrm{M}\) 在实践中不可行。为了在最小化假设下建立非渐近保证，论文构造了由两部分组成的联合优化目标 \(\mathcal{L}(\theta) = \mathcal{L}_\mathrm{e}(\theta) + \mathcal{L}_2(\theta)\)。其中 \(\mathcal{L}_\mathrm{e}\) 为离散得分熵损失（利用凸函数 \(\varphi(a) = a \log a - a + 1\)），\(\mathcal{L}_2\) 为离散化的具体得分匹配二阶差分损失：

\[\mathcal{L}(\theta) = \sum_{k=0}^{K-1} h_{k+1} \mathbb{E}\left[\sum_{\sigma \in \mathcal{M}} \left\{ q_{t_k}^{\mathrm{M},\theta} \varphi\left(\frac{q_{t_k}^\mathrm{M}}{q_{t_k}^{\mathrm{M},\theta}}\right) + \left(q_{t_k}^{\mathrm{M},\theta} - q_{t_k}^\mathrm{M}\right)^2 \right\}(X_{t_k}^\mathrm{I}, \sigma(X_{t_k}^\mathrm{I}))\right]\]

借助条件期望性质，该损失函数在实际训练中可完全转化为关于已知条件桥转移核 \(q_t^{(X_1^\mathrm{I})}\) 的闭式样本估计目标 \(\tilde{\mathcal{L}}(\theta)\)。最关键的理论突破在于假设 M 1：仅要求训练后的最优参数满足 \(\mathcal{L}(\theta^\star) \leq \tilde{\varepsilon}^2\)（平均逼近误差），彻底摒弃了以往理论文献中对估计得分或真实转移速率强加的人为全局有界性、Lipschitz 平滑性等不切实际的前提。

3. 得分内禀稳定性与早停 DMPM 离散化：消解终端奇点与离散化误差

在生成阶段，模型从 \(X_0^{\theta^\star} \sim \mu_0\) 开始，在离散时间网格 \(t_k = 1 - (1+h)^{-k}\) 上采用 DMPM 方案运行分段常数跳跃采样。然而，当时间逼近终点 \(t \to 1\) 时，真实离散得分 \(u_t^\mathrm{M}\) 会因条件概率集中而发生奇点发散。论文创新性地证明了引理 1（得分内禀稳定性）：在任意早停截断区间 \([0, 1-\eta]\) 上，无论真实数据分布形态如何，跳跃桥得分满足由拓扑性质内生保证的一致双边有界性：

\[\frac{1-t}{m} \lesssim u_t^\mathrm{M}(x, \sigma(x)) \lesssim \frac{m}{1-t}, \quad \forall t \in [0, 1-\eta]\]

作者利用柯尔莫哥洛夫方程为离散得分及其熵函数建立了伊藤跳跃演化方程（Lemma 2 与 Lemma 3）。通过引入形如 \(t_k = 1 - (1+h)^{-k}\) 的几何自适应递进步长网格（满足步长 \(h_{k+1} = h(1-t_{k+1})\)），网格的自适应加密机制恰好严密抵消了由 \(1/(1-t)\) 带来的奇点漂移，最终将时间离散化误差 \(E_\mathrm{disc}\) 严格控制在 \(\tilde{O}((\lambda(m))^2 d^2 m^2 h)\) 内。

损失函数 / 训练策略¶

实际训练采纳无需后验边际的数值可处理损失函数 \(\tilde{\mathcal{L}}(\theta)\)：

\[\tilde{\mathcal{L}}(\theta) = \sum_{k=0}^{K-1} h_{k+1} \mathbb{E}\left[\sum_{\sigma \in \mathcal{M}} \left( - q_{t_k}^{(X_1^\mathrm{I})} \log q_{t_k}^{\mathrm{M},\theta} + q_{t_k}^{\mathrm{M},\theta} + \left(q_{t_k}^{\mathrm{M},\theta} - q_{t_k}^{(X_1^\mathrm{I})}\right)^2 \right)(X_{t_k}^\mathrm{I}, \sigma(X_{t_k}^\mathrm{I}))\right]\]

在采样离散化设计上，设置早停截断点 \(t_K = 1 - \eta\)（\(\eta \in (0,1)\)）。网格步长缩放参数 \(h\) 与早停参数 \(\eta\) 经过联合权衡：针对误差精度目标 \(\varepsilon\)，设置 \(\eta = \varepsilon / (C(m)d)\)，\(h = \varepsilon^2 / ((\lambda(m))^2 d^2 m^2 \log(m \eta^{-1}) \log(\eta^{-1}))\)，从而在避免发散的前提下实现了整体迭代复杂度的最优化。

实验关键数据¶

主实验（收敛复杂度与理论保证对比）¶

作为纯数学理论突破工作，论文的核心成果为与现有离散流匹配及离散扩散采样器收敛上界的严格理论对照。下表系统对比了达到 \(O(\varepsilon)\) 真实全变差（TV）距离或 \(O(\varepsilon^2)\) 相对熵（KL）精度所需的总迭代步数复杂度 \(K\) 与核心理论假设：

方法 / 理论框架	离散化方案	得分假设条件	保证测度	目标分布类型	迭代步数复杂度 \(K\)
(Wan et al., 2026) Thm 1	Tau-leaping / Euler	强条件逼近误差 (Eq. 16)	TV 距离	早停分布	\(\tilde{O}(d^2 m / \varepsilon^2)\)
(Wan et al., 2026) Thm 3	Time-corrected Sampler	强条件逼近误差 (Eq. 16)	TV 距离	早停分布	\(\tilde{O}(d^2 m / \varepsilon^2)\)
(Wan et al., 2026) Thm 4	Location-corrected	强条件逼近误差 (Eq. 16)	TV 距离	早停分布	\(\tilde{O}(d^2 m / \varepsilon^2)\) (最坏情况)
本文 (Theorem 2 - URW)	DMPM 采样	极简逼近误差 (M 1)	KL 散度	早停分布	\(\tilde{\mathbf{O}}(\mathbf{d^2 / \varepsilon^2})\)
本文 (Corollary 1 - URW)	DMPM 采样	极简逼近误差 (M 1)	TV 距离	真实目标分布 \(\mu_1\)	\(\tilde{\mathbf{O}}(\mathbf{d^2 / \varepsilon^2})\)
本文 (Corollary 1 - NNRW)	DMPM 采样	极简逼近误差 (M 1)	TV 距离	真实目标分布 \(\mu_1\)	\(\tilde{\mathbf{O}}(\mathbf{d^2 m^2 / \varepsilon^2})\)

消融实验（不同动力学过程与误差成分分解）¶

为了剖析不同参考跳跃过程（URW vs. NNRW）的内在几何机制，论文针对误差界中的关键常数项与误差构成进行了理论解构：

| 参考马尔可夫动力学 | 跳跃速率 \(\lambda(m)\) | 跳跃算子基数 \(|\mathcal{M}|\) | 早停截断因子 \(C(m)\) | 早停误差界 \(\|\mu_{1-\eta} - \mu_1\|_\mathrm{TV}\) | 词表规模 \(m\) 复杂度伸缩 | |---|---|---|---|---|---| | 均匀随机游走 (URW) | \(1/m\) | \(d(m-1)\) | \(1\) | \(\lesssim d \eta\) | 步数复杂度与 \(m\) 无关 (\(O(1)\)) | | 最近邻随机游走 (NNRW) | \(1/2\) | \(2d\) | \(m\) | \(\lesssim d m \eta\) | 步数随 \(m\) 二次放缩 (\(O(m^2)\)) | | 纯逼近误差项 \(E_\mathrm{approx}\) | - | - | - | - | \(O(m^2 \eta^{-2} \tilde{\varepsilon}(\sqrt{|\mathcal{M}|} + \tilde{\varepsilon}))\) | | 纯离散化误差项 \(E_\mathrm{disc}\) | - | - | - | - | \(O((\lambda(m))^2 d^2 m^2 h \log(\eta^{-1})\log(m\eta^{-1}))\) |

关键发现¶

均匀随机游走（URW）由于其完全图连通拓扑，单步跳跃即可在全词表范围重分配概率质量，其早停误差界与状态空间基数 \(m\) 完全解耦（\(C(m)=1\)），使得其在 TV 距离下的步数复杂度缩减至 \(\tilde{O}(d^2/\varepsilon^2)\)，彻底打破了以往离散模型随词表线性增长的理论瓶颈。
最近邻随机游走（NNRW）受限于环面近邻晶格结构，概率质量必须经过 \(m\) 个中间状态缓慢传导，导致其早停误差具有线性尺度因子 \(C(m)=m\)，反映出局部转移拓扑在全局生成任务中的理论收敛劣势。
离散流匹配因缺乏扩散模型的传递性恒等式（即 \(u_t(x,z) \neq u_t(x,y) u_t(y,z)\)），其离散化误差演化分析必须借助构造微分算子 \(\mathcal{A}_t^\mathrm{M}, \mathcal{B}_r^\mathrm{M}, \mathcal{C}_r^\mathrm{M}\)，技术难度远超离散扩散模型。

亮点与洞察¶

技术亮点：巧妙运用离散跳跃过程的 Girsanov 定理与伊藤公式，首次为离散流匹配的得分函数及其熵函数推导出显式演化微分方程，构建了纯解析的离散误差控制工具箱。
理论突破的"啊哈"时刻：作者揭示了无需强加网络参数假设的核心原因在于——通过将估计得分的相对熵利用凸对偶与 Jensen 不等式进行代数分解，残差项被跳跃桥的内禀有界性（利用 Amos 不等式严格证明的修正贝塞尔函数比值有界性）完美吸收，使统计逼近与离散化时间步完全解耦。
可复用的迁移价值：针对奇异时间端点设计的对数递进自适应网格 \(t_k = 1 - (1+h)^{-k}\) 及其与早停截断参数的平衡技巧，可广泛复用到其他带奇点的连续时间离散状态控制生成模型（如离散生成流、基于图的非平衡动力学等）。

局限与展望¶

作者承认的局限：目前的逼近误差假设 M 1 仅假定存在某种参数 \(\theta^\star\) 使得经验得分损失小于 \(\tilde{\varepsilon}^2\)，属于预言机（oracle-type）性质的假设，并未对特定深度神经网络架构（如 Transformer、离散 MLP）的逼近能力和样本复杂度展开统计学习理论刻画。
适用场景与条件局限：所有的收敛保证均建立在对称的随机游走参考过程（URW 或 NNRW）上，对工业界常用的大规模预训练掩码语言建模（Masked Discrete Flow）或非对称转移路径未做完整闭式覆盖。
未来改进方向：结合神经正切核（NTK）或统计学习界，进一步探索在有限训练样本和具体网络架构下，从经验样本到真实连续时间测度的端到端全流程泛化误差分析。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立离散流匹配在极简假设下的非渐近收敛保证，突破了以往研究的强假设与早停限制。
实验充分度: ⭐⭐⭐⭐☆ 作为纯理论文章，数学推导完备闭合，附录给出了超过 20 页的细致测度论与随机过程证明，理论对比极为详尽。
写作质量: ⭐⭐⭐⭐⭐ 符号系统规范清晰，动机阐述切中要害，从桥测度到马尔可夫投影的数学叙述层层递进。
价值: ⭐⭐⭐⭐⭐ 为离散生成模型（尤其是语言、符号与分子化学领域的离散流模型）奠定了坚实的理论基石。