🤖 machine learning

TreeGRNG: Binary Tree Gaussian Random Number Generator for Efficient Probabilistic AI Hardware

This paper introduces TreeGRNG, a hardware-efficient binary tree Gaussian Random Number Generator that replaces complex arithmetic units with low-cost comparators to achieve superior distribution accuracy, significantly reduced energy consumption, and higher throughput for Bayesian Neural Networks at the extreme edge.

Original authors: Jonas Crols, Guilherme Paim, Shirui Zhao, Marian Verhelst

Published 2026-06-16

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jonas Crols, Guilherme Paim, Shirui Zhao, Marian Verhelst

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 build a super-smart robot that can make decisions, but instead of just saying "Yes" or "No," it needs to say, "I'm 80% sure it's a cat, but maybe 20% sure it's a dog." This is the world of Bayesian Neural Networks (BNNs). They are great because they admit when they are unsure, which makes them safer for things like self-driving cars or medical diagnosis.

However, there's a huge problem: to make these networks work, every single "brain cell" (neuron) in the robot needs a special tool called a Gaussian Random Number Generator (GRNG). Think of this tool as a magical dice roller that doesn't just roll 1 through 6, but rolls numbers that follow a "bell curve" (most rolls are in the middle, fewer are at the extremes).

The Problem with Old Tools
Until now, building these magical dice rollers for tiny, battery-powered robots (like those in your smartwatch or a drone) has been a nightmare. The old methods are like trying to bake a cake using a massive industrial oven, a complex recipe book, and a team of chefs. They require:

Heavy math (multiplication, square roots).
Huge memory tables (like a giant cookbook).
Lots of energy and space.

This makes them too big and too hungry for power to fit inside the tiny chips needed for "extreme edge" devices.

The Solution: The "TreeGRNG"
The authors of this paper invented a new way to build this dice roller called TreeGRNG. Instead of a complex kitchen, they built a Binary Tree (a decision tree).

Here is how it works, using a simple analogy:

1. The "Weighted Coin Flip" Tree

Imagine you want to pick a number between 0 and 100, but you want the middle numbers (like 40–60) to be picked much more often than the edges (like 0 or 100).

Instead of calculating a complex formula to pick a number, the TreeGRNG asks a series of simple "Yes/No" questions, like a game of "20 Questions":

Level 1: "Is the number less than 50?" (Flip a coin).
Level 2: If yes, "Is it less than 25?" (Flip a coin again).
Level 3: If yes, "Is it less than 12?" (Flip a coin again).

The Magic Trick: In a normal game, the coin is fair (50/50). In TreeGRNG, the coins are weighted.

If the "bell curve" says the number is likely to be in the middle, the coin is rigged to land on "Yes" 90% of the time.
If the number is likely to be on the edge, the coin is rigged to land on "No" 90% of the time.

By following the path of these weighted coin flips, the machine naturally lands on the right numbers without ever doing complex math.

2. The Hardware "Secret Sauce"

The paper highlights two main reasons why this is a game-changer for hardware:

No Calculators Needed: Old methods needed expensive math chips (multipliers, adders). TreeGRNG only needs comparators. Think of a comparator as a simple referee that just asks, "Is this number bigger than that one?" It's incredibly cheap and tiny to build.
The "Mirror" Trick: Because a bell curve is symmetrical (the left side looks like the right side), the machine can use the same "referee" for both sides, just looking at the answer backwards. This cuts the hardware size in half.
The "Grouping" Trick: At the very tips of the tree (the extreme edges), the differences between numbers are so tiny that the machine can use the same referee for several different questions. This shrinks the hardware even more.

The Results: Why It Matters

The authors built this and compared it to the best existing technology (called TI-HT). Here is what they found:

Energy: It uses 3.7 times less energy per sample. It's like getting the same mileage out of a car but using a much smaller battery.
Speed & Space: It generates 5.8 times more numbers per second for the same amount of chip space. It's like fitting a supercomputer into a shoebox.
Accuracy: It is actually more accurate at creating the perfect bell curve than the old methods.
Flexibility: While the paper focuses on Gaussian (bell curve) numbers, the system is so flexible that you could theoretically change the "weights" of the coins to create any shape of probability distribution, not just a bell curve.

In Summary
The paper presents a clever way to build a random number generator for AI by replacing heavy math with a simple, cascading series of "weighted coin flips." By doing this, they created a chip design that is tiny, incredibly energy-efficient, and fast enough to bring advanced, "uncertainty-aware" AI to the smallest, most power-hungry devices in the world.

