ViterbiPlanNet: Injecting Procedural Knowledge via Differentiable Viterbi for Planning in Instructional Videos

Luigi Seminara; Davide Moltisanti; Antonino Furnari

cs.CVMar 4, 2026

ViterbiPlanNet: Injecting Procedural Knowledge via Differentiable Viterbi for Planning in Instructional Videos

Authors: Luigi Seminara, Davide Moltisanti, Antonino Furnari

Organizations: University of Catania · University of Bath

Abstract

Procedural planning aims to predict a sequence of actions that transforms an initial visual state into a desired goal, a fundamental ability for intelligent agents operating in complex environments. Existing approaches typically rely on large-scale models that learn procedural structures implicitly, resulting in limited sample-efficiency and high computational cost. In this work we introduce ViterbiPlanNet, a principled framework that explicitly integrates procedural knowledge into the learning process through a Differentiable Viterbi Layer (DVL). The DVL embeds a Procedural Knowledge Graph (PKG) directly with the Viterbi decoding algorithm, replacing non-differentiable operations with smooth relaxations that enable end-to-end optimization. This design allows the model to learn through graph-based decoding. Experiments on CrossTask, COIN, and NIV demonstrate that ViterbiPlanNet achieves state-of-the-art performance with an order of magnitude fewer parameters than diffusion- and LLM-based planners. Extensive ablations show that performance gains arise from our differentiable structure-aware training rather than post-hoc refinement, resulting in improved sample efficiency and robustness to shorter unseen horizons. We also address testing inconsistencies establishing a unified testing protocol with consistent splits and evaluation metrics. With this new protocol, we run experiments multiple times and report results using bootstrapping to assess statistical significance.

Figures & tables

Figure 1: Given start and goal visual states, a neural model computes step-wise emissions. We propose a Differentiable Viterbi Layer that uses a Procedural Knowledge Graph (PKG) to decode emissions into a predicted plan. The layer allows gradients from the planning Loss ( $\mathcal{L}$ ) to flow and train the neural model end-to-end, forcing it to learn structure-aware visual representations.

Figure 2: ViterbiPlanNet consists of four main stages: 1) Encoding Procedural Knowledge – extracting PKGs from training data 2) Visual Encoding (

f_{enc}

) – extracting features from start and goal frames, trained with the

\mathcal{L}_{align}

and

\mathcal{L}_{task}

losses, 3) Computing emission probabilities

b

with

f_{emiss}

, and 4) Structured Decoding (

f_{vit}

) – parametrized by the PKG, taking as input emission probabilities and outputting a soft plan

\tilde{\pi}

. Training with a plan loss

\mathcal{L}_{plan}

, gradients pass through Structured Decoding and optimize

f_{emiss}

	Train	Inference		Metrics (%) ↑
	DVL	DVL	VD	SR	mAcc	mIoU
1	$\times$	$\times$	$\times$	32.47 $\pm$ 0.32	60.63 $\pm$ 0.22	82.45 $\pm$ 0.02
2	$\times$	$\times$	✓	32.99 $\pm$ 0.28	58.57 $\pm$ 0.20	82.34 $\pm$ 0.08
3	$\times$	✓	$\times$	32.09 $\pm$ 0.26	58.57 $\pm$ 0.20	82.34 $\pm$ 0.08
4	$\times$	✓	✓	30.77 $\pm$ 0.19	57.04 $\pm$ 0.12	81.95 $\pm$ 0.20
5	✓	$\times$	$\times$	20.05 $\pm$ 0.63	54.61 $\pm$ 0.27	76.99 $\pm$ 0.41

Table 1: Ablation of Viterbi components on CrossTask for

T{=}3

Figure 3: Performance as a function of training data on CrossTask for

T=3

. ViterbiPlanNet is more parameter-efficient, as it does not need to memorize procedural knowledge.

Method	PKG Use	w/o PKG	w/ PKG	Improv.
KEPP [ 15 ]	Conditioning	32.37 $\pm$ 5.36	34.93 $\pm$ 2.60	2.56 $\pm$ 5.93
PlanLLM [ 28 ]	Post-processing	34.87 $\pm$ 1.32	36.84 $\pm$ 1.21	1.97 $\pm$ 1.81
SCHEMA [ 16 ]	Post-processing	33.93 $\pm$ 0.59	37.24 $\pm$ 0.60	3.31 $\pm$ 0.84
ViterbiPlanNet	Guided Training	32.47 $\pm$ 0.32	38.45 $\pm$ 0.32	5.98 $\pm$ 0.47

