Understanding Complexity in VideoQA via Visual Program Generation

Thank you for your detailed review and suggestions. We address your comments individually below (comment 2 of 2).

---

Q1: How do the findings in the paper generalize to models that take multiple frames as input?

Sevila takes in multiple video frames. The only model that does not take in multiple frames is ATP. Sevila does do frame selection. Other models (except for ATP) don't. We have additionally evaluated Tarsier [1], a recent multi-frame Video LLM based on LLaMA, which is the SoTA model on NextQA and is architecturally equivalent to Video-LLaVA. As shown in the table below, Tarsier also struggles with questions identified as complex by CodePlexity. We have updated Table 1 in the manuscript with this result. Additionally, Tarsier has been added to the results in Table 2 and Figure 3 of the manuscript, which also show that the findings in the paper generalize to Tarsier. Namely, that code-based metrics outperform their text-based counterparts, and that our approach, CodePlexity, further improves upon them.

---

Q2: Why not use VidOR instead of MOMA+ActivityNet+Charades for CodePlexQA

Thank you for raising this point. While VidOR provides a valuable dataset for video-related tasks, we chose not to use it for the following reasons:

1. Limited variety: Videos in VidOR lack diversity, both in terms of visual content and scenarios. This limits the range of complex, challenging questions that can be generated.
2. Short video duration: Most videos in VidOR are relatively short, which makes it difficult to create and evaluate questions requiring fine-grained temporal reasoning or extended contextual understanding.
3. Older source material: VidOR is sourced from YFCC, a collection of videos from Flickr dating back to 2016. While useful, these older videos may not represent the richness or variability seen in more contemporary datasets.

To address these limitations, we opted to use videos from three different sources: MOMA, ActivityNet, and Action Genome. This allows us to leverage a wider variety of video types, durations, and content, ensuring that our benchmark better captures the complexity and diversity of real-world scenarios.

---

[1] Wang, J., Yuan, L., Zhang, Y., & Sun, H. (2024). Tarsier: Recipes for training and evaluating large video description models. arXiv preprint arXiv:2407.00634.

[2] Ge, J. & Subramanian, S. & Shi, B. & Herzig, R. & Darrell, T. Recursive visual programming,. In ECCV’24

Thank you for your detailed review and suggestions. We address your comments individually below (comment 1 of 2)

---

W1: CodePlexity is not the perfect metric for evaluating question complexity in VideoQA

We wholeheartedly agree. Our question complexity metric based on visual program analysis has limitations, including not always predicting the correct complexity score (indeed, it achieves an mPEG score of only ~25/100). It is, however, the best automatic metric that exists at the moment, and is also significantly more accurate than humans (see analysis in Section 4.2). Importantly, it provides human-interpretable and actionable insights into the key sources of complexities of existing models, allowing us to automatically construct a new challenging VideoQA benchmark. While we acknowledge that our approach does not address all challenges of VideoQA, we believe it represents a significant and valuable step forward for the field.

---

W2: Our analysis does not consider video information

We acknowledge that our approach focuses on analyzing question complexity independently of video information. However, we emphasize that asking complex questions about videos is a long-standing challenge. The first benchmark for video-language reasoning was introduced in Rohrbach et al., CVPR'15, and was followed by dozens of attempts to manually design questions that cannot be answered from a single frame, which were largely unsuccessful [4, 21, 33]. Our method takes a data-driven approach instead, discovering sources of complexity directly from the data, which is both novel and complementary to existing methods.

Additionally, as discussed in Section 9.1 of the appendix, video and text-based complexities are composable. This validates the study of question complexity in isolation. Combining CodePlexity with accurate video complexity metrics could yield an even more comprehensive evaluation in future work. Hence, our study of question complexity in VideoQA is still a valuable and valid research direction.

---

W3: Both human and algorithmic baselines also only consider text information

It is indeed true that our baselines, including human evaluations, focus solely on text information. This is a deliberate choice, as our goal is to evaluate question complexity in isolation from the video. While humans may not perfectly estimate video question complexity based on text alone, their judgments still provide informative estimates. Comparing baselines with access to the same information ensures fair evaluations of our metric.

---

W4: Please report more recent VP methods and more recent datasets

We reran the analysis with the recommended RVP mode [2] and show that code-based complexity functions based on it also correlate negatively with model performance. Results are shown in Figure 19 of the Appendix and demonstrate that using a more advanced CodeGen model enhances the predictive power of code-based metrics for estimating question complexity. This highlights the extensibility of our method and its potential for further improvement as code generation models continue to evolve.

In addition, we are now re-running our experiments on MVBench. Please appreciate the effort involved in this, as it essentially requires re-running most of the experiments in the paper on a new, large-scale dataset. We expect the experiments to finish before 26th of November and will post the results here as soon as possible.

---

