LUT Tensor Core: Lookup Table Enables Efficient Low-Bit LLM Inference Acceleration

Zhiwen Mo, Lei Wang, Jianyu Wei, Zhichen Zeng, Shijie Cao, Lingxiao Ma, Naifeng Jing, Ting Cao, Jilong Xue, Fan Yang, Mao YangarXiv 2024 · arXiv · OpenReview

Abstract

As large language model (LLM) inference demands ever-greater resources, there is a rapid growing trend of using low-bit weights to shrink memory usage and boost inference efficiency. However, these low-bit LLMs introduce the need for mixed-precision matrix multiplication (mpGEMM), which is a crucial yet under-explored operation that involves multiplying lower-precision weights with higher-precision activations. Unfortunately, current hardware does not natively support mpGEMM, resulting in indirect and inefficient dequantization-based implementations. To address the mpGEMM requirements in low-bit LLMs, we explored the lookup table (LUT)-based approach for mpGEMM. However, a conventional LUT implementation falls short of its potential. To fully harness the power of LUT-based mpGEMM, we introduce LUT Tensor Core, a software-hardware co-design optimized for low-bit LLM inference. Specifically, we introduce software-based operator fusion and table symmetrization techniques to optimize table precompute and table storage, respectively. Then, LUT Tensor Core proposes the hardware design featuring an elongated tiling shape design to enhance table reuse and a bit-serial design to support various precision combinations in mpGEMM. Moreover, we design an end-to-end compilation stack with new instructions for LUT-based mpGEMM, enabling efficient LLM compilation and optimizations. The evaluation on low-bit LLMs (e.g., BitNet, LLAMA) shows that LUT Tensor Core achieves more than a magnitude of improvements on both compute density and energy efficiency.

Introduction

The rapid scaling of Large Language Models (LLMs) has necessitated aggressive quantization techniques. Compressing model weights to 1, 2, or 4 bits significantly reduces memory footprints, but creates a challenge for execution. While weights are low-precision, activations typically remain in higher precision (e.g., FP16) to preserve model accuracy. This disparity necessitates mixed-precision General Matrix Multiplication (mpGEMM).

Current hardware architectures, such as NVIDIA's Tensor Cores, are optimized for uniform precision. Executing mpGEMM on these platforms requires "dequantizing" low-bit weights back into high precision before multiplication, a process that introduces significant latency and energy overhead. Lookup Tables (LUTs) offer a theoretically efficient alternative by replacing multiplications with table lookups, but traditional LUT implementations are often hampered by high precomputation costs and inefficient memory access patterns.

The LUT-based mpGEMM Mechanism

The core idea of LUT-based mpGEMM is to precompute all possible partial products of a high-precision activation vector and a low-bit weight vector. For instance, with 4-bit weights, there are only 16 possible values for each weight element. By precomputing the products of these 16 values with the activation, the matrix multiplication is reduced to a series of table lookups and additions.

Illustration of LUT-based mixed-precision GEMM (mpGEMM) where activations are precomputed into a lookup table indexed by low-bit weights.

As shown in Figure 2, the activation vector is used to generate a Lookup Table (LUT). The low-bit weights then act as indices into this table to retrieve the corresponding results, which are then accumulated to produce the final output.

LUT Tensor Core: A Software-Hardware Co-Design

To overcome the limitations of naive LUT implementations, the LUT Tensor Core introduces a holistic co-design spanning software optimizations and hardware customization.

Overview of the LUT Tensor Core software-hardware co-design, featuring software-based operator fusion and the hardware LUT Tensor Core unit.

Software Optimizations

  1. Operator Fusion: To mitigate precomputation overhead, the system fuses LUT generation with preceding operators (like Normalization). This allows the LUT to be built once and reused across multiple operations, reducing redundant computation by hundreds of times.
  2. Weight Reinterpretation and Table Symmetrization: By remapping weights (e.g., reinterpreting binary {0, 1} as {-1, 1}), the authors exploit mathematical symmetry. This "odd function" property allows the hardware to store only half of the LUT, effectively doubling storage efficiency.
  3. Table Quantization: Precomputed LUT values are quantized to INT8, further shrinking the storage footprint with negligible impact on model perplexity.