Table 2: SR

\uparrow

(%) with and without PKG on CrossTask for

T=3

T	Method	CrossTask				COIN				NIV
T	Method	SR $\uparrow$ (%)	mAcc $\uparrow$ (%)	mIoU $\uparrow$ (%)	Params (M)	SR $\uparrow$ (%)	mAcc $\uparrow$ (%)	mIoU $\uparrow$ (%)	Params (M)	SR $\uparrow$ (%)	mAcc $\uparrow$ (%)	mIoU $\uparrow$ (%)	Params (M)
3	Qwen2.5-VL-32B [ 3 ]	11.48	36.35	69.52	32,000	3.65	17.51	52.10	32,000	7.41	27.65	59.73	32,000
	Qwen2.5-32B [ 17 ]	25.14	56.10	80.92	32,000	14.97	36.34	78.74	32,000	24.07	43.46	71.88	32,000
	Gemini 2.5 Pro [ 7 ]	29.18	57.90	81.48	$>$ 100,000	17.02	38.87	78.73	$>$ 100,000	24.07	43.46	71.86	$>$ 100,000
	Qwen3-30B [ 27 ]	23.37	55.96	81.16	30,000	14.52	36.56	78.07	30,000	24.81	42.84	70.80	30,000
	Qwen3-30B [ 27 ] + PKG	23.31	56.15	81.06	30,000	14.63	36.53	78.11	30,000	25.19	43.95	71.98	30,000

Table 3: Comparison with the state of the art. Best and second-best results are highlighted for each metric within each time horizon. Statistically significant performance differences (i.e., cases in which the confidence interval does not include zero) are marked in yellow .

Horizon	Method	CrossTask
Horizon	Method	SR $\uparrow$ (%)	mAcc $\uparrow$ (%)	mIoU $\uparrow$ (%)	Params (M)
T = 3	MTID ♣ [ 31 ]	40.45	67.19	69.17	1,085.20
T = 3	ViterbiPlanNet ♣	39.75	67.39	76.92	5.49
T = 4	MTID ♣ [ 31 ]	24.76	60.69	67.67	1,085.20
T = 4	ViterbiPlanNet ♣	24.19	61.12	80.67	5.52

Table 4: Comparison with MTID ♣ on CrossTask.

Figure 4: Parameter Efficiency on CrossTask and NIV.

Method	SR $\uparrow$ (%) [6 $\rightarrow$ 3]	SR $\uparrow$ (%) [6 $\rightarrow$ 4]	SR $\uparrow$ (%) [6 $\rightarrow$ 5]
Qwen2.5-VL-32B [ 3 ]	10.38	6.35	2.59
Qwen2.5-32B [ 17 ]	16.88	7.24	4.28
Gemini 2.5 Pro [ 7 ]	20.97	10.46	4.57
Qwen3-30B [ 27 ]	17.17	8.14	4.61
Qwen3-30B [ 27 ] + PKG	17.83	8.29	4.06
PKG beam search	18.31 $\pm$ 0.40	8.26 $\pm$ 0.18	5.14 $\pm$ 0.22

Table 5: Cross-Horizon Consistency results on CrossTask.

Figure 5: Qualitative comparison. The Base Model (top) learns to implicitly memorize the PKG, baking transition probabilities (arrows) directly into its predictions (circles). ViterbiPlanNet (bottom) learns smoother emissions decoupled from the graph, relying on the PKG’s structural guidance for decoding.

Figure 6: Given start and goal visual states, a neural model computes step-wise emissions. We propose a Differentiable Viterbi Layer that uses a Procedural Knowledge Graph (PKG) to decode emissions into a predicted plan. The layer allows gradients from the planning Loss ( $\mathcal{L}$ ) to flow and train the neural model end-to-end, forcing it to learn structure-aware visual representations.

	Train	Inference		Metrics (%) $\uparrow$
	DVL	DVL	VD	SR	mAcc	mIoU
