Searching Long Videos for Interrupted Events

Most questions about long videos concern events that do not happen in one piece. Someone chops vegetables, answers the phone, and goes back to chopping. A person refills a glass four times over an hour. Current video-language models, meaning large language models that also take video frames as input, can afford to look at only a few dozen frames. They also treat every event as one continuous time span. When the relevant event is split into pieces, a model with a small frame budget either misses some pieces or merges them into one span that falsely covers the gaps. Either way, questions such as "was the stove on during every pause in chopping?" or "how many separate times did she refill the glass?" get answered by guessing.

We propose to change what a long-video search looks for. The search should look for a non-convex interval: a single event made of several disjoint pieces that share one identity. It should not look for a single best window. The question is compiled into a small set of constraints over these multi-piece events, using a forgotten 1990s algebra built for exactly this case. Those constraints then decide which parts of a coarse-to-fine tree over the video are worth spending frames on. The video model does only local perception on short clips. Bookkeeping about pieces, gaps and relations moves into a solver that is exact and cheap.

Core Claim

Our claim is that, under a fixed frame budget, searching a temporal tree for the set of fragments of an event beats searching for isolated windows. The fragments are tracked as an $n$-interval $I=\{[s_1,e_1],\dots,[s_n,e_n]\}$ with $e_i<s_{i+1}$, and branches are pruned using constraints derived from the question. The gain should appear on questions about interrupted or recurring events, and it should grow with the number of fragments $n$. Accuracy on ordinary single-span questions should stay the same.

The mechanism has three parts, each doing something a single-window search cannot:

  1. Stopping early. An existential question ("did X ever overlap Y") can stop at its first witness.
  2. Pruning whole subtrees. A universal or one-to-one question ("every X is followed by a Y", "the $k$-th X pairs with the $k$-th Y") can discard a subtree once a coarse, calibrated check says the event is absent from it.
  3. Repairing split fragments. Fragments that fall across a partition boundary are rejoined by testing whether adjacent pieces meet, that is, whether one ends exactly where the next begins.

If the video contains $N$ frames and the event has $n$ fragments, a well-calibrated absence check lets the search inspect on the order of $n\log N$ clips rather than scanning uniformly. This follows from the usual depth-times-branches argument for trees. The claim holds only if the check is calibrated, and that is what the experiments must test.

What Prior Work Does and Does Not Do

The symbolic foundation. Path Consistency in a Network of Non-Convex Intervals supplies the formal method. Morris, Shoaff and Khatib extend Allen's thirteen interval relations (before, meets, overlaps, during and so on) to sequences of disjoint pieces through four operators:

  • Always: the relation holds between all pairs of pieces.
  • Only: any relation that holds between pieces must come from the given set.
  • Sometimes: the relation holds for at least one pair of pieces.
  • Always-and-only: a one-to-one correspondence between occurrences.

They prove that consistency checking takes polynomial time in the number of events and in the correlation index. That work assumes a small, static, fully known network. We reuse its operators as the target language for compiling questions. We do not reuse its assumption that all intervals are given in advance: in our setting the intervals are discovered by spending frames.

Earlier representations of non-convex time. Weak Representations of Interval Algebras (Ligozat's formalization of multi-piece intervals) and A Representation for Collections of Temporal Intervals (Leban et al.'s slicing and dicing of calendars) are the representational ancestors. Neither touches perception.

The closest existing system. Iterative Zoom-In: Temporal Interval Exploration for Long Video Understanding is a best-first search over a tree of temporal intervals that uses the video model's own confidence to decide where to zoom. It motivates our proposal, because it shows adaptive tree search with 8 to 16 frames per step beats single-pass uniform sampling. It also sets the bar: it lifts Qwen-VL-2.5 from 51.5% to 57.9% on LongVideoBench and from 48.5% to 55.1% on VideoMME. Its search state, however, is one contiguous window, and it has no way to link pieces of one event found in distant branches. That is the gap we target.

