FMT: Lossless Image Compression in a Fixed Number of Parallel Steps
Organizations: LEAD Lab, ITMO University
Abstract
Learned lossless codecs make smaller files than common classical codecs, yet the images we archive and train on still use classical codecs. A main reason is time: a learned codec takes seconds to decode a photo that a classical codec opens in milliseconds, and their faster variants give up most of their gain in size. We argue that much of this time is spent waiting, not computing: the network waits for the values it conditions on, and the arithmetic decoder reads them one at a time. We introduce FMT (Fixed-step Multiscale Tree), a lossless image format whose decoding order and entropy coder are designed together so that neither wait grows with the image. FMT stores an image as a coarse-to-fine tree whose steps hold independent values: a GPU predicts each step at once and decodes it in parallel rANS lanes that carry their states from step to step, so an image of any size decodes in a fixed number of sequential steps. On this tree we build a family of bit-exact codecs, from a rule with no network to large networks, and no codec we ran on the same GPU beats any of them on both size and speed. Without a network, FMT beats NVIDIA's HTJ2K on size and speed; with a large one, it decodes Kodak photos 9 to 61X faster than learned codecs we ran on the same A100, at the same size or smaller.
Figures & tables
| Decoding order | Steps | Coder chain | A value sees |
|---|---|---|---|
| Value by value [ 56 ] | 1,179,648 | 1,179,648 | above and left |
| JPEG XL groups [ 48 ] | 196,608 | 196,608 | its block |
| HTJ2K blocks [ 51 ] | 5 | 4,096 | its block |
| Interpolation [ 22 ] | about 15 | 1,179,648 | all sides |
| Patch groups [ 28 ] | 94 | – | earlier groups |
| FMT tree | 36 or 72 | 7,410 | all sides |
| Dense | Neural | Fast | |
|---|---|---|---|
| Tree | pixels, 36 steps | pixels, 72 steps | 5/3 wavelet |
| Colours | ranked first | best of top 4 | YCoCg-R |
| Prediction | mean of 4 | mean of 4 | lifting |
| Probabilities | 256 histograms | 5 logistics | none |
| Model input | 2 context values | 24–48 neighbours | — |
| Networks | — | 16 2 to 768 4 | — |
| Kodak | CLIC.p / 4 | DIV2K / 4 | ||||
| Codec | bpsp | ms | bpsp | ms | bpsp | ms |
| FMT on one RTX 4090 | ||||||
| fast ⋆ | 3.981 | 0.23 | 3.870 | 0.71 | 4.145 | 0.87 |
| dense ⋆ | 3.187 | 0.45 | 2.671 | 0.83 | 3.071 | 1.02 |
| 16 2 ⋆ | 2.960 | 4.5 | 2.447 | 7.9 | 2.782 | 8.9 |
| 32 2 ⋆ | 2.902 | 4.9 | 2.408 | 8.9 | 2.731 | 10.0 |
| Learned codec | bpsp | time | FMT | size | faster |
|---|---|---|---|---|---|
| One model for all images | |||||
| HPAC-Fast | 2.95 | 0.40 s | 512 4 ∘ | 5.9% | 7.5 |
| HPAC | 2.73 | 0.90 s | 512 4 ∘ | 1.7% | 17 |
| DLPR | 2.86 | 1.42 s | 512 4 ∘ | 3.0% | 27 |
| LC-FDNet ‡ | 2.94 | 1.00 s | 512 4 ∘ | 5.6% | 17 |
| ArIB-BPS ‡ | 2.78 | 3.6 s | 512 4 ∘ | 0.2% | 61 |
| Measured by us | Published [ 28 , 27 , 10 ] | ||||
|---|---|---|---|---|---|
| CLIC.p | DIV2K | CLIC.p | DIV2K | ||
| FMT 16 2 | 2.602 | 2.775 | ArIB-BPS | 2.42 | 2.55 |
| FMT 64 2 | 2.506 | 2.673 | DLPR | 2.38 | 2.55 |
| FMT 128 2 | 2.480 | 2.644 | HPAC | 2.38 | 2.52 |
| FMT 512 4 | 2.386 | 2.551 | HPAC-FT ∗ | 2.34 | 2.47 |
| FMT 768 4 | 2.382 | 2.546 | CALLIC ∗ | 2.30 | 2.46 |
| One RTX 4090 | i9-14900K, 32 threads | ||||||
|---|---|---|---|---|---|---|---|
| Kodak | CLIC.p | DIV2K | Kodak | CLIC.p | DIV2K | ||
| FMT fast | 8811 | 11792 | 9116 | QOI | 3077 | 3195 | 3512 |
| FMT dense | 6716 | 7886 | 8019 | WebP | 1664 | 1771 | 1690 |
| HTJ2K | 4533 | 7097 | 7013 | PNG | 1572 | 1813 | 1596 |
| nvTIFF | 4558 | 6105 | 5587 | JXL e1 | 886 | 977 | 977 |
| nvCOMP | 2205 | 3364 | 3139 | FMT fast | 838 | 748 | 762 |
| 16 2 | 64 2 | 512 4 | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| per lane | bpsp | dec. | ent. | bpsp | dec. | ent. | bpsp | dec. | ent. | ||
| 512 | 72 | 512 | 2.997 | 5.4 | 4.0 | 2.855 | 11.5 | 4.2 | 2.634 | 80.3 | 4.9 |
| 2,048 | 18 | 2,048 | 2.961 | 6.5 | 5.1 | 2.819 | 12.6 | 5.4 | 2.597 | 81.3 | 5.8 |
| 8,192 | 5 | 7,371 | 2.952 | 10.1 | 8.7 | 2.810 | 16.1 | 8.8 | 2.588 | 84.7 | 9.3 |
| 32,768 | 2 | 18,428 | 2.950 | 17.6 | 16.2 | 2.808 | 23.3 | 16.0 | 2.586 | 91.7 | 16.5 |
| 262,144 | 1 | 36,855 | 2.949 | 29.6 | 28.3 | 2.807 | 35.0 | 27.8 | 2.585 | 102.9 | 28.0 |
| ideal, bits per subpixel | file, | GPU part, ms | ||||
| order | steps | generic | tuned | bits per subpixel | codec | graph |
| Final networks: 60,000 + 120,000 training steps (our 16 2: the first 60,000 on the RTX 3090, the rest on the RTX 4090 server) | ||||||
| tree (ours) | 72 | 3.084 | 2.949 | 2.960 | 6.5 | 5.2 |
| 2:1 wavefront | 5,367–6,135 | 3.007 ( 2.5%) | 2.900 ( 1.7%) | 2.913 ( 1.6%) | 258.4 | 235.2 |
| raster | 1,179,360 | 3.015 ( 2.2%) | 2.929 ( 0.7%) | – | – | – |
| First training cycle: 60,000 steps, all three trained on the RTX 3090 | ||||||
| levels | steps | root | generic | tuned | |
|---|---|---|---|---|---|
| 32 | 5 | 60 | 1/1,024 | 3.092 ( 0.2%) | 2.968 ( 0.5%) |
| 64 | 6 | 72 | 1/4,096 | 3.086 | 2.954 |
| 128 | 7 | 84 | 1/16,384 | 3.087 ( 0.0%) | 2.949 ( 0.2%) |
| Encoder | 16 2 | 64 2 | 512 4 | |||
|---|---|---|---|---|---|---|
| bpsp | bpsp | bpsp | ||||
| first-ranked transform | 3.096 | 2.970 | 2.783 | |||
| + best of top four | 3.088 | % | 2.967 | % | 2.777 | % |
| + best of 8 orientations | 3.075 | % | 2.960 | % | 2.774 | % |
| + per-photo tuning | 2.961 | % | 2.819 | % | 2.588 | % |
| Kodak | CLIC.p / 4 | DIV2K / 4 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Network | untuned | tuned | gain | untuned | tuned | gain | untuned | tuned | gain |
| 16 2 | 3.075 | 2.960 | 3.7% | 2.492 | 2.447 | 1.8% | 2.828 | 2.782 | 1.6% |
| 32 2 | 3.031 | 2.902 | 4.3% | 2.446 | 2.408 | 1.6% | 2.773 | 2.731 | 1.5% |
| 64 2 | 2.960 | 2.818 | 4.8% | 2.397 | 2.364 | 1.4% | 2.717 | 2.679 | 1.4% |
| 128 2 | 2.927 | 2.779 | 5.1% | – | – | – | – | – | – |
| 512 4 | 2.774 | 2.589 | 6.7% | 2.263 | 2.239 | 1.1% | 2.576 | 2.545 | 1.2% |
| Kodak, untuned | Kodak, tuned | 2K photos, tuned | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| GPU | Network | paper | same | paper | same | fast | pool | paper | same | fast | pool |
| RTX 3090 | 16 2 | 1.3 | 0.06 | 4.7 | 3.7 | 2.3 ( 0.02%) | 0.85 ( 0.03%) | 30.2 | 10.7 | 3.2 (0%) | 2.0 ( 0.01%) |
| 64 2 | 1.4 | 0.04 | 5.2 | 4.1 | 2.9 ( 0.05%) | 1.1 ( 0.16%) | 31.0 | 11.4 | 4.1 (0%) | 2.6 ( 0.03%) | |
| 512 4 | – | – | – | – | – | 5.0 ( 0.14%) | – | – | – | 13.9 ( 0.05%) | |
| A100 | 16 2 | – | – | – | – | 2.1 ( 0.01%) | 1.1 ( 0.01%) | 33.5 | – | 2.6 (0%) | 2.6 ( 0.03%) |
| 64 2 | – | – | – | – | 2.2 ( 0.01%) | 1.0 ( 0.12%) | 33.8 | – | 3.3 (0%) | 2.7 ( 0.03%) | |
| Set | Network | rank | tables | top 4 | orient. | tuning | quant. | coding | total |
|---|---|---|---|---|---|---|---|---|---|
| CLIC.p | 16 2 | 10.6 | 8.0 | 1.4 | 2.3 | 2.5 | 3.9 | 0.3 | 29.0 |
| 64 2 | 10.5 | 8.1 | 1.3 | 2.3 | 2.7 | 4.0 | 0.3 | 29.1 | |
| 512 4 | 10.6 | 8.0 | 2.5 | 4.4 | 12.0 | 5.8 | 0.8 | 44.0 | |
| DIV2K | 16 2 | 11.1 | 8.7 | 1.5 | 2.3 | 2.6 | 4.1 | 0.4 | 30.6 |
| 64 2 | 11.1 | 8.6 | 1.3 | 2.4 | 2.7 | 4.2 | 0.3 | 30.6 | |
| 512 4 | 11.1 | 8.6 | 2.6 | 4.6 | 12.0 | 6.1 | 0.8 | 45.9 |
| 64 2 | 128 2 | 256 2 | ||||
| Codec | bpsp | ms | bpsp | ms | bpsp | ms |
| FMT, untuned, on the RTX 3090 | ||||||
| 16 2 | 3.480 | 3.2 | 3.368 | 4.1 | 3.294 | 5.5 |
| 64 2 | 3.350 | 5.7 | 3.241 | 6.8 | 3.166 | 8.1 |
| 512 4 | 3.160 | 23.9 | 3.063 | 24.8 | 2.981 | 28.6 |
| One thread of the i9-14900K | ||||||
| Network | crop | untuned | tuned | kept | update |
|---|---|---|---|---|---|
| 16 2 | 64 2 | 3.452 | 3.395 ( 1.6%) | 89% | 1.7% |
| 128 2 | 3.351 | 3.257 ( 2.8%) | 99% | 1.2% | |
| 256 2 | 3.276 | 3.164 ( 3.4%) | 100% | 0.7% | |
| 64 2 | 64 2 | 3.330 | 3.297 ( 1.0%) | 72% | 2.1% |
| 128 2 | 3.230 | 3.149 ( 2.5%) | 100% | 1.7% | |
| 256 2 | 3.155 | 3.036 ( 3.8%) | 100% | 1.1% |
| Tuning | 16 2 | 64 2 | 512 4 | |||
|---|---|---|---|---|---|---|
| bpsp | s | bpsp | s | bpsp | s | |
| 200 iterations | 2.961 | 4.5 | 2.819 | 5.1 | 2.588 | 14.9 |
| 25 iterations | 2.995 | 2.6 | 2.868 | 2.7 | 2.676 | 4.4 |
| A100, ms | same streams | |||||
|---|---|---|---|---|---|---|
| Network | size | std. | port. | ratio | std. | port. |
| 16 2 | 0.0001% | 7.1 | 7.4 | 1.04 | 24/24 | 24/24 |
| 32 2 | 0.0001% | 8.0 | 8.2 | 1.03 | 24/24 | 24/24 |
| 64 2 | 0.0001% | 12.1 | 12.7 | 1.05 | 24/24 | 24/24 |
| 128 2 | 0.0045% | 28.1 | 26.4 | 0.94 | 0/24 | 24/24 |
| 512 4 | 0.0017% | 55.1 | 167 | 3.03 | 0/24 | 24/24 |
| A100 | RTX 3090 | ||||||
| Network | kernels | size | ms | ratio | ms | ratio | same |
| 512 4 | standard | – | 81.0 | 1.00 | 84.6 | 1.00 | 0/24 |
| fp32 | 0.002% | 168 | 2.07 | 143 | 1.68 | 24/24 | |
| int8 | 0.25% | 89.0 | 1.10 | 85.3 | 1.01 | 24/24 | |
| int8, asym. | 0.16% | 91.2 | 1.12 | 87.3 | 1.03 | 24/24 | |
| 768 4 | standard | – | 85.9 | 1.00 | 130 | 1.00 | 0/24 |
| Mode | bpsp | exact | ms |
|---|---|---|---|
| fast | 3.981 | yes | 0.19 |
| dense | 3.187 | yes | 0.54 |
| 16 2 | 2.960 | yes | 6.33 |
| 32 2 | 2.902 | yes | 7.15 |
| 64 2 | 2.818 | yes | 12.5 |
| 128 2 | 2.779 | no | – |
| Results | Machine | Software | Clock | Statistic |
|---|---|---|---|---|
| Main paper: Fig. 4 and Tab. 3, one image at a time | RTX 4090; host AMD EPYC 7702 | CUDA 12.8, PyTorch 2.8 | from the compressed bytes in host memory to the RGB image in GPU memory: parsing, merge of the update and inverse colour transform inside; index tables of the image size built once, outside | minimum of 7 rounds after a warm-up, mean over the images |
| CPU codecs (main paper and Sec. S8 ) | Core i9-14900K, 32 threads, WSL2 | imagecodecs 2026.3.6 (libjxl 0.11.2, libwebp 1.6.0, …) | from the compressed bytes to the image, both in host memory | as above, at each codec’s best number of threads |
| Throughput (main paper, Tab. 6; Sec. S9 ) | as above | as above | many images at once, batches on several host threads | best number of threads and batch size; megapixels per second |
| Published times (main paper, Tab. 4 and Fig. 4) | RTX 4090D (HPAC’s measurements); CALLIC : not stated | — | as stated by the authors | as published |
| A100 runs (main paper, Tab. 4 ‡ ; Tabs. S17 and S11 ) | A100-SXM4-40GB in a shared server | CUDA 12.6, PyTorch 2.7.1; rivals in their own environments | ours as in the first row; rivals from a bitstream in memory or on a RAM disk to the decoded image | ours: minimum of 7 rounds ( Tabs. S11 and S12 : best of 3); rivals: minimum of 3 after a checked decode (ArIB-BPS: one round, CUDA events) |
| RTX 3090 runs ( Secs. S3 , S4 , S5 and S7 ) | RTX 3090; host Core i9-14900K, WSL2 | CUDA 13.0, PyTorch 2.11 | as in the first row, but the lane runs time the decoder’s GPU part, from the parsed stream to the image; encoders: from the image in host memory to the stream in host memory | minimum of the stated rounds; a GPU temperature guard (pause above 73 ∘ C) is logged, and no timing that it paused is used (except the 33-MP 512 4 decodes of Tab. S18 , an upper bound) |
| CLIC.p (41) | DIV2K (100) | |||||
|---|---|---|---|---|---|---|
| Codec | all bits | per photo | published | all bits | per photo | published |
| FMT 16 2 | 2.602 | 2.671 | 2.775 | 2.783 | ||
| FMT 64 2 | 2.506 | 2.572 | 2.673 | 2.680 | ||
| FMT 128 2 | 2.480 | 2.545 | 2.644 | 2.651 | ||
| FMT 512 4 | 2.386 | 2.447 | 2.551 | 2.558 | ||
| FMT 768 4 | 2.382 | 2.442 | 2.546 | 2.553 | ||
| Set | FMT | against | size | 95% interval | smaller |
|---|---|---|---|---|---|
| Kodak | 16 2 | JPEG XL e9 | 2.6% | [ 1.6, 3.7]% | 3/24 |
| 64 2 | JPEG XL e9 | 2.3% | [ 3.1, 1.5]% | 20/24 | |
| 64 2 | JPEG XL e10 | 1.7% | [ 2.5, 0.8]% | 18/24 | |
| 64 2 | FNLIC | 2.2% | [ 3.2, 1.1]% | 20/24 | |
| 64 2 | LC-FDNet | 4.1% | [ 4.5, 3.7]% | 24/24 | |
| 64 2 ∘ | LC-FDNet | 0.8% | [ 0.3, 1.2]% | 7/24 |
| Kodak | DIV2K / 4 | |||
| Codec | bpsp | ms | bpsp | ms |
| FMT fast | 3.981 | 0.22 | 4.145 | 0.93 |
| FMT dense | 3.187 | 0.70 | 3.072 | 1.4 |
| FMT 16 2 | 2.960 | 7.6 | 2.782 | 14.8 |
| FMT 32 2 | 2.903 | 8.4 | 2.731 | 19.8 |
| FMT 64 2 | 2.818 | 12.6 | 2.678 | 37.5 |
| Network | pixels | MP | tables | total | B/px | first | later | MP/s |
|---|---|---|---|---|---|---|---|---|
| 16 2 | 3840 2160 | 8.3 | 1.8 | 2.1 | 276 | 42 | 33 | 248 |
| 5760 3240 | 18.7 | 4.0 | 4.8 | 276 | 130 | 76 | 246 | |
| 7680 4320 | 33.2 | 7.0 | 8.5 | 276 | 257 | 133 | 249 | |
| 64 2 | 3840 2160 | 8.3 | 1.8 | 2.1 | 276 | 109 | 100 | 83 |
| 5760 3240 | 18.7 | 4.0 | 4.8 | 276 | 337 | 221 | 85 | |
| 7680 4320 | 33.2 | 7.0 | 8.5 | 276 | 416 | 386 | 86 |
| tables | 16 2 | 64 2 | 512 4 | |||||
| Size | host | GPU | first | later | first | later | first | later |
| 64 64 | 0.78 | 0.35 | ||||||
| 256 256 | 2.3 | 0.43 | ||||||
| 768 512 | 26.3 | 3.4 | 7.2 | 6.1 | 13.3 | 12.5 | 85.5 | 84.8 |
| 2040 1356 | 123 | 7.2 | 19.6 | 13.9 | 45.7 | 39.9 | 500 | 494 |
| 3840 2160 | 370 | 17.1 | ||||||
| ms per photo, tables of | ||||
|---|---|---|---|---|
| Codec | bpsp | all sizes | 16 sizes | none |
| FMT dense, graph | 3.607 | 1.42 | 1.48 | – |
| FMT dense, eager | – | 0.94 | 0.80 | |
| FMT 16 2 | 3.458 | 6.21 | 7.20 | 7.69 |
| FMT 64 2 | 3.311 | 11.0 | 12.4 | 12.7 |
| JPEG XL e9 | 3.274 | |||
| Set | Codec | bpsp | ms | GPU | share | traced |
|---|---|---|---|---|---|---|
| Kodak | HTJ2K | 3.510 | 0.73 | 0.60 | 82% | 1.73 |
| dense, =512 | 3.187 | 0.54 | 0.43 | 79% | 0.59 | |
| dense, =2,048 | 3.150 | 1.17 | 1.05 | 90% | 1.23 | |
| CLIC.p/4 | HTJ2K | 2.960 | 1.35 | 0.99 | 73% | 2.13 |
| dense, =512 | 2.671 | 1.18 | 0.95 | 81% | 1.22 | |
| dense, =2,048 | 2.635 | 1.62 | 1.37 | 85% | 1.64 |
| Kodak | CLIC.p / 4 | DIV2K / 4 | |||||
| Codec | on | bpsp | ms | bpsp | ms | bpsp | ms |
| FMT fast | GPU | 3.981 | 0.23 / 0.25 | 3.870 | 0.71 / 0.74 | 4.145 | 0.87 / 0.93 |
| FMT dense | GPU | 3.187 | 0.45 / 0.46 | 2.671 | 0.83 / 0.84 | 3.071 | 1.02 / 1.06 |
| FMT 16 2 | GPU | 2.960 | 4.54 / 4.59 | 2.447 | 7.91 / 8.06 | 2.782 | 8.92 / 9.69 |
| FMT 32 2 | GPU | 2.902 | 4.92 / 4.94 | 2.408 | 8.91 / 8.94 | 2.731 | 10.0 / 10.9 |
| FMT 64 2 | GPU | 2.818 | 7.49 / 7.51 | 2.364 | 16.9 / 17.0 | 2.679 | 19.1 / 20.0 |
| Set | nvCOMP variant | bpsp | MP/s |
|---|---|---|---|
| Kodak | Deflate, Sub, 64k | 4.535 | 998 |
| GDeflate, Sub, 64k | 4.559 | 1485 | |
| GDeflate, Sub, 16k | 4.791 | 1952 | |
| ANS, Sub, 64k | 5.459 | 2026 | |
| GDeflate, raw, 16k | 5.596 | 2042 | |
| Bitcomp, raw, 64k | 6.904 | 2205 |
| Codec | device | Kodak | CLIC.p / 4 | DIV2K / 4 |
|---|---|---|---|---|
| FMT fast | GPU | 8811 | 11792 | 9116 |
| FMT dense ( ) | GPU | 6716 | 7886 | 8019 |
| HTJ2K (nvJPEG2000) | GPU | 4533 | 7097 | 7013 |
| TIFF-LZW (nvTIFF) | GPU | 4558 | 6105 | 5587 |
| nvCOMP, fastest | GPU | 2205 | 3364 | 3139 |
| JPEG 2000 (nvJPEG2000) | GPU | 410 | 1122 | 1056 |
Learned Image Compression
Learned image compression uses neural encoders, quantization, and entropy models to reduce image bitrates while balancing fidelity, perceptual quality, and task utility.
See all 135 papers