Many image and video quality metrics end with the same step. They score every pixel, patch, or frame, then keep only the worst fraction and average it. This is called worst-case or percentile pooling, and it exists because people judge a video by its most annoying defect, not by its average. CAMBI, Netflix's banding detector, is the clearest case. It computes a banding map at five spatial scales and four contrast levels for every pixel of every frame, then averages only the worst 30% of pixels. That pooling is why it reaches a rank correlation of -0.923 with human scores, where PSNR reaches -0.202 and VMAF 0.088 (CAMBI). The pipeline is lopsided, though. The expensive part is computed uniformly everywhere, and most of it is then thrown away.
We propose to compute the metric coarse-to-fine over a hierarchy of frames, regions, and scales, and to skip any part that provably cannot land in the worst tail. The final pooled score should be identical to the full computation, or within a stated tolerance at a stated confidence. The idea borrows the input-adaptive compute principle from language-model reasoning, where cheap early probes decide how much work each query gets (Learning How Hard to Think). Percentile pooling adds something those settings lack. Because the output depends only on order statistics, a skip decision can be checked exactly rather than guessed.
Core Claim
Let $c_i$ be the local badness value of unit $i$ (a pixel, block, or frame), let $N$ be the number of units, and let the pooled score be the mean of the $\lceil qN \rceil$ largest $c_i$, with $q = 0.3$ for CAMBI. Suppose we have computed exact values for a subset $E$ of units, and at least $\lceil qN\rceil$ of them satisfy $c_i \ge t$ for some value $t$. Then every unskipped tail slot is already filled by a value at least $t$. Any remaining unit $j$ whose cheap upper bound satisfies
$$U_j \le t$$
can be skipped without changing the pooled score, because it can at most tie a value already inside the tail. We run this rule top-down on a tree. The root is the video, below it are frames, then spatial blocks, then scales. A node whose bound falls below the running threshold is pruned together with all of its descendants.
When no analytic bound exists, we train a lightweight probe that predicts an upper quantile of $c_j$. We calibrate its pruning threshold with Learn-then-Test, the conformal risk-control procedure used for stopping reasoning early in Thought calibration. This gives the guarantee that the pooled-score error stays below $\varepsilon$ with probability at least $1-\delta$ over new videos.
What is new is not a better metric. It is a way to make existing worst-case metrics cheaper while provably preserving what they output. This differs in kind from difficulty routers, which trade accuracy for compute heuristically.
Research Program
The work has three parts.
Exact bounds for CAMBI. We derive cheap bounds for CAMBI's per-pixel banding value from quantities that gate it. Banding can only occur in smooth regions, so local gradient and flatness statistics computed at the coarsest scale should upper-bound the multiscale contrast response. We will verify this bound analytically against CAMBI's definition. Where the analysis fails, we will fall back to empirically calibrated bounds. We will be explicit about which regime each result belongs to.
Temporal extension. We extend the same rule to temporal percentile pooling over frames, as evaluated in A Comparative Evaluation of Temporal Pooling Methods for Blind Video Quality Assessment. There the expensive unit is a blind image-quality feature extractor run on a whole frame, and the bound comes from a learned, calibrated probe on a downsampled frame.
Training-time use. We apply the pruning during training of learned quality models whose loss uses percentile pooling. Only tail units receive gradients under such a loss, so running the full backbone forward and backward on units that provably or probably fall outside the tail is wasted training compute. The file notes that adaptive allocation during training is nearly unexplored. The only training-time example it contains is rollout allocation for reinforcement learning (Adaptive Rollout Allocation).
Where hierarchy helps and where it hurts. The hierarchy enters as the structure of the computation, and the hierarchical-classification literature both supplies and constrains the design. HD-CNN shows that conditional execution of fine components after a coarse decision gives 2.8x to 6.3x test-time speedups. Its routing is learned and unverified, whereas our pruning is checked against order statistics. Bonsai supplies the constraint. In deep trees, an early wrong decision permanently cuts off the correct leaf. For us, that means probabilistic pruning errors compound with depth. We will therefore keep the tree shallow and wide (video, frame, block of roughly 64×64, scale) and split the error budget $\delta$ across levels with a union bound.
An honest limit. Savings depend on how much of the content has bounds below the tail threshold. If banding covers 2% of a frame while $q=0.3$, the threshold sits near zero. In that case only units whose bound is essentially zero, such as textured regions CAMBI treats as non-flat, can be skipped. We will report the distribution of skip rates against artifact footprint rather than a single average.
Baselines
The reference point is full CAMBI, computed densely at all scales, contrasts, pixels, and frames. On the Netflix 4K banding subjective dataset it reports SROCC -0.923 (CAMBI). Our exact variant must reproduce this correlation to the third decimal, and in fact frame by frame, since it should output identical scores. It wins on measured compute: arithmetic operations and wall-clock time on the same hardware and implementation. In the calibrated variant, a win means a lower compute fraction at a correlation drop of at most 0.005.
The naive competitor is uniform reduction at matched compute. This means running CAMBI on every $k$-th frame, or on randomly subsampled blocks, with $k$ chosen so its measured cost equals ours on each clip. It is the strongest simple alternative because banding is often temporally persistent, so uniform frame striding may lose very little. We beat it only if, at equal cost, our score deviation from full CAMBI is lower. The comparison should be especially clear on clips with transient or localized banding, and the correlation with human scores should be no worse.
The strongest learned competitor is a distilled regressor: a small network trained to predict the full CAMBI score directly from downsampled frames, given the same training videos and tuning budget as our probe. For the temporal part, the strong baseline is dense extraction followed by EPooling, which ensembles mean, VQPooling, and hysteresis pooling. The file reports its gain only as about 0.03 SRCC over mean pooling on LIVE-VQC, and gives no absolute KoNViD-1k or LIVE-VQC values from that paper. We will therefore rerun it ourselves on the same frame features.
Two ablations isolate the key ingredient. The first uses the same probe and tree but prunes with a fixed heuristic threshold, as a difficulty router in the style of Learning How Hard to Think would, instead of the order-statistic rule. The second uses the order-statistic rule on a flat set of blocks with no hierarchy. The first ablation tells us whether certification matters. The second tells us whether the hierarchy adds savings beyond single-level pruning.
Why not just…?
Why not just subsample frames or run at lower resolution? This is the real threat. If banding persists across most frames, uniform striding may match us at equal cost, and we will say so if it does. The difference shows on content where the worst segment is short. Striding can miss it, and worst-case pooling exists precisely because such segments dominate human judgment (A comparative study of quality and content-based spatial pooling strategies). We will measure how often, and by how much, striding changes the pooled score relative to full CAMBI, split by persistent versus transient artifacts. If striding is never worse than our method, the proposal reduces to its training-time part.
Why not just distill the metric into a cheap network? A distilled regressor offers no guarantee of agreeing with the metric that practitioners trust and deploy. It is also most likely to fail on the rare, severe cases the metric was built to catch. Our exact mode gives the same answer by construction, and our calibrated mode gives a stated error bound. The experiment reports worst-case deviation over the test clips, not just mean deviation, for both approaches.
Why not just use a learned difficulty probe with a threshold, as in adaptive LLM compute? This is our first ablation. Damani et al. note that noisy difficulty predictions cause over-allocation to hard cases (Learning How Hard to Think). In our setting the mirror failure is under-allocation: pruning a region that belonged in the tail. The order-statistic rule prevents that exactly when an analytic bound exists, and bounds its probability otherwise. The ablation shows how often the heuristic prunes true tail units.
Decisive Experiments
On the Netflix 4K banding dataset, and on BAND-2k (BAND-2k) for broader content, we report five things: compute fraction versus full CAMBI, per-clip score deviation, SROCC against human scores, skip rate as a function of artifact footprint, and a false-positive check on clean encodes, where CAMBI stays below 5.
On KoNViD-1k and LIVE-VQC, we apply frame-level calibrated pruning to BRISQUE and CORNIA features under worst-percentile and EPooling-style temporal pooling. We report realized coverage of the $\varepsilon$ guarantee against the target $1-\delta$ and the SRCC change against dense extraction.
For training, we fine-tune a learned blind quality model with a percentile-pooled loss on KoNViD-1k, with and without pruned forward and backward passes. We compare final SRCC at matched wall-clock time.
The idea fails if either of two things happens. Exact pruning may save under 20% on realistic content because tail thresholds sit near zero. Or uniform striding may match calibrated pruning at equal cost across both persistent and transient artifact clips.
References
- CAMBI: Contrast-aware Multiscale Banding Index
- Learning How Hard to Think: Input-Adaptive Allocation of LM Computation
- Thought calibration: Efficient and confident test-time scaling
- A Comparative Evaluation Of Temporal Pooling Methods For Blind Video Quality Assessment
- Adaptive Rollout Allocation for Online Reinforcement Learning with Verifiable Rewards
- HD-CNN: Hierarchical Deep Convolutional Neural Networks for Large Scale Visual Recognition
- Bonsai: diverse and shallow trees for extreme multi-label classification
- A comparative study of quality and content-based spatial pooling strategies in image quality assessment
- BAND-2k: Banding Artifact Noticeable Database for Banding Detection and Quality Assessment