Hierarchical indexes that assume events do not recur. Hierarchical Encoding of Sequential Data With Compact and Sub-Linear Storage Cost builds a tree index over video with logarithmic storage and lookup. It constrains our design by showing the danger of such trees: an early wrong turn at a high level sends the whole search into the wrong subtree, and every query maps to a single node. We address this with calibrated absence checks and with a small number of backtracking branches kept alive.

Activity grammars that break on interruptions. Ryoo and Aggarwal's grammar over Allen relations, Recognition of Composite Human Activities through Context-Free Grammar Based Representation, shows that interval logic can structure recognition of composite activities. Its parse collapses when a sub-action is interrupted, because every terminal is assumed to be one continuous span. Our representation is designed for exactly that case.

Evidence that models cannot do interval reasoning themselves. The diagnostic benchmarks explain why we move interval reasoning out of the network rather than hoping more frames fix it:

  • TimeBlind reports that frontier video models reach under 50% on paired temporal questions where humans reach 98.2%, with negligible gains from 8 to 32 frames.
  • Perfect Times finds a strong bias toward reading actions as completed.
  • COTEMPQA shows that, in text, framing time as explicit numeric intervals gains about 10.8 points.

We carry that last observation into video.

Research Program

1. Compiling questions. We will build a compiler from natural-language questions to constraints over multi-piece events. A language model is prompted with templates for the four operators, counting, and ordinary Allen relations. Its output is checked by a small grammar. When compilation fails, the system falls back to single-window search, so the method can never do worse than its base on questions it cannot parse.

2. Search. Search runs on a binary tree over the video timeline. Each node holds two summaries from a small, fixed number of frames:

  • a presence score for each event mentioned in the question;
  • an absence score, calibrated on held-out data by temperature scaling so that "absent at confidence $p$" is right about $p$ of the time.

The search state is a partial assignment of discovered fragments to each event's multi-piece interval. The expansion priority of a node is the expected change in the answer's truth value from resolving that node, as computed by the constraint compiler. This is where the non-convex operators matter:

  • For a "sometimes" constraint, the search stops once a witness is found.
  • For "always" and "always-and-only" constraints, the search must cover the video. It can prune subtrees whose absence score passes a threshold.

Adjacent leaf fragments are merged when the video model judges the boundary to be a meets relation, meaning the same action continues across the cut. This repair targets the boundary artifact that fixed partitions create.

3. Local perception. Leaves are short clips of 8 to 16 frames. There the video model reports fragment start and end times. Consistency is then checked with the Morris et al. procedure over the recovered network, which stays small because it contains only the question's events.

4. Benchmark construction. No existing benchmark in the file is organized around interrupted events, so we will build one in two forms.

  • Controlled version. We splice clips from Charades, whose boundaries were re-annotated for Perfect Times, into long synthetic timelines. The number of fragments $n$, the gap lengths and the distractor events are all set by design. To keep splice boundaries from giving away event boundaries, we also splice in distractor clips so that cuts carry no information.
  • Natural version. We use Ego4D timestamped narrations. Repeated verb–noun narrations are grouped into fragments, questions are generated from operator templates, and a sample is verified by people. Ego4D matters because recurring actions happen naturally there. Its natural-language grounding baseline reaches only 5.45% recall@1 at IoU 0.3, which shows how hard it is to find even one span.

Baselines

Uniform sampling. The naive reference is the same base model, Qwen-VL-2.5, answering from frames sampled evenly across the video. We run it at a matched frame budget and also at 256 frames. Beating it at matched budget is the minimum requirement. For comparison, LongVideoBench reports 66.7% for GPT-4o, and we include GPT-4o at 256 frames where access allows, as a ceiling for a large proprietary model.

