acceptodds
Under review as a conference paper at ICLR 2027

NavIAgent: Coarse-to-Fine Active Frame Selection for Long-Form Video Understanding

14 views

Abstract

Long videos contain vast temporal search spaces, yet answer-critical visual evidence may be confined to a few brief moments. Under limited frame budgets, effectively locating such sparse evidence requires both broad temporal coverage and fine-grained temporal precision. This makes it challenging to search the long temporal horizon efficiently while preserving the resolution needed to capture decisive evidence. To address this challenge, we propose NavIAgent, a coarse-to-fine active frame selection framework that combines global temporal localization with fine-grained evidence acquisition. NavIAgent operates through two complementary stages. (1) At the coarse stage, a lightweight multimodal event graph indexes structured segment memories and rapidly localizes query-relevant candidate intervals. (2) At the fine stage, we deploy Strategic Memory Informed Lens for Evidence (Smile), an active agent optimized via reinforcement learning with dual-scale advantage and Free Energy-inspired intrinsic rewards. By formulating keyframe selection as a Partially Observable Markov Decision Process (POMDP), Smile performs discrete temporal navigation within candidate intervals and progressively acquires answer-relevant evidence from intermediate observations. Theoretical analysis shows that active policies have a more expressive hypothesis space than passive sampling, while unconstrained discrete navigation suffers from asymptotic temporal resolution dilution as video length increases, providing a formal motivation for our coarse-to-fine design. Extensive experiments on Video-MME, LongVideoBench, and LVBench across multiple vision-language backbones demonstrate consistent accuracy improvements of up to 11.6 percentage points, while substantially reducing visual frame consumption and inference latency. Our code is in the supplementary materials.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Long-Form Video Understanding, Active Perception, Multi-modal Agent, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_NbDtOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes NavIAgent, a coarse-to-fine framework for active frame selection in long-form video understanding. It first uses a multimodal event graph to retrieve relevant video segments. An RL-based agent called SMILE then selects informative frames within these segments. The authors introduce step-level rewards and dual-scale advantage estimation to improve active navigation. Experiments on three long-video benchmarks show improvements across multiple VLM backbones.

Critical strengths
  1. The paper addresses an important and meaningful problem in long-video understanding. The trade-off between global temporal coverage and fine-grained evidence localization is well motivated. The proposed coarse-to-fine framework is reasonable, and the overall method is clearly presented.
  2. The experimental results are promising. The method is evaluated on three benchmarks with multiple VLM backbones. Table 2 also shows that SMILE improves performance when the graph retrieval stage is fixed. The appendix provides additional training results and frame-budget analysis.
Critical weaknesses
  1. The proposed RL design is not sufficiently validated. Table 2 only evaluates SMILE as a whole, without isolating dual-scale advantage estimation or individual reward components. The reward contributions reported in Appendix E do not establish their effects on accuracy. Moreover, the evidence gain reward relies on a verifier score conditioned on the ground-truth answer. It is unclear whether this ratio reliably reflects evidence sufficiency. Comparisons with standard GRPO and targeted ablations would help establish the value of these design choices.
  2. The experimental gains are not fully explained, and some implementation details need clarification. The final VLM receives selected frames, graph memories, frame descriptions, and speech transcripts. It is unclear whether the baselines receive comparable information. The method also depends on coarse-stage retrieval, but the impact of retrieval errors is not analyzed. Besides, the supplementary code appears to differ from the paper in frame access, the navigation penalty in Eq. (9), and the evaluation dataset used during training. These differences raise questions about reproducibility.
Questions for authors
  1. How much does each reward component contribute to the final performance? Could the authors compare dual-scale advantage estimation with standard GRPO under the same settings?
  2. Could the authors explain why the ground-truth-conditioned verifier score ratio is a reliable measure of evidence gain? Is there any empirical evidence supporting this choice?
  3. Do the baselines receive the same auxiliary information as NavIAgent? How sensitive is the final performance to errors in coarse-stage retrieval?
  4. Could the authors provide a more complete efficiency analysis that includes graph construction and preprocessing costs?
  5. Is the supplementary code the same version used for the reported experiments? Could the authors clarify the differences in the RL implementation and explain how the held-out validation results were obtained?
9 comments

W1&Q1 RL Design Ablation

We thank the reviewer for this comment. We agree that Table 2 evaluates Smile as a whole, and we add the ablations that isolate the advantage estimator and each reward term below.


Experimental setup. All ablations use the same setup as the main training. And the two ablations change only the component under test, the balance ω\omega in Eq. 12 for the advantage and the corresponding coefficient in Eq. 9 for the reward, and keep every other hyperparameter fixed. The results are as follows.

Table 1 Ablation of the advantage estimator

VariantAccuracy(%)
trajectory-level advantage only, standard GRPO54.6
dual-scale, ω=0.5\omega=0.558.9

Table 2 Ablation of the reward terms

VariantAccuracy
full reward in Eq. 9 and Eq. 1058.9
without the CLIP novelty term, β=0\beta=057.6
without the belief gain, α=0\alpha=056.5
without the navigation cost, c=0c=058.4
terminal reward only52.4

