acceptodds
Under review as a conference paper at ICLR 2027

TimeGraph: Temporal Graph Memory for Long-Horizon Video Question Answering

Abstract

Long-horizon video question answering requires reasoning over information distributed across distant observations, where entities may persist while their states and relations change over time. Retrieving individual frames does not explicitly preserve these temporal dependencies, leaving entity continuity, temporal extent, and state changes to be reconstructed during answering. We propose TimeGraph, a temporal graph memory that organizes frame-level scene-graph observations into persistent entities, temporally bounded state and relation episodes, and explicit transition boundaries on a shared time axis. Given a question, TimeGraph uses entity and temporal constraints to retrieve a relevant temporal subgraph and convert its structure into answer-relevant evidence. We evaluate TimeGraph on NAVQA, NExT-QA, and OpenEQA, where it improves over previously reported results by 6.2, 3.1, and 1.9 points, respectively. Compared with frame-local lexical retrieval, temporal graph memory further improves performance by 35.25, 13.39, and 21.14 points across the three benchmarks. Further analysis shows that organizing visual evidence according to question demand can provide additional gains, although the effect varies across datasets and question types. These results demonstrate the value of establishing explicit temporal structure before question-time retrieval for long-horizon VideoQA.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Long-Horizon Video Understanding, Video Question Answering, Temporal Graph Memory, Structured Visual Memory, Temporal Reasoning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Qr3bOpenReview ↗
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
  1. 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
  1. 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.
  2. 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.
  3. 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
AuthorsOpenReview ↗

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.

DatasetLinked-pair precision (%)Erroneous-link rate (%)Same-entity proportion among sampled unlinked candidates (%)
NAVQA82.3317.6711.67
NExT-QA88.6711.3317.67
OpenEQA76.3323.679.33

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).

Perturbation10% accuracy (correct / total)20% accuracy (correct / total)Drop at 20% (pp)
Missing observations58.31 (2,913/4,996)55.80 (2,788/4,996)4.73
Relation errors59.31 (2,963/4,996)58.01 (2,898/4,996)2.52
Identity fragmentation60.01 (2,998/4,996)59.31 (2,963/4,996)1.22
Erroneous identity merges58.01 (2,898/4,996)55.50 (2,773/4,996)5.03

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 answer painting''. 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.

AuthorsOpenReview ↗

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 framesPreparation time (s)Peak RSS (GiB)Canonical graph and text index (MB)
NExT-QA, 213.2721.2844.48
NExT-QA, 446.2721.37916.90
NExT-QA, 687.8771.42922.05
NAVQA, 20544.3611.72493.24
NAVQA, 40984.7562.060156.06
NAVQA, 613160.7742.524236.49
NAVQA, 817308.1993.133319.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.

ScopeMeasurement conditionLatency (ms)
NExT-QA graph-only retrievalAfter loading21.92–68.44
NAVQA vector-search probesAfter loading8.10–34.94
Combined visual-query componentsCold shard loading16,846
Combined visual-query componentsWarm shards84.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 framesGraph refresh (ms)Append patch (ms)Combined maintenance (ms)
17190.90----
34484.6087.55639.79
51663.43106.62770.05
68874.10142.461,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.

AuthorsOpenReview ↗

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 configurationGPT-5.6 JudgeGPT-4.1 Judge
Temporal graph memory48.9253.41
Shared visual evidence49.3953.68
Demand-aware visual evidence53.5055.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.

SettingSpecification
Perception modelLLaVA-OneVision-1.5-8B-Instruct
Answering modelGPT-5.6-luna
QA templateSame task-level template within each benchmark
Observation scopeNAVQA: question-specific window; NExT-QA: video; OpenEQA: episode
Evaluation sets139 NAVQA, 4,996 NExT-QA, 1,636 OpenEQA questions
Evaluation protocolSame 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 configurationNAVQA Acc. (%)NExT-QA Acc. (%)OpenEQA score
Frame-level HSGG + embedding retrieval20.1449.8233.11
TimeGraph + embedding retrieval46.7658.7146.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.

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

