PaperlayerView exact revision on arXiv

Source-linked AI summary

Video Models Can Reason with Verifiable Rewards

Tinghui Zhu, Sheng Zhang, James Y. Huang, Selena Song, Xiaofei Wen, Yuankai Li, Hoifung Poon, Muhao Chen

arXiv:2605.15458v1cs.CV

TL;DR

Video models are mainly optimized for plausible generation, leaving their ability to satisfy explicit reasoning constraints underexplored. VideoRLVR applies verifiable-reward reinforcement learning with dense decomposed rewards and early-step optimization, improving success across Maze, FlowFree, and Sokoban over supervised fine-tuning.

  • Problem

    Video generation lacks sufficient evidence of satisfying task-specific spatial, temporal, and logical correctness beyond perceptual quality and coherence.

  • Method

    VideoRLVR optimizes video diffusion models for verifiable visual trajectories using SDE-GRPO, dense decomposed rewards, and Early-Step Focus.

  • Results

    VideoRLVR improves success rates over supervised fine-tuning across Maze, FlowFree, and Sokoban, by 6.1%, 5.5%, and 3.2%, respectively.

  • Takeaways & Limitations

    Verifiable reinforcement learning improves video reasoning across the evaluated domains, with dense decomposed rewards especially useful in low-success-rate settings.

Abstract

from arXiv · show

Video diffusion models have made rapid progress in perceptual realism and temporal coherence, but they remain primarily optimized for plausible generation rather than verifiable reasoning. This limitation is especially pronounced in tasks where generated videos must satisfy explicit spatial, temporal, or logical constraints. Inspired by the role of reinforcement learning with verifiable rewards (RLVR) in reasoning-oriented language models, we introduce VideoRLVR, a practical recipe for optimizing video diffusion models with rule-based feedback. VideoRLVR formulates video reasoning as the generation of verifiable visual trajectories and consists of an SDE-GRPO optimization backbone, dense decomposed rewards, and an Early-Step Focus strategy for efficient training. The Early-Step Focus strategy restricts policy optimization to the early denoising phase, reducing training latency by about 40% while preserving performance. We evaluate VideoRLVR on Maze, FlowFree, and Sokoban, three procedurally generated domains with objective success criteria. Across these tasks, VideoRLVR consistently improves over supervised fine-tuning baselines, with dense decomposed rewards proving especially important in low-success-rate settings. Our RL-optimized model also outperforms the evaluated proprietary and open-source video generation models on these verifiable reasoning benchmarks and out-of-domain benchmarks. These results suggest that verifiable RL can move video models beyond perceptual imitation toward more reliable rule-consistent visual reasoning.

1 Introduction

VideoRLVR addresses the gap between perceptual plausibility and objectively correct video reasoning by optimizing video diffusion models with verifiable rewards. It combines SDE-GRPO, dense decomposed rewards, and Early-Step Focus, improving success rates across Maze, FlowFree, and Sokoban while reducing training time by about 40%.

  • Motivation: Current video diffusion models prioritize perceptual quality, temporal coherence, and plausible motion, making objective correctness difficult to elicit and verify reliably.The central challenge is the mismatch between perceptual plausibility and objective correctness.
  • Method: VideoRLVR applies reinforcement learning with verifiable rewards to optimize video diffusion models for rule-verifiable visual trajectories.The framework provides informative feedback through dense decomposed reward functions.
  • Method: The framework combines an SDE-GRPO optimization backbone, dense decomposed rewards, rule-based trajectory generation, and an Early-Step Focus strategy.Early-Step Focus concentrates optimization on the early denoising phase rather than the entire denoising trajectory.
  • Results: 6.1%, 5.5%, and 3.2%: VideoRLVR improves success rates over the initializing SFT checkpoint on Maze, FlowFree, and Sokoban, respectively.The evaluation suite is designed for rule-based verification across all three domains.
  • Efficiency: about 40%: Early-Step Focus reduces training time by about 40% while preserving performance.The strategy restricts stochastic exploration and backpropagation to the early denoising phase.

2 Related Work