W5: Please provide additional details and statistics of the proposed CodePlexQA benchmark

We provide the requested details here and added them to Section 8 of the Appendix. The resulting dataset has an average of 2.40 questions per video. The duration of each video ranges from approximately 3 seconds to 10 minutes with an average video duration of about 1.5 minutes. This diverse range of video lengths is desirable as it is conducent to generating a wide variety of questions.

I thank the authors for the detailed explanations.

One big concern shared by other reviewers is the robustness of the proposed approach. In particular, results in the NextQA-ATP-Hard split help to shed some light on this issue.

My question regarding using videos from MOMA, ActivityNet, ActivityNet-Entities, and ActivityNet-Captions comes from the fact that comparing the NExT-QA benchmark and the proposed CodePlex-QA might be unfair. As the authors pointed out, VidOR has several limitations, including: limited variety, short video duration, and older source material. However, NExT-QA is composed of 6,000 VidOR videos. It seems that the benefits from CodePlex-QA may come from the video sources and not the proposed approach/metric. Generating CodePlex-QA from VidOR would yield a slightly better/fairer comparison.

Thank you for your detailed review and suggestions. We address your comments individually below.

---

W1: CodePlexity doesn't capture ‘the inherent complexity of the question’

Please note that the concept of "inherent question complexity" is not well-defined and that our work does not claim to capture it. Instead, our primary objective is to propose a practical and operationalizable metric, CodePlexity, to evaluate the relative difficulty of VideoQA questions for existing models. Our findings highlight a crucial gap: questions that appear straightforward to humans can be disproportionately challenging for current VideoQA architectures due to their inherent design limitations. CodePlexity addresses this gap by serving as a bridge between human intuition and model-specific difficulty.

---

W2: Visual programming methods are not evaluated in the paper

We thank the reviewer for pointing this out. We are currently evaluating ViperGPT on CodeplexQA and will post the results as soon as the evaluation finishes

---

W3: Comparison with NextQA-ATP-Hard split is not provided

This is a great point! We provide the requested evaluation below, as well as in Table 2 in the manuscript. Critically, ATP-Hard uses ground truth labels in Next-QA to select questions on which a proportion of model from an ensemble of 10 VideoQA models fails. In contrast, our approach only requires the question itself to determine its complexity.

Despite this oracle-like nature of ATP-Hard, CodeplexQA is substantially more challenging for the top performing models and approximately equally hard for the least effective VIOLET baseline. ATP-Hard is somewhat more challenging than CodeplexQA for InternVideo because this baseline is finetuned from CLIP and the samples in ATP-Hard were selected by seeing where CLIP-based models fail (i.e. this dataset represents an upper bound in terms of complexity for CLIP-based models). These results strongly support the effectiveness of both our complexity metric and of our automatic approach for generating challenging VideoQA benchmarks.

Thank you for your detailed review and suggestions. We address your comments individually below.

---

W1: All evaluations are conducted on NextQA

We thank the reviewer for pointing out this imitation. To evaluate the generalizability of our method, following the suggestion of Reviewer Hrka, we are now running analysis on the very recent MVBench dataset. Please appreciate the effort involved in this, as it essentially requires re-running most of the experiments in the paper on a new, large-scale dataset. We expect the experiments to finish before 26th of November and will post the results here as soon as possible.

---

W2: How do errors in code generation affect CodePlexity?

We thank the reviewer for bringing up this under-explored aspect of our method. We have analyzed the performance of CodePlexity on questions which ViperGPT answers correctly (i.e. the generated code is correct), vs. the questions on which ViperGPT fails and show the results here and in Table 4 in the updated manuscript. As you can see, while the correlation between models’ performance and predicted metric value is consistently higher when the code is correct for all code-based metrics, CodePlexity is a lot more robust to code generation errors than the baselines. Please also see our response to Reviewer RWYy above, where we show that using more advanced code generation models improves the predictive power of code-based complexity metrics.

---

W3: The sample size for the human study is relatively small.

Thank you for your observation. While we agree that a larger sample size is generally preferable, we argue that our sample size of 150 questions is consistent with established practices in the literature. For instance, in the original BLEU metric study by Papineni et al. (2002), human evaluations were conducted on 250 sentence pairs [1]. Similarly, in machine learning research, Ranzato et al. (2015) assessed their reinforcement learning model on 100-200 test cases for specific NLP tasks [2]. In linguistics, Koehn et al. (2007) conducted human evaluations of translations on sets of 150-300 sentences [3]. Given this precedent, we believe our sample size is reasonable and sufficient to draw meaningful conclusions.

---

W4: Does merging co-occurring subtrees risk missing important patterns?

We thank the reviewer for pointing out this important detail. To clarify, subtrees are only merged when they always co-occur in cases where one is a descendant of the other. This means their one-hot encodings are identical across all programs, ensuring that merging does not lose unique patterns. Since the co-occurrence is absolute, any pattern found in one subtree will also exist in the other. We have updated Section 7.1 of the Appendix to include this discussion.