The paper proposes TimeGraph, a question-independent temporal memory built on top of per-frame hierarchical scene graphs (HSGG). Object observations in adjacent sampled frames are linked into entity chains. Runs of consistent states/relations are merged into time-bounded episodes, and changes between episodes are stored as transitions. At question time, an LLM parses the question into (target, constraints, operation), a weighted scoring function retrieves a connected subgraph, and that subgraph restricts which visual candidates are retrieved. Everything is then serialized to text for a text-only LLM (GPT-5.6-luna). The paper reports 73.4 on NAVQA (139 questions), 66.7 on NExT-QA val, and 53.5 on OpenEQA EM-EQA. It also includes a progressive evidence analysis (Table 3), a component ablation (Table 4), and a per-category analysis of “demand-aware” evidence projection.

Critical strengths

1.The central idea is simple and reasonable. Separating what persists, when it holds and how it changes, and building this once per video rather than per question, is a sensible design for temporal QA. The episode/transition abstraction maps nicely onto duration, ordering and state-change questions.

  1. Table 4 is the most convincing part of the paper. With observations and QA model held fixed, adding entity continuity, then episodes, then transitions gives monotone gains on all three benchmarks.

  2. The authors are fairly careful in places. They call Table 3 a pipeline-level comparison rather than an ablation, add clustered bootstrap CIs, and say openly that the small OpenEQA gain from shared visual evidence is not stable across episodes. The case studies include a genuine failure (Fig. 9). Fig. 5 is honestly labeled as successor-window retrieval rather than identity tracking.

Critical weaknesses
  1. Incomplete and unaligned comparison with prior work. Table 2 omits stronger LLM-based results on NExT-QA val (e.g., LLoVi 67.7 and VideoAgent 71.3, per arXiv:2403.10517), so the +3.1 claim does not hold as stated. On NAVQA it is unclear whether baselines used the same 139-question subset. On OpenEQA, GPT-5.6-luna judges its own answers while published scores used other judges.

  2. Weak control baseline. The large gains in Table 3 are measured against lexical-overlap retrieval. An embedding- or caption-based retrieval baseline with the same observations, QA model and budget is needed to show that the gain comes from temporal structure rather than better evidence selection.

  3. Per-dataset tuning. Table 5 shows quite different retrieval designs, coefficients and budgets for each dataset, and the paper does not say what data they were selected on. NExT-QA results are on the validation set, which also makes the “zero-shot” label questionable.

  4. Identity continuity is claimed but not measured. Association only links adjacent sampled observations (w = 1) and has no re-identification, and Fig. 5 itself shows the same baby receiving two IDs. Fragmentation and false-merge rates are not reported.

  5. Fig. 2 attributes the error reduction to TimeGraph, but it compares against a 2021 supervised model and so mostly reflects the stronger LLM. The large per-category gains in Fig. 4 rest on very few questions (n = 6–9). The paper also doesn’t explain how visual evidence is converted to text for the text-only QA model.

Questions for authors

1.What criteria determined which prior results were included? Can the OpenEQA comparisons be rescored under a common judge?

2.How does a same-budget embedding- or caption-retrieval baseline perform?

3.How were the dataset-specific profiles chosen, and how does a single shared profile perform?

4.How often are entities fragmented or wrongly merged, and how much does this affect accuracy?

6 comments
AuthorsOpenReview ↗

Response to Reviewer hWpk (Part 1)

Thank you for the constructive comments. We agree that the original manuscript requires more comprehensive comparisons, stronger controls for evidence retrieval, and a more careful interpretation of the results. We have added same-answerer and same-retriever experiments, evaluated a shared retrieval profile, conducted quantitative association and error-sensitivity analyses, and introduced an alternative OpenEQA evaluation.


1. Completeness and Comparability of Evaluations Against Prior Work

Summary of Reviewer Comment: The original comparison omits relevant LLM-based methods on NExT-QA, including LLoVi and VideoAgent, whose reported results exceed TimeGraph. The comparability of NAVQA baselines is also unclear, and using GPT-5.6-luna as both answer generator and evaluator for OpenEQA may introduce evaluator-specific bias. The reviewer requests more comprehensive comparisons and clarification of the evaluation protocols.

Response

We agree that the original comparison was incomplete and that the previous claim of a 3.1-point advantage on NExT-QA was not supported. We have added the missing methods, revised the corresponding claims, and clarified the evaluation scope and scoring protocols.

1.1 Updated NExT-QA comparison

We added LLoVi and VideoAgent to the full-validation comparison:

MethodVisual modelsQA modelInference organizationAccuracy (%)
LLoViLLaVA-1.5-7BGPT-4Frame captions followed by language reasoning67.7
VideoAgentCogAgent; EVA-CLIP-8B-plusGPT-4Iterative frame retrieval, captioning, and answering71.3
TimeGraphLLaVA-OneVision-1.5-8B (HSGG)GPT-5.6-lunaTemporal memory with graph and visual retrieval66.73

TimeGraph achieves 66.73%, below LLoVi (67.7%) and VideoAgent (71.3%). We have removed the previous claim of a 3.1-point advantage. Instead, we clarify their complementary strengths: LLoVi uses dense temporal descriptions, VideoAgent performs answer-guided iterative retrieval, whereas TimeGraph focuses on explicitly structured temporal memory and question-conditioned evidence retrieval. The additional controlled experiments in Section 2 provide a more direct assessment of temporal-memory organization. These changes are reflected in Table 5 of the revised manuscript.

1.2 NAVQA evaluation scope

Our NAVQA evaluation covers all 139 non-position questions, obtained by excluding the 71 position questions from the original 210-question benchmark.

Question typeNumber
Binary67
Free-text33
Time30
Duration9
Total139

We report results separately for different evaluation subsets:

Evaluation subsetMethodAccuracy
Binary (67 questions)ConceptGraphs29.9%
ReMEmbR NVILA-Lite-2B48.3%
ReMEmbR NVILA-Lite-8B60.7%
DAAAM67.2%
TimeGraph (55/67)82.09%
Binary + free-text (100 questions)TimeGraph (70/100)70.00%
Long descriptive (20 questions)ReMEmbR65.0%
TimeGraph (15/20)75.00%
All non-position questions (139)VL-KnG GR32.4%
VL-KnG GER-G66.2%
TimeGraph (102/139)73.38%

The ReMEmbR result on the Long descriptive subset is a micro-average across three random seeds. DAAAM reports Descriptive Question Accuracy, and its released OC-NaVQA evaluator computes binary accuracy by default.

Importantly, exact question-level overlap and protocol equivalence have not been verified for every published baseline. We therefore present these results as contextual comparisons rather than claiming that all methods were evaluated on identical subsets. The revised manuscript explicitly reports the question counts and evaluation scopes alongside the corresponding results.

1.3 OpenEQA evaluation with an alternative Judge

We agree that using GPT-5.6-luna as both answer generator and evaluator may introduce evaluator-specific effects. We therefore re-scored the saved answers for the same 1,636 OpenEQA questions using GPT-4.1 under the official OpenEQA scoring protocol.

The original evaluation script specifies GPT-4-1106-preview, which was discontinued on 23 October 2026. We used GPT-4.1 as an available alternative Judge. This is an additional evaluation under the official scoring protocol, not an exact reproduction with the original Judge.

Evidence configurationGPT-5.6 JudgeGPT-4.1 Judge
Temporal graph memory48.9253.41
Shared visual evidence49.3953.68
Demand-aware visual evidence53.5055.90

All configurations use the same GPT-5.6-luna-generated answers. The relative ranking is consistent across both Judges, with demand-aware visual evidence achieving the highest score. We therefore report GPT-4.1 as an alternative Judge rather than the original official evaluator. These results are included in Table 17.

AuthorsOpenReview ↗

Response to Reviewer hWpk (Part 2)

2. Strength of Retrieval Baselines and Contribution of Temporal Structure

Summary of Reviewer Comment: The reported gains rely primarily on lexical-overlap retrieval, which may not sufficiently isolate the contribution of temporal organization. The reviewer requests stronger embedding- or caption-based retrieval comparisons using the same observations, answering model, and evidence budget.

Response

We agree that lexical-overlap retrieval alone is insufficient to establish the contribution of temporal memory. We therefore conducted matched embedding-retrieval experiments using the same perception model, answering model, QA template, and evidence budget. We also evaluated uniform-frame captions and All-HSGG observations as complementary evidence configurations.

2.1 Matched embedding-retrieval comparison

