# Understanding Complexity in VideoQA via Visual Program Generation

arXiv: https://arxiv.org/abs/2505.13429 · HTML: https://mlsanity.com/paper/2505.13429/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 55 of its 86 references that are in the map.
- First posted on arXiv 19 May 2025.

## Builds on (most cited first, 30 of 55)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Visual Instruction Tuning](https://mlsanity.com/paper/2304.08485/) (2023)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [Improved Baselines with Visual Instruction Tuning](https://mlsanity.com/paper/2310.03744/) (2023)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Is Space-Time Attention All You Need for Video Understanding?](https://mlsanity.com/paper/2102.05095/) (2021)
- [CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning](https://mlsanity.com/paper/1612.06890/) (2016)
- [HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face](https://mlsanity.com/paper/2303.17580/) (2023)
- [MVBench: A Comprehensive Multi-modal Video Understanding Benchmark](https://mlsanity.com/paper/2311.17005/) (2023)
- [Dense-Captioning Events in Videos](https://mlsanity.com/paper/1705.00754/) (2017)
- [NExT-QA:Next Phase of Question-Answering to Explaining Temporal Actions](https://mlsanity.com/paper/2105.08276/) (2021)
- [EgoSchema: A Diagnostic Benchmark for Very Long-form Video Language Understanding](https://mlsanity.com/paper/2308.09126/) (2023)
- [ViperGPT: Visual Inference via Python Execution for Reasoning](https://mlsanity.com/paper/2303.08128/) (2023)
- [Hollywood in Homes: Crowdsourcing Data Collection for Activity Understanding](https://mlsanity.com/paper/1604.01753/) (2016)
- [Visual Programming: Compositional visual reasoning without training](https://mlsanity.com/paper/2211.11559/) (2022)
- [Socratic Models: Composing Zero-Shot Multimodal Reasoning with Language](https://mlsanity.com/paper/2204.00598/) (2022)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [InternVideo: General Video Foundation Models via Generative and Discriminative Learning](https://mlsanity.com/paper/2212.03191/) (2022)
- [Neural Module Networks](https://mlsanity.com/paper/1511.02799/) (2015)
- [GPTScore: Evaluate as You Desire](https://mlsanity.com/paper/2302.04166/) (2023)
- [Visual Classification via Description from Large Language Models](https://mlsanity.com/paper/2210.07183/) (2022)
- [MERLOT: Multimodal Neural Script Knowledge Models](https://mlsanity.com/paper/2106.02636/) (2021)
- [Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding](https://mlsanity.com/paper/1810.02338/) (2018)
- [Action Genome: Actions as Composition of Spatio-temporal Scene Graphs](https://mlsanity.com/paper/1912.06992/) (2019)
- [STAR: A Benchmark for Situated Reasoning in Real-World Videos](https://mlsanity.com/paper/2405.09711/) (2024)
- [Self-Chained Image-Language Model for Video Localization and Question Answering](https://mlsanity.com/paper/2305.06988/) (2023)
- [Competence-based Curriculum Learning for Neural Machine Translation](https://mlsanity.com/paper/1903.09848/) (2019)

## Built on by (most cited first, 3 of 3)

- [Linear Scaling Video VLMs for Long Video Understanding](https://mlsanity.com/paper/2605.31598/) (2026)
- [An Attribute-Based Measure of Video Complexity](https://mlsanity.com/paper/2606.00640/) (2026)
- [DAEP: Difficulty-Aware Evidence Planning for Medical Video Corpus Temporal Answer Grounding](https://mlsanity.com/paper/2608.06869/) (2026)

## Abstract (arXiv)

We propose a data-driven approach to analyzing query complexity in Video Question Answering (VideoQA). Previous efforts in benchmark design have relied on human expertise to design challenging questions, yet we experimentally show that humans struggle to predict which questions are difficult for machine learning models. Our automatic approach leverages recent advances in code generation for visual question answering, using the complexity of generated code as a proxy for question difficulty. We demonstrate that this measure correlates significantly better with model performance than human estimates. To operationalize this insight, we propose an algorithm for estimating question complexity from code. It identifies fine-grained primitives that correlate with the hardest questions for any given set of models, making it easy to scale to new approaches in the future. Finally, to further illustrate the utility of our method, we extend it to automatically generate complex questions, constructing a new benchmark that is 1.9 times harder than the popular NExT-QA.