Micro-Diffusion Compression - Binary Tree Tweedie Denoising for Online Probability Estimation

Roberto Tacconelli

Source-linked AI summary

Micro-Diffusion Compression - Binary Tree Tweedie Denoising for Online Probability Estimation

Roberto Tacconelli

arXiv:2603.08771v3Mar 9, 2026stat.MLcs.ITcs.LG

TL;DR

Adaptive compressors can produce overly flat predictions when sparse-context priors dominate, motivating a correction beyond normalized counts. Midicoth applies binary-tree, multi-step Tweedie denoising after model blending; it achieves 1.753 bpb on enwik8 and 2.119 bpb on alice29.txt, while remaining fully online and non-neural. Its scope is narrower on very small files and binary data.

Problem
Sparse PPM contexts can be dominated by prior smoothing, making predicted distributions flatter than the source distribution and reducing probability-estimation quality.
Method
Midicoth reverses prior-induced shrinkage with binary-tree Tweedie calibration applied in three denoising steps after five online model components are blended.
Results
1.753 bpb on enwik8 beats xz -9 at 1.989 bpb by 11.9%, while 2.119 bpb on alice29.txt beats xz -9 at 2.551 bpb by 16.9%.
Takeaways & Limitations
The post-blend Tweedie layer consistently reduces compressed size by 2.6–2.8% across both datasets and can calibrate an ensemble’s final distribution.
Takeaways & Limitations
On very small files below 50 KB, limited observations and pipeline overhead may reduce Midicoth’s advantage; binary data also receives little benefit from its word and high-order context models.

Abstract

from arXiv · show

We present Midicoth, a lossless compression system that introduces a micro-diffusion denoising layer for improving probability estimates produced by adaptive statistical models. In compressors such as Prediction by Partial Matching (PPM), probability estimates are smoothed by a prior to handle sparse observations. When contexts have been seen only a few times, this prior dominates the prediction and produces distributions that are significantly flatter than the true source distribution, leading to compression inefficiency. Midicoth addresses this limitation by treating prior smoothing as a shrinkage process and applying a reverse denoising step that corrects predicted probabilities using empirical calibration statistics. To make this correction data-efficient, the method decomposes each byte prediction into a hierarchy of binary decisions along a bitwise tree. This converts a single 256-way calibration problem into a sequence of binary calibration tasks, enabling reliable estimation of correction terms from relatively small numbers of observations. The denoising process is applied in multiple successive steps, allowing each stage to refine residual prediction errors left by the previous one. The micro-diffusion layer operates as a lightweight post-blend calibration stage applied after all model predictions have been combined, allowing it to correct systematic biases in the final probability distribution. Midicoth combines five fully online components: an adaptive PPM model, a long-range match model, a trie-based word model, a high-order context model, and the micro-diffusion denoiser applied as the final stage.

1. Introduction

Midicoth targets a bottleneck in adaptive compression: prior smoothing makes sparse-context predictions too flat, while the model cannot distinguish prior-dominated from data-dominated regimes. It reframes smoothing as denoising and applies binary-tree Tweedie corrections through a five-layer online pipeline.

1. Introduction: Sparse PPM contexts are dominated by the Jeffreys prior, producing flatter-than-source distributions and wasting coding bits.With many observations, the prior becomes negligible and predictions are already well-calibrated, but PPM uses the same normalized-count mechanism in both regimes.
1. Introduction: Midicoth treats Jeffreys smoothing as shrinkage toward uniform and reverses it with a Tweedie empirical-Bayes denoising step.The correction is applied to predicted probabilities rather than changing the underlying adaptive model.
1. Introduction: Binary-tree decomposition converts each 256-way byte calibration into eight binary decisions, improving data efficiency through parent-bit context.The method estimates score functions nonparametrically at each node using calibration tables.
1. Introduction: Three successive denoising steps apply additive corrections with independent score tables, allowing later stages to refine residual prediction errors.The update is expressed as p̂′ = p̂ + δ across K = 3 steps.
1. Introduction: The five-layer cascade combines PPM, match, word, high-order context, and final Tweedie correction, with ablations measuring each component’s contribution.The contribution list identifies the denoiser as the final post-blend correction stage.

