COVER: Giving Video Temporal Grounders an Error Bar They Can Prove

Paper: 2608.07434 Authors: Aseel Mohamed, Rasul Khanbayov, Erchin Serpedin, Hasan Kurban Categories: cs.CV, cs.IR

The Gap

Video temporal grounding (“given this sentence, when does it happen in this video?”) has been an interval-regression problem since the beginning. 2D-TAN and its descendants score candidate spans; Moment-DETR / QD-DETR / UniVTG / MomentDiff regress or decode a start and an end; and lately people just prompt a video-LLM (Video-LLaMA, VTimeLLM, TimeChat) and parse timestamps out of the text. Every one of these returns exactly one interval. The whole field then reports R@1 at IoU 0.5 / 0.7 and mIoU, which are population averages: they tell you the model is right 55% of the time, and tell you nothing about which 55%.

Two things break here. First, the evaluation target itself is shaky. Re-annotate the same query-video pair with independent annotators and, as the paper reports, a large fraction of pairs get moments overlapping by less than half. So “IoU 0.5 against the single stored label” is measuring agreement with one annotator’s draw from a distribution, not distance from truth. Second, and worse for anyone deploying this, a wrong interval and a right interval look identical at inference. Confidence scores from these models are uncalibrated softmax or DETR class logits; temperature scaling or Bayesian heads would give you a number, but no guarantee attached to it.

The prior art on uncertainty is either (a) heuristic — ensemble spread, dropout variance, “predict a wider box when unsure” — with no coverage claim, or (b) conformal prediction applied to classification and regression, where the output is a label set or a scalar interval. Nobody had defined what a conformal prediction set even is when the label lives in the space of time intervals, nor handled the case where the model emits a per-frame relevance curve rather than an interval.

PROBLEM: grounders emit one interval, no reliability statement
    |          a wrong interval looks like a right one at deploy time
    v
OBSERVATION: re-annotation disagrees (IoU < 0.5 on many pairs)
    |          => the label is a DISTRIBUTION over intervals
    v
ASSUMPTION: calibration pairs and test pairs are exchangeable
    |
    v
METHOD: COVER == nonconformity score + quantile + widen
    |          post-hoc, black-box, no retraining
    +--> score A: two-sided boundary widening   (grounder emits interval)
    +--> score B: super-level-set on relevance  (grounder emits a signal)
    |
    v
THEORY: (i) how wide the certified region gets
    |   (ii) when coverage survives conditioning on event length
    |  (iii) how much slack when one video's moments break exchangeability
    v
EVIDENCE: 3 benchmarks x 5 grounders; realized coverage tracks 1 - alpha
    |          width exposes failure modes that mIoU hides
    v
CONCLUSION: change the output object -- ship a certified temporal region

The Increment

One sentence: Before, a grounder handed you a timestamp pair and you had to trust it; after, the same frozen grounder hands you a time region with a finite-sample, distribution-free promise that the true moment is inside it at least 1-alpha of the time.

Core Mechanism

COVER is split conformal prediction, ported to the interval-output world, and the port is where the actual work is. Phase one: take a held-out calibration set of labeled (query, video, ground-truth moment) triples. Run the frozen grounder on each. For every calibration example compute a single nonconformity number that says “how much would I have had to stretch this prediction for it to contain the truth?” Collect those n numbers, sort them, and take the ceil((n+1)(1-alpha))-th smallest. That one scalar q is the entire calibrated artifact. Phase two: at test time, run the grounder, stretch by q, ship the region. No gradients, no logits, no retraining, no access to the model’s insides — it works on an API that only returns “12.4s to 19.8s”.

The interesting design choice is the score family, because it determines the shape of the region. For grounders that emit an interval, the two-sided boundary-widening score asks how far each boundary missed in the direction that would have excluded the truth: roughly s = max(pred_start - gt_start, gt_end - pred_end), possibly normalized by predicted duration. This score is monotone in the widening amount, which is exactly the nested-set property conformal needs, so thresholding it yields the region [pred_start - q, pred_end + q]. Symmetric widening is a modeling decision, and the paper notes you can calibrate the two sides separately if start and end errors are asymmetric (they usually are — ends are fuzzier than starts).

For grounders that emit a per-frame or per-clip relevance signal r(t) — highlight-detection heads, retrieval similarity curves, attention over frames — you don’t have boundaries to widen. Here the score is built on the super-level-set: define the score from the relevance value at the true moment (e.g., s = 1 - r evaluated on the ground-truth span), calibrate q, and return the region { t : r(t) >= 1 - q }. Lowering the threshold monotonically grows the set, again giving nesting. The catch, and it’s a real one, is that a super-level-set need not be contiguous: you can get a union of disjoint time chunks. That is arguably more honest (the model genuinely thinks there are three candidate spots) but it complicates both the “region width” accounting and downstream consumption.

 CALIBRATION PHASE   (run once, on held-out labeled pairs)

  (query, video) --> [ ANY GROUNDER ] --> base output
                        (frozen, black box)     |
                                                v
   ground truth [g_s, g_e] -----> [ NONCONFORMITY SCORE ]
                                                |
      A:  s_i = max( g_s - p_s ,  p_e - g_e )   |   (interval output)
      B:  s_i = 1 - min r(t) over [g_s, g_e]    |   (signal output)
                                                v
                                  [ s_1 , s_2 , ... , s_n ]  sorted
                                                |
                        q = ceil( (n+1)(1-alpha) )-th smallest
                                                v
                                    q  ==  ONE SCALAR


 TEST PHASE   (per query, no labels, no retraining)

  (query, video) --> [ ANY GROUNDER ] --> [p_s, p_e]      or      r(t)
                                              |                    |
                                     widen by q                threshold
                                              v                    v
                              [ p_s - q , p_e + q ]     \{ t : r(t) >= 1 - q \}
                                              |                    |
                                              +---------+----------+
                                                        v
                                          CERTIFIED REGION  C(x)
                              P( true moment contained in C(x) ) >= 1 - alpha
                              width( C(x) ) == usable reliability signal

Think of the hurricane forecast cone. The National Hurricane Center’s model spits out a single predicted center track — that’s your base grounder’s interval, one confident line through a space of possibilities. Nobody publishes the bare line, because it’s wrong by construction. What they publish is a cone drawn around it, and the cone’s width is not a model output at all: it comes from an archive of past storms where they measured how far the actual track ended up from the forecast track. Take the 2/3 quantile of those historical misses and you get the two-thirds cone. That archive is COVER’s calibration set; the historical miss distances are the nonconformity scores; the quantile is q; the cone is the certified region.

The metaphor keeps paying. The cone is drawn on both sides of the track because the storm can veer either way — that’s the two-sided boundary-widening score, and if storms in this basin veer right more often than left you’d draw an asymmetric cone, which is per-side calibration. Some forecast products don’t give you a center track at all; they give you a spaghetti plot of ensemble members, and you shade the area where enough members pass through. That’s the super-level-set score: threshold a density instead of widening a line, and yes, sometimes the shaded area breaks into two blobs because the ensemble disagrees about which way the storm splits. The width bound in the paper is the observation that a cone is only useful if it’s narrower than the ocean — a bad base model forces a cone so wide the guarantee is technically true and practically vacuous. Length-conditional coverage is the known complaint that a cone calibrated over all storms under-covers the fast, erratic ones. And the exchangeability discussion is the fact that successive forecasts of the same storm are correlated, so treating them as independent archive entries inflates your effective sample size — in COVER’s case, multiple query-moments drawn from one video.

Key Concepts

• Split conformal prediction: Suppose you have a black-box predictor and you want an honest error bar without assuming anything about the data distribution or the model. Here’s the whole trick: on 500 examples the model has never trained on, write down how badly it missed each one. Sort those 500 miss magnitudes. The 450th one is a number q such that, historically, 90% of misses were smaller than q. Now on a fresh example, output “prediction plus or minus q”. Why is this valid rather than hand-waving? Because if the new example is statistically interchangeable with the 500 old ones, its miss magnitude is equally likely to land in any of the 501 slots of the sorted list, so the probability it exceeds the 450th is at most 10%. That’s it — a rank argument, no Gaussians, no asymptotics, no assumption that the model is any good. It’s finite-sample exact (with the ceil((n+1)(1-alpha)) correction) and works if your model is a neural net, a lookup table, or a coin flip. The cost: the guarantee is *marginal, averaged over all test examples, and it says nothing about any particular one.

• Nonconformity score, and why the interval case is not obvious: A score is just “how surprising is this label given this prediction?” For scalar regression it’s |y - yhat| and everyone agrees. For a *moment, the label is a pair (start, end) and the prediction is a pair, so there are many candidate scores: symmetric difference, 1 - IoU, max boundary error, sum of boundary errors. The constraint that narrows it down is nesting: as you loosen the threshold, the region you output must only grow, never shift or shrink. Max-boundary-error has this property (widen both ends by q), which is why COVER uses it; 1 - IoU does not correspond to any clean nested family of intervals, which is why you can’t just conformalize the metric everybody reports. This is the transferable lesson: conformalizing a structured output means finding a one-parameter family of nested sets that your score induces, and that family is your design space.

• Exchangeability, and how video breaks it: Exchangeability means you could shuffle your calibration and test examples and the joint distribution wouldn’t notice. Grounding datasets violate this in a specific way: Charades-STA and QVHighlights give you many queries per video, and moments from the same video share scene, lighting, actor, and annotator. If your calibration set contains 12 moments from a video and your test set contains 3 more from it, those 15 are correlated, your effective n is closer to 1 than 15, and the quantile you computed is optimistic. The clean fix is to split by video rather than by sample, and the paper’s contribution here is quantifying the coverage slack when you don’t — useful because in practice you often can’t get a clean video-level split.

Framework Shift

Before (mainstream grounding):        After (COVER):

video timeline                        video timeline
|____________________________|        |____________________________|
        [==pred==]                        [<=====  C(x)  =====>]
     [==gt==]                                  [==pred==]  core
                                            [==gt==]  inside == covered
IoU = 0.41  ->  logged as "miss"
                                      calibrate once on held-out set:
report: R@[email protected] = 55.2                    q = quantile of past misses
        mIoU    = 47.8
                                      report: coverage 0.90 (target 0.90)
at deploy time:                               mean width 8.4s / 31% of video
  output = [12.4s, 19.8s]
  reliability = ???                    at deploy time:
  a miss is invisible                   output = [9.1s, 23.1s], covered w.p. .9
                                        width small  -> act on it
one number per DATASET                  width huge   -> route to human
                                      one number per PREDICTION

From point prediction to set prediction, the core shift is that reliability stops being a dataset-level average you report in a table and becomes a per-instance quantity you can act on at deployment.

Expert Assessment

Problem choice: Real gap, and well chosen. The annotator-disagreement observation is the strongest card in the paper — if independent annotators overlap by less than 0.5 IoU on a large fraction of samples, then a decade of R@[email protected] leaderboard climbing has partly been fitting annotator idiosyncrasy, and that deserves saying out loud. Conformal prediction has been sweeping through CV one output space at a time (classification sets, detection boxes, segmentation masks, pose), so temporal grounding was going to get conformalized by someone this year; this paper got there with more task-specific theory than a minimal port would have. The honest framing is “timely and correct” rather than “surprising.”

Method maturity: Clever in the framing, mostly standard in the machinery. Split conformal with a monotone score is textbook; the increment is choosing the right score families and noticing that the two big classes of grounders need different ones. The super-level-set score is the more interesting of the two, because it’s the only route to certifying video-LLMs and highlight heads that don’t emit clean boundaries, and it generalizes beyond this task. What’s underplayed: the simpler baseline of “just report a wider interval scaled by predicted confidence” would fail to give a guarantee, but a *calibrated per-instance-normalized score (divide by predicted duration, or by an uncertainty estimate) is the standard efficiency fix in conformal regression, and I’d want to see how far that alone closes the gap to the fancier machinery. Also missing from the abstract: any treatment of adaptivity via conformalized quantile regression, which is the natural stronger competitor.

