CS Paper Radar

Closed-Form Predicate-Level Shapley Attribution for Sliding-Window Aggregates

Pouya Khani, Ira Assent

cs.DB ·submitted 2026-08-24 10:52 UTC · v1

Abstract

Streaming engines report sliding-window aggregates in real time, but they do not explain \emph{why} an aggregate takes its current value. A natural target is the Shapley value from cooperative game theory, which axiomatically distributes an aggregate among the tuples in the window. Practitioners, however, ask predicate-level questions (e.g., how much a region or customer tier contributed to an average or variance spike). Exact Shapley computation is exponential in the window size, and existing estimators discard the massive overlap between consecutive windows. We show that for SUM, COUNT, AVG, and population/sample variance, exact predicate-level Shapley values admit closed forms in three additively maintained summaries per predicate (count, sum, and sum of squares), with coefficients that depend only on two running harmonic numbers. Attribution therefore reduces to $O(1)$ summary updates per slide for registered predicates, with no coalition enumeration. Overlapping and compositional predicates are answered exactly via atomic refinement of Boolean signatures. We further characterize the phenomenon: every moment-polynomial aggregate admits such a form, while MAX, MIN, and quantiles provably do not at any fixed moment order. Experiments match brute-force Shapley values to floating-point precision on over $10{,}000$ windows, sustain $\approx\!2\,μ$s per slide up to $N=10^6$ ($3{,}200\times$ faster than per-window recomputation of the same formulas), and explain a nighttime fare spike on 2.9M NYC taxi trips at $\approx\!1.8$M summary updates per second.

Comment
submitted to IEEE Access

Closest papers

Nearest neighbours by meaning across the whole index.

Incremental Delta-Shapley: A Standalone Runtime for Predicate Attribution on Sliding Windows

cs.DB ·2026-08-27 ·Pouya Khani, Ira Assent
similarity 0.76
Abstract

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.

0.15

Target-Stratified Fair Range Summaries: Improved Fair $\varepsilon$-Nets and Geometric Hitting Sets

cs.DS cs.DM ·2026-09-17 ·Mingchao Zhou, Lei Zhao, Zhipeng Cai, Zhao Zhang
theory similarity 0.58
Abstract

Compact summaries are a key tool for approximate query processing over large datasets. For range-query workloads, an $\varepsilon$-net provides a small summary that hits every sufficiently large range. However, classical $\varepsilon$-nets only guarantee range validity and do not control the group composition of the selected tuples. As a result, the summary may be range-valid but poorly representative, which can propagate imbalance to downstream query results. Motivated by recent work on fair $\varepsilon$-nets and fair geometric hitting sets \cite{dehghankar2025fair}, we study fairness-aware range summaries under prescribed target group ratios. Different from previous sample-and-repair approach, we propose a target-stratified sampling method. For demographic parity (in which the ratio of fairness is determined by group proportion), our sample size is $O(A_{\varepsilon})$, coinciding with the standard $\varepsilon$-net bound, improving previous bound of $O\!\left(A_\varepsilon\log\frac{k}{\varphi}\right)$. For custom-ratio targets (in which the ratio of fairness is determined by manually defined proportion), our sample size is $O(A_Γ)$, where $Γ$ is a parameter measuring the gap between the customized ratio and the demographic parity; we prove that this dependence on $Γ$ is unavoidable, with a worst-case lower bound of $Ω(Γ/\varepsilon)$. Using our target-stratified sampling method, we could improve the previous approximation ratio for the fair geometric hitting set problem by a logarithmic factor, and making use of this result, we could in turn improve the size of custom-ratio fair $\varepsilon$-net. Experiments on real and synthetic datasets demonstrate that our method constructs smaller fair summaries than existing approaches, scales to large datasets and fine-grained group constraints, and improves downstream range query processing.

0.19

ShapleyOG: Fast Adaptive Shapley Value Estimation with Odd Gaussian Processes

cs.LG stat.ML ·2026-11-04 ·David Rundel, R. Teal Witter, Santo M. A. R. Thies, Matthias Feurer, Fabian Fumagalli +1 more
similarity 0.57
Abstract · Preprint under review

