# An Attribute-Based Measure of Video Complexity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 67 references that are in the map.
- First posted on arXiv 30 May 2026.

## Builds on (most cited first, 25 of 25)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [LLaVA-OneVision: Easy Visual Task Transfer](https://mlsanity.com/paper/2408.03326/) (2024)
- [The Kinetics Human Action Video Dataset](https://mlsanity.com/paper/1705.06950/) (2017)
- [InternVL3: Exploring Advanced Training and Test-Time Recipes for Open-Source Multimodal Models](https://mlsanity.com/paper/2504.10479/) (2025)
- [Video-MME: The First-Ever Comprehensive Evaluation Benchmark of Multi-modal LLMs in Video Analysis](https://mlsanity.com/paper/2405.21075/) (2024)
- [Video-LLaVA: Learning United Visual Representation by Alignment Before Projection](https://mlsanity.com/paper/2311.10122/) (2023)
- [MVBench: A Comprehensive Multi-modal Video Understanding Benchmark](https://mlsanity.com/paper/2311.17005/) (2023)
- [NExT-QA:Next Phase of Question-Answering to Explaining Temporal Actions](https://mlsanity.com/paper/2105.08276/) (2021)
- [EgoSchema: A Diagnostic Benchmark for Very Long-form Video Language Understanding](https://mlsanity.com/paper/2308.09126/) (2023)
- [LongVideoBench: A Benchmark for Long-context Interleaved Video-Language Understanding](https://mlsanity.com/paper/2407.15754/) (2024)
- [VideoLLaMA 3: Frontier Multimodal Foundation Models for Image and Video Understanding](https://mlsanity.com/paper/2501.13106/) (2025)
- [Adaptive Computation Time for Recurrent Neural Networks](https://mlsanity.com/paper/1603.08983/) (2016)
- [Measuring Calibration in Deep Learning](https://mlsanity.com/paper/1904.01685/) (2019)
- [TempCompass: Do Video LLMs Really Understand Videos?](https://mlsanity.com/paper/2403.00476/) (2024)
- [What matters when building vision-language models?](https://mlsanity.com/paper/2405.02246/) (2024)
- [Competence-based Curriculum Learning for Neural Machine Translation](https://mlsanity.com/paper/1903.09848/) (2019)
- [Qwen2.5-1M Technical Report](https://mlsanity.com/paper/2501.15383/) (2025)
- [Evaluating CLIP: Towards Characterization of Broader Capabilities and Downstream Implications](https://mlsanity.com/paper/2108.02818/) (2021)
- [VideoLLM: Modeling Video Sequence with Large Language Models](https://mlsanity.com/paper/2305.13292/) (2023)
- [CinePile: A Long Video Question Answering Dataset and Benchmark](https://mlsanity.com/paper/2405.08813/) (2024)
- [Apollo: An Exploration of Video Understanding in Large Multimodal Models](https://mlsanity.com/paper/2412.10360/) (2024)
- [Answer, Assemble, Ace: Understanding How LMs Answer Multiple Choice Questions](https://mlsanity.com/paper/2407.15018/) (2024)
- [Breaking Down Video LLM Benchmarks: Knowledge, Spatial Perception, or True Temporal Understanding?](https://mlsanity.com/paper/2505.14321/) (2025)
- [Understanding Complexity in VideoQA via Visual Program Generation](https://mlsanity.com/paper/2505.13429/) (2025)

## Abstract (arXiv)

A new framework for the estimation of the complexity posed by video-question pairs to video-LLMs, Video Attribute-Based Complexity (VideoABC), is proposed. Video complexity is defined as the probability of failure of a video-LLM for a given video-question pair. VideoABC is a non-parametric complexity measure, using a reference video dataset and a pre-defined vocabulary of video attributes informative of complexity, eg the scene complexity or the speed of the video event informative of the question. In a training phase, reference videos are projected into the space of these attributes, which is then quantized. The expected ABC of each quantization cell is then computed. Given a new video and its projection into the attribute space, complexity is estimated by the expected ABC of the associated quantization cell. To enable the use of VideoABC with small reference video datasets, two quantizers are combined: a k-means quantizer that enables accurate complexity estimates for samples in the distribution of the reference dataset and a universal lattice quantizer that guarantees generalization to out-of-distribution samples. A synthetic video generation procedure, inspired by target-distractor manipulations of psychophysics studies, is proposed to populate the cells of the lattice quantizer during training, enabling the computation of their expected ABCs. Experimental results show that VideoABCis effective even with very low-dimensional attribute representations, substantially outperforming approaches like `video-LLM as judge' with much less complexity. Finally, the explainable nature of the VideoABC score, in terms of well-defined attributes, is shown to provide insights on how the attribute composition of benchmarks affects their complexity.