2. Related Work

Prior compression work ranges from PPM and context mixing to neural language-model compressors, with post-prediction correction emerging as a useful design pattern. Midicoth positions micro-diffusion as a lightweight, non-neural alternative that conceptually connects Tweedie calibration with diffusion denoising.

2. Related Work: PPM predicts through variable-order contexts, while PAQ and CMIX blend many specialized models, reaching stronger enwik8 results at substantially higher resource costs.PAQ8px reaches ∼1.27 bpb and CMIX ∼1.17 bpb on enwik8, with CMIX using 16–64 GB RAM and hours of compression time.
2. Related Work: Post-prediction correction motivates Midicoth as a lightweight alternative to computationally expensive context-mixing systems.The related-work discussion explicitly identifies mixing and SSE as correction mechanisms.
2. Related Work: SSE and micro-diffusion both recalibrate predicted probabilities, but SSE uses gradient-based piecewise-linear maps while micro-diffusion estimates additive Tweedie corrections from sufficient statistics.A two-stage SSE chain interfered with Tweedie denoising and performed worse than Tweedie alone.
2. Related Work: Tweedie’s formula supplies a conceptual basis for correcting shrinkage, although the paper states that Jeffreys smoothing is not additive Gaussian noise and the link is not exact.Calibration tables approximate the Tweedie term nonparametrically.
2. Related Work: Micro-diffusion adapts diffusion-style score estimation to shrinkage toward uniform, using the effective noise level and three reverse-denoising updates.Independent score estimators are used at each step.
2. Related Work: Neural compressor examples achieve 0.9–1.1 bpb on enwik8 with pre-trained transformers, whereas Midicoth uses purely adaptive statistical models on a single CPU core.The comparison places the systems in different resource and modeling regimes.

3. Method

Midicoth builds an online compression pipeline whose blended byte predictions are calibrated by a multi-step Tweedie-inspired denoiser. Binary-tree calibration makes correction data-efficient, while post-blend placement addresses biases across the full ensemble.

Pipeline: Five online layers produce and encode each byte distribution: PPM, match, word, high-order context, and post-blend Tweedie denoising.The pipeline normalizes and blends predictions before arithmetic coding, then updates all models online.
Motivation: Jeffreys smoothing pulls low-count PPM predictions toward uniform, making them substantially flatter than the underlying source distribution.For n = 5 and qR = 0.9, the root estimate is 0.515 instead of 0.9, costing 0.96 rather than 0.15 bits at that node.
Tweedie calibration: Micro-diffusion treats this shrinkage as denoising and applies an empirically estimated additive correction to predicted probabilities.The correction is estimated from calibration bins as the difference between empirical outcomes and average predictions.
Binary-tree calibration: Each 256-way prediction becomes eight MSB-to-LSB binary decisions, reducing calibration complexity and providing coarse-to-fine hierarchical context.Binary outcomes receive one observation per prediction, while 27 bit contexts distinguish tree levels and parent paths.
Empirical contribution: 2.3–2.7%: the post-blend micro-diffusion layer’s reported contribution, while three denoising steps reduce compressed size by a further 1.5–2.5% beyond one step.The layer is applied after all model blending so it can correct systematic biases in the complete distribution.

3.4 Extended Match Model

The extended match model detects long-range repetitions with multiple context lengths and blends a repetition-based prediction into the upstream distribution.

Detection: Five hash tables track repeated contexts of lengths 4, 6, 8, 12, and 16 bytes.Each table maps an FNV-1a context hash to a position in the history buffer.
Prediction: Starting from length 16, the model predicts the byte following the longest available matched context.Continuation tracking increases confidence after consecutive correct predictions.
Blending: The match prediction is blended with the upstream distribution using a confidence-dependent weight capped at 0.95.The weight is wm = min(c · 0.85, 0.95).

3.5 Word Model

The word model combines trie-based continuation estimates with word-boundary statistics to predict bytes within and between words.