Evidence configurationNAVQA (%)NExT-QA (%)OpenEQA
Frame-level HSGG + embedding retrieval20.1449.8233.11
TimeGraph + the same embedding retrieval46.7658.7146.81
Gain+26.62 pp+8.89 pp+13.70

Both conditions use the same frame-level observations, embedding retriever, answering model (GPT-5.6-luna), prompt, evaluator, and evidence budget. The main difference is whether observations are organized into temporal graph memory before retrieval. These results provide the most direct evidence for the contribution of temporal-memory organization and are reported in Table 7.

2.2 Additional evidence configurations

We further evaluated uniform-frame captions and All-HSGG facts under the same answering model.

For uniform-frame captions, we sample one quarter of the available RGB frames, rounded up and bounded between 16 and 64; all frames are used when fewer than 16 are available. Sampling is uniform within the applicable observation scope. For All-HSGG, frame-level facts, including bounding boxes, are serialized chronologically, with a maximum of 1 million factual tokens per question. Seventeen NAVQA contexts exceed this limit, and only their first 1 million tokens are retained.

Evidence configurationNAVQA (%)NExT-QA (%)OpenEQA
Frame-level HSGG + embedding retrieval20.1449.8233.11
TimeGraph + embedding retrieval46.7658.7146.81
Uniform-frame captions41.7359.6142.76
All-HSGG facts, including bounding boxes58.9965.4951.50
Full TimeGraph system73.3866.7353.50

All-HSGG correctly answers 82 of the 139 NAVQA questions (58.99%). Its mean factual input volume is 437,033 tokens per NAVQA question, 35,547 per NExT-QA question, and 184,849 per OpenEQA question, corresponding to 8.33×, 9.93×, and 1.94× the respective TimeGraph input volumes.

All-HSGG exposes individual frame-level observations while leaving cross-frame associations and temporal boundaries implicit. TimeGraph explicitly organizes these structures and retrieves question-relevant evidence. However, the uniform-caption and All-HSGG conditions do not use matched evidence representations or token budgets. We therefore interpret them as complementary evidence comparisons rather than strict token-matched controls. These results are reported in Tables 14 and 15.

2.3 Updated graph-retrieval ablation

We also revised the first row of the original graph ablation. Previously, the frame-level graph condition used the lexical-overlap baseline from Table 3, resulting in identical scores. We reran this condition using graph retrieval, while retaining the same observations, answering model, prompt, evaluator, and evidence-budget policy as the graph-based ablation.

Memory representationNAVQA (%)NExT-QA (%)OpenEQA
Frame-level HSGG + graph retrieval20.8650.3234.58
+ Entity continuity24.4653.0437.20
+ Temporal episodes33.8159.6543.59
TimeGraph graph-only52.5260.5348.92

The revised first row provides a graph-retrieval control distinct from the lexical baseline. We have updated Table 8 and clarified the retrieval procedure and evidence budget for each condition. The representation-level interpretation depends on identical graph retrieval, candidate-processing rules, and evidence budgets across all four configurations.

AuthorsOpenReview ↗

Response to Reviewer hWpk (Part 3)

3. Dataset-Specific Retrieval Profiles and Generalization

Summary of Reviewer Comment: The dataset-specific retrieval configurations, scoring coefficients, and evidence budgets are insufficiently explained. It is also unclear whether benchmark evaluation data were used for parameter selection and whether the term "zero-shot" is appropriate. The reviewer requests a shared retrieval configuration across benchmarks.

Response

We agree that the original manuscript did not sufficiently explain the retrieval profiles or distinguish training-free inference from strict zero-shot evaluation. The original evidence budgets reflect differences in observation scope and evidence requirements:

DatasetGraph evidence budgetVisual evidence budget
NAVQA108
NExT-QA1612
OpenEQA108

NAVQA involves question-specific observation windows and navigation-related temporal constraints; NExT-QA emphasizes actions and event ordering; OpenEQA focuses on episodic object, attribute, and spatial-relation evidence.

To assess the dependence on dataset-specific settings, we evaluated a shared retrieval profile using identical graph-retrieval procedures, scoring weights, candidate-processing rules, and evidence budgets. Each question uses at most 16 graph records and 12 visual-evidence records, with a common evidence-text cap of 32,768 tokens. Question-dependent retrieval constraints and demand-aware evidence organization are retained.