Horizon $T=4$
1	$\times$	$\times$	$\times$	18.93 $\pm$ 0.58	55.12 $\pm$ 0.46	79.87 $\pm$ 0.26
2	$\times$	$\times$	✓	18.64 $\pm$ 0.75	55.00 $\pm$ 0.38	79.78 $\pm$ 0.18
3	$\times$	✓	$\times$	21.54 $\pm$ 0.50	53.19 $\pm$ 0.46	79.90 $\pm$ 0.28
4	$\times$	✓	✓	19.92 $\pm$ 0.18	52.09 $\pm$ 0.43	79.78 $\pm$ 0.34

Table 6: Ablation of Viterbi components on CrossTask for

T\in\{4,5,6\}

Figure 7: Performance as a function of training data on CrossTask for

T=4

Figure 8: Performance as a function of training data on CrossTask for

T=5

Figure 9: Performance as a function of training data on CrossTask for

T=6

Horizon $T=4$
Method	PKG Use	w/o PKG	w/ PKG	Improv.
KEPP [ 15 ]	Conditioning	22.57 $\pm$ 0.52	22.34 $\pm$ 0.43	-0.23 $\pm$ 0.69
PlanLLM [ 28 ]	Post-processing	19.90 $\pm$ 0.40	22.91 $\pm$ 1.39	3.01 $\pm$ 1.42
SCHEMA [ 16 ]	Post-processing	19.79 $\pm$ 0.72	24.18 $\pm$ 0.47	4.39 $\pm$ 0.91
ViterbiPlanNet	Guided Training	18.93 $\pm$ 0.58	24.64 $\pm$ 0.30	5.71 $\pm$ 0.64
Horizon $T=5$

Table 7: SR

\uparrow

(%) with and without PKG on CrossTask for Horizons

T\in\{4,5,6\}

Horizon $T=3$
Method	w/ Task S.	w/o Task S.
PDPP [ 25 ]	36.73 $\pm$ 0.59	8.39 $\pm$ 8.02
PlanLLM [ 28 ]	36.84 $\pm$ 1.21	15.37 $\pm$ 14.09
SCHEMA [ 16 ]	37.24 $\pm$ 0.60	37.00 $\pm$ 0.27
ViterbiPlanNet	38.45 $\pm$ 0.32	38.32 $\pm$ 0.12
Horizon $T=4$

Table 8: SR

\uparrow

(%) with and without Task Supervision (Task S.) for Horizons

T\in\{3,4,5,6\}

T	Method	CrossTask				COIN				NIV
T	Method	SR $\uparrow$ (%)	mAcc $\uparrow$ (%)	mIoU $\uparrow$ (%)	Params (M)	SR $\uparrow$ (%)	mAcc $\uparrow$ (%)	mIoU $\uparrow$ (%)	Params (M)	SR $\uparrow$ (%)	mAcc $\uparrow$ (%)	mIoU $\uparrow$ (%)	Params (M)
3	Qwen2.5-VL-32B [ 3 ]	11.48	36.35	69.52	32,000	3.65	17.51	52.10	32,000	7.41	27.65	59.73	32,000
	Qwen2.5-32B [ 17 ]	25.14	56.10	80.92	32,000	14.97	36.34	78.74	32,000	24.07	43.46	71.88	32,000
	Gemini 2.5 Pro [ 7 ]	29.18	57.90	81.48	$>$ 100,000	17.02	38.87	78.73	$>$ 100,000	24.07	43.46	71.86	$>$ 100,000
	Qwen3-30B [ 27 ]	23.37	55.96	81.16	30,000	14.52	36.56	78.07	30,000	24.81	42.84	70.80	30,000
	Qwen3-30B [ 27 ] + PKG	23.31	56.15	81.06	30,000	14.63	36.53	78.11	30,000	25.19	43.95	71.98	30,000

Table 9: Comparison with the state of the art. Best and second-best results are highlighted for each metric within each time horizon. Statistically significant performance differences (i.e., cases in which the confidence interval does not include zero) are marked in yellow .