Hardware Customization

The hardware unit is designed for maximum efficiency:

  • Elongated Tiling: Unlike standard square tiles, the LUT Tensor Core uses an elongated tiling shape. This maximizes "table reuse," ensuring that a single precomputed LUT serves as many weight columns as possible.
  • Bit-Serial Design: A flexible bit-serial architecture allows the same hardware circuitry to support various weight precisions (1, 2, or 4-bit) seamlessly.
  • LMMA Instruction Set: A new instruction set, LUT Matrix Multiply-Accumulate (LMMA), was developed and integrated into compilers like TVM and Welder to automate these optimizations.

Evaluation and Results

The LUT Tensor Core was evaluated across several LLMs, including LLAMA-2 (7B to 70B), OPT, BLOOM, and BitNet, using the WikiText-2 and MMLU benchmarks.

  • Compute Density and Energy Efficiency: The design achieved a 1.44× improvement in both compute density and energy efficiency compared to the state-of-the-art UNPU accelerator.
  • Area Efficiency: The LUT Tensor Core occupies only 16% of the area of a conventional MAC-based Tensor Core while delivering superior performance.
  • End-to-End Performance: On real-world models like BitNet and quantized LLAMA, the system demonstrated inference speedups ranging from 2.06× to 5.51×.
  • Accuracy: The use of INT8 for LUT quantization resulted in negligible accuracy loss; for example, LLAMA-2-7B perplexity remained virtually unchanged.

Conclusion

The LUT Tensor Core demonstrates that a software-hardware co-design centered on lookup tables can significantly outperform traditional dequantization-based approaches for low-bit LLM inference. By offloading precomputation to software and optimizing hardware for table reuse and symmetry, the system achieves substantial gains in efficiency and performance. Future work includes extending this approach to KV cache quantization and exploring the integration of structured sparsity to further enhance throughput.

Summary updated

Abstract

As large language model (LLM) inference demands ever-greater resources, there is a rapid growing trend of using low-bit weights to shrink memory usage and boost inference efficiency. However, these low-bit LLMs introduce the need for mixed-precision matrix multiplication (mpGEMM), which is a crucial yet under-explored operation that involves multiplying lower-precision weights with higher-precision activations. Unfortunately, current hardware does not natively support mpGEMM, resulting in indirect and inefficient dequantization-based implementations. To address the mpGEMM requirements in low-bit LLMs, we explored the lookup table (LUT)-based approach for mpGEMM. However, a conventional LUT implementation falls short of its potential. To fully harness the power of LUT-based mpGEMM, we introduce LUT Tensor Core, a software-hardware co-design optimized for low-bit LLM inference. Specifically, we introduce software-based operator fusion and table symmetrization techniques to optimize table precompute and table storage, respectively. Then, LUT Tensor Core proposes the hardware design featuring an elongated tiling shape design to enhance table reuse and a bit-serial design to support various precision combinations in mpGEMM. Moreover, we design an end-to-end compilation stack with new instructions for LUT-based mpGEMM, enabling efficient LLM compilation and optimizations. The evaluation on low-bit LLMs (e.g., BitNet, LLAMA) shows that LUT Tensor Core achieves more than a magnitude of improvements on both compute density and energy efficiency.
BibTeX
@misc{mo2024lut,
  author = {Zhiwen Mo and Lei Wang and Jianyu Wei and Zhichen Zeng and Shijie Cao and Lingxiao Ma and Naifeng Jing and Ting Cao and Jilong Xue and Fan Yang and Mao Yang},
  title = {{LUT Tensor Core: Lookup Table Enables Efficient Low-Bit LLM Inference Acceleration}},
  year = {2024},
  eprint = {2408.06003},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.06003},
}
Figure