🤖 machine learning

FQTree: Fine-grained Quantization and Hardware Generation of Boosted Decision Trees

This paper presents FQTree, a fine-grained quantization-aware training algorithm combined with the QXXGB hardware generation framework, which optimizes boosted decision trees for FPGA deployment by reducing LUT usage by 26–57% while maintaining or improving accuracy.

Original authors: Zhiqiang Que, Chang Sun, Haiyang Wang, Dinesh Pamunuwa, Roshan Weerasekera, Qijia Tang, Bakhtiar Zadeh, Wayne Luk, Maria Spiropulu

Published 2026-08-13

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhiqiang Que, Chang Sun, Haiyang Wang, Dinesh Pamunuwa, Roshan Weerasekera, Qijia Tang, Bakhtiar Zadeh, Wayne Luk, Maria Spiropulu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to make decisions, like a referee in a video game or a security guard at a club. You don't want the robot to be a slow, heavy thinker; you want it to be lightning fast, making split-second choices without stuttering. This is the world of "Boosted Decision Trees" (BDTs). Think of a BDT not as a single giant brain, but as a team of many small, simple decision-makers. Each one asks a simple question like, "Is the temperature above 20 degrees?" or "Is the speed over 50 mph?" Based on the answer, the team passes the baton to the next person in line. By the end of the line, the whole team has added up their opinions to make a final call. These teams are famous for being great at spotting patterns in messy data, but they have a problem: they are often too heavy and slow for the tiny, super-fast chips (called FPGAs) that power real-time systems like self-driving cars or particle physics experiments.

The big challenge is that these decision teams are usually trained using "floaty" numbers (like 3.14159...), which are precise but take up a lot of space and energy to store. To make them run on tiny chips, engineers usually try to squeeze these numbers into smaller, simpler boxes (like whole numbers). But it's like trying to fit a giant, wobbly jelly into a small, rigid box: if you just squish it in after the jelly has already set, it breaks, and the robot starts making dumb mistakes. The old way of doing this was to guess the right box size for everyone, which often wasted space or ruined the robot's smarts.

This paper introduces a clever new method called FQTree (Fine-grained Quantization Tree) and a companion tool called QXGB that changes how we build these decision teams. Instead of training the team with big, floaty numbers and then trying to squeeze them into a box later, FQTree teaches the team to think in small, simple boxes while they are learning. It's like training a gymnast to perform on a narrow balance beam from day one, rather than letting them practice on a wide floor and then forcing them onto the beam right before the competition.

The secret sauce is that FQTree realizes that not all members of the decision team are equally important. The first few members, who make the big, obvious calls, need to be very precise. The later members, who just make tiny tweaks to fix small errors, don't need to be as precise. FQTree automatically figures out exactly how much "brain space" each member needs. It gives the big thinkers more bits (more detail) and the small thinkers fewer bits (less detail), saving a massive amount of space. It also uses a trick called "bias folding," which is like shifting all the numbers so they are all positive, allowing the hardware to drop the sign bit and become even simpler.

Once the team is trained in this efficient way, the QXGB framework acts like a magical translator. It takes the trained team and instantly builds a custom hardware blueprint for a chip, without needing a human engineer to redraw the circuits for every new design. The results are impressive: on three different tests (one for recognizing handwritten digits, one for spotting jet particles in physics, and one for finding network intruders), this method used 26% to 57% less hardware space (specifically Look-Up Tables, or LUTs) than the current best methods, while keeping the accuracy just as high or even making it better. In some cases, it even made the decisions twice as fast. It's a win-win: the robot gets smaller, faster, and just as smart.

Technical Summary: FQTree – Fine-grained Quantization and Hardware Generation of Boosted Decision Trees

Problem Statement

Boosted Decision Trees (BDTs) are widely used in latency-critical applications due to their predictive performance and compact size, making them suitable for Field-Programmable Gate Array (FPGA) deployment. However, efficient hardware implementation remains challenging. Existing FPGA-oriented BDT designs typically rely on uniform or manually tuned fixed-point representations across the entire model. This approach fails to account for the heterogeneous numerical roles of different BDT components (input features, split thresholds, leaf values, and accumulation logic), often leading to unnecessary hardware costs or avoidable accuracy degradation.

Furthermore, straightforward post-training quantization (PTQ) is often ineffective for BDTs. Unlike neural networks where quantization perturbs arithmetic continuously, BDT quantization can cause discrete routing changes; small perturbations to features or thresholds may flip branch decisions, entirely altering the selected leaf. This sensitivity necessitates a Quantization-Aware Training (QAT) approach that exposes the model to quantization effects during optimization, allowing numerical parameters to adapt to reduced precision while preserving predictive quality.

Methodology

The FQTree Algorithm

The authors propose FQTree, a hardware-aware, fine-grained QAT algorithm for BDTs. Unlike PTQ, FQTree incorporates quantization directly into the training loop.

