Understanding Complexity in VideoQA via Visual Program Generation

Thank you for your detailed review and suggestions. We appreciate your recognition of the novelty, clarity, and effectiveness of our approach, and of the extensiveness of our theoretical and empirical analysis. We respond to your comments below.

---

Applicability beyond VideoQA.

Indeed, our approach is, in principle, applicable to any QA domain. To illustrate this, we analyzed the GQA image QA benchmark (Hudson et al., CVPR'19), generating programs with ViperGPT. For consistency, we evaluated BLIP-2 (Li et al., ICML'23) (analogous to SeViLA) and ViperGPT. We found that the overall complexity of generated programs is significantly lower in images (10% of programs with cyclomatic complexity above 5 vs.~45% in NExT-QA). As a result, the relationship between cyclomatic complexity and model performance is much stronger in VideoQA than in ImageQA (coefficient of determination R² of 0.75 vs. 0.39).

Intuitively, this difference in program complexity is not surprising, as answering a question in a video typically requires analyzing more content than in a single image. In the case of NLP, the underlying tasks often involve even simpler reasoning patterns. E.g., the multi-step reasoning chains in HotPotQA are linear, and the dataset collected to evaluate HuggingGPT (Shen et al., NeurIPS'23) has fewer than 2 module calls per prompt on average, and in simple patterns.

These findings suggest that while CodePlexity is broadly applicable, its most significant utility lies in VideoQA, where the reasoning complexity is significantly higher and model failure modes are more nuanced. We will include these results, along with a discussion on broader applicability, in the manuscript.

---

Code generation model.

Indeed, the specifics of the CodeGen model used—such as module granularity and few-shot examples—affect the generated programs, which affects subtree encodings. Importantly, Section 10.3 shows our approach generalizes to different CodeGen models.

(i) Effect of function granularity: This question is particularly insightful. In the extreme, if all questions mapped to a single VideoQA function, our complexity metrics would assign the same score to every question, losing all discriminatory power. Conversely, more granular functions enable finer-grained analysis—e.g. distinguishing whether models struggle more with “why” or “how” questions. This relates to our discussion above. We’ll add this to the paper.

(ii) Impact of few-shot examples: We use the official ViperGPT prompts and examples. We show our approach generalizes across different visual programming models in Section 10.3, despite changes in the APIs and modules. Similarly, Section 10.2 shows CodePlexity is more robust to code gen errors than the baselines. Thus, we expect that changes in the few-shot examples would not significantly alter the overall trends.

---

Dataset construction ablation.

Thank you for this insightful suggestion. Please note that we have already provided an ablation of a part of our dataset construction pipeline in Section 10.1, where we show that applying our selection algorithm to the existing questions in NeXT-QA results in a more challenging subset. However, this does not isolate the video source effects.

To address this, following your suggestion, we now adapt our pipeline to use the same videos from VidOR (Shang et al., ICMR'19) as NExT-QA. To generate the questions, we use VidOR annotations and augment them with annotations from VidSTG (Zhang et al., CVPR'20) and captions generated by ChatGPT (Zhang et al., arXiv'24). We then apply our full pipeline without modifications to obtain CodePlexQA-VidOR. Finally, we evaluate the same baseline models and report the results below.

As the table shows, CodePlexQA-VidOR remains consistently more difficult than NExT-QA across all models, despite using identical video sources. CodePlexQA-Vidor is slightly easier than our original CodePlexQA, both because of divergent data sources and because the less detailed VidOR scenegraphs limit the expressivity of the generated questions. This confirms that while video source contributes to overall dataset characteristics, the key driver of difficulty is our question generation and selection methodology, not merely differences in video content.

---

Explanation of logistic regression training.

Thank you for bringing that up. Each question-subtree pair does have multiple labels (one per model in the training set), but we average them into a single soft label. The logistic regression model is then trained on these, allowing it to capture consensus across the different models. We will clarify this in the Methodology section.

Thank you for your review and valuable feedback. We address your comments individually below.

---

On defining complexity via model performance

We appreciate your perspective that human perception plays a fundamental role in defining question difficulty. However, our work does not claim that model performance alone defines question complexity in a universal sense. Instead, it offers a systematic, adaptable tool for uncovering common failure modes across a diverse set of VideoQA models. This is especially useful for benchmarking and diagnosing model capabilities — areas where human intuition can be inconsistent or coarse-grained.

Our approach does not preclude human judgment, but augments it with an automatic, scalable metric that is sensitive to the kinds of reasoning models struggle with. We strive to make this clear throughout the paper (e.g., see L026-027 in the abstract, or L077-080, L101-104 in the introduction). If there are specific instances where our framing could be improved, we would greatly appreciate any suggestions on how to refine them further.

---

Clarifying Table 1

Thank you for the detailed feedback. As described in L230-240 in Section 4.1, models are split into training and validation sets ($M_{tr}$ and $M_{val}$) to assess the generalization of complexity metrics. “Train Models” refers to models whose outputs are used to learn metrics like CodePlexity and fine-tuned BERT, while “Val Models” are held out for evaluation. This protocol ensures that the learned metrics do not overfit to specific architectures or training signals. To improve clarity, we will update the caption of Table 1 to explicitly define Train and Val Models, ensuring readers can easily interpret the results.

---

Results with more recent VideoQA models

We include models across architectural types (graphNN-based, transformer-based, codegen-based) and training paradigms (supervised, contrastive, zero-shot). Please note that Tarsier was the state-of-the-art zero-shot model on NExT-QA at the time of writing, and it shares architectural principles with methods like LLaVA-Video. In response to your suggestion, we have now added LLaVA-Video to our analysis and report the updated Tables 1 and 2 below. The new results further support our claims that CodePlexity is an effective question complexity metric (Table 1) and that our CodePlexQA benchmark is challenging for a wide spectrum of VideoQA models (Table 2). We will include the updated tables in the final version of the manuscript.

Table 1: Comparison of question complexity metrics using mPEG on the validation set of NExT-QA. BERT and CodePlexity are trained on the first four models ($M_{tr}$).

Table 2: Difference in prediction accuracy between the manually annotated NExT-QA and our automatically generated CodePlexQA for a representative set of zero-shot VideoQA models.

We will move the MVBench evaluation, including LLaVa-next results, to the main paper.

---

Using CodePlex-QA for training

Thank you for this insightful suggestion. To investigate this, we have split CodePlex-QA into train and val and fine-tuned SeViLA. We observed that training on CodePlex-QA indeed can help improve the performance of VideoQA models (accuracy increases from 44.8 to 47.3). However, the gap is narrower compared to fine-tuning the same method on NExT-QA (accuracy improvement from 64.2 to 73.4). This suggests that our analysis uncovered deeper reasoning limitations in existing VideoQA approaches, which may not be easily resolved by simply increasing the amount or diversity of the training data. We will include these results, along with additional discussion, in the final version of the manuscript.

Thank you for your thoughtful and encouraging review. We appreciate your recognition of the novelty, clarity, and potential impact of our approach. We respond to your questions and concerns individually below.

---

Model-specific vs intrinsic difficulty.

We acknowledge that our metric does not aim to capture an intrinsic notion of question complexity. Instead, it offers a systematic, adaptable tool for uncovering common failure modes across diverse VideoQA models (see L026-027 in the abstract, or L077-080, L101-104 in the introduction). This is a deliberate design choice. To the best of our knowledge, no universally accepted definition of "intrinsic question difficulty" in VideoQA exists, and all heuristic-based attempts to define it so far have not stood the test of time [1, 2, 3]. Rather than seeking an elusive 'intrinsic' complexity measure, our approach provides empirical insights grounded in real model behavior. This makes it a valuable complement to any future efforts to define question difficulty more formally.

---

Influence of the code generator on the complexity metric.

The choice of code generation model is indeed an important factor in our methodology. To investigate this, we have analyzed the robustness of code-based complexity metrics to code generation errors in Section 10.2 and re-ran our experiments using the recent RVP CodeGen approach (Ge et al., 2024) as a substitute for ViperGPT in Section 10.3. The results demonstrate that, while program correctness does affect the predictive power of code-based metrics, CodePlexity is a lot more robust to code generation errors than the baselines. Moreover, the performance of code-based metrics can benefit from advancements in visual programming models, as they can provide richer and more accurate program representations.

---

How can we ensure the benchmark remains reliable as models improve?

Ensuring benchmark relevance over time is a well-known challenge in machine learning, and we have designed our approach with this in mind. Specifically, our work does not introduce a fixed benchmark, but rather a data-driven framework for estimating question complexity in VideoQA. This framework enables the automatic generation of challenging benchmarks that evolve alongside advancements in model capabilities. Unlike static, human-designed datasets, our method allows the complexity metric to be recomputed and the dataset to be regenerated as new models emerge. This adaptability ensures that CodePlex-QA remains a relevant and challenging evaluation tool as the field advances.

Furthermore, as demonstrated in Sections 4.2 and 10.4, our approach generalizes across datasets and model families—including recent video-language models like Tarsier and LLaVA-NeXT. This indicates that our method is not overly dependent on any single model or model family, further reinforcing its reliability as models continue to evolve.

---

Without a stable, model-agnostic definition of difficulty, how can future researchers rely on the benchmark?

We appreciate the importance of this question for ensuring meaningful evaluation over time. While our method does not define complexity in an absolute, model-agnostic sense, we argue that such a definition is not only difficult to establish but may also be fundamentally impractical. Unlike domains such as mathematics or logic, where problem complexity can be grounded in formal systems, VideoQA involves rich, ambiguous, multimodal inputs where “difficulty” is inherently contextual and model-dependent.

Rather than attempting to define question complexity in the abstract, our goal is to offer a practical, empirical, and extensible framework for estimating it based on observed model behavior. CodePlexity is intentionally data-driven: by analyzing model failures, we can surface interpretable, reproducible signals of what these models find challenging. As models evolve, the complexity metric can be re-learned to reflect their capabilities. By continuously adapting to emerging models, our approach ensures that future researchers can still use it as a meaningful evaluation tool, precisely because it is not fixed in absolute terms.

---

References:

[1] Buch, Shyamal, et al. "Revisiting the "video" in video-language understanding." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2022.

[2] Huang, De-An, et al. "What makes a video a video: Analyzing temporal information in video understanding models and datasets." Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018.

[3] Liu, Xin, et al. "No frame left behind: Full video action recognition." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2021.

Thank you for the thoughtful and constructive feedback. We are encouraged by your positive assessment of our method's novelty and its potential impact on the VideoQA community. We respond to your questions and concerns individually below.

---

“Gold” vs model-specific question complexity

We acknowledge that defining question complexity is inherently challenging, and our approach does not aim or claim to provide a definitive measure. Instead, it offers a systematic, adaptable tool for uncovering common failure modes across a diverse set of VideoQA models. We try to be explicit about this in the paper (e.g. see L026-027 in the abstract, or L077-080, L101-104 in the introduction). If you have specific concerns about our phrasing, we would greatly appreciate any suggestions on how to make this distinction even clearer.

---

The role of the visual information

We agree that visual content can influence question difficulty. While our focus is on question-based complexity estimation, we provide both theoretical and empirical analysis of incorporating visual content in Section 9.1 of the supplement. Specifically, we show that video statistics (e.g., number of entities in a frame) correlate with residual difficulty not explained by CodePlexity. That is, as you suggested, visual features can complement our question-centric metric and serve as a promising avenue for further research. Importantly, our method achieves strong predictive performance even without incorporating visual features, highlighting its efficiency and applicability.

---

Given the same question, complexity can vary across videos

This is a great point and is closely related to our discussion of the role of the visual information above. As you mentioned, this limitation arises from the fact that current visual programming methods do not incorporate video information when generating programs. Addressing this, we see two promising directions: (1) adjusting text-based complexity estimation using video features (as we explored in Section 9.1), or (2) incorporating video content directly into the code generation process to improve program accuracy, with the latter approach being more principled. Our results in Section 10.3 in the supplementary demonstrate that advances in visual programming methods directly translate into improved predictive power of code-based metrics, and we expect that incorporating video information in them would significantly enhance our approach.

---

Visual programming methods’ performance on NExT-QA and MVBench

We report ViperGPT’s performance on NeXT-QA in Table 2 in the main paper. As expected, it underperforms compared to the most recent VideoQA models, but still outperforms earlier methods like InternVideo. Note that Section 10.2 shows that even imperfect programs produce useful complexity signals. Our proposed CodePlexity metric demonstrates strong robustness to the correctness of the programs used in the analysis, reinforcing its reliability.

Following your suggestion, we have now evaluated ViperGPT and RVP on MVBench, where they achieve accuracies of 38.4% and 35.0%, respectively. For reference, these are comparable to recent approaches such as GPT-4V (run with 16 frames as input at 512×512 resolution), which obtains 43.5%, and VideoChat [1] (also with 16 frames), which achieves 35.5%. This further highlights the relative effectiveness of code-generation-based methods in VideoQA. We will include these results in the final version of the manuscript.

---

References:

[1] Li, KunChang, et al. "VideoChat: Chat-centric video understanding." arXiv preprint arXiv:2305.06355 (2023).

---