- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proposes TimeGraph, a temporal graph memory framework for long-horizon video question answering, aiming to address the limitations of traditional frame-level retrieval methods in capturing entity continuity, state changes, and relation evolution across time. The proposed method organizes frame-level scene graphs into persistent entities, temporally bounded state and relation episodes, and explicit state transitions, thereby constructing a structured temporal memory. During question answering, TimeGraph retrieves relevant temporal subgraphs based on entity and temporal constraints and converts them into evidence to support downstream reasoning. Experiments conducted on three benchmarks, NAVQA, NExT-QA, and OpenEQA, demonstrate improvements of 6.2, 3.1, and 1.9 percentage points, respectively, over previously reported results, validating the effectiveness of explicit temporal modeling for long-video understanding and reasoning tasks.
Critical strengths
- The temporal graph memory design is innovative and well-motivated. The paper proposes TimeGraph, which organizes frame-level scene graphs into persistent entities, temporally bounded state and relation episodes, and explicit state transitions. This design effectively captures entity continuity and state changes across time, addressing the limitations of traditional frame-level retrieval methods in explicitly modeling temporal dependencies. It also provides a more structured memory representation for long-video understanding.
Critical weaknesses
- Strong Dependence on the Accuracy of Scene Graph Construction TimeGraph relies on frame-level scene graphs to construct temporal memory and establishes persistent entities and state transitions through cross-frame entity association. However, real-world videos often involve challenges such as occlusion, viewpoint changes, variations in object appearance, and errors in scene graph recognition.
- Insufficient Analysis of Computational Overhead and Scalability TimeGraph requires several processing steps, including scene graph extraction, cross-frame entity association, state and relation episode construction, and temporal transition detection. These operations may introduce substantial additional computational and storage overhead. As video length increases, the number of entities, relations, and state transitions may also grow, making temporal graph construction and maintenance increasingly complex.
- Insufficient Experimental Evidence to Fully Demonstrate the Advantages of the Proposed Method Although TimeGraph achieves performance improvements on NAVQA, NExT-QA, and OpenEQA, several aspects of the experimental evaluation deserve further consideration. First, the improvements over previously reported results are 6.2, 3.1, and 1.9 percentage points on the three benchmarks, respectively, with some of these gains being relatively modest. Second, while the proposed method demonstrates substantial improvements over frame-local lexical retrieval, comparisons primarily against relatively simple retrieval strategies may not be sufficient to establish the superiority of temporal graph memory over more advanced memory-based approaches. The authors should consider including comparisons with recent methods based on long-video memory, temporal retrieval-augmented generation, and dynamic knowledge graphs. Furthermore, these comparisons should be conducted under consistent settings, including the same visual features, backbone models, and inference budgets, to ensure a fair and convincing evaluation.
Questions for authors
1.If errors occur in the initial scene graphs or cross-frame entity matching is inaccurate, these errors may propagate into the temporal graph, negatively affecting subsequent retrieval and question-answering performance. The authors should further investigate the sensitivity of the proposed method to scene graph quality and entity association errors, and evaluate its robustness in complex real-world scenarios. 2.A key question is whether the additional computational cost of constructing temporal graphs is justified by the performance improvements compared with direct frame-level retrieval. The authors are encouraged to provide a more comprehensive analysis of graph construction time, storage requirements, retrieval latency, and overall question-answering efficiency, particularly through scalability experiments on ultra-long videos.
6 comments
Response to Reviewer Qr3b (Part 2)
2. Computational Overhead and Scalability of Temporal Graph Memory
Summary of Reviewer comment:
The current evaluation does not sufficiently characterize construction time, memory consumption, retrieval latency, or incremental maintenance. Could the authors provide measurements across different sequence lengths, clarify whether visual perception and QA inference are included, and discuss how construction costs can be amortized across multiple queries?
Response:
We agree that computational cost is important for assessing the practical applicability of temporal graph memory. We therefore profiled memory preparation, storage, question-time retrieval, and incremental maintenance separately.
(1) Temporal memory construction and storage.
We evaluated seven workloads with three repetitions each on a machine equipped with an Intel Core i7-14700HX, approximately 16 GB RAM, and an NVIDIA RTX 4060 Laptop GPU (8 GB). The local memory stage used one worker, four CPU threads, and CUDA-based text encoding.
Importantly, these measurements start from existing HSGG observations and cached visual features; they exclude upstream visual perception and HSGG extraction. Preparation includes temporal construction, canonicalization, projection, text encoding, indexing, and graph serialization. Preparation times are medians over three repetitions, while peak RSS is the maximum observed resident memory.
| Dataset and sampled frames | Preparation time (s) | Peak RSS (GiB) | Canonical graph and text index (MB) |
|---|---|---|---|
| NExT-QA, 21 | 3.272 | 1.284 | 4.48 |
| NExT-QA, 44 | 6.272 | 1.379 | 16.90 |
| NExT-QA, 68 | 7.877 | 1.429 | 22.05 |
| NAVQA, 205 | 44.361 | 1.724 | 93.24 |
| NAVQA, 409 | 84.756 | 2.060 | 156.06 |
| NAVQA, 613 | 160.774 | 2.524 | 236.49 |
| NAVQA, 817 | 308.199 | 3.133 | 319.21 |
The NExT-QA measurements correspond to three videos, while the NAVQA measurements use four progressively longer prefixes of the same sequence. At 817 sampled frames, the separately retained temporal intermediate graph occupies 612.39 MB, distinct from the 319.21 MB canonical graph and text index. RSS measures the resident memory of the complete measurement process.
For NAVQA, increasing the sequence length from 205 to 817 frames (3.99×) increases preparation time from 44.361 s to 308.199 s (6.95×). At 817 frames, temporal construction, canonicalization, and projection take 87.902 s, 118.481 s, and 48.782 s, respectively, accounting for approximately 82.8% of total preparation time. This indicates that structural processing is the dominant cost in the current implementation.
These measurements characterize scaling over the tested prefixes, rather than establishing performance on arbitrarily long videos. We have added the results in Table 18.
(2) Question-time retrieval latency.
We separately measured graph retrieval, vector-search probes, and visual-query processing. The latter includes text encoding, shard search, and JSON serialization.
| Scope | Measurement condition | Latency (ms) |
|---|---|---|
| NExT-QA graph-only retrieval | After loading | 21.92–68.44 |
| NAVQA vector-search probes | After loading | 8.10–34.94 |
| Combined visual-query components | Cold shard loading | 16,846 |
| Combined visual-query components | Warm shards | 84.36 |
The difference between cold and warm visual-query latency is primarily associated with shard loading. The warm measurement better reflects repeated queries after the visual index has been loaded.
These are local retrieval measurements, not end-to-end QA latency. They exclude upstream visual perception and HSGG extraction, as well as the external answering model's API latency. We will provide the component-level breakdown and tail-latency measurements in the supplementary material. The results are summarized in Table 20.
(3) Incremental temporal-graph maintenance.
We also measured graph refresh and append-patch application on successive prefixes of one NExT-QA video.
| Sampled frames | Graph refresh (ms) | Append patch (ms) | Combined maintenance (ms) |
|---|---|---|---|
| 17 | 190.90 | -- | -- |
| 34 | 484.60 | 87.55 | 639.79 |
| 51 | 663.43 | 106.62 | 770.05 |
| 68 | 874.10 | 142.46 | 1,025.68 |
The results demonstrate that updates can be applied to an existing temporal graph, although refresh remains a non-negligible cost as the sequence grows. Combined maintenance latency was measured independently and should not be interpreted as the arithmetic sum of the separately reported component measurements. We have clarified this protocol in Table 22.
(4) Cost amortization and practical implications.
Memory construction is performed before question answering and can be reused across multiple queries about the same video. Its effective per-query cost therefore decreases as the number of queries increases, while question-time graph retrieval and vector-search probes are substantially cheaper than rebuilding the memory.
Response to Reviewer Qr3b (Part 3-1)
3. Experimental Comparisons and Evidence for the Contribution of Temporal Graph Memory
Summary of Reviewer comment:
The current comparisons do not sufficiently isolate the contribution of temporal graph organization. Published results may involve different perception models, answerers, and evaluation protocols, while frame-local lexical retrieval may be an insufficient baseline. Could the authors provide controlled comparisons with consistent perception, retrieval, answering, and evidence budgets, including embedding-based retrieval, uniform-frame captions, and all frame-level scene-graph observations? The evaluation scope for NAVQA and Judge configuration for OpenEQA should also be clarified.
Response:
We agree that cross-paper comparisons alone cannot isolate the contribution of temporal graph memory. We therefore added controlled comparisons with shared perception, retrieval, and answering settings, and distinguish these experiments from supplementary comparisons with alternative evidence representations.
(1) Clarifying comparisons with published results.
On NExT-QA, TimeGraph achieves 66.73%, compared with the published results of LLoVi (67.7%) and VideoAgent (71.3%). We therefore do not claim to outperform these methods on the full validation set. Our main claim concerns the contribution of temporal graph organization under controlled settings, as evaluated below.
For NAVQA, our evaluation contains 139 non-position questions after excluding 71 position questions from the original 210. These comprise 67 binary, 33 free-text, 30 temporal, and 9 duration questions. Since the evaluation subsets and scoring protocols of published methods are not necessarily identical, we identify the scope of each comparison and avoid implying same-subset evaluation unless verified.
For OpenEQA, the original evaluation script specifies GPT-4-1106-preview as the Judge, which is no longer available. We therefore evaluated the same 1,636 saved answers using GPT-4.1-2025-04-14 as an alternative Judge, retaining the official prompts, reference-answer handling, extra-answer handling, score parsing, and normalization procedure. This is an alternative-Judge evaluation using the official scoring protocol, not an exact reproduction of the original Judge.
| Evidence configuration | GPT-5.6 Judge | GPT-4.1 Judge |
|---|---|---|
| Temporal graph memory | 48.92 | 53.41 |
| Shared visual evidence | 49.39 | 53.68 |
| Demand-aware visual evidence | 53.50 | 55.90 |
Demand-aware visual evidence achieves the highest score under both Judges. Under GPT-4.1, it improves over shared visual evidence by 2.22 points and over temporal graph memory by 2.49 points. We have explicitly reported the Judge configuration in Table 17.
(2) Controlled comparison with the same embedding retriever.
To isolate the contribution of temporal organization, we compared frame-level HSGG and TimeGraph using the same perception model, embedding retriever, answering model, QA template, observation scope, and evidence-budget policy.
| Setting | Specification |
|---|---|
| Perception model | LLaVA-OneVision-1.5-8B-Instruct |
| Answering model | GPT-5.6-luna |
| QA template | Same task-level template within each benchmark |
| Observation scope | NAVQA: question-specific window; NExT-QA: video; OpenEQA: episode |
| Evaluation sets | 139 NAVQA, 4,996 NExT-QA, 1,636 OpenEQA questions |
| Evaluation protocol | Same evaluator and scoring procedure within each benchmark |
The configurations differ in evidence representation: frame-level HSGG stores frame-local object, attribute, and relation records, whereas TimeGraph organizes observations into linked entity chains, temporal episodes, and transitions. Both use the same embedding retrieval protocol and matched evidence budget.
| Evidence configuration | NAVQA Acc. (%) | NExT-QA Acc. (%) | OpenEQA score |
|---|---|---|---|
| Frame-level HSGG + embedding retrieval | 20.14 | 49.82 | 33.11 |
| TimeGraph + embedding retrieval | 46.76 | 58.71 | 46.81 |
| Gain | +26.62 pp | +8.89 pp | +13.70 |
This is our primary controlled comparison. With the perception model, answerer, embedding retriever, and evidence budget held constant, TimeGraph consistently improves over frame-level HSGG retrieval. These results provide direct evidence for the benefit of explicitly organizing frame-level observations into temporal graph memory. We have added this comparison in Table 7.
Response to Reviewer Qr3b (Part 1)
Thank you for your constructive comments. We appreciate the reviewer’s concerns regarding scene-graph reliability, computational overhead, and the strength of the experimental comparisons. In response, we have added quantitative evaluations of entity association and graph-error sensitivity, profiled memory construction, retrieval, and incremental maintenance costs, and conducted controlled comparisons under consistent perception, retrieval, and answering settings. We have also clarified the limitations and scope of our method.
1. Reliability of Scene-Graph Construction and Cross-Frame Entity Association
Summary of Reviewer comment:
TimeGraph relies on frame-level scene graphs and cross-frame entity association, but errors in object detection, attribute recognition, relation extraction, and entity matching may propagate through temporal memory and affect downstream QA. The current manuscript does not sufficiently quantify association reliability, identity fragmentation, erroneous merging, or sensitivity to imperfect graph observations. Could the authors provide quantitative association evaluations and controlled graph-perturbation experiments?
Response:
We agree that errors in scene-graph observations and entity association can propagate into temporal memory and affect downstream QA. We conducted two complementary evaluations: an association-quality audit and controlled graph-perturbation experiments.
(1) Quantitative evaluation of entity association.
We randomly sampled 300 linked pairs and 300 unlinked candidate pairs from each dataset, resulting in 1,800 pairs. We manually assessed whether linked observations correspond to the same physical entity and whether unlinked candidates nevertheless refer to the same entity.
Linked-pair precision measures the proportion of sampled associations that correctly connect observations of the same entity; the erroneous-link rate is its complement. The last column measures the proportion of sampled unlinked candidates that actually refer to the same entity, rather than dataset-wide association recall.
The results show that association errors remain non-negligible, particularly on OpenEQA. We have added the evaluation in Table 13 and will clarify the candidate-pair sampling procedure, annotation criteria, and annotation agreement where available in the supplementary material.
(2) Sensitivity to controlled graph perturbations.
We further evaluated the impact of four types of graph errors on all 4,996 NExT-QA questions, keeping the answering and evaluation settings fixed. The unperturbed graph-only configuration achieves 60.53% accuracy (3,024/4,996).
At the 20% perturbation level, erroneous identity merges produce the largest accuracy drop (5.03 pp), followed by missing observations (4.73 pp). Identity fragmentation has a smaller effect (1.22 pp). This suggests that merging different entities can introduce contradictory attributes and relations into a single entity history, whereas fragmentation primarily distributes evidence across separate chains.
These experiments are controlled sensitivity tests, not estimates of naturally occurring graph-error rates. We have added the perturbation units, sampling procedure, and randomization protocol in Table 12 of the revised manuscript.
(3) Error propagation and limitations.
We also analyzed an OpenEQA failure case in which an incorrect
painting above television'' relation became the highest-ranked evidence and led all three configurations to answerpainting''. The revised appendix provides an evidence trace covering the erroneous relation, its retrieval priority, the evidence passed to the answering model, and the resulting answers from the three configurations.We further clarify that entity association is primarily performed between adjacent sampled observations. The current implementation does not provide dedicated global re-identification after long-term occlusion. Thus, the resulting representations should be understood as temporally linked entity chains, rather than guaranteed globally persistent identities. We have revised the relevant descriptions and explicitly acknowledged long-term occlusion and identity recovery as limitations.