DatasetOriginal profileShared profileDifference
NAVQA73.3871.94−1.44 pp
NExT-QA66.7366.37−0.36 pp
OpenEQA53.5053.27−0.23 points

The shared profile yields results close to the original configurations, with differences no larger than 1.44 points. This suggests that performance is not solely dependent on dataset-specific evidence budgets.

We have clarified the parameter-selection procedure, when the settings were fixed, and whether benchmark evaluation labels or outcomes were used. Since NExT-QA is evaluated on its validation set, we have also replaced or qualified the stronger "zero-shot" claim. We use training-free to describe inference without additional model training, rather than implying that all retrieval settings were selected independently of benchmark evaluation. These results are reported in Table 16.

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

The paper proposes TimeGraph, a training-free temporal graph memory for long-video QA. Per-frame scene graphs are linked across adjacent frames into persistent entities, with time-bounded state and relation episodes and explicit transitions between them. At question time, an LLM parses the question and retrieves a relevant subgraph plus supporting visual evidence. GPT-5.6-luna then answers from a text serialization of that evidence. The method reports gains of 6.2, 3.1 and 1.9 points over prior published results on NAVQA, NExT-QA and OpenEQA, and much larger gains (13–35 points) over a lexical frame-retrieval baseline.

Critical strengths

The decomposition into entities, episodes and transitions is clean and well motivated. Building the memory once per video, independent of the question and without training, is a sensible design. I also appreciated that the analysis is candid. The authors acknowledge that Tables 1–2 are not controlled comparisons, report where a gain is not stable (Table 6), and include a failure case.

Critical weaknesses
  • It is hard to tell how much of the gain comes from the temporal graph. The answering model is GPT-5.6-luna, while most compared methods use much weaker models (HGA, SeViLA, GPT-4). The only same-LLM baseline is lexical frame retrieval, which is quite weak: 17.27% on NAVQA, below every ReMEmbR variant in Table 1. The first row of the Table 4 ablation is also identical to that lexical baseline, so the ablation may be changing the retriever as well as the memory structure. Same-LLM baselines with frame captions or embedding-based retrieval are needed to support the main claim.
  • The evaluation is not well aligned with the cited results. On OpenEQA, GPT-5.6-luna is both answerer and judge, which makes the +1.9 margin hard to interpret. On NAVQA, the evaluation uses only 139 questions (+6.2 is about 9 questions), and it is unclear whether the baselines used the same subset. Retrieval settings are also tuned per dataset (Table 5) without saying how they were chosen, which weakens the "zero-shot" and generality claims.
Questions for authors
  • Can you add same-LLM baselines (uniform frame captions, all HSGG observations without retrieval, embedding-based retrieval)? This would most affect my score.
  • Does every row in Table 4 use the same retriever and evidence budget?
  • Can you rescore OpenEQA with the original evaluator, and confirm that the NAVQA baselines use the same 139 questions?
  • With w = 1, an entity cannot be re-identified after occlusion; in Fig. 5, the same baby gets two IDs 1.25 s apart. How reliable is entity association in practice, and how does it hold up on longer videos?
5 comments
AuthorsOpenReview ↗

Response to Reviewer dRAC (Part 1)

Thank you for the constructive comments. We agree that the contribution of temporal graph memory needs to be distinguished from the effects of the answering model, evidence representation, and retrieval strategy. We have conducted additional controlled comparisons, revised the graph ablation, evaluated OpenEQA with an alternative Judge, tested a shared retrieval configuration, and quantified entity-association errors and their impact on QA. We have also clarified the evaluation scope and acknowledged the limitations of the current association mechanism.


1. Contribution of Temporal Graph Memory

Summary of Reviewer Comment: The reported gains may be influenced by differences in answering models and evidence representations rather than temporal graph memory itself. The lexical-retrieval baseline is also insufficient to isolate the contribution of temporal organization. The reviewer requests comparisons using the same answering model, including embedding-based retrieval, uniform-frame captions, and all HSGG observations.

Response

We agree that comparisons across different answering models cannot isolate the contribution of temporal graph memory. We therefore conducted additional experiments using the same answering model (GPT-5.6-luna), task-level QA template, and evaluation protocol within each benchmark.

Shared experimental settings

