Grounding Compositional Video Queries with Parallel-Scan Temporal Operators

Many questions people ask of long videos are not descriptions of a single moment. They are relations between moments: "the second time I opened the fridge after talking to the plumber," or "what I picked up between washing the knife and turning on the stove." Current video temporal grounding systems, which take a text query and a video and return the start and end time of the matching moment, encode such a query as one flat text vector and hope the video model untangles "second," "after," and "between" internally. We propose to break the query into a small tree of atomic sub-queries joined by temporal operators. A shared video backbone grounds each atom as a per-frame relevance curve. The operators are then computed as linear recurrences over the timeline, which means they can be evaluated with a parallel scan (the prefix-sum trick that lets linear recurrent networks train in logarithmic rather than linear depth). Composition therefore costs almost nothing extra, and the whole system stays end-to-end differentiable.

The core bet is that temporal relations like "after," "n-th time," and "while" have exactly the algebraic form that linear state-space models already exploit. They can be written as recurrences $h_t = a_t h_{t-1} + b_t$ whose coefficients come from atom relevance curves. That makes it possible to keep the proposal-free, linear-time efficiency of recent long-video grounders and still handle relational structure without enumerating pairs of candidate intervals, which would bring back quadratic cost.

Core Claim

A grounding model that sends decomposed atoms through a shared hybrid video backbone and combines them with scan-computable temporal operators will outperform flat-query grounders on relational and ordinal queries. It will match them on simple queries, and the number of sequential steps will grow with tree depth times $\log N$ (for $N$ frames) rather than with the number of model calls. The claim is falsifiable at a specific point: if a cheap symbolic composition of top-1 intervals from a flat grounder reaches the same accuracy, the differentiable scan operators are not the contribution.

What Prior Work Leaves Open

The closest system is HieraMamba. It builds a multi-scale "video pyramid" with bidirectional Mamba blocks for linear-time global context and a small local Transformer for short-range detail. It reports 25.66% average recall on Ego4D-NLQ and 18.05% on MAD-v2. Its query, however, is a single flat embedding, and its anchors are uniform rather than query-driven. MLVTG and SpikeMba also use Mamba-style linear scans for grounding and also treat the query flatly. These three papers supply our backbone design and our strongest baselines. None of them gives a query any internal structure.

Three lines of work do decompose structure, and each one stops short of what we need. WINNER parses the sentence into a phrase tree and aligns its nodes to pre-detected object tubes. This shows that hierarchical parsing resolves ambiguity when the scene contains several similar entities. But WINNER's tree is syntactic rather than temporal-relational, and it depends on detector proposals. Re-thinking Temporal Search for Long-Form Video Understanding (T*) splits a question into target and cue objects and searches keyframes in a logarithmic, tree-like way. Its own authors note that it cannot reason about duration or counting, because it looks for isolated "needle" frames. HiTeA builds its hierarchy over the video (event, scene, action) rather than over the query. In text QA, ProbTree and RoHT show that tree decomposition limits how far an early error spreads. They evaluate their nodes sequentially, by post-order traversal. We reuse their confidence-gating idea, but our nodes are evaluated in parallel over a shared video encoding.

Two results constrain the design. Simple linear attention language models balance the recall-throughput tradeoff (BASED) shows that pure linear recurrences trail hybrids that add small sliding-window softmax attention by 10.36 accuracy points on recall-heavy tasks. LoLCATs shows that linear attention smooths out sharp, concentrated attention patterns. Sharp boundaries are exactly what grounding needs, so the atom grounder must be a hybrid rather than pure Mamba. The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity places selective SSMs in constant-depth threshold circuits ($TC^0$). We do not claim our operators escape that class at any single level. The narrower point is that an explicit query tree supplies compositional depth from outside the model, instead of asking a fixed-depth video model to discover the nesting from a flat vector.

Research Program

The system has three parts.

The first part is a decomposer. A frozen language model rewrites each query into a tree. The leaves are atomic, visually groundable phrases ("open fridge," "talk to plumber"). The internal nodes come from a fixed vocabulary of temporal operators: after, before, while, between, n-th occurrence, and conjunction. A query with no relational structure becomes a single leaf, and the system then reduces to a flat grounder. Following ProbTree, the parser's log-likelihood is kept as a confidence score. At the root, a learned gate uses this score to mix the composed output with a flat-query path, so a bad parse degrades gracefully instead of failing.

The second part is a shared hybrid atom grounder. The video is encoded once, independent of the query, by a HieraMamba-style pyramid. Bidirectional linear recurrences provide global context, and a hardware-aligned sliding-window softmax attention of 64 to 128 frames, in the style of BASED, handles local sharpness. Each atom then passes through a light cross-modal head that outputs a per-frame relevance curve $p^{k}_t \in [0,1]$ for atom $k$ at frame $t$. All atoms in a tree are batched through this head together. As a result, the expensive video encoding is paid once per video no matter how complex the query is.

The third part is a set of scan operators. Each operator maps child curves to a parent curve through a linear recurrence. For "Y after X," define a "not-yet-happened" state $h_t = (1 - p^{X}_t)\, h_{t-1}$ with $h_0 = 1$. The parent curve is then

$$ s_t = p^{Y}_t \,\bigl(1 - h_{t-1}\bigr). $$

This is a prefix product, so it is associative and can be computed by a parallel scan in $O(\log N)$ depth. "N-th occurrence" uses a prefix sum of soft onsets, $c_t = c_{t-1} + \mathrm{relu}(p^{Y}_t - p^{Y}_{t-1})$, followed by a soft indicator that $c_t$ is near $n$. "While" is an elementwise product. "Between" combines an after-scan with a reversed before-scan. Every level of the tree is evaluated in one batched scan, so the sequential depth is roughly the tree depth times $\log N$. Finally, a proposal-free boundary regression head, as in ExCL, reads the root curve and outputs start and end times. No interval pairs are ever enumerated. Training uses the final boundary loss end-to-end. Where atom-level timestamps exist, we add auxiliary atom losses.

