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
Venue: ICML 2025 poster (2025)
Keywords: videoqa
complexity
codegen
Primary area: applications->computer_vision

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.

Understanding Complexity in VideoQA via Visual Program Generation
Cristóbal Eyzaguirre'
Igor Vasiljevic?
Achal Dave? 2 Jiajun Wu² Rares Andrei Ambrus? Thomas Kollar?
Juan Carlos Niebles'
Pavel Tokmakov
eeyaguinne.gghhubioloooeeeeeee
Abstract
shown in Figure 1 (top). In our study, human subjects over- whelmingly perceive the question on the right as the more complex to answer, but evaluating a variety of state-of-th 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.
We propose data-driven approach analyz- ing query complexity in Video Question Answer- ing (V)deoQA). Previous efforts in benchmark design have relied on human expertise to de- sign challenging questions, yet we experimen- tally show that humans struggle to predict which questions are diffieult for machine learning mod- els. Our automatic approach leverages recent ad- vances in code generation for visual question swering, using the complexity of generated code as proxy for question difficulty. We demon- strate that this measure correlates significantly better with model performance than human esti- mates. To operationalize this insight, we propose 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 fur- ther illustrate the utility of our method, we ex- tend to automatically generate complex ques- tions, constructing a new benchmark that is 1.9 times harder than the popular NEXT-QA.
Experts might assume they would perform better at this task, but the history of VideoQA benchmarks suggests oth- erwise. 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; 8;; Liu et al., 2021). Although many attempts have been made to address this limitation, they predominantly adopt 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 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 al., 2023; Gupta & Kembhavi, 2023; Subramanian et al., 2023), which pro- duces modular executable programs answer natural lan- guage 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) capture the elusive complexity of the original questions.
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 con- text (Decety & Grèzes, 1999; Decety et al., 1997: Wurm & Caramazza, 2022: Aflalo et al., 2020). This versatility allows us function effectively in dynamic environments, yet it simultaneously complicates our ability to assess what is hard for machines. Consider the two video-question pairs
Specifically, we begin by collecting visual programs gen- erated 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 large collection of diverse algorithms. We then cal- culate several standard structural complexity metrics (Mc- Cabe, 1976) for these programs and collect human judg- ments for subset of the dataset. Intriguingly, our analysis demonstrates that, despite the programs being imperfect,
Stanford Computer Science "Toyota Research Insti- tute. Correspondence to: Cristóbal Eyzaguirre <ceyza- guirre stt.sssstaoorr.ddu.....
Proceedings of the 1nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(ss.

---

Understanding Complexity in VidcoQA via Visual Program Generation
Query: What does the dog do after latting go of the bone?
Query: Where is this?
for Evams An videos
Lutsing go
(vides
let qu started true
middle caption middle frame capticus
frane Lo_
Erame
Seoo__Atoer__treee staated Eraso
ansivez answer, petsorrrreeosooooo lon (quest widdle_ ooppeio,,, 2oomtior)
bresh desoriotion
Ecome after utaztedd contiions
Human Estimate: Easy!
Human Estimate: Hard!
CodePlexity Estimate: Hard
CodePlexity Estimate: Easy
SeViLA
SeviLAAz
X
ViperGPT
X
InternVidea
Violet
SoVILA
SeviLAZS
ViperGPT
InternVidea,
Figure I. 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 casier 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 a much more reliable predictor.
standard code complexity metries correlate better with ma- chine learning models' performance than human estimates (see Figure 3). Moreover, improvements in code generation result in stronger corelation (Figure 19), and these observa- tions generalize between benchmarks (Figure 20).
2. Related Work
Large single-stage models. Current methods for video- language understanding explores various modeling strate- gie (Jiang & Han, 2020) uses Graph Convolutional Networks (GCNs) to align video and language. Mer- lot (Zellers et al., 2021) leverages ASR-captioned videos for superviee training. VIOLET (Fu et al., 2021) em- ploys 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 Times- Former (Bertasius et al., 2021) and VideoMAE (Feichten- hofer et al., 2022), focus on action recognition. mPL.G- 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 Tar- sier (Wang et al., 2024), LLaVA-NeXT (Liu et al., 2024), and VideoChat2 (Maaz al., 2024), explore unified video- language modeling by extending the language model with visual adapters. Similarly, SeViLA (Yu et al., 2023a) fol- lows this LLM-based paradigm but adds an additional stage for frame selection, extending the select-then-answer ap- proach popularized by ATP (Buch et al., 2022).
We then propose CodePlexity a novel algorithm for es- timating question complexity from code that takes into ac- count 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 cumaaninterprettable 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 defini- tions 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 compact description of video and uses an LLM (OpenAI, 2023a) generate question candidates first. We then gen- erate visual programs for each question and use our code- based metric to select the hardest subset. We evaluate sev- eral zero-shot VideoQA methods on the resulting bench- mark and observe a 1.9x gap in performance compared to existing datasets like NExT-QA (Xiao al., 2021).
Code generation models. Recent works address frame se- lection and question answering via code generation, lever- aging text-to-code models like Codex (Chen et al., 2021). VisProg (Gupta & Kembhavi, 2023) decomposes natural language queries into compositional programs using zero- shot pretrained models. ViperGPT (Surís et al., 2023) gen- erates and executes Python code via a vision-API prompt, achieving of-te-of-the-art results without additional train- ing. Code (Subramanian et al., 2023), concurrent work, specializes in single-frame QA with smaller API. RVP (Ge et al., 2024) introduces recursive strategy to break down complex queries into subproblems. enhancing flexibility. Earlier models (Andreas et al., 2016; Johnson et al., 2017b; Kim et al., 2018; Hu et al., 2017; Yi et al., 2018) integrated code generation through supervised learn-
To summarize, contributions are 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 evalu- ating model-specifie challenges in VideoQA, identifying common failure modes and providing actionable insights for future research; (3) We use CodePlexity to automati- cally construct CodePlex-QA - novel benchmark that is 1.9 times harder than the popular NExT-QA.
2

---

Understanding Complexity in VidcoQA via Visual Program Generation
ing or reinforcement learning.
models perform worse on more complex questions.
Complexity estimation. Prior work has proposed ways to estimate complexity for other settings and modalities. In NLP, text complexity is often approximated by length (Pla- tanios et al., 2019; Spitkovsky et., 2010; Tay et al., 2019), with variations including conjunction count (Koemi & Bo- jar, 2017), phrase count (Tsvetkov et al., 201 and de- pendeney tree depth (Tsvetkov al., 2016b). In computer vision, image complexity has been linked to object count (Wei et al., 2016) or human annotations (Tudor Ionescu et al., 2016; Soviany et al., 2020). Finally, (Graves, 2016) suggested that, in reasoning tasks, complexity can be es- timated by the number of steps required by a recurrent model. Later (Eyzaguirre & Soto, 2020) used a similar ap- proach it to quantify the complexity of VQA questions.
However, directly estimating complexity C' from natural language question q is challenging problem even for hu- mans, as we demonstrate in Section 4.2. Instead, our key idea, inspired by the notion of Kolmogorov Complex- ity (KC) (Kolmogorov, 1963), is to utilize the rich and highly highly-structured intermediate representations programs, to capture the elusive complexity of the original natural language queries. Concretely, we capitalize on the recent code generation-based methods (Surís et al.. 2023; Gupta & Kembhavi, 2023; Subramanian et al., 2023) that oper- ate in a 2-stage fashion: first, given a question a pro- gram generator 'T from a Large Language Model (LLM) is used to translate it into an executable program = = (()). An off-the-shelf execution engine like Python can then be used to produce an answer à ((v, 2). Running such an approach on dataset 'D results in set of programs P(D) = {21, #2, $2....,... 22...,,NN? EN}
Complexity from code. Measuring complexity through code has a rich history; Kolmogorov defines complexity based on the succinctness of the program that can repre- sent said object (Kolmogorov, 1963; Solomonoff, 2009). However, its incomputability limits its practical application (Zvonkin & Levin, 1970). Software engineering rely on tangible metries like cyclomatic complexity that measure the number of independent paths in program (McCabe, 1976), a computable yet less philosophically rich approach.
Next, in Section 3.2 we propose several techniques for code analysis of increasing intricacy and show how they can be used to build a function for question complexity estimation via code C(q) xx C(2). Then, in Section 3.3, we demon- strate how analysis of the generated code can help gain in- sights into the failure modes of VideoQA models. Finally, in Section 3.4 we discuss how such algorithms can be used to automatically construct challenging benchmarks.
Synthetic datasets play a key role in Video Question Answering by using symbolic programs to separate per- ception from reasoning (Johnson et al., 2017a; Grunde- McLaughlin et al., 2021; Yu al., 2023b; Wu et al., 2021). Grouping these programs into skill-hased families enables correlation of model performance with reasoning patterns. In contrast, we leverage code generation to estimate ques- tion complexity without costly annotations, extending to diverse question types. Our approach provides a direct, computable complexity measure, bridging theoretical and practical aspects of machine learning.
3.2. CodePlexity: Estimating Question Complexity from Code
As a first step we review existing software engineering met- rics that map code into complexity scores C(z) + R. In particular, we focus on Lines of Code (LoC) and Cyclo- matic Complexity (McCabe, 1976). The former simply correlates the number of lines in program with its com- plexity C(z) x |z), whereas the latter quantifies the number of thnearl--indppender paths through the source code and is denoted as C(=) = CC((). To minimize the impact of spurious factors, we pre-process the code by removing all the comments and empty lines first, and make sure to use the same set of basic primitives in all experiments. Both metrics are indicative of the code's structural complexity, with higher values suggesting more intricate control flow. However, they do not take the contents of the code into con- sideration, which, as we shown in Section 4.2, limits their predictive power.
3. Methodology
3.1. Preliminaries
We study the problem of estimating the complexity of questions in VidcoQA. We are given a dataset consist- ing of collections of videos, questions, and answers D = (V, Q, A,, along with a set of K models already trained on the task M- m Our goal then is to de- sign a function C that allows to categorize questions 9 E Q into groups based their complexity with re- spect to M. Crucially, we are interested in a general met- ric consistent across all models my E .M. Concretely, for any two questions qı, 92 E Q, together with corre- sponding videos U1, U2 E V, if C(q1) > C(z2). we ex- pect model performance P(m.q: q, v) to vary accordingly: P(m,, gi, 01) P(mj: 92, 02) Vmy E M, indicating that
To address this drawback, we propose a new method, Code- Plexity, illustrated in Figure 2. CodePlexity involves an- alyzing the components of the generated code that affect question complexity, considering both its structure and se- mantic content. More specifically, we develop compiler to parse each question's 's code into its basic syntactic ele- ments, creating a Abstract Syntax Tree or AST (Hoe et al.,
3

---

Understanding Complexity in VidcoQA via Visual Program Generation
Diipiing
CodeFlaxity
0.85
What was the teacher doing while he was playing the piano for the first time?
1Al Prime
"Dosiittin Itam wiile stobio playcla pusse" insuttyciis
cilii paggen quecsie lista, quesitin
Query
Code Generation
AST Generation
Subtree encoding Complexity Estimation
Figure 2. Estimating question complexity via code. Our approach to estimating question complexity involves converting the question into code, decomposing the pseudo-code into abstract syntax subtrees (St), before correlating subtree presence with model performance.
1986) T compile(z) with nodes N and edges E. In this model, nodes represent variables, functions, and con- trol structures, while the edges capture the logical and hier- archical relationships between them. The AST framework abstracts the code away from its syntax, allowing us to fo- cus on the underlying logic and structure. By generating ASTs for the entire dataset, obtain comprehensive set E P(D)), laying the ground- work for a deeper analysis of code complexity factors.
logistic regression model trained these one-hot encod- ings to predict the success of models m, E .M. Note that the training set effectively treats each (x;, (()) pair as a distinct instance, where 21") is the binary outcome for ques- tion with respect to model m, (1 for success, 0 for fail- ure). This approach is justified by our objective to identify subtrees that universally challenge the models, implying a structural complexity in the code that transcends specific models. We then obtain the final complexity function via:
T(D) = (compile(z))
Next, we mine T for common subroutines (recurring log- ical patterns or functions) that occur in the code. ASTs subroutines manifest as subtrees, which we denote as (N', E.), where N' C N, E' C E and V(u, v) E E", u E N' A N'. Importantly, not all subtrees constitute valid Python code, since they might fail to comply with Python's 's syntax rules. To systematically identify valid subtrees, we define a function G(T) that yields an unordered set of all valid subtrees of T. denoted as (TT) = {Si, S2,.... S. Considering the entire dataset, the collection of all valid subtrees across the dataset can be represented S(D) UT)T(D) G(T).
CodePlexity(3) - = -t-oowwx + b).
(3)
Next, we discuss how our subtree analysis approach allows to obtain deeper insights into the sources of complexity for existing VideoQA models.
3.3. Subtree Analysis
Unlike black-box box metrics, in addition to a numerical score, our approach also outputs interpretable set of subtrees that correlate with challenging questions. We now demon- strate how to identify subroutines that have high impact model performance, More specifically, we are interested in subtrees that are linked to a decrease in model my 's per- formance with a high degree of statistical significance (set at 0.99). To test this, we establish null hypothesis (HO) stating that the proportion of successes is the same with and without the subtree present:
Then, to avoid duplicates, we merge subtrees that always co-occur when one is a descendant of the other. Specif- ically, (merged (D) is defined as the subset of S(D) that excludes S2 if there exists a subtree S such that S₁ and S2 always co-occur and S2 is contained in S1 (see Section 7.1 for formal definition). The presence of specific subrou- tine within program's AST can be verified via subgraph isomorphism check:
HO: P(m;, IS S(D)) = P(mj,qq S(D)). (4)
Conversely, our alternative hypothesis posits that the pro- portion of successes without the subtree is greater, imply- ing that its presence hurts performance:
ISO(T, = S e G(T).
(1)
To aggregate the identified subtrees into a quantitative met- ric of complexity, we assign each subtree in Smergea (D) an index and encode each question q in the dataset using one-hot encoding x, RR(Smerga(PP),, where in index k of x; signifies the presence of subtree Sz in question's AST T,
HA: P(m,, 91 S(D) < P(my, g $ S(D)).
(5)
We conduct a one-sided test to evaluate these hypotheses and define a subset of subtrees, denoted as Smn, (D), for which their presence statistically correlated with de- crease in the performance of the model my:
1
if Sk)
Cik 0
(2)
otherwise
Sm, (D) = {S S(D) ((, < 0.01), (6)
This representation transforms the complex structure of code into a fixed-size vector, enabling straightforward ap- plication of machine learning models. We then employ a
where p(S. m2) denotes the corresponding p-value. Fi- nally, to identify the subroutines that are associated with
4

---

Understanding Complexity in VidcoQA via Visual Program Generation
performance decrease for multiple models, we consider the intersection of the sets:
define a thorough evaluation protocol and detail our exper- imental setup in Section 4.1. We then evaluate how the code-based metrics proposed in this work compare to hu- man subjects and several simple baselines in predicting the performance of a wide variety of contemporary approaches on the popular NexIQA benchmark in Section 4.2. We con- clude by performing a detailed analysis of the subroutines that show the strongest correlations with challenging ques- tions in Section 4.3.
S - n S,, (D).
(7)
MyEM
Identifying the specific subtrees that cause a decrease in models' performance allows us to obtain deeper insights into where and how they may falter. In Section 4.3, we perform this analysis for several state-of-the-ar art approaches and suggest areas for improvement in model design.
4.1. Experimental Setup
3.4. Learning to Ask Hard Questions
Evaluation protocol. Our goal to compare the predictive power of several approaches for estimating question com- plexity in VideoQA with respect to a variety of machine learning models .M on dataset D. Importantly, some of the metrics we study require training data in the form of questions paired with outcomes of a model my E &M on them (g.,, v,")) Thus split the whole pool of models M into the training Mer and held-out validation MMal sets and report results on the latter.
We now build on our code-based question complexity met- ric deseribed in Section 3.2, and propose method for auto- matically generating challenging question-answer pairs for any given set of videos. Concretely, our approach takes as input a set of videos V paired with natural language sum- maries C. We then follow prior work by (Mangalam et al., 2023) and prompt a large language model (LLM) to gener- ate question and answer candidates based on each summary individually q. = LLM (c, prompt). The exact prompts are listed in Section 7.4 of the appendix.
To quantitatively compare the effectiveness of different ap- proaches, some of which map a question to a numerical value corresponding to its complexity, whereas others di- rectly return an ordering of the questions, we propose a uni- fying metric, Performance Extremity Gap (PEG). In partic- ular, we first numerical complexity estimates to sort questions accordingly. We then measure the disparity in model mj's 's performance /' between the casiest and the hardest a% of the questions via:
Importantly, our approach is agnostic to the nature of C, which can either be annotated manually, or generated auto- matically. In this work, we take the latter approach and capitalize on existing datasets with scene graph annota- tions (Luo et al., 2021; 2022; Zhou et al., 2019; et al., 2020) paired with an image captioning model to generate natural language summaries of the video such that lan- guage model can understand them (Menon & Vondrick, 2022: Wang et al., 2022b; Zeng et al., 2023). We detail this algorithm in Section 8 of the appendix.
PFG(m);;))
1
Σ
P(mj. (4)
Na
gEQuatoa.a
Following our approach from Section 3.2, we then convert each generated question q into code, and use our trained CodePlexity model (Equation 3) to estimate its complexity. A set of candidate questions Q" can be selected by setting a threshold 5 for minimum complexity:
Σ
P(my.q.0.
N
qEQusiea.a
Finally, inspired by the mAP metric (Everingham et al., 2010), we average the PEG values over a E (0,0.5) to obtain the final mPEG score.
Q' = {g E Q((()) 2 63.
(8)
CodeGen Models. We leverage ViperGPT (Surís et al., 2023) our main approach for generating visual programs from questions. To investigate the influence of the Code- Gen model, we also re-ran our experiments with the recent RVP (Ge et al., 2024) approach (see Section 10.4).
Finally, we manually filter the candidate dataset D (V, Q", A+} to remove the question/answer pairs that can- not be accurately answered from the corresponding videos due to inaccuracies in the generated summaries or LLM hallucination. We emphasize that this final manual filter- ing only needed to ensure the perfect quality of the final dataset D* In practice, we only had remove 12% of the questions, demonstrating that the fully automatic pipeline is capable of producing useful datasets by itself.
VidcoQA Models. We ground our complexity metric in the performance of seven representative VideoQA methods, chosen for their coverage of existing architectural philoso- phies, pre-training strategies, and state-of ofte-of-the-an perfor- mance. In particular, we use VIOLET (Fu et al., 2021) and Intern Video (Wang et al., 2022a), which are pre-trained with contrastive lanualle objectives and fine-tuned for VideoQA We also evaluate Se (Yu et al., 2023a), which is based on the BLIP-2 (Li et al., 2023) large-scale
4. Evaluating Complexity Estimation
In this section, we compare different approaches to estimat- ing question complexity in VideoQA. To this end, we first
5

---

Understanding Complexity in VidcoQA via Visual Program Generation
Success Rate vs Human Annotater Score
Success Rate vs Dependency Parse Tree Max. Depth
Success Rate vs Cyclomatic Complexity
1.0
1.0
6.9
0.9
0.9
Tora
SeR.AZS
0.7
0.6
0.6
0.6
FCA
0.5
0.5
62
02
0.2
Human Annotater Score
Dependency Purse Tree Mac. Depth
Cydteaaicc Complecty
Figure 3. Correlation of various approaches for estimating question complexity with VideoQA models' success rate on these questions. We observe that humans struggle to accurately predict what is hard for machine learning models and that code can serve as a more reliable source of prediction than natural language questions.
visual-language model; we assess both its zero-shot vari- ant (SeViLA-ZS) and a fine-tuned version (SeViLA), Ad- ditionally, we evaluate HGA (Jiang & Han, 2020), a GNN- based model for video reasoning, representing earlier ap- proaches prior to the prevalence of video large language models (videoLLMs). We also evaluate the simple but ef- fective ATP baseline (Buch et al., 2022), model inten- tionally restricted to processing only a single frame. Fur- thermore, we include the results from executing the pro- grams generated by ViperGPT (Surís et al., 2023). Fi- nally, we evaluate the recent state-of-the-ar model, Tar- sier (Wang et al., 2024), and the current state-of-the-ard model LLLVa-Vides (Zhang et al., 2024). The mod- els are split into training and validation sets as follows: MMer = [VIOLET, SeViLA, ViperGPT,, ATP), Muat {HGA, Se ViLL-ZZ,, Intern Video, Tarsier, LLa Va- Video}.
& Toutanova, 2019) to predict the probability of model success given the question using exactly the same train- ing data. We also prompt GPT-4 (OpenAI, 2023b) to esti- mate the complexity of a question on Likert scale (Likert, 1932). Details and prompts are provided in Section 7.3.
Finally, we conduct human study subset of 150 ques- tions. To this end, we recruited 30 human subjects via the Prolific platform (Palan & Schitter, 2018). The subjects were asked to sort three questions at a time according to their perceived relative complexity. The final sequence or- der of the entire subset was calculated via pairwise ELO scores (Elo, 1967). More details and an example of the an- notation interface are provided in Section 7.2.
4.2. Results
We begin by visualizing the correlation of human estimates of question complexity with the performance of all 9 mod- els used in our study the manually annotated questions from NEXT-QA in Figure 3 (left). We observe that, while downward trend clearly exists, with the questions labeled as the hardest by humans resulting in lower success rate for models compared to the casiest ones, the correlation is very weak. Notably, the questions that are ranked as being average in complexity are in fact the hardest for the models.
Dataset. It is crucial that the dataset used to perform our analysis features as many diverse challenges as possible. We focus on the NEXT-QA (Xiao et al., 2021) benchmark for its size, variety of human-annotated questions, and its focus spatio-temporal reasoning in videos over mere visual-fact retrieval (Zhong et al., 2022). In addition, its popularity provides a large pool of models with pre-trained, public checkpoints for our study. We perform the evalua- tion on the validation set, further splitting the questions into 80% used train the metrics and the other 20% held out for computing mPEG. To assess generalizability, we also evaluated our method on the recent MVBench dataset (Li et al., 2024), including additional models such as LLaVA- NeXT (Liu et al., 2024) and VideoChat2 (Li et al.. 2024), in Section 10.5 of the appendix.
We then evaluate two baselines on the same set of ques- tions, one based on the natural language queries (depen- dency tree depth shown in Figure 3, center) and one based on the generated code (cyclomatic complexity, Figure 3, right). Both show a much stronger correlation with the models' performance, with cyclomatic complexity being the most consistent. These results demonstrate that human intuition about sources of complexity in VideoQA does not reflect the main challenges for machine learning models, and that generated code can be a more reliable source for estimating complexity than natural language.
Baselines. In addition to the code-based metrics introduced in Section 3.2, we evaluate several baselines that attempt to directly estimate question complexity from the natural language query itself. In particular, learning-frr free base- line, we follow (T'vetkov et al., 201 and correlate the complexity of a question with the maximum depth of its parsed dependency tree. To more fairly compare to our learnale, code-based metric we fine-tune BERT (Kenton
Next, we report a more systematic comparison of different text- and code-based metries using mPEG on the validation set of NExT-QA in Table 1. Comparing the three language-
6

---

Understanding Complexity in VidcoQA via Visual Program Generation
Train Models
Val. Models
SeViLA
ViperGPT
ATP
VIOLET
HGA
SeViLA ZS
Vndern
Tarsier
Va-VieVideo
Dependency Tree Depth
12.9
7.9
11.1
15.9
7.4
13.5
17.7
10.1
6.9
GPT-4 (OpenA1, 2023b)
9.6
8.9
11.6
5.8
7.8
14.6
13.9
10.8
5.2
BERT (Kenton & Toutanova, 2019)
12.5
6.0
18.3
17.3
7.7
14.3
21.1
10.8
11.4
Lines of Code
16.4
15.3
14.2
12.0
9.9
16.2
17.5
14.4
9.38
Cyclomatic Complexity
18.2
14.2
18.7
15.9
8.9
17.2
24.2
16.7
11.5
CodePlexity (Ours)
26.7
21.3
21.0
15.8
14.1
25.6
26.6
24.9
17.3
Table 1. Comparison of question complexity metrics using mPEG on the validatiin set of NEXT-QA, BERT and CodePlexity are trained using the outputs of the first four models (labeled Train in the table), and evaluated on the rest. Text-based metrics (above) perform worse than the code-based ones (below), and our approach demonstrates the highest correlation with the models' performance.
based metrics in the upper part of the table on the held-out models, we find them to perform similarly. Notably, the BERT-based model which is trained on the questions and prediction outcomes of the four models, performs better than the learning-free baselines for Intern Video and Lla Video, but fails to generalize to Ae.. This demonstrates that the space of the natural language is not structured enough to fit robust complexity estimation model.
ViperGPT, and VIOLET. In Figure 4 (right) we visualize the intersections between these three individual sets S* (Equation 7) as a Venn diagram. A perceptible common trend is apparent: different architectures have their own weaknesses, but the commonalities are surprisingly fre- quent. We manually inspect the eight subroutines that are shared among all three sets and identify that they represent two clear patterns (subtrees are listed in Section 9.3).
In contrast, code-based metrics, shown in the lower part of Table demonstrate better predictive ability overall, with even the simplest Lines of Code baseline outperforming the text-based metrics in most scenarios. Cyclomatic Com- plexity shows top results among all non-learning-ooe based metrics, and our proposed approach, CodePlexity, achieves significant improvements over it by learning to identify code primitives which correlate with challenging questions.
The first group of primitives, manifesting in such structures as those containing For loops with complex control flow in them, captures reasoning about not just the content of the frame, but also its placement in a sequence of events. We provide an example of corresponding subtree together with a question that requires this reasoning pattern in Fig- ure 4 (left). The second group contains primitives that rep- resent detailed analysis of specific elements (objects, rela- tionships) within a scene. The examples include questions that require identifying the precise placement of an object within a frame.
Notably, ViperGPT is the only model that executes gen- crated programs, making it more sensitive to code com- plexity - reflected in its declining success rate as program intricacy increases. Yet, intriguingly, similar declines are seen in models without access to code, suggesting our met- rics capture broadly challenging patterns across architec- tures and training regimes. Even cutting-edge models like Tarsier and LLaVa-Video struggle with questions flagged as hard by CodePlexity, despite it being trained on older models. In addition, while all code-based metrics are af- fected by code correctness (see Section 10.3), CodePlexity demonstrates the greatest robustness.
In summary, we discovered that VideoQA methods strug- gle with fine-grained temporal reasoning and lack spatio- temporal, object-centric representations. This is in ac- cord with prior studies (Buch et al., 2022; Huang et al., 2018; Liu et al., 2021) that demonstrated that naive, single- frame baselines can achieve top performance on main- stream VideoQA benchmarks, which were used to develop these methods.
Note that the granularity of the functions provided to the code generation model controls the specificity of the in- sights produced by our analysis tool. If too coarse - for instance, collapsing all questions into a single function it could lose the ability to differentiate between questions. In contrast, using finer-grained functions enables more nu- anced analysis. such as revealing if models tend to struggle more with "why" questions than with "how" questions.
In the next section, we apply the techniques introduced in Section 3.3 to identify the code structures responsible for this universal challenge to model performance.
4.3. Subtree Analysis
This brings us to the final aspect of our analysis: under- standing these structural elements of the code that con- tribute to question complexity. We follow the approach proposed in Section 3.3 and identify the subtrees which are statistically correlated with decrease in the performance Sin for three models out of out training set M SeViLA,
Next, we show how our approach can be used to automat- ically generate a new benchmark that challenges existing approaches.
7

---

Understanding Complexity in VidcoQA via Visual Program Generation
SeViLA
ViperGPT
55
30
50
What did the man sitting on top do after he came off the person on the ground?
QUERY:
28
VIOLET
Figure 4. Detailed analysis of subtrees that correlate with challenging questions among several models. We find that, although each model has its own error-modes, subroutines are shared among all of them (right). One the patterns we find then analyzing the shared code structures is reasoning about the order of events (left).
Dataset
Tarsier SeViLA ZS ViperGPT Intern VIOLET
Random
NEXT-QA 82.5%
70.9%
64.2%
60.0%
50.9%
37.7%
20.0%
ATP-Hard 77.6%
59.8%
54.9%
51.8%
24.6%
25.4%
20.0%
CodeplexQA 65.0%
52.5%
43.7%
45.8%
29.9%
27.6%
20.0%
Table 2. Difference in prediction accuracy between the manually annotated NEXT-QA, its adversarially selected subset ATP-Hard and our automatically generated CodePlex- QA for representative set of zero-shot VideoQA models. Our benchmark is empirically 1.9 times harder than NEXT-QA, validating the effectiveness of our complexity estimation approach.
5. Dataset Generation
jects in the videos. Following (Xiao et al., 2021) we gener- ate 5 answer candidates for each question (1 correct answer and 4 distractors), and use accuracy the evaluation met- ric. We set the 8 in Equation 8 to select the top 10% of the data according to the estimated complexity (calibrated on NEXT-QA). Further details are provided in Section 8
In this section, we apply our method to automatically create a new, challenging VideoQA benchmark, CodePlex-QA. We begin by detailing the source datasets and key imple- mentation details in Section 5.1. We then compare the performance of recent VideoQA methods on the popular NEXT-QA (Xiao et al., 2021) to that CodePlex-QA in Section 5.2 to validate the effectiveness of our approach. Our dataset will be released.
5.2. Results
To construct CodePlex-QA, we run the generation pipeline described in Section 3.4, obtaining 20791 candidate ques- tions (several question candidates are generated for each video). Then we calculate each question's complexity score using CodePlexity only retain questions that meet or exceed the minimum complexity threshold as in Equa- tion 8. The resulting datasets consists of 2261 questions. The final manual filtering to ensure the answerability of the generated questions removes only 12% of the candidates, leaving 1981 samples, all of which are used for evaluation.
5.1. Experimental Setup
Source datasets. We generate questions using 3 differ- ent datasets, all of which provide seene-graphs annotations: MOMA (Luo et al., 2021; 2022); ActivityNet (Caba Heil- bron et al., 2015), which we combine with ActivityNet- Entities (Zhou et al., 2019) and ActivityNet-Captions (Kr- ishna et al., 2017), and the ActionGenome (Ji et al., 2020) annotations for Charades (Sigurdsson et al., 2016). This results in pool of 4191 videos that are passed to our algo- rithm. Additionally, Section 10.2 of the appendix includes an ablation experiment that controls for video content while keeping the question generation pipeline unchanged. To this end, we use only videos from VidOR (Shang et al., 2019), matching those used to construct NEXT-QA.
We then evaluate the shot baselines from our pool of methods on CodePlex-QA and report their accuracy in Ta- ble 2. We also report the results on the popular NExT-QA benchmark and on ATP-Hard (Buch et al., 2022), an adver- sarial split of NEXT-QA, for reference. Note that the accu- racy of the random baseline is the same for all the bench- marks, so the numbers are directly comparable. We observe that that the accuracy on our generated questions is signif- icantly lower than on NEXT-QA. Specifically, CodePlex- QA is 1.9 times harder than the manually annotated NExT- QA (complexity estimated by averaging the accuracy of the methods and subtracting random chance).
Implementation details. We use GPT-4 (OpenAI, 2023b) to generate question and answer candidates following prior work by (Mangalam et al., 2023) and leverage a of the-art image captioning model, LLaVA 1.5 (Liu et al., 2023a;b), to list visual attributes of the main actors and ob-
8

---

Understanding Complexity in VidcoQA via Visual Program Generation
QUERY: What action does the barber perform most frequently?
QUERY: What does the man do after sofa?
QUERY: What was the person's reaction tripping the stairs?
A Washing heir
Leavas the sole to
Ai Thiyy and stogped willing
austherstt
loughed
C1 Combingharr
CI boo one unpanter sear curiion back theadda
Thes got angry and throw the book
Cy hut
DJ Cears ha supplis
Difrny aporedl it and walling
FiMarag
sparzer
Figure 5. Example questions in CodePlex- QA generated with our approach. It features many challenges that are under-represented existing, manually-designed benchmarks, motivating development of new approaches with enhanced spatio-temporal modeling capacity.
We further report models' performance on ATP-Hard, a subset of NExT-QA created using ground truth labels and specifically designed to be adversarial to CLIP-based mod- els. Despite this oracle nature of ATP-Hard, CodeplexQA is substantially more challenging for the top performing models and approximately equally hard for the weakest VI- OLET baseline. ATP-Hard is somewhat more challenging than CodeplexQA for Vntern because it is finetuned from CLIP and the samples in ATP-Hard specifically target CLIP-based models. These results support the effective- ness of both our complexity metric and of our automatic approach for generating VideoQA benchmarks.
Impact Statement
In our study, we utilize many distinct pre-trained mod- cls, each with its inherent biases, to identify challenging questions within an existing dataset. Although they have different pre-training schemes, these models likely encode similar implicit biases, owning to their training on internet scale data collections. In particular, several of our selected models, along with our visual descriptors extractor, rely on CLIP (Radford et al., 2021) as a visual encoder, meaning they likely replicate the same biases including those identi- fied in previous studies (Agarwal al., 2021).
Furthermore, the dataset we base the majority of our analy- sis on, NExT-QA (Xiao al., 2021), is not fully represen- tative of real-world diversity and complexity. This limita- tion in addition to the biases present in the chosen models can lead to skewed or incomplete analysis. In addition, our analysis' focus on interplay between the constituent syn- tactic elements in code may overlooks critical sources of complexity not apparent in the code structure. These in- clude, for example, differences related to gender and eth- nicity, which are not explicitly manifested in the code.
Figure 5 includes a representative sample of gener- ated questions that illustrate the variety of scenarios in CodePlex-QU They include questions that require fine- grained temporal reasoning (e.g., comparing the frequency of different actions), sequential event understanding (e.g. identifying actions that follow specific trigger events), well as reasoning about objects. Data-driven nature of our approach ensures that CodePlex-QA highlights under- represented challenges in undoo-understnndig More ex- amples are shown the video.
Our own proposed benchmark, CodePlex-QA builds upon the existing datasets MOMA (Luo et al., 2021; 2022), Ac- tivityNet (Caba Heilbron et al., 2015), and Action Genome (Ji et al., 2020), and therefore includes the same biases. We urge researchers and practitioners to refer to the relevant dataset cards. Finally, our selection methodology for filter- ing videos and questions may inadvertently introduce new biases, or amplify existing ones.
Further experiments that isolate and evaluate specific com- ponents of pipeline be found in the appendix. In particular, in Section 10.1 we validate our question selec- tion algorithm. Similarly. in Section 10.2 we isolate the impact of video source on dataset difficulty, confirming the effectiveness of our question generation approach.
6. Conclusion
This work is in part supported by the Toyota Research Institute (TRI), AFOSR YIP FA9550-23- 1-0127, ONR N00014-23-1-2355,, and ONR YIP N00014- 24-1-2117.
Acknowledgments.
We demonstrated that generated code complexity is an ef- fective measure of question complexity in VideoQA, in- troducing a novel metric that outperforms existing ones, Our approach identifies subroutines associated with diffi- cult questions across wide range of models, providing in- sights into key challenges in VideoQA. Finally, we have shown how our metric can be used to automatically gen- erate a novel benchmark CodePlex-QA. which is 1.9 times harder for existing models than the manually labeled NEXT-QA. As new methods are developed, our approach can be re-applied, ensuring continued progress in the field.
9

---

Understanding Complexity in VidcoQA via Visual Program Generation
References
Everingham, M., Van Gool, L.,, Williams, C. K., Winn, J., and Zisserman, A. The pascal visual object classes (VOC) challenge. International journal of computer vi- sion, 88:303-3333 2010.
Aflalo. T., Zhang, C., Rosario, E., Pouratian, N., Orban, G., and Andersen, R. A shared neural substrate for action verbs and observed actions in human posterior parietal cortex. Science advances, 6(43), 2020.
Eyzaguirre, C. and Soto, A. Differentiable adaptive com- putation time for visual reasoning. In CVPR, 2020.
Agarwal, S., Krueger, G., Clark, J., Radford, A., Kim, J. W., and Brundage, M. Evaluating CLIP: towards char- acterization of broader capabilities and downstream im- plications. arXiv preprint arXiv:2108.02811 2021.
Feichtenhofer, C., Li, Y., He, K., et al. Masked autoen- coders as spatiotemporal learners. NeurIPS, 2022.
Fu, J., Ng, S.-K., Jiang, 7., and Liu, P. GPTScore: Evaluate as you desire. arXiv preprint wxiiv2332..4116, 2023.
Andreas, J., Rohrbach, M., Darrell, T., and Klein, D. Neu- ral module networks. In CVPR, 2016.
Fu, T.-.,, Li, I.., Gan, Z.,, Lin, K., Wang, W. Y., Wang. L., and Liu, Z. VIOLET: End-to-end video-language transformers with masked visual-token modeling. arXiv preprint arXiv:2111 2021.
Bertasius, G., Wang, H., and Torresani, L. Is space-time at- tention all you need for video understanding? In ICML,, 2021.
Ge, J., Subramanian, S., Shi, B., Herzig, R., and Darrell, T. Recursive visual programming. In ECCV, 2024.
Buch, S., Eyzaguirre, C., Gaidon, A., Wu, J., Fei-Fei, L., and Niebles, J. C. Revisiting the "video" in video- language understanding. In CVPR, 2022.
Graves, A. Adaptive computation time for recurrent neural networks. In NIPS, 2016.
Byrd, R. H., Lu, P., Nocedal, J., and Zhu, C. A lim- ited memory algorithm for bound constrained optimiza- tion. SIAM Journal on scientific computing, 16(5):1190- 1208, 1995.
Grunde-McLaughlin, M., Krishna, R., and Agrawala, M. AgQA: A benchmark for compositional spatio-temporal reasoning. In CVPR, 2021.
Gupta, T. and Kembhavi, A. Visual programming: Com- positional visual reasoning without training. In CVPR, 2023.
Caba Heilbron, F., Escorcia, V., Ghanem, B., and Car- los Niebles, J. ActivityNet: A large-scale video bench- mark for human activity understanding, In CVPR, 2015.
Hoe, A. V. Sethi, R., and Ullman, J. D. Compil- ers ers-principles, techniques, and tools. Pearson Addison Wesley Longman, 1986.
Chen, M., Tworek, J., Jun, H., Yuan, Q. Pinto, H. P. d. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brock- man, G., et al. Evaluating large language models trained on code. arXiv preprint 1xXiv21107.03374 2021.
Hu, R., Andreas, J., Rohrbach, M., Darrell, T., and Saenko, K. Learning to reason: End-to-end module networks for visual question answering. In ICCV, 2017.
Chiang, W.-L., Li, Z., Lin, Z., Sheng. Y., Wu, Z., Zhang. H., Zheng, L., Zhuang, S., Zhuang, Y., Gonzalez, J. E., et al. Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality. See https://vicuna Imsys. org (accessed 14 April 2023), 2023.
Huang, D.-A., Ramanathan, V., Mahajan, D., Torresani, L., Paluri, M., Fei-Fei, L.,, and Niebles, J. What makes a Analyzing temporal information in video understanding models and datasets. In CVPR, 2018.
video a video:
Decety, J. and Grèzes, J. Neural mechanisms subserving the perception of human actions. Trends in cognitive sci- ences, 3(5):172-178, 1999.
Hudson, D. A. and Manning, C. D. GQA: new dataset for real- sal-world visual reasoning and compositional question answering. CVPR, 2019.
Decety, J., Grezes, J., Costes, N., Perani, D., Jeannerod, M., Procyk, E., Grassi, F,, and Fazio, F. Brain activity during observation of actions. influence of action content and subject's 's strategy. Brain: a journal of neurology, 120(10):1663-177) 1997.
Ji, J., Krishna, R., Fei-Fei, L., and Niebles, J. C. Action genome: Actions as compositions spatio-temporal scene graphs. In CVPR, 2020.
Jiang, P. and Han, Y. Reasoning with heteroge- neous graph alignment for video question answer- ing. In AAAI Conference on Artificial Intelligence, 2020. URL battps://api.stt / www.nti org/CorppusT::21336677
Elo, A. E. The proposed usef rating system, its develop- ment, theory, and applications. Chess Life, 22(8):242- 247, 1967.
10

---

Understanding Complexity in VidcoQA via Visual Program Generation
Johnson, J., Hariharan, B., Van Der Maaten, L.., Fei-Fei, L.,, Lawrence Zitnick, C., and Girshick, R. CLEVR: A diagnostic dataset for compositional language and ele- mentary visual reasoning. In CVPR, 2017a.
Luo, Z., Xie, W, Kapoor, S., Liang, Y., Cooper, M., Niebles, J. C., Adeli, E., and Li, F.E. MOMA: Multi- object multi-actor activity parsing, NeurIPS, 2021.
Luo, Z., Durante, Z. Li, L., Xie, W. Liu, R., Jin, E., Huang, Z., Li. Y., Wu, J., Niebles, J. et al. MOMA- LRG: Language-refined graphs for multi-object multi- actor activity parsing. NeurIPS, 2022.
Johnson, J., Hariharan, B., Van Der Maaten, L., Hoffman, J. Fei-Fei, L., Lawrence Zitnick, C., and Girshick, R. Inferring and executing programs for visual reasoning. In ICCV, 2017b.
Maaz, M., Rasheed, H., Khan, S., and Khan, F. VideoGPT+: Integrating image and video encoders for enhanced video understanding. arXiv preprint arXiv:2406.0944 09418,, 2024.
Kenton, J.
D. M.-W. C. and Toutanova, L. K. BERT: Pre- training of deep bidirectional transformers for language understanding. In naacL-IILT, 2019.
Kim, S. W., Tapaswi, M., and Fidler, S. Visual reasoning by progressive module networks. In JCLR, 2018.
Madaan, A., Tandon, N., Gupta, P., Hallinan, S., Gao, L., Wiegreffe, S., Alon, U., Dziri, N., Prabhumoye, S., Yang, Y., et al. Self-refine: Iterative refinement with self- feedback. NeurIPS, 2023.
Koemi, T. and Bojar, O. Curriculum learning and mini- batch bucketing in neural machine translation. In RANLP, 2017.
Mangalam, K., Akshulakov, R., and Malik, J. EgoSchema: A diagnostic benchmark for very long-form video lan- guage understanding. In NeurIPS, 2023.
Kolmogorov, A. N. On tables of random numbers. Sankhyā: The Indian Journal of Statistics, Series A, pp. 369-376, 1963.
McCabe, T. J. A complexity measure. IEEE Transactions Software Engineering, SE-2(4):308-332) 1976.
Kramer, O. and Kramer, O. Scikit-learn. Machine learning for evolution strategies, pp. 45-53, 2016.
Menon, S. and Vondrick, C. Visual classification via de-
Krishna, R., Hata, K. Ren, F. Fei-Fei, L., and Car- los Niebles, Dense-captioning events in videos. In ICCV, 2017.
scription from large language models. In ICLR, 2022.
OpenAl. 2023a.
Chatgpt.
httpps:/ww..opeeett com,
Li, J. Li, D., Savarese, S., and Hoi, S. BLIP-2: Bootstrap- ping language-image pre-training with frozen image en- coders and large language models. In ICMI, 2023.
OpenAL. GPT-4 technical report, 2023b.
Li, K., Wang, Y., He, Y., Li, Y., Wang, Y., Liu, Y., Wang. Z., Xu, J., Chen, G., Luo, P., et MVBench: compre- hensive multi-modal video understanding benchmark. In CVPR, 2024.
Palan, S. and Schitter, C. Prolific. a subject pool for online experiments. Journal of Behavioral and Experimental Finance, 17:22-27, 2018
Platanios, E. A., Streteu, O., Neubig, G., Poczós, B., and Mitchell, T. Competence-based curriculum learning for neural machine translation. In ACL, 2019.
Likert, R. A technique for the measurement of attitudes. Archives of psychology, 1932.
Liu, H., Li, C., Li, Y., and Lee, J. Improved baselines with visual instruction tuning. In NeurIPS Workshop Instruction Tuning and Instruction Following, 2023a.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al. Learning transferable visual models from natural language supervision. ICML, 2021.
Liu, H., Li, C., Wu, Q. and Lee, J. Visual instruction tuning. In NeurlPS, 2023b.
Rafailov, R. Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. Direct preference optimiza- tion: Your language model is secretly reward model. NeurlPS, 2023.
Liu, H. Li, C., Li, Y., Li, B., Zhang. Y., Shen, S., and Lee, Y. J. LLaVA-NeXT: Improved rea- soning, ocr, and world knowledge, January 2024. URL -1----1a---
Shang, X., Di, D., Xiao, J., Cao, Y., Yang. X., and Chua, T.S. Annotating objects and relations in user- meer-generated videos. In Proceedings of the 2019 on International Con- ference on Multimedia Retrieval, pp. 279-287. ACM, 2019.
Liu, X., Pintea, S. L., Nejadasl, F. K., Booij, O., and Van Gemert, J. C. No frame left behind: Full video ac- tion recognition. CVPR, 2021.

---

Understanding Complexity in VidcoQA via Visual Program Generation
Shen, Y., Song, K., Tan, X., Li, D., Lu, W., and Zhuang, Y. HuggingGPT: Solving Al tasks with ChatGPT and its friends in hugging face. NeurIPS, 2023.
Wang. J., Yuan, L.,, Zhang, Y., and Sun, H. Tarsier: Recipes for training and evaluating large video description mod- els. arXiv preprint arXiv:2407.00634, 2024.
Sigurdsson, G. A., Varol, G., Wang, X., Farhadi, A., Laptev, I., and Gupta, A. Hollywood in homes: Crowd- sourcing data collection for activity understanding. In ECCV, 2016.
Wang. Y., Li, K., Li, Y., He, Y., Huang, B., Zhao, Z.,, Zhang, H., Xu, J., Liu, Y., Wang. Z., et al. Intern Video: General video foundation models via generative and discrimina- tive learning. arXiv preprint arXiv:2212.03:: 0.99... 2022a.
Solomonoff, R. J. Algorithmic probability: Theory and applications. Information theory and statistical learning, pp. 1-23, 2009.
Wang, Z., Li, M., Xu, R., Zhou, L., Lei, J., Lin, X., Wang, S., Yang, Z., Zhu, C., Hoiem, D., et al. Language mod- els with image descriptors are strong few-shot video- language leamers. NeurlPS, 2022b.
Soviany, P., Ardei, C., Ionescu, R. T., and Leordeanu, M. Image difficulty curriculum for generative adversarial networks (CuGAN). In 2020.
Wei, Y., Liang, X., Chen, Y., Shen, X., Cheng, M.-M.,, Feng, J., Zhao, Y., and Yan, S. STC: A simple to com- plex framework for weakly-supervised semantic seg- mentation. IEEE Transactions on Puttern Analysis and Machine Intelligence, 39(11):2314 2320, 2016.
Spitkovsky, I. Alshawi, H., and Jurafsky, D. From baby steps leapfrog: How "less is more" unsupervised dependency parsing. In ACL, 2010.
Wu, B., Yu, S., Chen, Z., Tenenbaum, B., and Gan, C. STAR: benchmark for situated reasoning in real-world videos. In NeurlPS, 2021.
Subramanian, S., Narasimhan, M., Khangaonkar, K., Yang, K., Nagrani, A., Schmid, C., Zeng, A., Darrell, T., and Klein, D. Modular visual question answering via code generation. In ACL, 2023.
Wurm, M. F. and Caramazza, A. Two 'what' pathways for action and object recognition. Trends in cognitive sciences, 26(2):003-116, 2022.
Surís, D., Menon, S., and Vondrick, C. ViperGPT: Visual inference via python execution for reasoning. ICCV, 2023.
Xiao, J., Shang, X., Yao, A., and Chua, T.-S. Next-QA: Next phase of question-ane aanterrngn explaining tempo- ral actions. In CVPR, 2021.
Tay, Y., Wang, S., Luu, A. T., Fu, J., Phan, M. C.,, Yuan, X., Rao, J., Hui, S. C., and Zhang, A. Simple and effective curriculum pointer-generato networks for reading com- prehension over long narratives. In ACL, 2019.
Xu, H. Ye, Q. Yan, M., Shi, Y., Ye, J., Xu, Y., Li, C., Bi, B., Qian, Q., Wang. W., et al. mPLUG-2: A modu- larized multi-modal foundation model across text, image and video. arXiv preprint arXiv:2302.004400 2023.
Thomee, B., Shamma, D. A., Friedland, G., Elizalde, B., Ni, K., Poland, D., Borth, D., and Li, L.-J. YFCC100M: The new data in multimedia research. Communications of the ACM, 59(2):44-7,, 2016.
Yang. Z., Qi. P., Zhang, S., Bengio, Y., Cohen, W. W., Salakhutdinov, R., and Manning, C. D. HotpotQA: A dataset for diverse, explainable multi-hop question an- swering. In EMNLP, 2018.
Tsvetkov, Y., Faruqui, M., Ling, W., MacWhinney, B., and Dyer, C. Learning the curriculum with bayesian opti- mization for task-specific word representation learning. In ACL, 2016a.
Yi, K., Wu, J., Gan, C., Torralba, A., Kohli. P., and Tenen- baum, J. Neural-symbolic VQA: Disentangling reason- ing from vision and language understanding. NeurIPS, 2018.
Tsvetkov, Y., Faruqui, M., Ling, W., Mac Macnhinney, B., and Dyer, Learning the curriculum with bayesian opti- mization for task-specific word representation learning. In ACL, 2016b.
Yu, S., Cho. J., Yadav, P., and Bansal, M. Self-chained amage-language model for video localization and ques- tion answering. NeurlPS, 2023a.
Yu, Z., Zheng, L., Zhao, Z., Wu, F. Fan, J., Ren, K., and Yu, ANeiQA: A large-scale benchmark for fine- fine-graine the-grained compositional reasoning over untrimmed videos. In CVPR, 2023b.
Tudor lonescu, R., Alexe, B., Leordeanu, M., Popescu, M., Papadopoulos, D. P., and Ferrari, V. How hard can it be? estimating the difficulty of visual search in an image. In CVPR, 2016.
Zellers, R., Lu, X., Hessel, J., Yu, Y., Park, J. S., Cao, J., Farhadi, A., and Choi, Y. Merlot: Multimodal neural script knowledge models. NewrIPS, 2021.
Van Den Oord, A., Vinyals, O., et al. Neural discrete rep- resentation learning. NeurlPS, 2017.
12

---

Understanding Complexity in VidcoQA via Visual Program Generation
Zeng, A., Attarian, M., Ichter, B., Choromanski, K., Wong, A., Welker, S., Tombari, F., Purohit, A., Ryoo, M., Sind- hwani, V., et al. Socratic models: Composing zero-shot multimodal reasoning with language. In ICLR, 2023.
Zhang, Y., Wu, J., Li, W., Li, B., Ma, Z., Liu, Z., and Li, C. Video instruction tuning with synthetic data, 2024. URL https: /awxvv. org/ abs/ 000.. 02713.
Zhang, Z., Zhao, 7.., Zhao, Y., Wang. Q., Liu, H., and Gao, L. Where does it exist: Spatio-temporal video grounding for multi-form sentences. In CVPR, 2020.
Zhong, Y., Ji, W., Xiao, J., Li, Y., Deng, W., and Chua, T.- S. Video question answering: Datasets, algorithms and challenges. EMNLP, 2022.
Zhou, L., Kalantidis, Y., Chen, X., Corso, J. J., and Rohrbach, M. Grounded video description. In CVPR, 2019.
Zvonkin, A. K. and Levin, L. A. The complexity of finite objects and the development of the concepts of infor- mation and raddomess by means of the theory of algo- rithms. Russian Mathematical Surveys, 25(6):83, 1970.
13

---

Understanding Complexity in VidcoQA via Visual Program Generation
Appendix
Here, ISO(T, S) indicates that subtree S is isomorphic subtree within program T, and S2 S Si denotes that S2 is contained within Si.
This appendix includes further details, results and discus- sions that were not included in the main paper due to space limitations:
By applying this merging strategy, we ensure that all sig- nificant patterns are retained. The one-hot encodings of Si and S2 are identical across all programs where they appear, so merging them does not alter the representation of the data. This approach maintains the richness of the syntactic structures while optimizing the dataset for analysis.
1. Section 7 provides additional technical details for our baselines and complexity estimation methods.
2. Section 8 compliments Section 5 in the main pa- per providing extra technical specifies regarding the dataset generation pipeline.
7.2. Human Annotation Interface and Processing
For our human baseline we conduct an annotation effort subset of 150 questions from the validation set of the NEXT-QA dataset. To this end, we recruited 65 human sub- jects via the Prolific platform (Palan & Schitter. 2018), us- ing the provided filters to select for annotators that are pro- ficient in English.
3. Section reports additional results and analysis to those in Sections 4.2 and 4.3 in main paper.
4. Finally, Section 10 includes important ablations to validate the importance of individual components of our model and data generation pipeline.
The annotators were shown 50 sets of questions (one set at time), where they were asked to sort the questions cording to their perceived complexity by indicating which questions were the easies/ and hurdest. An example set and the annotation interface is shown in Figure 6. Consis- tency was validated by repeating pairs of questions multiple times (the third question can vary). We check that relative orders remain consistent and don't 't consider subjects who demonstrated low consistency. We further filter out anno- tations that were done in too little time, and annotators who finished the complete study in less than minimum reason- able time. The annotations from the remaining 30 subjects were used to calculate the total ordering of the questions.
We also include separate video with qualitative ex- amples of the analyzed questions and samples from Finally,
our new dataset at youtu.b/IMV/NNZZPIW we release code, models, and other materials at ceyza- hitrree.iiitubhio/oodeeeeig
7. Additional Technical Details
7.1. Merging Duplicate Subtrees
To avoid duplicated subtrees and reduce redundancy, we merge subtrees that always co-occur when one is descen- dant of the other. Specifically, a subtree Si is said to always co-occur with another subtree S2 if every occurrence of Sy in the dataset D is also an occurrence of St. In such cases, since S2 is always contained within Sj, we can merge S2 into S₁ without losing any unique patterns.
A. How many people can be seen dancing on the stage? (s) one. (b) six.
[c] three. (di) nine. (e) two.
B. How does the lady react to the man maving his hand to her waist? [s)
put an the girl nose. (b) laugh. [c] dance. (d) plays the instrument. (e)
waves her hand.
Merging these subtrees does not risk missing important pat- terns because any syntactic or semantic information cap- tured by S2 is inherently included in Sj. This is due to the fact that S₁ encompasses all occurrences of S2, ensuring that the features associated with S2 are preserved within ST. By eliminating redundant subtrees, we streamline the dataset, which can improve computational efficiency with- out compromising data integrity.
C. Why does the man bend down while cutting? (a) dribbingg ball. (b)
play with elmo. (c) chop leaves. play game.
the rod fixed place. (e)
Which question the "hardest" to answer about a video?
Which question is the "easiest" to answer about a video?
Move bockwardd
Move forward
The merged set of subtrees Smareed (D) is defined as:
Figure 6. We ask human annotators provide the relative order- ing of three provided questions according to the estimated com- plexity of answering the question about an unseen video.
Smerged (D) = S(D) \ (S2 E ( StE E S(D):
(VT E D. ISO(T, ISO(T.
We compute the final order of the questions using Elo scores (Elo, 1967). Originally developed to rank chess players, the Elo system models the outcome probability of unseen comparison between a pair of entities (eg. chess
A (S2 }
(10)
14

---

Understanding Complexity in VidcoQA via Visual Program Generation
players or, in our case, questions) as function of their score ratings 8;- In comparison each entity's s comparative performance is assumed to be Normally distributed around their score with fixed variance 8 The probability of a fa- vorable outcome for entity when compared to an opponent entity j is given by the probability that the performance of i surpasses the performance
ant of GPT-3.5 with support for 16k context window (nec- essary because of the long API Specification). We prompt this model with both the API and a System message to make sure the output is usable as code. Additionally, we process the output to extract the code and format such that it can be executed and analyzed. We include the prompt used:
Prompt
8:
8 V28
(11)
[SYSTEM]Only use the functions you have been provided with."
where represents the cumulative distribution of a zero- mean, unit-varianee Gaussian. The scores are updated after every comparison according to the Elo update rule.
[SYSTEM]Only complete the code. Don't include markdown syntax (eg. ticks).
[USER]<API Spec.>
# query
7.3. GPT question complexity scoring
# [answers[0]. answers([],
answers([]]
In order to automatically estimate the complexity of a ques- tion directly from it's text without biasing the method to- wards any specific definition of complexity we refer to the Natural Language Processing literature which has shown that assessments made by Large Language Models corre- late with human judgement (Madaan et al., 2023; Fu et al., 2023; Chiang et al., 2023; Rafailov et al., 2023). To this end, we leverage GPT-4 (OpenAI, 2023b) to generate a complexity score on Likert scale (Likert, 1932) (ranging from one to five). We the temperature zero (for repli- cable results) and generate single token with the score. We prompt the model follows:
answers(3], answers[4]]
def execute execute coimand(viiddeo,,,
possible answers, answers
question): # Reason every step
7.5. Logistic Regression Parameters
We use the SciKit-Lean (Kramer & Kramer, 2016) imple- mentation of Logistic Regression model. Each question- subtree pair has multiple labels (one per model in the train- ing set) logistic regression model is then trained on these, allowing it to capture consensus across the different models We train until convergence and choose parameters based on the re- ported mean accuracy over folds. The resulting model uses L2 regularization with weight e 1.0 and trained with the L-BFGS solver (Byrd et al., 1995).
average them into single soft label. The
Prompt
(SYSTEM) You are an assistant that -for the pro- vided question and its corresponding answer options- estimates the complexity of answering said question about an unknown video. Return your answer as score from 1 to 5 (1 being the easiest and being the hard- est).
7.6. Cyclomatic Complexity Calculation
We compute of Cyclomatic Complexity via an open source implementation'.
[USER] I'll provide a question and its candidate an- swers. Estimate the complexity of answering the
question about a (unseen) video. Output should ONLY be the integer score (1-5) that you assign to the question (ic. no JSON, no text, no markdown, no nothing).
8. Additional Question Generation Details
As noted in Section 5 of the main paper, we leverage ex- isting video datasets with scene-graph annotations MOMA (Luo et al., 2021; 2022), ActivityNet (Caba Heilbron et al., 2015), and Action Genome (Ji al., 2020). As necessary step we need translate the annotations into textual for- mat such that generative language model could use it. We begin by identifying the main activity and its sub-activities, including the start and end times of each. This temporal framework serves as a scaffold for the detailed enumera- tion of the actors and objects involved. Actors and objects are cataloged not just by their presence, but also in rela- tion specific sub-activities. When high level textual
query A: answers(0), B: answers(1), C: answers(2], D: answers(3), E: answers[4]
7.4. CodeGen details
We the same API in the original ViperGPT pa- per (Surís et al., 2023). For NEXT-QA analysis we use the programs and predictions from (Surís et al., 2023), which were generated by Codex (Chen et al., 2021), a Code Com- pletion LLM. Since Codex is no longer avaialble, for the CodePlex-QA code generations we instead use a text vari-
"https://radi http://rrddo..rretaeeeeeeoo.. readthedocs..org
15

---

Understanding Complexity in VidcoQA via Visual Program Generation
description is not available leverage captioning mod- els to generate visual descriptors of the actors in the video. More details in Section 8.1.
out the entire video. Consequently, exclude videos in the dataset for which objects actors cannot be reli- ably identified. Our implementation of the filtering process eliminates any videos from the dataset where the identities of actors are not consistently recognizable based on their class nome identifier. In practice, we define a Python function to detect 'collisions' instances where the same identifier used for different class names within subac- tivity, across different subastivities without consistent mapping.
The resulting dataset has an average of 2.40 questions per video. The duration of each video ranges from approxi- mately 3 seconds to 10 minutes with an average video du- ration of about 1.5 minutes. This diverse range of video lengths is desirable it conducent to generating a wide variety of questions.
The following sections describe the methods and prompts we used to translate the graphs into textual scripts for each specific dataset: MOMA (Luo et al., 2021; 2022) in Sec- tion 8.2, ActivityNet (Caba Heilbron et al., 2015) in Sec- tion 8.3, and Action Genome (Ji et al., 2020) in Section 8.4.
As noted in Section 5 of the main paper, we need to trans- late the contents of the seene-graph-in-time annotated in MOMA into a textual format such that a generative lan- guage model could use We now describe the method we used to translate the graphs into textual scripts.
Finally, Section 8.5 describes how the generated scripts are used to generate new questions.
We begin by identifying the main activity and its sub- activities, including the start and end times of each. This temporal framework serves as a scaffold for the detailed enumeration of the actors and objects involved. Actors and objects are cataloged not just by their presence, but also in relation to specific sub-activities. We identify their class names and descriptive attributes along with arrival their de- parture times within each sub-activity and store these for later. We also track state changes and action, both tran- sitive and intransitive, that occur during the sub-activities, along with the identifiers that map to the actors and objects involved.
8.1. Visual Descriptors extraction
A limitation of using Scene Graphs is that they tipically don't include visual descriptions of the nodes they relate. This is in juxtaposition with the way humans typically refer to actors and objects. To this end we describe the main actors in the video using a Captioning model. In particular, we use Llaval.5 (Liu et al., 2023a;b) to describe single instance of the actor in the video. We leverage the included bounding box annotations for the actors in each annotated interaction. We choose the bounding box with the largest area (in pixels) in the first subactivity the actor appears in. We then crop the relevant area and zero-pad the borders to make the final image square, as this is the format that Llaval.5 was trained with. The resulting cropped image passed into the captioning model along with a prompt modified from Llava.
The final script is structured in a hierarchical format, start- ing with the main activity title and its timeframe, followed by detailed sections for each sub-activity. These sections enumerate the actors present, and a chronological account of events, actions, and state changes. We also generate a descriptive caption for each actor involved following Sec- tion 8.1 and include in the prompt. An example of an activity and its first sub-activity is shown:
Prompt
"A chat between a curious human and an artificial in- telligence assistant. The assistant gives helpful, de- tailed, and polite answers to the human's 'ss questions. [USER]<image>>
# Activity: "Dining" (0-597)
All actors:
customer. Visual deseription: The per- son in the picture a woman with long, dark hair. She is wearing white shirt and black tie.
ROLE:
Look at the picture and tell me only about the per- son's looks that don't change. Like what they' 're wear- ing, their hair color and style. Don't talk about where they are OR what they're doing. (Tag is <actor classsaaasss.. [ASSISTANT]
ROLE: waiter. Visual description: The waiter in the picture is a young man wearing a white shirt and black tie.
Importantly, we also pass in the textual identifier for the actor, indicated in the prompt as saactor.classaan
## Sub activity (0-10): The waiter is talking to the customer or helping them into their seat
8.2. MOMA
Actors present: customer, waiter
A significant limitation specific to MOMA is the inconsis- tency in annotated identifiers for object or actor through-
16

---

Understanding Complexity in VidcoQA via Visual Program Generation
Happened during sub-activity:
descriptions. We then list the annotated actions (along with their respective start and end times). Finally, iterate over the annotated-per--faan object-actor relationships and track when their state changes. We provide the timestamp at which the state-change occurred and the change itself to the generation model. As was the case with ActivityNet, we don't need to generate visual attributes as the high level description often provides them. An example script is shown below:
(attribute) waiter standing
(transitive action) waiter talking to cus- tomer (intransitive action) waiter bending
8.3. ActivityNet
Although the original ActivityNet (Caba Heilbron et al., 2015) dataset didn't include scene-graphs, follow up work ActivityNet-Entiiies (Zhou et al., 2019) provides additional annotations for objects, attributes, relationships and ac- tions. Further, we also use the per-subactivity captions in the ActivityNet-Captions (Krishna et al., 2017) dataset.
# Activity (duration: 30.62): "A person sits at desk in the living room. The person laughs as they pick up bag of groceries from under the desk."
Location: "Bedroom"
As was the case with MOMA, we translate the contents of the semee-raph-in-timee annotated into a textual format such that it can parsed by a generative language model. We once again divide video into main activity and component subactivities, and take note of their start and end times. Actors present in particular subactivity are listed within the subactivity description, along with their provided visual descriptions when available in ActivityNet Entities (Zhou et al., 2019). Finally, we filter relationships such that we only keep those that involve actors and list those for each actor. An example of an activity and a sub- activity is shown below:
Other descriptions:
A person is sitting at adesk they pick up bag and then they get up
The person is sitting the computer desk and bends over to pick up the garbage, which he sits on his lap, and then gets up carrying the garbage.
Actions:
Taking a bag from somewhere (9.00, 16.40)
# Activity: "doing archery" (time: 11-177)
Sitting at table (0.00, 29.30)
## Sub activity (15-39): He loads an arrow in the bow.
Someone is standing up from somewhere (25.00,
30.80)
All actors descriptions from subactivity:
Holding bag (12.70, 32.00)
Visual description (time: 31): attributeclass:
Someone laughing (0.00, 30.80)
person age&sex: man hairstyle: straight
hairlength: short haircolor: ['black'] acces-
Sitting in a chair (0.00, 32.00)
sory: ['glove'] skincolor: white upperclothes-
type: t-shirt upperclothescolor: ['white']-
Relation Changes (wrt. actor):
lowerelothestype: shorts lowerclothescolor:
['black'] status: I'standing'. 'shooting'] lo-
bag goes from " "holding" to '"tuuhhing' at 18.0" bag goes from ""tuuhhin"" to "holding' at 20.0"
cation: outdoors
Relations for actor in subactivity:
person pulling bow
person holding arrow
bag goes from "holding" to "touching'' at 26.0"
8.4. Action Genome
bag goes from ""oouhhin"" ""holding" at 27.0"
We leverage the scene-graph annotations in Ac- tionGenome (Ji et al., 2020) for the Charades video dataset (Sigurdsson et al., 2016) and use the annotated activity along with its duration and high level description. When available we also include the location and other
17

---

Understanding Complexity in VidcoQA via Visual Program Generation
chair goes from ""sitting.on _on"" "None at 28.0"
the annotations are missing descriptions:
chair goes from "None" to " crottcconacting" at 28.0"
Also avoid saying "unclassified ..." to refer to actors.
If you weren't I provided with a role use visual descrip- tions instead.
8.5. Question Generation from Scripts
9. Additional Results and Analysis
Each textual script generated above is combined with a prompt requesting that the language model output inter- esting questions about the video, without specifying that they should be hard, or how interesting should be inter- preted. The complete prompt is used to condition Large Language Model to generate the requested questions and answer candidates in JSON format. The chosen language model is GPT-4. We set the sampling temperature to zero and decode greedily (for replicability). We include the ex- act prompt used here:
9.1. Relation to Video Complexity
Our approach estimating the complexity of VideoQA tasks is grounded in insights from classical complexity the- ory, specifically the Chain Rule for Kolmogorov Complex- ity. According to this rule, the complexity of a composite entity, such as a (video, question) pair, can be expressed as the sum of the complexity of one component (c.g., the question) and the conditional complexity of the other com- ponent (e.g., the video conditioned on the question), plus logarithmic term:
Prompt
You generate interesting questions to ask about the video for which the description is provided. Pretend you don't get the exact description (ie. no exact times or player ids) but you did watch the video, so you have a notion of what happens, and when. Reeuun a list of Multiple Choice questions formated as json with q, ans, distl, dist2, dist3, dist4 keys. 'distN' are 4 distractors..
K(r, v) - K(x) + (ylx>) + (loo((((a ()))
(12)
In cases where there is minimal shared information be- tween the video and the question, the complexity of the pair can be approximated as the sum of their individual com- plexities, up to this logarithmic term:
What interesting questions to ask about this video? (description provided) Return numbered list of Multiple Choice questions formated as a json with q, ans, distl, dist2, dist3, dist4 keys. 'distN' are 4 distractors
K(x,v) R K(x) + K(y) + O(log( (x,
(13)
In this work, we focus on estimating the complexity of the question, which parallels the structure suggested by the Chain Rule for Kolmogorov Complexity. If treat the video x and the question y, then the complexity of the (video, question) pair can be thought of in similar way. where the complexity of the question K(y) is a key component of the overall task complexity. While we do not directly compute Kolmogorov complexities, this anal- ogy provides theoretical motivation for focusing only on the question complexity. Estimating the complexity of the question is valuable because robust methods for assessing the complexity of the video to achieve more comprehensive measure of the total task complexity in future work.
Try to use visual descriptions of the actors instead of their role sometimes (eg. the person with the red shirt instead of the waiter).
**EVER*** say subactivities. Eg. don't say "first subactivity", instead say "while the waiters served the drinks".
Video description:
later be combined with
<ESC
The difference between the predicted complexity of the question and the actual model performance on a given question can be used as a proxy for estimating the video's complexity. Prior work by (Wei et al., 2016) has approxi- mated image complexity by the number of objects present in an image. We extend this approach to video complexity, utilizing the VidOR dataset (Shang et al., 2019), which pro- vides annotations of entities and their relations in videos. Conveniently, VidOR and NexIQA share the same video
Remember, **NEVER** say subactivities. Eg. don't say "first subactivity", instead say "while the waiters served the drinks".
When generating questions for videos from the MOMA dataset we also include an additional instruction to make sure the model doesn't 't refer to actors as unclassified when
18

---

Understanding Complexity in VidcoQA via Visual Program Generation
source, YFCC100M (Thomee al., 2016), allowing us to align entity counts with our models' performance on Nex- IQA.
To illustrate this, we analyzed the GQA image QA bench- mark (Hudson & Manning, 2019), generating programs with ViperGPT (Surís et al., 2023), For consistency, we evaluated the BLIP-2 (Li et al., 2023) VQA model (cho- sen as it shares the same backbone with SeViL.A) and ViperGPT. We found that the overall complexity of gen- erated programs is significantly lower in images (10% of programs with cyclomatic complexity above 5 compared to =:45% in NEXT-QA). As result, the relationship between cyclomatic complexity and model performance is much stronger in VideoQA than in ImageQA, evidenced by a higher coefficient of determination R²² of 0.75 vs. 0.39.
Correctly Answered Hard Quastions
Differecee in Number Subjectt/Objecs
Incorrectly Answered Easy Quesions
0.2
011
Intuitively, this difference in program complexity is not sur- prising, as answering a question in a video typically re- quires analyzing more content than in a single image. In the case of NLP, the underlying tasks often involve even sim- pler reasoning patterns. For example, the multi-step rea- soning chains in HotPotQA (Yang et al., 2018) are linear, and the dataset collected to evaluate HuggingGPT (Shen et al., 2023) has fewer than module calls per prompt on average, and in simple patterns.
-01
SeVIA
SWVLA 29
VierOPT
Intervidee
ATP
VOLUT
Figure 7. Comparison the average number of entities (subjects and objects) in videos where models perform poorly on low com- plexity tasks (easier questions) versus where they perform well on high complexity tasks (harder questions). More entities make easy questions harder, while fewer entities make hard questions casier.
9.3. Subtrees Visualization
In this section, we present visualizations of subtrees which correlate with question that are challenging to answer for all 3 models analyzed in the main paper (see Sections 3.3 and 4.3). A majority of the nodes present in the ASTs encode non-essential information such as variable names, while we care about the actual structure and the operations being executed on the frames. For this reason, we ignore variable names and values when comparing two subtrees to one another. Similarly, we develop a tool to visualize the general structure of subtrees that performs a related node- trimming step. Finally, the visualizations of ASTs in the paper (eg. Figure 4 of the main paper) include an addi- tional simplification step in which nodes are merged to aid in understanding and interpretability.
Figure 7 compares the difference in the average number of entities (subjects and objects) in videos where mod- els perform poorly on low complexity tasks (easier ques- tions) versus where they perform well high complexity tasks (harder questions). The trend indicates that, for easier questions (low complexity), videos with more subjects/ob- jects tend to result in poorer model performance, while for harder questions (high complexity). models perform better when fewer subjects/objects are present in the video.
This pattern supports the idea that the sources of complex- ity of a VideoQA task can be combined. Simple questions become more challenging when accompanied by complex videos, and difficult questions can be made easier in the presence of simpler vidcos. This relationship between video complexity and question complexity reinforces the importance of estimating both components. While our cur- rent approach focuses on question complexity, combining with accurate video complexity estimations can yield more precise measure of the overall task complexity. We leave the exploration of more accurate methods for video complexity estimation to future work.
All the 8 subtrees that are shared by the models in the main paper are shown in Figure 16. There are two principal patterns that can bee seen from analyzing them. The first group includes primitives that allow for temporal reason- ing (Figures 8 to 13). The other common pattern group in- cludes questions that require more detailed analysis of spe- cific elements (objects, relationships) within a scene (Fig- ures 14 and 15).
First, we consider the primitives necessary for temporal reasoning, i.e. for questions that necessitate taking into ac- count specific frame's placement in a sequence of events.
9.2. Applicability to other tasks
In principle, our approach applicable to any QA domain. However, we limit the scope of this paper to VideoQA, where the reasoning complexity is significantly higher and model failure modes are more nuanced; thus, our approach has the most significant utility.
The subtrees shown in Figures 8 and 9 both contain the control flow necessary for identifying an event that happens after a particular condition has been met. Figure 8 in partic- ular illustrates a common pattern for finding the frame after
19

---

Understanding Complexity in VidcoQA via Visual Program Generation
Ariie Cara
Nea
Modd:
Mack
Auigon Carse
Ins
Arigg Crrss
With www..//ggeeeoooo
Flacó
Figure 8.
Figure
Assign Coost
False
Module
Flostii
Andign Corrd
Novz
Figure 11.
Figure 10.
Figure 12.
Expe
fiame.deter object()
Figure 13.
Figure 14.
Figure 15.
Figure 16. Subtrees identified as hard.
something has happened, with a For Loop that identifies the relevant part of the video, followed by an addition to look after. Similarly, Figure 9 is common programs that have to identify a second condition that happens after first one. For this reason the control-flow is slightly more complex, and includes second conditional that is only checked for after the first condition has been satisfied.
video when frame that meets the required criteria is seen. Intuitively, this pattern allows for the identification of the first event in the video that meets some criteria, as the break in the loop avoids overwriting the variable with frames that come in the future. And Figure 13 shows an iterator over the video, which is the main primitive necessary consider frames in order. This primitive is often used in conjunction with others shown, eg. with the break statement in Fig. 12 to find the first frame that meets the condition.
Figures 10 to 13, while also temporal, are less obviously so. The presence the primitives shown Figure 10 cor- relates with code that includes a loop over frames the video. This pattern commonly used to setup for iterating over the video until a relevant frame found. Upon identi- fication, the first boolean variable switches to True and the other one is used to store the frame. Intuitively, this pattern is useful for answering questions about a specific moment of a video. The primitives in Figure 1l show code that se- lects a frame from the middle of the video. In practice, pro- grams include this code as a fail-safe when searching for specific frame, falling back selecting the middle frame in satisfying frame is found (eg. Fig. 8). Figure 12 shows a break statement that will halt an iteration the
The other common pattern group involves questions that require more granular consideration of specific elements (objects, relationships) within a scene. For example. the subtree shown in Figure 15 is included in questions that require focusing on single specific object or actor in frame of the video. Relatedly, programs that include the subtree in Figure 14 require identifying at least two objects or actors and then relating them (by calling simple.gat an image question answering module).
20

---

Understanding Complexity in VidcoQA via Visual Program Generation
Success Rate par Model by Number of Fromes in Temporal Support
Figure 18 indeed validates that our approach is success- ful in identifying a subset of NEXT-QA that is more chal- lenging for all models evaluated compared to the original dataset. However, our final dataset generation pipeline re- sults in an even more challenging benchmark by first con- structing a more diverse pool of videos and questions for the filtering approach to select from.
Paornge Succus Raz0
Mode's
SeviLA
SeilAA
0.4
0.3
ATP
VIOLTT
10.2. Validating Question Generation Pipeline with Same Videos
Counting quast ors
Singla-ramm
Mull-frame
While the validation of the question selection algorithm component of our dataset construction pipeline in Sec- tion 10.1 shows that our selection algorithm is effective in identifying challenging subsets of questions, this does not fully guarantee that the higher observed complexity in CodePlex-QA in Table 2 is exclusively due to the question generation pipeline. Therefore in this section we isolate the video source effects by adapting our pipeline to use the same videos from VidOR (Shang al., 2019) as NEXT-QA.
Figure 17. Temporal support (i.e. number of frames question needs) according the generated program. All models tested per- form significantly worse on questions that require more frames. Counting questions listed separately, as they potentially quire every frame to be checked.
9.4. Additional Analysis Results: Temporal Support
The interpretable nature of subtrees allows us to manually identify subset of subtrees we know correspond to sub- routines that store frames. We leverage Equation 1 to count the appearance of said subtrees in each program's 's ASTs to find the temporal support of each question. As pre- vious works have proposed (Mangalam et al., 2023), we validate that significant source of question complexity in Video Question Answering is owed to the number of frames needed to answer the question (Figure 17).
To generate the questions, we use VidOR annotations and augment them with annotations from VidSTG (Zhang et al., 2020) and captions generated by ChatGPT (Zhang et al., 2024). We then apply our full pipeline without modifica- tions to obtain CodePlex- QA- VidOR. Finally, we evaluate the baseline models from Table and report the results in Table 4.
As Table 4 shows, CodePlexQA- VidOR remains consis- tently more difficult than NExT-QA across all models, de- spite using identical video sources. CodePlexQA-Videe is slightly easier than our original CodePlexQA, both because of divergent data sources and because the less detailed Vi- dOR scenegraphs limit the expressivity of the generated questions. This confirms that while video source con- tributes overall dataset characteristics, the key driver of difficulty is question generation and selection method- ology, not merely differences in video content.
9.5. Dataset Statisties: CodePlex-QA
The outcome of the data generation process is summarized in Table 3, which presents breakdown of CodePlex-QA. For each source dataset, the table shows the number of questions and videos that pass the described CodePlexity filter. Importantly, majority of the questions are associ- ated with a unique video.
10.3. Impact of Code Generation Correctness Complexity Metrics
10. Ablations
10.1. Validating Question Selection Algorithm
To investigate the relationship between code generation correctness and the alignment of complexity metrics to problem structure, we conduct an ablation study compar- ing cases where the generated code produces correct an- swers with those where it does not. Note that "incorrect answers" do not necessarily imply that the code itself is in- valid; rather, it may fail to produce the expected output.
We now validate our approach for selecting hard questions based on our complexity estimation using the NExT-QA validation set. In particular, we follow the same approach (and with the same threshold and parameters) as when con- structing CodePlex -A, and select the most challenging questions from this set. We then evaluate the same models from Section 5.2 this subset, which call NEXT-QA", and compare to both the original NEXT-QA dataset, and CodePlex-O2 QA. This allows to separate the effects of ques- tion generation and question filtering when constructing CodePlex- QA as NEXT-QA and NEXT-QA" share exactly the same base set of questions.
The results are summarized in Table 5, which presents the correlation between the complexity metrics and the mPEG metric for various models. From Table 5, is evident that the correlation between the mPEG metric and the various code-based complexity metrics is consistently higher for
21

---

Understanding Complexity in VidcoQA via Visual Program Generation
#Questions
# Videos
Action Genome (Ji et al., 2020) ActivityNet (Caba Heilbron et al., 2015)
1572
1154
749
594
MOMA (Luo et al., 2021; 2022)
133
93
Table 3. Composition of CodePlex-Q4 PAA in terms of number of questions and videos from each source dataset.
Dataset
Tarsier
SeViLA ZS
ViperGPT Intern Video
VIOLET Random
NEXT-QA
70.9%
64.2%
60.0%
50.9%
37.7%
20.0%
CodePlexQA 52.5%
43.7%
45.8%
29.9%
27.6%
20.0%
CodePlexQA-VidOR 59.6%
58.5%
50.4%
46.2%
30.0%
20.0%
Table 4. Difference in prediction accuracy of zero-shot VideoQA models hetween the manually annotated NEXT-QA, our automatically generated CodePlex-QAA and its VidOR-hased variant. CodePlexQA-VidOR consistently harder than NExT-QA despite sharing video sources, while slightly easier than the full CodePlexQAA.
Success Rate per Model Easy vs. Hard Subsets
power of code-based complexity metrics.
10.4. Impact of Code Generation Model Choice
0.5
Peerigg Surcess Paaee
This section evaluates the influence of the code generation model on the performance of our complexity estimation framework. Specifically, we compare ViperGPT, the pri- mary model used in our analysis, with Recursive Visual Programming (RVP) (Ge et al., 2024), a newer model de- signed for visual programming tasks. Unlike traditional ap- proaches, RVP employs a recursive code generation strat- egy, which systematically breaks down complex problems into manageable subproblems. This allows it handle in- tricate question structures with greater flexibility.
0.4
Madels
SeMILA
Intemviidoo
Random
6.0
Figure 18. Filtering NExT-QA using approach indeed results a more challenging subset for the evaluated models. How- ever, our full dataset construction pipeline results in an even more challenging benchmark by first generating a more diverse pool of samples select from.
Figure 19 illustrates the relationship between the estimated complexity of questions and the performance of Visual Pro- gramming models. For both ViperGPT and RVP, we ob- serve sigmificant negative correlation between the com- plexity metric and the model's success rate. This trend highlights that the estimated complexity of question increases, the likelihood of the model correctly addressing it decreases. This correlation underscores the utility of the complexity metric as predictive tool for identifying chal- lenging questions.
cases where the generated code produces correct answers. However, we highlight that CodePlexity is a lot more ro- bust to code generation errors than the baselines. In other words, while the correlation between models' performance and metric value improves when code is correct, CodePlex- ity consistently outperforms baselines in robustness to code generation errors. This underscores its practicality even when errors occur.
10.5. Impact of Analysis Dataset Choice
To assess the generality and robustness of our find- ings, we replicated our analysis using a different dataset, MVBench (Li al., 2024), which offers a diverse set of videos and questions compared to NExT-QA. Specif- ically, we repeat the same experimental setup that in Section 4.1, first generating programs for the questions in MVBench, and then rerumning our pipeline to generate pro- grams using ViperGPT, extract code based metrics, and train our CodePlexity metric. Furthermore, we additionally consider two new models in our analysis: VideoChat2 (Li
These results suggest that correct code generation often aligns better with problem complexity, as reflected in higher correlations with the mPEG metric. By contrast, incorrect code, while potentially valid in syntax struc- ture, often fails to capture the underlying complexity of the problem, thereby diluting the relationship between the met- rics.
In a similar manner, Section 10.4 how that using more advanced code generation models improves the predictive
22

---

Understanding Complexity in VidcoQA via Visual Program Generation
Train Models
Validation Models
SeViLA ViperGPT
ATP
VIOLET
HGA
SeViLA ZS InternVideo Tarsier
Lines of Code
Correct
0.1373
0.1747
0.1455
0.0712
0,1654 0.0756
0.2022
0.1475
Incorrect
0.1245
0.0540
0.0656
0.0735
0.0831
0.0696
Cyclomatic Complexity
Correct
0.1702
0.2128
0.1930
0.0649
0.1739
0.2825
0.1634
Incorrect
0.1351
0.1118
0.0881
0.0664
0.0973
0,1388
0.1071
CodePlexity
Correct
0.2608 0.2810
0.3128
0.3178
0.0867
0,2095 0.1839
0.2877 0,1700
0.1950
Incorrect
0.2041
0.2542
0.1087
0.1857
Table 5. Correlation of complexity metrics with mPEG for cases where the generated code produces correct and incorrect answers.
et al., 2024) and Llava-NExT (Liu et al., 2024) as these represent the state of the art the MVBench dataset.
10.6. Training CodePlexQA
We split CodePlex-QA into train and val sets and fine-tuned VeViAA We observed that training on CodePlex-O0 - in- deed can help improve the performance of VideoQA mod- els on these hard questions (accuracy increases from 44.8 to 47.3). However, the gap is narrower compared to fine- tuning the same method on NExT-QA (accuracy improve- ment from 64.2 73.4). This suggests that our analysis covered 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 first visualize the correlation between code-based com- plexity metrics and the performance of various VideoQA models on MVBench in Figure 20, Consistent with our ob- servations on NEXT-QA, we found that code-based com- plexity metrics exhibit strong negative correlation with model performance on MVBench. Specifically, both Lines of Code and Cyclomatic Complexity continued to demon- strate consistent and strong correlation, indicating that questions requiring more intricate code are more challeng- ing for all the models evaluated. This is despite the base code generation model ViperGPT (and RVP) performing worse MVBench than NEXT-QA, where they achieve accuracies of 38.4% and 35.0%, respectively. For refer- ence, these are comparable to recent approaches such as GPT-4V (run with 16 frames as input at 512x512 12 resolu- tion), which obtains 43.5%, and VideoChat (Li et al., 2024) (also with 16 frames), which achieves 35.5%.
We further conducted systematic evaluation of different code-based metrics using the mPEG metric the val- idation set of MVBench, summarized in Table 6. Our proposed CodePlexity metric significantly outperformed the naive code complexity measures, such as Lines of Code and Cyclomatic Complexity. CodePlexity achieved higher predictive accuracy in estimating question difficulty across all evaluated models on MVBench. Note that Code- Plexity generalizes the held-out models in analysis (VideoChat2 (Li et al., 2024) and Llava-NExT (Liu et al., 2024)).
These consistent results across two distinct datasets sug- gest that code-based complexity metrics, and CodePlexity in particular, are effective tools for assessing question dif- ficulty VideoQA tasks regardless of the dataset's 's charac- teristics.
23

---

Understanding Complexity in VidcoQA via Visual Program Generation
Train Models
Models
Vider
SeViLA ZS
Tarsier
VideoChat2
LLaVA-NeXT
Dependency Tree Depth GPT-4 (OpenAI, 2023b)
6.5
6.2
19.7
16.5
12.2
2.3
0.0
14,8
12.8
8.9
BERT (Kenton & Toutanova, 2019)
25.5
11.6
18.7
20.9
21.6
Lines of Code
4.4
9.5
12.5
10.3
9.2
Cyclomatic Complexity
13.0
9.6
6.1
5.2
4.5
CodePlexity (Ours)
41.3
33.0
44.6
29.9
27.5
Table Comparison of question complexity metrics using mPEG on the validation set of MVBench. CodePlexity trained on the first three models. Our approach demonstrates the highest correlation with the models' performance.
Success Rate Cyclomatic Complexity
Average
Success Rate vs Lines Code
Sevil
VipercPT
Tarsler
Video
UavaNest
Success Rate
SeVILA 25
IntervVidee
0.7
0.5
0.6
0.4
0.5
0.3
0.4
0.2
0.3
2
3
5
Cyclomatic Complexity
0.2
8
10
11
12
13
14
15
16
ViperGPT
Lines of Code
Success Rate vs Cyclomatic Complexity
Success Rate vs Cyclomatic Complexity
1.0
Average
0.9
SeVILA
Tarsier
SeVIA
LlavaNext
0.8
ViperGPT
SeVILA 25
Intervvisoo
IntormMideo
0.7
ATP
Success Rate
0.7
VIDLET
0.6
HCA
0.6
0.5
0.5
0.4
0.4
0.3
0.2
2.0
2.5
3.0
3.5
4.0
4.5
5.0
5.5
6.0
Cydomaticc Complexity
Cyclomatic Complexity
RVP
Figure 20. Correlation of VideoQA models' success rate on MVBench for various approaches for estimating question com- plexity. As was case for NEXT-QA, we observe that code complexity correlated strongly with question complexity.
Figure 19. Comparison of code-based complexity metrics when using different code generation models. Lines both cases show significant negative correlation of complexity metric with model performance for both variants.
24


Reviews:
[{"review_id": "xw6arRe5vo", "reviewer": "Reviewer_rEFD", "summary": "## update after rebuttal\n\nThe paper introduces an interesting method of relying on visual programs to evaluate the complexity of VideoQA task. The authors develop methods to analyze the code complexity to estimate the question complexity. The proposed method, CodePlexity, correlates better with the model performance compared with human judgments. To show the utility of this approach, the authors also use this approach to create a dataset CodePlex-QA, which is empirically 1.9x more difficult than NextQA.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n\n**“Gold” vs model-specific question complexity**\n\nWe 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. \n\n---\n\n**The role of the visual information**\n\nWe 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.\n\n---\n\n**Given the same question, complexity can vary across videos**\n\nThis 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.\n \n---\n\n**Visual programming methods’ performance on NExT-QA and MVBench**\n\nWe 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.\n\nFollowing 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. \n\n---\n\n**References:**\n\n[1] Li, KunChang, et al. \"VideoChat: Chat-centric video understanding.\" arXiv preprint arXiv:2305.06355 (2023).\n\n---", "claims_and_evidence": "The evidence is overall convincing. One concern is that there might not be a gold definition of \"question complexity\". It is more rigid to claim that this method can find the questions that are challenging for existing video models.", "methods_and_evaluation_criteria": "The approach is novel and makes sense. \n\nA concern is that the approach only depends on the question part of the VideoQA. Nevertheless, the visual content, for example, the length of the video, may have an important role. The approach might be better if it incorporates visual information in some way.", "theoretical_claims": "The paper contains some deductions on the metric for code complexity, and they make sense.", "experimental_designs_or_analyses": "Overall the experiment designs are valid and the analysis is interesting. Many experiments are added in the appendix.", "relation_to_broader_scientific_literature": "The research question is very interesting and is a focus of current research. People are thinking of ways to build better video benchmarks, and this paper provides insights into this direction.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\nThe method is novel, interesting, and makes sense. The idea of evaluating VideoQA questions with visual programming is smart, and the authors show this method's effectiveness through their experiments. This work can be inspiring to many follow-up works on video LLMs.\n\nWeaknesses:\nThe approach, including the baselines, relies only on the \"text\" questions but ignores the visual content. The video part may play an important role, like how long the video is, and how many entities are there in a frame. Existing methods of visual programming ignore such information and may limit the proposed methods' effectiveness.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. Is there a possibility that given the same question, its complexity can be very different given different videos? How would you address this?\n\n2. Just curious, how well are visual program methods on NExT-QA and MVBench? From my experience, I expect their accuracy to be relatively poor.\n\nThe authors have answered the questions in rebuttal.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WkAShU0twa", "reviewer": "Reviewer_rPct", "summary": "This work focuses on important issues in the VideoQA domain and presents a novel approach that provides new perspectives for future model evaluation and benchmark dataset construction. The core contribution is to propose a data-driven approach to systematically identify and analyze model-specific weaknesses in VideoQA tasks.\n\nSpecifically, the paper presents a visual program generation approach to analyzing the complexity of questions in video question and answer (VideoQA) tasks. The authors measure the difficulty of a question by converting a natural language question into executable code and utilizing the structural complexity of the code. Specifically, the paper proposes the CodePlexity approach, which parses the abstract syntax tree (AST) of the code, extracts the subtree structure, and trains a logistic regression model to predict how challenging different types of problems are for the model.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n\n**Model-specific vs intrinsic difficulty.**\n\nWe 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.\n\n---\n\n**Influence of the code generator on the complexity metric.**\n\nThe 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. \n\n---\n\n**How can we ensure the benchmark remains reliable as models improve?**\n\nEnsuring 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.\n\nFurthermore, 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.\n\n---\n\n**Without a stable, model-agnostic definition of difficulty, how can future researchers rely on the benchmark?**\n\nWe 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.\n\nRather 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.\n\n---\n\n**References:**\n\n[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.\n\n[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.\n\n[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.", "claims_and_evidence": "See weakness", "methods_and_evaluation_criteria": "See weakness", "theoretical_claims": "No serious flaws found", "experimental_designs_or_analyses": "No serious flaws found", "relation_to_broader_scientific_literature": "This work focuses on an important research problem, and the proposed method is novel.", "essential_references_not_discussed": "Related works are clear", "other_strengths_and_weaknesses": "Strengths\n\nThis paper focuses on an important research problem in VideoQA, aiming to systematically identify and analyze model-specific challenges. The proposed approach is both methodologically sound and conceptually novel, leveraging visual program generation to assess question complexity in a unique way. Additionally, the paper is well-structured, clearly written, and effectively presents its methodology, results, and contributions.\n\nWeaknesses\n\nSince the estimated complexity is derived from the generated code rather than the intrinsic difficulty of the question itself, the benchmark primarily reflects model-specific difficulty rather than absolute question difficulty, which may restrict its broader applicability. Consequently, long-term impact and reliability of CodePlex-QA benchmark remain unclear, as its difficulty could be tightly coupled to the specific capabilities of the models used for generation. That being said, I acknowledge the potential of the proposed method and thus maintain a positive rating for now.", "other_comments_or_suggestions": "None", "questions_for_authors": "The benchmark created by this method primarily reflects relative difficulty as defined by the specific code generator used as a reference point. As models rapidly evolve these days, the benchmark may quickly become outdated or lose its effectiveness in distinguishing between truly challenging questions. Given that model capabilities are difficult to quantify precisely, how can we ensure that the benchmark remains a faithful and reliable measure of VideoQA complexity as models improve? Moreover, without a stable and model-agnostic difficulty definition, how can future researchers determine whether the benchmark continues to serve as a meaningful evaluation tool?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QKi96Ljc1J", "reviewer": "Reviewer_V8ky", "summary": "This paper proposes a data-driven approach to analyzing query complexity in Video Question Answering (VideoQA). They design an automatic approach that leverages recent advances in code generation for visual question answering, using the complexity of generated code as a proxy for question difficulty. They demonstrate that this measure correlates significantly better with model performance than human estimates. They construct a new benchmark that is 1.9 times harder than the popular NExT-QA.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and valuable feedback. We address your comments individually below.\n\n---\n\n**On defining complexity via model performance**\n\nWe 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. \n\nOur 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. \n\n---\n\n**Clarifying Table 1**\n\nThank 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.\n\n---\n\n**Results with more recent VideoQA models**\n\nWe 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.\n\n**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}$).\n| | SeViLA | ViperGPT | ATP | VIOLET | HGA | SeViLA ZS | InternVideo | Tarsier | Llava-Video |\n|-|--------|----------|-------|--------|------|-----------|-------------|---------|---------|\n| **Type** | Train | Train | Train | Train | Val | Val | Val | Val | Val |\n| **Dependency Tree Depth**| 12.9 | 7.9 | 11.1 | 15.9 | 7.4 | 13.5 | 17.7 | 10.1 | 6.9 |\n| **GPT-4** | 9.6 | 8.9 | 11.6 | 5.8 | 7.8 | 14.6 | 13.9 | 10.8 | 5.2 |\n| **BERT** | *12.5* | *6.0* | *18.3*| *17.3* | 7.7 | 14.3 | 21.1 | 10.8 | 11.4 |\n| **Lines of Code** | 16.4 | 15.3 | 14.2 | 12.0 | 9.9 | 16.2 | 17.5 | 14.4 | 9.38 |\n| **Cyclomatic Complexity**| 18.2 | 14.2 | 18.7 | 15.9 | 8.9 | 17.2 | 24.2 | 16.7 | 11.5 |\n| **CodePlexity (Ours)** | *26.7* | *21.3* | *21.0*| *15.8* | **14.1** | **25.6** | **26.6** | **24.9** | **17.3** |\n\n**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.\n| Dataset       | LlaVa-Video | Tarsier | SeViLA ZS | ViperGPT | InternVideo | VIOLET | Random |\n|---------------|---------|---------|-----------|-------------|-------------|--------|--------|\n| **NExT-QA**       | 82.5% | 70.9%   | 64.2%     | 60.0% | 50.9%       | 37.7%  | 20.0%  |\n| **ATP-Hard**      | 77.6% | 59.8%   | 54.9%     | 51.8% | 24.6%       | 25.4%  | 20.0%  |\n| **CodeplexQA**          | 65.0% | 52.5%       | 43.7%     | 45.8% | 29.9%       | 27.6%  | 20.0%  |\n\n\nWe will move the MVBench evaluation, including LLaVa-next results, to the main paper.  \n\n---\n\n**Using CodePlex-QA for training** \n\nThank 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.", "claims_and_evidence": "I want to mention that I'm not convinced by the pre-assumed claim in this paper, which is that \"we should define question complexity by model performance instead of by humans\". I believe it is always up to humans, because models eventually learn from human. The performance difference (human think a question hard but model performance is high) can be because of lots of reasons, e.g. dataset construction and evaluation method. Specifically, human can think the \"Where is this?\" question in Figure1 hard because they think of many perspectives e.g. campus, city wise location, country wise location, but model many only think about restricted perspectives, e.g. whether it is outdoor or indoor. These can all be affected by the answers in the data. Therefore, I'm not convinced that question complexity is decided by models. Instead, they should be decided by humans. \nIf we see this paper as finding and auto-generating harder questions for certain videoQA models, then it's more appropriate.", "methods_and_evaluation_criteria": "It's hard to interpret the result table. E.g. in Table 1, how to read the results? What does Train Models and Val Models mean? How do they relate to each other?", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Many models are not that up to date, e.g. VIOLET, InternVideo, HGA. Why not experiment with LLaVa-Video and LLaVa-one-vision? These are specially designed for video tasks, and better than LLaVa-Next.  \nOne small comment is to move the result table of the newer model e.g. LLaVa-next to the front.", "relation_to_broader_scientific_literature": "It's related to visual programing.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I wonder if the generated  CodePlex-QA benchmark can be used as training data and improve these tested video QA models in the paper?", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See Claims And Evidence. Happy to raise score if questions are addressed.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vxIEnwbyte", "reviewer": "Reviewer_tu7h", "summary": "This paper proposes a data-driven approach to assess question complexity in VideoQA tasks by leveraging the complexity of generated code as a proxy. The mPEG results on NExT-QA and MVbench demonstrate the effectiveness of Codeplexity. Furthermore, the newly introduced dataset, CodePlex-QA, features more challenging questions than those in NExT-QA and the ATP-hard subset, validating the feasibility of this method for creating more difficult datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n\n**Applicability beyond VideoQA.**\n\nIndeed, 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).\n\nIntuitively, 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.\n\nThese 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.\n\n---\n\n**Code generation model.**\n\nIndeed, 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.\n\n**(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.\n\n**(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.\n\n---\n\n**Dataset construction ablation.**\n\nThank 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.\n\nTo 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.\n\n|Dataset|Tarsier|SeViLAZS|ViperGPT|InternVideo|VIOLET|Random|\n|-|-|-|-|-|-|-|\n|NExT-QA|70.9%|64.2%|60.0%|50.9%|37.7%|20.0%|\n|CodePlexQA|52.5%|43.7%|45.8%|29.9%|27.6%|20.0%|\n|CodePlexQA-VidOR|59.6%|58.5%|50.4%|46.2%|30.0%|20.0%|\n\nAs 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.\n\n---\n\n**Explanation of logistic regression training.**\n\nThank 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.", "claims_and_evidence": "Yes. The claims are clearly proved.", "methods_and_evaluation_criteria": "Below are some concerns about the proposed method.\n\nQ1. **Applicability Beyond VideoQA:** While CodePlexity is applied to analyze the complexity of VideoQA tasks, it appears to be fundamentally a language-based approach with no direct connection to video content (L042 Right). This raises the question of why the authors have limited its application to VideoQA. Could the same methodology be effectively applied to QA datasets in the NLP domain, such as HotpotQA? Clarifying its broader applicability would strengthen the method's relevance.\n\nQ2. **Code Generation Model:** The authors use ViperGPT for code generation, which relies on function templates and few-shot examples to translate questions into code. This raises two concerns:\n(i) Does the granularity of functions influence subtree generation? For instance, functions like `llm_query` and `simple_query` are partially similar. What would happen if these were merged or further decomposed into more fine-grained functions, such as `query_how` or `query_why`?\n(ii) Are few-shot examples used in the prompt? If so, how do the quality and quantity of these examples impact the results? Addressing these points would provide deeper insights into the robustness of the code generation process.\n\nQ3. **Dataset Construction and Fairness:** The CodePlex-QA dataset is constructed using videos different from those in NExT-QA, which may introduce unfairness due to variations in the inherent complexity of the videos. To enhance the robustness and credibility of the pipeline, a comprehensive ablation study could be conducted:\n(i) Apply the pipeline to construct QA pairs using the same video sources as NExT-QA.\n(ii) Use the same threshold to filter out a challenging subset from NExT-QA and evaluate its accuracy.\nSuch an approach would ensure a fairer comparison and make the pipeline more convincing.", "theoretical_claims": "Yes. I think the theoretical claims are no problems.", "experimental_designs_or_analyses": "Q4. The explanation of the logistic regression model training process is somewhat unclear. Specifically, the authors state that each $\\left(\\mathbf{x}_i, y_i^{(j)}\\right)$ pair is a distinct instance (L177 Right). To clarify, does this imply that for a single question $\\mathbf{x}_i$ and its valid subtrees, there are four corresponding labels $y_i^{(0)}, y_i^{(1)}, y_i^{(2)}, y_i^{(3)}$, each being either 1 or 0? If this is the case, how is the regression model trained? Please correct any inaccuracies in my understanding.", "relation_to_broader_scientific_literature": "This paper proposes an effective method for analyzing question complexity in QA tasks by using code as a proxy, an approach that is both reasonable and clear. Statistical analysis demonstrates that CodePlexity outperforms human evaluation and traditional complexity assessment methods. Additionally, the CodePlex-QA dataset confirms the pipeline's reliability in constructing substantially more challenging QA datasets.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The use of code as a proxy for assessing question complexity is novel and effective.\n\n2. The method is supported by comprehensive theoretical proofs and statistical analysis, demonstrating its feasibility.", "other_comments_or_suggestions": "None.", "questions_for_authors": "See above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel data-driven method leveraging visual program generation to systematically evaluate query complexity in VideoQA tasks, introducing CodePlexity as a proxy metric correlating strongly with model performance. Reviewers generally appreciate the methodological novelty, empirical strength, and clear presentation, highlighting that the approach provides valuable insights into model-specific weaknesses and contributes effectively to the creation of challenging benchmarks such as CodePlex-QA. Key concerns raised include reliance on code generation without explicitly considering visual content, potential biases introduced by model-specific definitions of complexity, and generalizability to evolving models. The authors convincingly address these concerns through comprehensive rebuttals, additional experiments, and clarifications, demonstrating robustness, broader applicability beyond VideoQA, and adaptability to newer models. Overall, reviewers agree on the significance and potential impact of this work, leading to a consensus recommendation for acceptance.
Decision: Accept (poster)