Propagate end-to-end accuracy guarantees for approximate-over-approximate plans

Context

ASAPPlanner can structurally nest SummaryAgg nodes, but selected post-ASAP plans need machine-readable end-to-end error guarantees. Approximate parents must not consume approximate children unless their composed guarantee satisfies the callers existing AccuracyTarget`.

Accuracy legality and cost ranking are separate responsibilities.

Required planning pipeline

candidate generation
    -> guarantee propagation
    -> AccuracyTarget satisfaction check
    -> legal candidates only
    -> cost ranking/global selection

CostModel must not override accuracy legality.

Accuracy model and typed guarantees

The deployment-extensible AccuracyModel supplies local guarantees, propagates them through a CompositionOperator, and checks the result against AccuracyTarget. Guarantees retain typed metrics rather than reducing every error to an unqualified epsilon:

#[non_exhaustive]
enum ErrorMetric {
    AbsoluteValue,
    RelativeValue,
    Rank,
    Cardinality,
    Frequency,
    L2Frequency,
    TopKMembership,
}

struct ResultGuarantee {
    metric: ErrorMetric,
    bound: BoundExpr,
    failure_probability: ProbabilityExpr,
    provenance: Vec<GuaranteeSource>,
}

BoundExpr and ProbabilityExpr are serializable expression vocabularies. Provenance records selected parameters, child guarantees, composition steps, runtime observations, and unavailable statistics. Caller-visible guarantees belong on finalized/readout values; exact outputs have zero error.

Core propagation rules

The default model is conservative and fail-closed:

Exact input contributes zero bound and zero failure probability.
Compatible additive/Lipschitz errors compose bounds additively and probabilities by union bound.
Supported non-negative relative errors compose as e_inner + e_outer + e_inner * e_outer.
Exact sum over approximate values sums bounds; exact extrema take the maximum bound.
Incompatible rank, cardinality, frequency, value, L2-frequency, and membership metrics require an explicit conversion rule.
Unknown statistics remain unknown; unsupported compositions keep the raw/pre-ASAP alternative.

TopK membership requires widened per-key confidence intervals and is certified only when:

min_lower_bound(selected_top_k)
    > max_upper_bound(non_selected)

CountSketch uses an L2-frequency theorem and must never reuse CMS`s L1 theorem.

Accuracy-budget allocation

The full root epsilon/delta must not be allocated independently to every approximate layer. An AccuracyBudgetAllocator enumerates finite allocations; each allocation produces parameters through existing sizing, and candidates whose propagated guarantees miss the target are rejected before global selection.

Initial additive allocation may split epsilon and delta evenly across approximate layers. Root QueryRequirements.accuracy and explicitly supplied local AggIntent.accuracy must have documented precedence.

Cost model

Accuracy allocation changes state/update/read costs, but correctness filtering happens first. Recurring costs use explicit units and rates; shared state is counted once. One-shot plus recurring work requires an explicit horizon. Unknown statistics must not become zero.

Acceptance criteria

PR #303 implementation status

PR #303 implements the four requested Planner-side guarantees. ASAPPlanner remains a mathematical planner and does not import asap_sketchlib; runtime observations are a separate evidence source that can instantiate symbolic terms later.

Completed in ASAPPlanner

TopK membership-margin certificates: carry widened selected/excluded boundary intervals and their union-bound failure probability; certify only strict separation and reject missing, invalid, or overlapping evidence.
CountSketch L2 sizing and propagation: add L2Frequency, sqrt(3 / width) * ||f||_2, epsilon-derived width, delta-derived odd median depth, and a conservative Hoeffding failure bound. CMS posterior L1 relaxation is not reused.
Hydra shared-grid composition: add inner and outer collision bounds and union-bound their failure probabilities. Deployment/data-dependent leaves stay symbolic and fail closed until instantiated.
KLL/HLL/KMV/Theta confidence: attach conservative 99%-confidence contracts to committed parameters; reject tighter unsupported confidence and targets missed because of parameter caps.
Check parameter-derived guarantees against targets even for exact inputs, before cost ranking.
Add unit/integration coverage and document the contracts.

Remaining evidence/runtime integration

Feed runtime or planning-time TopK boundary intervals into PropagationStats; static candidates remain rejected without evidence.
Instantiate CountSketch stream-L2 and Hydra shared-grid symbolic statistics from a serving implementation when concrete absolute bounds are required.
Add an implementation-specific amplification/confidence model if confidence tighter than the built-in 99% contract is required.
Preserve imported evidence as GuaranteeSource::RuntimeObservation and export it through DAG JSON.
Keep affected candidates fail-closed when required evidence is unavailable.

