A promise about the rank is not a promise about the value

A summary of thirty-eight tuples is asked for the 99.9th percentile of twenty thousand values drawn from a Pareto distribution. It answers 4,189.8. The true answer is 253.4.

Its promise was that the returned value’s rank would be within 2% of the stream from the rank asked for. The rank of 4,189.8 in this stream is 20,000 — it is the largest value that ever arrived — and the rank asked for was 19,980. The rank error is 0.10%, well inside the promise, and the answer is sixteen times too large.

Nothing has gone wrong. That sentence is the essay.

Two errors, and what connects them #

For an answered query there are two numbers to measure and this site measures both.

Rank error. $\lvert \mathrm{rank}(a) - qn \rvert / n$, where $a$ is the answer. How far, as a fraction of the stream, the returned value sits from where it was asked for. This is what is guaranteed.

Value error. $\lvert a - v_q \rvert / v_q$, where $v_q$ is the true $q$-quantile. How wrong the number is, as a fraction of the number. This is what a reader of the answer cares about, and nothing guarantees it.

They are connected by the shape of the distribution and by nothing else. Write $Q$ for the quantile function — the inverse of the empirical distribution — and the relation is a derivative:

$$\text{value error} \approx \frac{Q'(q) \cdot \text{rank error}}{Q(q)}$$

So the ratio between them is the local steepness of the quantile function, scaled by the value there. On a uniform distribution $Q$ is a straight line and the ratio is about one. In a heavy tail $Q$ climbs almost vertically and the ratio is enormous.

Measured, on four distributions #

The same summary, $\varepsilon = 0.02$, twenty thousand values, worst case over eight quantiles:

The left column is flat, because it is a promise and the promise does not depend on the data. The right column spans two orders of magnitude on the same structure with the same tolerance.

Looking inside the log-normal row, quantile by quantile:

The middle of the distribution is answered well by both measures. The last two rows are answered with the same number, and that number is the maximum of the stream.

Why the answer is the maximum #

This is not a coincidence and it is not a bug. It follows directly from the structure.

A Greenwald–Khanna summary merges neighbouring tuples whenever the invariant allows, and the invariant allows a merge whenever the combined tuple’s rank uncertainty stays under $2\varepsilon n$. Out in the tail there are very few items per unit of value, so a tuple can absorb a large stretch of the value range while absorbing few enough items to stay under the cap. Whole swathes of the tail collapse into one tuple.

And the value a merged tuple keeps is the right-hand one — the larger. Merging tuple $i$ into tuple $i+1$ discards $v_i$ and keeps $v_{i+1}$. Applied repeatedly across the top of the distribution, the surviving representative of everything above some point is the largest value that was ever seen.

So the summary’s stored values are not a sample of the distribution. They are systematically the upper end of each merged group, and in a region where the distribution is thin that upper end can be enormously far from the group’s typical member. The rank is right by construction and the value is drawn from the wrong end of the interval on purpose.

The reversal #

Here is where it becomes a decision rather than a caution.

The previous essay matched the deterministic summary against a plain uniform sample of the same bits and the summary won at every size — 0.90% rank error against 3.52% at 7,392 bits. Score the same two structures on value error instead:

The ordering reverses. The structure with the better guarantee returns the worse numbers, by a factor of thirteen at the middle size, and the reason is the mechanism above: a sample’s stored values are drawn from the distribution and a merged summary’s are not. A uniform sample of 114 items from a log-normal stream contains items from the tail in the right proportion, and its 99th percentile is one of them.

On a Pareto stream the gap is wider still — 1,553% against 33% at 3,648 bits — and the direction never changes.

The other direction is also true #

It is worth completing the symmetry, because the asymmetry is easy to mistake for a defect in rank guarantees specifically.

A structure that promised a value guarantee — the number returned is within 1% of the true $q$-quantile" — would say nothing about the rank. On the two-cluster distribution, a value within 1% of 800.1 is anywhere in the upper cluster, and the upper cluster spans ranks 10,000 to 20,000: half the stream. A promise of 1% on the value would permit an answer whose rank was fifty per cent wrong.

So neither promise implies the other, in either direction, and which one is useful depends entirely on what the answer is for.

A rank promise is what a load-balancing or capacity decision wants. “Ninety-nine per cent of requests are below this” is a statement about a proportion of requests, and the proportion is what is being reasoned about.

A value promise is what a threshold or a comparison wants. “Is p99 above a second?” is a question about a number, and the number is what is being reasoned about.

The two are asked in the same words, by the same people, of the same dashboard.

Where the two coincide, exactly #

There is exactly one family of distributions on which the distinction vanishes, and naming it makes clear how special the coincidence is.

If the values are uniform on an interval, $Q$ is linear, $Q'$ is constant, and a rank error of $\varepsilon$ is a value error of $\varepsilon$ times the range. On the uniform stream measured above, the worst rank error is 1.77% and the worst value error against the range is 1.8% — the same number to the precision it is worth quoting.

Every other distribution separates them, and the direction of the separation is always the same: value error is larger wherever the density is low, which is always the tail, which is always where the interesting quantiles are. The distinction is worst exactly where quantiles are most used, and that is not bad luck — it is the same fact stated twice, since a quantile is interesting precisely where the density is too low to reason about by averages.

The case this actually breaks #

Tail latency, which is the single most common use of a streaming quantile summary anywhere.

A service records response times and reports p99 to a dashboard. Response times are log-normal-ish with a heavy tail, exactly the shape above. A summary at $\varepsilon = 0.02$ reports p99 as 2,170 milliseconds when the true p99 is 318, and its own guarantee is intact — the value it returned really does sit within 2% of the stream from the 99th percentile, because 2% of the stream is four hundred requests and the top four hundred requests span from 300 milliseconds to two seconds.

The consequences are worth spelling out because they are all in the same direction.

An alert threshold set at a second fires constantly. An engineer looking for the cause finds nothing, because there is nothing: the system’s actual 99th percentile is a third of a second. And the natural response — tighten $\varepsilon$ — helps far less than expected, because at $\varepsilon = 0.01$ the answer is still the stream maximum for $q = 0.999$ and the value error is 187%.

The general shape is one this site keeps meeting: a limit that is not a prediction, a permitted failure rate that nothing breached, a formula whose assumption is false and whose prediction holds. Every one of them is a true statement about a quantity that is not the quantity anybody wanted, and every one is invisible while the statement is being checked and the quantity is not.

How large the summary would have to be #

One more measurement, because “tighten the tolerance” is the first thing anybody tries and it is worth knowing what it would take.

To get the log-normal stream’s 99th percentile right to within 10% in value, the summary must not merge across the region where the value changes by 10% — which around $q = 0.99$ is a stretch of about two hundred items in twenty thousand, or 1% of the stream. That needs $\varepsilon$ of roughly 0.005, which is 150 tuples and 14,400 bits.

For the 99.9th percentile the same argument gives a stretch of about twenty items, $\varepsilon \approx 0.0005$, and around 1,500 tuples — 144,000 bits, which is a quarter of the cost of simply keeping every value in the stream.

The tolerance a value error requires scales with $1 - q$, and the state scales with its reciprocal. That is the precise sense in which a uniform-tolerance rank summary is the wrong structure for a tail query, and it is why the relative-error variants below exist at all rather than being a refinement nobody needed.

What to do about it #

Four options, in increasing order of how much they cost.

Use a sample when the value is what matters. It is simpler, it has no deterministic guarantee, and on the measurements above it returns better numbers at the same size. If the output is a dashboard rather than an admission-control decision, this is usually right.

Use a relative-error summary. Structures exist — biased quantile summaries, and the $t$-digest — whose promise is $\varepsilon q$ rather than $\varepsilon$, so the tolerance tightens automatically as $q$ approaches 1. They are the correct answer for p99 and they are not implemented here, because comparing a published accuracy figure against numbers measured under different conditions would be asserting a comparison rather than making one.

Report the rank that came back. A summary knows the rank interval of the tuple it returned. Reporting the value at rank $r \in [19{,}601, 20{,}000]$ is 2,169.8 is honest and is exactly as cheap as reporting the number alone.

Keep the values. Twenty thousand at 32 bits is 640,000, which is 87 times the summary. On a stream of twenty thousand that is a rounding error in a modern process; on a stream of twenty billion it is not, which is the only reason any of this exists.

The threshold question does not need a quantile at all #

The alerting case above is worth returning to, because the standard remedy list misses the cheapest repair by treating the wrong question as fixed.

Is p99 above one second? is not a request for a quantile. It is a request for a comparison, and comparisons of that shape have an exact answer that costs two integers:

$$p_{99} > T \iff \#\{v > T\} > 0.01\,n$$

Count the arrivals and count the arrivals above the threshold. If the second is more than a hundredth of the first, the 99th percentile exceeds $T$; otherwise it does not. No approximation, no tolerance, no distribution assumption, and eight bytes of state — against a summary of several thousand bits that answers the same question wrongly by a factor of six on the stream measured here.

The reason the exact answer is available is that a threshold test throws away everything the hard part of the problem was about. Estimating a quantile means locating a position in an order that is still arriving; testing a quantile against a fixed value means counting a predicate, and counting a predicate is the easiest thing a stream does. The difficulty was never in the tail — it was in not being told which value to compare against.

That reframes the dashboard case entirely. An alert threshold is known in advance, by definition: somebody typed it into the alerting rule. So the alert can be evaluated exactly, and the summary is needed only for the display — the number a human reads when they want to know roughly where the tail sits. Those two uses have completely different accuracy requirements and are almost always served by one structure, which is how a display-quality estimate ends up deciding whether to page somebody.

The generalisation is worth carrying past this subject. A question that names a value is a counting question and a question that names a rank is an ordering question, and only the second is hard. Several of the structures in this collection exist because a rank was wanted; a system that discovers it only ever wanted thresholds has been paying for the wrong problem, and the sentence that reveals it is usually already written in a configuration file.

The summary can bracket its own answer #

The third remedy above — report the rank interval that came back — is right, and it does not go as far as the structure allows. The summary can report an interval in the value as well, and that interval is a genuine bracket around the true quantile rather than a description of the uncertainty.

Every stored tuple carries a rank interval $[r_i, r_i + \Delta_i]$ and a value $v_i$ that occurred in the stream. Ranks are monotone in value, so two things follow immediately. If a stored $v_j$ has $r_j + \Delta_j < qn$, then the true $q$-quantile is at least $v_j$. If a stored $v_i$ has $r_i > qn$, then the true $q$-quantile is at most $v_i$. Taking the largest $v_j$ and the smallest $v_i$ satisfying those gives

$$v_j \;\le\; v_q \;\le\; v_i$$

with no assumption about the distribution and no additional state. It is one extra walk of a list that was walked anyway.

On the log-normal stream’s 99th percentile the returned answer is 2,169.8 against a true 318.3, and the bracket that accompanies it would run from somewhere around a hundred to the stream maximum. A number that is six times too large is a defect; a bracket a decade wide is a description of what the structure knows, and only one of those can be acted on correctly by a reader who was not told which distribution the stream came from.

The bracket is also the honest form of the essay’s central complaint. The summary is not wrong about the tail; it is uninformative about it, and the two are indistinguishable when a single number is reported. A wide bracket says this structure cannot resolve the value here at this tolerance, which is exactly the sentence a dashboard needs and exactly the sentence a point estimate cannot express.

Two limits on the idea, both worth stating. The bracket is not tight — it is bounded by the values that happen to be stored, so in a region the summary has merged flat it is as wide as the merged region, which is the whole subject of this essay reappearing as a width rather than as an error. And the bracket says nothing about the direction of the point estimate inside it: the table above shows the answer below the truth at $q = 0.05$ and far above it at $q = 0.99$, so the error is not one-signed and no correction factor exists to apply. What can be reported is the interval, which is why reporting it is the recommendation rather than adjusting the number.

The honest limit #

Two things this essay has not established.

It has not shown that Greenwald–Khanna is inaccurate. Every number it produced was inside its promise on every distribution tested, including at the quantiles where its value error was in the hundreds of per cent — the two facts are simultaneously true and that is the entire point.

And the reversal is measured on four distributions with one arrival order and one seed per size. The direction was the same in every case and the magnitude was not: the gap at 7,392 bits on the log-normal stream is nil, because at that size the sample’s own tail estimate happened to land on the same value. A structure whose advantage varies from thirteenfold to nothing across a sweep is one whose advantage should be measured on the stream at hand rather than taken from here.

What does generalise is the mechanism, and it needs no measurement at all: a promise about a position in a sorted order becomes a promise about a number only when multiplied by the local slope of the distribution, and nothing in the structure knows that slope.