Temporal Backtracking Search for Test-time Generative Video Reasoning¶

会议: NeurIPS 2026
arXiv: 2606.13861
代码: https://sejoonjun.github.io/TBS/
领域: VLM 推理
关键词: 视频生成推理, 测试时计算缩放, 时序回溯搜索, 过程验证, 条件复用

一句话总结¶

针对传统视频生成推理在去噪步搜索无效以及根节点采样盲目丢弃上游正确进度的困境，本文提出时序回溯搜索（TBS），通过可变前缀条件生成、时序过程验证与前缀优先级搜索，将视频推理重构为“生成-验证-回溯”循环，在长程与分布外视频推理任务中显著优于 Best-of-N。

研究背景与动机¶

生成式视频模型正逐步从纯粹的视觉内容创作演进为面向序贯决策的世界模拟器，智能体通过从生成的视频模拟中提取动作方案，能够在想象空间中进行搜索、规划并解决复杂任务。在这种以逻辑推理为导向的范式下，测试时计算缩放（test-time scaling）的核心优化目标不再是美学画质或文本对齐度，而是轨迹的逻辑正确性——即生成的视频是否呈现出解决给定问题的有效因果路径。

然而，现有的视频测试时扩展范式在长程逻辑推理中普遍面临两个严峻的经验瓶颈。首先，中间潜在变量的解码分析表明，视频扩散模型在去噪轨迹的最早几个步骤内就过早锁定了高层空间运动规划，后续去噪步骤的计算投入根本无法挽救从起点就产生逻辑缺陷的轨迹，因此在去噪步轴线上进行搜索对于纠正逻辑错误完全无效。其次，视频生成中的逻辑推理错误并非在时间轴上均匀分布，而是高度聚集在生成轨迹的前期阶段；当前社区广泛采用的根节点 Best-of-N（BoN）采样将整段视频视为不可分割的整体，一旦遇到单步失误就将完整视频推倒重来，既盲目丢弃了上游已验证的有效前缀进度，又在前期瓶颈区域反复重复采样并再次失败，造成巨大的计算浪费。

面对长程时序中错误累积导致的“条件复用差距”，最合理的策略是将搜索空间从去噪步轴线彻底转向时间轴，保留已验证的有效前缀并把有限计算预算精准投向错误后缀的局部修复。本文的核心 idea 是：将单次全量视频生成重构为基于时间轴的“生成-验证-回溯重启”迭代闭环（Temporal Backtracking Search, TBS），通过可变长度前缀条件生成机制保留前序运动动量，借助时序过程验证器定位首个失误帧并提取对齐重启锚点，进而基于优先级前沿队列重配计算预算延展有效轨迹。

方法详解¶

整体框架¶

TBS 将长程时序视频生成推理拆解为基于状态空间树的短程子问题求解过程。系统由生成器 $\mathcal{G}$、过程验证器 $\mathcal{V}$ 和优先级搜索前沿队列 $\mathcal{F}$ 协同驱动。整体流程包含三大核心阶段：首先在根节点生成初始候选轨迹；随后由过程验证器判定逻辑正确性、定位首个错误帧并提取经时间潜在步长对齐的有效前缀锚点；最后在搜索循环中弹出最高优先级的有效锚点，以此为条件分支采样生成后续子轨迹，直至寻得完全正确的求解视频或耗尽计算预算。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["初始帧 v_1 与任务 Prompt p"] --> B["根节点采样候选视频<br/>k_1 条完整候选轨迹"]
    B --> C["时序过程验证与锚点提取<br/>检测首个错误帧 F 并对齐至 VAE 潜步 R"]
    C -->|达成完全解 EM=1| D["输出正确解视频"]
    C -->|未解但含有效前缀 R>1| E["入队优先级前沿池 F<br/>元组 (K, v_1:R, π)"]
    E --> F["弹出最优前缀锚点 n*<br/>依启发式分数 π 贪婪选取"]
    F --> G["可变 K 条件后缀扩展<br/>保持前序动态并采样 s 个子后缀"]
    G --> C

关键设计¶

1. 可变 K 前缀条件生成引擎：跨时间分支的动力学保持

