LatticeBridge：稀有事件序列推断实现忠实结构化序列生成

# 稀有事件序列推理实现忠实结构化序列合成
代码与基准文件：https://github.com/farukalpay/latticebridge
来源：https://arxiv.org/html/2606.11203
Bugra Kilictas  计算机工程系，巴赫塞希尔大学 bugra\.kilictas@bahcesehir\.edu\.tr

\(2026年4月\)

###### 摘要

结构化序列生成通常要求模型在单个输出中满足多个源自输入的约束。标准解码方法可能给流畅的延续分配高概率，而对同时实现所有必需锚点的延续分配低概率。我们在此框架下将其视为稀有事件序列推理问题。*LatticeBridge* 结合了一个紧凑的前缀语言模型、实例编译的表面自动机以及一个扭曲序贯蒙特卡洛 (SMC) 解码器，该解码器包含重采样、多层次分裂以及一个源自实例提供短语的源支持提议项。约束表示从每个输入实例编译而来，不依赖人工策划的词法类别。在涵盖 CommonGen、E2E NLG 和 WikiBio 的 2,610 个可达到验证任务上，粒子解码器在精确锚点满足度和平均锚点覆盖率上，均优于在共享提议模型下的贪婪、束过滤和最佳-of-k 祖传基线。由于仅满足精确锚点并不能排除不支持的属性替换，评估同时报告了必需锚点覆盖率、源覆盖率、源入侵诊断、重叠度、运行时间和粒子统计量。该基准在固定提议模型下刻画了忠实度–重叠度–延迟边界。

## 1. 引言

自回归模型提供了强大的局部延续模型，但结构化生成常常需要满足局部似然度难以充分表示的合取约束。例如，在数据到文本生成中，输出可能需要实现多个概念或属性值，同时保持可读性。高似然度的延续可能仅满足这些锚点的子集，而硬约束解码器在满足锚点时可能产生不稳定的搜索行为。我们将这种不匹配视为一个分布问题：即使单个锚点是常见的，在基模型下完全满足锚点的延续集也可能具有低概率。