Experimental integrity: Three benchmarks and five grounders spanning trained localizers and black-box video-LLMs is the right breadth, and “realized coverage tracks the target” is the correct primary result — though it’s also the easy result. Split conformal covers by construction; if it didn’t, you’d have a bug or an exchangeability violation. So the paper’s real experimental burden is *efficiency, and that’s where I’d push hardest: what is the mean certified width as a fraction of video duration at alpha = 0.1? If Charades-STA’s certified regions average 40% of a 30-second video, the guarantee is honest but the product is a shrug. The abstract promises a width bound theoretically and “calibration exposes what point metrics hide” empirically, but I can’t tell from the abstract whether widths are competitive or merely reported. Second red flag to check: whether the calibration/test split is by video or by sample. The paper explicitly develops theory for the within-video dependence case, which suggests they know the issue — but it also means the headline coverage numbers may come from a sample-level split, which is mildly optimistic. Third: coverage is measured against the single stored label, which is exactly the annotator draw the introduction argues is unreliable. That’s not a contradiction (conformal covers the label-generating distribution, which is what you actually get at test time) but it does mean the guarantee inherits the noise rather than resolving it, and the paper should not let readers conflate “covers the annotation” with “covers the true event.”

Writing quality: Judging from the abstract, the theory got the attention and the motivation got compressed. The re-annotation study is the paper’s most quotable finding and it’s a single clause in the abstract — that should be a figure and a subsection with the protocol, the annotator count, and the IoU histogram, because it justifies the entire enterprise and is citable independently. Conversely, the three theory results are described so telegraphically (“bounds how large the certified region becomes, when coverage survives conditioning on event length, and how it degrades when moments from one video break exchangeability”) that a reader can’t tell if these are tight or cosmetic. The section I’d rewrite: a dedicated efficiency analysis that puts width, coverage, and mIoU on the same axes across all five grounders, so the claim “calibration exposes what point metrics hide” becomes a picture rather than an assertion.

Verdict: weak accept — correct, useful, and well-motivated, but the conformal machinery is off-the-shelf and the paper’s value hinges on efficiency numbers and the annotator study, both of which need more room than they appear to get.

Takeaways

Specific things worth stealing:

1. The nesting-constraint heuristic for conformalizing structured outputs. When you want a coverage guarantee over something that isn’t a scalar, don’t start from your favorite metric — start by asking “what one-parameter family of nested sets can I even build here?” That question kills 1 - IoU as a score and hands you max-boundary-error for free. Same recipe applies to bounding boxes (grow by q), masks (dilate by q), ranked lists (extend to top-k(q)), and code completions (accept top-p(q)).

2. The super-level-set score as a universal adapter. Any model that emits a dense relevance/score signal over a domain can be conformalized by calibrating a threshold on that signal, no matter what its final decoder does. This is how you certify a black-box you can’t get boundaries out of, and it transfers straight to anomaly detection (threshold the anomaly score), retrieval (threshold similarity), and audio event detection. Budget for non-contiguous output regions and decide up front whether your consumer can handle a union of chunks.

3. Split by cluster, not by sample. If your dataset has multiple labeled items per underlying entity (moments per video, sentences per document, patches per slide, readings per patient), sample-level calibration splits quietly inflate your effective n and give you optimistic quantiles. Split by entity. Cheap to do, and the failure is invisible if you don’t.

4. Width as a deployment-time router. The most practical output of this paper isn’t the guarantee, it’s that the certified region’s width is a per-instance reliability number you can threshold: narrow region, auto-accept; wide region, send to a human or fall back to full-video search. That’s a usable selective-prediction system built on top of a frozen model you don’t control.

5. The evaluation-critique framing. Before optimizing a metric further, measure the label noise floor by re-annotating. If independent annotators only agree at 0.5 IoU, chasing 0.7 IoU is partly overfitting to annotator style. This move is available in any task with subjective boundaries — summarization spans, entity boundaries, segmentation edges — and it’s usually more interesting than another point on the leaderboard.