Boosting with Quantization: During the stage-wise boosting process, each newly fitted tree is immediately quantized before being used in subsequent training stages. This ensures that later trees adapt to the residual errors of the already-quantized ensemble, compensating for both task residuals and quantization-induced distortion.
Leaf-Value Quantization Scheme: The core innovation is a hardware-oriented leaf-value quantization strategy. Instead of uniform precision, FQTree assigns precision based on the magnitude of leaf values:
- Global Step & Tree-wise Shift: A global quantization step size ( $s$ ) is used across the ensemble, combined with a tree-wise shift factor ( $f(\vec{v})$ ).
- Non-negative Integer Representation: The scheme transforms leaf values into compact non-negative integers. Negative values are clipped to zero, and a shift is applied to remove the sign bit, simplifying the datapath.
- Bias Folding: The offset removed during rebasing is folded into a tree-level or class-level bias term, which is added only once after accumulation, rather than carried through every tree path.
- Dynamic Bitwidth: The bitwidth for each tree ( $b_t$ ) is determined by the dynamic range of its quantized integer values ( $\lceil \log_2(\max(\vec{v}'_{int}) + 1) \rceil$ ). Early trees, which contribute more to the final prediction, naturally receive more bits, while later corrective trees use fewer bits.
Feature/Threshold Quantization: Standard uniform quantization is applied to features and thresholds, with their precision naturally aligned in hardware via signed subtractors.

The QXGB Framework

To bridge the gap between training and deployment, the authors introduce QXGB (Quantized XGBoost), a compiler-based framework for automatic hardware generation.

Dataflow Representation: The trained quantized BDT is lowered into an extended Distributed Arithmetic Instruction Set (DAIS) intermediate representation (IR). This IR is extended with an explicit MUX instruction to capture the conditional routing of decision nodes, treating BDT inference as a stateless dataflow kernel.
Automatic Generation: The compiler symbolically traces the computation graph and generates synthesizable RTL or High-Level Synthesis (HLS) code. This flow supports bit-exact emulation and allows for systematic exploration of the accuracy-latency-resource trade-off without manual redesign.

Key Contributions

FQTree Algorithm: A fine-grained QAT approach featuring a hardware-oriented leaf-value quantization formulation that utilizes a global step, tree-wise shift, and bias folding to enable compact, non-negative integer representations.
QXGB Framework: A scalable, compiler-based flow for generating efficient, low-latency FPGA BDT implementations for both HLS and RTL, minimizing latency and resource usage.
Comprehensive Evaluation: Demonstration that the method reduces Look-Up Table (LUT) usage by 26–57% compared to state-of-the-art FPGA-based BDT designs while matching or improving accuracy.

Experimental Results

The method was evaluated on three datasets: JSC (Jet Substructure Classification in high-energy physics), MNIST (handwritten digit classification), and NID (Network Intrusion Detection).

JSC Dataset: FQTree achieved 75.7% accuracy with 1,652 LUTs and 2 cycles (4.0 ns). Compared to TreeLUT (75.6% accuracy, 2,234 LUTs, 3 cycles), FQTree improved accuracy while reducing LUT usage by ~26% and pipeline depth. At a lower-cost point, FQTree achieved 74.8% accuracy with only 548 LUTs (31% fewer than TreeLUT) and 1 cycle latency.
MNIST Dataset: The highest-accuracy configuration reached 97.7% accuracy with 8,147 LUTs and 2 cycles, outperforming the previous best (POLYBiNN, 97.2%) with significantly lower latency and resource usage. At moderate points, FQTree achieved 96.7% accuracy with 2,744 LUTs, representing a ~39% reduction in LUTs compared to TreeLUT for similar accuracy.
NID Dataset: FQTree achieved 93.1% accuracy with only 157 LUTs and 1 cycle, a ~55% reduction in LUTs compared to TreeLUT (92.7% accuracy, 345 LUTs).
PTQ Baseline: When compared to a Post-Training Quantization baseline using the same quantizer, FQTree consistently provided better accuracy-resource trade-offs, confirming that the gains stem from both the quantizer design and the QAT optimization process.

Significance and Claims

The paper claims to provide the first unified workflow for FPGA deployment of BDTs that combines hardware-oriented leaf-value quantization, quantization-aware training, and automatic hardware generation.

The authors emphasize that their approach addresses the specific challenges of BDTs, where quantization affects routing decisions, not just arithmetic precision. By integrating fine-grained precision control into training and automating the hardware generation via the QXGB framework, the method enables systematic exploration of the accuracy-latency-resource trade-off. The results demonstrate that FQTree can identify compact, high-quality implementations that significantly outperform existing state-of-the-art designs in terms of hardware efficiency (LUT usage) while maintaining or improving predictive accuracy.