Modern video encoders spend most of their time on one decision: how to cut each frame into blocks. In Versatile Video Coding (VVC, the H.266 standard), the reference encoder tries nearly every way of recursively splitting a 128×128 region into smaller rectangles. For each candidate it runs full prediction, transform and entropy coding, then keeps the split with the lowest cost $J = D + \lambda R$, where $D$ is distortion, $R$ is bits and $\lambda$ sets how the two are weighed. This search accounts for over 97% of intra encoding time (DeepQTMT). Current speedups come in two kinds. Handcrafted gradient rules are readable but rigid. Deep convolutional classifiers are more adaptive, but nobody can say why they prune a given split. The deep classifiers also carry their own sequential cost: they run one stage per level of the split tree.
We propose learning very small, crisp decision trees with sparse linear leaves. The trees read cheap gradient features computed only from the source pixels. They are trained on labels weighted by how much rate-distortion cost a wrong pruning decision would cause. Each tree has three outcomes: prune this split, keep it, or defer to the exhaustive search. Because the features never depend on the encoder's earlier decisions, the tree can be evaluated for every candidate block of a region in one batched pass. This removes the stage-by-stage dependency that makes deep cascades slow. Every pruning rule is a short inequality that an engineer can read, switch off, and measure. The claim is that this matches the speed-quality trade-off of a deep partition network on the same encoder, with far lower predictor latency and a rule-level audit trail.
Core Claim and What Is New
Three kinds of prior work motivate the proposal, and each leaves a specific gap.
The non-learned cross-block rule of Cross-Block Difference Guided Fast CU Partition compares directional Sobel gradients between candidate sub-blocks against fixed empirical thresholds. It reaches 41.64% time saving at 0.97% BD-rate increase on VTM-9.3. BD-rate is the average bitrate change needed to reach equal quality, so lower is better. This shows that cheap, readable features carry most of the pruning signal. Its thresholds, however, are static and are not tuned to an rate-distortion objective.
DeepQTMT trains a six-stage early-exit network with a loss that is aware of rate-distortion cost, on the CPIV dataset of intra partitions. It cuts VTM-7.0 time by 44.65–66.88% at 1.32–3.19% BD-rate increase. Its decisions are opaque, and its stages run in sequence.
The two-stage method of Bagged Tree and ResNet-Based Joint Fast CTU Partition already uses a tree, but only for the coarsest HEVC split decision. That tree alone gives 22.37% saving at 0.25% loss. The method then hands fine decisions to a 34-layer ResNet. Its authors concede that this network is heavy, and they report that its errors cluster at object boundaries.
So neither "trees for partitioning" nor "rules for partitioning" is new by itself. The new element is a specific combination. First, the trees are trained with a rate-distortion-weighted loss and crispification, borrowed from interpretable reinforcement-learning policies. Second, they have an explicit defer outcome. Third, they are evaluated in one pass that does not depend on earlier decisions. Fourth, the claim is tested as a trade-off among predictor latency, readability and BD-rate on a single encoder version.
The method comes from interpretable control. Interpretable Continuous Control Trees use "differentiable crispification": the tree makes hard true/false routing decisions in the forward pass while still passing gradients during training, and it places sparse linear controllers at the leaves. The authors match deep networks with 300–600x fewer parameters. Linear Model U-Trees show that linear leaves let shallow trees approximate complex value functions. They also show that closely imitating a teacher does not guarantee good task performance, which is why we train on the encoder's rate-distortion outcome directly rather than imitating a CNN.
The latency argument comes from the depth-latency literature. The Efficiency Misnomer shows that sequential depth, not operation count, dominates wall-clock time. Double-Win NAS and VanillaNet turn that observation into shallow deployable networks. Those works flatten the network. We flatten the dependency structure of the decision itself.
Method
For a candidate block $n$ and split type $m$ (quad, horizontal or vertical binary, horizontal or vertical ternary), let $\Delta J_{n,m} = J^*_{n,\neg m} - J^*_n$. This is the increase in best achievable cost if split $m$ is forbidden. It is zero when $m$ was not the encoder's final choice.
Labels come from exhaustive VTM encodes. We train a tree $f_m$ per split type, conditioned on the quantization parameter (QP, which sets how coarsely the encoder quantizes) and on block size. Each tree outputs a leaf score $s$. The loss charges each wrong prune by its cost increase $\Delta J$ and each missed prune by the time that split would have taken. The per-split time is measured once from encoder profiling.
At deployment, a node is pruned when $s > \tau_{\text{hi}}$, kept for full search when $s < \tau_{\text{lo}}$, and otherwise deferred to the unmodified search. The pair $(\tau_{\text{lo}}, \tau_{\text{hi}})$ acts as a speed-quality knob that can be read directly.
The features are a fixed, cheap set computed from source pixels. They include the four directional Sobel energies of each candidate sub-block and their max/min ratios, following Cross-Block Difference. They also include sub-block variances, mean differences, and the QP. Since none of these depends on a parent's encoding result, a whole region's candidate nodes form one feature matrix, and all trees evaluate in one vectorized pass. Tree depth and leaf sparsity are capped so that each rule reads as at most four inequalities plus a linear score over at most three features. The trees are then exported as plain C code inside VTM.
Research Program
The work has three parts. The first is a training and export pipeline built on CPIV-style exhaustive VTM labels, with the rate-distortion-weighted, crispified tree training described above.
The second is a latency study. We profile predictor cost on the encoder's CPU and, separately, in batched form. We compare three versions under identical features, differing only in dependency structure: the one-pass trees, the same trees made sequential by adding features from the parent's result, and DeepQTMT's staged cascade. This separates what one-pass evaluation buys from what the tree representation buys.
The third is an audit protocol. For each rule we predict its time and BD-rate contribution from training statistics, then measure it by disabling that single rule in the encoder. How closely prediction matches measurement quantifies whether the explanations are faithful. We also map where deferrals concentrate, testing whether they fall on the object-boundary blocks where the BTRNFAjoint network reportedly fails.
Baselines
The naive reference point is unmodified VTM All-Intra with exhaustive partition search. It defines 0% time saving and 0% BD-rate, and all other methods are measured against it on the same machine.
The strongest non-learned competitor is Cross-Block Difference (paper), which reports 41.64% average time saving at 0.97% BD-rate on VTM-9.3 over classes A1–E at QPs 22/27/32/37. We will reimplement it on the same VTM version and features. We will also give its thresholds the same QP-conditioned tuning budget, in encoder evaluations on the training sequences, that our trees receive. This makes it a fairly tuned threshold rule rather than a fixed one. Beating it means lower BD-rate at equal time saving across the operating curve.
The strongest learned competitor is DeepQTMT (paper), which reports 44.65–66.88% time reduction at 1.32–3.19% BD-rate on VTM-7.0. Because the version differs from our target, we will run its released model, or a retrained one on the same CPIV data, inside our VTM build. We will sweep its exit thresholds to trace a full curve. Beating it means matching its BD-rate at equal time saving while using a predictor that is at least an order of magnitude cheaper per region and contains only readable rules. Merely matching it at higher readability is the minimum acceptable result.
Two ablations isolate the key ingredients. The first is unconstrained gradient-boosted trees on the same features. They show how much accuracy the readability caps cost. The second is our trees with the defer outcome removed, so every node is forced to prune or keep. It shows what deferral contributes near object boundaries.
Why not just…?
Why not just tune the Cross-Block Difference thresholds per QP? This is the most serious threat. A single-split tree with depth one is a threshold rule, so our model family contains it. The ablation that grows tree depth from one upward on identical features, under an identical tuning budget, answers the question directly. If depth-one trees match deeper ones, we will report that tuned thresholds suffice and that the value of learning lies only in the rate-distortion-weighted objective and deferral. We will then test those two ingredients on the threshold rule alone.
Why not just distill DeepQTMT into a tree? Imitation-style extraction, as in Linear Model U-Trees, inherits the teacher's errors. That work also found that close imitation did not guarantee task performance. We include a distilled tree with the same capacity caps, trained on DeepQTMT's outputs instead of $\Delta J$, and compare BD-rate at matched time saving.
Why not just keep the CNN, since DeepQTMT reports under 5% overhead? In a slow reference encoder the overhead is indeed small. Once pruning removes around 60% of encoder time, the same absolute overhead becomes a much larger share of what remains, and it grows further in faster encoders. We will report predictor time as a fraction of the pruned encoder's time, not the original's. We will also concede the latency argument if that fraction stays negligible, since readability and auditability remain the claim in that case.
Decisive Experiments
We train on CPIV and on exhaustive encodes of non-test sequences. Testing uses JVET common test conditions classes A1–E, All-Intra, QPs 22/27/32/37, on a single VTM build. We report time saving, BD-rate in PSNR and VMAF, predictor time per region, and rule count, and we plot full trade-off curves for every method.
Four outcomes decide the proposal. The first is whether the trees' curve lies on or below DeepQTMT's on BD-rate at matched time saving. The second is whether depth greater than one beats fairly tuned thresholds. The third is whether one-pass evaluation cuts predictor time relative to the sequential variant without costing BD-rate. The fourth is whether rule-level predicted effects correlate with measured effects when each rule is disabled.
A loss on the first outcome with a win on the fourth would still establish readable rules as an honest, measured alternative. A loss on the second would redirect the contribution to training objective and deferral rather than tree structure.
References
- DeepQTMT: A Deep Learning Approach for Fast QTMT-Based CU Partition of Intra-Mode VVC
- Cross-Block Difference Guided Fast CU Partition for VVC Intra Coding
- Bagged Tree and ResNet-Based Joint End-to-End Fast CTU Partition Decision Algorithm for Video Intra Coding
- Learning Interpretable, High-Performing Policies for Autonomous Driving
- Toward Interpretable Deep Reinforcement Learning with Linear Model U-Trees
- The Efficiency Misnomer
- Double-Win NAS: Towards Deep-to-Shallow Transformable Neural Architecture Search for Intelligent Embedded Systems
- VanillaNet: the Power of Minimalism in Deep Learning