Technical Summary: TreeGRNG: Binary Tree Gaussian Random Number Generator for Efficient Probabilistic AI Hardware

Problem Statement
Bayesian Neural Networks (BNNs) offer significant potential for enhancing the trustworthiness of AI systems by quantifying decision-making uncertainties, which is critical for safety-critical applications like healthcare and autonomous driving. However, deploying BNNs at the extreme edge is hindered by the resource-intensive requirement to integrate a Gaussian Random Number Generator (GRNG) into every neuron. State-of-the-art (SoTA) GRNG algorithms, such as Ziggurat, Box-Muller, and Table-Hadamard, rely heavily on complex arithmetic operations (multipliers, adders), extensive look-up tables (LUTs), and rejection sampling. These dependencies result in prohibitive area and energy overheads, making them unsuitable for ultra-low-power, resource-constrained edge hardware.

Methodology
The paper proposes TreeGRNG, a novel architecture that generates Gaussian Random Numbers (GRNs) using a binary tree structure, fundamentally replacing complex arithmetic units with ultra-low-cost constant comparators.

Algorithmic Core: The algorithm approximates any Probability Density Function (PDF), specifically Gaussian, by splitting the output range into $2^N$ $2^{N}$ bins (where $N$ $N$ is the desired bit precision). The generation process involves two phases:
1. Bin Creation (Design Time): The target PDF is divided into equidistant intervals. For each node in a binary tree of depth $N-1$ , a decision threshold is pre-calculated based on the integral (area) of the PDF curve for the left and right sub-bins.
2. Bin Selection (Run-time): A Uniform Random Number Generator (URNG), implemented via Linear Feedback Shift Registers (LFSRs), provides random bits. At each tree level, a "weighted coin flip" is performed by comparing the URNG output against the pre-determined constant threshold. A logic '0' or '1' directs the path left or right, building the final $N$ -bit index.
Hardware Implementation: The architecture utilizes a parallel implementation where each tree level contains an LFSR and decision blocks. To minimize hardware cost, the paper introduces three specific optimizations for Gaussian distributions:
1. Symmetry Optimization: Exploiting the symmetry of the Gaussian PDF to reuse thresholds and invert outputs for the right side of the distribution, halving the comparator count.
2. Cluster Optimization: Grouping adjacent nodes with similar thresholds to share comparators, reducing the exponential growth of hardware complexity to linear growth.
3. Pipelining: Inserting registers to shorten the critical path and increase throughput.

Key Contributions

Arithmetic-Free Architecture: TreeGRNG eliminates the need for multipliers, adders, LUTs, and complex transcendental functions (e.g., sine, cosine, logarithm) typically required by SoTA GRNGs.
Hardware-Aware Optimization: The proposal demonstrates how Gaussian properties (symmetry and threshold clustering) can be leveraged to drastically reduce the number of required comparators without significant loss in distribution accuracy.
Flexibility: Unlike many fixed-function GRNGs, the TreeGRNG framework allows designers to adjust the shape of the sampled probability distribution by modifying the pre-computed thresholds, extending beyond standard Gaussian generation to any discrete PDF.
Open-Source Availability: The design is made available as open-source hardware.

Experimental Results
The authors implemented the TreeGRNG in SystemVerilog and synthesized it using a 45nm standard cell library, comparing it against the SoTI TI-HT (Table-Hadamard Transform) architecture.

Area and Energy: The optimized TreeGRNG achieves a 3.7× reduction in energy per sample compared to the TI-HT SoTA.
Throughput and Efficiency: It delivers a 5.8× boost in throughput per unit area.
Accuracy: The distribution accuracy, measured by the Kolmogorov-Smirnov Test (KST), surpasses the SoTA while maintaining negligible error even with hardware-reducing optimizations (clustering and symmetry).
Scalability: The circuit area grows linearly with threshold bitwidth, unlike the exponential growth seen in non-optimized implementations.

Significance and Claims
The paper claims that TreeGRNG represents a paradigm shift for probabilistic AI hardware by removing the computational bottleneck of random number generation at the edge. By replacing arithmetic-heavy logic with simple constant comparators, the design achieves a superior trade-off between area, power, and throughput. The authors position this as the first solution capable of generating diverse PDF shapes with such hardware efficiency, enabling the practical deployment of uncertainty-aware BNNs in extreme edge environments where resources are scarce. The work opens new horizons for future probabilistic AI designs that require high-efficiency stochastic computation.

1. The "Weighted Coin Flip" Tree

2. The Hardware "Secret Sauce"

The Results: Why It Matters

More like this