Suppose you want the median of a stream that may never end.
You could keep every value forever.
Or you could keep enough values, at carefully chosen weights, to preserve rank structure within a known error envelope.
KLL chooses the second path.
Quick Read
KLL is a compact quantile-sketch family designed to estimate ranks and quantiles over data streams with provable error guarantees. It repeatedly compacts retained observations so memory remains bounded while the surviving items represent larger and larger portions of the original stream.
One-sentence answer: KLL is lossy because it discards most individual observations while preserving a weighted approximation of their ordering that supports quantile queries within bounded rank error.
The Core Trick Is Compaction
Imagine retaining a batch of ordered values at one level.
When the level becomes too full, the sketch sorts or organises the retained values and keeps only part of them, promoting the survivors to a higher level with greater weight.
Two low-weight observations can become one higher-weight representative.
Exact local detail disappears. Approximate rank mass survives.
Weighted Survivors Stand In for Discarded Values
A retained item at a higher level represents more of the original stream than one at the base level.
The sketch therefore becomes a compressed weighted sample of the ordered data.
It does not preserve the exact sequence or exact multiplicity of every value. It preserves enough weighted order to approximate ranks.
Randomisation Prevents Systematic Bias
When compacting an ordered run, a sketch should not always keep the lower value or always keep the upper value.
Randomised selection avoids introducing a consistent directional bias across repeated compactions.
The uncertainty becomes stochastic but analyzable.
Rank Error Is the Guarantee
KLL-style sketches are valuable because the main guarantee is mathematical rather than merely visual.
Ask for the value around rank 0.9 and the returned item should correspond to a nearby rank with high probability, where “nearby” depends on sketch size and configured accuracy.
This is a rank-space guarantee.
It does not promise that the returned numerical value is close in absolute units when the distribution changes sharply around that rank.
Why KLL Does Not Need the Stream Length in Advance
A streaming system may not know how many observations will arrive.
KLL can update online as the stream grows.
That makes it suitable for monitoring, telemetry, distributed analytics and other settings where data volume is discovered only by living through it.
Mergeability Makes KLL a Distributed Primitive
Compatible sketches built on separate partitions can be merged.
This allows one machine to summarise one shard, another machine another shard, and a higher layer to combine them without moving every raw value.
Again, the raw observations disappear from the fast path while a useful algebra over their order survives.
KLL and t-Digest Are Not Competitors in Every Sense
KLL is attractive when provable rank-error guarantees are central.
t-digest is often chosen for strong empirical tail accuracy and practical percentile estimation over floating-point data.
The choice is not merely “which is more accurate?”
It is “which error contract fits the receiver’s risk?”
The Middle and the Tails Do Not Always Deserve Equal Precision
A service may care much more about p99 latency than p50 latency.
A KLL configuration with roughly uniform rank-error treatment can be entirely appropriate if the receiver wants broad quantile coverage.
If the application overwhelmingly cares about extreme tails, another sketch with different accuracy allocation may fit better.
KLL Preserves Distribution Position, Not Provenance
The sketch cannot tell you which user generated the 99th-percentile event.
It cannot replay the sequence.
It cannot reconstruct every discarded value.
If those questions may matter later, the sketch should sit beside richer logs rather than replace them.
Education: Bounded Approximation Is a Better Lesson Than “Close Enough”
Students often hear approximation described informally.
KLL demonstrates a more mature idea.
You can design a representation whose error behaviour is part of the mathematics.
Approximation becomes an engineered contract rather than a vague compromise.
When KLL Is Exactly the Right Loss
Use it when percentile queries are important, bounded rank error matters, data arrive as a stream, memory is limited, and mergeable summaries are valuable.
It is especially strong when the receiver values a provable error model across the quantile range.
When KLL Becomes Dangerous
- Rank error is mistaken for value error.
- The application needs extreme-tail precision beyond the chosen sketch configuration.
- Incompatible sketches are merged.
- Approximate percentiles are used as exact settlement values.
- Raw logs are discarded even though later provenance or replay is required.
- The user sees many decimal places and assumes exactness.
A Practical KLL Audit
- Error: what rank error can the receiver tolerate?
- Memory: how large is the sketch?
- Quantiles: which parts of the distribution matter most?
- Merge: must sketches combine across partitions?
- Display: is approximate output labelled appropriately?
- Threshold: could rank uncertainty change a consequential decision?
- Source: where is richer evidence retained?
Sources and Further Reading
Continue Through eduKateSG
Continue with How Lossy Works | Quantile Sketches and the companion How Lossy Works | t-Digest.
Final Thought: Provable Loss Can Be Safer Than Hidden Exactness
KLL does not keep the stream.
It keeps a mathematical promise about what remains measurable after the stream is gone.