Horizon	Method	CrossTask				COIN				NIV
Horizon	Method	SR $\uparrow$ (%)	mAcc $\uparrow$ (%)	mIoU $\uparrow$ (%)	Params (M)	SR $\uparrow$ (%)	mAcc $\uparrow$ (%)	mIoU $\uparrow$ (%)	Params (M)	SR $\uparrow$ (%)	mAcc $\uparrow$ (%)	mIoU $\uparrow$ (%)	Params (M)
T = 3	MTID ♣ [ 31 ]	40.45	67.19	69.17	1085.20	30.44	51.70	59.74	1085.20	28.52	44.44	56.46	1085.20
T = 3	ViterbiPlanNet ♣	39.75	67.39	76.92	5.49	34.42	51.20	81.25	6.01	34.44	48.89	95.07	5.45
T = 4	MTID ♣ [ 31 ]	24.76	60.69	67.67	1085.20	22.74	49.90	61.25	1085.20	24.89	44.54	57.46	1085.20
T = 4	ViterbiPlanNet ♣	24.19	61.12	80.67	5.52	24.09	45.71	77.84	6.21	28.95	47.81	80.07	5.46
T = 5	MTID ♣ [ 31 ]	15.26	-	-	1085.20	-				-

Table 10: Performance comparison of MTID ♣ and ViterbiPlanNet ♣ across the CrossTask, COIN, and NIV datasets. The best and second-best results are highlighted for each metric within each time horizon.

Method	SR $\uparrow$ (%) [6 $\rightarrow$ 3]	SR $\uparrow$ (%) [6 $\rightarrow$ 4]	SR $\uparrow$ (%) [6 $\rightarrow$ 5]
Qwen2.5-VL-32B [ 3 ]	3.47	1.75	1.00
Qwen2.5-32B [ 17 ]	6.71	6.55	3.75
Gemini 2.5 Pro [ 7 ]	5.35	7.20	2.12
Qwen3-30B [ 27 ]	5.82	4.31	2.51
Qwen3-30B [ 27 ] + PKG	5.80	4.84	2.71
PKG beam search	6.85 $\pm$ 0.27	4.39 $\pm$ 0.14	1.66 $\pm$ 0.20

Table 11: Cross-Horizon Consistency results on COIN.

Method	SR $\uparrow$ (%) [6 $\rightarrow$ 3]	SR $\uparrow$ (%) [6 $\rightarrow$ 4]	SR $\uparrow$ (%) [6 $\rightarrow$ 5]
Qwen2.5-VL-32B [ 3 ]	9.26	5.70	1.60
Qwen2.5-32B [ 17 ]	3.33	5.70	8.02
Gemini 2.5 Pro [ 7 ]	1.11	6.14	9.63
Qwen3-30B [ 27 ]	3.33	5.70	8.02
Qwen3-30B [ 27 ] + PKG	4.07	7.46	9.63
PKG beam search	15.19 $\pm$ 1.70	14.56 $\pm$ 2.46	14.76 $\pm$ 2.46

Table 12: Cross-Horizon Consistency results on NIV.

