FMT: Lossless Image Compression in a Fixed Number of Parallel Steps
Ammar Ali
cs.CV
2026-11-18
FMT decodes any photo in a fixed 72 steps via a coarse-to-fine tree and state-carrying rANS lanes; no-network mode beats HTJ2K, large networks run 9-61x faster than learned codecs.
Learned lossless codecs beat PNG and JPEG XL on file size, then lose the deployment on speed: seconds per photo against milliseconds. Anything written once and read many times, a training set or an archive, cares about decode speed as much as size, which is why classical formats still hold that ground.
The diagnosis comes first. Most of a learned codec's decode time is waiting, not computing. Two serial chains cause it: the network waits for the values it conditions on, and the arithmetic decoder reads values one at a time, often on the CPU. FNLIC reports 13 ms of network inference per photo; in the author's runs it took half a second, two fifths of it in the entropy coder. LCFDNet spent a fifth of its second on a CPU coder. More GPU cores do not shorten a chain.
FMT (Fixed-step Multiscale Tree) designs the decoding order and the entropy coder together, so neither chain grows with the image.
The image lives in a coarse-to-fine tree. The root stores one raw pixel every 64 pixels; six levels follow, each treating decoded pixels as square corners, first filling centers, then edge midpoints. Every new pixel is predicted from decoded neighbors and only the residual is stored, split into a short path of decisions: its size in bits, then the remaining bits. The structural guarantee is that pixels within one step never depend on each other; a center sees only coarser levels, an edge adds its own level's centers.
The root's spacing fixes the step count. Any photo decodes in 72 steps (neural modes) or 36 (dense mode); a larger photo just has larger steps. A 768×512 photo takes 1,179,648 steps value by value and 196,608 with JPEG XL's groups; FMT's longest single coder chain is 7,410 values.
Entropy decoding uses interleaved rANS lanes: each step deals its values round-robin to many independent decoders, every lane carries its state across steps, and lane count scales with the image. This is the pivotal trade-off. Fresh lanes per step would need 34 times as many, each storing a final state, for files 13% larger.
Three modes share one tree and one format. Fast stores wavelet residuals at fixed widths, no probabilities at all. Dense drops the network for 256 histograms learned once. Neural modes run small MLPs (16×2 up to 768×4) outputting discretized logistic mixtures, with per-photo tuning (FiLM scales and shifts plus a LoRA-style low-rank update) costing 0.14–1.2% of the file. Probabilities become fixed-point integer tables and kernels fix operation order, so streams decode bit-identically across GPUs. FNLIC's released streams decode wrongly on all 24 Kodak photos on the author's GPU.
Kodak, one photo at a time, one RTX 4090:
| Codec | bpsp | Decode |
| FMT fast | 3.981 | 0.23 ms |
| FMT dense (no network) | 3.187 | 0.45 ms |
| HTJ2K (NVIDIA GPU library) | 3.510 | 0.55 ms |
| FMT 64×2 | 2.818 | 7.5 ms |
| JPEG XL e9 (32-thread CPU) | 2.885 | 10.7 ms |
| FMT 512×4 | 2.589 | 53.5 ms |
| DLPR (learned, author's run) | 2.857 | 5373 ms |
| CALLIC (learned, published) | 2.54 | 1.7 s |
Dense, with no network, makes files 8–10% smaller than HTJ2K from NVIDIA's GPU library and decodes 1.2–1.6× faster. The 64×2 beats JPEG XL at effort 9 by 2.3–3.8% in size and 1.4–1.6× in speed, one GPU against a fully used 32-thread CPU. Against learned codecs, the 512×4 hits 2.589 bpsp in 53.5 ms: by published times it is 7.5× faster than HPAC-Fast, 27× faster than DLPR, 61× faster than ArIB-BPS, at equal or smaller size; it is 1.7–2.7% larger than HPAC-FT and CALLIC, which need 17–32× the time. Same-machine A100 runs against FNLIC, LC-FDNet and ArIB-BPS give 8.8–61×. At full load the fast mode pushes 8.8–11.8 gigapixels per second, more than any codec tested; only formats with 28% larger files, such as TIFF-LZW, decode faster. An ablation swapping in a wavefront order (steps grow with the image) saves 0.3–2.4% in size for 8–78× the steps: a 4K frame takes roughly 24,000 steps against the tree's 72.
The paper turns learned-compression slowness into an engineering problem with a named culprit, serial dependency rather than compute, and that diagnosis travels to other neural compression work. Training-data pipelines can use the fast and dense modes for throughput and size at once; mid-size networks approach learned ratios without second-long decodes; one format slides along the whole size-speed frontier. Bit-exact portability across GPUs is an underappreciated deployment issue that integer probability tables solve outright, while exposing FNLIC's streams as non-portable.
The boundary is real: per-image-adapted CALLIC and HPAC-FT stay 1.8–3.4% smaller on the full validation sets, and an LLM-based predictor 5.5–10%, at 140–500 s per image. FMT wins the segment where size and speed hold simultaneously, not maximum ratio.
Stated by the author: 8-bit photographs only, 10–16 bit film masters and medical scans need retraining; per-photo tuning costs seconds on the encoder (3.5–8.9 s per Kodak photo for the 512×4 on an A100); the decoder caches per-size tables at 276–403 bytes per pixel, up to 9.6 GB for a 33-megapixel image; small images lose, a 64×64 thumbnail still walks all 72 steps in 3.2 ms against roughly 0.5 ms for CPU codecs; the 128×2 and larger networks have no CPU decoder, and portable kernels cost 3.0–4.4× in fp32; streams need checksums, since one error propagates to finer levels.
Open questions from this reading: the JPEG XL comparison pits a GPU against a loaded CPU, a stated but real mismatch the reader has to convert; some learned baselines come from published times on different machines, though the A100 same-machine runs cover the important ones; code is listed as forthcoming, so nothing is independently reproducible yet. It is a single-author paper carrying an unusually large experimental load, most of it in the supplement, and its weight depends on whether third parties can reproduce the numbers.