English Ver
Token Compression via Mixed-Radix Decomposition for Discrete Representation in Transformers
1. Introduction
Modern Transformer-based architectures often rely on large-scale discrete token vocabularies to represent semantic categories, especially in classification, action prediction, and reinforcement learning contexts. However, as the number of target classes increases (e.g., 360 directional actions), maintaining an equivalent number of tokens becomes computationally expensive and semantically inefficient.
This paper proposes a novel token compression framework based on mixed-radix decomposition. We demonstrate that a large number of discrete meanings (e.g., 360) can be compactly and bijectively represented by combinations of significantly fewer tokens (e.g., 38 tokens for 2D or 24 tokens for 3D decomposition). This results in up to 95% compression in token space without losing expressive power.
2. Related Work
- Tokenization Methods: WordPiece, SentencePiece, Byte Pair Encoding (BPE)
- Discrete Representation Learning: VQ-VAE, DALL·E Discrete Codes
- Mixed-Radix Number Systems: Used in encoding/decoding systems with unequal bases
- Action Space Decomposition: Hierarchical or structured reinforcement learning
3. Proposed Method
3.1 Overview
Given a target number of discrete meanings ( T ), our goal is to find a minimal set of token axes (dimensions) ( d ) and per-axis token sizes ( n_i ) such that:
[
T \leq \prod_{i=1}^{d} n_i
]
The total number of required tokens is:
[
\text{Total Tokens} = \sum_{i=1}^{d} n_i
]
We aim to minimize this sum.
3.2 Uniform Radix Decomposition
Let each axis have ( n ) tokens. We can use:
[
n = \lceil T^{1/d} \rceil \Rightarrow \text{Total Tokens} = d \times n
]
Example for ( T = 360 ):
- ( d = 2 \Rightarrow n = 19 \Rightarrow 38 ) tokens
- ( d = 3 \Rightarrow n = 8 \Rightarrow 24 ) tokens
3.3 Mixed-Radix Optimization
Instead of uniform ( n ), we find token counts ( n_1, n_2, ..., n_d ) such that their product is ( \geq T ) and their sum is minimized.
E.g., ( 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 360 \Rightarrow 17 ) tokens
This is a form of mixed-radix encoding where each axis has a different base.
3.4 Encoding & Decoding
We define:
- Encode: Map token indices ( (i_1, ..., i_d) ) to scalar index ( s \in [0, T) )
- Decode: Map ( s ) back to ( (i_1, ..., i_d) )
We implement this via positional weighting similar to numeral systems:
[
s = i_1 + i_2 n_1 + i_3 (n_1 n_2) + \cdots + i_d \prod_{j=1}^{d-1} n_j
]
4. Experiments
4.1 Setup
We simulate a Transformer tasked with predicting 360 discrete directions (e.g., R-stick actions in games).
We compare:
- Baseline: Flat 360-token softmax classifier
- Uniform 2D/3D Compression: 19x19 or 8x8x8 token combinations
- Mixed-Radix Token Heads: Token axes: [2,2,2,3,3,5]
4.2 Metrics
- Accuracy
- Token efficiency (tokens per class)
- Parameter count
- Inference latency
4.3 Results
| Method | Total Tokens | Accuracy | Inference Speed | Compression |
|---|---|---|---|---|
| 360 Flat Tokens | 360 | High | Slow | Baseline |
| 2D (19x19) | 38 | ~High | Fast | ~89.4% |
| 3D (8x8x8) | 24 | ~High | Very Fast | ~93.3% |
| Mixed-Radix [2,2,2,3,3,5] | 17 | ~High | Very Fast | ~95.3% |
5. Discussion
This method enables significant reductions in token count while preserving class distinction. The decomposed structure also opens pathways for interpretability and modularity in token usage.
Limitations include:
- Potential complexity in training heads to coordinate correctly
- Need for precise decoding logic
6. Conclusion
We propose a novel token compression scheme using mixed-radix decomposition to represent large discrete spaces efficiently. This method achieves significant compression while maintaining performance and enables modular, scalable token structures for future Transformer-based systems.
Appendix
- Python code for finding optimal decompositions
- Encoding/decoding examples
- Open-source implementation link (future work)
日本語バージョン
トークン圧縮のための混合基数分解によるTransformer離散表現の最適化
1. はじめに
近年のTransformerベースのモデルでは、大規模な離散トークンボキャブラリを用いることが一般的であり、特に分類・動作予測・強化学習の文脈においてその傾向は顕著です。しかし、たとえば360方向のような多数のカテゴリを扱う場合、それに対応するトークン数を維持することは計算負荷が高く、表現効率も低下します。
本研究では「混合基数分解」に基づいた新しいトークン圧縮手法を提案します。たとえば360個の離散的意味を、わずか38トークン（2次元分解）や24トークン（3次元分解）で一意に表現可能であることを示し、最大95%以上の圧縮を実現します。
2. 関連研究
- トークナイゼーション手法：WordPiece、SentencePiece、BPEなど
- 離散表現学習：VQ-VAE、DALL·Eのトークン化
- 混合基数表現：異なる基数を使う数値システム
- 行動空間の分解：階層型強化学習、構造的アクション分類
3. 提案手法
3.1 概要
離散表現数 ( T ) に対して、軸数（次元）( d )、および各軸ごとのトークン数 ( n_i ) を決定し、以下を満たすようにします：
[
T \leq \prod_{i=1}^{d} n_i
]
使用する総トークン数：
[
\text{Total Tokens} = \sum_{i=1}^{d} n_i
]
このトークン合計数を最小化することが目標です。
3.2 等基数分解
全軸に同じトークン数 ( n ) を割り当てた場合：
[
n = \lceil T^{1/d} \rceil \Rightarrow \text{Total Tokens} = d \times n
]
例：( T = 360 ) のとき
- ( d = 2 \Rightarrow n = 19 \Rightarrow 38 ) トークン
- ( d = 3 \Rightarrow n = 8 \Rightarrow 24 ) トークン
3.3 混合基数による最適化
軸ごとのトークン数 ( n_1, n_2, ..., n_d ) をバラバラに設定し、積が ( T ) 以上かつ和が最小になるような分解を探索。
例： ( 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 360 \Rightarrow 17 ) トークン
これは各軸が異なる基数を持つ「混合基数表現」として扱えます。
3.4 エンコードとデコード
- エンコード：( (i_1, ..., i_d) ) を整数スカラー ( s \in [0, T) ) に変換
- デコード：スカラー ( s ) を座標 ( (i_1, ..., i_d) ) に変換
これは混合基数的に以下で行えます：
[
s = i_1 + i_2 n_1 + i_3 (n_1 n_2) + \cdots + i_d \prod_{j=1}^{d-1} n_j
]
4. 実験
4.1 セットアップ
360方向（例：ゲームにおけるRスティック操作）を予測するTransformerモデルを用意。
比較対象：
- 通常方式：360クラスのsoftmax分類
- 2次元/3次元圧縮：19×19 や 8×8×8 の構成
- 混合基数：[2,2,2,3,3,5] のような構造
4.2 評価指標
- 精度（Accuracy）
- トークン効率（1クラスあたりトークン数）
- モデルパラメータ数
- 推論速度
4.3 結果
| 手法 | トークン数 | 精度 | 推論速度 | 圧縮率 |
|---|---|---|---|---|
| 360分類トークン | 360 | 高 | 遅い | 基準 |
| 2D（19×19） | 38 | 高 | 速い | 約89.4% |
| 3D（8×8×8） | 24 | 高 | 非常に速い | 約93.3% |
| 混合基数 [2,2,2,3,3,5] | 17 | 高 | 超高速 | 約95.3% |
5. 考察
この手法により、トークン数を大幅に削減しつつ、表現力を損なわずに意味のある圧縮が可能になります。また、各軸ごとに意味解釈可能な構造を持たせることで、解釈性や拡張性も高まります。
制限として：
- 各トークンヘッドの学習の調整が必要
- 正確なエンコード・デコードの設計が必要
6. 結論
本研究では、混合基数によるトークン分解という新たなトークン圧縮手法を提案しました。従来の360トークン表現を最大95%以上圧縮しながら、高精度な予測性能を維持できることを確認しました。将来的には、小型TransformerやエッジAI、操作空間の自動圧縮などへの応用も期待されます。
付録
- 最適な分解を探索するPythonコード
- エンコード/デコードの例
- OSS実装（準備中）
最適解を求めるPythonメソッド(総当り)
import math
from itertools import combinations_with_replacement
def find_min_sum_factorization(target: int):
"""
整数targetの積がtargetになるような自然数の組み合わせのうち、
要素の和が最小になるものを探索する。
Parameters:
target (int): 分解したい対象の整数
Returns:
tuple: (最小和, 組み合わせリスト)
"""
min_sum = float('inf')
best_combo = None
# 組み合わせの長さは 1～log2(target)+1 程度までで十分
max_factors = int(math.log2(target)) + 1
for r in range(1, max_factors + 1):
for combo in combinations_with_replacement(range(2, target + 1), r):
prod = math.prod(combo)
if prod == target:
s = sum(combo)
if s < min_sum:
min_sum = s
best_combo = combo
return min_sum, best_combo