Analysis of results. The dual-scale advantage raises the held-out NExT-QA accuracy from 54.6 to 58.9, so the step-level term is what makes the trajectory-level signal usable for credit assignment. On the reward side, removing either the belief gain or the CLIP novelty term lowers the accuracy by a visible margin, removing the navigation cost has a smaller effect, and keeping only the terminal reward gives the lowest accuracy at 52.4. The RL design therefore gains from the advantage estimator and the dense rewards together, rather than from the terminal reward alone.


We thank the reviewer for this meaningful comment. We will add the two ablations and the analysis above to the revision.

W1&Q2 Verifier Ratio Reliability

We thank the reviewer for this question. We first define the ratio from the belief update, then show how it evolves during training together with the success rate.


What the ratio is. The belief update in Eq. 10 has two inputs. The first is the counterfactual ratio rtr_t = p2p_2 / max(p1p_1, ϵeps\epsilon_{eps}), where p1p_1 = J(QQ, MtM_t) is the verifier's probability that the accumulated memory MtM_t is already sufficient to answer QQ, and p₂ = JJ(QQ, MtM_t, y∗y*) is the probability under the same memory when the ground-truth answer is also given as a reference. The second is the momentum coefficient ρ\rho that smooths the recursion. We write the ratio as rtr_t here to keep it distinct from ρ\rho. Both terms come from the same verifier and the same memory, so anything that makes the context generally plausible, such as an on-topic scene description, raises p1p_1 and p2p_2 together and leaves the ratio near one. The ratio departs from one only when the memory makes the specific answer y∗y^* more credible than an arbitrary answer would be, which is the diagnosticity of the evidence rather than its topical relevance.

To make it clear, we track the mean ratio at STOP and the accuracy on NExT-QA, evaluated every 30 steps with the protocol of Fig. 6 and Table 6. Table 3 reports the checkpoints at steps 30 to 390.

Table 3 Mean ratio at STOP and accuracy during training (NExT-QA)

Training step3060120180240300390
mean rtr_t at STOP0.840.870.890.860.931.191.31
accuracy (%)32.233.536.240.147.053.058.9

Analysis of results. Early in training the ratio stays below one, which means the memory at termination is not yet more supportive of the correct answer than of an arbitrary one, and the accuracy is correspondingly low. From step 300 onward the ratio moves above one while the accuracy reaches 53.0 and then 58.9, so the policy learns to stop on evidence that is diagnostic for the specific answer. The dip at step 180 shows that the trend is not monotone, which is expected because the ratio is a per-step signal and the accuracy is a trajectory-level outcome, but the two move upward together over training.


We thank the reviewer for this meaningful comment. We will add the tracking experiment and the analysis above to the revision.

W2&Q3 Information Parity and Retrieval Errors

We thank the reviewer for this question. We first clarify that the paper's Table 1 reports NavIAgent under the same no-ASR setting.


Same setting in the paper's Table 1 and Fig. 4. All numbers in the paper's Table 1 for NavIAgent are measured in the no-subtitle setting. Fig. 4 is the frame-budget ablation on Video-MME Long without subtitles, and the paper's Table 1 uses exactly this setting for NavIAgent and for baselines. As defined in Eq. 15, the context WW is the concatenation of the segment memories mim_i, the frame descriptions dkd_k and the transcripts UiU_i. The memories and descriptions are always present because they are produced by the coarse stage and by Smile during navigation, while the transcripts are optional and are added only when the speech tool is enabled.

Same-input comparison with RL-based selectors. To check that the gain is not produced by the extra information of the coarse stage, we compare the three RL-based selectors under a shared front-end. The event-graph retriever first localizes four candidate segments for each Video-MME Long question, and ReFoCUS[R1], TSPO[R2] and NavIAgent then select 8 frames per segment from the same candidate frames and are answered by the same frozen Qwen3-VL-4B under identical prompts. Under this identical input and budget, NavIAgent reaches 59.7, against 55.3 for ReFOCUS and 56.9 for TSPO, so the gain of 4.4 and 2.8 points comes from the selection policy rather than from the front-end. The results are as follows.

Table 4 Comparison with RL-based frame selection under a shared front-end and a shared answering budget

MethodBackboneVideo-MME Long
ReFoCUS [R1]Qwen3-VL-4B55.3
TSPO [R2]Qwen3-VL-4B56.9
NavIAgentQwen3-VL-4B59.7

Candidate set size. For the second question, we add a group of experiments. The coarse stage returns ∣CQ∣=k|\mathcal{C}_Q| = k candidate chunks, and kk controls how much of the video the fine stage may inspect and how much it costs. We vary k∈{2,4,8,16}k \in \{2,4,8,16\} on Video-MME Long and report the accuracy and the recall of the answer-bearing chunk.

Table 5 Effect of the candidate set size (Qwen3-VL-8B, Video-MME Long)

Candidate chunks kk24816
accuracy (%)57.260.961.461.6
recall of the answer-bearing chunk (%)78.591.294.696.1

Analysis of results. Reducing the candidate set from four chunks to two costs 3.7 points, and the recall drops from 91.2 to 78.5 percent, so in many questions the answer-bearing evidence is simply missing from the set. Enlarging the set to eight and sixteen chunks adds only 0.5 and 0.7 points, and the recall rises to 94.6 and 96.1 percent, which means the graph retrieval has already placed the answer-bearing chunk in the top four in most cases and the extra chunks mostly add distractors, at a proportional cost in frames and latency. We therefore keep k=4k=4, where the accuracy has nearly saturated and the cost is still acceptable.


