H-DDCM: Hadamard Codebooks for Fast Generative Image and Video Compression

AI summary

Overview

Research area: Generative (diffusion/flow-based) image and video compression — specifically training-free codecs that reuse a frozen pretrained generator as a decoder.

Technical level: Advanced. The paper assumes familiarity with diffusion sampling, sparse coding, and combinatorial bitstream coding, though its core idea (swap a huge random dictionary for a fast structured one) is conceptually simple.

Scope: The paper introduces H-DDCM, a training-free generative compression framework that replaces dense Gaussian codebooks with implicit randomized Hadamard dictionaries and adds a table-free combinatorial bitstream coder, then extends the framework to streaming autoregressive video compression.

What This Paper Is About

Training-free diffusion codecs such as Turbo-DDCM compress data by selecting, at each denoising step, a combination of atoms from a shared Gaussian codebook that best matches the residual between the target and the model's current prediction. This works well perceptually at ultra-low bitrates, but the codebook must be stored or regenerated, and its cost grows with both the latent dimension and the codebook size. The paper's goal is to keep the quality of a complete codebook while removing its memory, compute, and bitstream bottlenecks, so the approach scales to large image latents (FLUX) and fast autoregressive video models.

Key Contributions

1. Implicit randomized Hadamard dictionary. Dense Gaussian codebooks are replaced by dictionaries of the form D_t H, where H is the normalized Hadamard matrix and D_t is a Rademacher diagonal drawn from a shared seed at every step. The fast Walsh–Hadamard transform (FWHT) gives projection and reconstruction in O(d log d) compute and O(d) memory for a full-dimension dictionary (K = d) that is never materialized. Because the basis is exactly orthonormal, Turbo-DDCM's top-M thresholding rule becomes the exact solution of the sparse least-squares problem rather than an approximation.

2. Table-free, group-factorized lexicographic bitstream coding. Turbo-DDCM encodes the M selected indices as an unordered subset via a lexicographic rank but relies on a dense precomputed binomial table. The authors introduce (i) an incremental Pascal-rule recurrence and (ii) a hockey-stick-identity formulation with binary-search unranking, plus a grouping protocol that splits K atoms into G groups, sends a stars-and-bars count vector, then encodes each group locally. This preserves the bit savings while keeping combinatorial operations tractable at large dimensions.

3. Overcomplete Hadamard dictionary. For the low-bitrate regime (small M), B independent randomized Hadamard bases are concatenated into a d × Bd dictionary, exposing Bd candidate directions at the cost of one FWHT per basis. Top-M selection across all bases is used as in Turbo-DDCM, and the pseudo-inverse of the selected sub-matrix is available, though the analysis coefficients are found to give an almost identical noise direction.

4. Streaming video extension with re-encoded-tail KV-cache refresh. The framework is adapted to the Causal-Forcing (CF) autoregressive video flow model, with a scheme that periodically re-encodes recently reconstructed frames into a fresh KV-cache prefix so that compression can extend beyond the model's native context without extra transmitted bits.

Main Findings

• Matching a complete codebook at FLUX scale: At latent dimension d = 2^18, H-DDCM closely matches complete-codebook Turbo-DDCM (K = d) and DiffC in PSNR and FID across the evaluated bitrate regime, without materializing the corresponding codebook. Capping Turbo-DDCM's codebook below d reduces quality, while using the complete codebook substantially increases memory and runtime.

• Speed on images: At matched bitrate on SD 2.1, H-DDCM and Turbo-DDCM (K = d) both achieve a 1.3 s round-trip time, versus 5.5 s for DiffC and 61 s for DDCM. On FLUX, H-DDCM reduces round-trip time from 66 s for Turbo-DDCM (K = d) to 44 s. The paper states H-DDCM is the fastest training-free method in its comparisons.

• The memory bottleneck it removes: A complete Gaussian codebook requires approximately 128 GiB of storage for large image latents such as FLUX, and roughly 167 GiB for video latents such as those used by Causal-Forcing. The Hadamard construction needs O(d) memory and is regenerated from a seed.

• Video throughput: Among training-free methods sharing the CF backbone, H-DDCM achieves the highest measured encoding and decoding throughput while giving competitive rate-distortion-perception performance. HEVC, VVC, and DCVC-UF achieve higher PSNR but substantially weaker perceptual quality as measured by DOVER and FVMD. ZeroGVC achieves comparable PSNR but weaker temporal/motion consistency (FVMD) and lower throughput, and the paper reports temporal discontinuities at ZeroGVC's I-frame boundaries visible in space-time slices. Both Turbo-DDCM variants show lower PSNR and perceptual quality, with the complete-codebook variant incurring substantially lower throughput.

• Where the exactness claim comes from: For a single Hadamard basis, the objective decouples coordinate-wise because A_t is orthonormal, so thresholding the correlations u_t = A_t^T r_t is the exact minimizer of the sparse problem. For the overcomplete B-basis dictionary, atoms from different bases are not mutually orthogonal, so global top-M is again a heuristic, as in Turbo-DDCM.

• Not reported in the text: The paper's numeric PSNR, FID, DOVER, FVMD, BPP and memory values are presented graphically in Figures 1–4 rather than tabulated in the main text; the truncated content does not enumerate them.

Methodology in Plain English

