Why Full-Search RDO Is So Slow in AV1 Encoding

Rate-Distortion Optimization (RDO) is the decision-making engine of modern video compression, balancing visual fidelity against bitrate by minimizing the cost function \(J = D + \lambda R\). In the AV1 video codec, executing a brute-force or "full-search" RDO—evaluating every possible combination of encoding parameters to find the absolute mathematical optimum—results in extreme computational bottlenecks. This article explains the technical mechanics behind AV1’s architecture, demonstrating how its expanded block partitioning, deep intra/inter prediction toolsets, and extensive transform options cause the full-search RDO search space to explode exponentially.

Exponential Partitioning Trees

The primary driver of RDO complexity in AV1 is the block partitioning structure. Unlike legacy codecs that primarily rely on symmetric quad-tree splitting, AV1 uses a 128x128 Superblock (SB) architecture with recursive splitting down to 4x4 blocks.

AV1 supports ten distinct split modes at each node:

• None (no split)
• Horizontal split (2:1)
• Vertical split (1:2)
• Quad-tree split (4 sub-blocks)
• Horizontal 4:1 split
• Vertical 1:4 split
• Four "T-shape" partition variants (horizontal and vertical odd splits)

To evaluate a single 128x128 superblock via full search, the encoder must recursively calculate the rate-distortion cost of the parent block and compare it against the summed costs of all possible child configurations down to several levels deep. The sheer number of valid geometric tree permutations per superblock reaches into the millions.

Multiplicity of Prediction Modes

Once a partition geometry is proposed, the encoder must determine the optimal prediction mode for that block. AV1 drastically expands the candidate pool for both intra and inter frames.

For intra-prediction, AV1 provides 56 directional angles, alongside non-directional modes (DC, Smooth, Paeth) and advanced tools like Chroma from Luma (CfL), which models chroma pixels as a linear function of reconstructed luma pixels.

For inter-prediction, the search space is even larger:

• Compound Prediction: Combines two motion vectors using multiple blending strategies, including distance-weighted, difference-weighted, and wedge-codebook masking (which divides a block diagonally using predefined geometric shapes).
• Warped Motion and Global Motion: Evaluates affine models (rotation, zoom, shear) alongside standard translational motion.
• Reference Frames: AV1 allows blocks to reference up to seven distinct frames out of a pool of eight buffered references, requiring extensive motion estimation across multiple temporal directions.

Testing every prediction mode requires computing motion vectors, generating prediction blocks, and determining residuals for each candidate.

The Transform Domain Combinatorial Explosion

In traditional codecs like H.264, residual data is usually transformed using standard Discrete Cosine Transform (DCT) variants. AV1, however, implements up to 16 transform combinations for various block shapes, pairing separable transforms across horizontal and vertical dimensions.

These include:

• DCT-2
• Asymmetric Discrete Sine Transforms (ADST, flipped ADST)
• Identity transforms (no transform applied in one or both directions)

In a full-search RDO pipeline, the encoder cannot merely estimate transform efficiency; it must compute the forward transform, quantize the coefficients, run entropy coding to measure the exact bit cost (\(R\)), perform inverse quantization, run the inverse transform, and subtract the reconstructed block from the source to measure pixel distortion (\(D\), typically using Sum of Squared Errors). Performing this full loop for 16 transform types across thousands of partition possibilities is computationally crippling.

The Cost of Exact Bitstream Modeling

Calculating the rate (\(R\)) in the RDO equation requires exact knowledge of how many bits a given decision will emit. AV1 uses a multi-symbol arithmetic coder (a non-binary arithmetic coding engine adapted from Daala) that dynamically tracks probability states using Cumulative Distribution Functions (CDFs).

Because CDF contexts update based on neighboring decisions, calculating exact bit costs is strictly serial and cannot be easily parallelized across neighboring blocks. A full-search encoder must either clone and roll back entropy coder states millions of times per frame or execute expensive simulated entropy coding passes for every candidate branch.

The Necessity of Heuristics

Because an unconstrained, full-search RDO pass on raw 4K or 1080p footage would require days or weeks to process a single minute of video, practical AV1 encoders—such as SVT-AV1, libaom, and rav1e—do not use pure full search. Instead, production encoders rely on machine-learning-driven early termination, dynamic pruning of unlikely partitions, and stage-filtered RDO (evaluating rough metrics like Sum of Absolute Transformed Differences before committing to full entropy-coded RDO) to deliver AV1's high compression efficiency within manageable timeframes.