We thank the reviewer for this meaningful comment. We will add the candidate set analysis and Table 4 and 5 to the revision.

Reference

[R1] ReFoCUS: Reinforcement-guided Frame Optimization for Contextual Understanding - CVPR 26' Findings

[R2] TSPO: Temporal Sampling Policy Optimization for Long-form Video Language Understanding - AAAI 26'

W2&Q4 Full Efficiency Accounting

We thank the reviewer for this comment. Following the reviewer's suggestion, we add a full accounting that includes the coarse stage. Our design targets the setting of one video with multiple questions, so we report the cost as a function of the number of questions asked about the same video, and we report both the wall-clock time and the computation, measured as the number of processed tokens. The statistics use a 41-minute video from Video-MME Long.

Table 6 Coarse stage and online inference cost

StageNavIAgent time (s)NavIAgent tokens (K)EGAgent time (s)EGAgent tokens (K)
Coarse stage513187598239
Online inference, per question111101149123

Table 7 Average cost per question as the number of questions grows

Questions per video1351015
NavIAgent, average time (s)624.0282.0213.6162.3145.2
EGAgent, average time (s)747.0348.3268.6208.8188.9
NavIAgent, average tokens (K)288.0163.3138.4119.7113.5
EGAgent, average tokens (K)362.0202.7170.8146.9138.9

Analysis of the results. The coarse stage of NavIAgent is cheaper than the graph construction of EGAgent, at 513 s against 598 s and 187K against 239K tokens. And the online cost is lower as well, at 111 s against 149 s and 101K against 123K tokens per question. Besides, because both costs are one-time, the average cost per question falls as the number of questions grows, from 624.0 s and 288.0K tokens at one question to 145.2 s and 113.5K tokens at fifteen questions for NavIAgent, and from 747.0 s and 362.0K tokens to 188.9 s and 138.9K tokens for EGAgent.

Our advantage. We acknowledge that NavIAgent has a higher latency than the non-agent methods, but the accuracy improvement is significant, and the two-stage design can use different models to reduce the cost. The paper's Table 3 reports 117 s per query for LongVideo-R1 and 51.3 s for VideoBrain, and both are one-shot methods. For 15 questions NavIAgent takes 145.2 s, so it is slower than both, and we do not claim otherwise. However, this is a widely known property of agent-based video understanding rather than an artifact of our design. For a one-hour video the stored graph is a JSON file of about 1.6 MB. In addition, Figure 5 shows that the accuracy is not sensitive to the capacity of the indexing model, so the graph can be built with a cheaper model, which lowers the construction cost further. Since NavIAgent also brings a substantial accuracy improvement over the base model, we believe the design offers a clear advantage for long-video question answering with repeated queries.


Thanks for the reviewer’s comment and all the clarifications and modifications will be synchronized in the latest version of the manuscript.

W2&Q5 Code Consistency

We thank the reviewer for this question. The supplementary code is the same version used for the reported experiments, which we explain here and will correct in the revision.


Frame access convention. The action is a relative jump of 3 to 20 percent of the current time window, and the policy observation consists of the normalized position, the normalized displacement and the number of frames in the current window as context. The semantics of an action are therefore independent of the window length. During training the window is the sampled timeline of the whole video, and during inference Smile navigates inside a retrieved candidate chunk, where frames are passed per chunk and positions are normalized to [0,1][0,1]. The phrase calibrated against the local candidate chunk in Section 3.3.1 describes the inference behavior, and we will state the training window explicitly.

Navigation penalty in Eq. 9. This point reflects an oversight on our side. The linear form ∣at∣\lvert a_t \rvert in the paper was our earliest definition of the navigation cost, while all experiments reported in the paper were run with the code, in which the cost is the squared energy form. The CLIP novelty term is implemented as the L2 distance between two L2-normalized CLIP embeddings, which matches Eq. 9. We will correct Eq. 9 in the paper immediately so that the equation matches the code, and we apologize again for this oversight.

Evaluation data. Smile is trained on the NExT-QA train split. The curves in Fig. 6 and the values in Table 6 are obtained on the NExT-QA val split, with an evaluation every 30 optimization steps. The evaluation inside the training script is used only for monitoring and is not the setting behind Fig. 6 or Table 6.


Thanks for the reviewer’s comment and we will fix it in the revised version and add more explanations.

Reviewer_yzy7OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes NavIAgent, a coarse-to-fine active frame selection framework for long-form video understanding. The framework first constructs a multimodal event graph using segment-level video descriptions to identify relevant temporal regions. Then, an RL-trained active exploration agent, Smile, performs sequential keyframe selection within the retrieved segments to provide visual evidence for downstream video question answering.

Critical strengths
  1. The paper addresses an important problem in long-form video understanding, particularly efficient keyframe selection under limited frame budgets.

  2. The reviewer finds the combination of event-graph-based retrieval and RL-based active frame selection potentially meaningful. The experimental results show consistent improvements across multiple video benchmarks and VLM backbones.