Shapley values are a central tool for attribution in machine learning. Since their exact computation requires evaluating the cooperative game to be explained on exponentially many player coalitions, they are typically estimated from a limited number of evaluations. Recently, ShaplEIG has shown that adaptively selecting the coalitions to evaluate substantially improves sample efficiency over classical estimators. This, however, comes at the cost of a sequential procedure that, in every iteration, refits a Gaussian process surrogate of the game and selects the coalition with the largest expected information gain about the Shapley values. The resulting computational overhead limits its applicability to costly games with low evaluation budgets. We present fast adaptive Shapley value estimation with Odd Gaussian Processes (ShapleyOG) to overcome this limitation. ShapleyOG leverages the fact that Shapley values depend only on the odd component of the game, and we show that under paired sampling a Gaussian process surrogate on this component alone yields the same Shapley value posterior and coalition selection criterion from half as many observations. Moreover, ShapleyOG refits the surrogate only on a sparse schedule and efficiently updates the selection criterion in between, and it extends quadrature-based computation schemes to the prior covariance of the Shapley values, which allows for exact or cheaper approximate computation. In extensive experiments on diverse games, ShapleyOG matches the estimation accuracy of ShaplEIG while reducing its overhead by up to three orders of magnitude. As a result, it outperforms state-of-the-art non-adaptive estimators at equal total computation time already when a single evaluation takes a tenth of a second and a budget of a few thousand evaluations suffices, thereby widening the regime in which adaptive coalition selection is applicable and pays off.

0.24

CASI: Credit Assignment via Set Intervention for Agentic Retrieval

cs.AI cs.IRcs.LG ·2026-10-14 ·Xinyi Cheng, Tianfu Zhang, Jiwen Li, Xuesen Zhang, Shihao Yu +3 more
similarity 0.55
Abstract · 19 pages, 2 figures, 8 tables

Large language models increasingly generate multiple retrieval actions jointly, while downstream systems often provide only one reward for the resulting set. Broadcasting this reward provides a valid score-function gradient estimator for the expected set-level objective, but does not determine a coalition-dependent within-set attribution. We introduce CASI (Credit Assignment via Set Intervention for Agentic Retrieval), which constructs the missing counterfactual information through snapshot-grounded set intervention: generate and retrieve once, hold replayable snapshot components fixed, and evaluate alternative subsets under common conditions. Shapley aggregation converts these marginals into within-set credit, which bounded zero-sum advantage shaping incorporates into policy optimization. For m >= 4, singleton, leave-one-out, and full-set endpoints do not generally determine the Shapley allocation; under additive set values, extra coalition evaluations are redundant. In a five-action sponsored-search setting, exhaustive auction replay over 1,200 requests reveals substantial coalition dependence. Under the training-time evaluator, CASI achieves the highest median cosine similarity to a replay-defined Shapley reference among evaluated credit rules; under a sensitivity backend, CASI does not outperform Singleton. Across five independent training runs, CASI-trained policies achieve higher held-out auction-replay set value than Singleton- or Broadcast-trained policies. In a randomized seven-day production A/B test on 10% of traffic, the CASI-trained policy yields an observed 3.51% lift in the primary advertiser-value metric over production control.

0.23

TempShap: When and How Much a Feature Matters in Time-Series Forecasting

cs.AI cs.GTcs.LG ·2026-10-23 ·Chi Zhao, Anastasiia Chelnokova, Jing Liu, Elena Parilina
similarity 0.54
Abstract

Attribution for a time-series forecaster should answer two questions that a feature-level scalar cannot: when in the input window a feature acts, and how much its influence changes across the forecast horizon. Most existing Shapley explainers treat each feature as one player and therefore collapse both axes. We propose TempShap, a retrospective, loss-based Shapley framework whose players are the individual input cells $(t,i)$. Its attribution tensor yields temporal-localization and horizon-impact profiles. We validate these against planted temporal structures, a tractable exact cell game, and a closed-form attribution oracle for a real linear forecaster. Permutation sharing estimates the cell-level game at localized perturbation cost. Under redundant inputs, one-at-a-time scores under-credit substitutable information, whereas the signed Shapley decomposition preserves total value and yields more reliable held-out deletion rankings under mean masking. A planted counterexample isolates the redundancy mechanism. Experiments show a deletion-ranking advantage across Shapley estimators, forecasting benchmarks, and model families. TempShap therefore makes fine-grained Shapley attribution both practical and operationally useful.

