{"id":"2b80cc9a-655a-4062-beb8-3c7e8c8fd2af","arxiv_id":"2506.16928","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"LMQ-Sketch combines partitioned Count-Min/ASketch state with a version-handshake synchronization to support concurrent F1, F2, and point queries with Intermediate Value Linearizability semantics.","lead":"LMQ-Sketch is a compact data-summary structure that keeps answering frequency, F1, and F2 queries while new stream updates keep arriving, instead of pausing ingestion. A smart business person might care because high-rate analytics systems, such as network monitoring or database backends, could get fresh approximate answers from a small memory footprint without stalling the data pipeline.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"F2 branch depends on unproven half-full/EWMA projection; Lemma 19 is IVL relative to LMQ-proj+, so it does not by itself establish accuracy against true F2.","rationale":"The reader's weakest assumption matches my concern: the F2 result relies on the unvalidated projection in Eq. 5. This is load-bearing because Corollary 20 presents F2Lagom as an IVL implementation of LMQ-proj+, but LMQ-proj+ has no independent accuracy guarantee. The paper builds a careful chain from CM+ to PartCMS+ to PartAS+ to LMQ-all+, and at the final step it replaces exact buffered counts with a heuristic, supported only by Observation 18 and an informal geometric argument. Since F2 is one of the three headline query types, a failure of this projection would remove the accuracy justification for the F2 number even though throughput, memory, and the PQ/F1 arguments would remain intact. The empirical sections do not isolate the projection error: Sec. 6.2 compares end-of-stream MAPE against other sketches, and Sec. 6.4 compares returns to IVL bounds rather than to true F2. The concern is concrete and addressable because source code is provided. I keep the reader's CONDITIONAL verdict rather than strengthening it, since the code permits a direct instrumented check and the rest of the design is well argued.","tokens_in":21776,"tokens_out":8867,"duration_ms":97805,"concrete_test":"Run the released implementation with P=128, B=1000, Zipf-2 input; instrument queryF2Lagom to snapshot, for every a in Ti.AF, the exact total buffered count sum_j DF_j[a] at the scan instant and compare it with P·AFmavg[a]/2. Compute per-query absolute error of the compensation term and MAPE of LMQ-proj+ against exact LMQ-all+ (Eq. 2) on a quiescent snapshot. If the mean absolute projection error exceeds 10% of the exact compensation term, or LMQ-proj+ MAPE is more than 2x LMQ-all+ MAPE at P=128, the heuristic is not a reliable basis for the F2 accuracy claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing step is Alg. 6 / Eq. 5: buffered heavy-key occurrences are replaced by P·AFmavg[a]/2, on the assertion that delegation filters are 'on average half full' (Sec. 4.3). No error bound is given; Observation 18 is stated without derivation, and r/2 is a total-buffer count (Obs. 9), not a per-key bound. The projection can miss by a factor of two in the squared term whenever the P filters for a heavy key fill and flush in phase (all near full at query time vs. the assumed half-full mean), and the EWMA AFmavg lags such phase patterns. More structurally, Lemma 19 proves only that F2Lagom is an IVL implementation of LMQ-proj+, where LMQ-proj+ is defined by Eq. 4-5, i.e., the same heuristic formula. That guarantee is relative to the algorithm's own reference value and does not connect the returned number to true F2 unless LMQ-proj+ is separately shown to approximate F2. The only support is the geometric intuition in Fig. 2c and the empirical MAPE in Fig. 4; there is no analytical bound. The introduction's further claim that <100 µs latency 'implies error below 0.01%' is likewise unsupported by Sec. 6.4, which measures distance to IVL interval endpoints rather than error against true F2. The F2 accuracy pillar of the central claim therefore remains unestablished.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents LMQ-Sketch, a partitioned, concurrent sketch data structure that supports point queries, the first frequency moment F1, and the second frequency moment F2 from a single memory footprint while updates are being processed. The high-level claims are: point queries are an IVL implementation of the ASketch point query, F1 is an IVL implementation of exact F1, and F2 is handled by a new 'Lagom' synchronization scheme that returns an IVL implementation of a quantity the authors call LMQ-proj+. The authors report F2 query latency below 100 microseconds, update throughput above 2 billion updates per second on 128 threads, and an order-of-magnitude memory reduction relative to the SW-SKT multi-sketch baseline. The paper contains formal-sounding lemmas for the concurrency semantics, a geometric explanation of the F2 compensation, and an extensive evaluation on synthetic Zipfian data and CAIDA traces.","tokens_in":22151,"tokens_out":4409,"duration_ms":46640,"significance":"If the central claims hold, this is a valuable contribution to concurrent data structures for streaming analytics. The paper offers a concrete design that combines partitioning, delegation filters, and a lightweight handshake to achieve IVL semantics for multiple query types, and it ships an open-source implementation that is evaluated on a 128-core machine. The strongest parts are the point-query and F1 arguments, which are plausibly rigorous, and the empirical demonstration that the Lagom synchronization overhead is small. The main significance of the contribution, however, rests on the F2 accuracy claim, and that part is currently supported only by a heuristic projection and by an IVL statement relative to that same heuristic. The experimental evaluation is careful in several dimensions, and the open-source artifact is a clear strength, but the theoretical basis for the F2 accuracy pillar is not yet established.","major_comments":[{"comment":"The F2 compensation is the load-bearing step of the paper, but it rests on two unproven assertions: that delegation filters are 'on average half full' at any scan, and that the EWMA AFmavg[a] tracks the number of buffered occurrences of a. Observation 18 is stated without a derivation, and its phrase 'up to r/2 ignored occurrences per heavy key' is not justified because r=PB from Observation 9 is a total-buffer bound over all keys and all delegation filters, not a per-key bound. The projection P*AFmavg[a]/2 enters the squared term in Eq. (5), so a constant-factor error in the assumed occupancy is not benign. For example, if the P delegation filters of a heavy key fill and flush in phase, the actual buffered count can be near P*AFmavg[a] at query time, not P*AFmavg[a]/2, and the squared term can be off by a factor close to four. The paper needs either a concrete error bound for the projection under stated assumptions, or an explicit and prominent statement that the F2 accuracy of LMQ-proj+ is a heuristic that is validated only empirically.","section":"Sec. 4.3, Eq. (5) and Observation 18"},{"comment":"Lemma 19 only establishes that the concurrent query is an IVL implementation of LMQ-proj+, where LMQ-proj+ is defined by Eqs. (4)-(5), i.e., by the same heuristic formula whose accuracy is at issue. This does not connect the returned number to the true F2 of the stream. The manuscript needs a separate argument that LMQ-proj+ approximates F2, for example by bounding its deviation from CM+ or PartAS+ under the stated skew assumptions, or by proving an (epsilon, delta) bound for the projection. As written, Corollary 20(3) overstates what the lemmas imply: the reader is given an IVL guarantee about a reference value that is itself unproven as an estimator of F2.","section":"Sec. 5.3, Lemma 19 and Corollary 20"},{"comment":"The abstract and introduction claim that F2 query latency between 1 and 100 microseconds 'implies freshness with error below 0.01%'. This claim is not supported by the evaluation in Sec. 6.4. Figure 8 measures the return value of the concurrent query relative to reconstructed IVL interval endpoints Qstart and Qend; it does not measure error against the true F2 of the prefix observed by the query. To support the sub-0.01% claim, the paper would need to report, for concurrent executions, the distance between the returned value and the true F2 computed over the queried prefix, with a clear definition of the error metric. Without that evidence, the accuracy implication from latency should be removed or substantially weakened.","section":"Sec. 6.4 and abstract"}],"minor_comments":[{"comment":"The description of AFmavg as 'Projected count of buffered occurrences' is imprecise. From Algorithm 1, AFmavg is an exponentially weighted moving average of the flush sizes observed for a key, not a direct projection of the current buffer contents. The table and surrounding text should be aligned with the actual update rule.","section":"Table 1 and Algorithm 1, line 1.4"},{"comment":"The y-axis label 'Relative error (%)' is misleading because the plotted quantity is the distance to the IVL-permitted interval boundaries, not an error relative to the true F2. Renaming the axis to something like 'Relative deviation from IVL bounds (%)' would avoid overinterpreting the figure.","section":"Fig. 8"},{"comment":"The probability expression '1−δ = 1− 3 4 −H' appears to have a typesetting error; it should presumably read '1−(3/4)^H'. Please correct this so the definition is unambiguous.","section":"Section 2, Definition 1"},{"comment":"The reference list entry for the LMQ-Sketch software is attributed to 'Anonymous author(s)', while the title page lists the authors. For an arXiv version with author names, the reference should be updated to avoid confusion.","section":"Reference [3]"},{"comment":"The table in Lemma 10 uses symbolic entries such as 'P -relaxed monotonic' and 'r-relaxed monotonic' without defining these terms in the main text. Since the paper introduces these notions only inline, a short definition before the lemma would improve readability.","section":"Section 4.4, Lemma 10"}],"recommendation":"major_revision","confidential_remarks":"The reader's conditional verdict is fair. The F2 accuracy pillar is the central novel claim, and it is currently supported by an unproven heuristic rather than a theorem. I would like the revision to either provide a rigorous analysis of LMQ-proj+ or to reframe the paper's guarantees as empirical for F2 and formal only for point queries and F1. The self-citation to Delegation Sketch [40] is methodologically appropriate, since the paper builds on that design, but the contribution would be stronger with an independent treatment of the F2 projection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a solid systems contribution: a single sketch that answers point queries, F1, and F2 concurrently with updates, with explicit IVL semantics, open-source code, and a memory advantage over SW-SKT that comes from partitioning rather than merging. The point-query and F1 results are the strongest part--they are IVL implementations of well-defined references (ASketch point query and exact F1), and the synchronization handshake in Lemma 8 is carefully argued. The monotonicity table in Lemma 10 is a nice addition.\n\nThe soft spot is exactly where the stress-test lands. Lemma 19 shows that the F2 query is an IVL implementation of LMQ-proj+, the paper's own estimator defined in Eqs. 4-5. That estimator includes the EWMA projection, and no bound connects it to true F2. Observation 18's r/2 compensation is stated without derivation, and the 'filters are on average half full' claim is plausible but unproven; if fill phases align across the P filters, the squared term can miss by a factor of two. The introduction's link between <100us latency and 'error below 0.01%' is not supported by Section 6.4, which measures distance to IVL interval endpoints, not error relative to true F2. These are specific, addressable issues, not defeaters: the empirical MAPE in the sequential setting is impressive, and the concurrent evaluation clearly shows the latency advantage.\n\nMinor omissions: the EWMA weight w=0.8 and the buffer bound B are not sensitivity-tested, and the concurrent accuracy evaluation would be stronger if it also reported error against true F2 rather than only IVL-interval position.\n\nWho should read it: people building concurrent stream processing systems, and researchers interested in what IVL does and does not guarantee. It is a good reading-group candidate for that second reason alone.\n\nVerdict: this deserves a serious referee. I would send it to a systems or concurrency venue and ask for either a bound on the projection error for heavy keys or an explicitly scoped accuracy claim. The core design and the point-query/F1 semantics are strong enough that a revision should be accepted.","headline":"A genuinely useful engineering contribution to concurrent multi-query sketching, but the F2 accuracy claim is relative to a heuristic estimator, not to true F2; the paper still deserves a serious referee.","tokens_in":22644,"tokens_out":2770,"would_cite":true,"duration_ms":30078,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A single composite sketch can answer frequency, F1, and F2 queries concurrently with updates, keeping global query latency under 100 microseconds and update throughput above 2 billion per second.","keywords":["concurrent data structures","data sketches","intermediate value linearizability","freshness","synchronization","frequency moments","Count-Min Sketch","streaming algorithms"],"falsifier":"Record the true occupancy of the small update buffers at the moment a global F2 query scans a partition, replay a bursty stream in which one heavy key floods the buffers just before the query, and compare the returned $\\hat{F}_2$ with the exact $F_2$ computed offline; if the estimate deviates by more than the sequential $(\\epsilon,\\delta)$ bounds whenever buffers are far from half full, the projection's core assumption fails.","tokens_in":21545,"feed_emoji":"⚡","tokens_out":13180,"duration_ms":125313,"temperature":0.7,"pith_summary":"This paper claims that a single, small data sketch can answer three kinds of questions—frequency of individual keys, total item count $F_1$, and second frequency moment $F_2$—while updates keep arriving at very high rate; previously, designs either used several separate sketches or could not run queries concurrently with updates. The proposed LMQ-Sketch partitions the input among threads, delegates updates into small buffers, and maintains per-partition partial results so that global queries touch only a few numbers instead of rescanning the whole sketch. A lightweight handshake between query and updater gives every query intermediate-value linearizability, meaning the returned value lies between the values a sequential query would return at the start and at the end of its execution. The authors report update throughput above 2 billion per second on 128 threads, F2 query latency below 100 microseconds, and memory use roughly an order of magnitude below the separate-sketch baseline. If these results hold, high-rate analytics systems could maintain one structure instead of several, with fresher concurrent answers.","feed_headline":"One compact sketch answers three query types at over 2B updates/s","feed_subtitle":"One memory-light structure replaces many separate sketches and keeps global query latency under 100 microseconds.","key_machinery":"The central object is LMQ-Sketch's composite structure: the domain is split into P partitions, each owned by one thread and carrying an Augmented Sketch (an ASketch filter for heavy keys in front of a Count-Min Sketch), delegation filters that buffer updates for other partitions, an $F_1$ partial counter, and per-row $F_2$ partial sums. The load-bearing mechanism is Lagom—\"just enough\"—which synchronizes global queries with updates through a version-pair handshake and replaces expensive full scans with the projection $H_{\\mathrm{Lagom}}(a)=(AF[a]+P\\cdot AF_{\\mathrm{mavg}}[a]/2)^2 - AF_{\\mathrm{old}}[a]^2$. A geometric argument treats $F_2$ contributions as areas of frequency-squares: the estimator adds the square of the current filter count, subtracts the square of the old count to avoid double-counting what is already in the Count-Min Sketch, and compensates for unmerged buffered occurrences by assuming filters are on average half full. This keeps global queries to a few reads per partition while preserving the one-sided error behavior of CM+.","core_discovery":"The paper's central claim is that point queries, $F_1$, and $F_2$ can all be served from one composite, partitioned sketch under concurrent updates, with intermediate-value linearizability (IVL) semantics and accuracy close to the sequential $(\\epsilon,\\delta)$ bounds. For $F_2$, the estimator LMQ-proj+ forms a CM+ estimate per partition from incrementally maintained row sums, then adds for each heavy key $a$ the compensation term $H_{\\mathrm{Lagom}}(a)=(AF[a]+P\\cdot AF_{\\mathrm{mavg}}[a]/2)^2 - AF_{\\mathrm{old}}[a]^2$, which accounts for occurrences still buffered in delegation filters without scanning them. A version-counter handshake ($V_1/V_2$ plus a being-scanned flag) stops a global query from reading a partition while a filter flush is moving data, giving an atomic per-partition snapshot without deadlock. The paper proves that this query is an IVL implementation of LMQ-proj+, that the $F_1$ query is an IVL implementation of exact $F_1$, and that the point query is an IVL implementation of the ASketch point query, along with explicit monotonicity-of-scans relations between query types.","pith_inferences":["Editorial inference: the half-full projection is the most workload-sensitive component; a testable extension is to replace the fixed $P\\cdot AF_{\\mathrm{mavg}}[a]/2$ compensation with per-filter occupancy measured at query time, which would remove the main heuristic while keeping the same handshake.","Editorial inference: the same technique—per-partition partial aggregates plus a version-pair handshake—should transfer to other expensive global aggregates, such as quantile or entropy estimates, as long as each partition can maintain an incremental contribution, potentially broadening the impact beyond the three query types tested.","Editorial inference: the claimed memory advantage is contingent on comparing against a baseline that keeps separate sketches per query; a baseline whose separate sketches are optimized for exactly this mixed workload could narrow the gap, so the order-of-magnitude figure is workload- and baseline-dependent."],"forward_implications":["If the central claim holds, one small structure suffices for the three most common stream queries concurrently, replacing disjoint sketches and cutting the memory budget by about an order of magnitude on the tested skewed workloads.","Global F2 queries answer in under 100 microseconds even at 128 threads, so the interval of possible answer values is small and reported results stay fresh relative to the update stream.","Update throughput remains above 2 billion per second under concurrent query load on synthetic skewed streams, implying the consistency machinery does not become the bottleneck.","Every supported query is covered by a formal consistency statement—IVL for point, F1, and F2 (the last against the projected estimator), plus bounded monotonicity between query types—so users can reason about what a returned value means during concurrent runs."],"supporting_citations":[{"why":"Supplies the Count-Min Sketch, its point-query estimator, and the exact F1 row-sum property that LMQ-Sketch builds on.","marker":"[14]"},{"why":"Provides the CM+ method for estimating F2 from a Count-Min Sketch, the basis of the per-partition F2 partial results.","marker":"[15]"},{"why":"Introduces the Augmented Sketch filter for heavy keys, including the AFold old-count bookkeeping used to avoid double-counting in F2.","marker":"[39]"},{"why":"Contributes the partitioned delegation design and the IVL point-query result that LMQ-Sketch extends to global queries, and serves as the main concurrent point-query baseline.","marker":"[40]"},{"why":"Defines Intermediate Value Linearizability and its locality property, used to prove the concurrency semantics of the F2 and other queries.","marker":"[37]"},{"why":"Serves as the separate-sketch multi-query baseline whose memory budget and accuracy LMQ-Sketch compares against.","marker":"[11]"},{"why":"Provides the F2 estimator used as an accuracy reference in the memory and accuracy evaluation.","marker":"[12]"},{"why":"Supplies the monotonicity-of-scans notion used to state cross-query consistency properties.","marker":"[18]"}],"fun_headline_variants":["One sketch, three query types, 2B updates/s","Concurrent multi-query sketch: 2B updates/s, low memory","Lagom: single sketch for point, F1, F2 with concurrency","Answer multiple queries concurrently with one memory-light sketch","Multi-query sketch with IVL semantics at 2B updates/s"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The F2 estimate's accuracy rests on an unproven heuristic: the small buffers that hold updates before they are merged into the sketch are assumed to be on average half full when a global query looks at them, and the compensation term uses P times the moving average of buffered counts divided by two; if real buffer occupancy is not centered at half, the estimate is biased and the paper supplies no formal bound for that bias.","fun_headline_variants_meta":{"raw":{"variants":["One sketch, three query types, 2B updates/s","Concurrent multi-query sketch: 2B updates/s, low memory","Lagom: single sketch for point, F1, F2 with concurrency","Answer multiple queries concurrently with one memory-light sketch","Multi-query sketch with IVL semantics at 2B updates/s"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000231,"raw_usage":{"total_tokens":1542,"prompt_tokens":1058,"completion_tokens":484,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":674,"completion_tokens_details":{"reasoning_tokens":392}},"tokens_in":674,"tokens_out":484,"duration_ms":4658,"temperature":1.0,"reasoning_tokens":392,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:16:34.079982+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Record the true occupancy of the small update buffers at the moment a global F2 query scans a partition, replay a bursty stream in which one heavy key floods the buffers just before the query, and compare the returned $\\hat{F}_2$ with the exact $F_2$ computed offline; if the estimate deviates by more than the sequential $(\\epsilon,\\delta)$ bounds whenever buffers are far from half full, the projection's core assumption fails.","supporting_citations":[{"cited_title":"Muthukrishnan","cited_arxiv_id":null,"evidence_quote":"Provides the CM+ method for estimating F2 from a Count-Min Sketch, the basis of the per-partition F2 partial results."},{"cited_title":"Intermediate Value Linearizability : A Quantitative Correctness Criterion","cited_arxiv_id":null,"evidence_quote":"Defines Intermediate Value Linearizability and its locality property, used to prove the concurrency semantics of the F2 and other queries."},{"cited_title":"Sketching streams through the net: Distributed approximate query tracking","cited_arxiv_id":null,"evidence_quote":"Provides the F2 estimator used as an accuracy reference in the memory and accuracy evaluation."},{"cited_title":"Time- Lapse Snapshots","cited_arxiv_id":null,"evidence_quote":"Supplies the monotonicity-of-scans notion used to state cross-query consistency properties."}],"review_version":2}