传统视频扩散模型通常仅支持以单帧（$K=1$）作为初始条件进行全序列联合去噪，无法直接从任意中间帧无缝续写。若简单地截取错误发生前的最后一帧静态图像作为 $K=1$ 的新起点重置生成，会彻底丢失前置轨迹建立的速度、加速度、朝向及任务演进动量，导致后续修复成功率断崖式暴跌（消融实验显示修复率从 100% 暴跌至 2.5%）。为了赋予视频生成模型在任意干净前缀后无缝分支且不增加推理代价的能力，TBS 基于 Wan2.2-TI2V-5B 训练了支持可变前缀长度 $K$ 的 LoRA 适配器。在潜空间训练阶段，设定前 $K$ 个潜在帧的时间步为 $t_i=0$（纯净无噪隐变量），仅对后续 $i > K$ 的后缀潜在帧施加加噪与去噪损失： $$\tilde{\mathbf{z}}_i = \begin{cases} \mathbf{z}_i, & i \leq K \\ (1 - t)\mathbf{z}_i + t \boldsymbol{\epsilon}_i, & i > K \end{cases}$$ 为了防止模型面对长前缀输入时发生特征崩塌，训练过程引入递进式课程学习（curriculum learning），将 $K$ 的最大上限从 1 逐步放宽至 20 潜在帧，使模型能够稳定承接长达数十帧的动态上下文。

2. 时序过程验证与潜帧对齐回溯锚点提取

单凭结果检验（Outcome Verification）只能给出非黑即白的二值信号，无法指导时间轴上的局部搜索。TBS 引入细粒度过程验证器 $\mathcal{V}$，依据领域规则、学习型轨迹预测或物理仿真状态，定义轨迹步间转移有效性指示函数 $\phi(v_1, \dots, v_t)$，并据此提取整段视频的首次逻辑失效帧： $$F(\mathbf{v}) = \min \{ t : \phi(v_1, \dots, v_t) = 0 \}$$ 由于潜空间视频扩散模型存在时间压缩因子 $\tau$（在 Wan2.2 中 $\tau=4$，即每个潜在帧对应 4 个像素帧），重启帧必须与 VAE 的潜在时间网格严格对齐，否则会导致潜在特征重叠或因果信息泄露。系统计算向下取整的安全重启帧 $R(\mathbf{v}) = \tau \cdot \lfloor (F(\mathbf{v}) - 1) / \tau \rfloor$ 与潜在前缀长度 $K = R / \tau$。若 $R > 1$，则该前缀被视为宝贵的中间求解资产，连同验证器评估的启发式优先级分数 $\pi$ 封装为锚点存入前沿池 $\mathcal{F}$。

3. 前缀优先级状态前沿搜索：打破单次全量采样的算力浪费

在长程规划问题中，全量独立采样因“条件复用差距”（Conditional Reuse Gap）而效率极其低下——从根节点从头生成全局解的联合概率 $P_{\mathrm{root}} = p_\theta(\mathbf{v}^*_{2:T} \mid v_1^*, p)$ 随时间步呈指数衰减，而在已验证前缀 $\mathbf{v}^*_{1:\ell}$ 基础上修补剩余后缀的难度 $P_{\mathrm{repair}}(\ell) = p_\theta(\mathbf{v}^*_{\ell+1:T} \mid \mathbf{v}^*_{1:\ell}^*, p)$ 显著降低。TBS 维护一个全局前沿优先队列 $\mathcal{F}$，每轮迭代依 $\pi$ 弹出最有希望的前缀锚点，利用可变 $K$ 扩散模型派生 $s$ 个子代后缀分支，并将新产生的未完成有效前缀重新回填至队列。总计算预算由根节点采样数 $k_1$、每轮分支数 $s$ 及最大扩展步数 $m$ 严格约束为 $B = k_1 + s(m - 1)$。根据不同任务的错误特征，TBS 展现出灵活的拓扑自适应性：在空间漂移易于后缀修复的迷宫任务中采用“窄而深”（$k_1=2$）的纵深回溯，而在存在不可逆死锁状态的推箱子（Sokoban）任务中采用“宽根节点”（$k_1=8$）结合 BFS 死态剪枝的搜索拓扑，确保算力精准投向具备真实延展价值的轨迹分支。

损失函数 / 训练策略¶

