Unified Position-Invariant Random Access Through Two Compression Layers via Absolute-Offset Coordinates: A Bit-Perfect Device-Resident Proof Yakiv Shavidze
arXiv:2606.24531v1 [cs.DC] 23 Jun 2026
ACE / GLYPH Research [email protected]
Abstract Random access into compressed data is normally confined to a single layer. Entropy-layer methods (Recoil) seek within rANS by storing intermediate decoder states; dictionary/match-layer methods seek within LZ-style references. We are not aware of a format that supports a single position-invariant seek through both an entropy layer and a match layer addressed by one coordinate. We show that ACEAPEX’s absolute-offset design provides exactly this: because the match layer resolves every back-reference to an absolute position at encode time, and the entropy layer is applied per block, an arbitrary block can be decoded through both layers using one coordinate, bit-perfect, in isolation. We prove this with a three-phase verification that closes the empty-buffer trap (confirming the output buffer is empty before decode, equals the original after, and that neighboring blocks are untouched). The seek of one 16 KB block through ANS-entropy and match completes in 0.334 ms. We verify the full entropy+match pipeline end-to-end on four data profiles (real FASTQ, repetitive genome, English text, mixed) and characterize the hardware ceiling the format reaches: the absolute-offset structure unrolls to as many as 25,344 independent parsers on one H100, which sequential LZ77 cannot do. We state explicitly what is not claimed: this is a round-trip correctness proof, not a disk-archive format; throughput figures are match-phase; and the unified-seek result is demonstrated for two layers, with three-layer generalization left as a hypothesis. Code and the verification harness are in the project repository.
1
Introduction
batched GPU ANS but, again, has no match layer below to seek through. In prior work we introduced ACEAPEX, a parallel LZ77 codec whose match layer resolves every backreference to an absolute position in the decompressed output at encode time [1], and showed device-resident GPU match-decode with position-invariant region seek at the match layer [2]. This paper adds the entropy layer on the GPU and proves the property that the twolayer structure uniquely enables: a single positioninvariant random access through both the entropy layer and the match layer, addressed by one absolute-offset coordinate, bit-perfect and isolated. We are deliberately narrow. We do not claim GPU entropy parallelism as novel—it is well established (Recoil, DietGPU, interleaved rANS [6]). We do not claim that a universal entropy+match pipeline is itself novel. The single contribution is the unified seek through both layers by one coordinate, and a rigorous proof that it is correct and isolated. Everything else in the surrounding space is occupied, and we say so explicitly throughout. This paper is the third in a sequence and closes it. The first [1] established the absolute-offset format and
Compressed data is usually read from the beginning. Random access—decoding an arbitrary region without decompressing everything before it—is valuable for archives, genomics, and GPU-resident pipelines, but it is hard because compression introduces dependencies. Two independent lines of work attack this. In the entropy layer, Recoil [3] enables parallel rANS decoding with random access by storing intermediate decoder states as entry points. In the match/dictionary layer, formats that resolve references can seek to reference boundaries. Each solves random access within its own layer. A realistic codec stacks both: an entropy layer over a match layer. To seek into such a stack at an arbitrary position, one must enter both layers correctly at that position. To our knowledge, no existing format supports a single position-invariant seek through both an entropy layer and a match layer using one shared coordinate. Recoil addresses the entropy layer only; it has no match layer beneath it. CPU genomic tools such as Hecate [4] slice per stream but operate on a single layer and are not GPU-resident. DietGPU [5] provides 1
its CPU decode. The second [2] moved one layer—the match layer—onto the GPU device-resident, with region seek at that layer. The present paper adds the second layer—entropy—on the GPU and proves the property the full two-layer stack uniquely enables: a single seek through both layers by one coordinate. The arc is format → one layer on GPU with seek → both layers with a unified seek. This is the closing of the stack, not a repetition of it; each paper depends on the one before, and this one cannot stand without the absolute-offset match layer the first two built.
out an absolute-offset match layer: Recoil has no match layer; Hecate is single-layer and CPU; DietGPU has no match layer beneath its ANS.
4
Experimental Setup
All GPU experiments ran on a single NVIDIA H100 80 GB HBM3 (SXM). Correctness is bit-perfect throughout, verified by FNV hash of decoded output against the original bytes. The verification harness (round-trip ANS encode/decode composed with the match decoder, plus the three-phase seek checker) is in the project repository for reproducibility. Throughput 2 Background and Prior Stack figures, where given, are match-phase on decompressed ACEAPEX stores each LZ77 back-reference as an abso- streams, consistent with Paper 2; we do not report full lute position in the decompressed output rather than a end-to-end ANS+match throughput as a single number relative distance within a sliding window. The encoder (see Limitations). performs a global match search and partitions output into fixed-size blocks; because offsets are absolute, any Core Result: Unified Twoblock decodes once the blocks holding its source bytes 5 are present [1]. Paper 2 [2] showed this match layer runLayer Seek ning device-resident on a GPU with region seek at the match layer (0.365 ms), stream separation, and range The central experiment seeks a single block through decoding to decouple output size from VRAM. both the ANS entropy layer and the match layer usPaper 2 timed the match phase; entropy ran on the ing one absolute-offset coordinate, and verifies the reCPU. The open question it left was the second layer: sult in three phases designed to close the empty-buffer can the entropy stage also run on the GPU, and—more trap (where a decoder appears correct only because the importantly—can a single seek pass correctly through original data was already present in the output buffer). both layers at an arbitrary position? This paper answers We seek block 2000 of 81,729 (the middle of the real that. FASTQ clean profile):
3
• Phase 1 (buffer is empty before decode): the hash of the output region before the match phase differs from the original (9c1bda7f̸=original). The buffer is genuinely empty—we are not reading preloaded original data.
Why Only an Absolute-Offset Match Layer Enables This
The structural argument is short. A unified seek through two layers requires that, at the target position, both layers can be entered without having processed earlier positions. The entropy layer can be made enterable per block (store or recompute per-block entropy state—Recoil’s contribution, and what DietGPU’s batching gives). The hard part is the layer beneath: a match layer with relative offsets cannot be entered at an arbitrary block, because a relative reference points backward by a distance that assumes the decoder already knows its current absolute position, which depends on everything decoded so far. Absolute offsets remove that dependency. A match referencing absolute position p can be resolved as soon as the block containing p is available, regardless of the decoder’s path to the current block. So a single coordinate—the absolute block boundary— simultaneously names the entropy entry point and the match entry point. This is why the unified seek is, to our knowledge, structurally unavailable to formats with-
• Phase 2 (output equals original after decode): after decoding through both layers, the seeked region’s FNV (cf485979995c1602) equals the original FNV. The seek is correct over the full 16,384-byte block. • Phase 3 (neighbors untouched): the blocks immediately before and after the target are checked as zero (prev=0, next=0). Only the target block was written—true isolation, not a wide decode that happens to include the target. The single-block seek through both layers completes in 0.334 ms. This is the paper’s core claim, and the three-phase structure is the evidence of its rigor: each phase rules out a distinct way the result could be falsely positive. We emphasize the boundary immediately. This is a round-trip: the ANS stream is encoded and decoded 2
Table 2: Per-stream ANS ratio by profile. Values <1 mean ANS inflates the stream.
Table 1: End-to-end ANS+match, bit-perfect, four profiles. Throughput is match-phase. Profile clean (real FASTQ NA12878) repeat (repetitive genome) enwik9 (English text) silesia (mixed)
Result
Match-phase
Profile
LIT
OFF
LEN
CMD
MATCHES OK MATCHES OK MATCHES OK MATCHES OK
121.9 GB/s 183.3 GB/s 6.1 GB/s —
clean (genome) repeat (genome) enwik9 (text) silesia (mixed)
1.42 3.06 1.47 1.27
0.51 0.27 1.02 1.04
0.09 0.04 0.49 1.05
0.60 0.48 1.38 1.41
Table 3: Parser parallelism vs. match-phase throughput, one H100.
within one run, not loaded from a prepared on-disk archive. The experiment proves the correctness and isolation of a unified two-layer seek, not a storage format. The 0.334 ms latency includes kernel-launch overhead and is not optimized; it is evidence of correctness, not a speed record. To our knowledge, this is the first demonstration of a single position-invariant seek through both an entropy layer and a match layer addressed by one coordinate, on a GPU, with proven isolation—as distinct from singlelayer random access, which is well established for LZstyle match layers [7] and for ANS entropy layers [8] separately, and from approaches that store per-position decoder state as metadata. We claim only this narrow, layered priority, and we substantiate it by the targeted prior-art review in Section 9 rather than by assertion; single-layer random access is decades deep, and we do not claim priority there.
6
G
parallel parsers
GB/s
8 16 32
25,344 12,672 6,336
154.8 176.9 166.8
(ratio <1), because those streams are structural rather than byte-entropic. On text the effect is milder (offsets neutral, commands helped); on mixed data all streams are ≥1. The behavior is data-dependent (Table 2). The design conclusion, now reproduced across four profiles, is that entropy coding should be applied selectively and adaptively per stream—measured at encode time—not by a fixed rule.
7
Hardware Ceiling the Format Reaches
End-to-End Across Four ProThe absolute-offset structure removes the byte-N files
depends-on-byte-N −1 chain of sequential LZ77, exposing massive independent parallelism. We characterize the ceiling this reaches on one H100. Sweeping the per-parser granularity G on the clean 16 KB stream: The format unrolls to as many as 25,344 independent parsers at G=8, with the throughput optimum at 12,672 parsers (G=16, 176.9 GB/s; Table 3). Sequential LZ77 cannot expose this parallelism at all— each byte depends on the previous one. A block-size sweep confirms the GPU saturates early: from 16 KB to 4 KB blocks, throughput rises only 166.1→177.5 GB/s (+7%) for 4× the blocks, while ratio falls 3.939→3.839. Sixteen-kilobyte blocks already saturate the device. At scale, a 50 GB genome compresses to a 23.6 GB archive containing 3,051,758 seekable blocks. Decod6.1 Per-Stream Entropy Is Dataing all 50 GB at once exceeds VRAM (50 GB output + Dependent 23.6 GB input ≈ 73 GB), which is the empirical wall that A practical finding for codec design: applying ANS makes range decoding mandatory rather than optional. to all four streams is counterproductive on some data. A range decode of blocks 0–1000 returns its region in Measuring per-stream ANS ratio (compressed/raw, <1 0.654 ms without decompressing the other 50 GB. We means ANS inflated the stream): note the honest bound: that 0.654 ms region is latencyOn genomic data, ANS compresses literals (LIT) but bound (a 1000-block range underfills the parser array), inflates the structural offset/length/command streams not a peak-throughput figure. To show the entropy+match composition is not specific to one input, we verified it end-to-end (ANS round-trip composed with GPU match decode, FNV-checked) on four profiles: All four are bit-perfect (Table 1). The enwik9 figure (6.1 GB/s) is low for an instructive reason consistent with Paper 2: it was encoded with 1 MB blocks (200 blocks total), which underfills the GPU (200 tasks across 132 SMs). The genomic profiles used 16 KB blocks (4096 blocks) and reach 121–183 GB/s. This is the occupancy effect, not a correctness issue—block size, set at encode time, governs how many independent parsers the format exposes.
3
8
Limitations
patented by three major vendors, each for its own domain: Microsoft (US9058223, parallel entropy encoding on GPU), Intel (US12299940, interleaving cascaded dictionary and entropy token-streams for texture supercompression, class G06T), and Qualcomm (US12556707, compression of entry-point indexes for wide-scale parallel entropy coding in neural video codecs, class H04N). The first targets parallel encoding, the second dense texture throughput via fused stages (interleave, not seek), the third entry-point index compression for neural video. None addresses positioninvariant random access through a match layer and an entropy layer by a single absolute-offset coordinate. Our mechanism differs in operation—unified two-layer seek versus parallel encoding or interleaving—and is the only one providing addressability into compressed data rather than throughput or index density. NVIDIA Parabricks is orthogonal: it accelerates analysis (FASTQ→BAM→VCF) and treats compression as transport/staging (decompress→analyze→discard), whereas we keep data compressed-resident and seek into it (keep→seek→keep). It is a potential complement at the input layer, not a competitor. Finally, conditionalindependence random access through a fixed parameter is a known principle in genetics (popgen-FSE), which structurally supports the absolute-offset approach.
We state the boundaries explicitly; they delimit the claim rather than weaken it. Round-trip, not disk archive. The ANS stream is encoded and decoded within one run. This proves the correctness and isolation of the entropy↔match coupling and the unified seek; it does not prove a storage format that loads a prepared ANS archive from disk. That is the next engineering step. Sub-range, not whole file at once. Experiments run on block ranges (4096 / 200 / 1 block). Whole-file decode proceeds in sub-batches (the ANS batch limit is on the order of a few thousand blocks per call); this is scaling work and is separate. Correctness does not require the whole file, but we do not claim “all 50 GB in one pass.” Match-phase throughput, not full-pipeline throughput. GB/s figures are match-phase on decompressed streams, as in Paper 2. We do not report a single “X GB/s full ANS+match end-to-end” number. Latency includes launch overhead. The 0.334 ms seek is a correctness-and-isolation proof, not an optimized latency. Sub-range ratios are not representative. Ratios measured on early-file block ranges are not published as ACEAPEX’s ratio, since the file head is homogeneous. “Not found in our scan” is not “does not exist.” Two targeted searches did not find a competitor occupying our exact point. We phrase this as “to our knowledge,” not “no one.”
9
10
Related Work
Discussion: A Two-Layer Result, and a Three-Layer Hypothesis
The core experiment proves the unified seek for N =2 layers (entropy + match). It suggests a general princiRecoil [3] enables parallel rANS random access via ple: any stack of transforms becomes position-invariantstored intermediate states; our entry points come from addressable by a single coordinate if each layer resolves absolute-offset block boundaries, not stored states, and its dependencies to absolute positions at write time. We our random access passes through a match layer Rehave verified N =2. We offer N =3 (a third layer with coil does not have. Single-layer random access is itself a genuine dependency) only as a hypothesis and future decades deep and we cite it first: Kreft and Navarro [7] work; it is not proven here, and we do not present it as give LZ77-like compression with fast random access such. at the match layer, and Bamler [8] characterizes ANS seeking at the entropy layer (requiring stored decoder state). Our contribution is neither of these alone but 11 Conclusion the unified seek through both. Hecate [4] (2026) is a modular genomic compressor with per-stream codecs We demonstrated a single position-invariant random acand random-access slicing; it is CPU, single-layer, and cess through both an entropy layer and a match layer, not absolute-offset GPU-resident—the nearest neigh- addressed by one absolute-offset coordinate, bit-perfect bor, from which we differ by GPU-residency and unified and isolated, verified by a three-phase check that closes two-layer position-invariance. DietGPU [5] is batched the empty-buffer trap. The unified seek of one 16 KB GPU ANS with no match layer beneath; we use it as the block through ANS-entropy and match completes in entropy layer and say so. Interleaved rANS [6] estab- 0.334 ms. We verified the entropy+match composition lishes that entropy parallelism is long known, which is end-to-end on four data profiles and characterized the why we do not claim it. hardware ceiling the absolute-offset format reaches (up Parallel entropy coding on GPUs is independently to 25,344 independent parsers on one H100). To our 4
knowledge this two-layer unified seek is structurally un- [7] S. Kreft and G. Navarro, “LZ77-like Compression available to formats without an absolute-offset match with Fast Random Access,” in Proc. Data Compreslayer beneath the entropy layer. We have been exsion Conference (DCC), 2010, pp. 239–248. plicit about what is not claimed: round-trip not archive, match-phase throughput, two layers not three. Code [8] R. Bamler, “Understanding Entropy Coding With Asymmetric Numeral Systems (ANS),” and harness are in the project repository, MIT-licensed, arXiv:2201.01741, 2022. archived on Zenodo (DOI: 10.5281/zenodo.20812332).
Author Contributions and Use of AI Assistance The author is solely responsible for the research: the central claim, the experimental design, the three-phase verification protocol, the prior-art review and novelty boundary, the verification of every figure against primary sources, and all final decisions. AI assistance (Claude, Anthropic) was used as a tool for drafting prose and for computational support, under the author’s direction and review. No part of the scientific judgment—what to claim, what to measure, what counts as proven, and what is left as a limitation—was delegated. This statement is made in the interest of full transparency; the standards of correctness and honesty applied here are the author’s own and are documented by the reproducible harness.
Acknowledgments The author thanks the encode.su community and the maintainers of lzbench for tooling and discussion.
References [1] Y. Shavidze, “ACEAPEX: Parallel LZ77 Decoding via Encode-Time Absolute Offset Resolution,” arXiv:2606.04268, 2026. [2] Y. Shavidze, “Compressed-Resident Genomics: Full-Pipeline Device-Resident GPU LZ77 Decode with Position-Invariant Random Access,” arXiv:2606.18900, 2026. [3] T. Lin et al., “Recoil: Parallel rANS Decoding with Decoder-Adaptive Scalability,” arXiv:2306.12141, 2023. [4] K. Szewczyk and S. Rahmann, “A Modular Genomic Compressor,” arXiv:2603.15390, 2026. [5] J. Johnson, “DietGPU: GPU-based Lossless Compression for Numerical Data,” open-source, 2022. [6] F. Giesen, “Interleaved arXiv:1402.3392, 2014.
entropy
coders,”
5