What Governs Decode Throughput in Absolute-Offset GPU LZ77? A Work-Granularity Mechanism and an Encode-Time Min-Match-Length Lever Yakiv Shavidze
arXiv:2607.18541v1 [cs.DC] 20 Jul 2026
Independent Researcher ORCID: 0009-0008-3622-3448 https://github.com/yasha1971-coder/aceapex Artifact DOI: https://doi.org/10.5281/zenodo.21316748
Abstract—The ACEAPEX line of work established a lossless LZ77 format whose back-references are absolute output positions, giving parallel, compressed-resident GPU decode with sub-millisecond region seek. What it did not establish is what governs the decode throughput of such a format, or how to improve it. This paper answers both. Through controlled ablations on an NVIDIA H100 we show that decode throughput is governed not by occupancy, compute, address scatter, or launch parallelism, but by work granularity: throughput is a function of the average match length, because a short match leaves most lanes of a cooperating warp idle. A synthetic copy kernel confirms a 3.5× throughput span (212 → 744 GB/s) as average match length grows from 32 to 1024 bytes. Real data sit at the low end (mean match length 6.5 on enwik9, 10.1 on FASTQ). We then show that this mechanism yields a practical, encode-side lever: raising the minimum match length by distance class (6/8/10/12 → 12/16/24/32) improves both compression ratio and decode throughput simultaneously on all eight tested datasets, with no exceptions and no change to the decode kernel. FASTQ decode rises from 142.6 to 178.6 GB/s while ratio improves 1.8%; enwik9 throughput rises 78%. This is not a trade-off: both gains follow from one cause, removing short matches whose far offsets cost more entropy than they save. All figures are bit-perfect (FNV on GPU paths, byte compare on CPU paths) and git-verifiable. Scope is explicit: figures are matchphase, device-resident; entropy and host transfer are outside the timer; seek is read/block-level, not coordinate-level; and we do not claim to exceed the hardware bandwidth ceiling. Index Terms—GPU decompression, LZ77, lossless compression, work granularity, match length, random access
None of these characterizes what determines decode throughput, nor offers a lever to improve it. That is the gap this paper closes. a) Positioning: We state our claim precisely and without overreach. ACEAPEX’s key contribution is not raw decode speed—specialized GPU decompressors and fixed-function hardware can be faster in isolation. Its distinguishing property is the co-existence of three capabilities in one system: compressed-residency, absolute-offset parallel decode, and sub-millisecond region seek. These capabilities exist separately in other systems, but their combination—random access into GPU-resident compressed data without whole-file decompression—is, to our knowledge, unique to the absoluteoffset design. b) Contributions: • Characterization. Decode throughput is governed by work granularity—the average match length—rather than occupancy, compute, bandwidth in isolation, or launch parallelism (Section III). • Lever. An encode-time minimum-match-length threshold (6/8/10/12 → 12/16/24/32 by distance class) improves ratio and throughput together on all tested data (Section IV). • Method. The gain is obtained entirely on the encode side, with no change to the decode kernel, and is bit-perfect throughout.
I. I NTRODUCTION
II. E XPERIMENTAL S ETUP
Prior papers in this series established the ACEAPEX format and its device-resident behaviour. Paper 1 [1] introduced the absolute-offset codec, CPU thread scaling, GPU wavefront decode, and integration into lzbench 2.3. Paper 2 [2] added a full device-resident pipeline with genomic region seek and range decode of a 50 GB genome, reporting up to 260 GB/s in the device-resident regime. Paper 3 [3] proved a single position-invariant seek through both the entropy and match layers, timed at 0.334 ms for one 16 KB block, bit-perfect and isolated.
Hardware is an NVIDIA H100 80 GB HBM3, 132 SMs, CUDA 12.4. The pipeline is tile-ANS: entropy is decoded over 64 KB tiles in cooperative groups of up to 6000; the match kernel is k_decode_g with cooperation width G ∈ {8, 16, 32} (G=32 in all end-to-end runs). Block size is set via the ACEAPEX_BS encode override. Entropy tiles are cut across the flat stream independently of the LZ block size, so the two granularities are decoupled by construction. Timer scope is the match phase, device-resident: host–device transfer and CPU entropy are outside the timer; all runs are warm.
TABLE I T HROUGHPUT IS A FUNCTION OF EFFECTIVE WORKLOAD ( LANES ). VALUES ARE NORMALIZED TO THE SATURATED THROUGHPUT OF THE SAME SWEEP, SO THE COMPARISON IS INDEPENDENT OF THE ABSOLUTE RATE OF ANY ONE CORPUS . Lanes (G × Nblocks ) ≥1 M 131 K 65 K 32 K
TABLE II S YNTHETIC COPY THROUGHPUT VS . AVERAGE MATCH LENGTH , H100. VALUES FROM A REPRESENTATIVE RUN OF THE PUBLISHED P U R E C O P Y . C U ; RUN - TO - RUN VARIATION IS ABOUT 1%. avg len GB/s
Normalized throughput 1.00 (saturated) 0.77 / 0.82 / 0.83 (three configs) 0.52 / 0.53 0.31 (starved)
III. W HAT G OVERNS D ECODE T HROUGHPUT A. Effective workload
lanes = G × Nblocks ,
64 416
128 607
256 692
512 734
1024 744
TABLE III C OMPRESSION RATIO , BASE VS . TUNED THRESHOLD .
Correctness is verified on every data point by FNV hash on GPU paths and byte comparison on CPU paths. Datasets are NA12878 FASTQ (1 GB), enwik9, and the twelve Silesia files.
Sweeping block size and cooperation width jointly over a twelve-point grid (FASTQ 1 GB, all bit-perfect) shows that throughput is a function of effective workload, defined as the number of concurrent lanes
32 212
Dataset
base
tuned
change
FASTQ 1 GB enwik9 256 MB dickens mozilla webster nci xml samba
3.90 2.64 2.58 2.62 3.09 9.92 6.29 3.92
3.97 2.77 2.71 2.68 3.23 10.25 6.70 4.13
+1.8% +4.9% +5.0% +2.3% +4.5% +3.3% +6.5% +5.4%
Not address scatter. Sorted and scattered source addresses give identical throughput. • Not launch parallelism. Two concurrent decode streams sum to about 0.7× the throughput of a single stream— less, not more. •
not of block size or G separately. Configurations with equal lanes reach near-equal throughput (Table I): three What remains is work granularity. A synthetic copy kernel distinct (G, bs) settings at 131 K lanes land within 8% (1 GB, H100) traces throughput directly against average match of one another, while the device starves below ∼32 K length (Table II): a 3.5× span. The reason is structural— lanes and saturates above ∼1 M lanes. Occupancy here a 32-byte match occupies one byte per thread across a 32is obtained analytically from the CUDA occupancy API wide cooperative group, leaving the warp underloaded; longer matches fill it. (cudaOccupancyMaxActiveBlocksPerMultiprocessor), not from profiler counters, which are restricted on the cloud IV. T HE M IN -M ATCH -L ENGTH L EVER host (ERR_NVGPUCTRPERM): k_decode_g⟨32⟩ uses 39 registers, giving maxblk=12 and 132 × 12 = 1584 resident A. Where real data sit blocks. Real corpora sit at the low, steep end of the curve. On B. Two regimes enwik9, 32.5 M matches cover 82.8% of output at mean length On Silesia (block size 64 K, G=32, all bit-perfect) two 6.5, with 99.1% of matches below 32 bytes. On FASTQ, regimes appear. When saturated (lanes > 1 M) throughput matches cover 81.7% of output at mean length 10.1, with is a function of lanes and data type is irrelevant. When 95.7% below 32 bytes. Short matches are what hold throughunder-saturated (Silesia files below 32 MB, lanes 2.5 K–25 K) put down—and, as we show next, they also cost compression. throughput depends on both lanes and data. For example x-ray at 4128 lanes reaches 11.8 GB/s, while samba at 10528 lanes B. Main result reaches only 5.1 GB/s—more lanes, lower throughput—which We raise the minimum match length by distance class. With points past lane count to a per-match property. distance bands d < 128, d < 16384, d < 2097152, and d ≥ 2097152, the minimum length is changed from 6/8/10/12 C. The property is match length to 12/16/24/32. Encode and decode are re-run end-to-end We isolate that property by elimination. Each competing (ACEAPEX_BS=16384, G=32, device-resident, bit-perfect on explanation is tested against a control and rejected: every point). Tables III and IV give the result: ratio and throughput both improve on all eight datasets, without a single • Not compute or parse. A pure-copy kernel fed predecoded triplets reaches essentially the full kernel’s exception. Notably, tuned FASTQ decode (178.6 GB/s) exceeds the throughput (within 4%)—logic is not the bottleneck. ∼142 GB/s plateau of the base configuration—not by breaking • Not occupancy. Forcing more resident blocks with launch_bounds(128,16) (registers 39 → 32, the hardware limit but by shifting the operating point along maxblk 12 → 16) lowers throughput through register the throughput-vs-length curve, removing the short matches that pinned it low. spill, by 9% at 16 K and 14% at 256 K block size.
TABLE IV M ATCH - PHASE DECODE THROUGHPUT (GB/ S ), BASE VS . TUNED . Dataset
base
tuned
change
FASTQ 1 GB enwik9 256 MB dickens mozilla webster nci xml samba
142.6 91.6 17.6 28.9 47.1 47.2 7.6 15.8
178.6 163.5 25.5 29.3 54.8 49.1 9.1 23.9
+25.2% +78% +45% +1.4% +16% +4% +20% +51%
C. Why both improve at once The two gains are two consequences of one cause. A short match to a far, near-random offset spends more bits encoding that offset than it saves in replaced literals; on FASTQ at minimum length 4, offset bytes are 51.6% of the compressed stream. Raising the minimum length removes such matches: offset entropy falls enough to offset the literals that return, so ratio holds or improves, while the mean match length rises, so the decoding warp is better loaded and throughput rises. One cause, two effects—not a trade-off. The optimum on the tested data is 12/16/24/32; pushing to 16/24/32/48 raises throughput but lowers the FASTQ ratio on the full 1 GB set (3.97 → 3.93), so we do not adopt it. V. R ELATED W ORK CODAG [4] increases decode parallelism by assigning compressed chunks to warps rather than thread blocks at runtime, eliminating the leader-thread bottleneck; they characterize speedup over a baseline but do not vary compression granularity. We instead treat block size as an encode-time parameter and characterize the decode-throughput saturation curve; entropy-tile and match-block granularity are moreover decoupled by construction—neither of which CODAG addresses. CODAG targets standard relative-offset formats without random access, whereas ACEAPEX’s absolute-offset format enables position-invariant seek. We note agreement on one point: CODAG reports GPU decode as compute-bound, consistent with our split profile (ANS 9%, match 91%). A conceptually related granularity-saturation trade-off has been observed in other GPU workloads: Optimus [5] shows that in diffusion-LLM decoding, fixed block sizes saturate GPU resources at a load-dependent point, so no single granularity is optimal across regimes. We observe an analogous effect for absolute-offset LZ decode, where throughput saturates as a function of effective workload (lanes = G× block count); unlike Optimus’s runtime granularity control, our lever is an encode-time parameter. The specific effective-workload formulation is ours. For completeness: fixed-function decompression (e.g. Blackwell’s decompression engine, up to 462 GB/s LZ4) is neither absolute-offset nor seekable, and nvCOMP has been proprietary since 2.3. We disambiguate terminology explicitly: throughout, “block size” denotes the LZ compression block set at encode time, not the CUDA thread block.
VI. L IMITATIONS AND H ONEST B OUNDARIES Seek is read/block-level (read id → block), not coordinate (chr:pos) access; coordinate access is future work. • The min-length optimum is data-dependent at the margin (16/24/32/48 costs FASTQ ratio); 12/16/24/32 is the universal win on the tested data. • The plateau we observed on enwik9 (≈217 GB/s, measured with the pure-copy harness driven by the tuned match-length distribution rather than a uniform length) is a real bandwidth limit at that granularity; three independent bypass attempts failed, and we do not claim to exceed hardware. • Nsight counters are restricted on the cloud host; occupancy is computed analytically via the CUDA API, and the mechanism is established by controlled ablation rather than profiler counters. • Encode is slow and data-dependent (0.3–3.4 GB/s); this paper concerns decode, and we make no encodethroughput claim. • The seek combination was “not found in nvCOMP, DietGPU, CODAG, or the Blackwell decompression engine”; we do not claim no system can do it (Gompresso and gpuLZ were not evaluated for seek). •
VII. R EPRODUCIBILITY All figures reproduce from the public repository. research/decode-mechanism/ (commit 640a7e5) contains the pure-copy harness that traces the throughputvs-match-length curve (Table II) and supplies the parse-bound ablation, together with the match-length histogram (Section IV-A) and the per-stream entropy tool (Section IV-C); every figure in those sections was re-derived from these published files on an H100. research/match-threshold/ (commit 701c624) contains the encoder diff and reproduction steps for the lever (Tables III and IV); the throughput column of Table IV, like the grid in Table I, additionally requires the pipeline binary e2e_pipe_tile.cu (commit fb27234), whose build command is in the file header and which requires DietGPU (Meta, MIT-licensed) and glog. Everything is obtainable from https://github.com/yasha1971-coder/aceapex. An archived snapshot of the code at publication time is deposited on Zenodo: https://doi.org/10.5281/zenodo.21316748. FASTQ figures in this version were re-measured on ENA accession ERR194147 (first 1,073,741,620 bytes, 4,010,191 reads, md5 9af9ffaa0e15dba938408a711740e101, 38 quality levels, quality entropy 3.72 bits/symbol); the previously posted FASTQ sample had degenerate quality strings. The lever holds and is stronger on the corrected data. The enwik9 and Silesia figures were always measured on real corpora and are unchanged. VIII. C ONCLUSION Decode throughput in an absolute-offset GPU LZ77 codec is governed by work granularity—the average match length— and this understanding yields a cheap encode-time lever that
improves compression ratio and decode throughput at once, on all tested data, without touching the decode kernel. The natural next step is to carry the mechanism into a full device-resident pipeline and a head-to-head evaluation against production decoders. R EFERENCES [1] Y. Shavidze, “Parallel LZ77 decoding via encode-time absolute offset resolution,” arXiv:2606.04268, 2026. [2] Y. Shavidze, “Compressed-resident genomics: full-pipeline deviceresident GPU LZ77 decode with position-invariant random access,” arXiv:2606.18900, 2026. [3] Y. Shavidze, “Unified position-invariant random access through two compression layers,” arXiv:2606.24531, 2026. [4] Park et al., “CODAG: characterizing and optimizing decompression algorithms for GPUs,” arXiv:2307.03760, 2023. [5] C. Wei, C. Guo, J. Zhang, H. Shan, B. Duan, Y. Zhou, H. Li, Y. Wang, Y. Chen, and D. Zhuo, “Optimus: Elastic Decoding for Efficient Diffusion LLM Serving,” arXiv:2605.24832, 2026.