Source-linked AI summary
Incremental Delta-Shapley: A Standalone Runtime for Predicate Attribution on Sliding Windows
Pouya Khani, Ira Assent
TL;DR
IDS addresses the lack of timely predicate-level explanations for sliding-window aggregates by turning closed-form Shapley attribution into a standalone runtime with incremental summaries and mechanisms for unregistered predicates. It matches exhaustive attribution to floating-point precision, achieves up to 4.3×10^5 speedup over per-window scans, and reduces adaptive ad hoc cost by up to 9.2×.
Problem
Sliding-window aggregate systems report aggregate changes but do not identify which predicates account for them while the relevant window remains active.
Method
IDS incrementally maintains global, marginal, and atom summaries from window deltas, evaluates closed forms in constant time, and answers unregistered predicates through scans, indexes, or sampling.
Results
Attribution matches exhaustive Shapley enumeration to floating-point precision; incremental maintenance reaches up to 4.3×10^5× speedup over per-window scans, while adaptive promotion cuts ad hoc cost by up to 9.2×.
Takeaways & Limitations
The runtime makes predicate attribution and per-slide attribution change available as deployable operators for active sliding windows, including overlapping and previously unregistered predicates.
Takeaways & Limitations
IDS is evaluated as a standalone single-node library through deterministic offline replay; distributed execution, fault tolerance, exactly-once processing, and production DSMS integration are out of scope.
Abstract
from arXiv · showhide
Continuous aggregate queries over sliding windows are common in real-time analytics, but most systems report \emph{what} an aggregate is doing without attributing \emph{which} predicates account for the result. A companion paper~\cite{khani2026closedformpredicatelevelshapleyattribution} shows that exact predicate-level Shapley attribution for SUM, COUNT, AVG, and variance needs only three additive predicate summaries with closed-form coefficients. Those results settle the mathematics, not how a runtime maintains summaries across slides, exposes attribution, answers unregistered predicates, or amortizes repeated ad hoc ones. We present \textbf{IDS} (Incremental Delta-Shapley), a standalone single-node runtime that turns those closed forms into a deployable explanation system. IDS consumes window-maintenance deltas, updates global, marginal, and atom summaries, and evaluates any closed form in constant time. Overlapping predicates use atomic refinement, and a restricted SQL-like API exposes attribution and its per-slide change as first-class operators. Unregistered predicates are answered by a retained-state scan, an inverted index, or an amortized sliding-window sample with concentration guarantees; frequent ones are promoted by rebuilding the refinement. On synthetic, adversarial, NEXMark-style, and NYC taxi workloads, attribution matches exhaustive Shapley enumeration to floating-point precision; incremental maintenance is flat in $N$ and up to $4.3\times10^{5}\times$ faster than per-window scans of the same form; and adaptive promotion cuts ad hoc cost by up to $9.2\times$ on Zipfian traces.
1 Introduction
IDS addresses the systems problem left open by closed-form predicate attribution: maintaining explanations across sliding-window updates and serving registered, compositional, and ad hoc queries. It packages delta maintenance, atomic refinement, a query API, and mechanisms for unregistered predicates into a standalone runtime.
- Closed forms settle predicate attribution mathematically, but not how a streaming runtime maintains state, exposes queries, handles unregistered predicates, or amortizes promotion.
- Unregistered predicates are supported through retained-state scans, optional indexes, or sampling, while repeated ad hoc predicates can be promoted by rebuilding the refinement.
- IDS consumes window-maintenance deltas and updates global, predicate, and atom summaries instead of recomputing overlapping windows from scratch.Its maintenance cost is O(|Δ_t| K) for K registered predicates and O(|Δ_t|) per predicate.
- Atomic refinement answers arbitrary Boolean combinations of overlapping registered predicates from active atoms while preserving Efficiency over the atom partition.
- A restricted SQL-like API exposes REGISTER PREDICATE, SHAPLEY_ATTRIBUTE, and SHAPLEY_DELTA as first-class operators.
2 Background: What the Engine Evaluates
IDS evaluates predicate-level Shapley attribution using the companion paper’s closed forms over sliding-window summaries. The engine adopts the sum-of-member-values semantics and exploits affinity in three additive predicate summaries.
- Predicate attribution sums tuple Shapley values over the tuples matching a Boolean predicate, which IDS distinguishes as registered or ad hoc as the stream evolves.
- For SUM, COUNT, AVG, and both variance games, closed forms use global summaries, predicate summaries, and running harmonic numbers without coalition enumeration.
- With global N, A(W), and B(W) fixed, each closed form is affine in the predicate summaries m_P, A_P, and B_P.
- Affinity enables exact additive state maintenance, composition by adding disjoint-group summaries, and unbiased attribution estimates from unbiased summary estimates with concentration guarantees.
3 IDS Architecture
IDS maintains attribution state incrementally from window deltas, retaining marginal and atom summaries alongside optional active-window structures. The slide loop applies signed additive updates and refreshes harmonic state before evaluating requested closed forms.
- IDS comprises delta-maintained attribution summaries, a predicate/atom registry, optional retained active-window state, and running harmonic numbers.
- The runtime accepts insertions and expirations from replay, live sources, or upstream changelogs, with count- and time-based windows represented as signed delta batches.
- Global, marginal, and atom summaries are maintained for the window, registered predicates, and Boolean signatures of overlapping predicates.
- The evaluator computes attribution only after assembling active-window summaries, and compensated summation plus an Efficiency check address numerical drift and correctness.
- 3.3 The Slide Loop: Each entering tuple adds (1, y, y^2) and each leaving tuple subtracts the same triple from every satisfied summary, giving O(|Δ_t|) work per affected predicate.
- 3.3 The Slide Loop: Harmonic numbers are updated incrementally when cardinality changes, while optional samples, indexes, and retained expiry state support ad hoc processing.
4 Maintaining the Atomic Refinement
IDS maintains overlapping registered predicates through atomic refinement, while marginal summaries accelerate common single-predicate lookups. It compacts inactive atoms and merges matching atom summaries before evaluating compositional attribution.
- Atomic refinement partitions the active window by each tuple’s K-bit predicate signature, making Boolean combinations disjoint unions of matching atoms.This prevents overlapping predicates from counting tuples multiple times and supports intersections, unions, complements, and set differences.
- Per-slide updates add or subtract each affected tuple’s summary triple from global, marginal, and atom state.The maintained state includes count, value sum, and squared-value sum summaries.
- Marginal summaries reduce registered single-predicate attribution from O(|S_W|) atom aggregation to O(1) lookup.IDS updates one marginal triple per registered predicate in the same pass over each maintenance delta.
- IDS merges matching atom summaries before one closed-form evaluation for compositional queries, retaining per-atom evaluation as a cross-check.The two strategies are asserted to agree in the test suite.
- Atom-table size follows the number of active signatures, with zero-count atoms reclaimed; it can range from 12 to N depending on predicate structure.When the atom state remains too large, IDS materializes explicitly enumerated intersections and falls back to scans or approximation for other combinations.
5 Declarative Query API
IDS exposes predicate attribution through a restricted SQL-like interface that registers predicates and evaluates current-window or consecutive-window attribution through compiled closed forms.
- Analysts register predicates declaratively and invoke SHAPLEY_ATTRIBUTE for current-window attribution or SHAPLEY_DELTA for its consecutive-window change.SHAPLEY_DELTA supports alerting on changes between adjacent windows.
- Compilation maps registered predicates to membership functions and initializes or rebuilds their summaries before closed-form evaluation.Predicates registered after stream start are bootstrapped through an exact retained-state atomic-refinement rebuild.
- Compositional attribution over registered predicates is answered exactly from atom-level summaries through the same declarative query surface.The interface supports combinations such as conjunctions, complements, and disjunctions.
SELECT
The query examples show continuous attribution for Boolean combinations of registered predicates, while the runtime interprets delta attribution as consecutive current-window change rather than a separate delta game.
- SELECT: The API expresses conjunction, complement, and disjunction attribution as SHAPLEY_ATTRIBUTE calls over a sliding-window AVG query.The examples cover region_eu AND tier_premium, region_eu AND NOT tier_premium, and region_eu OR region_us.
- SELECT: SHAPLEY_DELTA reports consecutive current-window changes in ΦP and is used for alerting, rather than defining a separate delta game.
6 Ad Hoc Predicate Mechanisms
IDS answers unregistered predicates through exact scans, applicable indexes, or sliding-window samples, choosing among exactness, selectivity, retained state, and throughput trade-offs.
- Mechanism 1: Retained State Scan: Exact retained-state scans evaluate an ad hoc predicate over active tuples, accumulate its three summaries, and then apply the closed form in O(1).The overall exact query costs O(N) and serves as the correctness fallback and bootstrap path.
- Mechanism 2: Index Assisted Scan: Indexes make conjunctions of equality predicates exact and faster than full scans at low selectivity, but posting-list work can reach Θ(N) at high selectivity.Disjunctions and ranges require appropriate index types.
- Mechanism 3: Sliding Window Sampling: Sampling estimates attribution from the three predicate summaries because the closed form is affine in those coordinates while global summaries remain exact.Sliding-window samples use chain-sample for count windows and priority-sample for time windows.
- 6.4 Concentration Bounds: Uniform sampling provides unbiased summary-based attribution estimates, with an AVG concentration rate of O(1/√r) and a leading factor O(M log N).The finite-population factor applies only to without-replacement sampling; with replacement uses ρ_r = 1.
- Mechanism 3: Sliding Window Sampling: Stratification helps when ad hoc predicates align with declared strata; otherwise IDS prefers index or retained-state paths.
- Sampling Maintenance: O(log r) amortized arrival cost replaces eager O(|Δ_t|r) sample maintenance through lazy candidate-list pruning.A sweep triggered after the candidate list grows beyond twice its expected steady-state size removes at least half the list.
- Sampling Maintenance: Under amortized pruning, sampling costs under 1 μs per tuple and is flat in r, while it is the only mechanism that need not retain the window.
7 Adaptive Predicate Promotion
IDS amortizes repeated ad hoc predicate questions by promoting frequently queried predicates into the registered set, while preserving exact atomic refinement through a full rebuild.
- Repeated ad hoc predicates are migrated into the registered set to avoid paying their per-call cost indefinitely.IDS tracks query frequency over a sliding observation window and promotes predicates exceeding a threshold.
- Exact promotion must split every active atom according to the new predicate because adding it changes all existing predicate signatures.
- Exact promotion scans the retained active window once to repartition atoms and initialize the new marginal, after which slides maintain the refinement exactly.The one-time bootstrap costs O(N).
- A provisional sample bootstrap supports only marginal queries initially, and its error remains unchanged under exact inserts and deletes until an exact rebuild.
8 Standalone Prototype
The standalone IDS prototype separates state ownership, delta production, predicate planning, and query execution into a tested single-node library.
- IDS is implemented as a Python 3.12, NumPy, and Numba single-node library whose IDSState owns summaries, atoms, harmonics, and optional retained state.
- Window managers emit deterministic delta batches, while the predicate registry, planner, replay driver, and restricted DSL parser support registration, dispatch, validation, and executable query examples.
9 Evaluation
Across deterministic replays and four workload families, IDS preserves attribution accuracy while making registered maintenance and queries largely independent of window size; ad hoc strategies trade state, latency, and error differently.
- 9. Evaluation: Every attribution discrepancy reached the double-precision floor across enumeration checks, delta equivalence replays, and Efficiency residuals.Errors were ≤4 × 10^-12 absolute, ≤5 × 10^-13 relative for delta equivalence, and ≤4 × 10^-15 relative for Efficiency.
- 9. Evaluation: IDS ingest throughput is flat in N, while the per-window scan baseline degrades as Θ(1/N).Throughput rises from 7.3 × 10^7 tuples/s at |Δt| = 1 to 1.3 × 10^8 tuples/s at |Δt| = 100.
- 9. Evaluation: 4.3 × 10^5× is the maximum measured speedup over per-window scans, with 4.8 × 10^3 at N = 10^5, K = 4, and |Δt| = 10.
- 9. Evaluation: 1.38 μs is the p50 latency for single-predicate attribution, remaining flat from K = 1 to K = 64; compositional queries grow with |S_W| instead.
- 9. Evaluation: At N = 10^5, summaries are 0.006% of the full analytic footprint, while retained window state dominates memory at 30.5 MiB and the index adds 15.3 MiB.
- 9. Evaluation: Sampling follows O(1/√r) error behavior; 5% sampling estimates AVG attribution within 0.2–3.1% of the aggregate, while variance error is 1–14% at r/N = 0.05.
- 9. Evaluation: 22.5× is the median tightening from empirical Bernstein–Serfling over the range-based bound, reducing observed slack from 246× to 10× with empirical coverage 1.00.
- 9. Evaluation: 0.62–0.79 μs per tuple is the essentially flat amortized pruning cost, 343× cheaper than eager domination updates at r = 2048.
10 Related Work
Prior work covers efficient sliding-window aggregation, sampling, stateless Shapley estimation, and incremental data valuation, while IDS adds predicate-level attribution for expiring windows.
- Classical and modern sliding-window engines efficiently evaluate aggregates but do not expose predicate-level attribution or IDS’s atom, marginal, retained-state, and query-surface objects.
- Sliding-window sampling requires expiration-aware methods because classical reservoir sampling does not handle tuple expiration.
- IDS uses concentration analyses for with- and without-replacement sampling, while smooth histograms remain an unexplored space–precision alternative.
- KernelSHAP and permutation estimators recompute each window as a fresh problem, serving as baselines for the maintained runtime’s per-window cost.
- Dynamic data valuation updates Shapley values under insertions and deletions for model utility games, whereas IDS targets expiring aggregate windows with O(1) evaluation from additive summaries.
11 Limitations and Future Work
IDS is scoped to a single-node prototype, selected aggregate operators, ordered updates, and workloads whose atom fanout may not represent adversarial schemas.
- Distributed execution, fault tolerance, exactly-once processing, and production DSMS integration remain outside the evaluated standalone library’s scope.
- Shipped operators cover SUM, COUNT, AVG, and two variance games; quantiles, MIN/MAX, joins, and model inference queries remain unsupported.
- Exact ad hoc scans, indexes, local expiry derivation, and exact promotion require O(N) retained active-window state, unlike summaries-only registered-predicate deployments.
- Late arrivals require reordering or retroactive correction because the prototype assumes event-time ordered inserts and expirations within each emit tick.
- Under many overlapping high-fanout predicates, the atom table can approach N, while adversarial schemas remain uncharacterized.