0.25

Constant-Loss Round-Preserving Direct Sums for Information Complexity

cs.CC cs.IT ·2026-10-11 ·Haoran Wang
theory similarity 0.54
Abstract

Strong direct-sum theorems relate the information needed to solve many independent instances of a communication problem to the information needed for one instance. For Gap-Majority composition, an optimal information bound was previously known, but preserving the number of communication rounds incurred an additional logarithmic loss. We prove a round-preserving Gap-Majority lemma with constant additive information loss, independent of both the number of instances and the number of rounds. More generally, we establish a variance direct-sum theorem for additive square-integrable observables over product distributions. For protocols with a bounded number of terminal answer values, the extracted single-coordinate protocols preserve the round budget, and their average information cost is at most the original information cost divided by the number of coordinates, plus a term depending only on the answer alphabet and the allowed variance loss. The proof uses centered counterfactual conditional means and a global variance amortization argument. Rather than encoding absolute conditional means for every possible terminal answer, we encode the information not already determined by the common view. The total squared innovation is controlled by a telescoping variance potential, yielding an information loss independent of the number of coordinates. We also derive same-round mean-square estimation bounds for arbitrary terminal outputs.

0.58

RelShap: Relationally Consistent Shapley Explanations

cs.LG ·2026-08-11 ·Seungeun Lee, Joao Fonseca, Julia Stoyanovich
code/data similarity 0.54
Abstract

Machine learning pipelines commonly flatten relational data into single-table representations, discarding structural constraints. Widely used Shapley value-based feature attributions then rely on feature independence, evaluating the model on combinations that could never arise in the underlying data, producing misleading explanations. We propose RelShap, a framework that incorporates relational constraints and data provenance into Shapley value computation, restricting both background data and coalition evaluation to relationally valid configurations. The framework is estimator-agnostic and composes with Kernel SHAP, Monte Carlo, and Leverage SHAP without altering their sampling or weighting properties. Functional dependencies further induce equivalence classes over feature coalitions, which RelShap exploits to reduce runtime without changing Shapley values; we provide a combinatorial characterization of the expected speedup. Experiments across multiple datasets, models, and estimators show that RelShap produces explanations that are more faithful to the data-generating process, correctly identifying the dominant feature in controlled settings where existing methods, including Conditional SHAP and ManifoldShap, do not. Our code is available at: https://github.com/duneag2/relshap.

0.24

When Agent Memory Needs to Compute: Evidence Access and Executable Aggregation

cs.AI ·2026-10-14 ·Zerui Yang, Quan Xue, Chaorui Zhang, Xueyan Niu, Xuanyu Zheng +6 more
similarity 0.53
Abstract

Questions about an agent's history often require aggregating events, which retrieval alone does not resolve. We combine source-preserving evidence access with executable aggregation. Trajectory Memory (TM) retains the original trajectory and constructs a source-addressable reading view at question time. TallyMem augments it with a reusable event ledger, model-generated event specifications and deterministic execution. With a commit-specific adaptation on 776 questions from 99 held-out MINTEval repositories, TallyMem raises Qwen3-32B exact match from 35.2% to 49.0%, a 13.8-point gain over TM; gains span 12.8-13.9 points across three readers. A controlled probe with event sets parsed independently from raw logs shows an 11.0-point gain, from 82.8% to 93.8%, without routing. On full AMA-Bench, the routed system yields a smaller 1.3-point gain, from 69.8% to 71.1%. These results support executable aggregation on tasks that require combining events, with benefits dependent on the task and event specification, the largest residual system-error category in our diagnostic analysis.

0.37