Components: Three components support word prediction: a continuation trie, a word-bigram table, and a word-frequency table.The trie stores per-node continuation counts, while the other tables model next-word starts and completion counts.
Prediction: During words, the trie predicts continuation bytes; at boundaries, the bigram table predicts the next word’s first byte.Confidence comes from observations at the current trie node.
Blending: Word predictions are blended with the upstream distribution using a weight capped at 0.45.The blending weight is ww = min(cw · 0.35, 0.45).
Implementation: Prediction caching avoids traversing the trie twice by reusing the forward-pass result during updates.This mechanism targets redundant trie work rather than changing the predicted distribution.

3.6 High-Order Context Model

The high-order context model extends context length beyond PPM’s order-4 limit through separate hash-based models for orders 5–8. It preserves sharp predictions and is blended separately because fusing these orders into PPM performed worse.

Model design: Four hash tables model orders 5–8, extending effective context length beyond PPM’s order-4 limit.Each table aggregates matching positions into a full 256-value count distribution.
Contrast: The high-order model treats matching positions as an aggregated distribution rather than selecting one matched byte as the match model does.This distinguishes its count-based prediction mechanism from long-range single-position matching.
Prediction: Highest-order-first fallback selects orders 8 through 5, using the first context with total count at least 4.This provides a count-based fallback rule for sparse high-order contexts.
Smoothing: Minimal smoothing of ϵ = 10^-4 preserves the sharp distributions that make high-order contexts useful.The model avoids PPM’s 0.5 prior strength for these higher-order predictions.
Separation from PPM: Fusing orders 5–8 into PPM’s fallback chain performed consistently worse than using the separate blended model.The paper attributes this design choice to the mismatch between PPMC exclusion and sparse high-order contexts.

3.7 Arithmetic Coder

Midicoth uses a standard 32-bit arithmetic coder with E1/E2/E3 renormalization and quantizes predicted probabilities into integer frequencies before coding. On alice29.txt, this quantization produced a measured negative overhead relative to theoretical model entropy.

Arithmetic coding: The coder uses 32-bit low, high, and value registers with E1/E2/E3 renormalization.It also uses a 14-bit frequency scale, minimum frequency 1 per symbol, and bit-packed byte output.
Frequency quantization: Predicted probabilities are quantized into integer frequencies before being passed to the arithmetic coder.The frequency scale is T = 16,384, with cumulative frequencies formed from symbol frequencies.
Frequency quantization: −985 bytes: 14-bit quantization produced negative overhead on alice29.txt relative to theoretical model entropy.The quantized output was 985 bytes smaller than the theoretical model entropy.
Frequency quantization: Rounding acts as mild regularization by smoothing noise in the probability estimates.This explanation is given for the observed negative overhead from quantization.

4. Experimental Setup

The evaluation uses a compact native C implementation tested on two text-compression datasets with single-core CPU timing. Results are compared with high-setting dictionary compressors and context-mixing systems, alongside referenced LLM-based results.

Implementation: Midicoth is implemented in approximately 2,000 lines of C with gcc -O3 -march=native and only libm.The implementation uses no external libraries, GPU, or pre-trained models.
Hardware and timing: All experiments run on a single Intel/AMD x86-64 CPU core, with timing measured using clock_gettime(CLOCK_MONOTONIC).The setup fixes execution to one core and specifies the monotonic timing source.
Datasets: Evaluation covers alice29.txt at 152,089 bytes and the first 100 MB of English Wikipedia from enwik8.alice29.txt is English literary text from the Canterbury Corpus, while enwik8 is part of the LTCB benchmark.
Baselines: Comparisons include gzip -9, xz -9, bzip2 -9, Brotli -q 11, Zstandard -19, PAQ8px, and CMIX v21.Referenced LLM-based results from ts_zip and Nacrith provide additional context and require pre-trained neural networks and GPU hardware.

5. Results

Midicoth improves compression across small and large text benchmarks, with gains arising from exclusion, auxiliary models, and post-blend Tweedie calibration. The denoiser’s corrections vary with data volume and confidence while successive steps reduce residual error.