Prior work applies reinforcement learning to diffusion and flow-matching models, investigates video generation as visual-state reasoning, and uses verifiable rewards to train reasoning-oriented language models. These lines of research motivate treating video generation as a verifiable reasoning process.

  • Reinforcement learning for diffusion and flow-matching models: Reinforcement learning aligns diffusion and flow-based generative models with human preferences, perceptual objectives, and task-specific rewards.Prior methods formulate denoising as a sequential decision process and apply policy-gradient or preference-optimization methods to text-to-image and video generation.
  • Reasoning in video generation models: Recent studies examine video generation models as reasoning systems, framing generated videos as chains of visual states or “chain of frames.”Large-scale video models show emerging abilities on visual puzzles and sequential prediction, while benchmarks evaluate reasoning-oriented video tasks.
  • Verifiable reinforcement learning and reasoning models: Verifiable reinforcement learning rewards reasoning models using objective correctness signals rather than only human preference judgments.Examples include mathematical equivalence, executable code tests, and rule-based verification, providing scalable supervision for reasoning-oriented language models.

3 Problem Formulation

VideoRLVR formulates video reasoning as conditional generation of rule-verifiable visual trajectories and casts reverse video denoising as an MDP. Because deterministic flow-matching dynamics lack tractable stochastic transition densities, the framework uses an SDE formulation and evaluates Maze, FlowFree, and Sokoban.

  • RLVR for Video Reasoning: Video reasoning generates visual-state sequences whose transitions and terminal states are checked against task-specific rules.The conditioning input is c = (I0, T), comprising an initial image and textual instruction.
  • Video Generation as a Markov Decision Process: Reverse denoising is formulated as an MDP over latent variables, with rewards computed after decoding the final video.The MDP is defined over denoising steps rather than reasoning steps.
  • Video Generation as a Markov Decision Process: Deterministic flow-matching ODE solvers provide no tractable stochastic transition density for likelihood-ratio policy gradients.The next latent is a deterministic function of (x_tk, c), motivating an SDE-based formulation with stochastic transitions.
  • Tasks: VideoRLVR evaluates three rule-verifiable visual reasoning domains: Maze, FlowFree, and Sokoban.These tasks support rule-based correctness checks, large-scale instance generation, and varied reasoning complexity.

4 RLVR Recipe for Video Reasoning Models

VideoRLVR is a three-part recipe for optimizing video models with verifiable rewards: SDE-GRPO, Early-Step Focus, and dense decomposed rewards. It makes stochastic policy optimization efficient while providing task-aware feedback for rule-based video reasoning.

  • Recipe components: VideoRLVR combines an SDE-GRPO optimization backbone, Early-Step Focus, and dense decomposed reward design and acquisition.These are the recipe’s three components.
  • SDE-GRPO: SDE-GRPO converts deterministic flow-matching denoising into stochastic Gaussian transitions, enabling closed-form log-probabilities and likelihood-ratio policy gradients.GRPO estimates relative advantages from sampled groups without a separate critic, while the final objective adds a reference-model KL penalty.
  • Early-Step Focus: 40% training-latency reduction is achieved by restricting stochastic perturbation, log-probability computation, and backpropagation to the first 10 of 20 denoising steps while preserving reasoning performance.Full trajectories remain used for generation and reward evaluation; later steps retain the generative refinement process.
  • Dense decomposed rewards: Dense decomposed rewards measure partial progress through rule-based structural components, especially improving reward variation in low-success-rate domains.Maze uses multiplicative connectivity and wall-consistency rewards, while FlowFree combines multiple structural metrics.

5 Experiments

