Compose accuracy guarantees through arithmetic and comparisons over approximate values #669

Activity

1. zzylol commented on Oct 13, 2026

   

   zzylol

   on Oct 13, 2026

   ContributorAuthor

   More actions

   Theoretical error composition (first derivation)

   Notation: the true value is $x$ and the estimate is $\hat x$. A guarantee says $\Pr[\hat x \in I(x)] \ge 1-\delta$.

   1. Input guarantees by summary kind

   Kind	Summaries	Guarantee
   Exact	exact accumulators, raw recompute	$\hat x = x$, $\delta = 0$
   Additive, one-sided	Count-Min (non-negative updates)	$x \le \hat x \le x + \varepsilon N$, where $N$ is the total weight ($L_1$)
   Additive, two-sided	Count Sketch	$\lvert\hat x - x\rvert \le \varepsilon \lVert f\rVert_2$
   Relative value	DDSketch quantiles	$\lvert\hat v - v\rvert \le \alpha \lvert v\rvert$ (deterministic, as long as the bucket limit is not hit)
   Rank	KLL quantiles	$\mathrm{rank}(\hat v) \in [(q-\varepsilon)n,\ (q+\varepsilon)n]$, i.e. $Q(q-\varepsilon) \le \hat v \le Q(q+\varepsilon)$, where $Q$ is the empirical quantile function

   2. General rule: interval arithmetic plus a union bound

   Suppose each input satisfies $x_i \in [L_i, U_i]$ with failure probability $\delta_i$. Then $f(\hat x_1, \dots, \hat x_k)$ lies in the interval extension of $f$ over $\prod [L_i, U_i]$. The failure probability is $\le \sum_i \delta_i$ (union bound). When $f$ is monotone in each argument, the bound is attained at the corners.

   Two refinements of the failure probability:

   • Shared summary. If several inputs read the same summary instance and it was sized for a simultaneous guarantee (e.g. KLL sized for all quantiles at once), its $\delta$ counts once, not once per input.
   • Many groups. A vector result evaluates one point per group or series. Per-point guarantees (CMS, Count Sketch) then give $G\delta$ over $G$ groups, unless the summary gives a simultaneous guarantee over all keys.

   3. Operators with absolute errors $e_x, e_y$ (meaning $\lvert\hat x - x\rvert \le e_x$)

   Operator	Error bound of the result
   $x \pm y$	$e_x + e_y$ (tight, since the errors can align). Two one-sided CMS inputs give a two-sided error for $x - y$, in $[-\varepsilon N_y,\ \varepsilon N_x]$
   $-x$, $x + c$, $c \cdot x$ (with $c$ a literal or time())	$e_x$, $e_x$, $\lvert c\rvert e_x$
   $x \cdot y$	$\lvert \hat x\rvert e_y + \lvert \hat y\rvert e_x + e_x e_y$
   $x / y$, when $\lvert\hat y\rvert > e_y$	$\dfrac{\lvert \hat x\rvert e_y + \lvert \hat y\rvert e_x}{\lvert\hat y\rvert(\lvert\hat y\rvert - e_y)}$. Unbounded (None) when the interval for $y$ contains 0
   min, max, clamp(x, lo, hi)	1-Lipschitz: $\max(e_x, e_y)$, and $\max(e_x, e_{lo}, e_{hi})$ for clamp
   sum over $k$ groups	$\sum_i e_i$
   avg over $k$ groups	$\frac{1}{k}\sum_i e_i$

   4. Relative errors

   • Product. The relative error is $(1+\alpha_x)(1+\alpha_y) - 1 \approx \alpha_x + \alpha_y$.
   • Ratio. The relative error is $\frac{1+\alpha_x}{1-\alpha_y} - 1$.
   • Difference. The absolute error is $\alpha_x\lvert x\rvert + \alpha_y\lvert y\rvert$. The relative error of the difference is $\frac{\alpha_x\lvert x\rvert + \alpha_y\lvert y\rvert}{\lvert x - y\rvert}$, which is unbounded as $x \to y$ (cancellation). So a relative target on a difference cannot be guaranteed from relative-error inputs alone. An absolute target can be.

   5. Rank errors (KLL): the example in this issue

   KLL bounds the rank, not the value. For $\hat v_{0.99} - \hat v_{0.5}$, with rank errors $\varepsilon_1$ and $\varepsilon_2$ and the function decreasing in its second argument:

   $$Q(0.99-\varepsilon_1) - Q(0.5+\varepsilon_2) ;\le; \hat v_{0.99} - \hat v_{0.5} ;\le; Q(0.99+\varepsilon_1) - Q(0.5-\varepsilon_2)$$

   The failure probability is $\le \delta_1 + \delta_2$, or $\delta$ once if both quantiles come from one KLL sized for a simultaneous guarantee. This applies to all three forms in this issue: the vector form, the scalar() form, and scalar(q99) - scalar(q50).

   • This interval is valid, but its width in value units depends on the data (on $Q$ near 0.99 and 0.5). A difference has no rank meaning, so it cannot be stated as "rank error $\varepsilon$".
   • So for rank-error inputs the combined guarantee is either:
     • a rank-interval guarantee: the same expression evaluated at quantile levels shifted by at most $\pm\varepsilon_i$, toward the corners given by $f$'s monotonicity. Stage 3 converts it to a value width using data statistics, e.g. the study's empirical distribution; or
     • None, if Stage 3 has no such statistics.
   • For non-monotone $f$ (e.g. $\lvert x - y\rvert$), take the min and max of $f$ over the box of shifted levels.

   6. Comparisons and predicates (filters, bool, value HAVING, topk membership)

   A comparison $\hat x > t$ is correct for every group whose true value is outside the band $[t - e^{+},\ t + e^{-}]$. Here $e^{+}$ and $e^{-}$ are the input's over- and under-estimation bounds. Groups inside the band may flip.

   • The guarantee is a band guarantee: no misclassification outside the band, with probability $1 - G\delta$ over $G$ groups, or $1 - \delta$ under a simultaneous guarantee. It is not an error on the output value.
   • This matches the decision for value HAVING (guarantee None for value error). A band guarantee is the stronger, precise form, if Stage 3 wants it.
   • The threshold can itself be approximate, as in rate(a) > scalar(q99) - scalar(q50). Then the band widens by the threshold's error: $e_t$ from §3 for absolute errors, or the rank interval from §5.

   7. Proposal for #575 / Stage 3

   1. The guarantee type: Exact | Abs { e, delta } | Rel { alpha, delta } | RankInterval { levels, delta } | Band { e_plus, e_minus, delta } | None.
   2. Compose through operators with §3–§6. Abs and Rel compose in closed form. RankInterval passes through monotone operators. Division by an interval that contains 0, and a relative target on a difference, give None.
   3. Count $\delta$ once per distinct summary instance and per evaluated point, unless the summary gives a simultaneous guarantee.
   4. Stage 3 checks the composed guarantee against the entry's target. For RankInterval or Band it uses data statistics to turn the result into value terms, or treats it as None.
   5. Pass 1 / Stage 1 never prune a candidate because of how its output is combined.

   Open questions:

   • Should the user-facing accuracy target for a combined expression be absolute, relative, or "rank-interval"?
   • In the MVP, should RankInterval be evaluated with study statistics, or simply be None?
2. zzylol commented on Oct 13, 2026

   

   zzylol

   on Oct 13, 2026

   ContributorAuthor

   More actions

   Decision (2026-10-13): in the MVP, a RankInterval guarantee is treated as None. Stage 3 does not yet convert rank intervals into value widths using data statistics.
3. zzylol

   added 11 commits that reference this issue on Oct 13, 2026

   fix(planner): plan structurally identical scalar references once

   ...

   c5e9270

   refactor(planner): plan the workload on the unified operator IR (#542)

   ...

   eb2799f

   feat(planner): give composed Stage 1 candidates theoretical guarantees

   ...

   843a607

   fix(planner): keep summary candidates for combinations of approximate…

   ...

   dd53f37

   feat(planner): give composed logical ASAP candidates theoretical guar…

   ...

   bf89005

   fix(planner): keep summary candidates for combinations of approximate…

   ...

   32d5183

   fix(planner): read empirical output accuracy from deployment evidence…

   ...

   139ff71

   fix(planner): read empirical output accuracy from deployment evidence…

   ...

   9e3e6e9

   feat(planner): compose candidate logical ASAP DAGs from Pass 1 per-co…

   ...

   156ffb8

   fix(planner): read empirical output accuracy from deployment evidence…

   ...

   7fcd2af

   feat(planner): physical ASAP-aware optimization and plan selection fo…

   ...

   f30a399
4. zzylol commented on Oct 13, 2026

   

   zzylol

   on Oct 13, 2026

   ContributorAuthor

   More actions

   Implementation pointers. #676 keeps the legacy accuracy-composition code as library code that the planning stages do not call yet, so this issue can build on it:

   • accuracy/composition.rs, AccuracyModel::propagate, PropagationStats and QuantileInputDomain: propagation rules through operators.
   • accuracy/allocation.rs: splitting an error budget across nested summaries.

   Wiring them into Stage 1 composition (composed_guarantee) is the work tracked here. A top-k membership (band) guarantee also belongs here: #589 and #593 bound item frequencies and weights, not membership.