The starting point is the observation that a training-free diffusion codec only ever uses its codebook in two ways: to compute how well each candidate atom matches the current residual, and to rebuild the chosen combination. Both are just matrix-vector products. So instead of storing a giant matrix of random Gaussian vectors, the authors use a structured matrix that has the same useful property — orthonormal columns — but can be applied on the fly.

That matrix is a Hadamard matrix, whose columns form an orthonormal basis and which can be multiplied by a vector in O(d log d) time with a fast transform, using only O(d) memory. To prevent the fixed Hadamard structure from aligning badly with image content, they multiply by a random ±1 diagonal at each denoising step. Encoder and decoder generate the same random diagonal from a shared seed, so nothing about the dictionary needs to be stored or transmitted. At each step the encoder takes the fast transform of the residual, keeps the M largest-magnitude coefficients, quantizes them, and sends only their positions and values; the decoder reconstructs the same noise map and follows the same trajectory.

For the bitstream, the M chosen positions form an unordered set, so sending their combinatorial rank is cheaper than sending them individually — but the standard implementation needs a huge lookup table of binomial coefficients. The authors replace it with formulas computed on demand, and split the dictionary into G groups so that each combinatorial computation stays small.

For video, they take a causal autoregressive flow model that generates frames chunk by chunk from a KV cache and treat it as a codec. Because the model was trained on a limited context (21 latent frames, i.e. 81 pixel frames, i.e. 7 chunks of 3 latent frames), they periodically re-encode the last 9 reconstructed pixel frames into a fresh cache prefix. Since both sides have those reconstructions already, the refresh costs no extra bits and preserves temporal continuity across segment boundaries.

Why This Matters

For research, the paper shows that the memory and compute cost of codebook-based generative compression is an artifact of using unstructured random dictionaries, not a fundamental requirement. It connects the compression problem to classical structured-sensing ideas (randomized Hadamard transforms, incoherence) and demonstrates that a training-free codec can operate at modern latent scales, which prior dense-codebook methods could not afford.

Real-world applications:

• Ultra-low-bitrate image delivery, where perceptual plausibility matters more than pixel fidelity, such as bandwidth-constrained streaming or archival thumbnails.
• Long-form video transmission over constrained channels, where the streaming formulation targets close to real-time operation on a single GPU.
• Compression tied to existing generative backbones, useful when an organization already serves a particular diffusion or flow model and does not want to train a codec per backbone.
• On-device or edge deployment, since avoiding codebook materialization removes tens to hundreds of gigabytes of memory overhead.

Industry relevance: the results (44 s versus 66 s round trip on FLUX, 1.3 s versus 61 s on SD 2.1, highest measured throughput among CF-based methods on video) target the practical throughput and memory budgets that deployment demands, and the training-free property means a codec can follow backbone upgrades without retraining.

Future Directions

• Recovering exactness for the overcomplete dictionary. With B independent Hadamard bases, cross-basis atoms are not orthogonal, so global top-M is again a heuristic. The paper notes the pseudo-inverse of the selected sub-matrix is available but that analysis coefficients are empirically near-identical; a principled selection rule for the overcomplete case remains open.
• Extending beyond the tested backbones and resolutions. Evaluation covers SD 2.1 at 512×512, FLUX at 1024×1024, and CF at 832×480; whether the structured dictionary and grouped bitstream scale to higher resolutions, longer contexts, or other generators is untested here.
• Refining the cache-refresh policy. The scheme uses a fixed refresh of the last 9 reconstructed pixel frames and a larger selection budget M_start at the first chunk after a refresh; adaptive choices of refresh length and budget are natural follow-ups.
• Tighter bitstream overheads. The grouping protocol trades a stars-and-bars count vector (log2 of a binomial term) for parallelizable, bounded-size operations; closing that small rate gap, or adapting G per step, is an open engineering question.

Target Audience

Researchers and engineers working on neural image and video compression, generative-model-based codecs, or diffusion/flow sampling who want to understand how to make training-free generative compression practical at modern latent dimensions. It is also relevant to practitioners in video streaming and codec deployment who care about memory footprint and throughput, and to readers interested in structured random matrices and combinatorial bitstream design. Readers without background in diffusion sampling or sparse coding will find the method sections demanding.

Authors’ abstract

Training-free diffusion-based compression methods repurpose the generative priors of a diffusion or a flow model to compress data without retraining them as task-specific codecs. Recent codebook-based approaches such as Turbo-DDCM achieve strong perceptual quality at ultra-low bitrates, but their reliance on dense Gaussian codebooks remains costly in both memory and computation, and scales poorly with the large latent dimensions of modern image and video generators. Their combinatorial bitstream encoding further becomes computationally heavy at this scale. We introduce H-DDCM, a scalable generative compression framework that replaces Gaussian codebooks with implicit randomized Hadamard dictionaries. The fast Walsh-Hadamard transform allows for implicitly synthesizing full-dimensional dictionaries with $O(d \log d)$ compute for projection and reconstruction and $O(d)$ memory, without materializing the full-dimensional dictionary. We further introduce an efficient table-free lexicographic coding scheme that makes combinatorial encoding practical at larger dimensions. Beyond images, we adapt the framework to an autoregressive video flow model and develop a streaming compression scheme that periodically re-encodes recently reconstructed frames into a fresh KV-cache prefix, preserving temporal context across segments at no additional transmitted bits. This enables long-form, close to real-time generative video compression on a single GPU. Across image and video benchmarks, H-DDCM achieves competitive rate-distortion-perception performance while substantially reducing the memory and computational overhead of codebook-based training-free generative compression.