基础视频生成模型选用 Wan2.2-TI2V-5B，冻结主干权重并引入 Rank=32、Alpha=32 的 LoRA 适配层，在预编码的 VAE 潜在表征缓存上进行整流流匹配（Rectified Flow）微调。优化器采用 AdamW，学习率恒定设为 $2 \times 10^{-4}$，权重衰减为 $1 \times 10^{-4}$。推理阶段去噪步数固定为 50 步，无分类器引导（CFG）缩放系数与 Sigma 偏移量均设为 5.0。前缀长度 $K$ 采用五阶段课程训练：从前 10% 进度的 $K=1$，逐步过渡到 10%–30%（最大 $K=5$）、30%–55%（最大 $K=10$）、55%–80%（最大 $K=15$），最终在 80%–100% 阶段达到最大 $K=20$ 并均匀采样长前缀桶，确保模型具备极强的长前缀生成鲁棒性。

实验关键数据¶

主实验¶

评估涵盖结构化网格推理（2D Maze、3D Maze、Sokoban、Sliding Puzzle、Keys-and-Doors）、连续导航规划（Target-Bench）与真实双臂机器人操作仿真（RoboTwin）三大机制各异的基准。在结构化推理任务中，重点评估严格匹配率（Exact-Match, EM %）；连续导航评估路径位移误差与一致性；机器人操作评估物理成功率。

数据集 / 划分	指标	BoN-1 (单次)	BoN-10	TBS-10 (同算力)	BoN-20	TBS-20 (同算力)
2D Maze (Overall)	EM (%)	51.0 ± 4.0	75.2 ± 3.6	84.0 ± 3.1	79.0 ± 3.4	90.3 ± 2.6
2D Maze (Hard)	EM (%)	18.3 ± 4.8	53.0 ± 5.7	68.7 ± 5.5	60.0 ± 5.6	81.0 ± 4.8
3D Maze (Overall)	EM (%)	85.5 ± 3.0	96.2 ± 1.9	97.2 ± 1.7	96.7 ± 1.8	97.7 ± 1.6
3D Maze (Hard)	EM (%)	73.0 ± 5.3	92.7 ± 3.6	94.3 ± 3.2	93.7 ± 3.4	95.3 ± 3.0
Sokoban (Overall)	EM (%)	41.5 ± 4.0	75.5 ± 3.6	77.7 ± 3.5	82.0 ± 3.3	82.7 ± 3.3
Sokoban (Hard)	EM (%)	37.0 ± 5.6	72.3 ± 5.3	73.0 ± 5.3	78.3 ± 5.0	79.7 ± 4.9
Sliding Puzzle (Overall)	EM (%)	39.5 ± 4.0	74.7 ± 3.7	80.8 ± 3.3	82.2 ± 3.3	86.5 ± 3.0
Sliding Puzzle (Hard)	EM (%)	41.3 ± 5.7	74.0 ± 5.2	81.3 ± 4.8	81.3 ± 4.8	88.7 ± 4.1
Keys-and-Doors (Overall)	EM (%)	52.3 ± 4.0	94.5 ± 2.1	96.5 ± 1.8	97.7 ± 1.6	99.2 ± 1.1
Keys-and-Doors (Strict-OOD)	EM (%)	0.0	0.3	8.3 ± 3.7	0.7	22.7 ± 5.0

在连续导航基准 Target-Bench 上，TBS 在同等算力预算下全面优于 BoN：在预算 5 下，TBS-5 相比 BoN-5 将偏离真实路径大于 1 米的失误率（MR）从 2.70% 显著压低至 1.56%，逼近一致性得分（AC）从 0.872 提升至 0.936，官方综合评分从 0.473 提升至 0.511。在 RoboTwin 双臂机器人操作仿真中，TBS-5 在干净场景下取得 53% 成功率（相比 BoN-5 的 49% 绝对提升 +4%）。

消融实验¶

1. 前缀条件生成策略消融（已知可修复父前缀子集，40 样本）

配置 / 策略	2D Maze EM (%)	2D Maze 任意目标成功率 (%)	Sliding Puzzle EM (%)	说明
Full Prefix (TBS 默认)	100.0% (40/40)	100.0% (40/40)	100.0% (40/40)	完整编码前序多帧动态潜变量
Last-frame Reset (单帧重置)	2.5% (1/40)	5.0% (2/40)	5.0% (2/40)	丢弃前序帧，仅以锚点单帧重置 ($K=1$)

