{"id":"a694a989-ac2f-44d0-adae-153395e23414","arxiv_id":"2505.10560","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"PromSketch caches Exponential-Histogram sketch summaries in memory so overlapping window-aggregation rule queries can be answered approximately without rescanning raw time series.","lead":"PromSketch adds an approximate in-memory cache of sketch summaries to Prometheus-like monitoring systems, cutting query latency by up to two orders of magnitude in benchmarks while holding average errors near 5%. It is a practical systems result for anyone operating large-scale Prometheus deployments, and the code is released on GitHub.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Operational-cost claim treats PromSketch precomputation as free; 400x reduction is an accounting artifact until ingestion-path CPU is priced in.","rationale":"The reader's weakest_assumption is exactly the one I would flag: Table 1 and the abstract's 'two orders of magnitude' cost reduction omit the measured precomputation cost. The paper itself provides the evidence for the concern (Fig. 7 throughput slowdowns, and the introduction's '1.3x to 3x' admission), so this is not an external objection but an internal inconsistency between the cost accounting and the benchmark data. The latency improvement, accuracy validation (5% MRE/KSTest across tested configurations), and the EH+KLL/EHUniv constructions are plausible and partly supported by measurements; those parts do not need to be rejected. The cost claim is the load-bearing part because it is the headline contribution and the basis of the 400x/4x comparison, and it is currently an accounting artifact rather than a total-cost result. The 70% coverage claim is also unsupported by a workload analysis, though secondary. A conditional accept that requires restating the cost claim with ingestion-side compute priced in, and ideally providing a query-workload justification for the 70% figure, matches the evidence available.","tokens_in":27483,"tokens_out":1961,"duration_ms":16514,"concrete_test":"Recompute Table 1 with a billing model that charges the measured ingestion-path CPU: take the §6.1.3 throughput ratios (e.g., 1.3x slowdown for EHKLL/PS-PM, 4.1x-4.5x for EHKLL/EHUniv/PS-VM at 10K series) and apply AWS Prometheus's per-sample query-processing rate or VictoriaMetrics' EC2 vCPU rate to the additional precompute time on the 268B-sample/month workload. If the incremental ingestion cost is added to the $28.6/month query figure, recompute the ratios against the $11,520/$7,443 baselines; if the 400x figure drops below one order of magnitude, the headline cost claim should be restated as query-path-only. Second, enumerate all aggregation-over-time functions in Prometheus's function catalog and count how many are actually implemented by PromSketch (EHKLL, EHUniv, uniform-sampling, plus min/max/topk/distinct), reporting the denominator used for the 70% claim.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central cost claim rests on Table 1, where query-processing cost drops to $28.6/month (PS-PM) while 'data ingestion' stays at the Prometheus baseline of $9,186 and storage is unchanged. The text explicitly says PromSketch reduces query-processing cost 'while not increasing the storage and data ingestion costs' (§6.1.1). But §6.1.3/Fig. 7 measures a 1.3x-3.1x insertion-throughput slowdown (Prometheus integration) and 1.4x-7.2x slowdown (VictoriaMetrics), and the introduction itself concedes 'precomputation overhead is moderate as 1.3x to 3x of non-precomputed/cached Prometheus'. Precomputation consumes real CPU on the ingestion path, so under a resource-based cloud billing model those cycles are billable. If the ingestion path were operated at the same AWS-Prometheus-style per-sample rate as the query path ($0.1/B samples), the cost of reprocessing each of the 268B samples for sketch updates would be roughly $26.8/month-added-over-baseline; more importantly, under VictoriaMetrics-style vCPU billing, the measured 4.1x-4.5x (EHUniv/EHKLL) ingestion slowdown on the VictoriaMetrics integration is not cost-free, yet Table 1 keeps VM ingestion 'incl.' in a way that does not expose the added PromSketch compute. Thus the '400x' and 'at least 4x' query-processing reductions compare only query-path dollars while omitting the measured ingestion-side compute, which is the very resource the paper's own benchmarks show is spent. The fairness question is not exact dollar magnitude but that the headline claim is not a total-cost-of-ownership statement. A second, related weakness: the 70% coverage claim (coverage of Prometheus aggregation-over-time queries) is asserted in the abstract, §4.2, and Table 3 without a workload analysis or catalog enumeration, so the breadth of the contribution is not yet evidenced.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PromSketch, an approximate in-memory intermediate-result cache for Prometheus-compatible timeseries monitoring systems. The system maintains Exponential Histogram (EH) buckets over recent time windows, using KLL sketches per bucket for quantile queries, universal sketches with an exact-map hybrid for GSum statistics (entropy, distinct count, L2 norm, top-K), and uniform sampling for average/stddev queries. At query time it answers overlapping sub-window aggregations by merging bucket sketches instead of rescanning raw samples. The authors provide error-bound analyses for EHKLL and EHUniv, describe single-machine and distributed integrations into Prometheus and VictoriaMetrics, and report experiments on synthetic and real traces claiming mean errors at or below 5%, latency reductions of up to about 200x, and query-processing cost reductions of 400x versus Prometheus and at least 4x versus VictoriaMetrics. They also report ingestion-throughput slowdowns of 1.3-3.1x over Prometheus and 1.4-7.2x over VictoriaMetrics in §6.1.3.","tokens_in":27901,"tokens_out":11227,"duration_ms":108123,"significance":"If the cost accounting is corrected and the sub-window error bound is fixed, this is a substantial contribution: it is, to my knowledge, the first end-to-end approximate intermediate-cache design for overlapping time-window rule queries in Prometheus-like systems; it combines a general window framework with mergeable sketches and includes provable memory-accuracy statements; and it ships a public Go implementation and uses public datasets. The latency and error measurements in Table 4 and Figures 6-13 are systematic, repeated, and reported against two real baselines, which is a genuine strength. The two issues below, however, affect the two headline claims (cost reduction and guaranteed sub-window accuracy), so the paper needs revision before the claims can be accepted as stated.","major_comments":[{"comment":"The headline cost reductions of 400x and at least 4x are computed with an incomplete cost model. Table 1 keeps PromSketch's ingestion costs at the baseline ($9,186 for PS-PM and 'incl.' for PS-VM) while moving query processing to $28.6/month, and §6.1.1 states that PromSketch reduces query-processing cost 'while not increasing the storage and data ingestion costs.' But §6.1.3 and Fig. 7 measure a 1.3-3.1x insertion-throughput slowdown over Prometheus and a 1.4-7.2x slowdown over VictoriaMetrics, so the precomputation consumes real CPU on the ingestion path. Under the resource-based billing model used for VictoriaMetrics in the same table, those cycles are billable; under a per-sample model, reprocessing the 268B samples at the paper's own $0.1/B-sample query rate would add roughly $26.8/month to the PS-PM row. Please recompute the cost comparison with the ingestion-path precomputation priced (e.g., vCPU-hour for PS-VM and per-sample for PS-PM), report both query-path and total operational costs, and state explicitly whether the 'two orders of magnitude' claim refers only to query-path spend.","section":"§6.1.1, Table 1; §6.1.3, Fig. 7"},{"comment":"The sub-window rank-error analysis for EHKLL appears incorrect. The text says the total rank difference from the EH sub-window query is at most C_i - C_j, where B_i is the discarded bucket containing t1 and B_j is the included bucket containing t2. Each of these buckets contributes a nonnegative error: excluding part of B_i misses up to C_i items, and including all of B_j adds up to C_j items after t2. The combined rank error should therefore be bounded by a sum of the two contributions (or by max(C_i, C_j) in the best case), not by their difference. As written, C_i - C_j is non-positive under Invariant 2 (C_1 <= ... <= C_l), so the subsequent upper bound of 2*epsilon_EH * N_t1/(N_t1 - N_t2) + epsilon_KLL does not follow. Please rederive this bound with absolute values or explicit worst-case analysis, and state the assumptions needed for the claimed sub-window guarantee.","section":"§4.2.1, EHKLL Error Guarantee"},{"comment":"The sub-window query procedure in Algorithm 1 includes the whole bucket B_j when t2 falls strictly inside B_j, which adds the suffix of B_j after t2 to the approximate window. The error analysis should explicitly account for this suffix, since the stated guarantee is for the window (t1, t2). The current discussion mentions that B_j contributes at most C_j, but the formula then uses C_i - C_j, and the relationship between the approximate window [end(B_i), end(B_j)] and the true window [t1, t2] is never made precise. A precise statement of which samples are included and excluded would also resolve the sign issue in the preceding comment.","section":"§4.2.1, Algorithm 1 and query semantics"}],"minor_comments":[{"comment":"The AWS Prometheus cost figures are internally inconsistent: the Introduction gives $11,520 for query processing and $9,256 for ingestion, while §6.1.1 gives $11,560 and $9,186, and Table 1 gives $11,520 and $9,186. Please harmonize these numbers and show the arithmetic, since 10 queries/minute each processing 8B samples per month does not obviously produce $11,520 at the stated $0.1/B-samples rate without additional assumptions.","section":"§2.3 and §6.1.1"},{"comment":"The claim that PromSketch covers '70% of Prometheus' aggregation over time queries' is not supported by any query-corpus analysis. Please state the query corpus, the weighting of queries, and the counting methodology that yields the 70% figure.","section":"Abstract and Table 3"},{"comment":"The body text says the drill-down queries cover '10^5-, 10^4-, and 10^3-second time windows' while the Table 4 caption says '10K-, 100K-, and 1M-sample windows.' Please clarify whether the axes are time durations or sample counts, and use consistent units throughout.","section":"§6.1.2 and Table 4"},{"comment":"There are several typographical errors and inconsistent spellings, e.g., 'remoevd' in §4.3, 'Kubernates' in the introduction and §4.4, and 'Google Promethues' in reference [101]. A thorough proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a VLDB 2025 accepted preprint; my recommendation is based on the submitted manuscript's internal consistency. I do not see circularity in importing the EHUniv construction and error bound from [69], but since [69] shares an author and the manuscript relies on its Theorem 3.5 for a central guarantee, it would be prudent to have that sub-window GSum statement verified independently. The '70% coverage' claim also needs a concrete derivation before it can be evaluated. Both major issues are fixable within the scope of the paper, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Josh — quick read of the PromSketch preprint. Bottom line: it's a real system with a real evaluation, and the latency results are likely to hold up. But the headline cost reduction is not a total-cost claim: Table 1 keeps ingestion costs at the baseline while the paper's own Fig. 7 shows the precomputation slows ingestion 1.3x–3x on Prometheus and 4.1x–7.2x on VictoriaMetrics. Those cycles are billable under the VictoriaMetrics-style model the paper uses, so the 400x and 'at least 4x' numbers are query-path-only accounting. The stress-test note lands.\n\nWhat's actually new: the EHKLL construction (EH buckets of KLL sketches with a rank-error bound for arbitrary sub-windows) is a legitimate extension; the hybrid exact-map/universal-sketch buckets are a sensible engineering optimization; and the integration with Prometheus and VictoriaMetrics, plus the distributed version, gives the paper concrete standing. The EHUniv framework is from [69] with an overlapping author, but that's a citable published result, not a self-citation problem. The implementation is in the repo, latency measurements are systematic and repeated against two baselines, and the error results support the ≤5% claim for the tested configurations.\n\nSoft spots beyond the cost accounting: the 70% coverage of Prometheus aggregation-over-time functions is asserted from Table 3 without any workload analysis or enumeration of the function catalog, so it's currently unverifiable. And the paper assumes approximate answers are fine for alerting rules without discussing threshold effects — that could matter operationally but is a minor omission, not a flaw in the core approach.\n\nThis is a solid systems contribution, not a breakthrough. It will be useful to anyone building or benchmarking approximate query caches for timeseries monitoring. Deserves a serious referee; the main revision request should be a full cost model that prices ingestion-side precomputation and a sensitivity analysis of the 400x number. I'd take it to reading group and engage with it.\n\nRecommended: send to peer review (it's already accepted at VLDB, so moot), but with that cost-model revision demanded.","headline":"Real system, real latency wins, but the 400x cost claim prices the measured ingestion overhead at zero.","tokens_in":28441,"tokens_out":3500,"would_cite":false,"duration_ms":30474,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"PromSketch caches overlapping window aggregations in compact sketches, cutting rule-query latency by up to two orders of magnitude while keeping mean errors at 5% or below.","keywords":["timeseries monitoring","approximate query processing","rule queries","Exponential Histogram","KLL sketch","universal sketch","sliding window","query caching"],"falsifier":"Run the Table 1 1000-node, 268-billion-sample workload on the released PromSketch code and bill the extra ingestion CPU (the measured 1.3x–3x insertion slowdown) at the same per-vCPU-hour rate the paper applies to query processing; if the resulting total monthly cost is not roughly two orders of magnitude below Prometheus's, the central cost claim is falsified.","tokens_in":27226,"feed_emoji":"⚡","tokens_out":5190,"duration_ms":51211,"temperature":0.7,"pith_summary":"PromSketch sets out to show that the dominant cost of timeseries monitoring rule queries is wasted work: periodic queries over overlapping windows repeatedly scan the same samples and recompute the same aggregations. The paper claims that an in-memory cache of approximate intermediate summaries, built from Exponential Histograms combined with quantile, universal, and sampling sketches, can serve a large share of these queries—covering 70% of Prometheus' aggregation-over-time functions—with mean errors at or below 5%. If true, a Prometheus-compatible engine could cut rule-query latency by up to two orders of magnitude and query-processing cost by roughly 400x versus Prometheus and at least 4x versus VictoriaMetrics without increasing storage or ingestion charges. That would change the default economics of alerting and recording rules for large cluster monitoring.","feed_headline":"Sketch cache cuts monitoring query latency by up to 100x","feed_subtitle":"PromSketch reuses overlapping window computations with KLL and universal sketches, holding mean errors at or below 5%.","key_machinery":"The load-bearing mechanism is the Exponential Histogram used as a cache index: a sequence of non-overlapping buckets whose sizes grow exponentially as they age, each bucket holding a sketch. Because EH buckets are mergeable (the target statistics are weakly additive), a query over any sub-window $(t_1,t_2)$ is answered by merging the buckets strictly between the two boundary buckets, with the discarded boundary buckets contributing controlled rank or norm error. The paper pairs EH with KLL sketches for quantiles (EHKLL), with universal sketches for GSum statistics (EHUniv), and with uniform sampling for sum/avg/stddev, and adds a hybrid optimization in which small buckets keep exact item-frequency maps before converting to sketches. This machinery is what lets the cache answer many overlapping and drill-down windows from one compact in-memory structure.","core_discovery":"The central discovery is that repeated data scans and repeated query computations over overlapping windows are the two bottlenecks in rule-query engines, and both can be bypassed by caching intermediate results rather than raw samples or final answers. PromSketch maintains, per timeseries, an Exponential Histogram whose buckets hold composable sketches—KLL sketches for quantiles (and min/max), universal sketches for entropy, distinct count, L2 norm, and top-k, and a sliding-window uniform sample for average, sum, and variance. Any sub-window of the recent window is answered by merging the buckets that cover it, so a 5-, 10-, or 15-minute drill-down can be served from the same cached structure without rescanning storage. The paper proves rank-error bounds for the EH+KLL combination (final normalized rank error at most $2\\epsilon_{EH}+\\epsilon_{KLL}$) and memory bounds for the EH+universal-sketch combination, and it reports end-to-end latency and cost results on synthetic and real traces.","pith_inferences":["Beyond the paper, the cost comparison depends heavily on the query-to-ingestion ratio: PromSketch's advantage should grow with more frequent rule evaluations and shrink for workloads that mostly ingest data and rarely query, since the ingestion-path overhead remains in either case.","Beyond the paper, the same EH-as-cache design could be applied to label-dimensional aggregation or to metrics with string values beyond IP addresses, since universal sketches operate on any item universe, though the paper leaves that extension unproven.","Beyond the paper, because small EH buckets use exact maps, a natural adaptive policy would set bucket sizes so that typical drill-down queries touch only exact-map buckets, potentially pushing mean error far below 5% for common workloads."],"forward_implications":["Rule queries with overlapping windows, such as 10-minute windows evaluated every minute, can be served from precomputed bucket merges, so alerting and recording rules no longer rescan storage on every evaluation.","Drill-down queries that zoom from a 1M-sample window into 100K and 10K sub-windows keep mean errors under 5% at a fraction of the memory of exact storage, which supports anomaly localization on the same cache.","Operators can trade memory for accuracy explicitly through knobs such as $k_{EH}$ and $k_{KLL}$, since error decreases as memory grows for all evaluated statistics.","Because the cache is a standalone module integrated through a small query-parser patch, the same design transfers to any PromQL-like engine, including distributed deployments where nodes shard timeseries by consistent hashing."],"supporting_citations":[{"why":"Supplies the Exponential Histogram bucket structure and invariants that let any sub-window be answered by merging a controlled number of buckets.","marker":"[60]"},{"why":"Supplies the KLL quantile sketch with rank-error guarantees, which becomes the inner sketch of each EHKLL bucket.","marker":"[72]"},{"why":"Supplies universal sketching so a single sketch per bucket can answer entropy, distinct count, L2 norm, and top-k queries.","marker":"[78]"},{"why":"Provides the recursive GSum algorithm and the theorem for estimating functions of frequency vectors that EHUniv relies on.","marker":"[52]"},{"why":"Extends the EH framework to interval and sub-window queries and establishes the EH-based L2 heavy-hitter bounds used in the design.","marker":"[69]"},{"why":"Provides the sliding-window uniform sampling algorithm used to answer average, sum, standard deviation, and variance queries.","marker":"[80]"},{"why":"Provides the cloud billing model for storage, ingestion, and query processing used to compute the 400x cost reduction claim.","marker":"[10]"}],"fun_headline_variants":["Sketch caches cut monitoring query latency 100x","PromSketch makes timeseries queries 100x faster","Approximation-first caching accelerates rule queries 100x","Sketch-based precomputation speeds monitoring 100x","Cached window sketches reduce query latency 100x"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The cost-reduction numbers assume that the ingestion-time sketching work, which the paper itself measures as a 1.3x–3x insertion-throughput slowdown, is operationally free: Table 1 charges PromSketch only for query processing while keeping storage and data-ingestion costs at the uncached baseline.","fun_headline_variants_meta":{"raw":{"variants":["Sketch caches cut monitoring query latency 100x","PromSketch makes timeseries queries 100x faster","Approximation-first caching accelerates rule queries 100x","Sketch-based precomputation speeds monitoring 100x","Cached window sketches reduce query latency 100x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00054,"raw_usage":{"total_tokens":2605,"prompt_tokens":975,"completion_tokens":1630,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":591,"completion_tokens_details":{"reasoning_tokens":1551}},"tokens_in":591,"tokens_out":1630,"duration_ms":11307,"temperature":1.0,"reasoning_tokens":1551,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:07:17.895130+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the Table 1 1000-node, 268-billion-sample workload on the released PromSketch code and bill the extra ingestion CPU (the measured 1.3x–3x insertion slowdown) at the same per-vCPU-hour rate the paper applies to query processing; if the resulting total monthly cost is not roughly two orders of magnitude below Prometheus's, the central cost claim is falsified.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Exponential Histogram bucket structure and invariants that let any sub-window be answered by merging a controlled number of buckets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the KLL quantile sketch with rank-error guarantees, which becomes the inner sketch of each EHKLL bucket."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies universal sketching so a single sketch per bucket can answer entropy, distinct count, L2 norm, and top-k queries."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the recursive GSum algorithm and the theorem for estimating functions of frequency vectors that EHUniv relies on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Extends the EH framework to interval and sub-window queries and establishes the EH-based L2 heavy-hitter bounds used in the design."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the sliding-window uniform sampling algorithm used to answer average, sum, standard deviation, and variance queries."}],"review_version":1}