Understanding Complexity in VideoQA via Visual Program Generation

Authors: Cristobal Eyzaguirre, Igor Vasiljevic, Achal Dave, Jiajun Wu, Rares Andrei Ambrus, Thomas Kollar, Juan Carlos Niebles, Pavel Tokmakov
Primary area: applications to computer vision, audio, language, and other modalities
Keywords: video understanding, codegen

Abstract:
We propose a data-driven approach to analyzing query complexity in Video Question Answering (VideoQA). Previous efforts in benchmark design have largely relied on human expertise to construct challenging samples. In this work, we experimentally demonstrate that humans struggle to accurately estimate which questions are hard to answer for machine learning models. 
    Our alternative, automated approach takes advantage of recent advances in code generation for visual question answering. In particular, we use generated code complexity as a proxy for the question complexity and demonstrate that it indeed shows a much stronger correlation with the models' performance, compared to human estimates. We then present a novel algorithm for estimating question complexity from code. It identifies fine-grained primitives which correlate with the hardest questions. These human-interpretable results lead to a number of discoveries about the key sources of complexity for VideoQA models. Finally, we extend our approach to generate complex questions for a given set of videos. This allows us to automatically construct a new benchmark, which is 1.9 times harder for VideoQA methods than existing manually designed datasets.

Decision: reject
Reviewer scores: 6, 6, 3, 6

Reviews and discussion:
<thread>
creation date:
1730586997699

thread_type:
official_review

<thread_object>
creator: reviewer_hrka

<content>
summary:
This paper explores a data-driven method for evaluating question complexity for Video Question Answering (VQA) by collecting the visual programs generated by ViperGPT. Then, they analyze the code outputs and leverage them to assess the difficulty of the questions in a VQA triplet.
Given the output code from the Visual Programming module (ViperGPT), they propose CodePlexity, an algorithm that parses the generated code via Abstract Syntax Trees (AST), and later identifies valid subtrees. These subtrees are then scored by correlating subtrees with difficult questions -- subroutines that hurt the VQA model performance. The authors use NExT-QA as the benchmark to analyze their proposed metric. 
Given this metric, they also propose a pipeline to generate difficult question-answer pairs for a set of videos from MOMA, ActivityNet (+Entities/Captions), Action Genome, and Charades. 
Finally, they compare the results of models SeViLA-ZS, InternVideo and VIOLET on their proposed new dataset (CodePlex-QA) against NExT-QA.

strengths:
+ This paper is easy to read, the method is easy to follow and the qualitative examples help to illustrate the motivation of their work.

+ Leveraging Visual Programming outputs as a proxy for assessing the difficulty of a given task is an underexplored domain -- in software engineering, an active area of study is the correlation between the code complexity and difficulty of the task. This is an open problem, and this paper proposes an interesting generalization of this task.

+ Decomposing the output code from the VP module via ASTs, and identifying subtrees that decrease performance via scoring, may give an interesting angle for generating an interpretable pipeline to analyze subprocesses that might be hurting the models' performance. In principle, this looks like an interesting approach and a viable metric for VP-based methods.

weaknesses:
- Visual Programming (VP) is an interpretable framework for several visio-linguistic tasks, however, VP may output very simple code for a quite complex task, yielding false positive or false negative hard cases, and VP might not be reliable -- for a very complex task, the output code could be simple; the LLM might regard it as a simple task, but it's actually the opposite
In addition, VP falls short against end-to-end models (e.g., ViperGPT acc. is 60% vs SeViLa (finetuned) acc. is 73.8%) -- given its underperformance, it is hard to justify the use of its outputs as a proxy for evaluation of complexity. It is also hard to justify using VP for measuring task complexity and then evaluating on end-to-end models.

- Disregarding visual inputs: "Text-based metrics (above) perform worse than the code-based ones (below), and our approach demonstrates the highest correlation with the models’ performance."  -- this completely ignores the visual modality, which seems problematic.

- The authors claim: "In summary, we discovered that VideoQA methods struggle with fine-grained temporal reasoning and lack spatio-temporal, object-centric representations. This is in accord with prior studies" [3] -- however, those studies regard both visual and language modalities for assessing temporal reasoning in video QA, giving high importance to the video part.

- Human evaluations: Figure 6: We ask human annotators to provide the relative ordering of three provided questions
according to the estimated complexity of answering the question about an unseen video -- how to correctly assess the complexity of the task without looking at the video?

- Experimental setup:
Baselines [1] focus on grammar and text only. BERT and GPT-4 also focus on text only.

- Generalizability: ViperGPT is the VP module used in this paper, however, VP has significantly progressed. Different methods leverage multiple LLMs, there has been extensive problem decomposition and iteration that impact the code outputs. Further experiments with other VP approaches might be required to ensure generalization. Similarly, the proposed metric and dataset is only compared against NExT-QA. Other benchmarks might be necessary to validate the proposed metric and dataset (e.g., MVBench [2] compiles a collection of datasets (with subsets of samples from a diverse range of sources), which includes spatio-temporal analysis, spatial action, object, position, scene, count, attribute and cognition).

- For dataset generation, the authors compare their pipeline with [4] -- however, an important step for EgoSchema is the manual curation of the whole dataset in the final step -- details for this step is not further detailed in this paper.
Furthermore, as a comparison, EgoSchema consists of over 5000 human curated multiple choice question answer pairs, spanning over 250 hours of real video data -- significantly larger than the 1981 samples -- what is the length of each video sample?


[1] Yulia Tsvetkov, Manaal Faruqui, Wang Ling, Brian MacWhinney, and Chris Dyer. Learning the curriculum with bayesian optimization for task-specific word representation learning. In ACL, 2016. 

[2] Li, Kunchang, et al. "Mvbench: A comprehensive multi-modal video understanding benchmark." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.

[3] Shyamal Buch, Crist´obal Eyzaguirre, Adrien Gaidon, Jiajun Wu, Li Fei-Fei, and Juan Carlos Niebles. Revisiting the” video” in video-language understanding. In CVPR, 2022.

[4] Karttikeya Mangalam, Raiymbek Akshulakov, and Jitendra Malik. EgoSchema: A diagnostic benchmark for very long-form video language understanding. In NeurIPS, 2023.

questions:
- SeViLA "leverages a single image-language model (BLIP2) to tackle both temporal keyframe localization and question answering on videos" How the findings in this paper generalize to models that take multiple video frames for VQA? (e.g., VideoChat2 [5], Video-LLaVA [6])?

- NExT-QA uses videos from VidOR [7] -- CodePlex-QA use videos from MOMA, ActivityNet, ActivityNet-Entities, ActivityNet-Captions), Action Genome, and Charades. Why not using the same videos, or at least the same source video dataset (VidOR)?

[5] Li, Kunchang, et al. "Mvbench: A comprehensive multi-modal video understanding benchmark." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.

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

[7] Xindi Shang, Donglin Di, Junbin Xiao, Yu Cao, Xun Yang, and Tat-Seng Chua. Annotating objects and relations in user generated videos. In ICMR, pages 279–287, 2019
</content>
</thread_object>

</thread>
<thread>
creation date:
1730610389424

thread_type:
official_review

<thread_object>
creator: reviewer_ehtb

<content>
summary:
In this paper, the author claims that the questions considered difficult are different from the actual difficult questions to current VideoQA models. Therefore, the authors propose a new metric: CodePlexity, to evaluate the difficulty of a VideoQA question. This metric is based on the recent visual programming methods, where a visual program of a question is generated and which complexity is evaluated. Based on this metric, the authors found that most models struggle with questions where multiple frames are included and frame order need to be take into consideration. Then based on the metric, the author proposes CodePlex-QA and claims that it is 1.9 times harder than existing benchmarks.

strengths:
1. The paper proposes a novel metric to evaluate the complexity of the VideoQA problem and also proposes a CodePlex-QA that is more difficult for current VideoQA models. The idea of leveraging code to develop a new metric for question difficulty analysis is interesting.
2. The paper conducts thorough experiments on testing the correlation of the metric.

weaknesses:
1. The criteria for what makes a question complex or challenging for models—especially compared to human intuition—seem speculative. Without more rigorous validation, it’s unclear whether the proposed complexity measures truly capture inherent question difficulty or just reflect the limitations of current VideoQA models. Also, the idea of identifying questions that are “easy for humans but hard for machines” is ambiguous. It seems plausible that any difference in difficulty may be more a result of model architecture and training rather than the intrinsic complexity of the question itself.
2. Visual programming is a natural way (and probably the best way) to address the CodePlex-QA  task. The author didn't report how well the recent visual programming methods (Visprog, ViperGPT, CodeVQA), especially those on addressing complex logical questions (eg. RVP[1]) addresses the task.
3. The comparison between Next-QA and CodePlex-QA (Table2) is not convincing enough as previous works have shown that Next-QA have easy questions[2]. How is CodePlex-QA compared with Next-QA ATP-Hard split?

[1] Recursive Visual Programming
[2]Revisiting the "Video" in Video-Language Understanding

questions:
1. What are the results of the recent visual programming methods on this task?
2. How complex is CodePlex-QA compared with Next-QA ATP-T/ATP-C split?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730709395910

thread_type:
official_review

<thread_object>
creator: reviewer_8wrw

<content>
summary:
This paper proposes a novel approach to analyzing and measuring question complexity in VideoQA by leveraging generated code complexity. The authors demonstrate that code-based metrics correlate better with model performance compared to human judgment and introduce CodePlexity, an algorithm for estimating question complexity. They use this to identify challenging patterns in VideoQA and automatically generate a new benchmark dataset, CodePlex-QA, which proves to be significantly more challenging than existing datasets.

strengths:
- The idea to measuring question complexity using code generation is well-motivated
- The ablation studies and analysis are well-designed

weaknesses:
- All experiments are conducted on a single dataset (NExT-QA) for analysis. Therefore, it leads to the limited evaluation across different types of VideoQA tasks.
- The authors should discuss more how errors of code generation might affect the complexity metrics
- The human evaluation study uses only 150 questions, which is a relatively small sample
- We concern that the merging of subtrees that "always co-occur" could potentially miss important patterns in edge cases
- The manual filtering process for the generated dataset (removing 12% of questions) could introduce selection bias

questions:
- Why the authors do not validate the proposed approach on other VideoQA datasets besides NExT-QA?
- How do errors in code generation impact the complexity metrics?
- Are there any important patterns that might be missed by your current subtree merging approach?
- What specific criteria were used to manually filter out the 12% of questions?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730777925845

thread_type:
official_review

<thread_object>
creator: reviewer_rwyy

<content>
summary:
This paper introduces an approach to analyzing and generating complex questions for Video QA. The authors propose the use of generated code complexity as a metric to evaluate question difficulty. They introduce "CodePlexity," a novel algorithm that analyzes generated code's structure and content to identify patterns that make questions challenging for ML models. This allows the creation of a new VideoQA dataset named "CodePlex-QA" which features more complex questions than existing datasets without relying on human expertise.

strengths:
-	The paper introduces a novel and interesting approach using code complexity to evaluate question complexity.
-	The paper offers interesting insights into the differences in human evaluation, text-based and code-based evaluation.
-	The experiment results show clear empirical evidence to support the claims.

weaknesses:
Please see the question section below

questions:
-	The paper represents subtrees in question code using simple one-hot encoding without additional processing, which might ignore the frequency of subtrees and their structural relationships. Additionally, this representation can be very sparse. How does this affect CodePlexity's performance?
-	To what extent does the choice of code generation model affect the method's results? Would using different code generation models lead to identifying different patterns of complexity, and how might this impact the method's consistency?
-	Since the method evaluates difficulty without considering visual information, there might be cases where code generation is challenging due to question ambiguity, but the task would be straightforward with visual context. Is CodePlexity truly measuring question difficulty, or is it primarily measuring code generation complexity?
-	Most models evaluated in the paper are large video-language models built upon language model architectures. Since these models share similar language model foundations with the code generation approach, they might inherently struggle with the same types of questions that are difficult for code generation. Does this architectural similarity explain their correlated performance? How well would the method generalize to fundamentally different architectures that might employ different reasoning mechanisms?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732255699543

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response

comment:
We sincerely thank the reviewers for their thoughtful feedback and valuable suggestions. We have carefully addressed each comment individually and would like to take this opportunity to summarize the contributions of our work and clarify its scope.

It is hard to define what constitutes a good review in a few words, but one of the best definitions we have heard goes as follows: “A good review does not judge a paper based on what it is **NOT** (i.e. what a reviewer wishes it was), but rather based on what it **IS** (i.e. the value it brings to the community)”. We hope the reviewers and the AC can agree with this simple definition.

With this in mind, here are a few things our work is **NOT**:
1. Our metric does not capture the ‘inherent complexity of questions’ in VideoQA (Reviewer EhtB). Instead, it quantifies question complexity for existing models.
2. Our metric does not represent all the aspects of complexity in VideoQA (Reviewers RWYy, Hrka), focusing solely on question complexity instead. 

We never claim any of these contributions in the paper. 

In contrast, here are a few things our work **IS**:
1. It provides a novel perspective on question complexity analysis to the community that has struggled to achieve progress [4, 21, 33], and is in need of fresh insights.
2. It proposes a practical and operationalizable metric for estimating question complexity in VideoQA, which outperforms all the alternatives and indeed is more effective than humans at this task (see our analysis in Section 4.2).
3. It provides an automatic pipeline for generating challenging questions based on the proposed metric, which is used to construct a new VideoQA benchmark.

We humbly argue that these contributions make our work a meaningful addition to the VideoQA research community.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733275121546

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers,

We deeply appreciate your thoughtful feedback and constructive engagement, which helped to improve our paper. Below, we summarize our core contributions and highlight the results provided during the rebuttal process that validate and expand upon these contributions.

### **Key Contributions:**

Our work introduces a **data-driven framework for estimating question complexity in VideoQA**, consisting of:

1. **CodePlexity Metric:** A practical, interpretable, and adaptable metric that assesses question complexity using visual program generation.
2. **Insights Into Model Limitations:** Identification of shared failure modes across state-of-the-art VideoQA models, offering actionable insights to guide future research.
3. **Benchmark Generation:** A methodology for creating datasets, such as CodePlex-QA, that systematically surface questions challenging for current VideoQA models.

Our framework does not propose a fixed definition of “true complexity” but instead offers a systematic, adaptable tool for evaluating model-specific challenges in VideoQA. By identifying failure modes common to diverse models, we provide actionable insights to guide future research. As new datasets and models emerge, our framework can be reapplied to identify fresh challenges, ensuring sustained progress in the field.

---

### **Key Insights from Rebuttal Results:**

During the rebuttal period, we validated the robustness and generalizability of our approach:

1. **Diverse Code Generation Models:** We evaluated our framework with the recent RVP CodeGen model in place of ViperGPT. This analysis demonstrated that using a more advanced visual programming model improves the predictive power of code-based metrics, reinforcing the argument that code serves as a robust proxy for question complexity in VideoQA.
2. **Wide Range of VideoQA Architectures:** By testing CodePlexity on diverse VideoQA models such as HGA and Tarsier, we confirmed its applicability across a wide range of architectural approaches. These results reaffirm that our metric captures shared challenges across fundamentally different model designs.
3. **Generalization to New Datasets:** We extended our evaluation to MVBench, a recent dataset with unique characteristics. On MVBench, CodePlexity showed strong correlation with question complexity across multiple models, including LLaVA-NeXT and VideoChat2 (state-of-the-art on MVBench). Our metric outperformed a wide array of code-based and language-based complexity metrics, demonstrating its effectiveness across diverse data sources.
4. **Robustness to Code Generation Errors:** We further analyzed the impact of code generation errors, showing that CodePlexity remains robust and outperforms other metrics even when the generated code contains inaccuracies. This highlights its practicality in real-world scenarios where code generation may not be flawless.

Our rebuttal reinforces the central claim of this work: **CodePlexity is a robust, generalizable, and practical tool for advancing VideoQA research**. By systematically identifying shared challenges and providing a foundation for generating new benchmarks, our framework offers a scalable path toward tackling foundational challenges in VideoQA.

We hope the reviewers will recognize the strengthened contributions and validated applicability of our work in guiding future advancements in this domain.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a new method for evaluating question complexity in Video Question Answering by leveraging the programs generated by ViperGPT. The authors analyze these code outputs and use them to assess the difficulty of questions in a VQA triplet. To achieve this, they propose CodePlexity, an algorithm that processes the generated code through Abstract Syntax Trees (AST), identifies valid subtrees, and scores them based on their correlation with challenging questions. While the reviewers agree that the paper is well-written and using ASTs to evaluate visual program code is a promising direction, the reviewers raised several points weaknesses of the paper: In particular, the core point of using ViperGPT as the proxy for the evaluation of question complexity, given ViperGPTs relatively low performance, as well as the robustness of the proposed approach.