2. 搜索策略消融（固定预算 $B=20$，困难划分）

搜索策略	2D Maze Hard	Sliding Puzzle Hard	Sokoban Hard	Keys-Doors Strict-OOD	说明
BoN-20 (根节点独立)	60.0%	81.3%	78.3%	0.7%	无前缀复用
Greedy (容量=1 单线修补)	61.0%	83.7%	74.7%	6.7%	仅保留单一最优锚点，极易过早过拟合
Beam-2 (容量=2 束搜索)	78.3%	87.3%	77.3%	19.7%	保留两个分支候选，显著改善单线问题
Random (无序随机弹出)	74.7%	84.0%	78.7%	12.7%	保留前沿多样性但缺乏启发式优先级排序
TBS-20 (全前沿优先级搜索)	81.0%	88.7%	79.7%	22.7%	全局最优前沿管理 + 状态质量优先

关键发现¶

时序回溯是长程 OOD 推理断崖式提升的唯一根源：在 Keys-and-Doors 严格分布外（Strict-OOD，161 帧超长路径）测试中，单次生成与 BoN-20 彻底崩溃（准确率仅 0.7%），而 TBS-20 达到了 22.7%。机制追踪发现，TBS-20 解出的全部 68 个成功样本中，根节点（深度 0）解出数为 0，100% 的成功求解均来自深度 $\geq 1$ 的回溯分支。
动态前缀包含无法由静态单帧替代的动量上下文：在可修复样本消融中，仅仅将动态前缀替换为单帧状态重置，修复成功率便由 100% 塌缩至 2.5%，证实视频推理的修复极其依赖前置帧赋予的连续动作趋势与环境交互惯性。
搜索拓扑因领域失效模式而异：在轨迹错误仅表现为局部漂移的几何路径任务（Maze）中，“窄根深探”（$k_1=2$）显著占优；而在包含死锁状态的语义任务（Sokoban）中，由于前缀可能在视觉合法的同时已陷入全局不可解死态，必须采用“宽根搜索”（$k_1=8$）并结合 BFS 状态验证，否则单纯加深搜索反而会陷入错误前缀的局部死循环。

亮点与洞察¶

将扩散模型测试时算力扩展从去噪轴转移至时间轴：揭示了视频扩散模型在去噪前几步即冻结空间运动规划的关键机理，指出去噪步搜索和全局重采样的本质缺陷，开创了时间维度的“生成-验证-回溯”新范式。
可变前缀条件生成的低成本实现：通过整流流加噪掩码与渐进式课程训练，以单个轻量级 LoRA 赋予大模型任意中间帧因果分支生成能力，保证每次局部修补的计算成本严格恒定。
对噪声验证信号的高容忍度与平滑退化特性：Target-Bench 连续导航实验证实，即便过程验证器受高达 0.7 米的高斯噪声干扰，TBS 依然能够优于或平滑收敛至 BoN 表现，不会因验证器噪声产生负向崩溃。

局限与展望¶

依赖基础生成模型的局部先验能力：TBS 本质上是放大和拼接视频模型已具备的局部生成能力，无法凭空创造模型完全未掌握的底层能力。在 RoboTwin 强视觉扰动场景下，因单步前缀成功率极低，TBS 的收益明显收窄。
当前依赖领域特定或外部模拟验证器：当前实现中过程验证高度依赖符号规则、外部轨迹预测器或物理仿真。未来需要探索端到端的隐式视频过程奖励模型（Video PRM），实现无须外部仿真器的通用自动化时序回溯搜索。

评分¶

新颖性: ⭐⭐⭐⭐⭐ [首次揭示去噪步搜索在视频逻辑推理中的失效瓶颈，系统性提出时序回溯前缀搜索架构]
实验充分度: ⭐⭐⭐⭐⭐ [覆盖符号网格、连续导航、双臂物理仿真三大维度，含严谨的深度分布与 OOD 机制分析]
写作质量: ⭐⭐⭐⭐⭐ [逻辑链条严密，动机图与消融设计高度自洽，定量定性分析透彻]
价值: ⭐⭐⭐⭐⭐ [为视频生成模型作为具身世界模拟器的测试时扩展奠定了坚实且极具启发性的方法基础]