Instructional videos come with free supervision: the narrator says "now pour the milk," and a model can learn what pouring milk looks like without anyone drawing boxes or marking timestamps. The trouble is that much of what narrators say is never shown on screen. They greet viewers, read out sponsor segments, describe steps they skip, and make filler remarks like "okay, so." Current methods for aligning narration to video have to decide, sentence by sentence, whether the sentence matches some stretch of video or should be thrown away. They make that decision with a hand-tuned "drop cost," a fixed penalty for discarding a sentence. We propose to replace that knob with a quantity that has a probabilistic meaning: how much better a sentence matches this clip than it matches a typical clip from anywhere in the corpus.
Computing "a typical clip from anywhere" is a partition-function problem. The partition function is the normalizing sum, here over every video clip in the dataset, that turns raw match scores into probabilities. It is too large to compute during training. In-batch estimates are badly biased for generic phrases, because such phrases match almost everything. We will learn a small network that predicts this normalizer for each sentence, in the style of AmorLIP. We will then use the normalized score inside an exact dynamic-programming sum over all monotone alignments, including alignments that leave sentences unmatched. The result is a posterior probability that each narration sentence is grounded. That posterior does three jobs at once: it localizes steps, it weights the contrastive training signal, and it is checkable against held-out annotations.
Core Claim
Let $e(s,v)$ be the learned similarity between narration sentence $s$ and video clip $v$. Let $\log Z(s) = \log \mathbb{E}_{v \sim \text{corpus}}[\exp e(s,v)]$ be the log-partition function of that sentence over the whole clip distribution. The normalized score
$$ r(s,v) = e(s,v) - \log Z(s) $$
is a pointwise mutual information. It is positive exactly when clip $v$ is more compatible with $s$ than an average clip is. We use $r$ as the emission score in an alignment lattice where each sentence either attaches to a clip or goes to a null state with score $0$. The null score is fixed at $0$ rather than tuned, because a score of $0$ is the neutral value of a log-ratio. The probability that sentence $s_j$ is grounded is then a ratio of two lattice partition functions:
$$ P(\text{grounded}_j) = 1 - \frac{\mathcal{Z}_{\text{lattice}}(s_j \to \text{null})}{\mathcal{Z}_{\text{lattice}}}. $$
Here $\mathcal{Z}_{\text{lattice}}$ is the sum of exponentiated path scores over all monotone alignments with drops. The numerator restricts that sum to paths that drop $s_j$. A forward-backward pass computes both exactly.
The claim is that two partition functions should be handled differently. The intractable one, over all clips for a sentence, is what makes the drop decision meaningful, and it should be amortized at the dataset level. The tractable one, over alignments within a video, should be summed exactly rather than replaced by a single best path. The specific prediction is that the gain should concentrate on generic and off-topic narration, where in-batch normalization is most biased, and should be largest on grounding calibration, not only on retrieval.
How This Relates to Existing Work
Three papers motivate the gap. MIL-NCE (Miech et al.) absorbs speech-to-video lag by treating 3–5 neighboring narrations as a bag of possible positives. It normalizes only over the minibatch and has no way to reject a bag that is entirely ungrounded. StepFormer aligns learned step slots to narration with Drop-DTW, which can discard sentences. Its drop cost is a heuristic hyperparameter, and its alignment is a single best path. NUCLR argues that a uniform in-batch denominator leaves a permanent error when data are non-uniform. It fixes this with a per-sample popularity variable for static images. In video, popular content such as talking heads and hands on counters is even more skewed than in static images, so this argument applies with more force.
Two papers supply the method. CDFL (Jun Li et al.) shows that summing energies over all transcript-consistent paths with forward logadd beats committing to one path. It reaches 50.2% mean-over-frames on Breakfast versus 45.7% for D3TW. However, CDFL assumes a clean, ordered transcript and has no null state. We borrow its exact path summation and add drops whose cost comes from the corpus normalizer. AmorLIP predicts the image-text partition function with small Random Fourier Feature networks. It reports 29.93% ImageNet zero-shot versus 25.26% for CLIP on CC-12M, at under 0.3% overhead. We reuse that amortizer, but use its output for a different purpose: AmorLIP feeds the predicted normalizer into a contrastive denominator, while we use it to set an alignment decision threshold. NUCLR's per-index state would cost one float per dataset item. We avoid that because sentences in a streaming video corpus are formed on the fly, and a predictor conditioned on the text embedding generalizes to unseen sentences.
Two lines constrain the design. Cali-NCE (Cali-NCE) down-weights mismatched pairs using a separately trained correspondence classifier. That is the closest functional competitor, but its weights have no normalization semantics and come from a second network that can itself absorb noise. The estimator theory of Jolicoeur-Martineau et al. and Yu et al. warns that log-normalizer estimates can have exploding finite-sample variance. For that reason we validate the amortized $\log Z(s)$ directly against brute-force estimates rather than trusting it implicitly.
Research Program
We will build a three-part model. The first part is a video and text encoder producing $e(s,v)$. For the main study it runs on frozen features, as StepFormer does, so that comparisons isolate the objective; a later end-to-end run tests whether the conclusions survive.
The second part is the normalizer network. It maps a sentence embedding to $\log Z(s)$ and is trained by regression onto log-mean-exp targets computed over a large rolling memory bank of clips drawn from across the corpus. Its parameters update on a slower timescale than the encoder.
The third part is the alignment layer. It is a banded monotone lattice over the sentences and clips of one video, with null states for both unmatched sentences and unmatched clips. The training loss is the negative log of the lattice partition function for the true video, contrasted against lattices pairing the same narration with other videos. This yields a sequence-level contrastive objective in which ungrounded sentences contribute almost nothing, because their posterior mass sits in the null state.
The analysis has three parts. The first is a calibration study. For a held-out set of sentences we compute $\log Z(s)$ exactly over a bank of one million clips, which is affordable at evaluation time with frozen features. We then measure the amortizer's error as a function of how generic the sentence is, using its frequency of near-duplicates as the measure. The second compares in-batch normalization against amortized normalization on exactly those generic sentences. The third looks at failure modes, specifically narration that is reordered relative to the video, which a monotone lattice cannot represent. We will report how often this occurs, using annotated steps in CrossTask as a reference.
Baselines
The naive reference point is MIL-NCE trained on the same HowTo100M subset and features, with its 3–5 narration window. It is the default training recipe, and Miech et al. report YouCook2 zero-shot R@10 of 51.2% and UCF-101 accuracy of 91.3% with end-to-end training. With frozen features we will rerun it rather than quote those numbers.
The strongest existing method for the localization question is StepFormer with Drop-DTW. StepFormer reports 28.3% F1 on CrossTask step localization. We will run it on the identical frozen features and data, and give its drop-cost percentile the same tuning budget we give our only free hyperparameter, the lattice band width. Beating it means exceeding its rerun F1 on CrossTask by more than the seed-to-seed spread across three seeds, and also exceeding it on ProceL, for which no reported result was found on Lacuna.
For noise-weighted training, the strongest competitor is Cali-NCE's correspondence-classifier weighting, trained on the same data. Cali-NCE reports MSR-VTT zero-shot R@1 of 13.1 versus 10.1 for its uncalibrated baseline. Beating it means higher MSR-VTT and YouCook2 retrieval at matched compute, plus better grounding AUROC.
Two ablations isolate the key ingredients. The first replaces the amortized $\log Z(s)$ with an in-batch log-mean-exp, keeping everything else fixed. This tests whether dataset-level normalization matters. The second replaces the forward sum with Viterbi, a single best path, keeping the normalizer. This tests whether exact marginalization over alignments matters. If the first ablation matches the full model, the partition-function component adds nothing, and we will say so.
Why not just…?
Why not just tune Drop-DTW's drop cost? This is the real threat. A per-video percentile threshold is a crude per-video normalizer and might capture most of the benefit. The decisive comparison is stratified by how generic the sentence is. A per-video threshold cannot tell "okay so" in a video full of talking from a real step. A per-sentence corpus normalizer can. If tuned Drop-DTW matches us on the generic-narration stratum, the idea reduces to a reparameterized threshold, and we will report it that way.
Why not just filter the data first with a captioner, as in Sieve or CapFilt? Sieve and BLIP's CapFilt score each pair in isolation with a heavy captioning model. That cannot handle narration that is grounded, but a few seconds away from its timestamp, which is the dominant failure in instructional video. These pipelines also carry their captioner's own hallucinations. We will run Sieve-style pruning on HowTo100M clips as a preprocessing baseline under equal total compute, counting captioning cost.
Why not just use bigger MIL windows or bigger batches? Miech et al. found that windows wider than roughly 10 seconds hurt, because the bag fills with irrelevant actions. NUCLR argues that a larger uniform in-batch denominator still leaves a non-vanishing error. We will nonetheless include a 4× batch MIL-NCE run. If it closes the gap, the bias in in-batch normalization is smaller in practice than claimed.
Proposed Experiments
Pretraining uses HowTo100M narrated videos with frozen features. Evaluation covers four areas. Step localization is measured on CrossTask (F1 and recall, against StepFormer's 28.3% F1 and Zhukov et al.'s 22.4% recall from Zhukov et al.), on ProceL, and on COIN. Zero-shot retrieval is measured on YouCook2 and MSR-VTT.
The most direct test is grounding detection. On CrossTask and YouCook2, a narration sentence counts as grounded if its timestamp window overlaps an annotated step. We report AUROC and expected calibration error of $P(\text{grounded})$ against Cali-NCE's confidence and Drop-DTW's binary drop decision.
The robustness test moves to the clean transcript setting of CDFL. On Breakfast, where CDFL reports 50.2% mean-over-frames, we corrupt the training transcripts by randomly deleting steps, inserting steps from other tasks, and swapping neighbors, at rates of 10% to 50%. CDFL has no valid path when a transcript is wrong, so the prediction is that it degrades sharply while our lattice degrades gracefully.
Two results would decide the question. The first is whether the amortized-versus-in-batch ablation shows a gap that grows with sentence genericness. The second is whether the amortizer's $\log Z(s)$ tracks the brute-force million-clip estimate closely enough that the drop decision rarely flips. If both hold, the partition function is doing real work. If neither holds, the contribution reduces to soft Drop-DTW.
References
- AmorLIP: Efficient Language-Image Pretraining via Amortization
- End-to-End Learning of Visual Representations From Uncurated Instructional Videos
- StepFormer: Self-supervised Step Discovery and Localization in Instructional Videos
- On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning
- Weakly Supervised Energy-Based Learning for Action Segmentation
- Cali-NCE: Boosting Cross-modal Video Representation Learning with Calibrated Alignment
- A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation
- ``Noisier'’ Noise Contrastive Estimation is (Almost) Maximum Likelihood
- SIEVE: Multimodal Dataset Pruning Using Image Captioning Models
- BLIP: Bootstrapping Language-Image Pre-training for Unified Vision-Language Understanding and Generation
- Cross-Task Weakly Supervised Learning From Instructional Videos.