---

W5: Does manual filtering of generated questions introduce a selection bias?

Our filtering process is very straightforward and as bias-free as possible. In particular, we only remove questions where the automatically generated answer is wrong, or the question cannot be answered from the video (for example, when the LLM refers to an actor by their annotated ID instead of a visual attribute). There is no manual filtering of questions beyond that.

---

[1] Papineni, K., Roukos, S., Ward, T., & Zhu, W.-J. (2002). BLEU: A method for automatic evaluation of machine translation. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL), 311–318. https://doi.org/10.3115/1073083.1073135

[2] Ranzato, M., Chopra, S., Auli, M., & Zaremba, W. (2016). Sequence level training with recurrent neural networks. arXiv preprint arXiv:1511.06732. https://doi.org/10.48550/arXiv.1511.06732

[3] Koehn, P., Och, F. J., & Marcu, D. (2003). Statistical phrase-based translation. Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (NAACL-HLT), 48–54. https://doi.org/10.3115/1073445.1073462

Thank you for your detailed review and suggestions. We respond to your question individually below.

---

Q1: Does the one-hot subtree representations limit the metrics’s performance?

Using one-hot encoding for subtree representations does not significantly limit metric performance because it is effectively similar to using counts in most practical scenarios. The likelihood of a subtree appearing multiple times in a program’s AST is minimal (except for leaf nodes). For a subtree to appear more than once, the same code logic would need to be repeated, which is uncommon. Therefore, the difference is negligible, and one-hot effectively captures the necessary structural information without compromising metric quality.

---

Q2: How does the code generation model affect the results?

Thank you for this excellent question. The choice of code generation model is indeed an important factor in our methodology. To investigate this, we re-ran our experiments using the recent RVP [1] CodeGen approach as a substitute for ViperGPT. Preliminary results, included in Figure 19 of the updated manuscript, demonstrate that using a more advanced CodeGen model enhances the predictive power of code-based metrics for estimating question complexity.

These results suggest that the performance of CodePlexity can benefit from advancements in code generation models, as they can provide richer and more accurate program representations. While this introduces some variability depending on the underlying model, the general approach remains robust and adaptable. We are in the process of completing a detailed analysis and will include the finalized results in the camera-ready version of the paper.

This highlights the extensibility of our method and its potential for further improvement as code generation models continue to evolve.

---

Q3: Is CodePlexity truly measuring question difficulty?

We acknowledge that CodePlexity is not a definitive complexity metric for VideoQA and has limitations, including its indirect consideration of video content. Our key observation is that generated code complexity (not “code generation complexity”) is strongly correlated with underlying question complexity for existing VideoQA models. In particular, we experimentally demonstrate in Section 4.2 that CodePlexity exhibits superior predictive power compared to other automatic metrics and even human evaluations. Hence, our approach is not "primarily measuring code generation complexity”.

---

Q4: How would our method generalize to fundamentally different VideoQA models?

We thank the reviewer for this insightful observation. It is true that most modern VideoQA approaches leverage large visual-language models in one way or another. That said, the models evaluated in our works are quite diverse: ATP only trains a frame selection module and is based on CLIP, ViperGPT is a Visual Programming approach that leverages a suite of modules (CLIP, GPT3, BLIP, XVLM), VIOLET is a multimodal transformer, which is trained from scratch on the Merlot dataset and SeViLA is a 2-stage video model finetunned from a VLM. In response to the reviewers suggestion we have added two additional models.

• HGA [2]: based on Graph Neural Networks, this model combines visual and textual features (from BERT) using a Graph Reasoning Network. It was the state of the art on NExT-QA before ATP.
• Tarsier [3]: the current state of the art on NExT-QA, based on Video-LLaVA [4]. The results are reported below, as well as in Table 1 in the manuscript. As you can see from the results, our question complexity metric indeed generalizes well to these disparate models.

If the reviewer has a concrete suggestion of a VideoQA approach which is fundamentally different from all the models listed above we would be happy to evaluate it as well.

---

[1] Ge, J. & Subramanian, S. & Shi, B. & Herzig, R. & Darrell, T. Recursive visual programming,. In ECCV’24

[2] Jiang, P., & Han, Y. (2020, April). Reasoning with heterogeneous graph alignment for video question answering. In Proceedings of the AAAI Conference on Artificial Intelligence

[3] Wang, J., Yuan, L., Zhang, Y., & Sun, H. (2024). Tarsier: Recipes for training and evaluating large video description models. arXiv preprint arXiv:2407.00634.

[4] Lin, Bin, et al. "Video-llava: Learning united visual representation by alignment before projection." arXiv preprint arXiv:2311.10122(2023).