Iterative Zoom-In. The strongest existing method is the tree search of Iterative Zoom-In. Its reported numbers are 57.9% accuracy on LongVideoBench and 55.1% on VideoMME with Qwen-VL-2.5. We re-run it with the same base model, the same per-step frame count, the same total frame budget and the same tree depth. Both systems get an equal hyperparameter-tuning budget on a shared validation split. No reported result was found on Lacuna for any method on non-convex event questions. Beating this baseline therefore means two things:

  • a clear accuracy gain on our benchmark at equal frames, growing with $n$;
  • staying within noise of its reported numbers on LongVideoBench and VideoMME, which contain mostly single-span questions.

Top-k Zoom-In. This is the most dangerous comparison. The same Zoom-In search returns its $k$ most confident leaves, with $k$ set to the true number of fragments as an oracle. The video model then answers from all of them. This isolates whether gains come from multi-piece search itself or merely from looking at several windows.

Ablations. Four ablations isolate the key ingredients:

  • keeping multi-piece search but replacing the solver with the video model reasoning freely over retrieved fragments;
  • keeping the solver but disabling constraint-driven pruning, so the search expands by confidence alone;
  • removing the meets repair;
  • removing absence calibration.

Why not just…?

Why not just feed the model more frames? TimeBlind reports negligible improvement from 8 to 32 frames and from 8B to 72B parameters on temporal structure. LongVideoBench does show gains of over 10% from 16 to 256 frames on long videos, but mainly on retrieval-style questions, and some open models got worse with more frames. This is a real threat for large proprietary models with long contexts. The 256-frame uniform baseline and the accuracy-versus-budget curves will show whether dense sampling closes the gap on multi-fragment questions. We expect it to fail on short fragments that fall between samples.

Why not just return the top few windows from Iterative Zoom-In? Confidence-ranked leaves tend to cluster around the single most salient fragment, because nearby windows share evidence. "Every occurrence" questions need coverage, not confidence. That said, this is the most likely competitor to match us, which is why we give it an oracle $k$. If it matches us on the natural Ego4D questions, the conclusion is that the solver and pruning add nothing beyond multi-window retrieval, and we would reduce the contribution to the benchmark and the compiler.

Why not just have the model output timestamps and do interval arithmetic in text, as COTEMPQA's math-style prompting does? This is exactly our "solver without multi-piece search" ablation run over uniform frames. Its weakness is upstream: the timestamps have to come from somewhere, and with a small uniform budget the fragments are never seen. The ablation separates better reasoning from better evidence gathering.

Why not just use a dedicated temporal grounding model to find all spans, then reason? Grounding one span in long egocentric video is already weak, at 5.45% recall@1 on Ego4D natural-language queries. Finding all $n$ spans compounds the misses. We will still include a grounding-then-solver pipeline on Ego4D so the comparison is measured, not assumed.

Proposed Experiments and Decisive Checks

Measurements. Along with answer accuracy we report fragment recovery and frames consumed. Fragment recovery is a set-matching temporal IoU between recovered and true multi-piece intervals, with a Hungarian assignment pairing recovered fragments to true ones.

Check 1: scaling with fragment count. On the controlled spliced benchmark, the gap over top-k Zoom-In should widen as $n$ goes from 1 to 6. At $n=1$ the two should be indistinguishable. A flat gap would falsify the core claim.

Check 2: accuracy per frame. Accuracy-versus-budget curves should show our method reaching the 256-frame uniform baseline with far fewer frames. If the gap closes as the budget grows, the method's value is specific to tight frame budgets, and we would report it that way.

Check 3: partition offsets. We shift the tree's partition boundaries by random offsets. With the meets repair enabled, accuracy variance should shrink. This directly tests the boundary-straddle problem.

Check 4: calibration. We measure how often a subtree is pruned while it actually contains a true fragment. If pruning is miscalibrated, universal questions will be answered wrongly as true. The absence-calibration ablation should show this failure clearly.

Check 5: transfer to real video. The Ego4D natural benchmark tests whether gains on spliced video survive real interruptions, where splice cues do not exist. LongVideoBench, VideoMME and the Allen-relation subset of TimeBlind confirm that treating everything as potentially multi-piece does not hurt ordinary questions.