# Shannonic: Efficient Entropy-Optimal Compression for ML Workloads > [!info] Talk metadata > - **会議:** [[MLSys2026]] Day 3 (May 20 / Wed)、Grand Ballroom 2、17:15 - 17:30 PDT > - **セッション名:** Research Track Oral -- Model Compression > - **登壇者:** Kareem Ibrahim (University of Toronto) > - **URL:** https://mlsys.org/virtual/2026/oral/3820 > - **OpenReview:** https://openreview.net/forum?id=NhMxI0GbB8 > - **共著者:** Kareem Ibrahim$^{1}$, Mohammadjavad Maheronnaghsh$^{1}$, Andreas Moshovos$^{1,2}$（$^{1}$University of Toronto, $^{2}$Vector Institute） > [!abstract] 概要（論文アブストラクトの忠実な日本語訳） > Shannonic は、機械学習テンソル向けのロスレス圧縮手法であり、エントロピー最適に近い圧縮、最小限の状態フットプリント、高スループットを達成する。Shannonic はオフラインの前処理ステップにより、テンソルの値空間を最適に選択された部分レンジに分割し、各値を (range index, offset) ペアとしてエンコードする符号化・復号テーブルを生成する。レンジは Asymmetric Numeral Systems (ANS) によるエントロピー符号化で圧縮される。Shannonic が標準 ANS より高い圧縮効率を達成することを形式的に証明し実証する。各種の 8 ビット量子化モデルにおいて、Shannonic のコーデックはわずか 530 B の状態で、シャノン限界の 1% 以内の符号化効率を達成する。連合学習では 1.3--3.1 倍の高速化、エッジ・クラウド LLM 推論では 29--32% のレイテンシ削減を実現する。 ## 問題設定: ML ワークロードにおけるデータ移動ボトルネック - 現代の ML デプロイメントは、単一ノード実行から、推論・継続学習・連合学習を含む分散実行へ移行している。GPU・CPU メモリ・SSD・リモートメモリ階層といった異種リソース間でのデータ移動が、帯域幅・レイテンシ・コストの各面で支配的なボトルネックとなっている（論文 1 節）。 - 具体的な 3 つのユースケースが挙げられている。(1) デバイス横断の連合学習では、帯域制約リンクを介した頻繁なモデル更新交換が訓練レイテンシとエネルギーに大きく影響する。(2) エッジ・クラウド分割 LLM 推論では、帯域制限ネットワーク越しのアクティベーション連続転送が通信をレイテンシの主因にする。(3) FlexGen のようなマルチティアメモリ仮想化システムでは、メモリ階層間の動的なデータストリーミングのコストが実行時間を支配する（論文 1 節）。 - ピーク計算性能は 2 年ごとに約 3 倍向上する一方、DRAM とインターコネクトの帯域はそれぞれ 1.6 倍と 1.4 倍の成長にとどまっている。Wang et al. (2020) は、多くの ML ワークロードが計算需要ではなくメモリ帯域と通信オーバーヘッドに律速されることを複数プラットフォームで実証している（論文 2 節）。 ## 量子化だけでは不十分: ロスレス圧縮の必要性 - 量子化はデータ量削減の主要手段だが、本質的にモデルサイズと品質のトレードオフを伴う非可逆手法である。キャリブレーションや適応が必要で、連合学習やオンデバイス継続適応のような動的環境では非実用的な場合がある（論文 1 節）。 - 実用パイプラインでは混合精度が一般的で、重みは 4 ビットまで圧縮可能でもアクティベーションやスケーリングメタデータはより高い精度を維持する。全レイヤを 8 ビット未満に量子化すると複雑タスクで大きな精度劣化が生じうる（論文 2 節、5.3 節）。 - 積極的な量子化後も、離散テンソルには非一様なシンボル統計に起因する冗長性が残存する。ロスレス圧縮はこの残存冗長性を精度無劣化で除去できる、量子化の補完的手法として位置づけられる（論文 1 節）。 ## 既存手法の課題: 汎用ロスレス圧縮はオーバーヘッドが大きい - 最も効果的な汎用ロスレス手法（Deflate、LZMA 等）は数十 KB--数 MB のルックアップテーブルと、スライディングウィンドウや大辞書などの大きな履歴状態を必要とする。これは ML デプロイメントのリアルタイム要件と合致しない（論文 1 節）。 - ハフマン符号化はシンボル確率が 2 のべき乗でない場合に非効率であり、量子化ニューラルネットワークテンソルの分数ビット長に近づけない（論文 3 節）。 - 標準 Tabled ANS (tANS) はシャノン限界に近い圧縮を達成するが、8 ビットシンボル（$N = 256$）で量子化損失 1% 以下を保つには $L \geq 4N$ 個の状態が必要で、4--16 kB のテーブルサイズとなる。この大きなテーブルは L1 キャッシュに収まらず、キャッシュミスがシンボルあたりの処理時間を支配する。また、並列ストリームはテーブル複製を要しコストをさらに増大させる（論文 3 節）。 ## Shannonic のアプローチ: レンジ分割 + ANS Shannonic は 2 階層の符号化スキームで tANS のテーブルサイズを桁違いに削減する。テンソルの値空間を $K$ 個の連続レンジに分割し、各値を (range index, offset) ペアとしてエンコードする。 ### 理論的基盤: Theorem 1（論文 4 節） - 確率分布 $\{p_i\}_{i=1}^{N}$ を持つ $N$ 個のシンボルに対し、$L$ 状態の標準 tANS の平均符号長は $CL_{\text{tANS}} = H(p) + D_{\text{KL}}(p \| q_{\text{tANS}})$ である。ここで $D_{\text{KL}}$ は離散状態割当 $q_i = f_i / L$ による量子化損失を定量する。 - Shannonic はアルファベットを $K$ 個のレンジ $\{\mathcal{R}_k\}$ に分割し、レンジ確率 $P_k = \sum_{i \in \mathcal{R}_k} p_i$ で tANS を適用する。平均符号長は $CL_{\text{Shannonic}} = H(P) + D_{\text{KL}}(P \| Q) + \sum_k P_k w_k$ となる。右辺第 3 項はオフセットビットのオーバーヘッドで $w_k = \lceil \log_2 |\mathcal{R}_k| \rceil$ である。 - Shannonic が tANS より低レートになる条件（Condition 3）: $D_{\text{KL}}(p \| q_{\text{tANS}}) - D_{\text{KL}}(P \| Q) > \sum_k P_k w_k - H(p|P)$。直感的には、少数のレンジへシンボルを統合することで量子化損失が減少し、その改善がオフセットビットのペナルティを上回るとき分割が有利となる。 - **実験的検証:** Llama-3.1-8B の `layers.16.self_attn.k_proj.weight`（4.2M INT8 値、$H(X) = 5.307$ bits/symbol）で、標準 tANS ($L = 1024$) は 5.592 bits/symbol だが、Shannonic ($K = 16, L = 128$) は 5.336 bits/symbol を達成する。量子化損失が 0.285 から 0.013 bits へ減少し、オフセットコストはわずか 0.017 bits である（論文 4 節）。 ### 前処理: 動的計画法によるレンジ選択（論文 4.1 節） - 入力テンソルのヒストグラム $h[x]$ を計算し、256 シンボルのアルファベット $[0, 255]$ を $K = 16$ 個の連続レンジに分割する最適化を動的計画法で解く。レンジ識別子の ANS 符号化コストとレンジ内オフセットの固定幅符号化コストの合計を最小化する。 - 最適分割は漸化式 $C[i, k] = \min_{j < i}\{C[j, k-1] + \text{Cost}(j, i-1)\}$ で求まる。$C[256, 16]$ からバックトラックして 16 個の最適レンジ境界を得る。 - 各レンジ $k$ に対し、`base[k]`（レンジ内最小値）、`nb[k]`（オフセットビット数）、`start[k]`（encTable 内の開始インデックス）、`bias[k]`（状態正規化用バイアス）を事前計算する。さらに各値をレンジインデックスにマップする `rangeId[256]` と、128 エントリの tANS テーブルをレンジ確率 $p_k = N_k / N$ から構築する（論文 4.1 節）。 ### 実行時符号化・復号（論文 4.2 節、Algorithm 2） - **符号化:** 各値 $x \in [0, 255]$ を定数時間で処理する。(1) `rangeId[x]` でレンジ識別子 $s$ を取得、(2) オフセット $o = x - \text{base}[s]$ を `nb[s]` ビットで出力、(3) 状態正規化のためのビット出力、(4) `encTable` 参照で状態遷移。全操作はテーブル参照・シフト・マスク・加算のみで、除算や乗算は不要。 - **復号:** 逆操作として状態 $X$ から `decTable[X]` でシンボル $s$ とビット数を取得し、オフセット $o$ を読み込んで $x = \text{base}[s] + o$ を復元する。 - 符号化・復号パスともに分岐なしで、クリティカルパス上に除算・乗算がない。これにより効率的なソフトウェアベクトル化とハードウェア実装が可能となる。 ### コーデック状態フットプリント（論文 4.1 節、Appendix A） - 選択された構成 $K = 16, L = 128$ で、符号化・復号テーブルを合わせたコーデック状態はわずか **530 B**。これは標準 tANS（$L = 1024$--$2048$, 4--6.7 kB）の **8--16 倍小さい**。 - 0.53 kB のワーキングセットは L1 キャッシュに完全に収まるため、シンボル処理がキャッシュミス誘発のメモリアクセスではなくテーブル参照と整数シフトで完結する。 ## 評価: 圧縮率（論文 5 節、Table 1、Figure 3） - ビジョン（MobileNetV3、ResNet-18/50、ShuffleNetV2、EfficientNet-V2）、NLP（BERT-WNLI、GPT-2）、LLM（Qwen2.5-7B-Instruct、Gemma-2-9B、Mistral-7B-Instruct、Llama-3.1-8B-Instruct）の各モデルで評価。ビジョン・BERT モデルの重みは公開 INT8 チェックポイントから取得、LLM は SmoothQuant の W8A8 設定を適用。アクティベーションは PyTorch フック経由で 10 サンプル入力から層ごとに記録。 - 全モデル・全テンソルにわたり、Shannonic はシャノン限界の 1% 以内で圧縮を達成する（$\% \text{diff} = (RP - H) / H \times 100$、RP は Shannonic の平均ビット数）。 - **CSR（圧縮サイズ比）** はアクティベーションで 0.39--0.69、重み・エンベディングで 0.49--0.85 の範囲。スパースモデル（ShuffleNetV2、EfficientNet-V2）では頻出ゼロ値が確率質量を集中させ、Shannonic が自然にスパース性の恩恵を受ける。 - Figure 3 の比較で、Shannonic は EBPC、Atalanta、Deflate、LZMA を重み・アクティベーションの両方で上回り、汎用圧縮手法（Deflate、LZMA）は ML テンソルに対しシャノン限界を超える圧縮を達成しない。 ## 前処理オーバーヘッド（論文 5.1 節、Table 2） - 前処理（ヒストグラム計算、16-way レンジ選択、状態テーブル構築）は Intel i9-10920X / 4 スレッドで計測。 - ResNet-50 の重み（51 MB）は 0.052 秒、Gemma-2-9B の重み（8.7 GB）は 15.4 秒。最大ワークロードでも 4 スレッドで完了し、Llama-3.1-8B の重みは 8 スレッドで 4.71 倍、16 スレッドで 5.67 倍に高速化する。 - 推論ではデプロイメント期間全体で 1 回のみのコストとして償却される。訓練では分布シフトに追従するためテーブルを定期的に再生成するが、連合学習（6.1 節）のラウンドごと再生成でも全体に対し無視できるオーバーヘッドである。 ## コーデック状態と圧縮のトレードオフ（論文 5.2 節、Figure 1） - Llama-3.1-8B のアクティベーションで、コーデック状態フットプリント対 CSR を体系的に分析。シャノン限界は CSR = 0.689、1% 超過閾値は 0.696。 - 標準 tANS ($L \in \{512, 1024, 2048\}$) は 0.696--0.743 の CSR を達成するが 1.4--6.7 kB の状態を要する。Shannonic ($K = 16, L = 128$) は 0.693 の CSR をわずか 0.53 kB で達成する（シャノン限界の 0.6% 以内）。 - 比較可能な圧縮率（0.696）の標準 tANS ($L = 2048$) に対し、状態量は **12.6 倍少ない**（0.53 vs 6.7 kB）。 ## 量子化との相互作用（論文 5.3 節、Table 3） - Qwen3-8B 上で MMLU（汎用知識）、WikiText-2（言語パープレキシティ）、HumanEval（コード生成）の 3 ベンチマークを用いて、量子化と Shannonic の組み合わせを評価。 - **INT8 + Shannonic（INT8+RP）:** MMLU 73.98%、WikiText-2 PPL 12.92、HumanEval pass@1 0.76 で、INT8 単体と同一の品質を維持しつつ、4.38 bits/weight を達成。これは INT4 のグループワイズ量子化（$g = 64$ で 4.50 bits/weight、$g = 32$ で 5.00 bits/weight）をフットプリントと精度の両面で実効的に上回る。 - **INT4 + Shannonic（INT4+RP）:** 4.24 bits/weight で、INT4 単体（4.50 bits/weight）からさらに 6% のフットプリント削減。エントロピー限界付近を維持。 - INT8 + Shannonic は量子化に対する補完的アプローチとして位置づけられる。INT8 はテンソル単位の量子化であり INT4 のようにグループごとのスケール・ゼロポイント計算を実行前に必要としないため、計算パイプラインの点でも有利である。 ## ユースケース 1: 連合学習（論文 6.1 節、Table 4） - FedML フレームワークに統合し、ResNet-18（11M パラメータ）で評価。8 ビット量子化の重み更新を Shannonic で圧縮し、アップリンクのみ圧縮する。ダウンリンクは標準伝送。テーブルはラウンドごとに集約モデルヒストグラムから再生成されるが、所要時間 0.052 秒はラウンド全体に対し無視できる。 - **圧縮結果（Table 4）:** CIFAR-10 / 100 クライアントで CSR = 0.297（2.3--3.3 倍の帯域削減）、1000 クライアントで CSR = 0.640。CIFAR-100 / 100 クライアントで CSR = 0.435、1000 クライアントで CSR = 0.667。1000 クライアントシナリオの CSR 悪化は、大母集団でのデータ異質性（個別クライアント更新がグローバルモデル統計から乖離）に起因する。 - ロスレスであるため、モデル品質は非圧縮 FedAvg と同一（精度・収束軌道に影響なし）。全圧縮率はシャノン限界の 1% 以内。 ### 無線エッジデバイスでの展開分析（論文 6.1 節） - エッジデバイスのスループットは Raspberry Pi 5（ARM Cortex-A76, 2.4 GHz）を代表として使用: 168 MB/s 符号化、286 MB/s 復号。サーバ側復号は 640 MB/s。 - **WiFi (802.11ac, 100 Mbps):** 非圧縮で 11 MB 更新に 0.88 秒。CSR = 0.297 で 0.34 秒（2.6 倍高速化）、CSR = 0.667 で 0.67 秒（1.3 倍高速化）。圧縮・伝送・復号の内訳は 0.07 + 0.27 + 0.01 秒。 - **LTE (22.5 Mbps):** 非圧縮で 3.9 秒。CSR = 0.297 で 1.24 秒（3.1 倍高速化）、CSR = 0.667 で 2.69 秒（1.5 倍高速化）。バッテリー制約デバイスでは CSR = 0.297 で $(3.9 - 1.16) \times 0.15 = 0.41$ J の送信エネルギー節約に対し、符号化オーバーヘッドはわずか $0.07 \times 0.75 = 0.05$ J。 - 総括すると、Shannonic は連合学習の通信レイテンシを **1.3--3.1 倍削減**し、モデル収束に影響を与えずエネルギー節約も提供する。 ## ユースケース 2: エッジ・クラウド LLM 推論（論文 6.2 節、Table 5） - EdgeShard のエッジ・クラウド分割構成（Llama2-7B を 32 GB Jetson AGX Orin と RTX 3090 間で分割）に Shannonic を統合。自己回帰生成ではトークンごとにアクティベーションがネットワーク越しに転送される。8 ビット量子化でトークンあたり約 4 KB のアクティベーションテンソルが生成され、CSR $\approx$ 0.69 に圧縮される（Table 1）。 - Jetson AGX Orin の ARM Cortex-A78AE で Shannonic 符号化を実行し、Raspberry Pi 5 の ARM Cortex-A76 性能（168 MB/s 符号化、286 MB/s 復号）をプロキシとして使用。クラウド側復号は 640 MB/s。 - **レイテンシ分析（Table 5）:** 100 トークン生成の転送レイテンシについて: - 50 Mbps: ベースライン 66 ms → Shannonic 適用で 47 ms（**29% 削減**、19 ms 節約） - 10 Mbps: ベースライン 224 ms → Shannonic 適用で 330 ms（**32% 削減**、106 ms 節約） - コーデックオーバーヘッドはトークンあたり符号化 0.024 ms + 復号 0.006 ms = 計 3 ms / 100 トークンで無視できる水準。 ## ソフトウェア・ハードウェア実装（論文 4.2 節、Appendix B・C） ### ソフトウェア実装 - C++ で実装。Raspberry Pi 5 (ARM Cortex-A76, 2.4 GHz) でシングルストリーム 168 MB/s 符号化・286 MB/s 復号、4 スレッドで 669 MB/s 符号化・1.14 GB/s 復号。Intel i9-10920X (3.50 GHz) でシングルストリーム 300 MB/s 符号化・640 MB/s 復号、4 スレッドで 1.08 GB/s 符号化・2.30 GB/s 復号、24 スレッドで 4.74 GB/s 符号化・9.76 GB/s 復号。 ### ハードウェア合成 - 7nm ASAP7 PDK で Shannonic エンコーダ・デコーダを合成。エンコーダは面積 279 $\mu$m$^2$、消費電力 0.79 mW、スループット 1.97 GB/s。デコーダは面積 267 $\mu$m$^2$、消費電力 1.08 mW、スループット 1.55 GB/s。コンパクトな面積・低消費電力により、高スループットアプリケーション向けの複数並列インスタンス配置が可能。 ## 圧縮が有利になる条件（論文 6 節） - 送信者が $S$ バイトを CSR で圧縮し、帯域 $R_\text{link}$ で転送し、受信者が復号するパイプラインをモデル化。1 バイトあたりの所要時間は $t_\text{compressed} = 1/R_\text{enc} + CSR/R_\text{link} + 1/R_\text{dec}$ である。 - **レイテンシ条件:** $CSR < 1 - R_\text{link}(1/R_\text{enc} + 1/R_\text{dec})$。リンク帯域が符号化・復号スループットに対して小さいとき圧縮が有利となる。 - **エネルギー条件:** $CSR < 1 - (P_\text{Shannonic} \cdot R_\text{link}) / (P_\text{tx} \cdot R_\text{enc})$。モバイルデバイスの無線送信電力 $P_\text{tx}$ は数百 mW--数 W だが、CPU コアの Shannonic 処理電力 $P_\text{Shannonic}$ は同等以下であるため、帯域制約環境でレイテンシ・エネルギーの両面で圧縮が有利となる。 ## 貢献のまとめ 1. **軽量エントロピー符号化アルゴリズム:** レンジ分割が直接符号化を上回る形式的条件（Theorem 1）を定立。IoT スケールから LLM まで多様なモデルで、シャノン限界の 1% 以内の圧縮をわずか 530 B の状態で達成する。 2. **実システム検証:** 連合学習で 1.3--3.1 倍の通信高速化、エッジ・クラウド LLM 推論で 29--32% のレイテンシ削減を、モデル品質を一切損なわずに実現する。 3. **効率的実装:** ソフトウェア（マルチスレッドスケーリング）とハードウェア（7nm 合成で 1.55--1.97 GB/s）の双方で高スループットを実証。標準 tANS と比べ 8--16 倍少ない状態量でありながら同等以上の圧縮効率を達成し、L1 キャッシュに収まるワーキングセットによりスループットが大幅に向上する。 ## 関連研究との位置づけ - **量子化との関係:** Shannonic は量子化の代替ではなく補完である。INT8 + Shannonic は INT4 グループワイズ量子化をフットプリントと精度の両面で上回りうる（Table 3）。 - **Atalanta (Delmas Lascorz et al., 2024):** 同じく (range, offset) 表現を用いるが、レンジインデックスに算術符号化を使い、値あたり 16 回の 16-bit 乗算・16 回の 20-bit 比較・アンダーフロー/オーバーフロー処理を要する。状態量は 50 B と少ないが演算コストが高い。Shannonic はわずかに多い状態（530 B）でより高い圧縮を達成しつつ、演算は単純なテーブル参照・シフト・加算のみで、ソフトウェア・ハードウェア実装が容易である。 - **EBPC (Cavigelli et al., 2019):** デルタ・ビットプレーン XOR 変換 + ランレングス符号化。単純だが Shannonic はより高い圧縮を達成する（Figure 3）。 - **汎用圧縮（Deflate, LZMA）:** オフライン保存・転送に最適化されており、32 kB+ のスライディングウィンドウや大辞書に依存する。ML テンソルに対しては Shannonic を下回る（Figure 3）。