BCJR-QAT: A Differentiable Relaxation of Trellis-Coded Weight Quantization
BCJR-QAT uses BCJR algorithm for differentiable quantization training, reducing PPL by 0.084 on WikiText-2.
Key Findings
Methodology
BCJR-QAT replaces Viterbi's argmax with the BCJR algorithm, achieving differentiability in quantization training. It uses Boltzmann expectation at temperature T to produce a soft codeword, converging to hard QTIP code.
Key Results
- On WikiText-2, single-layer BCJR-QAT reduces PPL by 0.084 compared to QTIP-PTQ, showcasing its advantage in quantization training.
- Multi-layer BCJR-QAT shows super-additive effects with a PPL reduction of 0.077 in joint training of layers [L4, L8].
- Experiments validate the drift-budget theory for BCJR-QAT escaping the QTIP-PTQ Voronoi basin.
Significance
BCJR-QAT provides a novel differentiable approach to quantization training, addressing the non-differentiability of Viterbi algorithm, enabling strong language models on consumer hardware.
Technical Contribution
BCJR-QAT introduces BCJR algorithm for differentiable quantization training and achieves efficient computation on a single GPU with a 6.57× speedup using Triton kernel.
Novelty
BCJR-QAT is the first to apply BCJR algorithm in quantization training, offering a new path selection mechanism compared to traditional Viterbi algorithm.
Limitations
- High-temperature phase gradient overshoot leads optimizer into worse Voronoi basin, affecting final performance.
- Layer-wise reconstruction MSE optimization in OLMoE model fails to improve end-task PPL.
Future Work
Future work includes conducting 16-layer joint end-to-end BCJR-QAT experiments on cloud-scale hardware and exploring further optimization of high-temperature training strategies.
AI Executive Summary
BCJR-QAT introduces a novel quantization training method by replacing Viterbi's argmax with the BCJR algorithm, achieving differentiability in quantization training. It uses Boltzmann expectation at temperature T to produce a soft codeword, eventually converging to hard QTIP code.
In experiments, BCJR-QAT demonstrates its advantage on WikiText-2, reducing PPL by 0.084 in single-layer training compared to QTIP-PTQ. Multi-layer joint training shows even more significant effects, surpassing the sum of single-layer gains.
Despite significant progress in quantization training, BCJR-QAT faces challenges with gradient overshoot in the high-temperature phase, affecting final performance. Future work will explore optimizing training strategies and conducting larger-scale experiments on cloud-scale hardware.
Deep Analysis
Background
Quantization training is a crucial method for compressing deep learning models, reducing model size without significantly degrading performance. Traditional methods like Viterbi algorithm face non-differentiability issues, limiting their application in quantization training.
Core Problem
The argmax operation in Viterbi algorithm is non-differentiable, preventing effective gradient propagation in quantization training, thus limiting model optimization capabilities.
Innovation
BCJR-QAT introduces BCJR algorithm to replace Viterbi's argmax, achieving differentiability in quantization training. It uses Boltzmann expectation to generate soft codewords and adjusts temperature T to converge from soft to hard codewords.
Methodology
- �� Use BCJR algorithm to compute exact marginal posteriors over paths
- �� Generate soft codewords as Boltzmann expectation
- �� Implement efficient computation using Triton kernel
- �� Gradually reduce temperature T during training to converge from soft to hard codewords
Experiments
Experiments conducted on WikiText-2 and C4 datasets, comparing BCJR-QAT with traditional QTIP-PTQ performance. Single-layer and multi-layer training strategies were used, validating drift-budget theory.
Results
BCJR-QAT reduces PPL by 0.084 on WikiText-2 compared to QTIP-PTQ, with multi-layer training showing even more significant effects, surpassing single-layer gains.
Applications
BCJR-QAT can be used for running strong language models on consumer hardware, reducing model size and improving efficiency.
Limitations & Outlook
Gradient overshoot in high-temperature phase affects final performance, requiring future optimization of training strategies.
Plain Language Accessible to non-experts
Imagine a factory where traditional quantization methods are like workers using rigid rulers to measure products, but the rulers can't bend, so some products can't be measured accurately. BCJR-QAT is like a flexible ruler that adjusts to the shape of the product, allowing for more accurate measurement.
ELI14 Explained like you're 14
Imagine playing a game where your character needs to navigate a maze. Traditional methods are like only being able to move in straight lines, while BCJR-QAT is like being able to move in curves, finding the exit faster! That's why it performs better on WikiText-2.
Glossary
BCJR Algorithm
An algorithm for computing exact marginal posteriors over paths, enabling differentiability in quantization training.
Used to replace Viterbi's argmax operation.
Viterbi Algorithm
A dynamic programming algorithm for selecting optimal paths, but faces non-differentiability issues.
Used in traditional quantization methods.
Boltzmann Expectation
Calculates probability distribution over paths at a given temperature to generate soft codewords.
Used in BCJR-QAT for generating soft codewords.
Triton Kernel
An efficient computation kernel used to accelerate BCJR algorithm computation.
Achieves efficient computation on a single GPU in BCJR-QAT.
Drift-Budget Theory
A theory predicting when BCJR-QAT can escape the QTIP-PTQ Voronoi basin.
Validated in experiments.
Open Questions Unanswered questions from this research
- 1 How to further optimize high-temperature training strategies to avoid gradient overshoot issues.
- 2 How to validate BCJR-QAT performance on larger-scale models.
Applications
Immediate Applications
Consumer Hardware Language Models
BCJR-QAT can be used to run strong language models on consumer hardware, reducing model size and improving efficiency.
Long-term Vision
Large-Scale Cloud Experiments
Future experiments on cloud-scale hardware to validate BCJR-QAT performance and scalability.
Abstract
Trellis-coded quantization sets the current 2-bit post-training frontier for LLMs (QTIP), but pushing below the PTQ ceiling requires quantization-aware training, and QAT on a trellis is obstructed by the non-differentiable Viterbi argmax. We introduce BCJR-QAT, a relaxation that replaces the argmax with the BCJR forward-backward sum-product algorithm at temperature $T$, producing a soft codeword equal to the Boltzmann expectation over trellis paths, exactly differentiable, recovering the hard QTIP code as $T \to 0$, and mathematically identical to the transfer-matrix computation for a 1D Ising-like spin chain. We contribute (i) a fused Triton kernel making BCJR tractable on a single consumer GPU ($6.57\times$ speedup, fp32 parity); (ii) a quantitative drift-budget theory of when BCJR-QAT can escape the QTIP-PTQ Voronoi basin, verified across four experiments; and (iii) a positive empirical result on Llama-3.2-1B at 2 bpw under end-to-end forward-KL distillation: with the right schedule (skip the high-$T$ phase to avoid an overshoot we diagnose), single-layer BCJR-QAT beats QTIP-PTQ by $\mathbf{-0.084}$ PPL on WikiText-2, and multi-layer compounding is super-additive.