A Model-Driven Lossless Compression Algorithm Resistant to Mismatch
This addresses a critical reliability issue in using complex models for compression, though it is incremental as it builds on existing prediction-based compression methods.
The paper tackles the problem of compression failing due to mismatches in predictive models like LLMs, and proposes a robust algorithm that achieves higher compression ratios than standard methods while ensuring reliable operation under certified mismatches.
Due to the fundamental connection between next-symbol prediction and compression, modern predictive models, such as large language models (LLMs), can be combined with entropy coding to achieve compression rates that surpass those of standard compression algorithms. However, this approach relies on the assumption that the predictive model produces identical output distributions at both the encoder and decoder, since even small mismatches can cause the decoding to fail. This assumption often fails with complex predictive models, particularly those based on neural networks, a phenomenon referred to as non-determinism. In this work, we propose a new compression algorithm based on next-token prediction that is robust to arbitrarily large, but structured, prediction mismatches. We prove the correctness of the proposed scheme under a formal mismatch certification, characterize its theoretical performance, and validate it experimentally on real datasets. Our results demonstrate reliable operation within the certified mismatch regime while achieving compression ratios that exceed those of commonly used compression methods.