The Invocation Bottleneck in LLM-Based Lossless Compression: What Can Be Removed and What Must Be Traded
Abstract
Large language models (LLMs) compress text far better than classical compressors, but LLM-based compressors are slow, particularly during decompression. We argue that their decoding time has two fundamentally different sources. Execution redundancy, such as per-token host transfers, CPU-side coding, and token-by-token encoding, is work that the coded output does not require and can be removed without changing a single output bit. Sequential dependency, one model call per decoded token, is inherent to lossless decoding and cannot be removed by better execution, only traded for more calls or for more bits. We remove execution redundancy with a GPU-resident pipeline whose block-parallel encoding is made lossless in half precision by batch-invariant kernels, speeding up arithmetic coding by up to 5.8x in encoding and 3.0x in decoding without changing its compression rate. We then study the two ways of trading sequential dependency, speculative dual-model coding (SDMC) and multi-token single-model coding (MSMC), characterize the compression cost of predicting several tokens from a shared prefix, and identify the workloads in which fewer model calls are worth that cost.
Related
- A JoLT for the KV cache: Near-Lossless KV Cache Compression via Joint Rank-bit Allocation
- The relative isoperimetric profile of a unit square with a central square removed
- Asymptotically Lossless Exact and Pivotal E-Values
- Rates and Nearly-Lossless State over a Multi-Access Channel with Causal State Information
- Lossless Source Coding with Marginal Distribution Constraint
BibTeX
@misc{yan2026invocation,
title = {{The Invocation Bottleneck in LLM-Based Lossless Compression: What Can Be Removed and What Must Be Traded}},
author = {Zhe Yan and Yihao Liu and Antonio Boffa and Huanchen Zhang},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05871},
eprint = {2611.05871},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05871},
}
RIS
TY - UNPB
TI - The Invocation Bottleneck in LLM-Based Lossless Compression: What Can Be Removed and What Must Be Traded
AU - Zhe Yan
AU - Yihao Liu
AU - Antonio Boffa
AU - Huanchen Zhang
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.05871
UR - https://arxiv.org/abs/2611.05871
AB - Large language models (LLMs) compress text far better than classical compressors, but LLM-based compressors are slow, particularly during decompression. We argue that their decoding time has two fundamentally different sources. Execution redundancy, such as per-token host transfers, CPU-side coding, and token-by-token encoding, is work that the coded output does not require and can be removed without changing a single output bit. Sequential dependency, one model call per decoded token, is inherent to lossless decoding and cannot be removed by better execution, only traded for more calls or for more bits. We remove execution redundancy with a GPU-resident pipeline whose block-parallel encoding is made lossless in half precision by batch-invariant kernels, speeding up arithmetic coding by up to 5.8x in encoding and 3.0x in decoding without changing its compression rate. We then study the two ways of trading sequential dependency, speculative dual-model coding (SDMC) and multi-token single-model coding (MSMC), characterize the compression cost of predicting several tokens from a shared prefix, and identify the workloads in which fewer model calls are worth that cost.
ER -