SettingSpecification
Perception modelLLaVA-OneVision-1.5-8B-Instruct
Answering modelGPT-5.6-luna
QA templateIdentical within each benchmark
Observation scopeQuestion-specific windows for NAVQA; entire videos for NExT-QA; entire episodes for OpenEQA
Evaluation set139 NAVQA, 4,996 NExT-QA, and 1,636 OpenEQA questions

Evidence configurations and results

ConfigurationNAVQA (%)NExT-QA (%)OpenEQA
Frame-level HSGG + embedding retrieval20.1449.8233.11
TimeGraph + embedding retrieval46.7658.7146.81
Uniform-frame captions41.7359.6142.76
All-HSGG observations58.9965.4951.50
Full TimeGraph73.3866.7353.50

The frame-level HSGG and TimeGraph conditions use the same embedding retriever and evidence budget. Compared with frame-level HSGG, TimeGraph improves performance by 26.62 percentage points on NAVQA, 8.89 points on NExT-QA, and 13.70 points on OpenEQA. Since the answering model and retrieval procedure are held constant, this provides the most direct evidence for the benefit of temporal memory organization.

The other two configurations provide complementary comparisons. Uniform-frame captions are generated from uniformly sampled RGB frames (one quarter of the available frames, bounded between 16 and 64; all frames are used when fewer than 16 are available). All-HSGG serializes frame-level facts, including bounding boxes, in chronological order, with a maximum of 1 million factual tokens per question. All-HSGG achieves 58.99%, 65.49%, and 51.50% on the three benchmarks, respectively. Its mean input volume is 437,033 tokens per NAVQA question, 35,547 per NExT-QA question, and 184,849 per OpenEQA question, corresponding to 8.33×, 9.93×, and 1.94× the respective TimeGraph input volumes. Seventeen NAVQA contexts exceed the 1-million-token limit, for which only the first 1 million tokens are retained.

Unlike TimeGraph, All-HSGG leaves cross-frame associations and temporal boundaries implicit in the serialized observations. However, these comparisons do not use matched evidence budgets, and chronological truncation may affect the evidence available to the answering model. We therefore interpret them as comparisons of alternative evidence configurations rather than strict token-matched ablations. The additional results are reported in Tables 14 and 15.

AuthorsOpenReview ↗

Response to Reviewer dRAC (Part 2)

2. Controlled Ablation of Graph Retrieval and Memory Representation

Summary of Reviewer Comment: The original ablation does not clearly separate memory representation from retrieval strategy. In particular, its first row appears identical to the lexical-retrieval baseline. The reviewer asks whether the same retriever, candidate-processing strategy, and evidence budget are used across configurations.

Response

We agree that the original ablation did not sufficiently distinguish these factors. The original frame-level graph condition used lexical-overlap retrieval, explaining its identical results to the frame-local retrieval baseline in Table 3 ( Table 6 in the revised manuscript). We therefore reran this condition using graph retrieval. The updated results are:

Memory representationNAVQA (%)NExT-QA (%)OpenEQA
Frame-level HSGG + graph retrieval20.8650.3234.58
+ Entity continuity24.4653.0437.20
+ Temporal episodes33.8159.6543.59
TimeGraph graph-only52.5260.5348.92

The revised first row provides a graph-retrieval baseline, distinct from the lexical-retrieval baseline in Table 3 (Table 6 in the revised manuscript). The results show progressively higher performance as entity continuity, temporal episodes, and transition information are incorporated.

We have updated Table 4 (Table 8 in the revised manuscript) and clarified the retrieval settings and evidence budgets in the revised manuscript. The representation-level interpretation of this ablation depends on using identical graph retrieval, candidate-processing rules, and evidence budgets across all four configurations; we have clarified these conditions in the experimental description.

AuthorsOpenReview ↗

Response to Reviewer dRAC (Part 3)

3. Evaluation Protocol, NAVQA Coverage, and Retrieval Configuration

Summary of Reviewer Comment: The evaluation protocol raises concerns about potential Judge bias in OpenEQA, the limited NAVQA evaluation subset, and dataset-specific retrieval settings. The reviewer requests an alternative OpenEQA evaluation, clarification of NAVQA baseline comparability, and a justification of retrieval parameter selection.

3.1 OpenEQA evaluation with an alternative Judge

