From Stateful to Stateless Blue Noise

The blue noise token sampling article describes a random number generator built as a binary tree of small error diffusion ditherers. Each node decides one bit of the output, and each node is a five-state integer machine. This article is about what that machine is a member of. There are at least three more forms of the same generator, and the smallest of them stores nothing.

01Where This Starts

The generator came out of image dithering. Each step narrowed the one before it.

None of what follows was looked for. One behavior of the generator was made visible by chance, and one correction prompted a further search.

Both rows of the figure are one ditherer switching between two kernels. At a node of the tree the ditherer always runs at 50% duty: it has to send half of its visits each way. Everything below happens at 50%.

02Towers

The first drawing of the generator's bit stream wrote a single stream along the rows of an eight-row panel, wrapping at its edge. When the panel happened to be an even number of columns wide, it showed towers: pairs of neighbouring columns that read 01 or 10 in every row, stacked all the way down, never 00 or 11. With an odd number of columns they are gone. The generator does not know how wide the panel is, so the pattern had to be in the stream, at period two.

The stream is fair overall and lopsided by parity. The reason is in the machine's graph. Its five states fall into two classes, and every transition crosses from one class to the other, so the machine is in one class on even steps and in the other on odd steps, for ever. The classes do not output 1 equally often.

One more thing is visible on the tape. Group the outputs in pairs, and with one of the two possible groupings every pair is 01 or 10. The other grouping is free to produce 00 and 11. That is what the towers were: an even width lined the pairs up in columns, and the pairs of the right grouping stood out.

03The Fractional Pair, Exactly

The remembered reason for dropping the fractional pair was that it needs floating point, or else suffers from rounding. That is half right, and the wrong half is the interesting one. What happens depends on what holds the error.

Held in whole output steps, the spread share of an error of 1 truncates to nothing and the density is wrong. Held in 48ths, the kernel's own denominator, the 2⁄48 share of a small leftover rounds to zero and the stream collapses into 0101. Double precision follows the table until a cancellation that should land on zero lands a rounding error to one side of it, and from there it runs in the opposite phase. Fixed point a few powers finer than the denominator never differs.

It never differs because the fractional pair is a finite machine too. The two error slots always sum to −1, 0 or +1. The leftovers, called x and y here, keep taking new values, but they stay strictly between 0 and 1 and only their sign reaches the output. Writing β for the spread share k2⁄48: y is β or β(1 − x), and x is βy.

Side by side, as single nodes over 2²¹ steps:

The fractional pair is the five-state machine with the parity lock turned up: 0.8 and 0.2 where binary routing has 0.6 and 0.4. It is closer to plain 0101, and it spends less randomness per bit. Read as a trend, the table asks a question. If the blue slope comes with the lopsided parity, what happens at the far end, where the only rule is that a pair is 01 or 10?

04Just the Pairs

Draw a random bit, output it, then output its complement. Repeat. Inside a pair the two bits always differ. Across pairs they are independent. So the autocorrelation of the stream is 1 at lag zero, −½ at lag one (half of all neighbours sit inside a pair), and zero beyond. A sequence with that autocorrelation has the power spectrum

which goes as f² at low frequencies: exactly +6 dB per octave, the ideal first-order blue noise slope. It is the spectrum of differenced white noise, reached with nothing but a coin and a promise to pay it back. The pair itself is old. Sent down a wire it is Manchester coding, chosen because it has no energy at DC; in Monte Carlo terms a sample and its mirror image are antithetic variates.

The pair sits on the curve at threshold ½. The two error diffusion machines sit a little under it at low frequencies, and they hold their slope at thresholds away from ½, where the pair's sags. That difference is what their memory across pairs buys: the pair forgets everything at each pair boundary, the machines carry an error across it.

The first four thresholds of the lab are powers of one half, and that matters. At ½ only the root decides, at ¼ the root and one child. A threshold such as 0.3 has no finite binary expansion, so the comparison reaches every level of the tree, and a node at level l is visited once in 2^l samples: its pairs act on a time scale 2^l times longer. The sum of those is still blue, but it rises at about +3 dB per octave, not +6. This is true of every form here, the shipped generator included.

Swept over every threshold k⁄1024, the slope depends on how many levels of the tree the threshold involves, and hardly at all on the form. Averaged over the thresholds of each kind, from 0 to 1, for the shipped five-state generator: +6.2, +6.5 and +6.0 dB per octave with one, two and three levels, +4.6 with four, +3.5 with five, +3.0 with six, and about +2.8 from there on. The peaks stand alone: the thresholds right beside ½ involve ten levels, and have the lowest slopes in the middle of the range.