The analysis has two strands. We measure where the gains come from by query type, and we test the claim that soft scans carry uncertainty better than hard composition. The second test asks whether gains concentrate on queries where the atom curves have several peaks.

Data and Evaluation

None of the benchmarks in our file isolates relational queries, so we build a compositional split from existing annotations instead of collecting new ones. Within each Ego4D-NLQ video, and separately within each stitched sequence of TACoS clips, we pair annotated moments whose order is known. We then write templated and language-model-paraphrased queries such as "Y after X," "the n-th Y," and "Y between X and Z." Ground truth follows deterministically from the source timestamps, and every generated query is filtered for uniqueness within its video. A human-verified subset of about 1,000 queries guards against artifacts of the templates.

Standard evaluation uses Ego4D-NLQ (average recall, as reported by HieraMamba and DeCafNet), MAD-v2 (average recall), TACoS, and Charades-STA (Recall@IoU and mIoU). These show that the method does not regress on ordinary queries. Efficiency is reported as FLOPs, wall-clock latency on 100-minute MAD videos, and the count of sequential steps.

Baselines

The naive reference is the same hybrid backbone and boundary head fed the flat, undecomposed query embedding. It uses identical data, training schedule, and compute. This isolates the effect of the decomposition and the operators. Any gain on the compositional split must be measured against this model.

The strongest existing method is HieraMamba. It reports 25.66% average recall on Ego4D-NLQ and 18.05% on MAD-v2, while DeCafNet reports 24.44 on Ego4D-NLQ DeCafNet: Delegate and Conquer for Efficient Temporal Grounding in Long Videos. HieraMamba is the toughest competitor because it already combines linear global context with local attention and is efficient on hour-long video. The only thing it lacks is query structure. We will retrain it on our training mixture with the same features and the same hyperparameter-search budget as our model, and evaluate it on both the standard benchmarks and the compositional split. Beating it means two things. On the compositional split, we need a statistically significant gain across three seeds. On standard Ego4D-NLQ we must stay within seed noise of its reported 25.66%. The file has no reported HieraMamba number for TACoS, so on TACoS we compare against our own reproduction and against SpikeMba's reported mIoU of 35.81. On Charades-STA, SpikeMba reports mIoU 51.74 and MLVTG reports [email protected] of 38.7.

The most important ablation baseline is symbolic post-hoc composition. Each atom is grounded by the flat model, its top-1 interval is taken, and the operator is applied as a hard rule. A second ablation replaces the fixed scan operators with a small Transformer over the stack of atom curves. This tests whether the specific recurrence form matters or whether any learned composer works equally well. A third ablation removes the sliding-window branch from the atom grounder to test the BASED-style hybrid argument in the video setting. A fourth uses oracle parses on the compositional split, which separates errors in decomposition from errors in grounding. For the training-free route, HiTeA reports 8.12% mIoU on Ego4D-NLQ. It serves only as a reference point, because its supervision setting differs.

Why not just…?

Why not just give a flat grounder token-level cross-attention to the full query? Token-level attention lets the model see "after" and "second" as words. It does not give the model a counting state or an ordering state over the timeline, and the circuit-complexity result suggests that fixed-depth models must learn any such nesting implicitly. Still, this is a plausible threat on short, frequent patterns. Our naive baseline will use token-level cross-attention, not a pooled vector, so the comparison measures structure and not text resolution. If it matches us on the compositional split, the operators are unnecessary.

Why not just ground each sub-query separately and combine the top intervals with rules? This is the real threat, and it is cheap. It fails when an atom has several plausible peaks, as with repeated actions in TACoS or Ego4D, because committing to top-1 throws away the alternative that the relation would have selected. The soft scan keeps every peak weighted by its probability. The hard-versus-soft ablation settles this directly, stratified by how many peaks the atom curves have. If symbolic composition matches us even on multi-peak queries, we will report the contribution as decomposition alone.

Why not just prompt a large video-language model with chain-of-thought or use T*-style keyframe search? Linear chains carry early errors forward, which is the problem ProbTree and Is a Question Decomposition Unit All We Need? document. T* is designed around isolated keyframes and acknowledges failure on counting and duration. Reported search methods reach only 2.1% temporal F1 on its LV-HAYSTACK benchmark. Both approaches also need many sequential heavy-model calls on 100-minute videos. We will run a T*-plus-VLM pipeline on a subset of the compositional split under a matched GPU-hour budget, so that both accuracy and latency can be compared.

Why not just make the backbone deeper or add more global attention layers? Depth helps a little, but full attention on hour-long video runs into the memory failures reported by Video Mamba Suite, and extra layers do nothing to the flat query. We will train a flat model with matched parameter count and extra hybrid layers, so that our gain cannot be explained by capacity.

Decisive Checks

The idea survives if four things hold. On the human-verified compositional split, it beats both the flat token-level baseline and the retrained HieraMamba by a margin larger than seed variance. It beats hard symbolic composition specifically on queries with multi-peak atoms. It stays within noise of HieraMamba's 25.66% Ego4D-NLQ and 18.05% MAD-v2 average recall. And its latency on MAD stays within a small constant factor of the flat model, because video encoding is shared across atoms. Failing the second check would reduce the contribution to "decompose and use rules," and failing the first would mean that strong flat grounders already handle relational queries well enough.