The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats Yakiv Shavidze
arXiv:2609.16731v1 [cs.DC] 15 Sep 2026
Independent Researcher ORCID: 0009-0008-3622-3448 https://github.com/yasha1971-coder/aceapex Abstract—Random access into compressed data is normally bought with density. We measure the exchange rate. Across four formats and nine axes on a common corpus, the cost of cutting a 254 MB archive into independently addressable 16 KiB units is 1.632% of the archive for an absolute-offset format against 6.57% for seekable zstd, and the gap widens as the unit shrinks: at 4 KiB, 5.33% against 10.06%. Because the cost is small, several properties follow that are usually unavailable: splitting an archive is free and occasionally profitable (−0.28% on tiled input), append needs no format change, seek latency does not depend on position, and one archive is read by both a CPU and a GPU decoder. We give three structural results with proofs and bit-perfect verification—that the repeat-distance chain of an LZ77 parse forms a substitution monoid and is therefore prefix-scannable without touching the bitstream, that self-overlapping matches are periodic rather than chained, and that dependency depth admits an encoder-enforced bound—and we report each measured limit together with the mechanism that sets it. Seventeen rejected directions are listed with their numbers, including one that improved density by 26% and was declined. Every claim carries a level: reproducible by command, measured with a stated reason, or estimated. The measurement tool is released separately (DOI 10.5281/zenodo.22713364) with 435 provenanced records. Index Terms—random access, compressed data, block granularity, LZ77, reproducibility
I. I NTRODUCTION The specifications of zlib, Brotli, LZ4 and Zstandard contain the same sentence: the format does not attempt to provide random access to compressed data. It is therefore bolted on afterwards—by our count in at least nine independent implementations, including zstd’s own seekable format, zeekstd, seekable-zstd, two Go ports, one for .NET, SeekableXZInputStream, Google’s RAC, and the .zsi indices from Clonezilla. The trade this creates has been studied since 2016. Moffat and co-authors [1] built the frontier for six methods across 36 points at 16, 64 and 256 KiB. RAGE [2] states it as common ground: the granularity of random access is set by the block size. The xz documentation says it plainly—smaller blocks mean faster seeks and worse compression. A 2026 challenge over 117 compressors [3] reaches the same conclusion by another route: no compressor dominates on every criterion. Genomics pays this price knowingly rather than by accident: CRAM 3.1 caps FQZComp at sixteen bits of context so that
the model can be fitted quickly, which is what makes it usable in a format built for random access [21]. What has not been done is to put a number on it. We do not discover the trade-off. We measure its steepness, and show a format where the curve is nearly flat. What follows from flatness is the subject of the paper: if independence is cheap, a set of properties that are normally mutually exclusive can be held at once. II. F ORMAT AND W HAT F OLLOWS A. The core Every back-reference is resolved to an absolute position in the decompressed output at encode time. Four separate streams are stored—literals, offsets, lengths, commands—and the block table holds prefix sums into the decompressed streams. Independence comes from exactly one restriction, that match search may not cross a block boundary (cur >= bstart); the entropy streams remain global. The specification is docs/FORMAT_STREAMS.md in the public repository. B. The cost of independence Two definitions are in circulation and both are legitimate; the paper must say which it uses. We publish both, because for a month we published payload figures without naming the convention, and an external check found it. Payload counts the compressed streams only, excluding the header and the block table: chr1 0.41%, enwik9 2.54%, FASTQ 1.93%. Archive counts the file on disk. Fine-grained index structures are usually dismissed on the grounds that the index files become impractical [16]; ours is measured rather than assumed. On chr1 the archive is 80,829,622 bytes at 16 KiB against 79,510,864 as a single block. The difference of 1,318,758 bytes is 1.632% of the archive, of which the block table—64 bytes per block over 15,499 blocks, or 991,936 bytes—accounts for 75.2%. All archive figures below use the archive convention. Table I gives the curve at five granularities, measured by an independent agent on a different machine. Two features of the zstd column deserve saying rather than smoothing: it is not monotone—256 KiB is worse than 64 KiB—and its last point is negative. Both were re-run
TABLE I C OST OF INDEPENDENCE BY GRANULARITY, ARCHIVE CONVENTION , CHR 1; MEASURED BY AN INDEPENDENT AGENT ON A X EON 6973P-C.
zstd-seekable
ACEAPEX
10.06% 6.57% 2.83% 4.30% −0.51%
5.33% 1.632% 0.598% 0.267% 0.150%
cost of independence (% of archive)
4 KiB 16 KiB 64 KiB 256 KiB 1 MiB
profile interactive seekable dense fast-decode
zstd-seekable ACEAPEX
10 8
not monotone
6 4 2 0 2
16
LIT
FSE
seek p50
ratio
16 KiB 256 KiB 256 KiB 256 KiB
64 KiB 256 KiB 1 MiB 1 MiB
4 KiB 32 KiB 32 KiB 4 KiB
0.084 ms 0.49 ms 0.85 ms —
3.655 3.769 3.778 3.761
5
2 1
0.51%: framed archive smaller than unframed
4 KiB
block
RTX PRO 4000 (24 GB) H100 (80 GB)
10
sequential / scan (×)
granularity
TABLE II P ROFILES AS POINTS ON A MEASURED FRONTIER . PAYLOAD CONVENTION , EPYC 4344P.
64
block granularity
256
1 MiB
Fig. 1. The cost of independence falls with granularity three to four times faster for one format than for the other; the zstd curve also bends upward at 256 KiB and goes negative at 1 MiB. Archive convention, chr1.
separately and every archive size matched byte for byte, on the same corpus with a pinned codec version. For bgzip no comparable single-parameter baseline exists, since gzip’s 32 KiB window makes the base already blockwise. That cell is n/a with a reason, not an omission. C. Cutting an archive is free Because blocks are independent and the entropy chunks follow the data, dividing an archive costs nothing and can pay. Splitting chr1 in half on a block-aligned boundary gives 80,663,353 bytes against 80,829,622 whole, −0.206%; tiling a 64 MB prefix into sixteen 4 MB pieces gives 22,966,121 against 23,030,417, −0.279%. Each part gets entropy chunks fitted to its own statistics. We state the mechanism as a hypothesis rather than a finding: zstd also updates its tables within a frame, so “local statistics” does not explain the whole effect. The practical consequence is that a container of sub-archives gives append-only behaviour with no format change. The overhead is 68 + 64b bytes for b blocks: 3.3% at one block, 1.3% at 64. D. Latency as a parameter Table II lists four configurations. None was chosen by hand; all four are points on a measured Pareto frontier drawn from a sweep of 324 configurations, every one bit-perfect.
28
10 below 29 scan 2loses 211 1.0 212
blocks in flight
213
214
215
Fig. 2. The scan’s advantage is a function of how loaded the device is, not a property of the algorithm: on the weaker card it falls below the sequential kernel once enough blocks are in flight, and on the H100 that crossing lies beyond our data.
III. T HREE R ESULTS A. The repeat-distance chain is a substitution monoid A cache of the last k distances, updated by permutation and by insertion of explicit constants, is closed under composition: each command defines a map whose every output slot is either a constant or a copy of an input slot. The class is closed, associative, and has an identity. Therefore all states are computable in O(kn) work and O(k log n) span without altering the bitstream; for k = 4 that is O(n) work and O(log n) span. Verification is per command over 21,132,882 commands across two opposing profiles, with zero discrepancies. The physical result depends on how loaded the device is, and we report the dependence rather than a single number. On an H100: 2.87× at 8192 blocks, 1.81× at 15,499, 1.82× at 31,000. On an RTX PRO 4000: 14.8× at 256 blocks, 2.1× at 4096, 1.12× at 8192, and 0.87× at 15,499. The crossing point sits between 8192 and 15,499 blocks on the weaker card and beyond our data on the H100. The mechanism is that the sequential kernel is latency-bound and plateaus while the scan kernel is throughput-bound and grows, so two lines cross. Small sets overstate the gain badly—256 blocks give 38×, which measures kernel launch rather than work—so the publishable figure is the saturated one.
B. Self-overlap is a period, not a chain When dist < len a decoder is obliged to copy byte by byte, each output byte depending on the one just written. This is the sequential dependency behind the belief that LZ77 cannot be parallelised. The overlapping region is periodic with period dist, so out[dst + k] = out[src + k mod dist], and the source lies entirely outside the range being written. Every k is independent and a warp writes 32 bytes at once. Measured across four corpora, the match layer speeds up by 2.75–8.42×, bit-perfect; this was first published in Paper 5 of this series [23], and we restate it here because it is one of the three places where the sequential reading of the format turns out to be wrong. The periodicity itself is neither new nor ours. Production CPU decoders use it already: zstd’s ZSTD_overlapCopy8 carries the tables dec32table = {0,1,2,1,4,4,4,4} and dec64table, LZ4 carries the same, and an open pull request vectorises them through pshufb and NEON tbl. What differs is the width. There the period is used to straighten the source so that eight bytes can be copied at once when offset < 8; here it is the width of a warp, because every offset inside the match is computed independently rather than walked.
TABLE III M EASURED LIMITS AND THEIR MECHANISMS .
axis
limit
mechanism
GPU decode CPU decode parse GPU seek encode bus efficiency
179.8 GB/s 2564 MB/s 64–72% 360 µs 232 MB/s 4.4%
work granularity, median match 7 B Amdahl ceiling 1.75×, literals 43% three sequential parts, one removed 282 of it fixed launch cost LZ77 phase 91%, 224 instr/byte a property of the data
200
device-resident decode (GB/s)
We are explicit about novelty. Scanning by function composition is old: Ladner and Fischer [4] in 1980, and standard for finite automata. What is new is that the repeat-distance parse of LZ77, which the field treats as sequential by construction, falls into that class, and that the gain costs no ratio.
61,995 blocks fit; 100,000 do not
180 160 140 120 100 80 60
RTX PRO 4000 (24 GB) H100 (80 GB) 4 KiB
8
block size
16
32
Fig. 3. Smaller blocks mean more independent units of work and higher occupancy; the direction is the same on both cards, and the usable left end is set by how many blocks fit in VRAM.
C. An encoder-enforced bound on depth 1 + max(levelsrc ) ≤ L ⇒ MaxLevel ≤ L, by induction, bitperfect over the whole of chr1. The ratio cost runs from zero to 0.0053%, and at L=32 compression slightly improves. A separate lever targets latency rather than structure. The MAX cap bounds the maximum and costs nothing but does not touch latency; the AVG cap forces literals where lev > 1 inside blocks whose average exceeds 2. It moves the spike cluster’s average from 4.36 to 0.56 and P99 from 4.33 to 1.50, for 0.081% of ratio—sixteen times cheaper than raising the minimum match length—with 1.223% forced literals, bitperfect. The distinction matters because it closed a conceptual gap in the previous paper: the spike cluster has eight times the median average depth, yet its maximum stays below L=32, so a MAX cap does not see it at all. IV. L IMITS , E ACH W ITH I TS M ECHANISM Table III lists what we hit and why. A. Block size, an axis nobody swept On an H100 the format reaches 179.8 GB/s at 4 KiB, 160.7 at 8 KiB and 128.0 at 16 KiB; on an RTX PRO 4000, 112.8 at 8 KiB, 99.2 at 16 KiB and 78.8 at 32 KiB. The direction is the same on both cards—smaller blocks mean more independent units of work and higher occupancy—and 179.8 exceeds the 172 published earlier in this series.
Ratio barely moves across an eightfold change: 3.174, 3.178, 3.181. The archive behaves differently, because the block table doubles: 2.42% at 8 KiB against 1.23% at 16 KiB. The VRAM limit is set by the number of blocks, not by volume: 80 GB holds 61,995 blocks and fails at 100,000; 24 GB holds 30,997. The optimal block size therefore depends on file size, and the ACEAPEX_BS >= 4096 floor in the code is physics rather than caution: 1 and 2 KiB do not fit even on 80 GB. B. On the CPU there is no memory wall Holding match length fixed at a median of 5 and varying only distance gives 13.8 ns per match when everything is in L1, 12.5 on real chr1, 12.6 beyond L1d, 12.8 beyond L2 and 13.8 beyond L3. There is no difference. The cost is instructions, not memory: with a median distance of 81 bytes the source was written a few cycles ago and is always in L1. The wall exists on the GPU and only on the write side. That is the 4.4% bus efficiency—store coalescing at a median length of 5.9 bytes. C. Match statistics From 1,508,720 matches over 4000 blocks of chr1, with the command stream decoded against the encoder and coverage summing to exactly 100%: length has median 7 and mean
TABLE IV R EGION READ , 16 K B LOGICAL , 200 REQUESTS . A RCHIVE CONVENTION , X EON 6973P-C ( INDEPENDENT AGENT ).
(Xeon 6973P-C) and are not expected to lie on it. The intercept belongs to the first machine, and on the second it differs. B. Batching, and a claim we had to correct
format / profile
ratio
p50 ms
p99 ms
amp.
b/even
bgzip + htslib zstd-seekable ACEAPEX inter. ACEAPEX dense
3.3826 3.0258 3.6585 3.7806
0.0955 0.0470 0.1308 1.2805
0.2048 0.0545 0.2340 2.4660
4.82× 2.00× 6.22× 83.4×
3699 7446 1386 131
8.03, but the shape matters more than the summary. Almost half of all matches—45.33%—are exactly the minimum length of six bytes, and the distribution is not unimodal: 15.04% at seven, a second rise to 18.51% at eight, then 7.33% and 3.70%, 7.42% over 11–16 and 2.62% above 16. Ninety per cent of matches are eleven bytes or shorter. Matches cover 18.5% of the decompressed output of chr1 and literals cover 81.5%, summing to 100%. That single pair explains several things at once: why a domain transform on literals is worth 17% of density, why the median match is short, and why the match layer works on a fifth of the data while the rest of the density is entropy. Distance has median 81 and p10 8, with 17.23% at d ≤ 16, 27.37% at ≤ 32, 43.83% at ≤ 64, 66.64% at ≤ 128, 72.42% at ≤ 256, 79.19% at ≤ 512, 85.71% at ≤ 1024, 92.23% at ≤ 2048, 96.99% at ≤ 4096, 99.35% at ≤ 8192 and 100% at the block size of 16,384. Destination alignment is a multiple of 32 in 3.09% of cases against a random expectation of 3.12%—that is, not at all. V. T HE T RADE - OFF M EASURED , N INE A XES One operation is timed: a 16,000-byte logical region at a random uncompressed offset, 200 requests, archive resident, timer around the API call only. Table IV gives four formatprofile pairs. Throughput on an EPYC 7763: bgzip encodes at 19.8 MB/s and decodes at 582.5; zstd-seekable 150.4 and 482.3; ACEAPEX 39.5 and 1281.0. The dense profile encodes at 39.2 and its full-decode figure is a data edge—three points diverged by more than 5%—so we do not publish it. The losses belong in the text, not in a footnote. ACEAPEX encodes 3.81× slower than zstd. zstd-seekable reads a single region three times faster than we do and reads half as many bytes doing it. What we win is density, above both, and full decode 2.20× faster than bgzip and 2.66× faster than zstd-seekable. A. A latency law, and an open question inside it Across nine chunk configurations with amplification from 4.75× to 40×, region latency fits 0.056 ms + 0.0083 ms × amplification with R2 = 0.93, where amplification is (LIT + 3 FSE)/block. The intercept of 56 µs is 69% of the fastest point and does not move with chunk size; four zstd frames are touched per region. This is an open question of the paper, not a result. The fit is drawn from a chunk sweep on one machine (EPYC 4344P); the profiles of Table IV were measured elsewhere
Requests are grouped by block before threads start, with a threshold of 512 below which we go sequential. A previously circulated figure of 13× compared eight threads against one. At equal thread count the gain is 1.84× (interactive: 5944 against 10912). A claim of this kind is obliged to name the thread count. The gain depends on request count—1.05× at 100, 2.75× at 600, 3.77× at 2000, 4.60× at 5000—and on the entropy Hα of the access distribution over blocks: 4.6× at 11.8 bits, 13.4× at 6.3 (Zipf 1.2), 48.6× at 5.8 (hot set). 244,000 requests were checked byte for byte. C. Where random access stops paying At roughly 700 requests on this file, full decode becomes cheaper— that figure is from the EPYC 4344P, taken where the batch and full-decode curves cross. The tool’s own breakeven for the same profile on the Xeon is 1386. Both are cost models on their own machine, and we give both rather than choosing. Across the four formats the tool reports 3699 for bgzip, 7446 for zstd-seekable, 1386 for the interactive profile and 131 for dense. We are not aware of anyone publishing these numbers. VI. O NE A RCHIVE , T WO C ONSUMERS The full device-resident pipeline runs entropy and match on the GPU, bit-perfect with FNV matching the original. An H100 80 GB reaches 179.8 GB/s at a 4 KiB block with G=16; an RTX PRO 4000 Blackwell 24 GB reaches 112.8 at 8 KiB, both on driver 580.178.04 under CUDA 12.4.131. Three H100s give 171.9, 171.5 and 171.5 GB/s simultaneously, all bit-perfect—a direct consequence of block independence: the file divides into N parts and each decodes without knowing about the others. G=16 is confirmed as the default: at a 4 K block, G=8 gives 156.4, G=16 gives 179.3 and G=32 gives 171.7. The single exception is a 16 K block on chr1, where G=32 gives 136.2 against 129.7. GPU seek loses to CPU seek on both cards: 360 µs on the H100 and 575–783 µs on the RTX PRO 4000, a 36% spread, against 82 µs on the CPU. The GPU is for streaming and for batches, not for a single read. ncu was unavailable three times (ERR_NVGPUCTRPERM in containers without -privileged), so occupancy is argued indirectly through the block-size sweep rather than from counters. VII. W HAT W E R EJECTED The acceptance rule is that nothing already achieved may get worse; a trade is declined regardless of how the arithmetic of the gain looks. The hardest case was order-1 rANS on literals: 2.113 bits per byte against zstd’s 2.861, a 26% density gain taking ratio
50
80
40
share of matches (%)
matches with distance d (%)
100
60 40
median 81 B: source still in L1
20 0
16
64
256
1024
4096
match distance d (bytes)
16384
45.3% of matches are exactly the minimum length: six bytes, a fifth of a warp
30 20 10 0
6
7
8
9
10
match length (bytes)
11-16
>16
Fig. 4. Two distributions explain two of the limits: sources sit close enough that they are still in L1 when reused, which is why there is no memory wall on the CPU; and matches are shorter than a warp, which is why the GPU write bus runs at 4.4%. Both panels come from the same parse of n = 1,508,720 matches over 4000 blocks of chr1.
region read, p50 (ms)
1.4 1.2
ACEAPEX dense
1.0 0.8 0.6 0.4 0.2
bgzip + htslib ACEAPEX inter.
zstd-seekable
0.0 3.0
3.2
3.4
3.6
compression ratio
3.8
Fig. 5. No format dominates: the two established ones read a region faster, ours are denser, and the dense profile trades an order of magnitude of latency for the last 3% of ratio. Xeon 6973P-C, chr1, 16 kB logical region.
from 3.181 to 4.105—and decode fell 11% with seek down 43%, so it was declined. Checked against Turbo-Range-Coder, whose adaptive order-1 gives 136 MB/s at zstd’s density where ours gives 728 MB/s at density 26% better. The decision held. Sixteen others, each with its number: a 6-byte hash gains 16% speed and loses 1.7% ratio on every corpus; a direct 8mer table is four times faster than the hash and finds half the matches; parsing for write geometry has nothing to align, since destinations are effectively random (3.09% against 3.12%) and matches longer than 32 bytes are 0.07% of tokens and 0.5% of data; SIMD search without tables is 7–16 times slower and finds half as much; aggregating short matches fails because the median run of consecutive short matches is 1; a 2-bit decode window fails because d is a multiple of 4 in 24.02% of cases against a random 25%; a 64-byte register window is 1.61× slower because maintaining it costs more than it saves;
transposing FASTQ loses 709% on bases, since correlation runs along a read and not across; order-1 on the command stream gains 6.3% over an alphabet of 249, which is 0.44 MB for a second coder; deriving the block table saves 0.70% of size for 4.6% of time; merging the DNA streams costs 1.3%; and skipping an empty length stream gains nothing. Four directions were closed earlier and belong in the same list, since a closed direction is also a result: a modular layout of literals (mod-4) cost 0.9% of ratio and gave nothing back at decode; a flat literal buffer in place of chunks cost 43% of seek; a 4-byte stride on DNA failed for the same reason transposition does, correlation running along a read rather than across; and separate decoders per stream (heterodecode) added 11% of time for no change in ratio. Two further items on early lists—generation indexing and the dual-stream bitstream—are not rejected ideas but features already implemented. That is seventeen rejected directions in total. VIII. M ETHOD I S A C ONTRIBUTION The absolute belongs to the machine; the ratio is what is checked. One regional call takes 0.082 ms on an EPYC 4344P, 0.111 on a laptop under WSL, 0.131 on a Xeon 6973P-C and 0.154 on an EPYC 9V74—a factor of two—while the ratio against bgzip stays between 10.8 and 15.2. Saturation. Measuring on the whole of an available file measures the corpus, not the system. Load must grow until the curve flattens; otherwise the figure is a data edge. We twice recorded an understated GPU number, 94 and then 136, because we were measuring the edge. Configuration is part of the name of a row, written as ACEAPEX @ SHA · block 16 KiB · lit 64 KiB · fse 4 KiB · threads 8. Library version is printed beside the number, since libzstd 1.5.5 is about a percent denser than 1.4.8. A contract of 32 checks runs from a clean clone with one command, downloads chr1 from UCSC and verifies its
md5, and runs in CI on every commit. Claims carry levels: R reproducible by command with an expectation and a tolerance, M measured with the reason it is not reproducible, and E estimated from measured quantities. External checking finds what the home machine cannot. In one day, external sources—CI, a laptop under WSL, an independent agent—found five defects and the main machine found none: a reused variable meant the report had not been written since 13 August; a threshold taken from one machine did not hold on three others; a 13× batch figure was comparing eight threads against one; a ratio was computed without the header and block table; and a read past the end of an array when the block equalled the file size (found by ASan). A sixth came through someone else’s measurement: the encoder default was losing 17.1% of density on genome, because literal chunking was off without an explicit LIT_CHUNK and the domain transform did not run without it (3.18065 against 3.72329). This is a methodological claim of the paper: a machine where everything is configured cannot verify reproducibility— it is the thing one needs to be independent of. IX. T HE T OOL hw-apex-bench is released separately under Apache-2.0 with measurements under CC BY 4.0, DOI 10.5281/zenodo.22713364: four codecs, nine axes, 435 records with provenance. A codec is added as a single adapter file; -check builds it, runs a round trip and prints the axes it supports, and an unchecked adapter is not admitted to measurement—which neither lzbench nor TurboBench enforces. An unsupported axis prints n/a with a reason supplied by the adapter, never an empty cell. The interface has been exercised by an external CLI adapter with no change to the core. X. L IMITATIONS Encode is 3.81× slower than zstd, because match search is confined to a block and the table does not amortise across boundaries. This is the same stick as the 1.632% of Section 2—one cost seen from two ends. A single region read in zstd-seekable is three times faster than ours at half the amplification. SAGe states our problem in the same words—genomic data is held compressed and must be decompressed and reformatted before an accelerator can touch it—and solves it in hardware, inside the storage device [15]. We solve it in the format, by making the compressed bytes directly readable. The two approaches are complementary and neither subsumes the other. A third line declines to change anything at all. Seekable OCI [22] traces zran.c through stargz to AWS SOCI and the zran mode of Nydus, and concludes that no new format is needed—only an external index mapping files to compressed byte ranges inside the existing gzip layers, which works because a DEFLATE block decompresses independently given a starting offset and 32 KiB of dictionary state. That is the price, and it is worth stating beside ours: 32 KiB of state
per entry point there, 1.632% inside the format here and no external index. These are production systems at large scale solving the same problem by the opposite route, and both work. Our guarantee is also of a different kind from the theoretical one. LZBE supports O(log n)-time random access to a symbol [6], and lower bounds for grammar-compressed strings [7], [8], [9] say where the ceiling of that line lies. We offer no asymptotic bound per symbol; we offer block independence by construction and measured microseconds for a 16 KiB region. Neither result implies the other, and a reader from either side should know which they are getting. Highly repetitive collections are a weakness: a match cannot leave its block, so repeats between versions of a file are not taken, and r-index style structures win there. The GPU figures come from rented cards rather than CI, since GPU runners for open projects effectively do not exist. The c(g) curves rest on one corpus; other data will move them, which is part of why the tool exists. There is no second independent decoder. The specification is published and nobody has written to it. There is no conformance corpus: there has been fuzzing, but no corpus. Of five gates toward a standard, two and a half are passed: the specification is published, an implementation works, an external independent benchmark exists, and there is one external user. A second independent decoder and a conformance corpus are not—and the first of those is the one thing that cannot be done alone. The code is in lzbench (PR #276, #277) under the maintenance of inikep and tansy. R EPRODUCIBILITY Canonical corpus: chr1, UCSC hg38, 253,935,557 bytes, md5 9465e0f0df6e2c6eb39729c39cee5465. Release tag paper6-v1, commit b9e29102477f82a498ba49d15dc49306fb8c0013. The ACEAPEX artifact is archived at DOI 10.5281/zenodo.22758786 for this version, with 10.5281/zenodo.20440964 resolving to all versions; the measurement tool is at 10.5281/zenodo.22713364. ACEAPEX is MIT licensed; the tool is Apache-2.0 with its measurements under CC BY 4.0. The contract runs from a clean clone with git clone https://github.com/yasha1971-coder/aceapex cd aceapex && ./reproduce_paper5.sh
and records 32 pass, 0 fail, 9 skipped on an EPYC 4344P, and 19 pass, 0 fail, 17 skipped on a four-core GitHub Actions runner. The difference is the GPU and large-corpus claims, which that runner cannot reach. The parametric sweep of 324 configurations from which the four profiles of Table II are drawn is published as sweep.jsonl in the same repository, together with sweep_all.sh that produced it. R EFERENCES [1] A. Moffat et al., “Access time tradeoffs in archive compression,” arXiv:1602.08829, 2016.
[2] C. D. Rask and D. E. Lucani, “RAGE for the machine: image compression with low-cost random access for embedded applications,” arXiv:2402.05974, 2024. [3] A. Ribeiro et al., “The 2026 algorithmic information theory data compression challenge,” arXiv:2606.17712, 2026. [4] R. E. Ladner and M. J. Fischer, “Parallel prefix computation,” J. ACM, vol. 27, no. 4, pp. 831–838, 1980. [5] I. Boneh and P. Gawrychowski, “Random access to LZ-End,” arXiv:2607.14923. [6] H. Shibata, Y. Nakashima, Y. Yamaguchi, and S. Inenaga, “LZBE: an LZ-style compressor supporting O(log n)-time random access,” arXiv:2506.20107v3, 2026. [7] F. Cicalese, T. Gagie, Z. Lipták, G. Navarro, N. Prezza, and C. Urbina, “Incongruity-sensitive access to highly compressed strings,” in Proc. 34th European Symposium on Algorithms (ESA), LIPIcs vol. 388, pp. 125:1–125:22, 2026. doi:10.4230/LIPIcs.ESA.2026.125. [8] A. Duyster and T. Kociumaka, “Random access in grammarcompressed strings: optimal trade-offs in almost all parameter regimes,” arXiv:2602.10864v2, 2026. [9] D. Kempa and T. Kociumaka, “Tight lower bounds for central string queries in compressed space,” SODA, 2026. [10] E. Sitaridi, R. Mueller, T. Kaldewey, G. Lohman, and K. A. Ross, “Massively-parallel lossless data decompression,” ICPP, 2016. [11] M. Köhler, T. Bingmann, and P. Sanders, “Rapidgzip: parallel decompression and seeking in gzip streams using cache prefetching,” HPDC, 2023, pp. 295–307. [12] T. Lin et al., “Recoil: parallel rANS decoding with decoder-adaptive scalability,” ICS, 2023. [13] G. Navarro, “Indexing highly repetitive string collections,” ACM Computing Surveys, 2021. [14] K. Wesley, “Massively parallel LZ77 compression and decompression on the GPU,” M.S. thesis, Dept. of Computer Science, Texas State University, San Marcos, TX, Dec. 2022. [15] N. Mansouri Ghiasi, T. Güloglu, H. Mustafa, C. Firtina, K. Koliogeorgi, K. Kanellopoulos, H. Mao, R. Nadig, M. Sadrosadati, J. Park, and O. Mutlu, “SAGe: a lightweight algorithm-architecture co-design for mitigating the data preparation bottleneck in large-scale genome sequence analysis,” in Proc. HPCA, 2026. arXiv:2504.03732. [16] J. Fu, B. Ke, and S. Dong, “LCQS: an efficient lossless compression tool of quality scores with random access functionality,” BMC Bioinformatics, vol. 21, art. 109, 2020. doi:10.1186/s12859-020-3428-7. [17] S. Grabowski, T. M. Kowalski, and R. Susik, “FFC: a scalable FASTA compressor,” Bioinformatics, vol. 42, no. 3, btag132, Mar. 2026. doi:10.1093/bioinformatics/btag132. [18] Meta, “DietGPU: GPU-based lossless compression,” software, https:// github.com/facebookresearch/dietgpu. [19] NVIDIA, “nvCOMP,” software, repository archived 2026. [20] A. Jarmusch and S. Chandrasekaran, “Microbenchmarking NVIDIA’s Blackwell architecture: an in-depth architectural analysis,” arXiv:2512.02189v3, 2026. [21] J. K. Bonfield, “CRAM 3.1: advances in the CRAM file format,” Bioinformatics, vol. 38, no. 6, pp. 1497–1503, Mar. 2022. doi:10.1093/bioinformatics/btac010. [22] J. Thompson, W. Mesard, J. Butler, S. S. B. Vellore Rajakumar, and H. Wang, “Seekable OCI: lazy-loading container images via rangerequest indexing,” arXiv:2607.06868, 2026. [23] Y. Shavidze, ACEAPEX Papers 1–5: arXiv:2606.04268, 2606.18900, 2606.24531, 2607.18541, 2608.10188.