{"id":"cb246ef4-3e2f-4de0-971c-081654426b4b","arxiv_id":"2505.13429","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Generated visual program code complexity, learned from abstract syntax subtrees, predicts VideoQA model performance better than human annotators and can construct harder benchmarks.","lead":"This paper introduces a way to measure how hard a video question is for AI models: turn each question into computer code, then analyze that code's complexity. The method predicts model accuracy better than human guesses and can auto-generate harder question benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Program faithfulness is the load-bearing assumption; the paper's own §10.3 shows correctness weakens correlations, leaving open that CodePlexity partly measures generator artifacts on hard questions.","rationale":"The reader's weakest assumption identifies the same load-bearing premise: the mapping z = pi(q) must faithfully reflect the reasoning required to answer a question. I agree with that emphasis. The paper provides genuine independent support for the central claim — held-out model evaluation on NExT-QA, cross-dataset replication on MVBench, the RVP code-generator comparison, and the Section 10.3 analysis showing CodePlexity is more robust than baselines to code correctness. These results make the claim credible. However, they do not establish that CodePlexity measures a stable property of the question rather than a property of the particular code generator's behavior. The CodePlex-QA construction step is especially vulnerable because no code execution or semantic verification is used, and manual filtering only checks answerability of the question, not faithfulness of the generated program. A paraphrase-invariance and cross-generator stability study would settle the concern: if complexity scores remain consistent when the same question is expressed differently or compiled by a different generator, then the proxy is robust; if not, the benchmark's '1.9 times harder' claim is confounded by generator artifacts. Since this is the same core risk the reader already identified and the existing evidence does not refute it, the verdict should remain conditional rather than being upgraded or downgraded.","tokens_in":27761,"tokens_out":9390,"duration_ms":94221,"concrete_test":"Take 200 NExT-QA validation questions and 200 CodePlex-QA questions. For each, generate programs with three independent code-generation backbones (ViperGPT/Codex, RVP, and a current GPT-4-class model), and also produce 5 meaning-preserving paraphrases per question with the same generator. Compute CodePlexity under a fixed subtree vocabulary for all variants. Then: (1) measure Spearman rank correlation of CodePlexity across backbones and across paraphrases; (2) recompute held-out-model mPEG using each backbone's programs. If cross-backbone or cross-paraphrase rank correlations are low, or if mPEG drops substantially for a backbone not used during CodePlexity training, the metric is not a stable property of question complexity and the correctness dependence flagged in Section 10.3 is confirmed as the central confound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"CodePlexity's validity rests on z = pi(q) (Section 3.1) being a faithful mirror of the reasoning needed to answer q. All features — subtree presence, one-hot encoding, logistic regression — are computed on generated code, so if the code generator produces structurally complex but semantically wrong programs on hard questions, the metric measures generator artifacts rather than intrinsic complexity. The paper's own §10.3 (Table 5) shows that for most train models the correlation with mPEG drops when generated code gives incorrect answers (e.g., SeViLA: Cyclomatic 0.1702 to 0.1351; ViperGPT: CodePlexity 0.3128 to 0.2041). This is precisely the failure mode that would bias the metric: hard questions stress the generator, yielding longer and more convoluted but unfaithful programs. The CodePlex-QA pipeline (Section 3.4) amplifies the concern: candidate questions are scored purely from code generated with GPT-3.5 (Section 7.4), without executing the code on the video or verifying semantic fidelity; only 12% manual answerability filtering is applied. The Limitations section also concedes that focusing on syntactic code elements 'may overlook... critical sources of complexity not apparent in the code structure.' Held-out models and MVBench/RVP generalization provide real support, but they do not eliminate the confound: a generator artifact can correlate with model difficulty because hard questions also stress generators. A direct test of stability across code generators and paraphrases is therefore needed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper argues that the complexity of LLM-generated visual programs is a robust, data-driven proxy for the difficulty of VideoQA questions. The authors generate code for questions using ViperGPT and RVP, compute structural metrics (Lines of Code, Cyclomatic Complexity), and propose CodePlexity, a learned metric that combines AST subtree presence features with logistic regression (Eq. 3) to predict model success. They evaluate the resulting complexity scores with the proposed mPEG measure on held-out models and held-out questions in NExT-QA and MVBench, reporting that CodePlexity outperforms human ratings, text-based baselines, and simple code metrics. The paper also uses CodePlexity to filter automatically generated questions, constructing CodePlex-QA, which they report is 1.9 times harder than NExT-QA. The main technical contributions are the interpretable subtree analysis of failure modes and the automatic benchmark construction pipeline.","tokens_in":28080,"tokens_out":3762,"duration_ms":39159,"significance":"If the central claim holds, this is a useful contribution: it offers a scalable and interpretable alternative to expert-curated difficulty measures, with a clean held-out evaluation protocol (four training models and five held-out models in NExT-QA, three and two in MVBench), evaluation on two datasets, and an ablation that controls for video-source effects by using the same VidOR videos as NExT-QA. The paper also makes its code and data available, which strengthens reproducibility. The most important caveat is that the metric is computed only on generated programs, so its validity depends on how faithfully those programs reflect the reasoning required by the question. The paper's own Section 10.3 shows that correlations weaken when generated code is incorrect, which makes the faithfulness concern load-bearing rather than incidental. The lack of statistical uncertainty in the main comparisons is also a substantive gap for a paper whose quantitative claims are differences in mPEG and benchmark accuracy.","major_comments":[{"comment":"The faithfulness of the generated program z = pi(q) is load-bearing, but the paper's own Table 5 shows that all complexity metrics, including CodePlexity, correlate less with model performance when generated code gives incorrect answers (e.g., ViperGPT: CodePlexity drops from 0.3128 to 0.2041; SeViLA: Cyclomatic drops from 0.1702 to 0.1351). This leaves open the confound that hard questions stress the code generator, producing structurally complex but semantically wrong programs, so CodePlexity may partly measure generator artifacts rather than intrinsic question complexity. The CodePlex-QA pipeline in Section 3.4 amplifies this concern because questions are scored purely from GPT-3.5-generated code without executing the code on the video and without semantic-fidelity verification beyond the 12% manual answerability filter. I recommend a direct test of stability across code generators (e.g., Codex, GPT-3.5, GPT-4, RVP) on the same questions, and a subgroup analysis that computes mPEG only on questions where the generated code is correct.","section":"Section 3.1 / Section 10.3, Table 5"},{"comment":"CodePlexity is trained on programs generated by Codex (via the ViperGPT API), but CodePlex-QA is scored using programs generated by a text variant of GPT-3.5 with a different prompt structure. There is no experiment showing that the learned logistic regression weights transfer across code generators. Since Eq. 3 is applied to GPT-3.5-generated programs to select the final benchmark, a distribution shift between training and scoring could change which subtrees are activated and thus distort the complexity scores. The authors should either report CodePlexity's ranking consistency across generators on the same question set, or retrain the metric on the target generator and compare resulting benchmark difficulty.","section":"Section 7.4 / Section 3.4"},{"comment":"The subtree significance test is applied at p < 0.01 over a very large set of candidate subtrees S(D), potentially thousands of hypotheses, without any multiple-testing correction. The intersection set S* in Eq. (7) may therefore contain spurious subtrees, and the subsequent interpretable insights in Section 4.3 (the eight shared subroutines) may be partially driven by false positives. The authors should report the number of subtrees tested and apply a correction such as Bonferroni, Benjamini-Hochberg, or a permutation-based null to justify the p < 0.01 threshold.","section":"Section 3.3, Eq. (6)"},{"comment":"The main quantitative claims are made without error bars or significance tests. For example, in Table 1, CodePlexity outperforms Cyclomatic Complexity by margins that vary from 1.0 to 8.8 mPEG points across held-out models, but there is no confidence interval or hypothesis test to distinguish these differences from noise. Similarly, the '1.9 times harder' claim in Table 2 averages across models with no uncertainty quantification. Because mPEG is an average over alpha thresholds, a bootstrap over questions and models would be an appropriate and straightforward remedy. I request bootstrap confidence intervals for the mPEG values and a paired test of CodePlexity vs. the best baseline for at least the held-out models.","section":"Section 4.1 / Tables 1, 2, 6"}],"minor_comments":[{"comment":"There is a typo in the Limitations paragraph: 'may overlooks critical sources' should be 'may overlook critical sources.'","section":"Broader Impacts and Limitations"},{"comment":"The text reports qualitative trends for human, dependency-tree, and cyclomatic-complexity correlations, but it does not provide numerical correlation coefficients. Reporting Spearman rho or R^2 for each panel would make the comparison in Section 4.2 more precise.","section":"Figure 3"},{"comment":"The human study description reports 65 recruited subjects and 30 retained annotators; please clarify how many comparisons per question were collected before consistency filtering, and whether the 150-question subset was selected randomly or with any stratification.","section":"Section 7.2"},{"comment":"The table caption says 'correlation between the complexity metrics and the mPEG metric'; mPEG is itself derived from correlations, so it would be clearer to state that the table reports the correlation between each complexity metric and the per-bin success rates used to compute PEG.","section":"Table 5"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope and the held-out evaluation design is a genuine strength. The main risk is the faithfulness confound identified in Section 10.3; I would like to see the proposed generator-stability and code-correctness controls before recommending acceptance. The lack of uncertainty quantification is secondary but should be addressed in the revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is worth a serious referee. The central empirical claim—that the complexity of LLM-generated visual programs predicts VideoQA model difficulty better than human ratings or text baselines—holds up under the tests the authors ran, and the evaluation design is genuinely careful. The main caveat is one the authors document but do not fully resolve: program faithfulness is load-bearing, and §10.3 shows that when generated code is wrong, correlations weaken.\n\nWhat is actually new: CodePlexity (AST subtree one-hot features plus logistic regression on model success) goes beyond cyclomatic complexity; the question-generation pipeline that uses CodePlexity to filter hard questions is a sensible operationalization; CodePlex-QA is a useful stress test. The demonstration that humans are poor predictors of model difficulty is clean, even if not entirely surprising.\n\nWhat is solid: the split into training and held-out models, the 80/20 question split, and the replication on MVBench with additional held-out models are the right checks. Table 1 shows CodePlexity ahead of baselines across models. The appendix ablations (NExT-QA*, VidOR-controlled) directly address the most obvious confound about video content. This is honest, reproducible work in spirit, though code and data are not yet shipped.\n\nSoft spots: no error bars or significance tests anywhere; given the noise in model accuracies, the size of the mPEG gaps is uncertain. Second, the faithful-program assumption: CodePlexity is computed on z = pi(q), and if the generator produces long, convoluted programs on hard questions precisely because it is stressed, the metric risks measuring generator artifacts. The paper's own §10.3 supports that worry; correlations drop noticeably on incorrect code. Held-out generalization helps, but a direct test across code generators and paraphrases is needed. Third, the '1.9 times harder' number is an average of per-model ratios, fine as a headline but not a precise claim. Fourth, the 12% manual filtering is small but means the pipeline is not fully automatic.\n\nNone of these refute the main claim; they are addressable. I would send this to reviewers. I would cite it, and I'd bring it to a reading group because the central assumption is worth discussing.","headline":"A solid, well-designed empirical paper; the program-faithfulness caveat is real but does not sink the core claim.","tokens_in":28644,"tokens_out":2559,"would_cite":true,"duration_ms":22557,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Program complexity predicts VideoQA difficulty better than human ratings, and the hardest-filtered questions form a benchmark 1.9 times harder than NExT-QA.","keywords":["video question answering","question difficulty estimation","visual program generation","code complexity","abstract syntax tree","benchmark construction","CodePlexity","VideoQA"],"falsifier":"Take a fixed set of NExT-QA questions, generate programs with two deliberately different generators whose failure patterns on hard questions are uncorrelated, train CodePlexity on one generator's outputs, and evaluate on the other; if the transferred score no longer predicts held-out model success while each generator-specific score does, the central proxy is generator-relative rather than a property of the questions. A cheaper check already available from the paper's data is to compare mPEG on questions whose generated code is semantically incorrect versus correct: if the signal disappears entirely on incorrect code, CodePlexity is tracking program quality rather than question complexity.","tokens_in":27550,"feed_emoji":"🎬","tokens_out":7854,"duration_ms":72538,"temperature":0.7,"pith_summary":"Video question answering is hard to benchmark because human intuition about difficulty does not match where machine models actually fail. This paper argues that an LLM's executable visual program for a question carries a reliable signal of that question's complexity, learnable from model outcomes instead of expert guesses. The introduced CodePlexity score predicts held-out model success on NExT-QA and MVBench better than human rankings, GPT-4 Likert ratings, BERT, dependency-tree depth, lines of code, and cyclomatic complexity. Applying the same score to automatically generated questions produces CodePlex-QA, on which six zero-shot models score about 1.9 times worse than on NExT-QA, with the learned subtrees pointing to shared failures in temporal ordering and fine-grained object analysis.","feed_headline":"Code complexity predicts which video questions stump AI","feed_subtitle":"A learned score over code subtrees builds a benchmark 1.9 times harder than NExT-QA.","key_machinery":"The engine is a compiler-assisted subtree analysis: each generated program is compiled to an Abstract Syntax Tree, all valid subtrees are mined, always-co-occurring nested subtrees are merged, and each question becomes a one-hot encoding over the distinct subtrees. A logistic regression trained on the pooled success labels of four VideoQA models then assigns each subtree a weight, and the final score $\\mathrm{CodePlexity}(z)=-\\sigma(w x+b)$ is the negative predicted success probability. The same subtree vocabulary doubles as an interpretable diagnostic: the eight subtrees shared by all training models cluster into patterns that require ordering frames in time (loops over frames, breaks after a first match, frame-after-event lookups) and patterns that require fine-grained object or relationship checks, giving a human-readable account of common failure modes.","core_discovery":"The central claim is that the complexity of a VideoQA question is encoded in the executable program an LLM writes to answer it, so question difficulty can be read off the program rather than judged from the natural-language text. Concretely, a generator $\\pi$ turns question $q$ into code $z=\\pi(q)$; each program is compiled to an Abstract Syntax Tree, subtrees are mined and merged, and the presence pattern becomes a one-hot vector $x_i$. A logistic regression trained on the pooled success/failure labels of several VideoQA models yields $\\mathrm{CodePlexity}(z)=-\\sigma(w x_i+b)$, the negative predicted success probability. The paper reports that, measured by the Performance Extremity Gap averaged over difficulty fractions, CodePlexity beats human annotator ELO rankings, GPT-4 Likert scores, BERT trained on the same labels, dependency-tree depth, lines of code, and cyclomatic complexity, on held-out models and on the MVBench dataset. The same score filters an LLM-generated pool of 20,791 candidate questions down to CodePlex-QA (1,981 questions after a 12% manual answerability check), where zero-shot models score about 1.9 times lower than on NExT-QA; the paper also reports that correlations weaken, but less for CodePlexity, when generated code is semantically incorrect.","pith_inferences":["If program complexity faithfully tracks reasoning load, the same CodePlexity score could drive curriculum design, active sampling, or test-time budgeting in any learned QA pipeline, not just benchmark construction.","The paper's own number shows fine-tuning SeViLA on CodePlex-QA improves accuracy only about 2.5 points, much less than fine-tuning on NExT-QA; a testable consequence is that these hard questions expose a representation gap that small amounts of extra data will not close.","Because the method's input is only question-plus-program, the residual between CodePlexity and actual model performance could be used as a separate, trainable estimator of video complexity, in line with the chain-rule motivation the paper sketches.","One caution worth testing: if two different program generators fail on different kinds of hard questions, transferability of a CodePlexity model trained on one generator may degrade; the claim of robustness across generators is currently supported only by a two-generator comparison."],"forward_implications":["Code complexity correlates with held-out model performance across architectures that never saw the metric during training, so the signal is not an artifact of one model family.","The learned subtree patterns identify shared weaknesses, chiefly fine-grained temporal ordering and object-centric spatial reasoning, giving model designers concrete places to intervene.","Because the measure is data-driven and re-trainable, it can be re-estimated as new VideoQA models appear, unlike fixed human-designed difficulty heuristics.","CodePlex-QA is harder than NExT-QA for every zero-shot model tested and harder than ATP-Hard for the strongest models, showing that question selection with this score can produce useful benchmarks without hand-written difficulty rules.","Code generation quality bounds the metric: stronger code generators give stronger correlations, and correlations weaken on incorrect code, so improving program synthesis directly improves complexity estimation."],"supporting_citations":[{"why":"Supplies ViperGPT, whose generated programs are the main code source for complexity analysis and whose predictions are one of the model signals used to ground the metric.","marker":"Surís et al., 2023"},{"why":"Supplies RVP, the second code generator used to check that complexity correlations survive a different program synthesis model.","marker":"Ge et al., 2024"},{"why":"Supplies NExT-QA, the primary benchmark of human-annotated questions and the pool from which filtered hard subsets are formed.","marker":"Xiao et al., 2021"},{"why":"Supplies the ATP baseline and the ATP-Hard adversarial subset, the comparison showing single-frame baselines and the reference hard split.","marker":"Buch et al., 2022"},{"why":"Defines cyclomatic complexity, the key structural baseline that CodePlexity must outperform.","marker":"McCabe, 1976"},{"why":"Provides the theoretical framing that the complexity of a generated program can proxy the complexity of the question.","marker":"Kolmogorov, 1963"},{"why":"Supplies SeViLA, both a training model whose success labels train the logistic regression and a zero-shot variant held out for evaluation.","marker":"Yu et al., 2023a"},{"why":"Supplies VIOLET, a training model whose success labels are used to train the CodePlexity model.","marker":"Fu et al., 2021"},{"why":"Supplies InternVideo, a held-out model used to test whether the learned metric generalizes beyond training models.","marker":"Wang et al., 2022a"},{"why":"Supplies HGA, a held-out GNN-based VideoQA model showing the metric extends beyond video-language transformers.","marker":"Jiang & Han, 2020"}],"fun_headline_variants":["Code complexity predicts which video questions trip up AI","Program subtrees decode video QA difficulty better than humans","AI-generated code gauges video question hardness automatically","From code to challenge: new benchmark 1.9x harder than NExT-QA"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The weakest link is that the code generated from a question faithfully represents the reasoning needed to answer it; if the generator's programs are not a faithful mirror, especially for hard questions, then CodePlexity measures generator artifacts rather than question difficulty.","fun_headline_variants_meta":{"raw":{"variants":["Code complexity predicts which video questions trip up AI","Program subtrees decode video QA difficulty better than humans","AI-generated code gauges video question hardness automatically","From code to challenge: new benchmark 1.9x harder than NExT-QA"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000331,"raw_usage":{"total_tokens":1858,"prompt_tokens":973,"completion_tokens":885,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":589,"completion_tokens_details":{"reasoning_tokens":815}},"tokens_in":589,"tokens_out":885,"duration_ms":7116,"temperature":1.0,"reasoning_tokens":815,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:13:38.090604+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a fixed set of NExT-QA questions, generate programs with two deliberately different generators whose failure patterns on hard questions are uncorrelated, train CodePlexity on one generator's outputs, and evaluate on the other; if the transferred score no longer predicts held-out model success while each generator-specific score does, the central proxy is generator-relative rather than a property of the questions. A cheaper check already available from the paper's data is to compare mPEG on questions whose generated code is semantically incorrect versus correct: if the signal disappears entirely on incorrect code, CodePlexity is tracking program quality rather than question complexity.","supporting_citations":[{"cited_title":"Next-QA : Next phase of question-answering to explaining temporal actions","cited_arxiv_id":null,"evidence_quote":"Supplies NExT-QA, the primary benchmark of human-annotated questions and the pool from which filtered hard subsets are formed."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines cyclomatic complexity, the key structural baseline that CodePlexity must outperform."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the theoretical framing that the complexity of a generated program can proxy the complexity of the question."},{"cited_title":"and Han, Y","cited_arxiv_id":null,"evidence_quote":"Supplies HGA, a held-out GNN-based VideoQA model showing the metric extends beyond video-language transformers."}],"review_version":1}