KLL Compaction & Rank Guarantees

Compacting Ordered Samples Without Losing Rank

Suppose a service records millions of response times but can retain only a small summary. Keeping the mean misses tail latency, while storing every value is expensive. A quantile sketch answers questions such as “what value has about 99% of observations below it?” KLL—the K-form of the Karnin–Lang–Liberty sketch—does this by repeatedly sorting small buffers and randomly keeping half their items.

Think of a stack of trays. New observations enter the bottom tray with weight one. When a tray overflows, sort its items, flip a fair coin, keep either the even or odd positions, discard the other positions, and move the kept items one tray upward. An item on level \(h\) carries weight \(2^h\). Two adjacent items of weight \(2^h\) are therefore represented by one randomly selected item of weight \(2^{h+1}\).

For a tiny compaction, sort \([2,4,7,9]\) at level zero. Choosing even positions retains \([2,7]\); choosing odd positions retains \([4,9]\). Each survivor moves to level one and represents weight two. Both outcomes preserve total represented mass \(4\). For a rank query at \(x=5\), the exact compacted-block rank is two. The even choice contributes weight two from value \(2\); the odd choice contributes weight two from value \(4\). Both happen to be exact here. At \(x=3\), the two outcomes contribute two or zero instead of exact rank one—an error of \(+1\) or \(-1\), centered at zero.

This deep dive builds on streaming quantiles by explaining why compaction preserves rank approximately and how weighted queries reconstruct a distribution. A weighted level assigns weight \(2^h\) to every retained level-\(h\) item. Compaction replaces a sorted group by one random parity at the next level. Capacity schedules decide how many items each level may hold; true KLL uses a carefully chosen schedule rather than merely giving every level the same capacity. Rank error is \(\widehat R(x)-R(x)\), where \(R(x)\) counts stream values at most \(x\). Mergeability means compatible summaries can combine their level buffers and compact again. Tail accuracy describes behavior near extreme quantiles; ordinary KLL targets uniform absolute rank error, while specialized variants can emphasize tails.

KLL approximates ranks, not numeric distances. A small rank error can correspond to a large value error across a distribution gap. Duplicates need a documented rank convention, and NaN handling, ordering, serialization, and randomness are part of the implementation contract.

Levels, Weights and Random Compaction

Let level \(h\) contain values of weight \(w_h=2^h\). New items enter level zero. When a level exceeds its capacity, KLL sorts an eligible even-sized region, flips a fair parity bit \(b\in\{0,1\}\), retains positions \(b,b+2,b+4,\ldots\), and promotes those survivors to level \(h+1\). Each promoted value's weight doubles.

Mass preservation is exact. Compacting \(2m\) items of weight \(2^h\) removes represented mass \(2m\cdot2^h\) and promotes \(m\) items of weight \(2^{h+1}\), the same amount. Consequently \[ \sum_{h\ge0}2^h|L_h|=n \] after every completed update, assuming no overflow and no temporarily retained odd remainder is misweighted.

For rank threshold \(x\), consider one sorted compaction. Pair adjacent values. Every pair entirely at or below \(x\) contributes its full weight whichever parity wins; every pair entirely above contributes zero. At most one pair straddles the cutoff. Its exact contribution is \(2^h\), while the compacted contribution is either \(0\) or \(2^{h+1}\). Thus one compaction contributes rank error in \(\{-2^h,0,+2^h\}\), with conditional expectation zero under a fair parity bit.

Errors at higher levels are larger, but far fewer high-level compactions occur. KLL's capacity schedule balances the number and scale of these random errors. A full proof charges variance or tail probability across levels and chooses capacities geometrically, with more protection at influential upper levels and specialized handling near the top. The resulting family attains near-optimal space: \(O((1/\varepsilon)\log\log(1/\delta))\) items for additive rank error \(\varepsilon n\) with failure probability \(\delta\), with \(O(1/\varepsilon)\) space at constant confidence. Precise constants, schedule, and small-\(n\) behavior depend on the KLL variant.

Always keeping one parity is a counterexample to unbiasedness. For the block \([1,3,6,8]\) and \(x=2\), always keeping evens always returns rank two instead of one, accumulating directional error. Random choice is not aesthetic; it turns deterministic drift into a mean-zero sum that concentration bounds can control.

Compared with deterministic GK summaries, KLL trades deterministic worst-case rank bounds for randomized bounds and typically strong compactness and merge behavior. Compared with reservoir sampling, KLL explicitly organizes weighted compactions to control ranks across the distribution.

flowchart TD
    A[New value enters level zero with weight one] --> B{Level exceeds capacity?}
    B -->|no| C[Retain current weighted state]
    B -->|yes| D[Sort eligible items]
    D --> E[Flip fair parity bit]
    E --> F[Keep alternating positions]
    F --> G[Promote survivors to next level]
    G --> H[Double their represented weight]
    H --> I[Total represented mass unchanged]
    I --> J[Each threshold sees bounded mean-zero error]
    J --> K[Charge errors across scheduled levels]
    K --> L[High-probability additive rank bound]
    E --> M{Biased or reused parity?}
    M -->|yes| N[Directional rank error may accumulate]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C,D navy;
    class E,F,G,H purple;
    class I,J,K,L teal;
    class M,N crimson;

Charging Rank Error Across Levels

Fix a threshold \(x\). The final estimated rank is \[ \widehat R(x)=\sum_{h\ge0}2^h\,|\{v\in L_h:v\le x\}|. \] Every compaction contributes a random error variable \(E_{h,t}(x)\) with conditional mean zero and \(|E_{h,t}(x)|\le2^h\). The total error is their sum. The proof challenge is not one compaction but the number of compactions at each level, their dependence structure, and their increasing weights.

A useful audit ledger records, for each level, its capacity, compaction count, parity choices, and maximum error charge. KLL analysis exploits the fact that level \(h\) represents increasingly large blocks: the number of possible compactions drops rapidly as \(h\) rises. Properly scheduled capacities keep the variance proxy and tail bound small enough that \[ \Pr\!\left[|\widehat R(x)-R(x)|>\varepsilon n\right]\le\delta. \] The strongest KLL results carefully handle all rank queries and schedule details; a simple equal-capacity hierarchy demonstrates the mechanism but uses \(O(k\log n)\) retained space and should not be mislabeled as the full near-optimal construction.

For a hand trace, compact \([1,3,6,8]\) at level zero, keep \([1,6]\), and promote with weight two. Add uncompacted level-zero values \([2,9]\). The weighted summary is \(1:2,6:2,2:1,9:1\), total mass six. At \(x=4\), estimated rank is \(2+1=3\). If the original six values were \([1,3,6,8,2,9]\), exact rank is three. At \(x=2\), estimate is three while exact rank is two, a \(+1\) error attributable to that compaction.

Perturb the parity to keep \([3,8]\). At \(x=2\), only uncompacted \(2\) contributes, so estimate one and error \(-1\). The two outcomes are symmetric. If the same biased choice is forced across many similar blocks, errors can align; independent fair bits are the defense.

import random

class CompactingQuantiles:
    """Readable KLL compaction core with equal per-level capacity.
    Production KLL replaces this simple capacity rule with its proven schedule.
    """
    def __init__(self, capacity=64, seed=7):
        if capacity < 4 or capacity % 2:
            raise ValueError("capacity must be even and at least four")
        self.capacity = capacity
        self.seed = seed
        self.rng = random.Random(seed)
        self.levels = [[]]
        self.n = 0

    def update(self, value):
        if not isinstance(value, (int, float)) or value != value:
            raise ValueError("finite ordered numeric value required")
        self.levels[0].append(value)
        self.n += 1
        self._compress_from(0)

    def _compress_from(self, level):
        while level < len(self.levels) and len(self.levels[level]) > self.capacity:
            items = sorted(self.levels[level])
            remainder = []
            if len(items) % 2:
                remainder = [items.pop()]
            parity = self.rng.randrange(2)
            promoted = items[parity::2]
            self.levels[level] = remainder
            if level + 1 == len(self.levels):
                self.levels.append([])
            self.levels[level + 1].extend(promoted)
            level += 1

    def weighted_items(self):
        return sorted((value, 1 << level)
                      for level, values in enumerate(self.levels)
                      for value in values)

    def represented_mass(self):
        return sum(weight for _, weight in self.weighted_items())

    def rank(self, value):
        return sum(weight for item, weight in self.weighted_items()
                   if item <= value)

    def quantile(self, q):
        if not 0 <= q <= 1 or self.n == 0:
            raise ValueError("q in [0,1] and nonempty sketch required")
        target = 1 + int(q * (self.n - 1))
        total = 0
        for value, weight in self.weighted_items():
            total += weight
            if total >= target:
                return value
        raise AssertionError("mass invariant broken")

    def merge(self, other):
        if self.capacity != other.capacity:
            raise ValueError("incompatible capacities")
        while len(self.levels) < len(other.levels):
            self.levels.append([])
        for level, values in enumerate(other.levels):
            self.levels[level].extend(values)
        self.n += other.n
        self._compress_from(0)

def exact_rank(values, x):
    return sum(v <= x for v in values)

values = list(range(1000))
sketch = CompactingQuantiles(64, seed=11)
for value in values:
    sketch.update(value)
assert sketch.represented_mass() == len(values)
assert abs(sketch.rank(500) - exact_rank(values, 500)) <= 50
assert abs(sketch.quantile(0.90) - 899) <= 50

left, right = CompactingQuantiles(64, 21), CompactingQuantiles(64, 22)
for value in values[:500]:
    left.update(value)
for value in values[500:]:
    right.update(value)
left.merge(right)
assert left.represented_mass() == 1000
assert abs(left.rank(900) - 901) <= 60

single = CompactingQuantiles(4)
single.update(7)
assert single.quantile(0) == single.quantile(1) == 7

try:
    CompactingQuantiles(5)
    raise AssertionError("odd capacity accepted")
except ValueError:
    pass

print("retained:", sum(map(len, sketch.levels)), "mass:", sketch.represented_mass())
print("p50/p90:", sketch.quantile(0.5), sketch.quantile(0.9))
print("merged rank at 900:", left.rank(900))

Percentiles at Production Scale

In a teaching case, use cards numbered one through sixteen, compact them by coin flips, and verify weighted mass after every move. Learners can query several thresholds and attribute every discrepancy to a specific compaction.

At production scale, a latency service can maintain one KLL sketch per service, region, and time window. Queries return p50, p90, p99, and rank-based SLO diagnostics. Partition sketches merge only when value type, ordering, \(k\) or accuracy parameters, capacity schedule, serialization version, NaN policy, and weighting semantics match. Merge buffers first and compact; averaging percentile values is mathematically invalid.

A retail event platform may use KLL for order-value distributions, but must distinguish unweighted events from weighted transactions. Repeating a value by weight can be too slow, while a native weighted KLL variant needs its own proof and format. Likewise, deletions are not handled by simply inserting a negative-weight value into an ordinary KLL.

Failure cases include adversarial ordering combined with predictable parity, biased pseudo-random bits, overflow of represented weights, incompatible merges, and treating value error as rank error. A p99 rank guarantee does not bound milliseconds when the distribution has a gap. Evidence invalidating deployment includes mass mismatch, exact-audit rank error above the configured envelope, merge results depending excessively on partition layout, serialized-version disagreement, or tail SLO decisions that remain unstable inside the allowed rank interval.

flowchart TD
    A[Define rank error and percentile decisions] --> B{Need absolute or tail-relative rank accuracy?}
    B -->|absolute| C[Evaluate standard KLL]
    B -->|tail-relative| D[Evaluate tail-focused variant]
    C --> E[Choose error confidence and schedule]
    D --> E
    E --> F[Fix type ordering NaN and merge contract]
    F --> G[Validate on exact sampled windows]
    G --> H{Mass rank error and latency acceptable?}
    H -->|no| I[Reject resize or change sketch]
    H -->|yes| J[Version and deploy]
    J --> K[Monitor drift merges and tail decisions]
    K --> L{Assumptions still hold?}
    L -->|yes| K
    L -->|no| I
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,F navy;
    class C,D,E purple;
    class G,J,K teal;
    class H,I,L crimson;

Implement and Audit KLL Compaction

Mastery begins with tracing weight, not merely retained values. After every compaction, verify \(\sum_h2^h|L_h|=n\). For several thresholds, compute exact rank, weighted estimated rank, and a ledger of compaction charges. Explain why only one adjacent pair can straddle a fixed threshold in a sorted compaction.

Implementation audits should test fair parity, fresh randomness, odd-buffer handling, cascaded compactions, duplicates, infinities or NaNs, numeric ordering, serialization, and compatible merge. A readable equal-capacity prototype is useful for these invariants, but its \(O(k\log n)\) storage is not the near-optimal KLL theorem. Production claims must be tied to the exact schedule and version actually deployed.

For extension, compare absolute-rank KLL with relative-error quantile sketches, deterministic GK, and reservoir sampling. Investigate weighted updates and sliding windows only through variants with explicit proofs. This bridges ordinary streaming quantiles to mergeable summaries, tail-aware monitoring, and distributed analytics.