Understanding Complexity in VideoQA via Visual Program Generation

Cristóbal Eyzaguirre, Igor Vasiljevic, Achal Dave, Jiajun Wu, Rares Andrei Ambrus, Thomas Kollar, Juan Carlos Niebles, Pavel Tokmakov · 2025

Read Understanding Complexity in VideoQA via Visual Program Generation by Cristóbal Eyzaguirre, Igor Vasiljevic, Achal Dave, Jiajun Wu, Rares Andrei Ambrus, Thomas Kollar, Juan Carlos Niebles, Pavel Tokmakov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-13429.txt.

Introduction

Cristobal Eyzaguirre and seven co-authors gauge how hard a video question is by the code a model writes to answer it. Past test design leans on human feel for hard, yet people guess model pain poorly. Code length and parts may track true pain more closely.

Code based scores track model scores far better than human guesses. An algorithm pulls the fine code parts that mark the hardest asks for any model set. It can also mint fresh hard questions on its own. A new test built that way proved near twice as hard as a famed video test.

Catalog record

CREATORCristóbal Eyzaguirre, Igor Vasiljevic, Achal Dave, Jiajun Wu, Rares Andrei Ambrus, Thomas Kollar, Juan Carlos Niebles, Pavel Tokmakov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-13429

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Understanding Complexity in VideoQA via Visual Program Generation Cristóbal Eyzaguirre, Igor Vasiljevic, Achal Dave, Jiajun Wu, Rares Andrei Ambrus, Thomas Kollar, Juan Carlos Niebles, Pavel Tokmakov Abstract 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. ceyzaguirre4.github.io/codeplexity Figure 1: Humans struggle to judge which questions present higher challenges for machine learning models. In our study, the question on the left is universally perceived as being easier than the one on the right, which is inversely correlated with the models’ performance. We show that the complexity of the corresponding visual program can serve as a much more reliable predictor. 1 Introduction Humans can effortlessly reason about activities, whether that reasoning requires understanding space and time, cause and effect, or fine-grained details and high-level context ( Decety & Grèzes 1999 ; Decety et al. 1997 ; Wurm & Caramazza 2022 ; Aflalo et al. 2020 ) . This versatility allows us to function effectively in dynamic environments, yet it simultaneously complicates our ability to assess what is hard for machines. Consider the two video-question pairs shown in Figure 1 (top). In our study, human subjects overwhelmingly perceive the question on the right as the more complex to answer, but evaluating a variety of state-of-the-art VideoQA models ( Yu et al. 2023a ; Wang et al. 2022a ; Surís et al. 2023 ; Fu et al. 2021 ) shows that the question on the left presents a significantly greater challenge for them. Experts might assume they would perform better at this task, but the history of VideoQA benchmarks suggests otherwise. Despite authors’ best efforts, studies show most datasets are dominated by questions solvable by naive, single-frame baselines ( Buch et al. 2022 ; Huang et al. 2018 ; Liu et al. 2021 ) . Although many attempts have been made to address this limitation, they predominantly adopt a top-down approach. These works start from an expert hypothesis of what is hard and validate this assumption by evaluating models on samples that specifically target the identified skill ( Xiao et al. 2021 ; Mangalam et al. 2023 ) . While this has led to some progress, such static, heuristic-based definitions of complexity are inherently myopic. In this work, we propose a bottom-up approach instead that discovers human-interpretable insights about the sources of complexity for VideoQA models from the data. To this end, we capitalize on a recent large language model (LLM)-based code generation paradigm ( Surís et al. 2023 ; Gupta & Kembhavi 2023 ; Subramanian et al. 2023 ) , which produces modular executable programs to answer natural language queries. While this approach has shown promise for zero-shot VideoQA ( Surís et al. 2023 ; Ge et al. 2024 ) , we are not interested in its task performance per se. Instead, we use its rich, structured intermediate representations—programs, as shown in Figure 1 (bottom)—to capture the elusive complexity of the original questions. Specifically, we begin by collecting visual programs generated by recent methods ( Surís et al. 2023 ; Ge et al. 2024 ) on the validation set of the challenging NExT-QA benchmark ( Xiao et al. 2021 ) , together with predictions of a large collection of diverse algorithms. We then calculate several standard structural complexity metrics ( McCabe 1976 ) for these programs and collect human judgments for a subset of the dataset. Intriguingly, our analysis demonstrates that, despite the programs being imperfect, standard code complexity metrics correlate better with machine learning models’ performance than human estimates (see Figure 3 ). Moreover, improvements in code generation result in stronger corelation (Figure 19 ), and these observations generalize between benchmarks (Figure 20 ). We then propose CodePlexity – a novel algorithm for estimating question complexity from code that takes into account the content of the program, in addition to its structure (Section 3.2 ). In particular, it learns to correlate individual subroutines with models’ performances, effectively mining for human-interpretable patterns that summarize the error modes of any given set of models. Crucially, like any data-driven approach, our CodePlexity metric is easy to extend to new models and datasets, ensuring sustained progress. This is in stark contrast to the static, heuristic-based definitions of complexity that are dominant in the field. Finally, to further demonstrate the utility of our analysis tool, we design an algorithm for automatically generating challenging questions for any given collection of videos in Section 3.4 . In particular, our approach takes as input a compact description of a video and uses an LLM ( OpenAI 2023a ) to generate question candidates first. We then generate visual programs for each question and use our code-based metric to select the hardest subset. We evaluate several zero-shot VideoQA methods on the resulting benchmark and observe a 1.9 \times gap in performance compared to existing datasets like NExT-QA ( Xiao et al. 2021 ) . To summarize, our contributions are as follows: (1) We demonstrate that generated code complexity is a robust, data-driven metric of question complexity in VideoQA, generalizing across code generation methods and datasets; (2) We present CodePlexity, an adaptable tool for evaluating model-specific challenges in VideoQA, identifying common failure modes and providing actionable insights for future research; (3) We use CodePlexity to automatically construct CodePlex-QA — a novel benchmark that is 1.9 times harder than the popular NExT-QA. 2 Related Work Large single-stage models. Current methods for video-language understanding explores various modeling strategies.HGA ( Jiang & Han 2020 ) uses Graph Convolutional Networks (GCNs) to align video and language. Merlot ( Zellers et al. 2021 ) leverages ASR-captioned videos for self-supervised training. VIOLET ( Fu et al. 2021 ) employs dVAE ( Van Den Oord et al. 2017 ) for masked video-text pretraining, evaluated on VideoQA and text-to-video retrieval. Masked space-time autoencoders, such as TimesFormer ( Bertasius et al. 2021 ) and VideoMAE ( Feichtenhofer et al. 2022 ) , focus on action recognition. mPLUG-2 ( Xu et al. 2023 ) unifies image- and video-language tasks with task-specific modules. More recently, large language model (LLM)-based approaches, such as Tarsier ( Wang et al. 2024 ) , LLaVA-NeXT ( Liu et al. 2024 ) , and VideoChat2 ( Maaz et al. 2024 ) , explore unified video-language modeling by extending the language model with visual adapters. Similarly, SeViLA ( Yu et al. 2023a ) follows this LLM-based paradigm but adds an additional stage for frame

Read the complete text