The pair forms trace the same comb with less swing. Over thresholds from 0.1 to 0.9 every form averages +3.0 dB per octave; the spread around that average is 0.60 for the five-state machine and 0.48 for the pair. The pair's peaks are lower (+6.0 at most, against +6.5) and its dip beside ½ is shallower (+2.9 against +2.5, and +2.2 for the seven-state machine). Between 0.1 and 0.9, at thresholds that involve seven levels or more, which is nearly all of them, the forms cannot be told apart: +2.9 to +3.0 dB per octave, and low frequencies 13 to 14 dB under the mean.

05In the Tree: Exact Strata

In the tree, the root sends each sample left or right. If the root's pairs are 01 or 10, every aligned pair of samples puts one sample in each half of the range. Each child is then visited exactly once per pair of samples, so its own pairs line up with blocks of four samples, and its 01 or 10 splits its half into quarters. The argument repeats down the tree.

The shipped generator starts its nodes from the stationary distribution, which mixes both classes. The nodes are then out of step with the sample index, and blocks of 16 or more are almost never exact. Nothing else changes: the spectrum is the same either way, because only the phase of each node moves. The parity lock that drew the towers is this property seen from the side.

06Three States, One Bit, None

On its own, a pair node has three states: at the start of a pair, owing a 0, owing a 1. In an aligned tree two of them are already known.

The node is named by the output bits above it, so the levels are computed in order, most significant first, one hash per level.

What this is a relative of

Take the hash away and the formula says: output bit l is bit l of t. That is the sample index written in binary and mirrored about the binary point: 1 becomes 0.1, 2 becomes 0.01, 3 becomes 0.11. This is the van der Corput sequence, the oldest low-discrepancy sequence and the one-dimensional core of the Halton and Sobol sequences. It has the block property above, and it is perfectly regular: nothing about it is random.

Owen scrambling randomizes it without breaking the blocks. Each output bit is flipped or not, and the decision depends on all the higher output bits: a binary tree with one random bit per node. That is the formula above with the pair number left out of the hash. It is a fixed point set, so at a depth of N bits it repeats after 2^N samples. Read in index order it is also not a random stream: its most significant bit is 1010… or 0101… for ever, its second bit repeats every four samples, and so on down.

This form was proposed by the AI co-author of these articles when asked whether the machine could be made stateless, and it is, up to the hash, the shuffled radical inverse of the renderers below; that is very likely where it came from, through the literature in the model's training data, and the review page sets the two side by side. The stateless pair tree is that construction with the scrambling bits redrawn for every pair. The blocks survive, because within a pair both samples use the same flip. The period goes, because the next pair uses another. And the five- and seven-state machines are the same tree again, with nodes that carry memory from one pair into the next.

Renderers already redraw the flips, for another reason. Laine and Karras shuffle the order of their samples with a hash in which each bit of the sample index is flipped according to the bits above it; Burley names this a nested uniform shuffle and combines it with the scramble. Flipping bit l of the index by a hash of index >> (l + 1) is redrawing the flip for every pair. The purpose there is to let many pixels share one sequence without sharing its order, not to make a random stream, but the stream is there all the same: run in index order, one dimension of Burley's shuffled scrambled sequence has a top bit of random 01 and 10 pairs, exact blocks, and a slope at threshold ½ of +5.6 to +7.4 dB per octave depending on the seed.

The common-grid stateless form shares their pairing and aligned-stratum properties. Here the flip is one hash of the node and the pair together; there it is a flip for the pair, shared by every node of a level, combined with a fixed flip for the node. In index order, over twelve seeds, that measures +5.96 to +6.01 dB per octave here against +5.6 to +7.4 there, because their hash is built for speed and its successive pairs are not independent draws. Measured in the next article: with the constants of PBRT's FastOwenScrambler in place of Laine and Karras's, their construction and this one agree on every stream-wide measure (pairs, spectra, aligned blocks), so that difference is the hash; they still differ in a sliding window, where their composed flip ties adjacent deals together, and that difference is the construction. A review of that work, with labs, sets the two side by side. The comparison pursued here is what such a stream does in time, at every threshold, and what nodes with memory change. The research notes below distinguish those shared properties from equivalence of the complete mapping.

