StateSMix: Online Lossless Compression via Mamba State Space Models and Sparse N-gram Context Mixing
| Authors | Roberto Tacconelli |
| Year | 2026 |
| HF Upvotes | 6 |
| arXiv | 2605.02904 |
| Download | |
| HF Page | View on Hugging Face |
Abstract
We present StateSMix, a fully self-contained lossless compressor that couples an online-trained Mamba-style State Space Model (SSM) with sparse n-gram context mixing and arithmetic coding. The model is initialised from scratch and trained token-by-token on the file being compressed, requiring no pre-trained weights, no GPU, and no external dependencies. The SSM (DM=32, NL=2, approximately 120K active parameters per file) provides a continuously-updated probability estimate over BPE tokens, while nine sparse n-gram hash tables (bigram through 32-gram, 16M slots each) add exact local and long-range pattern memorisation via a softmax-invariant logit-bias mechanism that updates only non-zero-count tokens. An entropy-adaptive scaling mechanism modulates the n-gram contribution based on the SSM's predictive confidence, preventing over-correction when the neural model is already well-calibrated. On the standard enwik8 benchmark, StateSMix achieves 2.123 bpb on 1 MB, 2.149 bpb on 3 MB, and 2.162 bpb on 10 MB, beating xz -9e (LZMA2) by 8.7%, 5.4%, and 0.7% respectively. Ablation experiments establish the SSM as the dominant compression engine: it alone accounts for a 46.6% size reduction over a frequency-count baseline and beats xz without any n-gram component, while n-gram tables provide a complementary 4.1% gain through exact context memorisation. OpenMP parallelisation of the training loop yields 1.9x speedup on 4 cores. The system is implemented in pure C with AVX2 SIMD and processes approximately 2,000 tokens per second on commodity x86-64 hardware.
Engineering Breakdown
Plain English
StateSMix is a lossless file compressor that trains a small Mamba-style state space model directly on the file being compressed, without any pre-trained weights or GPU hardware. The system combines a 120K-parameter SSM (depth=32, 2 layers) with nine sparse n-gram hash tables (bigram through 32-gram) and arithmetic coding to achieve compression by learning the statistical patterns in the specific file. The key insight is that you can get very good compression by continuously updating probability estimates as you process each token, mixing predictions from both the online-learned neural model and exact pattern matching, with an entropy-adaptive mechanism that decides how much to trust each signal.
Core Technical Contribution
The core novelty is demonstrating that lossless compression can be achieved with a fully online-trained SSM that requires no pre-training, GPU, or external dependencies—only the file itself. Instead of relying on a single model type, StateSMix couples a lightweight Mamba SSM with sparse n-gram tables via a logit-bias mechanism that selectively strengthens predictions for tokens that actually appear in local context, rather than applying dense mixing across all vocabulary. The entropy-adaptive scaling mechanism is adaptive tuning that adjusts how much the n-grams contribute based on the SSM's own uncertainty, creating a feedback loop where the two components reinforce each other. This is architecturally different from prior neural compression work that either requires massive pre-trained models or uses fixed hand-crafted statistical methods without learned components.
How It Works
The compression pipeline operates token-by-token on the input file: (1) Tokenize the file using BPE tokens, (2) Initialize the Mamba SSM from scratch with 120K active parameters spread across 32 hidden dimension and 2 layers, (3) For each new token, the SSM processes the previous context and outputs a probability distribution over the BPE vocabulary. In parallel, nine sparse n-gram hash tables (one for each n-gram size from 2 to 32) record which n-grams have appeared and their frequencies in the file so far. The n-gram tables use a softmax-invariant logit-bias mechanism: instead of normalizing, they add a learnable bias directly to the logits of tokens that appear in matching n-gram contexts, so the operation is equivalent to a conditional probability boost. An entropy-adaptive scaling mechanism computes the SSM's entropy or confidence on the current prediction and adjusts a weight factor—when the SSM is uncertain (high entropy), the n-gram biases are amplified; when the SSM is confident, they are attenuated. The combined probability distribution is then fed into an arithmetic coder, which encodes each token using its predicted probability, producing the compressed bitstream.
Production Impact
For production systems, StateSMix enables lossless compression on embedded or edge devices because it requires no pre-training phase, no GPU, and no external model downloads—you can run it on CPU in real time as files arrive. This is valuable for archival systems, incremental backup pipelines, or IoT devices where model management overhead is prohibitive; the compression ratio adapts to the specific file structure without retraining across datasets. The trade-off is that compression is slower than traditional algorithms like zstd because the SSM must be trained and updated token-by-token, and memory overhead is non-trivial (16M slots × 9 hash tables plus SSM state). Compared to dictionary-based compressors (gzip, zstd), StateSMix likely achieves better compression on repetitive or structured data but worse latency and predictability; compared to neural compressors like ByteStream or Finite Scalar Quantization, it avoids the need for large pre-trained models and GPU inference. Integration would require replacing compression libraries in your stack and accepting variable encode/decode times that depend on file size and complexity.
Limitations and When Not to Use This
StateSMix assumes the file being compressed is large enough and structured enough to support meaningful SSM training—on random noise or very small files, the online training will not converge and the n-gram tables will not accumulate useful statistics, likely resulting in poor compression ratios (possibly worse than no compression). The paper does not discuss how compression quality scales with file size, domain shift, or adversarial inputs, nor does it provide empirical compression ratios on standard benchmarks like the Silesia corpus or comparison to state-of-the-art methods like ZPAQ or neural compressors. The mechanism is also unidirectional: you must decompress sequentially by replaying the token-by-token SSM training, which prevents random access or parallel decompression; this makes it unsuitable for seek-friendly applications. The paper mentions the abstract is truncated ('entropy-adaptive scaling mechanism modulates the n-gram contribution based on the SSM''), so critical details about the exact scaling formula, hyperparameter tuning, and loss functions are missing from the provided text.
Research Context
This work builds on the recent success of Mamba and state space models as a lightweight alternative to transformers for sequence modeling, extending them into the lossless compression domain where online learning is natural. It also connects to the long history of context mixing in compression (PAQ family, Zstandard with context models) but replaces hand-crafted context selection with learned SSM features and sparse n-gram lookup. The entropy-adaptive mechanism echoes prior work in compression on mixture-of-experts and conditional computation, where different models contribute based on input characteristics. This opens a research direction toward learned, low-resource compressors that adapt per-file, contrasting with the current paradigm of large pre-trained neural compression models or fixed-rule statistical compressors.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::