Critical weaknesses
  1. In Lines 54–62, the authors discuss the limitations of existing active perception methods without sufficient citations. Several existing works [R1, R2, R3] already explore coarse-to-fine temporal mechanisms to address the tradeoff between global coverage and local precision. The reviewer believes the authors should more thoroughly discuss these related works and clearly highlight the fundamental distinctions or niches of the proposed method rather than presenting these challenges as largely unresolved.

  2. The theoretical part in Se 3.1 is difficult to follow. The main conclusions can be summarized as: 1) active perception has a more expressive policy space than passive selection, 2) detecting short events becomes more difficult as video length increases under a fixed frame budget. However, these observations are already well understood, and it is unclear what additional insights these provide. More importantly, the connection between these theoretical results and the necessity of the proposed event graph and RL-based navigation is not sufficiently established. The reviewer believes this section is difficult to understand its motivation to the proposed method. The authors should clarify what readers are expected to learn from this analysis, as the current narrative somewhat hurts the readability of the paper.

  3. The proposed method shares a similar research objective with existing RL-based frame selection methods [R4, R5]. Although the reviewer thinks some distinctions in the proposed framework (event-graph-based retrieval and sequential active navigation), direct comparisons with these methods are missing. Moreover, NavIAgent requires additional video preprocessing to construct the event graph. The reviewer believes that quantitative comparisons under comparable computational budgets are important to establish the actual advantages of the proposed method over existing RL-based frame selection approaches.


[R1] VideoZoomer: Reinforcement-Learned Temporal Focusing for Long Video Reasoning - ICLR 26'

[R2] LensWalk: Agentic Video Understanding by Planning How You See in Videos - CVPR 26'

[R3] T*: Re-thinking Temporal Search for Long-Form Video Understanding - CVPR 25'

[R4] ReFoCUS: Reinforcement-guided Frame Optimization for Contextual Understanding - CVPR 26'

[R5] TSPO: Temporal Sampling Policy Optimization for Long-form Video Language Understanding - AAAi 26'

Questions for authors
  1. One critical concern is the inference latency reported in Tab. 3. As the reviewer understands it, the proposed framework requires video segmentation (w/ PySceneDetect), followed by generating segment-level descriptions and constructing the event graph before active frame selection. However, it is unclear whether these preprocessing costs are included in the reported inference latency. Algo. 1 also seems to assume a precomputed event graph. The reviewer believes that the end-to-end computational cost should be reported, as this raises concerns about the fairness of the current efficiency comparisons.

  2. Overall, the reviewer agrees that the paper addresses an important problem and that the proposed framework has some meaningful aspects. However, the distinctions from closely related approaches and the fairness of the computational comparisons remain unclear. The reviewer hopes the authors can clarify these concerns during the rebuttal.

6 comments

W1 Coarse-to-Fine Citations

We thank the reviewer for this comment. We add an explicit comparison against [R1], [R2] and [R3].


Coarse-to-fine control is established, and the instantiation is the contribution. VideoZoomer [R1] takes a coarse low-frame-rate overview and then zooms into high-frame-rate clips through a tool call. LensWalk [R2] lets a planner set the temporal scope and the sampling density of each observation in a reason-plan-observe loop. T* [R3] searches hierarchically from a coarse frame-time grid to a finer one. What is specific to NavIAgent is the two-level interface, namely what the coarse level stores and how the fine level decides where to look next.

The fine level is a learned sequential policy rather than a tool call. In [R1] the answering model also emits the zoom call, in [R2] the loop is training-free, and in [R3] the zoom is a search rule. Smile is a separate 2B policy that makes discrete jumps of 3 to 20 percent inside a candidate chunk, keeps a persistent memory (Eq. 8), stops on an evidence belief (Eq. 10), and is trained with dense step rewards. The answering model therefore never decides where to look.

The cost is paid once rather than per query. [R1], [R2] and [R3] re-scan the timeline for each question, while NavIAgent builds the graph once and serves every later question from it. The additional preprocessing therefore enters the end-to-end budget only once, which we quantify in Q1 below and in the response to the third weakness.

Reference

[R1] VideoZoomer: Reinforcement-Learned Temporal Focusing for Long Video Reasoning - ICLR 26'

[R2] LensWalk: Agentic Video Understanding by Planning How You See in Videos - CVPR 26'

[R3] T*: Re-thinking Temporal Search for Long-Form Video Understanding - CVPR 25'

W2 Section 3.1 Readability

We thank the reviewer for this comment and we clarify that our two propositions are indeed closely tied to the specific design of the method.


Proposition 1 protects the fine stage. The separation in Eq. 1 is between two kinds of frame selection. A passive policy chooses all of its TT frames from the question alone. An active policy chooses the next frame from what it has already seen. Smile is active because Eq. 7 builds the action from the persistent memory Mt−1M_{t-1} and the current frame ftf_t, and because Eq. 8 updates that memory after every step. A query-aware selector that scores all frames once from QQ cannot use what it has seen and stays in Πpass(T)\Pi_{\mathrm{pass}}(T) no matter how accurate its scorer is, so Eq. 7 and Eq. 8 are what put Smile in Πact(T)\Pi_{\mathrm{act}}(T).

