Lookup Table (LUT) Methods for Mixed-Precision Matrix Computation

[5000user5000]

There are several ways to implement lookup tables for mixed-precision matrix operations:

1. Direct Mapping (Quantized Lookup)

   • Map a 4-bit quantized number into a 16-bit or 32-bit value.
   • Use it for 16×16 or 32×32 multiplication.
   • Simple but requires separate LUTs for different bit-widths.

2. Bitwise Decomposition (Bit-Serial Multiplication)

   • Source: T-MAC
   • Decomposes low-bit weights into bitwise components.
   • Uses precomputed LUTs indexed by bit patterns.
   • Avoids multiplications, but requires efficient memory management.

3. Vector Quantized LUT (VQ-LUT)

   • Source: MADDNESS, LUT-NN
   • Quantizes activations into representative vectors.
   • Precomputes multiplication results for these vectors.
   • Reduces computation but may introduce quantization error.

4. LUT Compression Techniques

   • Source: T-MAC, DeepGEMM
   • Mirror Consolidation: Stores only half of the LUT by exploiting symmetry.
   • Table Quantization: Compresses LUT values (e.g., FP16 → INT8).
   • Tiling & Reordering: Optimizes memory layout for faster lookup.

[5000user5000]

I am currently using method 1 to implement LUT on PR #18 — the Element-wise method or Direct Mapping method.
However, there's a slight difference: I don't map 4-bit values to 16-bit or higher.
Instead, my LUT stores all the precomputed int4 × int16 multiplication results, which are then used to perform GEMM.

[5000user5000]

In PR #32, the implementation has been revised to adopt a row-wise LUT regeneration approach instead of the original static element-wise mapping used in PR #18.

While the earlier version (PR #18) precomputed all INT4 × INT16 products and performed lookups directly using static (w, a) index pairs, the updated design dynamically rebuilds the LUT for each activation row during GEMM. This approach avoids storing large, fixed LUTs for all possible combinations and instead allows more efficient use of cache by reusing the activation row across an entire GEMM pass.

The main motivation for this change is to support mixed-precision inference with floating-point activations (e.g., FP16), where activation values are not quantized to a small integer range. Precomputing all possible INT4 × FP16 products is not feasible due to the high cardinality of FP16. The row-wise approach builds only the LUT needed for the current activation row, significantly reducing memory requirements and improving locality without sacrificing correctness.

This design also enables integration with tiling and multithreading strategies, making it suitable for more realistic inference scenarios.