Non-goals and related follow-up

Do not add a second correctness-policy enum.
Do not assume statistical independence by default.
Do not claim arbitrary cross-sketch or nonlinear composition.
Advanced nonlinear and correlation-aware error propagation #297 tracks nonlinear and correlation-aware propagation.
Exact/archive fallback execution and runtime integration remain separate from Planner mathematics.

docs(l4): reframe #171/#172 proposal as a shared accuracy algebra, fo…

docs(l4): separate the design from which issue it solves; norm-aware …

docs(l4): replace unified accuracy algebra with three grounded compos…

docs(l4): a taxonomy and recipe for composing summaries (bespoke) (#174)

docs: add an Interface section to each L1-L5 doc (#169)

Related open work

Paired with exact/summary representation work in Compose exact operators with summary plans across explicit update/readout boundaries #171.
Posterior error primitives are tracked by Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21 #239.
Roll-up-specific accuracy composition is tracked by Support accuracy-aware approximate Count roll-ups #278.
Structured nested summary kinds are tracked by Multi-dimensional / structured summary kinds (e.g. QTree-style range trees, Hydra-style sketch composition) #173.

Rewritten scope and proposed stacked-PR design

Current-code audit

The original issue is directionally correct but should not be implemented by merely passing a child epsilon into CostModel::size_params:

AccuracyTarget::{Exact, Epsilon, EpsilonDelta} already models the caller's accuracy requirement; do not add another correctness-policy model.
SummaryAgg can already nest structurally, so unsafe approximate-over-approximate plans can be constructed today.
SummaryNode/SummaryEstimate carries no machine-readable output guarantee or error provenance.
posterior CMS/CU/CountSketch bound functions now exist under post_asap::query_time::error_estimation, but they are runtime observations, not a general composition algebra.
Support accuracy-aware approximate Count roll-ups #278 is the specialized roll-up instance of the same “compose guarantees before declaring a candidate legal” problem.

The missing functionality is therefore:

represent the guarantee produced by each selected summary readout;
propagate guarantees through explicitly supported compositions;
reject nested approximate candidates when no sound propagation rule exists;
compare the composed guarantee with the existing root AccuracyTarget before cost ranking.

Architectural boundary

Accuracy legality and cost ranking must remain separate:

candidate generation
    -> guarantee propagation
    -> AccuracyTarget satisfaction check
    -> legal candidates only
    -> cost ranking/global selection

Do not put correctness decisions into CostModel. Introduce a separate deployment-extensible accuracy algebra:

trait AccuracyModel {
    fn local_guarantee(
        &self,
        family: &SummaryFamilyType,
        query: &SketchQuery,
        params: &SummaryParams,
    ) -> Option<ResultGuarantee>;

    fn propagate(
        &self,
        op: &CompositionOperator,
        inputs: &[ResultGuarantee],
        local: Option<&ResultGuarantee>,
        stats: &PropagationStats,
    ) -> Result<ResultGuarantee, AccuracyError>;

    fn satisfies(
        &self,
        guarantee: &ResultGuarantee,
        target: &AccuracyTarget,
    ) -> bool;
}

CostModel ranks only candidates for which satisfies is true. A deployment can provide both models, but one trait must not silently override the other.

Guarantee representation

Do not reduce every sketch to one untyped epsilon. Error metrics are not interchangeable:

#[non_exhaustive]
enum ErrorMetric {
    AbsoluteValue,
    RelativeValue,
    Rank,
    Cardinality,
    Frequency,
    TopKMembership,
}

struct ResultGuarantee {
    metric: ErrorMetric,
    bound: BoundExpr,
    failure_probability: ProbabilityExpr,
    provenance: Vec<GuaranteeSource>,
}

BoundExpr/ProbabilityExpr should be a small serializable expression vocabulary rather than a prose string, so planner-time symbolic bounds can later be instantiated using cardinality/fanout/runtime posterior observations.

Examples of GuaranteeSource:

AccuracyTarget and selected sketch parameters;
deterministic exact/zero error;
composed child node IDs;
union-bound step;
posterior runtime observation from Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21 #239;
required but unavailable statistic.

Attach the guarantee to the readout/value edge, not only to SummaryAgg state:

struct SummaryNode {
    expr: SummaryExpr,
    schema: SummarySchema,
    guarantee: Option<ResultGuarantee>,
}

Summary-state edges may carry a state capability/error model, but a caller-visible result guarantee belongs after SummaryEstimate or another finalized readout.

Sound default propagation rules

The first implementation should be deliberately conservative.

Exact input

B_exact = 0
delta_exact = 0

Composing an approximate operator over an exact input preserves only the outer local guarantee.

Additive absolute errors

Without an independence assumption:

B_total <= B_inner + B_outer
delta_total <= delta_inner + delta_outer

The delta formula is the union bound. Do not multiply probabilities unless the model explicitly establishes independence.

For a deterministic L-Lipschitz transformation:

B_output <= L * B_input + B_local
delta_output <= delta_input + delta_local

Relative errors

For compatible non-negative multiplicative guarantees:

(1 + epsilon_total)
    = (1 + epsilon_inner) * (1 + epsilon_outer)

epsilon_total
    = epsilon_inner + epsilon_outer + epsilon_inner * epsilon_outer

Sign changes, values near zero, and incompatible relative/absolute metrics require an explicit conversion proof or rejection.

Aggregating several approximate children

For exact sum over finalized estimates:

B_sum <= sum(B_i)
delta_sum <= sum(delta_i)

For exact max/min value bounds:

lower_max = max(lower_i)
upper_max = max(upper_i)

This bounds the returned value but does not necessarily identify the true winning key.

TopK over approximate values

Do not claim TopK membership accuracy by adding epsilons. Given per-key intervals [lower_i, upper_i], membership is certified only when the selected boundary is separated:

min_lower_bound(selected_top_k)
    > max_upper_bound(non_selected)

If an outer frequency sketch adds error, widen each interval by its compatible outer bound before applying this test. When the margin condition fails:

the candidate cannot claim exact TopK membership;
it may expose a weaker explicitly modeled guarantee if AccuracyTarget semantics support it later;
otherwise it is illegal and Planner keeps the pre-ASAP/raw alternative.

Incompatible metrics

Examples such as HLL cardinality error fed into a CMS frequency guarantee, or quantile rank error fed into value-additive logic, require a registered cross-metric propagation rule. The default is AccuracyError::UnsupportedComposition, never “treat child as exact.”

Budget allocation and candidate enumeration

Do not assign the full root epsilon independently to every approximate layer. For a root target (epsilon, delta), generate a finite set of local budget splits:

sum(epsilon_i) <= epsilon_total       // additive-bound case
sum(delta_i) <= delta_total           // union-bound case

Start with a deterministic conservative allocator:

epsilon_i = epsilon_total / approximate_layer_count
delta_i   = delta_total / approximate_layer_count

Expose allocation as a separate hook because equal splitting is rarely cost-optimal:

trait AccuracyBudgetAllocator {
    fn allocations(
        &self,
        target: &AccuracyTarget,
        composition: &CompositionShape,
    ) -> Vec<AccuracyAllocation>;
}

Each allocation produces candidate parameters through the existing sizing path. Search retains only candidates whose propagated guarantee satisfies the root target; global_selection then chooses by cost.

Existing per-node AggIntent.accuracy remains the local declared requirement where explicitly supplied. The workload/root QueryRequirements.accuracy, when present, is the end-to-end target. This PR must document precedence and must not silently reinterpret every frontend-copied per-node target as an already valid end-to-end allocation.

Cost model

For a two-layer maintained composition, use cost units per second:

nested_summary_cost_rate =
    inner_update_rate * inner_maintenance_cost_per_update
  + intermediate_emit_rate * (
        inner_readout_cost
      + outer_update_cost_per_item
    )
  + evaluation_rate * outer_readout_cost

Raw fallback:

raw_recompute_cost_rate =
    evaluation_rate * raw_recompute_cost

For shared repeating consumers:

evaluation_rate = sum(1 / query_interval_i)

State accounting:

nested_state_bytes =
    distinct_inner_state_bytes
  + distinct_outer_state_bytes

Shared state is counted once. If one-shot and recurring work are compared over horizon H:

total_cost(H) = recurring_cost_rate * H + one_shot_cost

Accuracy allocation affects sketch parameters and therefore maintenance/state/readout costs. Cost ranking happens after legality for each allocation. Every estimate carries unit, input provenance, and model version; missing statistics are unknown, not zero.

Recommended stacked PRs

PR 1 — Represent guarantees and fail closed

Add ErrorMetric, symbolic bound/probability expressions, provenance, and ResultGuarantee.
Attach guarantees to finalized post-ASAP value nodes.
Exact results receive the zero-error guarantee.
Sketch readouts receive a family-specific local guarantee derived from selected parameters.
Detect approximate child → approximate parent composition.
Reject it with a typed unsupported-composition reason unless an AccuracyModel rule exists.
Export the guarantee and rejection provenance through DAG JSON.

This PR fixes the current correctness risk even before any composition is admitted.

PR 2 — Conservative same-metric propagation

Add AccuracyModel and default additive/relative/union-bound rules.
Implement root-target satisfaction checks.
Implement equal budget splitting as the initial allocator.
Enumerate parameterized candidates for each legal allocation.
Reuse the algebra in Support accuracy-aware approximate Count roll-ups #278 instead of implementing separate roll-up arithmetic.

PR 3 — TopK stability and runtime posterior refinement

Represent per-key intervals required by the TopK margin certificate.
Admit TopK-over-approximate candidates only when membership or an explicitly requested weaker guarantee is provable.
Allow posterior bounds from Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21 #239 to tighten a runtime guarantee/provenance record.
Runtime observations may trigger Feed observed posterior sketch error back into re-planning (execution-time → planning-time loop) #250 replanning, but must not retroactively justify a planner candidate that lacked a sound planning-time contract.

Tests

Approximate child under approximate parent is rejected by default, not silently treated as exact.
Exact child contributes zero error.
Additive bounds and delta union bounds compose correctly.
Relative-error multiplication includes the cross term.
Incompatible metrics are rejected.
Equal budget allocation respects the root epsilon/delta.
A candidate whose composed bound exceeds the root target is absent before cost ranking.
A legal tighter/more-expensive candidate can beat an illegal cheaper candidate because legality precedes cost.
TopK margin-separated fixture is accepted; overlapping-interval fixture is rejected/falls back.
Shared nested summaries are costed and stored once.
DAG export contains metric, bound expression, failure probability, provenance, allocation, and rejection reason.

Acceptance criteria

No selected approximate-over-approximate plan lacks a machine-readable end-to-end guarantee.
The composed guarantee is checked against the existing root AccuracyTarget.
Unsupported or unprovable composition keeps the pre-ASAP/raw candidate.
CostModel cannot override accuracy legality.
Supported compositions use documented formulas and typed metrics rather than unqualified epsilon addition.
Support accuracy-aware approximate Count roll-ups #278 can reuse the same propagation primitives for approximate roll-ups.
Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21 #239 posterior bounds integrate as explicit runtime evidence, not as an implicit planning assumption.
No new protocol-specific correctness or scheduling model is added.

Non-goals

Adding another CorrectnessPolicy; AccuracyTarget remains authoritative.
Guaranteeing arbitrary cross-sketch compositions in the first PR.
Assuming independence between sketch errors by default.
Implementing exact/archive fallback access inside ASAPPlanner.
Prometheus alert-threshold or rule-group semantics.

Merge pull request #299 from ProjectASAP/feat/accuracy-guarantee-prop…

PR #299 (guarantee representation, fail-closed legality, conservative propagation, and budget allocation) has merged after reconciliation with current recurrence and cross-consumer accuracy work. This issue remains open for the explicitly deferred TopK membership-margin certificate/runtime-observation phase described in the PR.

Merge pull request #303 from ProjectASAP/review-pr-299-work

Propagate end-to-end accuracy guarantees for approximate-over-approximate plans #172

Description

Context

Required planning pipeline

Accuracy model and typed guarantees

Core propagation rules

Accuracy-budget allocation

Cost model

Acceptance criteria

PR #303 implementation status

Completed in ASAPPlanner

Remaining evidence/runtime integration

Non-goals and related follow-up

Activity

zzylol commented on Aug 26, 2026

Related open work

zzylol commented on Aug 26, 2026

Rewritten scope and proposed stacked-PR design

Current-code audit

Architectural boundary

Guarantee representation

Sound default propagation rules

Exact input

Additive absolute errors

Relative errors

Aggregating several approximate children

TopK over approximate values

Incompatible metrics

Budget allocation and candidate enumeration

Cost model

Recommended stacked PRs

PR 1 — Represent guarantees and fail closed

PR 2 — Conservative same-metric propagation

PR 3 — TopK stability and runtime posterior refinement

Tests

Acceptance criteria

Non-goals

zzylol commented on Aug 28, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions