💻 computer science

Arithmetic Variable LogLog: Advancing the Memory-Variance Frontier

This paper introduces Arithmetic Variable LogLog (AVLL), a new cardinality estimation algorithm that surpasses the state-of-the-art ExaLogLog in both accuracy and speed by utilizing arithmetic encoding and an early-exit mechanism to achieve a superior memory-variance product across all tested sizes.

Original authors: Brian Bushnell

Published 2026-08-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Brian Bushnell

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 running a massive party where millions of guests are streaming through the door, but you only have a tiny notebook to keep track of who is there. You can't write down every single name—that would fill up your notebook instantly. Instead, you need a clever trick to guess how many unique people have shown up without counting them one by one. This is the problem of "cardinality estimation," a puzzle that has fascinated computer scientists for decades. The goal is to squeeze the most accurate guess out of the smallest amount of memory possible.

For a long time, the best way to do this was like having a row of lockers, each with a specific size. You'd toss a guest's name into a locker based on a random code, and if the locker was empty, you'd mark it. If it was already full, you'd check if the new guest was "more unique" than the one already inside. The more lockers you had, the better your guess. But there was a catch: to get a super-accurate guess, you needed either more lockers (which took up more space) or bigger lockers that could hold more detailed information about each guest. For years, the debate was: is it better to have a few giant, super-detailed lockers, or a huge crowd of tiny, simple ones?

Enter a new contender called Arithmetic Variable LogLog (AVLL). Think of it as a magician who realized that the old way of packing lockers was wasteful. Instead of using rigid, pre-sized slots, AVLL uses a flexible, "arithmetic" packing method that fits way more tiny lockers into the same amount of space. The paper suggests that by squeezing in 5.5 times more of these tiny lockers, the system can make a much better guess than the previous champions, even though each individual locker holds less information. It's like realizing that having 1,000 tiny, quick-peek cameras gives you a better picture of a crowd than having just 200 giant, slow-motion cameras.

The Paper's Big Discovery

The author, Brian Bushnell, presents AVLL as a new way to count unique items in a data stream. They found that by using a clever math trick called "base-56 arithmetic encoding," they could pack 11 registers (the digital lockers) into a single 64-bit word of computer memory. In the past, standard methods would waste bits trying to fit these registers into fixed slots, but AVLL uses every single bit, leaving zero waste.

This packing trick gives AVLL a massive advantage: at a memory size of 1 KB (which is tiny in computer terms), AVLL can store 1,408 registers, whereas the previous state-of-the-art method, called ExaLogLog, could only fit 256 registers in the same space. That's a 5.5× advantage in the number of observations the system can make.

The paper shows that this "more is better" approach works incredibly well. In tests using 128,000 independent simulations, AVLL achieved a width-weighted mean absolute error of 1.63% at 1 KB. In comparison, ExaLogLog had an error of 1.71%. While that difference might sound small, in the world of high-precision counting, it's a significant win. The author calculated a "memory-variance product" (a score for how efficiently memory is used) of approximately 3.4 for AVLL, which is lower (and therefore better) than ExaLogLog's practical score of 3.78 and even beats its theoretical best of 3.67.

Speeding Up the Count

But AVLL isn't just more accurate; it's also surprisingly fast, especially when the computer is busy. The paper describes a mechanism called "early exit." Imagine a bouncer at the party door who can instantly tell if a guest is someone they've already seen, without even looking at the guest list. AVLL does this by comparing a guest's code to a global "floor" value. If the code is below the floor, the guest is ignored immediately, and the system doesn't even touch the memory where the lockers are stored.

In tests where thousands of these counting systems were running at once (simulating a crowded computer cache), AVLL was 2.7 to 4.5 times faster than ExaLogLog. This is because ExaLogLog has to check its memory for every single item, even if it's a duplicate, while AVLL filters out the vast majority of duplicates before they ever reach the memory. At high numbers of unique items, AVLL rejects about 96% of incoming data without touching the registers, keeping the system running smoothly.

What This Means (and What It Doesn't)

The paper explicitly rules out the idea that "richer" registers (like ExaLogLog's huge 32-bit lockers that store detailed history) are always better. The results suggest that for this specific type of counting problem, having more independent observations (more registers) is more valuable than having richer data per observation.

However, the author is careful to note that AVLL is not "idempotent" in the strictest sense. This means that if you feed the exact same duplicate data into the system twice, it might behave slightly differently than if you fed it once, though the paper shows that in practical tests with heavy duplication, the accuracy didn't drop at all. They also admit that their "HLDLC" estimator is a clever blend of different math formulas found through massive simulation, rather than a mathematically proven "perfect" solution like ExaLogLog's maximum likelihood estimator.

The paper concludes that AVLL is a self-contained tool (written as a single Java class) that is ready to use. It handles massive amounts of data without running out of memory space for the counter itself, and it works just as well whether the data is a chaotic mix of unique items or a repetitive stream of duplicates. The core message is a shift in philosophy: in the battle for memory efficiency, density beats richness. By packing more simple, independent counters into the same space, we can get a clearer, faster, and more accurate picture of the data stream.

Technical Summary: Arithmetic Variable LogLog (AVLL)

Problem Statement

Cardinality estimation—the task of counting distinct elements in a data stream using bounded memory—requires a fundamental tradeoff between memory usage and estimation accuracy. While HyperLogLog (HLL) has long been the practical gold standard, recent advances like ExaLogLog have pushed the memory-variance frontier by increasing the information density per register (using wide, variable-width registers and maximum likelihood estimation). However, these approaches often suffer from a low register count per byte, limiting the statistical independence of observations. Conversely, architectural compaction methods like DynamicLogLog (DLL) increase register density but historically lacked the per-register information depth of richer estimators. The challenge is to determine whether maximizing the number of independent registers or maximizing the information per register yields better accuracy under a fixed memory budget.

Methodology

The paper introduces Arithmetic Variable LogLog (AVLL), a novel estimator that prioritizes register density through arithmetic encoding and a blended estimation pipeline.

1. Arithmetic Register Encoding

Unlike traditional LogLog variants that use fixed-width bit slots (e.g., 6-bit or 8-bit registers), AVLL employs base-56 arithmetic encoding.

State Space: Each register encodes 56 distinct states, comprising an NLZ (Number of Leading Zeros) exponent and a 2-bit sub-NLZ history pattern.
Packing: Since $56^{11} < 2^{64}$ , AVLL packs 11 registers into a single 64-bit word with zero wasted bits. This results in a register width of approximately 5.82 bits.
Comparison: At a 2 KB memory budget, AVLL stores 2,816 registers, whereas ExaLogLog (using 32-bit registers) stores only 512. This yields a 5.5× register-count advantage.
Access: Register access requires 64-bit unsigned division and remainder operations (Long.divideUnsigned, Long.remainderUnsigned), which are computationally more expensive than fixed-width bit masking but are amortized by the estimator's early exit mechanism.

2. Architecture and Scaling

Shared Exponent (Global Floor): AVLL stores relative NLZ values against a global floor (globalNLZ), similar to DynamicLogLog. This allows the memory cost to scale as $O(B + \log \log C)$ rather than $O(B \times \log \log C)$ , effectively decoupling the maximum representable cardinality from the register width.
Early Exit: Elements with hash values below the current global floor are rejected immediately without touching register memory. At high cardinalities, this rejects >99% of elements, drastically reducing memory bandwidth usage.
Merge Support: AVLL supports register-wise merging by unpacking registers, performing bitwise OR operations on their bitmap representations, and repacking.

3. The HLDLC Estimator

AVLL utilizes a Hybrid Layered DLC (HLDLC) estimator, a four-component blended framework designed to minimize bias across the entire cardinality range:

LDLC (Layered DLC): A blend of DLC (Dynamic Linear Counting) and SBS (State Bias Sum) for low-to-mid cardinality, combined with HC (History Counting) for high cardinality.
Hybrid+2: A blend of SBS and Mean+H (a novel history-corrected harmonic mean).
Blending Strategy: The final estimate is a 50/50 blend of LDLC and Hybrid+2. This complementary bias cancellation reduces error below that of any single component.
Components:
- SBS: Exploits specific 2-bit history patterns for low-cardinality estimation.
- DLC: A tier-aware extension of Linear Counting that eliminates transition artifacts.
- HC: Uses history bits at tier boundaries to estimate high cardinality.
- Mean+H: A harmonic mean estimator corrected for sub-NLZ history patterns.
Implementation: All correction formulas are embedded as approximately 100 static constants within a single Java class, requiring no external tables or runtime dependencies.

Key Contributions

Arithmetic Encoding: Demonstrates the practicality of base-56 arithmetic encoding, achieving 11 registers per 64-bit word with zero bit waste.
HLDLC Estimator: Introduces a four-component blended estimator that achieves record accuracy without iterative solving (unlike ExaLogLog's Maximum Likelihood approach).
Record Accuracy: Achieves a width-weighted mean absolute error (MAE) of 1.63% at 1 KB, outperforming ExaLogLog (1.71%) by 4.7%. The empirical Memory-Variance Product (MVP) is ~3.4, which is lower than ExaLogLog's practical MVP (3.78) and its theoretical optimum (3.67), though the paper notes this is an empirical observation rather than a proven theoretical bound.
Deployment Speed: Under cache pressure (thousands of simultaneous sketches), AVLL is 2.7–4.5× faster than ExaLogLog due to the early exit mechanism filtering most elements before register access.
Unbounded Cardinality: The sliding-floor architecture removes the register-width-imposed ceiling on cardinality, supporting cardinalities up to the hash width limit (e.g., $2^{256}$ ) with near-constant memory overhead.
Robustness: Maintains accuracy under low-complexity (highly duplicated) data distributions with zero degradation, despite using non-idempotent tier promotion.

Experimental Results

Accuracy: AVLL outperforms ExaLogLog and seven other estimators (including HLL-TailCut4, UltraLogLog, and Apache HLL4) at every tested memory point (0.25 KB to 4 KB) under both high-complexity (all-unique) and low-complexity (skewed duplication) conditions.
Throughput:
- ALU-bound: AVLL matches ExaLogLog's throughput (~14,681 vs 13,801 M adds/s) when sketches fit in cache.
- Memory-bandwidth-bound: Under extreme cache pressure (sim=4,096), AVLL achieves 4,360 M adds/s compared to ExaLogLog's 1,609 M adds/s (a 2.7× advantage).
- Cardinality Scaling: AVLL's throughput increases by 177% as stream cardinality grows from 5M to 80M, whereas ExaLogLog remains flat, widening the speed gap to 9.7× at high cardinality.
Memory Efficiency: AVLL achieves the lowest empirical MVP (~3.4) demonstrated to date, beating ExaLogLog's practical MVP (3.78) and its theoretical optimum (3.67).

Significance and Claims

The paper posits a central design principle: "Density beats richness." For LogLog-family estimators, maximizing the number of independent hash observations (register count) often yields better accuracy than maximizing the information content per register, provided the estimator is sophisticated enough to extract information from the simpler encoding.

The author claims that AVLL represents a new state of the art by:

Surpassing the empirical performance of fixed-register estimators (ExaLogLog) through arithmetic packing and a blended estimator, achieving an MVP lower than ExaLogLog's theoretical optimum (though the paper clarifies this is an empirical result, not a theoretical proof of optimality for AVLL's encoding).
Solving the speed-accuracy tradeoff in deployment scenarios by leveraging early exit to minimize memory bandwidth usage.
Removing the cardinality ceiling inherent in fixed-width register schemes.

The paper acknowledges that AVLL is not strictly idempotent (due to tier promotion) and that its register access involves division overhead. However, it argues that these limitations are negligible in high-cardinality streaming applications where early exit dominates, and that the accuracy gains are robust across diverse data distributions. The implementation is provided as a self-contained Java class within the BBTools suite.