Element-wise LUT

分类: 高效推理与部署

Element-wise LUT (ELUT)

一种 mpGEMM 范式，在权重元素级（而非比特级）分组预计算查找表，实现比 bit-wise LUT 更细粒度、更低 bpw 的矩阵乘推理

R = \sum_{i=1}^{K/g} \text{Lookup}(\text{eLUT}_i, W_i)

其中 eLUT 大小为 $C^g$ （ $C$ 为权重基数，如三值 $C=3$ ），group size $g$ 受 SIMD 寄存器宽度限制。

镜像合并后的实际 bpw（三值 TL2）：

\text{bpw} = \frac{\log_2(C^g / 2)}{g} = \frac{\log_2(3^3 / 2)}{3} \approx 1.67

vs MAD-based: 预计算开销 $O(NKC^g/g)$ ，但累加复杂度降至 $O(MNK/g)$ ，对大 $M$ 更高效

vs Bit-wise LUT: 粒度更细，可实现非整数 bpw（三值 1.67 vs bit-wise 的 2）

硬件约束: 受 SIMD 寄存器宽度限制（128-bit 最多 16 个 int8 槽），三值时最大 $g=3$ （13.5 < 16）

镜像合并: 观察到三值 eLUT 一半值与另一半互为相反数，合并后 LUT 大小 $3^3/2 \approx 14$ ，恰好可放入 16 槽寄存器

潜力尚未完全释放：更长 SIMD 寄存器（未来 CPU）可支持更大 $g$ ，进一步降低 bpw

Bitnet.cpp: 首个在三值 LLM 边缘推理中实现 ELUT 的系统，提出 TL1（g=2, bpw=2）和 TL2（g=3, bpw=1.67）