因此，我们将结构化解码形式化为在序列空间上对稀有接受事件进行推理的问题。序贯蒙特卡洛方法适用于这种形式化，因为它们维护了一个带权重的不完整假设群体，并提供了关于权重退化与重采样的显式诊断。近期工作已将扭曲 SMC 与语言模型中的推理联系起来（Zhao 等人，2024 (https://arxiv.org/html/2606.11203#bib.bib27)；Wu 等人，2024 (https://arxiv.org/html/2606.11203#bib.bib26)）；2025–2026 年的相关工作进一步研究了学习型扭曲以及用于约束生成和模型聚合的 SMC 风格解码（Kim 等人，2025 (https://arxiv.org/html/2606.11203#bib.bib12)；Chan 等人，2026 (https://arxiv.org/html/2606.11203#bib.bib3)）。本研究分离了一个紧凑的条件提议模型、从每个输入实例编译的表面自动机，以及一个带有可直接观测控制信号的粒子解码器。

该实现将数据适配、约束编译、提议建模和评估分开。这种分离防止了基准特定的词汇规则在不经意间进入解码算法。我们采用以下设计约束：

- •约束必须*由实例驱动*，从源样本中提取，而非来自人工策划的主题词典。
- •库层必须在不同任务间可复用，同时数据集适配器保持精简和明确。
- •异常情况必须记录在日志指标中，而非隐藏在不报告的词汇异常里。

LatticeBridge 将每个结构化输入序列化为前缀，训练一个紧凑的前缀语言模型，将锚点短语编译为表面自动机，并运行一个扭曲 SMC 桥接器，其增量奖励取决于向接受自动机状态前进的进度。解码器还使用一个源自源短语的轻量级源支持提议因子，这在不引入数据集特定控制规则的情况下提高了精确值的实现能力。实验在共享提议模型下评估覆盖率、源覆盖率、重叠度、运行时间、有效样本量和接受质量，以便独立于模型规模检验推理层。

## 2. 贡献

本文做出了五项具体贡献。

1. 1. 将结构化序列合成形式化为一个顺序稀有事件推理问题，并使用由实例编译的表面自动机定义的到接受状态的距离势能。
2. 2. 引入一个紧凑的前缀语言模型，加上一个支持感知的扭曲 SMC 桥接器，将重采样、有效样本量和接受质量作为一等诊断指标公开。
3. 3. 提出针对 CommonGen、E2E NLG 和 WikiBio 的基准构建方法，仅使用输入派生的短语，并将模式处理保持在精简的数据集适配器中。
4. 4. 报告了多数据集验证结果，与贪婪、束过滤和最佳-of-k 祖传基线进行比较，同时包含标准误差、运行时间测量、粒子系统诊断、源覆盖率以及针对不支持值替换的源入侵诊断。
5. 5. 在 https://github.com/farukalpay/latticebridge 发布代码和基准文件，包括论文源文件、汇总表、生成的图表和诊断工件。

## 3. 问题形式化

设 \(x\) 为结构化输入，例如一组概念或属性-值对，并设 \(y_{1:T}\) 为目标表面序列。条件语言模型 \(p_\theta(y_{1:T} \mid x)\) 定义了基本合成分布。给定一组基于输入的锚点

\[
\mathcal{C}(x) = \{c_1, \dots, c_M\},
\]

其中每个 \(c_m\) 是从源实例中提取的表面短语。目标并非简单地最大化模型似然度，而是合成一个序列，该序列在 \(p_\theta\) 下既合理又对锚点忠实。

我们通过一个接受指示器来编码满足度：

\[
A(y_{1:T}; \mathcal{C}) = \mathbf{1}\{ \forall m, \; c_m \text{ appears in } y_{1:T} \}.
\]

那么精确的条件目标将是

\[
\pi_T(y_{1:T} \mid x, \mathcal{C}) \propto p_\theta(y_{1:T} \mid x) \, A(y_{1:T}; \mathcal{C}),
\]

但当 \(A=1\) 罕见时，直接从该分布采样通常是棘手的。

为了获得顺序桥接器，我们在生成前缀 \(y_{1:t}\) 后引入一个自动机状态 \(s_t\)。该自动机跟踪每个锚点短语已被实现了多少。用 \(d(s_t) \ge 0\) 表示到完全接受状态的剩余距离。然后我们定义一个松弛的序列目标：

\[
\gamma_T(y_{1:T}) = p_\theta(y_{1:T} \mid x) \exp\{\lambda \Phi_T(y_{1:T})\}, \quad \Phi_T(y_{1:T}) = -d(s_T),
\]

其中 \(\lambda > 0\) 控制偏向精确接受的程度。当 \(\lambda \to \infty\) 且存在接受轨迹时，分布集中于接受轨迹。

计算问题在于如何在有限的粒子预算下近似这个桥接器，同时保持约束表示与任务无关。我们一次性编译表面约束，然后在每个生成步骤运行一个扭曲粒子系统，奖励向接受状态的进展。

## 4. 无隐藏启发式的约束编译

### 4.1. 实例派生锚点

锚点提取仅在模式特定意义上因数据集而异，因为每个数据集暴露不同的结构化输入。CommonGen 提供源概念，E2E 提供属性值，WikiBio 提供标题和信息框字段值。提取后，推理层只接收表面短语和自动机状态。没有全局主题词典、领域清单或手动策划的属性图进入解码器。

设 \(\mathcal{P}(x)\) 为数据集适配器为源实例 \(x\) 暴露的候选短语集。在基准构建中，我们首先仅保留那些在同一实例的至少一个参考表面中出现的短语。这个可达到性标准防止了验证拆分中出现不可能精确匹配的标签，同时保持约束集为实例特定。解码器本身不使用参考。

在可达到的候选中，LatticeBridge 根据经验源信息分数（而非适配器顺序）选择最多 \(K\) 个锚点。对于评估子集 \(\mathcal{D}\)，定义源端文档频率

\[
\widehat{\mathrm{df}}(c) = \sum_{x' \in \mathcal{D}} \mathbf{1}\{c \in \mathcal{P}(x')\}, \quad I(c) = \log \frac{|\mathcal{D}|+1}{\widehat{\mathrm{df}}(c)+1}.
\]

每个示例使用 \(K\) 个得分最高的可达到短语。这种排序有利于在基准子集中具有经验特异性的锚点，并消除了对模式字段顺序的隐藏依赖。

### 4.2. 表面自动机

