GPU LZ77 decode latency is governed by the parse stage, not by back-reference depth; self-overlapping matches are parallel periodic fills, and an encode-time flag removes the last sequential element for 0.540% ratio.
Unified Position-Invariant Random Access Through Two Compression Layers via Absolute-Offset Coordinates: A Bit-Perfect Device-Resident Proof
1 Pith paper cite this work. Polarity classification is still indexing.
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. The seek of one 16KB block through ANS-entropy and match completes in 0.334ms. We verify the full entropy+match pipeline end-to-end on four data profiles 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.
citation-role summary
citation-polarity summary
fields
cs.DC 1years
2026 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
What Actually Serializes GPU LZ77 Decode: Three Decoders, Three Mechanisms, and an Encode-Time Lever That Removes the Last One
GPU LZ77 decode latency is governed by the parse stage, not by back-reference depth; self-overlapping matches are parallel periodic fills, and an encode-time flag removes the last sequential element for 0.540% ratio.