Skip to content
Preprint

The Invocation Bottleneck in LLM-Based Lossless Compression: What Can Be Removed and What Must Be Traded

Nov 2026 · 0 citations · 58 references
Computer Science Mathematics

TL;DR

This work removes 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.

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.

View source

Similar papers

Book Open access Oct 2026

BitLLM: Efficient Low-Bit, Conversion-Hiding LLM Decoding on Mobile GPUs

The rapid scaling of large language models (LLMs) has unlocked remarkable capabilities across various domains. However, deploying LLMs on mobile devices remains challenging because of their high computational and memory requirements. Low-bit quantization (e.g., 4-bit weights, 8-bit activations) can reduce model size wh...

Hang-Yu Zheng, Zhi-Hao Shu, Kun-Xiong Zhu et al. · 1 citation
Preprint Oct 2026

LLBPE: Linked-List Based GPU-Parallel BPE Tokenizer

This work develops LLBPE, a version of BPE that represents the token sequence as an array-based linked list so that each merge reduces to a constant- time pointer update.

Aditya Kovilur, V. C. Shekar, Ariful Azad · 1 citation
#machine learning Preprint Nov 2026

StrataFlux: Memory-Hierarchy-Native Low-Bit LLM Inference

Quantization reduces the memory and bandwidth demands of large language model (LLM) inference but can degrade accuracy; offloading higher-precision data can instead stall generation. We introduce StrataFlux, a framework that challenges this tradeoff by recovering accuracy lost to low-bit weight and key-value (KV) cache...

Jake Hyun, Zi-Yu Zhao, Jae-sun Seo et al. · 0 citations
Preprint Oct 2026

PlaneZip: Lossless Bit-Plane Compression of Training Activations Offloaded over PCIe

Training under a device-memory budget relies on tensor rematerialization: an evicted activation is either swapped to host memory or dropped and recomputed. Because GPU compute has outgrown PCIe bandwidth, cost-model planners such as MegTaiChi, which charge a swap its full transfer time, almost never swap, and swaps tha...

Zhu-Fang Gu, Qi-Zhe Tang, Yu-Xin Wang et al. · 0 citations
#machine learning Preprint Oct 2026

BitSparse: Compact Activation Storage for ReLU Feed-Forward Networks

Reducing memory use in large language model (LLM) training is an ongoing challenge. Activation checkpointing saves memory by recomputation, while lossy compression changes the stored activations. The reemergence of sparse $\relu$ and $\relu^2$ activations creates a third opportunity: losslessly compressing the activati...

Max Zhu, Bo-Han Sun, Pietro Liò et al. · 0 citations

Accelerating the Mitigation of LLM Inference Nondeterminism Across GPU Architectures

This work presents a solution employing a set of fixed-configuration fused-upcast GEMM kernels that load 16-bit weights from memory, upcast them to FP32 in registers, and accumulate with IEEE-754 arithmetic in a reduction order that is a pure function of the problem shape and is therefore independent of the device, its...

Liam Cooper, Shinnung Jeong, Hyeran Jeon et al. · 1 citation

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.