分词粒度可能使短语跟踪依赖于分段方式。一个词元级别的自动机可能在分词器将有用子串打包到单个词元中时失败。因此，LatticeBridge 使用构建在分词器词元所发射的字符串片段之上的表面自动机。对于每个短语 \(c_m\)，我们构建一个 KMP 风格的自动机，其状态为 \(0, \dots, |c_m|\)，跟踪当前匹配的字符前缀。所有此类自动机的乘积状态定义了全局约束格。这种设计补充了近期也把分词不匹配视为一等系统问题的基于自动机的约束解码工作（Koo 等人，2024 (https://arxiv.org/html/2606.11203#bib.bib13)）。

这种表示带来了三个操作性质：

1. 通过 \(d(s_t)\) 明确表示向接受的进展。
2. 约束逻辑在不同数据集间保持可复用。
3. 短语跟踪不再依赖于特定的 BPE 分段偶然性。

## 5. 扭曲序贯蒙特卡洛桥接器

### 5.1. 序列目标

设 \(y_t\) 为步骤 \(t\) 选择的词元，基模型定义一步条件分布 \(p_\theta(y_t \mid y_{<t}, x)\)。定义进展信号

\[
\Delta_t = d(s_{t-1}) - d(s_t),
\]

当新词元使前缀接近接受时该信号为正。桥接器使用的序列势能为

\[
G_t(y_t, s_{t-1}, s_t) = \exp\{\lambda \Delta_t\}.
\]

未归一化的路径密度变为

\[
\gamma_t(y_{1:t}) = p_\theta(y_{1:t} \mid x) \prod_{\tau=1}^t G_\tau.
\]

### 5.2. 扭曲提议

直接从基模型采样并通过 \(G_t\) 重新加权会导致粒子快速崩溃。我们改用扭曲提议

\[
q_t(y_t \mid y_{<t}, x, s_{t-1}) \propto p_\theta(y_t \mid y_{<t}, x) \exp\{\tau \Delta_t + \beta \psi_x(y_t)\},
\]

其中 \(\tau\) 是距离扭曲系数，\(\psi_x\) 是一个源支持分数。设 \(\mathcal{P}(x)\) 为数据集适配器暴露的全部源短语集，并设 \(\mathrm{first}(c)\) 为短语 \(c\) 的第一个分词器词元。我们在词汇表上定义一个短语起始经验测度

\[
\nu_x(v) = \frac{1}{|\mathcal{P}(x)|} \sum_{c \in \mathcal{P}(x)} \mathbf{1}\{\mathrm{first}(c) = v\},
\]

然后将其向均匀分布平滑，并处理对数密度比

\[
\psi_x(v) = \log \tilde{\nu}_x(v) - \log |\mathcal{V}|^{-1}.
\]

因子 \(\psi_x\) 计算成本低，并将提议偏向可以开始源支持短语的词元，这对于精确值、名称和实体提及特别有用。验证运行设置 \(\tau = \lambda = 2.0\) 和 \(\beta = 0.4\)。

### 5.3. 重要性权重与 ESS

如果粒子 \(i\) 采样 \(y_t^{(i)} \sim q_t\)，其增量权重更新为

\[
\log w_t^{(i)} = \log w_{t-1}^{(i)} + \log p_\theta (y_t^{(i)} \mid y_{<t}^{(i)}, x) + \lambda \Delta_t^{(i)} - \log q_t (y_t^{(i)} \mid y_{<t}^{(i)}, x, s_{t-1}^{(i)}).
\]

归一化权重为

\[
\bar{w}_t^{(i)} = \frac{w_t^{(i)}}{\sum_j w_t^{(j)}},
\]

有效样本量为

\[
\mathrm{ESS}_t = \frac{1}{\sum_i (\bar{w}_t^{(i)})^2}.
\]

当 \(\mathrm{ESS}_t < \rho P\) 时触发重采样，其中 \(P\) 是粒子数，\(\rho\) 是 ESS 阈值。

### 5.4. 多层次分裂

在低接受率情况下，即使扭曲提议也可能无法在靠近接受状态附近维持足够质量。我们使用周期性多层次分裂将有限粒子重新分配给剩余自动机距离更小的部分轨迹。在固定间隔，粒子按

\[
R_t^{(i)} = \log w_t^{(i)} - \lambda d(s_t^{(i)})
\]

排序，并复制顶层精英集以重新填充群体。此步骤与自适应多层次分裂相关（Cerou 和 Guyader，2007 (https://arxiv.org/html/2606.11203#bib.bib2)）。由于它在有限计算下改变估计器，我们将其视为搜索分配机制，而非精确后验采样器。

算法 1 扭曲 SMC 桥接器。
1: 用源前缀预热隐藏状态
2: 初始化 \(P\) 个粒子，带有自动机状态 \(s_0\)、隐藏状态 \(h_0\) 和权重 \(w_0=1\)
3: for \(t=1\) to \(T\) do
4:    for 粒子 \(i=1,\dots,P\) do
5:      从前缀模型计算基本逻辑值
6:      从自动机转换计算进展分数 \(\Delta_t^{(i)}\)
7:      从扭曲提议 \(q_t\) 采样 \(y_t^{(i)}\)
8:      使用重要性比率更新粒子权重
9:      更新自动机状态和隐藏状态
10:   end for
11:   计算 ESS 并在需要时重采样
12:   在预定检查点应用精英分裂
13: end for
14: 返回最佳接受序列和摘要诊断

## 6. 前缀语言模型

提议模型由一个嵌入层、一个堆叠的 GRU 和一个输出投影构成。此架构提供了一个稳定的条件提议，可以在本地硬件上快速训练，并在 SMC 期间逐步查询。它还使得跨粒子的隐藏状态复制成本较低，这对于局部粒子解码很重要。

每个示例序列化为

\[
\langle\text{bos}\rangle \langle\text{src}\rangle \text{源序列化} \langle\text{tgt}\rangle \text{目标表面} \langle\text{eos}\rangle.
\]

损失是一个掩蔽的下一词元交叉熵，其中源前缀被排除在监督之外。因此，模型学习 t