StateSMix：基于 Mamba 状态空间模型与稀疏 n 元上下文混合的在线无损压缩 StateSMix: Online Lossless Compression via Mamba State Space Models and Sparse N-gram Context Mixing
纯 CPU 在线训练 Mamba SSM + 稀疏 n 元混合的自包含无损压缩器。
前置知识
状态空间模型与 Mamba (SSM)
状态空间模型是序列动力学系统 $h'(t)=Ah+Bx,\ y=Ch+Dx$，离散化为 $h_i=\bar A h_{i-1}+\bar B x_i$。Mamba 进一步令 $B,C,\Delta$ 随输入变化，实现选择性遗忘，获得线性 $O(N)$ 推理与紧凑循环状态。
StateSMix 的整个预测核心是 2 层 Mamba（$D_M=32, N_L=2$，约 120K 有效参数）。要理解它在压缩中为何能击败 xz、为何对每个 token 都要重算 head projection $W \in \mathbb{R}^{v_e \times D_M}$，必须先理解 SSM 的循环状态大小（$2 \times 64 \times 16 = 2048$ floats）以及反向传播的代价分布。
算术编码 (Arithmetic Coding) 与交叉熵等价性
算术编码用 $q(t_i\mid t_{<i})$ 逐 token 收缩区间，输出长度恰为 $\sum_i-\log_2 q(t_i\mid t_{<i})$，等于真实分布与预测器的交叉熵。编/解码器每步必须用真实 token 更新才能对齐。
StateSMix 的所有混合设计（包括稀疏 logit-bias、熵自适应缩放）目的都是降低 $-\log_2 q(t_i\mid t_{<i})$ 这一项。要理解为何 SSM 必须与解码器共享相同的状态、为何模型在线训练后会被"烘进"比特流而无须显式传权重，必须先理解这一等价的双向性。
在线学习与遗憾界 (Regret)
在线学习器先输出 $q_i$ 再以真实标签更新；$N$ 步 regret 为 $R_N=\sum_i -\log q_i(t_i)-\min_q\sum_i -\log q(t_i)$。SGD/Adam 在 chunk 上做随机梯度下降即为实用在线算法。
StateSMix 用长度为 $C=32$ 的 chunk 调度 Adam，把 $\eta=0.002,\ G_\text{clip}=5$ 等参数被显式写到 Algorithm 1 中。要理解为何能做"自包含压缩"（无需预训练权重）以及为何前若干 chunk 要走更多迭代（warm-up），必须把优化过程理解为在线 regret 最小化而非离线训练。
n 元语言模型与稀疏计数 (n-gram with sparse counts)
n-gram 假定 $t_i$ 只与前 $n-1$ 个 token 有关。稀疏计数表只存 (context, continuation, count) 三元组；冲突用开放寻址 + 线性探测解决；PPM 在未见高阶上下文时回退到低阶。
论文的"sparse n-gram context mixing"与"softmax-invariant logit bias"两个核心贡献都建立在这个基础上。要看懂为何可以用 $\delta_j = \lambda \log(1+c_j/\alpha)$ 这样的纯加性扰动直接注入 SSM 的 logits、为何哈希表里只存 $c_j>0$ 的条目就够用，必须先熟悉 softmax 平移不变性与 open-address 哈希。
BPE 分词与紧凑词表重映射
BPE 把可变长字节合并为 $V$ 个 subword token（GPT-NeoX $V=49{,}152$）。由于单文件实际只出现 $v_e\ll V$ 种，可以构造 $\phi:[0,v_e)\to[0,V)$ 双射，把所有矩阵运算缩减到 $v_e$ 维。
StateSMix 报告 $v_e=18{,}058\!\sim\!44{,}298$，把 head projection 从 $V\cdot D_M$ 降到 $v_e\cdot D_M$，节省 10-63% 计算，并使 softmax/Adam 更新只触及"本文件中出现过的 token"。理解这一点对读懂"为何 SSM 训练 75% 时间在 head matmul"的 profile 至关重要。
研究动机
无损压缩长期面临"小但弱、强但依赖外部权重"的两难。xz (LZMA2) 在 enwik8 上仅 1.989 bpb，明显被神经网络超越；NNCP 等在线神经压缩器却要把 Transformer-XL 的 ~10 MB 权重塞进压缩包头，使短文件反噬到 ~3.96 bpb。Chinchilla 70B、FineZip (LLaMA-3-8B)、ts_zip (RWKV-169M)、Nacrith (SmolLM2+mixing, 135M) 等 LLM 压缩器在 enwik8 上达到 0.939–1.024 bpb，却需事先共享数百 MB 至数十 GB 预训练权重并依赖 GPU 推理，既不便携也不即时可用。另一端 CMIX (1.17 bpb) 需 16–64 GB RAM 与 <1 KB/s 吞吐；gzip (2.916 bpb)、bzip2 (2.321 bpb) 又远落后 LZMA2。中间存在明显空缺：没有 GPU、没有预训练模型、没有几十 GB 内存，能否让压缩器在 1–10 MB 自然语言文件上比 xz 还好？
本文的目标是StateSMix 的目标非常具体：（1）完全 self-contained——压缩包只含原始文本经过的比特流，模型本身（120K 个 SSM 参数 + n-gram 表）从零开始在线训练，并不被传出去；（2）零外部依赖——纯 C + AVX2 SIMD，gcc -O3 一行编译，无 Python、无 CUDA、无 BLAS；（3）要在 enwik8 10 MB 子集上做到 2.162 bpb，比 xz -9e (2.177 bpb) 还好 0.7%；在 1 MB 子集上比 xz 省 8.7%；在 100 MB 上拿到 2.130 bpb 的合理 baseline；（4）通过 ablation 证明 SSM 是主要贡献者（独自贡献 46.6% 体积下降），n-gram 只是补充。这些目标共同支撑一个新假设："小而在线"可以是与"大且预训练"并行的第三种无损压缩范式，而非二选一。
与已有工作不同的是，本文最关键的切入角度是把"在线训练"与"Mamba 的线性时间推理"配对。在 NNCP (Transformer-XL) 路线上，每个 token 都要反向传播过一个深 transformer，单核 CPU 跑不动；在 LLM 路线上，权重巨大且需要 GPU。StateSMix 第一次把 input-dependent 的选择性 SSM 装进压缩器，把每个 token 的训练代价控制到 ~120K 参数的纯 C 实现；同时利用"算术编码的预测-更新耦合"把模型参数"烧进"比特流，避免任何形式的模型外传。再加上 softmax 平移不变性 + 稀疏 logit-bias，把传统 n-gram 表从"稠密概率向量"压缩为"只存非零计数的小整数 + 一个 λ,α 控制量"，使得 2-gram 至 32-gram 全套表格加起来还能放在约 5 GB 哈希表内。这一组合（在线 Mamba + 稀疏 n-gram + 算术编码 + BPE 重映射）才是本文的真正新颖之处——单看任何一项都是已有技术，但把它们按"自包含 + 纯 CPU"这条主线编排在一起是第一次。
核心方法
直觉是"预测即压缩"：下一 token 概率越准，算术编码输出越短。巧妙在于让模型对当前文件足够准——不用预训练大模型，而是边压边训。技术路线分四段：（A）原始字节经 GPT-NeoX BPE（V=49,152）切成 token，构造只含真实出现 token 的紧凑词表，把全流程计算从 49,152 降到 $v_e \approx 18K-44K$；（B）每 token 进 2 层 Mamba SSM（$D_M=32, D_S=16, D_I=64, N_L=2$）得 $\ell^\text{SSM}$；（C）查 9 张 n-gram 表（bi/trigram 至 32-gram）稀疏计数，仅给 $c_j>0$ 的 token 加 $\delta_j=\lambda\log(1+c_j/\alpha)$，叠 LZ/recency/frequency 偏置；（D）softmax + 32-bit 算术编码器写比特流；每 32 token 用 Adam 更新 SSM 固定参数与词表参数。系统未存任何"模型"——解压按同一颗种子重新初始化随机参数，再用同一动态解码即可。
核心是与已有工作三层本质区别。第一层：在线训练 Mamba 替换离线预训练 LLM。ts_zip/FineZip/Nacrith 共享百 MB 至数十 GB 预训练权重，比特流丢模型；StateSMix 反过来——模型从零生长不外传，借算术编码的"编/解码器必须以同一真实 token 更新"耦合关系自动重建模型。第二层：softmax-invariant sparse logit bias 取代稠密 n-gram 表。本文利用 softmax 平移不变性，把偏置 $\delta_j=\lambda\log(1+c_j/\alpha)$ 仅施加到 $c_j>0$ 的 token——效果等价于贝叶斯后验（log 空间加性更新），存储与计算均只与本表非零条目数成正比。第三层：熵自适应混合 $s=\text{clip}((1-\beta)+\beta H/H_0, 0.2, 2.5)$。SSM 高置信时 $s\to 0.2$，n-gram 几乎不扰动；冷启动 $s\to 2.5$，n-gram 接管。$\beta=0.6, H_0=5.5$ nats。
方法步骤详情
方法分四阶段。阶段一预编码：原始字节经 GPT-NeoX BPE 得 token（~3.3 bytes/token），扫描得 ve 种 token、构造双射 phi，Rice 码写出（enwik8 ~12 KB）。阶段二随机初始化：weight 采 N(0, 0.02^2)，log decay 几何分布；2-gram 直接数组，高阶 mix64 hash + 2^24 slots + 8 路线性探测。阶段三在线循环，对位置 i：(i) Mamba 前向得 logits；(ii) 查 9 张表各阶 delta^k + LZ/recency/frequency 偏置；(iii) 按 SSM 熵算缩放 s，s·delta^k 加到 logits；(iv) softmax + 32-bit 算术编码器输出；(v) i mod 32=0 时取 32 token 跑 Adam（warm-up：1-10 步 8 次、11-30 跑 4 次、31+ 跑 2 次；eta=0.002，截断 BPTT）；(vi) 写 ti 入所有 n-gram 表。阶段四收尾：算术 finish → 比特流。
技术新颖性
新颖性归纳五点。（1）首次将 input-dependent selective SSM 用于通用无损文本压缩，把 Mamba 的"长程线性 + 短程输入门控"与算术编码需求对齐；此前 S4/Mamba 仅用于分类与生成。（2）softmax-invariant sparse logit bias 把 n-gram 偏置从"稠密加权和"降到"稀疏常数 logits 加到几个非零位置"，并严格证明它是 SSM 先验 $\cdot$ n-gram 似然的 Bayes 后验——首次在压缩场景给出概率解释。（3）紧凑词表重映射把 head projection 的内存/计算省 10–63%，Rice 编码头部使 enwik8 100 MB 仅多 ~12 KB。（4）熵自适应缩放提供 analytical mixing weight，避开 PAQ 风格 logistic 二次混合器，参数小仍按上下文动态整合。（5）9 张表全用线性探测深度 8 + 64-bit 完整 key，30% load 下平均额外探测 ~0.21。
实验结果
主结果见 Table 4。StateSMix 在 ≤10 MB 上一致击败 xz -9e：1 MB 2.123 vs 2.326 bpb (-8.7%)；3 MB 2.149 vs 2.271 (-5.4%)；10 MB 2.162 vs 2.177 (-0.7%)；100 MB 反向 2.130 vs 1.992 (+6.9%)，crossover 约 30 MB。Ablation (Table 5) 最有力：仅 count 基线 1,571,738 B；加 n-gram 省 16.1%；单独 SSM 省 46.6% 并击败 xz 1.3%；完整系统再省 4.1%。三条结论：SSM 是主要贡献者；n-gram 无 SSM 时几乎无用；二者正交互补。Table 6：bpt 由 8.10→7.10 (50k)→6.90 (500k)→6.813。StateSMix 是唯一同时满足在线 + 无预训练 + 无 GPU + self-contained 四件套的系统。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| enwik8 1 MB 子集 | bits per byte (bpb, 越低越好) + 相对 xz 改善 | 2.123 bpb (265,370 字节) | xz -9e (LZMA2): 2.326 bpb | -8.7% (相对 xz 节省字节) |
| enwik8 3 MB 子集 | bpb | 2.149 bpb (805,926 字节) | xz -9e: 2.271 bpb | -5.4% |
| enwik8 10 MB 子集 | bpb | 2.162 bpb (2,702,498 字节) | xz -9e: 2.177 bpb | -0.7% |
| enwik8 100 MB 完整 | bpb | 2.130 bpb (26,622,640 字节) | xz -9e: 1.992 bpb; NNCP: ~1.19 bpb; CMIX: ~1.17 bpb; Nacrith (SmolLM2+mixing, 135M†): 0.939 bpb; FineZip (LLaMA-3-8B†): 1.024 bpb; ts_zip (RWKV-169M†): ~1.11 bpb | vs 经典 xz +6.9%；vs LLM-based 落后 0.8–1.2 bpb（参数少 100–600×） |
| enwik8 3 MB 消融：SSM 单独 vs n-gram 单独 vs Count-only | 字节数 + bpb + 相对 Full 系统改善 | SSM + count only: 840,095 B / 2.240 bpb (-4.2%); n-gram + count only: 1,319,045 B / 3.517 bpb (+63.6%); Count only: 1,571,738 B / 4.191 bpb (+95.0%); Full (all): 805,926 B / 2.149 bpb — | xz -9e: 851,572 B / 2.271 bpb (+5.7%) | SSM alone 已经击败 xz 1.3%；Full 进一步节省 4.1% over SSM alone |
| enwik8 100 MB 在线 bpt 演化 | bits per token (bpt, 模型内部分数) | 冷启动 ~8.10 → 50k token ~7.10 → 500k ~6.90 → 3M ~6.83 → 10M ~6.83 (plateau) → 29.7M 最终 6.813 | log2(v_e=44,298)≈15.4 (随机) / 6.83 (饱和) | 在线训练使模型 bpt 从 8.10 收敛到 6.79，节省 ~1.3 bpt |
| 系统吞吐 | tok/s 与 KB/s | 1 核: 1.1K tok/s (400 KB/s)；4 核 OpenMP+AVX2: 2.0K tok/s (700 KB/s)；100 MB 压完 ~4.2h | CMIX: <1 KB/s；PAQ8px: <1 KB/s；NNCP: ~1 KB/s；ts_zip/FineZip/Nacrith: 仅 GPU 可行 | 比 PAQ/CMIX/NNCP 快 100–700×，且仅 CPU 即可 |
局限与改进
作者明示三条局限：（1）速度——压 100 MB 要 4.2 小时，75% 时间花在 train_chunk，主要是 head projection 反向传播。OpenMP 4 核仅 1.9× 加速。（2）内存——9 张表占 5.1 GB 峰值 RAM（主要是 16/32-gram 的 16M slots），把 StateSMix 排除在嵌入式场景之外。（3）规模 crossover——一旦 >~30 MB，LZMA 的拷贝模式能零代价复制多 KB 重复模板。额外局限：100 MB 上 bpb 仍逊于 xz 1.4 百分点；当前只在 BPE token 之上工作，未验证原始字节/二进制；缺 adversarial / 非自然语言鲁棒性测试；端到端随机初始化导致 run-to-run 方差，未报告 seed-to-seed 稳定性。
独立分析的弱点
五条可独立改进的弱点。（A）Head projection 单点瓶颈——$v_e \approx 44K$ 个 32 维 dot product 在 100 MB 跑 ~30M 次，占 75% 训练时间。改进：WTA hash 替稀疏激活，或卸到 GPU。（B）哈希表失配——9 张表统一 $2^{24}=16M$ slots，high-order 表 load 因子 <30%。改进：分层动态扩容。（C）固定 $\lambda_k$ 不适应文件——bigram 0.15 与 8-gram 0.03 是 enwik8 sweep 选出。改进：PAQ 风格 per-order 自适应 logistic mixer。（D）缺 BWT/MTF 预处理——改进：BPE 后插 BWT+MTF，把 30 MB crossover 推到 100 MB。（E）随机 init 在小文件吃亏——1 MB 时 SSM 尚未 warm-up，冷启动 bpt ~8.1 拖后腿。改进：发布 reference codec file，预热几代后 fine-tune。
未来方向
作者列 5 条方向，未来可延伸。第一，BWT 预处理：BPE 后做 BWT+MTF，把 30 MB crossover 推到 100 MB 甚至更高。第二，GPU 加速：head projection、softmax、Adam 均 embarrassingly parallel，估算 50-100× 提速，让更大型 SSM 落地。第三，自适应 n-gram weighting：online exponential-weights meta-learner（PAQ 风格）替代固定 $\lambda_k$。第四，可变阶回退：longest-match + 置信度回退替代"所有阶求和"，避免高阶噪声被低阶放大。第五，杂交 predict-or-copy：检测 >K token 精确复读时切换 LZ-style (offset, length) 编码，有可能在 100 MB 上追平甚至超过 xz。第六，codec file 预训练：发布默认随机模板作为"compressor codec"，是 StateSMix 与 Nacrith 之间的桥梁。
复现评估
可复现性较好，硬件门槛低。代码完全开源：https://github.com/robtacconelli/StateSMix；纯 C + AVX2 SIMD，无 Python/CUDA/BLAS 依赖。编译一行 `gcc -O3 -march=native -mavx2 -mfma` 即可。数据公开：评测全在公开 enwik8 基准（Matt Mahoney）上，提供 1/3/10/100 MB 四 excerpt。算力门槛低：单核 AVX2 CPU 即可，全 100 MB 在 4 核上约 4.2 小时，内存峰值 6.1 GB——任何 8 GB 内存笔记本都能复现。难度主要在算法调试：9 张哈希表 + 2 层 Mamba + 算术编码 + 紧凑词表 + 偏置 + Adam 调度 是 ~3K 行 C 复杂工程，初学者易卡在 OpenMP 与 AVX2 内核；$\lambda, \alpha$ 与 $H_0=5.5, \beta=0.6$ 等超参明确给出，但作者告知是基于 enwik8 sweep，迁移其他领域可能需重新搜索。综合达到可复现等级。
论文图表
伪代码 13 行覆盖整个压缩流程：line 1 BPE(s)，line 2 BuildVocabMap & remap，line 3 init SSM θ + n-gram 表 + ArithEncoder，line 4-12 for i=1..N：SSMForward 取 ℓ，叠加 NgramBias(Eq.10)，softmax 后 encode $t_i$，每 32 chunk 调 SSMTrain (Adam, niter steps)，最后调 NgramUpdate。line 13 ArithEncoder.finish() 输出比特流。
Algorithm 1 是论文方法论的执行化版本——把 Sec 4.1 的 4 阶段抽象流程锚定到具体函数调用与控制流，便于实现者逐步对照；它的 modular 结构也是 Sec 4.7 Combined Logit Computation 与 Algorithm Description 的相互校验点