Research map / Vision-language and multimodal / Visual question answering

Understanding Complexity in VideoQA via Visual Program Generation

ICML 2025 · Vision-language and multimodal › Visual question answering · approach: Multimodal question answering datasets · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes CodePlexity, a data-driven metric that uses subtrees of LLM-generated visual programs to estimate VideoQA question complexity, and uses it to build CodePlex-QA, a benchmark ~1.9x harder than NExT-QA.

Problem

Human judgments of which VideoQA questions are hard do not match model failures, and benchmark designers struggle to create genuinely challenging video questions. The paper seeks a data-driven, model-specific measure of question complexity.

Approach

Use the complexity of LLM-generated visual programs (code) as a proxy for question difficulty. CodePlexity mines AST subtrees that are statistically associated with failures across models and fits a logistic regression on their presence to score questions, then uses the score to filter generated questions into a harder benchmark.

Key results

• CodePlexity achieves mPEG of 26.7 on SeViLA and 25.6 on SeViLA ZS, exceeding cyclomatic complexity (18.2 and 17.2) and dependency-tree and GPT-4 text baselines on NExT-QA validation.
• CodePlex-QA is 1.9x harder than NExT-QA, with LLaVA-Video accuracy 65.0% vs 82.5% on NExT-QA and VIOLET at 27.6% vs 37.7%.
• Human complexity judgments correlate weakly with model success rates, while cyclomatic complexity correlates more strongly (R-style trend in Figure 3).

Measured effects reported in the paper

Surprising findings

• Human estimates of question difficulty correlate only weakly with model success, and questions humans rank as average complexity were often the hardest for models.
• Text-based complexity measures (dependency depth, BERT, GPT-4 Likert) perform worse than even simple code metrics like lines of code.

Limitations

• Benchmark and analysis depend on biases of CLIP-based models, NExT-QA, and source datasets (MOMA, ActivityNet, Action Genome).
• Code-based complexity relies on the code generator's quality; metrics are affected by code correctness and generation used GPT-3.5 instead of Codex.
• Final dataset required manual filtering removing 12% of candidate questions for answerability.

Experimental setup

Datasets: NExT-QA MOMA ActivityNet ActivityNet-Entities ActivityNet-Captions Action Genome Charades ATP-Hard MVBench GQA

Benchmarks: NExT-QA CodePlex-QA ATP-Hard MVBench

Metrics: mPEG (Performance Extremity Gap) accuracy Spearman-style correlation with success rate

Baselines: Cyclomatic Complexity Lines of Code Dependency Tree Depth BERT complexity regressor GPT-4 Likert complexity ATP-Hard

Builds on: ViperGPT Cyclomatic complexity ATP Elo rating

Closest papers by meaning

• Explicitly Guided Difficulty-Controllable Visual Question Generation (AAAI 2025 · similarity 0.89)
• ActivityNet-QA: A Dataset for Understanding Complex Web Videos via Question Answering (AAAI 2019 · similarity 0.88)
• Exploring Question Decomposition for Zero-Shot VQA (NeurIPS 2023 · similarity 0.88)
• MoReVQA: Exploring Modular Reasoning Models for Video Question Answering (CVPR 2024 · similarity 0.87)
• When Open-Vocabulary Visual Question Answering Meets Causal Adapter: Benchmark and Approach (AAAI 2025 · similarity 0.86)
• FRAMES-VQA: Benchmarking Fine-Tuning Robustness across Multi-Modal Shifts in Visual Question Answering (CVPR 2025 · similarity 0.86)