{"id":"eb064dde-3683-4b26-b530-0d513291b30f","arxiv_id":"2505.12293","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Hidden Sketch combines a reversible Bloom filter and a Count-Min sketch to recover heavy hitter keys and exact frequencies from roughly 1.44 n l bits plus a linear number of counters.","lead":"Hidden Sketch is a new streaming data structure that tracks the most frequent items in a data stream using far less memory than storing item keys explicitly, by hiding keys inside compact filters and reconstructing them later. A smart generalist might read this because accurate heavy hitter detection at small memory cost matters for network monitoring, fraud analytics, and any high-speed stream pipeline.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central exact-frequency-decoding claim rests on an unproven and in fact false assertion that ILP recovers true frequencies from rank-deficient CM systems; explicit rank-deficient instances with multiple nonnegative integer solutions refute it, so guaranteed reversibility does not hold.","rationale":"The reader's weakest_assumption is exactly the ILP/SVD exactness step, and my stress test agrees: that step is not merely missing a proof; it is false as stated. The constructed rank-deficient instance has two nonnegative integer solutions to the same CM system, so no objective-free ILP can be guaranteed to return the true frequencies. The pure-bucket peeling does not help, since there are no pure buckets. This undermines the strongest claimed contribution ('can record both the key and frequency exactly'). The sign error in Theorem A.4 is a secondary, repairable issue. I do not recommend REJECT: the RBF key-recovery idea, the hybrid design, and the empirical F1/ARE results are plausible contributions, and a revised claim of 'high-probability approximate decoding' or 'exact under stated rank/uniqueness conditions' would be supported. Hence the conditional verdict stands as the appropriate outcome.","tokens_in":14480,"tokens_out":12474,"duration_ms":132942,"concrete_test":"Run the authors' decoding pipeline on the explicit counterexample above: hash signatures {1,2,5}, {2,3,5}, {3,4,5}, {4,1,5}, primes 2,3,5,7, true frequencies (100,80,60,40), and bucket vector equal to ΦΣ_p x. After pure-bucket peeling (queue is empty), solve the residual system with the reported ILP step (no objective) and compare against (100,80,60,40). If the solver returns (205,10,102,10) or any other vector, the ILP exactness claim is refuted. Also run the decoder on 100 random rank-deficient instances with n=100, m=80, d=3 and true random nonnegative integer frequencies; count how often the returned vector differs from the true one.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In §3.3 the paper asserts that an ILP with no objective 'can yield actual frequencies even when the matrix is not full rank.' This is the load-bearing step for the central exactness claim. An ILP with no objective returns an arbitrary feasible point, and if the feasible region has more than one nonnegative integer vector, exact recovery is not guaranteed. Such multiplicity is concrete. Take d=3 hash functions, m=5 buckets, and four candidate keys with hash sets {1,2,5}, {2,3,5}, {3,4,5}, {4,1,5}. Let the primes be p=(2,3,5,7) and true frequencies x=(100,80,60,40). The integer vector z=(105,-70,42,-30) is in the null space of ΦΣ_p: the prime-weighted contributions cancel at every one of the five buckets. Hence x'=x+z=(205,10,102,10) is also a nonnegative integer solution to the same CM equations. No bucket is pure (buckets 1-4 contain two keys, bucket 5 contains four), so pure-bucket peeling terminates immediately; SVD gives a least-norm real solution, not necessarily an integer one; and an ILP without an objective can return x' or any other feasible point. Thus 'exactly decoding n items' is not guaranteed. The sign error in Theorem A.4 (m=(k-l)n/ln2) is real but repairable; the ILP uniqueness gap is not.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Hidden Sketch, a reversible sketch that combines a Reversible Bloom Filter (RBF) for implicit key encoding with a Count-Min (CM) sketch for frequency encoding. Keys are recovered bottom-up through hierarchical bitmaps and segment Bloom filters; frequencies are recovered by treating the CM sketch as a linear system, solved via pure-bucket peeling followed by SVD or, as an optimization, an integer linear program (ILP) with prime-weighted increments. The paper claims that this design records both keys and frequencies exactly with memory bounded by about 1.23 n w + 1.44 n l bits, and reports experiments on CAIDA, MAWI, and IMC showing F1 scores near 1 and low ARE under tight memory budgets. The theoretical appendix derives RBF memory bounds and cites prior hypergraph peeling results for the CM portion.","tokens_in":14761,"tokens_out":8518,"duration_ms":83413,"significance":"If the exactness and space-efficiency claims were correct, Hidden Sketch would be a meaningful contribution: it would allow exact key and frequency recovery at Bloom-filter-level memory, improving on FlowRadar's fragility and Reversible Sketch's memory overhead. The RBF design, which hierarchically encodes key segments into bitmaps and Bloom filters, is an original idea and the paper ships open-source code. However, the central advertised guarantee of exact frequency decoding is not supported and, as shown below, is false under the paper's own ILP formulation. The memory-bound proof also contains a sign error and an unproven 'best case' bound. The experimental results are promising but do not compensate for the broken theoretical core.","major_comments":[{"comment":"The claim that Integer Linear Programming 'can yield actual frequencies even when the matrix is not full rank' is false as stated. Consider d=3 hash functions, m=5 buckets, and four candidate keys with hash sets {1,2,5}, {2,3,5}, {3,4,5}, and {4,1,5}. Let the primes be (2,3,5,7) and the true frequencies x=(100,80,60,40). The vector z=(105,-70,42,-30) lies in the null space of ΦΣ_p: at every bucket the prime-weighted contributions cancel, e.g., bucket 1 receives 2·105 + 7·(-30)=0. Therefore x'=x+z=(205,10,102,10) is another nonnegative integer solution to the same Count-Min equations. No bucket is pure (buckets 1-4 contain two keys and bucket 5 contains four), so pure-bucket peeling terminates immediately. SVD returns the least-norm real solution, which is not guaranteed to be x, and an ILP with no objective can return x' or any other feasible point. Thus the statement in §3.3 is not a guarantee, and the Abstract's 'guaranteed reversibility' is unsupported. Moreover, the assertion in §3 that false positives from the RBF can be filtered because their decoded frequencies are zero fails whenever the linear system has multiple nonnegative integer solutions.","section":"§3.3, Eq. (1)"},{"comment":"The proof of Theorem A.4 contains a sign error in the intermediate memory expression. It states that an additional m = (k-l)n/ln2 bits are needed to achieve the target false positive rate. From Lemma A.1, reducing the false positive rate from 2^{-(l-k)} to O(1) requires m ≈ (l-k)n/ln2 bits, not (k-l)n/ln2. As printed, the total becomes (2k-l)n/ln2, which contradicts the theorem's nl/ln2. The final statement is correct after replacing (k-l) by (l-k), but the proof as written is invalid and must be corrected.","section":"Appendix A, Theorem A.4"},{"comment":"The claimed total memory bound of 'less than 1.23 n w + 1.44 n l bits in the best case' is not established. The only rigorous bound cited is the pure-peeling condition m > c_k n from references [23,24]. The paper states that the SVD and ILP steps lower the required number of buckets but provides no analysis, no theorem, and no bound for the resulting scheme. Consequently the 'best case' memory bound is an unsupported assertion, and the space-efficiency contribution is not proven.","section":"§3.2 and Appendix A"},{"comment":"The paper asserts that SVD provides 'mathematical guarantees for approximate or exact solutions' but does not state what guarantee applies to the decoded integer frequencies. When Φ is rank-deficient, the least-norm solution is generally a real vector, not the true integer frequency vector. The paper does not prove that the residual system after pure-bucket extraction has full column rank, nor that the least-norm real solution coincides with the true nonnegative integer solution. The empirical success rate in Figure 6, while suggestive, is not a substitute for the claimed guarantee.","section":"§3.2, SVD step"}],"minor_comments":[{"comment":"Line 8 contains a typo: 'dequeque' should be 'dequeue'. Also, the algorithm's loop and variable naming (e.g., 'Bucekt' in the comment) should be cleaned up.","section":"Algorithm 2"},{"comment":"The hash function for the bitmap block array is written as H(key)=h(key)*2^l + seg(key), which is ambiguous because seg(key) denotes a segment value, not a function selecting a bitmap. The notation should distinguish the segment index from the segment value.","section":"§3.1.1"},{"comment":"The proofs of Theorems A.2 and A.3 are approximate: expressions such as 'Due to the Lyapunov Central Limit Theorem' and the use of Jensen's inequality with '≈' do not constitute formal error bounds. Since Theorem A.4 depends on these approximations, the RBF memory proof should either be made rigorous or explicitly labeled as heuristic.","section":"Appendix A, Theorems A.2 and A.3"},{"comment":"Figure 6 reports success rates from 1000 trials but does not describe the hash functions, the prime assignment, or the frequency distribution used in the simulation. Add these experimental details and report confidence intervals or error bars.","section":"§5.2, Figure 6"},{"comment":"The cold filter parameters (CU sketch size and filtering threshold) are not reported in the experimental setup. Since the two-stage framework's accuracy depends on these free parameters, a sensitivity analysis or explicit parameter listing is needed.","section":"§5.1.4"}],"recommendation":"reject","confidential_remarks":"The counterexample in Major Comment 1 is decisive: it shows that the paper's central guarantee of exact frequency decoding via ILP is false as stated. The authors could in principle remove the ILP claim and present Hidden Sketch as a heuristic, but that would eliminate the claimed advantage over prior pure-peeling methods such as FlowRadar and would leave the memory-bound theorem without its main justification. Given the paper's advertised contribution is exactly 'guaranteed reversibility' with high space efficiency, I recommend rejection rather than major revision. The RBF hierarchical encoding idea and the experimental results are interesting, but they do not overcome the falsified theoretical core."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: Hidden Sketch is a clever combination that mostly works in experiments, but the paper's central theoretical claim—exact frequency recovery via ILP on a rank-deficient CM system—is false as stated. I can give you a concrete counterexample from the paper's own setup.\n\nThe new thing here is real: the hierarchical segment encoding of the Reversible Bloom Filter for key recovery, decoupled from frequency recovery as a linear system over a CM sketch, is a genuine departure from Reversible Sketch and FlowRadar. The two-stage cold filter is sensible. The experiments are extensive and show F1 near 1 at 100KB on three real datasets, and the code is open. That's a meaningful data point for network monitoring.\n\nBut the load-bearing claim doesn't hold. In §3.3 they say ILP 'can yield actual frequencies even when the matrix is not full rank' because it searches the nonnegative integer solution space. With no objective, an ILP returns any feasible point. Non-uniqueness is real. Take 4 keys, 5 buckets, 3 hash functions with hash sets {1,2,5}, {2,3,5}, {3,4,5}, {4,1,5}; primes (2,3,5,7); true counts (100,80,60,40). The vector (105,-70,42,-30) lies in the null space of ΦΣ_p, so (205,10,102,10) is another nonnegative integer solution to the same equations. No bucket is pure, so peeling stops immediately; SVD gives a least-norm real solution; the ILP can legally return the wrong vector. 'Guaranteed reversibility' collapses.\n\nThis is not a nitpick. The exactness claim is the paper's headline and the motivation for the prime-weighting optimization. The experiments may still hold in practice—the system may often be full rank—but the paper needs to either prove sufficient conditions for uniqueness or weaken the claim to high-probability approximate decoding.\n\nSecondary issues: Theorem A.4 has a sign error (the second term should be (l−k)n/ln2, not (k−l)n/ln2) and the SVD step's exactness for rank-deficient systems is asserted without proof. The rank-bound citation to [23,24] is reasonable but the adaptation should be explicit.\n\nVerdict: worth a serious referee. The design and experiments deserve engagement, but the theoretical section needs substantial revision before the paper can stand.","headline":"A clever hybrid sketch with strong experiments, but the central exact-frequency decoding guarantee is false as stated; the paper needs a major theoretical revision.","tokens_in":15304,"tokens_out":3665,"would_cite":false,"duration_ms":34334,"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":"Hidden Sketch claims to record heavy-hitter keys and exact frequencies in memory close to a Bloom filter's, and reports near-perfect F1 scores at 100 KB.","keywords":["data streams","heavy hitters","reversible sketch","Count-Min sketch","Bloom filter","frequency estimation","key recovery","space efficiency"],"falsifier":"Take a synthetic stream with a known set of $n$ keys whose hashes make the CM matrix rank-deficient after pure-bucket peeling, so the residual system has multiple nonnegative integer solutions; run the ILP decoder with no objective and check whether it returns the true frequency vector. If it returns any other feasible vector, the claimed guaranteed reversibility fails. A simpler observable version: measure exact-decoding success on Zipf streams as $m/n$ falls below the stated constants (e.g., 1.222 for three hash functions), where the paper's own theory predicts failure with probability $O(n^{-k+2})$.","tokens_in":14234,"feed_emoji":"📊","tokens_out":4093,"duration_ms":40646,"temperature":0.7,"pith_summary":"Hidden Sketch is a reversible data structure that claims to record both the identity and exact frequency of frequent stream items in roughly Bloom-filter-sized memory. It stores keys implicitly in a hierarchical Reversible Bloom Filter and stores frequencies in a Count-Min sketch treated as a linear system, then decodes keys by recursive candidate-set concatenation and frequencies by bucket peeling followed by SVD or integer linear programming. The paper proves a space bound of about $1.23 n w + 1.44 n l$ bits for $n$ items, and reports F1 scores near 1 on three network-traffic datasets even at 100 KB. If correct, this removes the usual trade-off between reversibility and memory in heavy-hitter tracking.","feed_headline":"Hidden Sketch recovers exact stream keys and counts at 100 KB","feed_subtitle":"A reversible Bloom filter stores keys, a Count-Min system stores frequencies, and peeling plus ILP decodes both.","key_machinery":"The central object is the pair consisting of the Reversible Bloom Filter and the Count-Min linear system. The RBF splits each key into $l/k$-bit segments arranged in a tree, stores leaf segments in per-block bitmaps and internal segments in ordinary Bloom Filters, so that bit positions themselves encode the key. The CM sketch is read as $\\Phi \\mathbf{x} = \\mathbf{y}$, where $\\Phi$ is the bucket-item incidence matrix; pure-bucket peeling solves the triangular part, and SVD or ILP resolves the residual, with prime-weighted increments making integer solutions sparser. This combination is what lets the structure be inverted without storing keys explicitly.","core_discovery":"The paper claims that key and frequency encoding can be separated: a Reversible Bloom Filter with 1-bit buckets encodes keys through bucket indices, and the CM Sketch encodes frequencies as a linear map $\\Phi \\mathbf{x} = \\mathbf{y}$. The RBF's hierarchical decomposition of the key into segments lets the decoder recover candidate keys by taking Cartesian products of segment candidate sets and filtering through per-node Bloom Filters, avoiding full key-space traversal. Frequencies are then recovered exactly by peeling pure buckets and solving the residual system with SVD or ILP; false-positive keys are discarded because their decoded frequency is zero. The paper asserts this yields guaranteed reversibility and exact frequency recovery with high probability, and that the total memory for $n$ items is less than $1.23 n w + 1.44 n l$ bits.","pith_inferences":["The same separation between a bit-level key filter and a linear frequency sketch could be ported to other linear summaries, such as Count sketch or moment sketches, to make them reversible; the paper tests only the Count-Min combination.","The prime-weighted increment trick suggests a general recipe: use coprime per-item weights so that null-space solutions become non-integer or sparse, but whether this preserves update speed at line rate with many items is untested.","The memory bound of $1.44 n l$ bits for the RBF assumes segment distributions are independent and that data skew does not blow up the Cartesian product of candidate sets; on adversarial skew the candidate sets could grow large, making the practical bound data-dependent.","A stress test not reported in the paper is to vary the bucket-to-key ratio $m/n$ on a Zipf stream and record exact-decoding success; the paper's Figure 6 hints the ILP step can succeed below $m=n$, but no closed-form bound for that step is proven."],"forward_implications":["If the space bound holds, a stream processor can track heavy hitters with key-level fidelity using memory comparable to a Bloom filter, enabling on-chip deployment in routers and switches.","Exact frequency recovery for reported keys means heavy-changer detection can compare true counts between windows instead of noisy estimates.","The RBF's hierarchical decoding returns a candidate key set equivalent in result to full key-space traversal but with less work, so false-positive keys are cheaply filtered by their zero decoded frequency.","The two-stage cold filter concentrates memory on significant items: infrequent items receive estimates, while frequent items receive exact keys and counts."],"supporting_citations":[{"why":"Defines the Count-Min sketch, the frequency-recording component that Hidden Sketch treats as a linear system.","marker":"[5]"},{"why":"Introduces the reversible sketch with index-based key encoding that Hidden Sketch extends and improves.","marker":"[14]"},{"why":"Provides FlowRadar's pure-bucket peeling idea and the hypergraph 2-core decoding analysis that motivates the CM peeling step.","marker":"[17]"},{"why":"Supplies the rank bound for random (0,1)-matrices used to bound the probability of decoding failure.","marker":"[23]"},{"why":"Gives the invertible Bloom lookup table peeling guarantee that supports the pure-bucket extraction success probability.","marker":"[24]"},{"why":"Treats sketches as compressive-sensing linear systems, the basis for the SVD and pseudo-inverse frequency decoding.","marker":"[22]"},{"why":"Provides the Bloom filter false-positive memory bound used in the RBF space analysis.","marker":"[29]"}],"fun_headline_variants":["Hidden Sketch: exact heavy hitters via dual reversible encoding","Peel and solve: reversible sketch for exact stream frequency tracking","RBF plus CM sketch: invertible design recovers keys and counts","Hidden Sketch: exact keys and frequencies from a single reversible structure","Dual-layer reversible sketch decodes heavy hitters without memory blowup"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim that frequencies are recovered exactly rests on the unproven assertion that the integer-linear-programming step returns the true nonnegative integer frequencies even when the CM matrix is not full rank, and that the SVD step's least-norm solution can be corrected to the true counts.","fun_headline_variants_meta":{"raw":{"variants":["Hidden Sketch: exact heavy hitters via dual reversible encoding","Peel and solve: reversible sketch for exact stream frequency tracking","RBF plus CM sketch: invertible design recovers keys and counts","Hidden Sketch: exact keys and frequencies from a single reversible structure","Dual-layer reversible sketch decodes heavy hitters without memory blowup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000958,"raw_usage":{"total_tokens":4043,"prompt_tokens":866,"completion_tokens":3177,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":482,"completion_tokens_details":{"reasoning_tokens":3088}},"tokens_in":482,"tokens_out":3177,"duration_ms":23007,"temperature":1.0,"reasoning_tokens":3088,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:37:21.533707+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a synthetic stream with a known set of $n$ keys whose hashes make the CM matrix rank-deficient after pure-bucket peeling, so the residual system has multiple nonnegative integer solutions; run the ILP decoder with no objective and check whether it returns the true frequency vector. If it returns any other feasible vector, the claimed guaranteed reversibility fails. A simpler observable version: measure exact-decoding success on Zipf streams as $m/n$ falls below the stated constants (e.g., 1.222 for three hash functions), where the paper's own theory predicts failure with probability $O(n^{-k+2})$.","supporting_citations":[{"cited_title":"Reversible sketches: enabling monitoring and analysis over high-speed data streams","cited_arxiv_id":null,"evidence_quote":"Introduces the reversible sketch with index-based key encoding that Hidden Sketch extends and improves."},{"cited_title":"Flowradar: a better netflow for data centers","cited_arxiv_id":null,"evidence_quote":"Provides FlowRadar's pure-bucket peeling idea and the hypergraph 2-core decoding analysis that motivates the CM peeling step."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the rank bound for random (0,1)-matrices used to bound the probability of decoding failure."},{"cited_title":"Invertible bloom lookup tables","cited_arxiv_id":null,"evidence_quote":"Gives the invertible Bloom lookup table peeling guarantee that supports the pure-bucket extraction success probability."},{"cited_title":"Toward Nearly-Zero-Error sketching via compressive sensing","cited_arxiv_id":null,"evidence_quote":"Treats sketches as compressive-sensing linear systems, the basis for the SVD and pseudo-inverse frequency decoding."},{"cited_title":"Dillinger and Panagiotis Manolios","cited_arxiv_id":null,"evidence_quote":"Provides the Bloom filter false-positive memory bound used in the RBF space analysis."}],"review_version":1}