In C, at 32 bits

At 32 bits the node is named by a per-level key and the output bits above it, rather than by a heap index. The keys depend only on the seed. The hash is the low-bias 32-bit hash the generator already uses, and the flip is its top bit.

/*
 * A stateless blue noise generator: every threshold of its output is blue noise in time, and
 * any sample can be computed directly.
 * From "From Stateful to Stateless Blue Noise" by Jan Boon (Kaetemi),
 * https://polyverse.dev/articles/bluenoise-generators.html
 * Implementations derived from this code or from that article must keep this reference and
 * this notice.
 */
#include <stdint.h>

/* lowbias32, from Chris Wellons's hash-prospector (public domain). The constants are the ones
 * TheIronBorn posted in issue 19 of that repository on 2022-05-07:
 * https://github.com/skeeto/hash-prospector/issues/19#issuecomment-1120105785 */
static inline uint32_t lowbias32(uint32_t x) {
    x ^= x >> 16; x *= 0x21f0aaadu;
    x ^= x >> 15; x *= 0x735a2d97u;
    x ^= x >> 15; return x;
}

typedef struct { uint32_t key[32]; } blue32;            /* per-level keys, fixed for a seed */

void blue32_init(blue32 *g, uint32_t seed) {
    for (uint32_t l = 0; l < 32; l++) g->key[l] = lowbias32(seed + (l + 1) * 0x9e3779b9u);
}

uint32_t blue32_at(const blue32 *g, uint32_t t) {       /* sample t, directly */
    uint32_t acc = 0;                                    /* the output bits decided so far */
    for (int l = 0; l < 32; l++) {
        uint32_t pair = (l < 31) ? t >> (l + 1) : 0;     /* which pair of visits */
        uint32_t flip = lowbias32(lowbias32(g->key[l] ^ acc) ^ pair) >> 31;
        acc = (acc << 1) | (flip ^ ((t >> l) & 1));
    }
    return acc;
}

The sequence is 2³² samples long. For a longer one, make t and pair 64-bit and fold the upper half of pair into the hash. This code and the page's own version give the same values.

07What the Memory Costs

The parity lock of section 02 is not the root's alone. Every node of a machine with memory is lopsided by the parity of its own visits, and a node at level l is visited once in 2^l samples. Seen from the output, the locks add up to a mean that depends on where in the index a sample falls. The pair forms have no such thing: the first bit of every pair is a fair coin.

Reading every second value

Every second output of the shipped generator has a mean of 0.45 or 0.55 instead of 0.5, depending on the seed, because the output lands in the upper half four times in ten on one parity of the index and six in ten on the other. Odd strides are unaffected. What is left of every second value is white as well as biased: the slope is gone (+0.05 dB per octave), and no start repairs that. The pair forms lose their slope the same way but stay unbiased at every stride, and the seven-state machine is biased more (0.65). The llama.cpp patch draws one value per token and already warns against sharing a generator between purposes; this is a stronger reason than the loss of the spectrum.

The aligned start

The reference draws each node's first state from the machine's stationary distribution, which mixes both parity classes; with a new seed the bars above change shape. An aligned start (section 05) draws it only from the class in which the node's 01 or 10 pairs line up with the sample index, and the bars become the same staircase for every seed. The step function and the spectrum stay the same. Measured on the five-state tree: a reader that consumes aligned blocks of 64 or 256 samples gets 2 to 6 times less error; a reader whose windows start anywhere gets no change at all. Token sampling has no block structure, so it would gain nothing.

And it has a price. An aligned start ties every node's lock to the sample index, so the mean of the stream becomes periodic at every power of two: against the stream's variance, −15 dB at period 2, which the reference start has too, and then −21, −27 and −33 dB at periods 4, 8 and 16, which it mostly does not. Strides of 4, 8 and 16 then read means of 0.42, 0.41 and 0.41. That is a grid laid over a design whose point was to be even in every window without one. The pair forms are exact in aligned blocks with no periodic mean at all; what they have is neighbours that are correlated on even samples and not on odd ones. If exact blocks are wanted, those are the forms to use, and the reference start is the right one for the machines with memory.

08Where This Leads

The stateless form of section 06 is, up to its hash, a construction from rendering: the radical inverse with its index shuffled and its value scrambled. The review of hash-based Owen scrambling goes through that mathematics, with the published code and labs that step it, and sets this form beside it. The review turned up behaviour of the stateless form that led to further stateless generators; those are discussed further in Stateless Blue Noise Generators.

09Open Questions

• Thresholds that are not a power of one half. Every form here falls to about +2.8 dB per octave once a threshold involves seven levels of the tree or more, which is nearly all of them (section 04). The lower levels act on longer time scales, and nothing in any of the nodes compensates for that. Whether a node with a small bounded state can hold the slope there has not been looked at.
• What the stateless form is, and prior work. The pair rule, hierarchical scrambling and random-access index shuffling have established precedents. The comparison notes below distinguish those shared properties from equivalence of the complete mapping; the next article carries the comparison for the forms without a grid.

10What Is New Here, and What Is Not

Part by part, against the sources in the reading list. Six labels are used. Existing: existing art, whether used knowingly or arrived at independently and then matched to a source. Variant: an existing construction with one stated change. Combination: existing parts put together in a way not found in the sources reviewed. New: no counterpart found in the sources reviewed. Result: a measurement or derivation about the objects on this page; a fact about them, not a technique. Implementation: code for a construction on this page; only its correctness is claimed. "Not found" means not found in the sources listed below, of which some are read in full and some are not; the reading list says which.

11Related Work and Comparisons to Make

Which bits determine the flip?

Keep three baselines separate: a fixed Owen scramble of the radical inverse, a nested shuffle of its indices, and the combination of both. Burley's §§3–4 distinguish these operations explicitly. The existing Owen review and stream lab are the starting point for reproducing the comparison at equal precision.

The common-grid rule here keys a flip on both the output prefix and the current pair number. In the shuffle-then-scramble construction, dependencies arise through two composed permutations. Matching the balanced pairs and aligned counts establishes shared properties; it does not by itself establish identical mappings or identical distributions over mappings.

A useful check is to enumerate small bit depths and compare the realizable permutations and correlations between nodes and successive pairs. Keep ideal independent flip tables separate from the practical hash implementations. A difference between two short hash mixers is not automatically a difference between the underlying constructions; the next article measures exactly that, the Laine and Karras constants against PBRT's in the same construction, and the difference is the constants.

What the converter literature already supplies

Welz, Galton and Fogleman describe random balanced symbols in §III-B, including how zero outputs can intervene when the switching block's input is even. This supplies a concrete antecedent for the pair rule. Their circuit routes a supplied code among converter elements; the tree here uses branch decisions to construct an output value. A comparison should preserve that difference in input and output roles.

For the five- and seven-state machines, compare reachable states, output timing, transition probabilities and initialization, as well as the accumulated-error bounds. A shared first-order spectrum is insufficient to identify a machine. The seven-state reduction here is at 50% duty; it should not be generalized to varying duty or to an entire converter without a separate derivation.

12Reading List

The pair and the common-grid form have their relatives in converter design and in the sampling literature; the sources for the forms without a grid are in the next article.

Closest: tree-structured dynamic element matching

1. I. Galton, "Spectral Shaping of Circuit Errors in Digital-to-Analog Converters," IEEE Transactions on Circuits and Systems II 44(10), 1997, 808–817; and US patent 5,684,482. A binary tree of switching blocks, each with a small bounded state, that spreads the mismatch error of a multibit converter. The patent gives the error spectrum as proportional to sin^2L(ω⁄2), which for L = 1 is (1 − cos ω)⁄2: the pair's spectrum. The tree splits a given input code among the converter's unit elements; it is not a tree over the bits of a value, and it is not read as a random number.
2. J. Welz, I. Galton, E. Fogleman, "Simplified Logic for First-Order and Second-Order Mismatch-Shaping Digital-to-Analog Converters," IEEE Transactions on Circuits and Systems II 48(11), 2001, 1014–1027. States the first-order rule in so many words: the switching sequence is built "by randomly choosing between" two symbols, (+1, −1) and (−1, +1), one of them "chosen randomly by a fair coin toss". That is the random pair of section 04, in a circuit, in 2001. Their second-order logic chooses the next symbol to keep a double sum bounded, which is memory across pairs, the nearest relative of the five-state machine. Read this first.

The sequence and its scrambling

1. J. G. van der Corput, "Verteilungsfunktionen (Erste Mitteilung)," Proceedings of the Koninklijke Akademie van Wetenschappen te Amsterdam 38, 1935, 813–821. Volume PDF. The sequence.
2. A. B. Owen, "Randomly Permuted (t,m,s)-Nets and (t,s)-Sequences," in Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Lecture Notes in Statistics 106, Springer, 1995, 299–317. Nested uniform scrambling: the tree of flips.
3. A. B. Owen, "Scrambled Net Variance for Integrals of Smooth Functions," Annals of Statistics 25(4), 1997, 1541–1562. Why scrambled nets beat both plain nets and random sampling on smooth integrands; relevant to the x² row of the comparison.
4. A. B. Owen, "Monte Carlo Variance of Scrambled Net Quadrature," SIAM Journal on Numerical Analysis 34(5), 1997, 1884–1910.
5. M. Pharr, W. Jakob, G. Humphreys, Physically Based Rendering, 4th edition, section 8.6 (radical inverse, van der Corput, Owen scrambling) and section 8.7 (hash-based scramblers). The most readable introduction; start here for the stateless form.
6. S. Laine, T. Karras, "Stratified Sampling for Stochastic Transparency," Computer Graphics Forum 30(4), 2011. The hash in which each bit is changed only by the bits on one side of it, used there to shuffle the order of the samples: the per-pair redraw of section 06, in 2011.
7. B. Burley, "Practical Hash-based Owen Scrambling," Journal of Computer Graphics Techniques 9(4), 2020. Owen scrambling computed with a hash instead of a stored tree, and the distinction between scrambling the values and shuffling the index. Sections 3–4 distinguish value scrambling from index shuffling; the latter is essential to the stream comparison in section 06.
8. T. Kollig, A. Keller, "Efficient Multidimensional Sampling," Computer Graphics Forum 21(3), 2002, 557–563. Random digit scrambling, the cheaper relative of Owen's.
9. P. Christensen, A. Kensler, C. Kilpatrick, "Progressive Multi-Jittered Sample Sequences," Computer Graphics Forum 37(4), 2018, 21–33. Progressive stratification with a random choice inside each stratum.
10. A. Helmer, P. Christensen, A. Kensler, "Stochastic Generation of (t,s) Sample Sequences," EGSR 2021. Owen-scrambled sequences generated as "the next sample goes in the opposite stratum", which is the pair rule; the scrambling is fixed per node.

The pair's spectrum under other names

1. J. Pauly, EE179 Lecture 6A, Stanford. Derives the power spectrum of split-phase (Manchester) line coding, which is the 01 or 10 pair used to carry data: no energy at DC.
2. R. Schreier, G. C. Temes, Understanding Delta-Sigma Data Converters, Wiley-IEEE Press, 2004. First-order noise shaping, noise transfer function 1 − z⁻¹, the same spectrum.
3. S. P. Lipshitz, J. Vanderkooy, "High-Pass Dither," AES 4th Regional Convention, Tokyo, 1989. Differenced random numbers as dither: the same spectrum with a triangular distribution instead of a uniform one.
4. J. M. Hammersley, K. W. Morton, "A New Monte Carlo Technique: Antithetic Variates," Mathematical Proceedings of the Cambridge Philosophical Society 52(3), 1956, 449–475. A sample and its mirror image, used together.
5. J. X. Wei (ATI), US patent 7,580,157, "High-pass dither generator and method," 2009. Multi-bit dither with a uniform distribution and a high-pass spectrum, made by filtering the words of a shift register: the nearest stated goal to the five-state tree that was found. No tree, and no evenness at every threshold.

Where this came from

1. Jan Boon (Kaetemi), "Stochastic Kernel-Switching Error Diffusion," blog.kaetemi.be, 2026.
2. Jan Boon (Kaetemi), "Blue Noise Token Sampling," polyverse.dev, 2026.
3. Jan Boon (Kaetemi), "Hash-Based Owen Scrambling, in Pictures," polyverse.dev, 2026. Where the stateless form of section 06 is set beside the literature, and where its dealing was first seen.
4. Jan Boon (Kaetemi), "Stateless Blue Noise Generators," polyverse.dev, 2026. The continuation: the form without its loop, the form without a grid, and the comparisons.

The hash

1. Christopher Wellons, hash-prospector (public domain): the two-round XOR/multiply mixer named lowbias32 in its README. The constants in the listings are the ones TheIronBorn posted in issue 19 on 2022-05-07 (bias 0.107 by the project's measure, against 0.174 for the README's); Boost's hash_mix_impl<32> (1.85.0) uses the same. An existing helper. Its suitability for these threshold spectra is a separate implementation measurement.