Proposition 2 protects the coarse stage and the action-space calibration. Eq. 2 gives the miss probability for TT inspections over a timeline of length LL, and the bound grows with LL, so the fine stage has to navigate a short interval instead of the whole video. The chunking follows directly from this. The video is cut at shot boundaries by Eq. 18 and Eq. 19 with the minimum scene duration of the paper's Table 5, and the chunks average about one minute as reported in Appendix D.1. This length is not arbitrary.

Small steps and a bounded candidate set. The action set A={+3%,+5%,+8%,+12%,+20%, STOP} in Section 3.3.1 is defined relative to the candidate chunk rather than to the whole video. A 3% step on a one hour video moves 108 s and can skip a short event, while the same step on a 60 s chunk moves 1.8 s and stays shorter than the event. We agree that a percentage action space is a design choice, and Proposition 2 is the reason the percentages are tied to the chunk.

The two propositions are co-existent. They are not two independent remarks attached to the method. Each one rules out a degenerate design. Proposition 1 alone licenses a closed-loop agent that navigates the whole timeline, which is the family of global-navigation agents, and such a design satisfies the expressiveness condition while violating the horizon condition of Eq. 2. Proposition 2 alone licenses a passive selector inside a short window, which is the family of query-aware selectors, and such a design satisfies the horizon condition while remaining in Πpass(T)\Pi_{\mathrm{pass}}(T), where the separation of Eq. 1 does not apply. NavIAgent is the design that satisfies both conditions at once. The coarse stage maps LL to LlocalL_{\mathrm{local}} and the fine stage is closed loop on that local horizon, so the interface between the two stages, namely the chunk-calibrated percentage action space and the lossy four-field index, is where the two propositions meet. This interface is the specific contribution of the framework, and it is why we state the two theorems together.


We thank the reviewer again for this meaningful comment. We will add the explanations above to the main text and to the appendix, and we will explain this part in more detail in the revision.

W3: Comparison with RL Selectors

We thank the reviewer for this comment. We agree that a direct comparison with the RL-based frame selection methods [R4] and [R5] was missing, and we add it below.


How the three methods differ. ReFoCUS [R4] and TSPO [R5] both learn a frame selection policy with reinforcement learning and select the whole frame set in one pass, conditioning the choice on the query and, for ReFoCUS, on the frames chosen earlier in the same pass. NavIAgent also learns with RL, but the policy runs as a closed loop inside a retrieved interval. It decides the next frame from the memory of the frames it has already described (Eq. 7 and Eq. 8) and stops when the evidence belief is sufficient (Eq. 10), and it is preceded by an event graph that localizes the interval once per video. The two baselines answer which frames to take, while NavIAgent answers where to look next.

Comparison setting. Since NavIAgent contains a coarse retrieval stage that the baselines do not have, a naive end-to-end comparison would confuse the retrieval front-end with the frame-selection policy. We therefore isolate the selection stage with a shared front-end. For every Video-MME Long question, our event-graph retriever first localizes four candidate segments. Then all three methods receive the same candidate segments and the same candidate frame lists (1 FPS), and each method selects 8 frames per segment, yielding 32 frames in total. These frames are combined with the same graph-derived textual context and passed to the same frozen answering model, Qwen3-VL-4B, under identical prompts and decoding settings. ReFoCUS and TSPO use their publicly released Hugging Face checkpoints and are applied to each segment independently with a selection length of 8 frames, while NavIAgent uses its native budget of 8 frames per candidate segment. The results are as follows.

Table 1 Comparison with RL-based frame selection under a shared front-end and a shared answering budget

MethodBackboneVideo-MME Long
ReFoCUS [R4]Qwen3-VL-4B55.3
TSPO [R5]Qwen3-VL-4B56.9
NavIAgentQwen3-VL-4B59.7

Results. As shown in Table 1, under the same retrieval front-end, NavIAgent achieves 59.7 on Video-MME Long, outperforming ReFoCUS (55.3) and TSPO (56.9) by +4.4 and +2.8, respectively. Since the front-end and the answering budget are shared, the gain can only be attributed to the RL-trained frame-selection policy itself, demonstrating the advantage of our method under an identical computational budget.


Thanks for the reviewer’s comment and we will update this comparison in the revision.

Q1: Preprocessing in Latency

We thank the reviewer for this important question. We agree that Algorithm 1 assumes a precomputed graph and we report the end-to-end cost here.


Including the coarse stage in the statistics. Following the reviewer's suggestion, we add a full accounting that includes the coarse stage. Our design targets the setting of one video with multiple questions, so we report the cost as a function of the number of questions asked about the same video, and we report both the wall-clock time and the computation, measured as the number of processed tokens. The statistics use a 41-minute video from Video-MME Long.

Table 2 Coarse stage and online inference cost

StageNavIAgent time (s)NavIAgent tokens (K)EGAgent time (s)EGAgent tokens (K)
Coarse stage513187598239
Online inference, per question111101149123

Table 3 Average cost per question as the number of questions grows

Questions per video1351015
NavIAgent, average time (s)624.0282.0213.6162.3145.2
EGAgent, average time (s)747.0348.3268.6208.8188.9
NavIAgent, average tokens (K)288.0163.3138.4119.7113.5
EGAgent, average tokens (K)362.0202.7170.8146.9138.9