The experiments test VideoRLVR on three rule-verifiable video reasoning domains and on transfer beyond training domains. VideoRLVR improves success rates over supervised fine-tuning and shows greater robustness than continued SFT as task complexity increases.

  • Experimental scope: Experiments compare VideoRLVR with supervised fine-tuning and competitive video-generation baselines on Maze, FlowFree, Sokoban, and an out-of-domain VBVR split.The evaluation targets both in-domain rule-based correctness and out-of-domain visual reasoning behavior.
  • Dataset: The dataset contains 30,000 procedurally generated samples, split evenly across Maze, FlowFree, and Sokoban, with varied color themes and 81-frame videos at 480×832 resolution.Color variation encourages reliance on structural invariants rather than specific visual features.
  • Evaluation: Evaluation combines trajectory alignment metrics—Precision, Recall, and F1—with symbolic success rate verifying whether generated videos satisfy task rules.Alignment is measured at pixel-, cell-, or action-level against reference solutions.
  • In-domain results: 6.1% on Maze, 5.5% on FlowFree, and 3.2% on Sokoban are VideoRLVR’s success-rate improvements over the SFT Epoch 5 checkpoint.VideoRLVR also surpasses recent state-of-the-art closed-source models on these visual reasoning tasks.
  • Scaling with task complexity: 3.2% on Maze and 5.4% on FlowFree are VideoRLVR’s margins over SFT Epoch 10, while continued SFT provides little FlowFree improvement and degrades Sokoban performance.VideoRLVR also shows less degradation as Maze scale increases.
  • Language-model comparison: Frontier LLMs show sharp performance decay on Maze despite sophisticated textual reasoning capabilities, unlike the RLVR-optimized video model.The comparison is used to highlight a representation bottleneck for language-only reasoning on the visual maze task.

6 Analysis

VideoRLVR’s analysis identifies Early-Step Focus and KL regularization as important design choices, while dense rewards are especially useful when task success is rare. Qualitative comparisons show that supervised fine-tuning can reproduce domain appearance without reliably satisfying task rules.

  • Early-Step Focus: Early-Step Focus preserves nearly unchanged Maze success rates and F1 scores when optimization uses the first L = 10 steps instead of the full L = 20 trajectory.The controlled experiment fixes the inference budget at T = 20 denoising steps; early denoising steps carry much of the reward-relevant structural signal.
  • KL Constraint: KL regularization maintains the generative prior, whereas removing the penalty with β = 0 can induce reward-hacking and visually implausible outputs.A constant penalty of β = 0.04 successfully anchors the model, according to the analysis.
  • Dense Reward Design: Sparse binary rewards are informative in Maze but provide little useful signal on high-complexity FlowFree and Sokoban tasks with near-zero initial success.Maze success occurs frequently enough during group rollouts to distinguish advantageous from disadvantageous trajectories, while FlowFree and Sokoban suffer extreme gradient sparsity.
  • Qualitative Generation Behavior: The SFT baseline often reproduces each domain’s visual format but can violate task rules through disconnected paths, inconsistent connectivity, or invalid object transitions.In Sokoban, the baseline produces a visually plausible but invalid shortcut rather than a valid box-pushing sequence.

7 Conclusion

The paper introduces VideoRLVR, a practical reinforcement-learning recipe that uses verifiable rewards to improve task-level logical correctness in video reasoning models.

  • 7 Conclusion: VideoRLVR combines rule-verifiable data generation, an SDE-GRPO optimization backbone, dense decomposed rewards, and Early-Step Focus.These components form the proposed practical recipe for optimizing video reasoning models.
  • 7 Conclusion: The approach targets the gap between perceptual video synthesis and task-level logical correctness.The paper frames verifiable rewards as a way to address this mismatch in video reasoning.
  • 7 Conclusion: Supervised fine-tuning provides an important visual and structural prior for video reasoning models.The passage identifies supervised fine-tuning as a foundational component of the experiments.

A Dataset Generation Details … A.3 Sokoban Generation