Compression results: 2.119 bpb on alice29.txt, outperforming xz -9 (2.551 bpb) by 16.9%.It also outperforms Brotli (2.445 bpb) by 13.3% and bzip2 (2.273 bpb) by 6.8%.
Compression results: 1.753 bpb on enwik8, outperforming xz -9 (1.989 bpb) by 11.9% and all other dictionary-based compressors.The gap to PAQ, CMIX, and LLM-based compressors remains significant, while Midicoth uses no neural network, training data, or GPU.
Ablation study: PPMC exclusion sharply strengthens the base PPM model, achieving 28.06% ratio on alice29.txt and 28.18% on enwik8_3M.Without exclusion, the corresponding ratios are 60.23% and 46.93%; exclusion removes probability mass already assigned at higher orders.
Ablation study: The match model contributes 5.6% on enwik8_3M, while the word and high-order context models together add 2–3.5% across all files.The match model’s benefit scales with repetitiveness and file size; the word model contributes 0.6–1.1% and orders 5–8 contribute 1.3–2.5%.
Ablation study: 2.6–2.8% is added by post-blend Tweedie across both datasets, exceeding the 1.2–1.6% from applying it before blending.Applied after blending, it calibrates systematic biases in the complete ensemble rather than only the PPM output.
Scaling and denoising behavior: ∼60 KB/s throughput remains consistent across input sizes while compression ratios improve on larger inputs.The correction magnitudes also adapt to data volume: alice29 corrections decrease with confidence, whereas enwik8_3M permits larger high-confidence corrections; later denoising steps are ∼4−6× smaller than step 0.

6. Discussion

Midicoth’s micro-diffusion layer corrects prior-induced and ensemble-wide probability biases through binary, multi-step calibration. The discussion also identifies performance trade-offs across data types, model complexity, and file sizes.

Micro-diffusion calibration: Binary tree calibration requires less data than calibrating a 256-way distribution and distinguishes different byte-range regimes through enriched bit contexts.The 27 contexts encode tree level and parent path while maintaining enough observations per bin for correction estimates.
Model-design trade-offs: All five evaluated extensions worsened compression on every tested file, while count-based components avoided the overfitting risk of gradient-based learners.The tested extensions included logistic mixing, SSE, soft match distributions, bit-level APM processing, and recency weighting.
Comparative performance: Midicoth reaches 1.753 bpb on enwik8 but remains behind PAQ at 1.27 bpb, CMIX at 1.17 bpb, and Nacrith at 0.939 bpb.Those systems use richer bit-level, context-mixing, or pre-trained transformer models.
Limitations: On very small files below 50 KB, fewer observations and pipeline overhead may reduce Midicoth’s advantage; binary data also receives limited benefit from its text-oriented models.The discussion additionally notes limits from PPM context order and single-threaded processing.

7. Conclusion

Midicoth combines multi-step Tweedie denoising with binary-tree calibration as a final correction stage for adaptive statistical compression. The five-layer system improves compression on both tested datasets without neural networks, training data, or GPUs.

Contribution: Midicoth treats PPM predictions as Jeffreys-prior-corrupted observations and applies a nonparametric Tweedie correction conditioned on noise level.The correction is computed from calibration tables as an estimate of the optimal additive adjustment.
Contribution: The post-blend denoiser reduces compressed size by 2.3–2.7% across all tested datasets and can process probability distributions from other context-model ensembles.Applying it after blending calibrates the complete ensemble output rather than only the PPM base model.
Contribution: Binary-tree decomposition with 27 enriched bit contexts enables data-efficient calibration from 152 KB files to 100 MB files.The contexts encode tree level and parent path to distinguish qualitatively different byte ranges.
Results: 1.753 bpb on enwik8 and 2.119 bpb on alice29.txt outperform xz -9 by 11.9% and 16.9%, respectively, without neural networks, training data, or GPUs.The full pipeline uses adaptive statistical models only.
Implementation: The implementation is approximately 2,000 lines of C, runs at approximately 60 KB/s on one CPU core, and is open-source.It has no external dependencies and is fully deterministic with bit-exact encoder–decoder symmetry.