Analysis of the results. The coarse stage of NavIAgent is cheaper than the graph construction of EGAgent, at 513 s against 598 s and 187K against 239K tokens. And the online cost is lower as well, at 111 s against 149 s and 101K against 123K tokens per question. Besides, because both costs are one-time, the average cost per question falls as the number of questions grows, from 624.0 s and 288.0K tokens at one question to 145.2 s and 113.5K tokens at fifteen questions for NavIAgent, and from 747.0 s and 362.0K tokens to 188.9 s and 138.9K tokens for EGAgent.

Our advantage. We acknowledge that NavIAgent has a higher latency than the non-agent methods, but the accuracy improvement is significant, and the two-stage design can use different models to reduce the cost. The paper's Table 3 reports 117 s per query for LongVideo-R1 and 51.3 s for VideoBrain, and both are one-shot methods. For 15 questions NavIAgent takes 145.2 s, so it is slower than both, and we do not claim otherwise. However, this is a widely known property of agent-based video understanding rather than an artifact of our design. For a one-hour video the stored graph is a JSON file of about 1.6 MB. In addition, Figure 5 shows that the accuracy is not sensitive to the capacity of the indexing model, so the graph can be built with a cheaper model, which lowers the construction cost further. Since NavIAgent also brings a substantial accuracy improvement over the base model, we believe the design offers a clear advantage for long-video question answering with repeated queries. We will elaborate on our strengths and weaknesses in the revised manuscript.


Thanks for the reviewer’s comment and all the clarifications and modifications will be synchronized in the latest version of the manuscript.

Reviewer_79uZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes NavIAgent, a coarse-to-fine framework for frame selection in long-video question answering. In the coarse stage, the video is segmented by shot detection, each segment is summarized by a VLM into a structured memory record (when / where / who-what / summary), and segments are linked into an event graph with temporal, coreference and LLM-verified causal edges; a query planner then retrieves up to four candidate segments using graph search and speech-transcript search. In the fine stage, Smile, a Qwen3-VL-2B agent with LoRA trained by GRPO on NExT-QA, navigates within each candidate segment with forward percentage jumps and writes a short description of each visited frame; its step reward combines CLIP novelty, a belief gain computed by a Qwen3-VL-8B verifier with access to the ground-truth answer, and a jump penalty, with a dual-scale (trajectory and step) advantage. The final VLM answers from the selected keyframes, segment summaries, frame descriptions and aligned speech transcripts. Two propositions argue that active policies are more expressive than passive ones and that fixed-budget navigation misses short events as video length grows. On VideoMME, LongVideoBench and LVBench, NavIAgent improves over uniform 32-frame sampling with Qwen3-VL-4B/8B (e.g., 53.2 → 60.9 on VideoMME Long with Qwen3-VL-8B, using 25.2 keyframes on average) and, by smaller margins, with InternVL3.5-8B.

Critical strengths
  1. Intuitive coarse-to-fine decomposition with sizable gains. Separating global localization (event-graph retrieval) from local evidence acquisition (an RL-trained navigation agent inside short candidate segments) is a sensible way to trade off coverage and temporal precision, and the reported improvements over uniform sampling on Qwen3-VL-4B/8B are large across three long-video benchmarks.
  2. Released code and prompts. The supplementary material includes the implementation, and all prompt templates are given in Appendix F, which helps reproducibility.
