AV1 Arithmetic Coder Probability Estimation Limits

This article provides a technical overview of the probability estimation accuracy limits within the AV1 video codec's multi-symbol arithmetic coder. It examines how cumulative distribution function (CDF) quantization, fixed-point precision bounds, minimum probability constraints, and dynamic adaptation algorithms collectively dictate the coder's statistical modeling resolution and theoretical compression ceiling.

CDF Representation and Scale Limits

AV1 uses a multi-symbol arithmetic coding engine derived from the Daala entropy coder, replacing the binary arithmetic coder (CABAC) used in prior standards like VP9 and HEVC. Instead of tracking independent binary states, AV1 tracks symbol probabilities using Cumulative Distribution Functions (CDFs).

The precision of these probabilities is bounded by fixed-point integer math:

• Total Scale Factor: The arithmetic coder normalizes total probability to a fixed scale of \(2^{15}\) (32,768). All cumulative frequencies must sum to this value.
• Granularity Bound: The finest discernible probability difference between two adjacent symbols is \(1 / 32,768\) (approximately \(0.00305\%\)). Probabilities smaller than this step cannot be distinguished or updated, setting a hard structural ceiling on estimation accuracy.

Minimum Probability Clamping

To prevent undefined behavior, symbol expansion overflows, or zero-width coding intervals, the arithmetic engine requires that every symbol in the alphabet possesses a non-zero probability.

• Strict Monotonicity: A valid CDF must strictly satisfy \(CDF[i] < CDF[i+1]\) for all active symbols \(i\) in an alphabet of size \(M\).
• Reserved Mass: To enforce distinct cumulative values, each symbol is allocated a minimum probability mass. In an \(M\)-ary alphabet, the remaining probability space available for estimation dynamic range is \(32,768 - M\). For maximum native alphabet sizes (up to 16 symbols), this reservation slightly compresses the representable probability envelope for highly dominant symbols.
• Coding Penalty: Rare events that occur with a true probability lower than \(1 / 32,768\) must be encoded as if their probability is at least \(1 / 32,768\), imposing a minor, unavoidable rate-distortion penalty on extreme outliers.

Adaptation Rate and Step Precision

AV1 continuously adapts its CDF models frame-by-frame and block-by-block based on observed symbol occurrences. This update process introduces secondary accuracy limits tied to the adaptation formula:

\[CDF_{new}[i] = CDF_{old}[i] + \left\lfloor \frac{(Target[i] - CDF_{old}[i])}{L} \right\rfloor\]

Where:

• \(Target[i]\) represents the ideal step function for the observed symbol.
• \(L\) is a dynamic learning factor controlled by the adaptation rate parameter \(N\), where \(L = 4 + (Count \gg 4)\) or fixed scaling steps based on symbol context, typically bounded between \(2^4\) (16) and \(2^5\) (32).

Because integer division with truncation (\(\lfloor \dots \rfloor\)) is used to maintain bit-exact cross-platform decoding, probability updates incur rounding errors. Once the difference \(|Target[i] - CDF_{old}[i]|\) drops below the divisor \(L\), updates freeze, creating a dead-zone where small statistical shifts fail to register in the CDF table.

Alphabet Size and Multi-Symbol Constraints

AV1 processes symbols in alphabets ranging from 2 up to 16 symbols natively. For distributions requiring larger alphabets, compound coding (e.g., prefix codes combined with fixed-precision raw bits) is used.

For native multi-symbol alphabets:

• The 15-bit precision must be distributed across all \(M\) symbols simultaneously.
• As alphabet size \(M\) approaches 16, the effective resolution per symbol degrades relative to a pure binary arithmetic coder, which only splits probability space between two states per decision.
• Correlated contexts must balance adaptation speed against variance: smaller update counts adapt quickly to non-stationary statistics but exhibit high estimation jitter, while saturated counts provide stable probabilities capped by the 15-bit quantization threshold.