We agree that using GPT-5.6-luna as both answer generator and evaluator may introduce evaluator-specific effects. We therefore re-evaluated the saved answers for all 1,636 OpenEQA questions using GPT-4.1 under the official OpenEQA scoring protocol.

The original evaluation script specifies GPT-4-1106-preview, which was discontinued on 23 October 2026. GPT-4.1 was therefore used as an available alternative Judge. This is a sensitivity analysis under the official scoring protocol, not an exact reproduction with the original Judge.

Evidence configurationGPT-5.6 JudgeGPT-4.1 Judge
Temporal graph memory48.9253.41
Shared visual evidence49.3953.68
Demand-aware visual evidence53.5055.90

All configurations use the same GPT-5.6-luna-generated answers. The relative ranking is consistent across both Judges: demand-aware visual evidence performs best, achieving 55.90 with GPT-4.1, compared with 53.68 for shared visual evidence and 53.41 for temporal graph memory. We retain the original results and report GPT-4.1 as an alternative Judge rather than the original official evaluator. These results are presented in Table 17.

3.2 NAVQA evaluation scope and baseline comparability

Our evaluation covers all 139 non-position questions from the original 210-question NAVQA benchmark, excluding 71 position questions.

Question typeNumber
Binary67
Free-text33
Temporal30
Duration9
Total139

To make the evaluation scope explicit, we report results for different question subsets:

Evaluation subsetMethodAccuracy
Binary (67 questions)ConceptGraphs29.9%
ReMEmbR NVILA-Lite-2B48.3%
ReMEmbR NVILA-Lite-8B60.7%
DAAAM67.2%
TimeGraph (55/67)82.09%
Binary + free-text (100 questions)TimeGraph (70/100)70.00%
Long descriptive (20 questions)ReMEmbR65.0%
TimeGraph (15/20)75.00%
All non-position questions (139)VL-KnG GR32.4%
VL-KnG GER-G66.2%
TimeGraph (102/139)73.38%

These published baseline results are contextual comparisons; exact question-level overlap and evaluation-protocol equivalence have not been verified for every method. In particular, DAAAM reports Descriptive Question Accuracy, and its released OC-NaVQA evaluator computes binary accuracy by default. We therefore avoid implying that all published results were obtained on identical subsets. The revised manuscript specifies the evaluation scope and question counts alongside each comparison.

3.3 Dataset-specific and shared retrieval configurations

We agree that the original manuscript did not sufficiently explain the dataset-specific retrieval profiles. The original graph/visual evidence budgets were 10/8 for NAVQA, 16/12 for NExT-QA, and 10/8 for OpenEQA. These settings reflect differences in observation scope and evidence requirements across the benchmarks.

To examine their influence, we additionally evaluated a shared retrieval configuration using identical graph-retrieval procedures, scoring weights, candidate-processing rules, and evidence budgets across datasets. Each question uses at most 16 graph records and 12 visual-evidence records, with a common evidence-text cap of 32,768 tokens. Question-dependent retrieval constraints and demand-aware evidence organization are retained.

DatasetOriginal profileShared profileDifference
NAVQA73.3871.94−1.44 pp
NExT-QA66.7366.37−0.36 pp
OpenEQA53.5053.27−0.23 points

The shared profile yields results close to the original configurations, with differences no larger than 1.44 points. This suggests that performance does not depend solely on the original dataset-specific evidence budgets.

We have clarified the parameter-selection procedure and the role of benchmark-specific settings in the revised Methods and Appendix. We also use training-free rather than an unrestricted zero-shot claim, since the latter would require demonstrating that all retrieval parameters were selected independently of benchmark evaluation. These results are reported in Table 16.

Comments on the paper

1 comment
Area_Chair_cN88OpenReview ↗

Friendly reminder from AC

Dear Reviewers,

Thank you for your reviews. The initial ratings are 2 / 2 / 3. The authors have posted extensive multi-part responses to all reviews. Thank you, Reviewer Qr3b, for engaging and confirming your assessment. Reviewers dRAC and hWpk, we would greatly appreciate hearing from you.

Please let us know whether the responses resolve your concerns and whether your assessment has changed. If issues remain, please state them concretely so the authors can still respond.

Thank you for your time and contributions.

Best regards, AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.