Metric	Dataset/Condition	Result
PKG Coverage	CrossTask ( $T{=}3{\to}6$ )	$97.4\to 93.0$ (%)
(% test sequences with	COIN ( $T{=}3{\to}6$ )	$90.8\to 77.0$ (%)
transitions in the graph)	NIV ( $T{=}3{\to}6$ )	$86.7\to 72.3$ (%)
Decoding Diversity	Uniform Emissions	$H{=}0.00$ , JSD ${=}0.56$
(Entropy $H{\uparrow}$ , Jensen–	SCHEMA w/o PKG	$H{=}4.39$ , JSD ${=}0.51$
Shannon Divergence JSD ${\downarrow}$ ,	SCHEMA w/ PKG	$H{=}2.61$ , JSD ${=}0.39$

Table 13: PKG coverage and decoding diversity metrics.

Figure 10: Error overlap analysis on NIV

T=6

Figure 11: We evaluate performance under progressively corrupted procedural knowledge graphs (PKGs). Left: edge dropout obtained by randomly removing graph transitions. Center: noisy transition probabilities produced by Gaussian perturbations with variance

\sigma

. Right: PKGs reconstructed from limited or noisy supervision.

Method [SR $\uparrow$ (%)]	$T=3$	$T=4$	$T=5$	$T=6$
SCHEMA [ 16 ]	32.1 $\to$ 32.7 $\pm$ 0.4	23.6 $\to$ 21.9 $\pm$ 0.3	16.6 $\to$ 14.2 $\pm$ 0.4	13.1 $\to$ 10.2 $\pm$ 0.2
ViterbiPlanNet	34.9 $\to$ 33.3 $\pm$ 0.4	25.4 $\to$ 22.8 $\pm$ 0.2	18.3 $\to$ 15.0 $\pm$ 0.2	14.1 $\to$ 10.8 $\pm$ 0.2
Improvement	+0.6 $\pm$ 0.5	+0.8 $\pm$ 0.4	+0.9 $\pm$ 0.5	+0.6 $\pm$ 0.3

Table 14: A single model is trained and evaluated using a unified PKG constructed from the union of all datasets. Gray values indicate the average performance of dataset-specific models, while arrows show the performance change when switching to a dataset-independent PKG.

Method [SR $\uparrow$ (%)]	$T=3$	$T=4$	$T=5$	$T=6$
SCHEMA [ 16 ]	29.55 $\pm$ 1.95	20.78 $\pm$ 1.94	13.91 $\pm$ 1.10	12.46 $\pm$ 1.57
ViterbiPlanNet	51.84 $\pm$ 0.95	48.14 $\pm$ 0.64	46.34 $\pm$ 0.49	41.98 $\pm$ 0.92
Improvement	+22.29 $\pm$ 2.17	+27.36 $\pm$ 2.04	+32.43 $\pm$ 1.21	+29.52 $\pm$ 1.82

Table 15: Evaluation on the egocentric instructional video dataset EgoPER [ 12 ] across planning horizons

T{=}3

–

6

Component	Name/Value
Visual Backbone	S3D [ 26 ]
Optimizer	Adam [ 10 ]
Learning Rate	$9\times 10^{-3}$
Dropout	0.20
Batch Size	256
Epochs	500

Table 16: ViterbiPlanNet training configuration.

Figure 12: LLM-Based sequence completion approach.

Figure 13: LLM + PKG sequence completion approach.

Figure 14: VLM-based sequence completion approach.

Graph-Based Planning

Graph-Based Planning represents states, tasks, or environments as nodes and edges to search for feasible, low-cost action sequences.

See all 99 papers

LAP: A Language-Aware Planning Model For Procedure Planning In Instructional Videos
Mar 10, 2026Lei Shi, Victor Aregbede, Andreas Persson +3
Örebro University, SE-701 82 Örebro, Sweden
RECIPE: Procedural Planning via Grounding in Instructional Video
May 19, 2026Luigi Seminara, Antonino Furnari, Lorenzo TorresaniVideo Understanding
Khoury College of Computer Sciences, Northeastern University, Boston · Department of Mathematics and Computer Science, University of Catania, Italy
Contrastive Energy Fields for Inference-Time Procedure Planning in Instructional Videos
Aug 17, 2026Mohamed Afham, Christoph Reich, Oliver Hahn +2Video Reasoning Inference-Time Optimization
TU Darmstadt · ELIZA · TU Munich +1

Mar 10, 2026J/K move · Enter open · S save

LAP: A Language-Aware Planning Model For Procedure Planning In Instructional Videos

Lei Shi, Victor Aregbede, Andreas Persson, Martin Längkvist+2

Örebro University, SE-701 82 Örebro, Sweden

Open paper AskPDF arXiv

Procedure planning requires a model to predict a sequence of actions that transform a start visual observation into a goal in instructional videos. While most existing methods rely primarily on visual observations as input, they often struggle with the inherent ambiguity where different actions can appear visually similar. In this work, we argue that language descriptions offer a more distinctive representation in the latent space for procedure planning. We introduce Language-Aware Planning (LAP), a novel method that leverages the expressiveness of language to bridge visual observation and planning. LAP uses a finetuned Vision Language Model (VLM) to translate visual observations into text descriptions and to predict actions and extract text embeddings. These text embeddings are more distinctive than visual embeddings and are used in a diffusion model for planning action sequences. We evaluate LAP on three procedure planning benchmarks: CrossTask, Coin, and NIV. LAP achieves new state-of-the-art performance across multiple metrics and time horizons by large margin, demonstrating the significant advantage of language-aware planning.

Abstract

Graph-Based Planning

Explore similar work

LAP: A Language-Aware Planning Model For Procedure Planning In Instructional Videos

RECIPE: Procedural Planning via Grounding in Instructional Video

Contrastive Energy Fields for Inference-Time Procedure Planning in Instructional Videos