Critical weaknesses
  1. The frame counts and the information given to the model are not comparable with the baselines. The "Frames" column in Table 1 counts only the keyframes passed to the final VLM. However, the coarse stage runs a VLM over every segment of the whole video to produce structured summaries and calls an LLM to build the graph edges, and the final context (Eq. 15, Algorithm 1) also includes segment summaries, frame descriptions and aligned speech (ASR) transcripts. The uniform-sampling baselines receive 32 frames only, and Fig. 4 is labeled "w/o sub", so it is unclear whether the baselines have access to any speech information. The comparison therefore conflates better frame selection with much more input information and much more computation. A baseline with the same transcripts, and NavIAgent without ASR, are needed to isolate the contribution of the method.
  2. The claim of substantially reduced inference latency is not supported. The abstract states that NavIAgent substantially reduces inference latency, but Table 3 reports 111 s per question, more than twice VideoBrain (51.3 s), and no latency is reported for the uniform-sampling baseline, which typically takes a few seconds. It is also not stated whether the 111 s includes building the event graph (described as "index-once"), nor whether the baseline runtimes were measured on the same hardware (the paper's experiments run on Ascend 910B NPUs) or taken from the original papers.
  3. The theoretical analysis gives little support to the design. Proposition 1 is trivial: an active policy can ignore its observations, so the passive class is contained in the active class by construction, and the strict separation uses a constructed distribution. The lower bound in Proposition 2, P_miss ≥ 1 − T·w_event / (L − w_event), holds for any policy that makes T point inspections, including NavIAgent itself. NavIAgent escapes this bound only because the coarse stage processes the entire video, outside the T-inspection budget, which is the same accounting issue as in W1. The "resolution dilution" part applies only to percentage-based action spaces, which is a design choice of the paper itself. The theory therefore does not motivate the coarse-to-fine design in a meaningful way.

Why these determine my recommendation. The main empirical claim, higher accuracy with fewer frames and lower latency, rests on a comparison in which NavIAgent processes the whole video and receives speech transcripts while the baselines do not, and the latency claim contradicts the paper's own Table 3. Together with a theoretical analysis that does not support the design, the evidence is not sufficient to establish the claimed advantages.

Questions for authors

Questions that could change my assessment

  1. Do the uniform-sampling and other baselines in Table 1 receive subtitles or ASR transcripts? What is the accuracy of NavIAgent without ASR, and of the baselines with the same transcripts?
  2. What is the total compute and wall-clock time per video including the coarse stage (segment captioning and graph construction), and how does it compare with uniform sampling on the same hardware? Were the runtimes of VideoBrain, LongVideo-R1 and EGAgent in Table 3 measured by you on the same hardware?
  3. Given that the bound in Proposition 2 applies to any policy with T point inspections, how does it specifically motivate the coarse-to-fine design rather than simply reflect that the coarse stage inspects the whole video?
5 comments

W1&Q1 ASR and Input Comparability

We thank the reviewer for this question. We first clarify that the paper's Table 1 reports NavIAgent under the same no-ASR setting.


Same setting in the paper's Table 1 and Fig. 4. All numbers in the paper's Table 1 for NavIAgent are measured in the no-subtitle setting. Fig. 4 is the frame-budget ablation on Video-MME Long without subtitles, and the paper's Table 1 uses exactly this setting for NavIAgent and for baselines. As defined in Eq. 15, the context WW is the concatenation of the segment memories mim_i, the frame descriptions dkd_k and the transcripts UiU_i. The memories and descriptions are always present because they are produced by the coarse stage and by Smile during navigation, while the transcripts are optional and are added only when the speech tool is enabled.

Discussion of Extra Information. Table 2 of the original paper retains graph retrieval and chunk memories while removing only active navigation. With Qwen3-VL-8B, disabling Smile raises the score to 55.3/48.2 versus 53.2/43.8 for uniform sampling, a gain of 2.1/4.4 points, and enabling Smile raises it further to 60.9/53.6, another 5.6/5.4 points. For Qwen3-VL-4B, the graph-side gain is 3.3/3.4 and the Smile gain is 5.6/6.1. These numbers show that most of the gain comes from active frame selection rather than extra textual information.

Same-input comparison with RL-based selectors. To check that the gain is not produced by the extra information of the coarse stage, we compare the three RL-based selectors under a shared front-end. The event-graph retriever first localizes four candidate segments for each Video-MME Long question, and ReFoCUS[R1], TSPO[R2] and NavIAgent then select 8 frames per segment from the same candidate frames and are answered by the same frozen Qwen3-VL-4B under identical prompts. Under this identical input and budget, NavIAgent reaches 59.7, against 55.3 for ReFOCUS and 56.9 for TSPO, so the gain of 4.4 and 2.8 points comes from the selection policy rather than from the front-end. The results are as follows.

Table 1 Comparison with RL-based frame selection under a shared front-end and a shared answering budget

MethodBackboneVideo-MME Long
ReFoCUS [R1]Qwen3-VL-4B55.3
TSPO [R2]Qwen3-VL-4B56.9
NavIAgentQwen3-VL-4B59.7

Additional ASR experiments. To measure what ASR contributes to each side, we run two extra configurations, uniform sampling with ASR and NavIAgent with ASR, on Video-MME Long and LongVideoBench with Qwen3-VL-4B. The uniform baseline receives the aligned transcripts of the same video. The results are as follows.

Table 2 Accuracy with and without ASR (%, 32 budget frames)

BackboneMethodASRVideo-MME LongLongVideoBench
Qwen3-VL-4BUniform samplingno50.752.5
Qwen3-VL-4BUniform samplingyes53.955.6
Qwen3-VL-4BNavIAgentno59.761.2
Qwen3-VL-4BNavIAgentyes62.663.4

Effect of ASR. Table 2 shows that ASR adds 2.2 to 3.2 points to both methods. The uniform baseline gains 3.2 points on Video-MME Long and 3.1 points on LongVideoBench, while NavIAgent gains 2.9 and 2.2 points on the same two benchmarks.


In the revision, we will state explicitly in the caption of the paper's Table 1 that no ASR is used, and we will add the ASR comparison above to the appendix.

Reference

[R1] ReFoCUS: Reinforcement-guided Frame Optimization for Contextual Understanding - CVPR 26' Findings

[R2] TSPO: Temporal Sampling Policy Optimization for Long-form Video Language Understanding - AAAI 26'

W2&Q2 Latency Claim and Preprocessing

We thank the reviewer for this comment. We agree that the abstract wording was not precise enough and we clarify that the latency reduction refers to graph-based agentic pipelines such as EGAgent, and that all timings are measured on the same NPU. The graph construction is a one-time cost, and it is amortized over the questions asked about the same video.


What the latency claim refers to. The claim in the abstract targets pipelines that, like ours, build a structured index and run multiple model calls per query. The matching reference point is EGAgent, which also adopts a graph-based retrieval pipeline. As the paper's Table 3 reports, NavIAgent takes 111 s per query against 149 s for EGAgent, a 25.5% reduction, while reaching 60.9% against 56.4% accuracy with 25.2 against 50 frames. Against LongVideo-R1, the per-query latency is 111 s against 117 s at 60.9% against 57.1%. The inference latency is therefore clearly lower than the graph-based baselines it is compared with, and it is obtained with fewer frames rather than more.

Including the coarse stage in the statistics. Following the reviewer's suggestion, we add a full accounting that includes the coarse stage. Our design targets the setting of one video with multiple questions, so we report the cost as a function of the number of questions asked about the same video, and we report both the wall-clock time and the computation, measured as the number of processed tokens. The statistics use a 41-minute video from Video-MME Long.

Table 3 Coarse stage and online inference cost

StageNavIAgent time (s)NavIAgent tokens (K)EGAgent time (s)EGAgent tokens (K)
Coarse stage513187598239
Online inference, per question111101149123

Table 4 Average cost per question as the number of questions grows

Questions per video1351015
NavIAgent, average time (s)624.0282.0213.6162.3145.2
EGAgent, average time (s)747.0348.3268.6208.8188.9
NavIAgent, average tokens (K)288.0163.3138.4119.7113.5
EGAgent, average tokens (K)362.0202.7170.8146.9138.9

Analysis of the results. The coarse stage of NavIAgent is cheaper than the graph construction of EGAgent, at 513 s against 598 s and 187K against 239K tokens. And the online cost is lower as well, at 111 s against 149 s and 101K against 123K tokens per question. Besides, because both costs are one-time, the average cost per question falls as the number of questions grows, from 624.0 s and 288.0K tokens at one question to 145.2 s and 113.5K tokens at fifteen questions for NavIAgent, and from 747.0 s and 362.0K tokens to 188.9 s and 138.9K tokens for EGAgent.

Our advantage. We acknowledge that NavIAgent has a higher latency than the non-agent methods, but the accuracy improvement is significant, and the two-stage design can use different models to reduce the cost. The paper's Table 3 reports 117 s per query for LongVideo-R1 and 51.3 s for VideoBrain, and both are one-shot methods. For 15 questions NavIAgent takes 145.2 s per question, so it is slower than both, and we do not claim otherwise. However, this is a widely known property of agent-based video understanding rather than an artifact of our design. For a one-hour video the stored graph is a JSON file of about 1.6 MB. In addition, Figure 5 shows that the accuracy is not sensitive to the capacity of the indexing model, so the graph can be built with a cheaper model, which lowers the construction cost further. Since NavIAgent also brings a substantial accuracy improvement over the base model, we believe the design offers a clear advantage for long-video question answering with repeated queries.

Thank you for the reviewer's comments. We will elaborate on our strengths and weaknesses in the revised manuscript.

W3&Q3 Theory-to-Design Support

We thank the reviewer for this comment. We agree that a theory needs to be meaningful in the concrete design. We clarify that our two propositions are indeed closely tied to the specific design of the method.


Proposition 1 protects the fine stage. The separation in Eq. 1 is between two kinds of frame selection. A passive policy chooses all of its TT frames from the question alone. An active policy chooses the next frame from what it has already seen. Smile is active because Eq. 7 builds the action from the persistent memory Mt−1M_{t-1} and the current frame ftf_t, and because Eq. 8 updates that memory after every step. A query-aware selector that scores all frames once from QQ cannot use what it has seen and stays in Πpass(T)\Pi_{\mathrm{pass}}(T) no matter how accurate its scorer is, so Eq. 7 and Eq. 8 are what put Smile in Πact(T)\Pi_{\mathrm{act}}(T).

Proposition 2 protects the coarse stage and the action-space calibration. Eq. 2 gives the miss probability for TT inspections over a timeline of length LL, and the bound grows with LL, so the fine stage has to navigate a short interval instead of the whole video. The chunking follows directly from this. The video is cut at shot boundaries by Eq. 18 and Eq. 19 with the minimum scene duration of the paper's Table 5, and the chunks average about one minute as reported in Appendix D.1. This length is not arbitrary.

Small steps and a bounded candidate set. The action {+3%,+5%,+8%,+12%,+20%,STOP} in Section 3.3.1 is defined relative to the candidate chunk rather than to the whole video. A 3% step on a one hour video moves 108 s and can skip a short event, while the same step on a 60 s chunk moves 1.8 s and stays shorter than the event. We agree that a percentage action space is a design choice, and Proposition 2 is the reason the percentages are tied to the chunk, so the choice is derived from the analysis rather than the analysis being arranged around the choice.

The two propositions are co-existent. They are not two independent remarks attached to the method. Each one rules out a degenerate design. Proposition 1 alone licenses a closed-loop agent that navigates the whole timeline, which is the family of global-navigation agents, and such a design satisfies the expressiveness condition while violating the horizon condition of Eq. 2. Proposition 2 alone licenses a passive selector inside a short window, which is the family of query-aware selectors, and such a design satisfies the horizon condition while remaining in Πpass(T)\Pi_{\mathrm{pass}}(T), where the separation of Eq. 1 does not apply. NavIAgent is the design that satisfies both conditions at once. The coarse stage maps LL to LlocalL_{\mathrm{local}} and the fine stage is closed loop on that local horizon, so the interface between the two stages, namely the chunk-calibrated percentage action space and the lossy four-field index, is where the two propositions meet. This interface is the specific contribution of the framework, and it is why we state the two theorems together.


We thank the reviewer again for this meaningful comment. We will add the explanations above to the main text and to the appendix, and we will explain this part in more detail in the revision.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.