Skip to content

(K): tighten the failure-probability big-M ceilings (RangeHeavy-8users-counter plans 2x slower) #1413

Open

Description

@zzylol

Problem, by example

Planning the RangeHeavy 8-user workload over a counter metric (rangeheavy-8users-counter, the paper-eval workload file) takes twice as long once constraint (K) checks the union bound over estimates (#1405), with the same MILP size and the same plan cost:

Planner MILP variables / constraints Planning wall time (release asap_planner --run-until stage3, one core, median of 5) Objective (cost/s)
main before #1405 5,057 / 11,245 13.76 s 9996.96734858
#1360 (old (K): one D per execution) 4,337 / 9,805 11.59 s 9996.96736909
#1405 ((K) with P and W) 4,337 / 9,805 22.21 s 9996.96728911

RangeHeavy-8users (no counter) shows the same effect, smaller: 9.20 s → 11.16 s, again 4,297 / 9,680 in both. RollupHeavy-8users is unchanged (19.5 s).

What should happen: the stricter check should cost about what the old one did, since it adds no variables or rows here.

Why it happens (likely cause, not yet profiled)

(K) bounds each execution's failure probabilities with big-M rows (crates/stage3-plan-selection/src/milp/accuracy.rs, chosen_producers and at_most_when_answering):

HW_{c,i} >= W_u - M^W_u (1 - y_{u,c,i})

where M^W_u is the largest W any selection gives u (ErrorModel::set_ceilings, each input taking its largest producer's ceiling). A readout's W is R · δ (its estimates per evaluation times its required δ), and Pass 2 adds looser readout copies for other queries (δ up to 0.01 and more), so a consumer above a readout of 1,000 series read at δ 0.01 has M^W = 10 while a whole-result root at δ 0.01 checks it against 0.01. The old (K) summed only δ per execution, so its ceilings were about 1,000 times smaller. With M far above the limit, the LP relaxation of these rows is weak (with y fractional, W_u − M(1 − y) is far below the limit), which would make branch-and-bound explore more. A first step is to log the ceilings and the solver's node count on this workload.

Measured alternative that did not help: dividing every failure probability (readout terms and root limits) by the smallest root limit, so the tightest limit is 1. On the same host it made RangeHeavy-8users 10% slower (10.3 s → 11.4 s) and the counter variant 48% slower (20.9 s → 30.8 s).

Proposal

Tighten the ceilings without changing which selections are feasible:

  1. Per execution, compute the largest root limit (widened by tolerated_limit) among the roots that check its P or W through some path (the same walk as ErrorModel::set_checked_failure_probabilities). When every query that can select the execution checks that term, a value above that limit makes every selection through it infeasible, so the ceiling can be clamped to it, with W_u ≤ limit added only in that case.
  2. Alternatively, leave out readout copies whose own W (constant) is above every root limit that reads it: no selection can use them for a query with a δ, and they only widen ceilings.

Option 2 is simpler and does not touch the rows; option 1 also covers non-readout executions.

Scope and acceptance

Status

Accepted as is for #1405 on 2026-11-17 (optimizer efficiency is deferred); this issue tracks the follow-up. Related: #1405, #1400, #1401.

Activity

  1. added
    accuracyAccuracy requirements, guarantees, and propagation
    enhancementNew feature or request
    optimizerWorkload optimization and plan selection
    on Nov 17, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    accuracyAccuracy requirements, guarantees, and propagationenhancementNew feature or requestoptimizerWorkload optimization and plan selection

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions