Transformer可以在回溯搜索中学习验证吗？

回溯搜索是经典约束求解器、规划器和定理证明器的基础。最近基于 Transformer 的推理系统通过其自己的中间步骤探索搜索树。常见的训练方法适合离线求解器轨迹上的自回归下一个词元损失。模型每一步的输入都是所有先前决策的累积轨迹。最佳的继续或回溯预测器仅取决于当前搜索状态，因为达到相同状态的两条轨迹允许相同的可行延续。我们证明，仅在累积轨迹上训练的解码器 Transformer 在两个方面未能满足这一要求：轨迹可以将状态特征分散到许多位置（分散检索），并且预测器可以以轨迹而不是状态为条件（历史纠缠）。我们通过本地化来解决分散检索，这是一种跟踪级修复，重写每个决策块以在本地公开状态特征。我们使用选择性状态注意力（SSA）来解决历史纠缠，这是一种固定注意力掩模，可以在结构上强制执行基于状态的决策，而无需修改训练数据、目标或参数。在传播暴露出矛盾之后，我们专注于反应性验证。我们在 3-SAT、图形着色、Blocks World 和回溯解析上测试 SSA。对于仅先前历史不同的相同状态对，SSA 会发出相同的决策，而累积训练的因果基线则不会。我们的贡献是对序列化轨迹数据上的 Transformer 行为进行诊断，并进行结构修复。搜索自己的推理步骤的预训练语言模型可能会面临同样的失败。我们的分析将推理时上下文清除作为无需重新训练即可应用相同隔离的候选方法。