The dataset uses rule-based generators to create visually rendered tasks with known valid trajectories and metadata for automatic verification. Maze, FlowFree, and Sokoban use task-specific construction and solving procedures to retain only verified instances.

  • A Dataset Generation Details: All generated instances include an initial visual state, textual instruction, ground-truth state/action trajectory, rendered video, and verification metadata.Rule-based generation ensures retained samples have verified valid solutions.
  • A.1 Maze Generation: Maze instances use maze-carving algorithms, opposite-corner start and goal cells, and shortest-path search to obtain valid trajectories.The listed carving methods include depth-first search, Prim’s algorithm, and Kruskal’s algorithm.
  • A.1 Maze Generation: Maze trajectories are expanded from logical cells to continuous pixel-level paths, with successive-coordinate differences producing actions in {U, D, L, R}.The expanded paths support rendering the ground-truth video.
  • A.2 FlowFree Generation: FlowFree puzzles are generated from full-coverage Hamiltonian paths constructed by Warnsdorff-style search with random tie-breaking and bounded retries.The search prioritizes neighboring cells with the fewest onward unvisited moves.
  • A.2 FlowFree Generation: Each FlowFree path is split into k contiguous segments, whose endpoints become colored dots while the complete segments remain the ground-truth flows.Each segment contains at least two cells, and every constructed puzzle has a known valid solution.
  • A.3 Sokoban Generation: Sokoban candidates sample connected floors, player, boxes, and targets, then apply deadlock filtering before symbolic solving.Filtering excludes trivially unsolvable configurations such as boxes in wall corners.
  • A.3 Sokoban Generation: Sokoban solving uses breadth-first search over states (p, B), enforcing legal player movement and box pushes through empty-floor transition checks.The state consists of the player position and set of box positions.
  • A.3 Sokoban Generation: Because breadth-first search expands by action length, the first solution is optimal; capped unsolved candidates are discarded and regenerated.Retained samples include metadata checking player motion, box motion, illegal pulls, teleportation, and final target conditions.

B Experimental Setup · B.1 Dataset · B.2 Evaluation

The experiments use 10,000 procedurally generated instances for each of Maze, FlowFree, and Sokoban, with videos encoding task-specific solution trajectories. Evaluation combines trajectory-alignment metrics with symbolic success detectors that verify rule-consistent outcomes and processes.

  • B.1 Dataset: Maze contains 10,000 samples with 7×7–21×21 grids, pairing unsolved layouts with ground-truth videos rendering contiguous paths between start and goal markers.Each instance includes start and goal markers and a reference path video.
  • B.1 Dataset: FlowFree contains 10,000 puzzles on 5×5–8×8 grids, generated by splitting Hamiltonian paths into colored segments that must occupy every cell.Videos progressively color each path from discrete color-pair endpoints.
  • B.1 Dataset: Sokoban contains 10,000 puzzles with 6×6–10×10 grids, 1–3 boxes, and solution trajectories capped at 60 moves.Videos align one agent push with each frame, starting from the initial board configuration.
  • B.2 Evaluation: Trajectory alignment is measured using precision, recall, and F1 at the solution-manifold unit most natural to each task.The evaluation uses pixel-level, cell-level, and action-level representations for Maze, FlowFree, and Sokoban, respectively.
  • B.2 Evaluation: Maze evaluation uses a pixel-level change mask between initial and final frames to isolate the generated path from the static background.This focuses the metric on model intervention rather than background reconstruction.
  • B.2 Evaluation: FlowFree evaluation extracts mean colors for each terminal-frame grid cell, emphasizing semantic path coloring over anti-aliasing artifacts.The cell-level representation targets correctness of the completed coloring.
  • B.2 Evaluation: Sokoban evaluation decodes videos into symbolic actions a ∈{U(Up), D(Down), L(Left), R(Right)} and reports position-aligned F1.This metric penalizes out-of-order or invalid moves despite potentially matching final states.
  • B.2 Evaluation: Binary symbolic success detectors parse videos into states to verify alternatives and rule compliance: Maze checks connected paths and walls, FlowFree checks endpoints, connectivity, and fill-rate, and Sokoban checks physics-valid processes and the target final state.The detectors address cases where a single ground-truth reference cannot capture valid alternatives or visually plausible rule violations.

C Analysis · C.1 KL Constraint

The KL-regularization ablation compares VideoRLVR training with and without a KL penalty while holding all other hyperparameters fixed. The regularized run uses β = 0.04, whereas the ablated run sets β = 0, removing the constraint to the SFT reference policy.

  • C.1 KL Constraint: The ablation holds the SFT checkpoint, group size, denoising-step budget, reward function, and training prompts constant while varying only β.The regularized setting uses the default β = 0.04; the ablated setting uses β = 0.
Loading 2605.15458v1…