{"id":"d4818feb-c2ec-4307-96ea-c11cd878a25c","arxiv_id":"1908.08656","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Wedge sampling outperforms diamond sampling for budgeted top-k maximum inner product search, and the new deterministic dWedge algorithm achieves high top-10 precision with large speedups on recommender datasets.","lead":"The paper studies approximate top-k search for recommender systems under a strict computation budget, and shows that wedge sampling is simpler and often more accurate than diamond sampling, which it proves is a combination of wedge and basic sampling. It then introduces dWedge, a fast deterministic wedge variant that reaches high precision on standard datasets while running far faster than brute-force search.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"dWedge's headline accuracy rests on the unanalyzed sign-trick extension of §3.2: Theorem 1 is non-negative only, and §3.1 explicitly disclaims the general case.","rationale":"The reader's weakest assumption is exactly the sign-trick extension, and I agree that it is the most load-bearing gap. The non-negative theoretical result (Theorem 1) and the wedge-versus-diamond comparison are internally coherent for positive inputs, and the empirical evaluation is reproducible and consistent on the tested datasets. However, the algorithm actually advertised for general budgeted MIPS is dWedge with signed counters on absolute values, and the paper provides no analysis of this extension; Section 3.1 even concedes that Theorem 1 does not hold for general inputs and leaves a fix to future work. This does not invalidate the empirical claims on the specific recommender datasets, but it does mean the central claim that dWedge is a general, significantly more accurate budgeted MIPS solver is conditional on the sign trick working in practice. The natural check is to run dWedge on a non-negative shift that provably preserves inner-product order: if the shift variant matches the sign-trick accuracy, the concern is resolved; if it fails, the reported accuracy is an artifact of the unanalyzed sign-trick heuristic. Since the reader already assigned CONDITIONAL with moderate confidence, this stress-test does not move the verdict.","tokens_in":13613,"tokens_out":10611,"duration_ms":114021,"concrete_test":"Re-run the Yahoo experiment (§4.4) with the non-negative shift suggested in §3.1: let x'_ij = sgn(q_j)x_ij + c_j with c_j = -min_i sgn(q_j)x_ij, and q'_j = |q_j|, so x'_i·q' = x_i·q + C preserves the top-k order. Run Algorithm 2 on (X', q') with S = n/100, B = 100 and compare Precision@10 and speedup to the reported sign-trick numbers. A material drop in Precision@10 would show the sign-trick counter weights, rather than the deterministic wedge idea, are responsible for the headline accuracy; comparable precision would retire the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weakness is the sign-trick extension in §3.2. Theorem 1 is proved only for non-negative X and q, and the paper states explicitly in §3.1 that 'For the general cases, Theorem 1 does not hold anymore,' with non-negative-order-preserving shifts deferred to future work. Algorithm 2 is then deployed on real matrix-factorization data (which has negative entries) by running on |X| and |q| and incrementing counters by sgn(x_ij)sgn(q_j)*ceil(s_j |x_ij|/c_j), followed by selecting the top-B counters. No theorem or analysis shows that the largest signed counters recover the top-k inner products when inner products can be negative; the only support is the empirical Precision@10 numbers, which are averaged over 5 runs and reported without variance. Because all headline claims (90% Precision@10, 20x-180x speedup) are measured on this unanalyzed extension, the paper's central claim that dWedge is a general budgeted MIPS solver has a real soft spot. This is not an external disagreement: the manuscript itself flags the gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the budgeted top-k maximum inner product search (MIPS) problem, where an algorithm is given a limited number of computational operations. The authors revisit wedge sampling and diamond sampling. They claim that diamond sampling is essentially a combination of wedge sampling and basic sampling, that wedge sampling requires fewer samples than diamond sampling to separate high and low inner products on non-negative data (Theorem 1, Section 3.1), and that their deterministic variant dWedge provides high Precision@10 with large speedups on Netflix, Yahoo, and Gist. The dWedge algorithm (Algorithm 2) greedily walks down each column sorted by value, allocating a column-specific number of samples, and then post-processes the top-B counters. Experiments compare dWedge to randomized wedge/diamond, Greedy-MIPS, and LSH-based solvers. The paper reports that dWedge returns top-10 MIPS with at least 90% accuracy at 20x-180x speedup on large data sets.","tokens_in":13819,"tokens_out":9816,"duration_ms":97511,"significance":"The theoretical part is solid for its stated scope: Theorem 1 is proved from first principles, and the comparison with the diamond bound in Section 3.1 is explicit and algebraically correct under the same non-negative assumptions. dWedge is a simple, plausible heuristic with a clear trade-off mechanism, and the paper provides a code link. If the empirical claims survive, dWedge is a useful practical addition to the budgeted MIPS toolbox. However, the paper's central general-input claims are weaker than the theory supports. The sign-trick extension for negative inputs is explicitly disclaimed in Section 3.1 and unproved in Section 3.2, and the experimental evidence in Section 4 is reported as five-run averages without variance or significance testing. The comparison with Greedy-MIPS in Section 4.3 also uses an asymmetric budget.","major_comments":[{"comment":"The paper's headline accuracy claims (Section 1.2) are for real data sets with negative entries, but the only concentration result, Theorem 1, is proved for non-negative X and q, and Section 3.1 explicitly states 'For the general cases, Theorem 1 does not hold anymore' and defers order-preserving shifts to future work. Algorithm 2 nevertheless uses the sign trick on absolute values and increments counters by sgn(xij)sgn(qj)⌈sjxij/cj⌉. No argument or experiment shows that the top-B counters produced this way recover the top-k inner products when inner products can be negative. This gap is load-bearing because dWedge's superiority is demonstrated on data with negative entries. Please provide a proof or a clear set of sufficient conditions for the sign-trick variant, restrict the paper's claims to non-negative inputs or to a validated non-negative transformation, or add a diagnostic study (e.g., the fraction of true top-10 points present in dWedge's top-B candidate set on the actual data) and state in the abstract that the general-case behavior is a heuristic.","section":"3.2, Algorithm 2"},{"comment":"Section 4.1 states that 'All randomized results are the average of 5 runs,' and the figures report Precision@10 and speedup values without error bars, standard deviations, or statistical significance. For a paper whose central claim is that dWedge provides 'significantly higher accuracy' than other solvers, and where some comparisons are close (e.g., Figure 3(c) at h=512), five runs are insufficient to support the comparison, especially since Wedge, Diamond, and dDiamond are randomized. Please report per-query or per-run variance, the number of queries used, and a significance test or at least the min/max range across runs.","section":"4.1, Figures 1-3"},{"comment":"The comparison with Greedy-MIPS is not made at equal budgets. For Netflix-200 and Netflix-300, Section 4.3 sets Bg = 2S/d+B+50 and Bg = 2S/d+B+20, respectively, giving Greedy more post-processing operations than dWedge, and the speedup shown in Figure 2 is based on the paper's own cost model rather than measured wall-clock time. This makes the statement that dWedge 'runs slightly faster and provides dramatically higher accuracy' hard to interpret as a fair head-to-head. Please provide an equal-budget comparison (same total operation count, or measured time for screening plus ranking for both methods with identical B), and report the accuracy-vs-time trade-off without inflating the baseline's budget.","section":"4.3, Figure 2"}],"minor_comments":[{"comment":"The abstract states that dWedge maintains 'top-5 precision at least 80%,' while the body (Sections 1.2 and 4.3) claims 'top-10 MIPS' and 'Precision@10.' Please align the abstract with the body.","section":"Abstract and Section 1.2"},{"comment":"Figure 2 captions contain typos: 'Bugdet' and 'Samle size.'","section":"Figure 2"},{"comment":"Section 2.3 would benefit from a precise description of how diamond sampling updates counters: the expectation computation E[Zi] implies a weighted increment, whereas Algorithm 1 increments a counter by 1 for wedge; the difference should be stated explicitly so that the claim that 'diamond follows the same procedure as wedge' is checkable.","section":"2.3"},{"comment":"Section 3.2: The cost model '2S/d + B inner product computation' is an approximation of dWedge's operation count; please clarify whether hash-table lookups and ceil operations are included, because the model is used to tune S and B and to compute speedups.","section":"3.2"},{"comment":"In Section 4.4, the text says RangeLSH estimates x·q as mi cos π(1-p) while the sign issue is discussed; a few sentences explaining why SimpleLSH does not suffer the same issue would improve clarity.","section":"4.4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript includes a public code link and does not misrepresent the existence of the sign-trick gap; the gap is stated in the text. My main concern for the editor is that the authors may need to either substantially extend the analysis or narrow the claims before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nRead this one if you care about approximate top-k retrieval on a budget. The paper does two things: it shows diamond sampling is just wedge sampling composed with basic sampling, and it introduces dWedge, a deterministic wedge-based algorithm that is simple, fast, and strongly competitive on standard recommender datasets. The decomposition is correct and useful, and the theoretical sample-complexity comparison for non-negative inputs is sound.\n\nThat said, the main advertised performance of dWedge is on data with negative entries, where the algorithm relies on a sign trick: run on absolute values, then accumulate signed counters. The paper's Theorem 1 explicitly does not apply to general inputs — Section 3.1 says so — and the authors defer an order-preserving transformation to future work. So there is a real gap between the analysis and the deployed algorithm. This is the single biggest weakness. It does not invalidate the empirical results, which are consistent and reproducible, but it means the central claim 'dWedge is a general budgeted MIPS solver' is only empirically supported.\n\nOther soft spots are minor by comparison: randomized results are averages over 5 runs with no variance reported; the cost model used to tune S and B is reasonable but slightly favorable to dWedge; and in the Greedy comparison they add extra inner-product computations to Greedy to equalize speedup, which is disclosed but should be kept in mind. The abstract also says 'top-5 precision at least 80%' while the body uses Precision@10 — a wording inconsistency.\n\nOverall, the paper is honest about its limitations, ships code and data, and presents a clearly useful heuristic. The wedge-vs-diamond reduction alone is worth a citation. I'd send it to peer review, with a request that the authors either extend the analysis to the sign-trick setting (even under distributional assumptions) or explicitly frame dWedge as a heuristic for non-negative data, and that they report error bars.","headline":"Solid budgeted-MIPS paper with a correct wedge/diamond decomposition and a strong empirical heuristic; main weakness is that the theory doesn't cover the sign-trick used on real data.","tokens_in":14344,"tokens_out":2485,"would_cite":true,"duration_ms":25688,"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":"A deterministic variant of wedge sampling can answer budgeted top-k maximum inner product search with high accuracy and large speedups.","keywords":["budgeted maximum inner product search","wedge sampling","diamond sampling","sampling-based top-k retrieval","deterministic sampling heuristic","recommender systems","locality-sensitive hashing"],"falsifier":"Generate a synthetic data set with mixed-sign entries where the true maximum inner products are negative or where the highest $|\\text{inner product}|$ items are not the highest inner product items; run dWedge with $S = n/100$ and $B = k$ and measure Precision@k against brute force. If precision falls far below the non-negative case, the sign-trick assumption is the culprit; the paper gives no bound covering this regime.","tokens_in":13386,"feed_emoji":"🎯","tokens_out":6242,"duration_ms":59115,"temperature":0.7,"pith_summary":"The paper sets out to show that wedge sampling, an old technique for approximating matrix multiplication, is the right engine for budgeted top-k maximum inner product search (MIPS), where an algorithm may spend only a fixed number of operations and must still return a good approximation of the top-k items. It claims that diamond sampling, the current state of the art for this problem, is really just wedge sampling combined with basic sampling, and that wedge needs strictly fewer samples to separate high from low inner products. The paper then contributes dWedge, a deterministic variant that pre-sorts each coordinate and greedily draws samples from the largest entries instead of sampling randomly. If the paper is right, a simple, tunable method can deliver at least 80% Precision@10 on standard recommender datasets and, at scale, top-10 accuracy around 90% with speedups of 20x to 180x over brute force.","feed_headline":"dWedge finds top-10 items within a budget at 90% precision","feed_subtitle":"The deterministic wedge sampler runs 20–180x faster than brute force on recommender datasets.","key_machinery":"The load-bearing object is the wedge sampling distribution: a row $i$ is drawn with probability $z_i / z = (x_i \\cdot q) / \\sum_i x_i \\cdot q$, implemented by first choosing column $j$ with probability $q_j c_j / z$ and then row $i$ from that column with probability $x_{ij} / c_j$. dWedge keeps the column-level allocation $s_j = S c_j q_j / z$ but replaces the random second draw with a deterministic scan down each column sorted by $x_{ij}$, giving the largest entries $\\lceil s_j x_{ij} / c_j \\rceil$ counter votes each. This is what lets dWedge spend an $o(n)$ budget without the random sub-sampling failure that afflicts wedge and diamond when $S/d$ is far smaller than $n$.","core_discovery":"The central claim is that the usefulness of wedge sampling for MIPS has been underestimated, and that its random sampling step is replaceable by a deterministic greedy step. Concretely, the paper proves (Theorem 1) that on non-negative data, $S \\ge \\frac{3z \\ln n}{(\\sqrt{\\tau_1}-\\sqrt{\\tau_2})^2}$ samples suffice to separate every point with inner product at least $\\tau_1$ from every point with inner product at most $\\tau_2$. It also argues this is strictly fewer samples than diamond sampling needs. dWedge translates this into practice: for each dimension $j$ it computes $s_j = S c_j q_j / z$, walks down the pre-sorted list of $x_{ij}$ values, and credits each visited point with $\\lceil s_j x_{ij} / c_j \\rceil$ votes. The points with the largest counters become the candidate set, and their exact inner products are computed for final ranking. On Netflix-300, Yahoo, and Gist, dWedge maintains Precision@10 above 80%, and on Yahoo it reaches about 90% at a measured speedup close to 180x.","pith_inferences":["The sign-trick extension is the paper's unsupported step: Theorem 1 is proved only for non-negative data, and the paper states it does not hold in general, yet dWedge is deployed on real data through absolute values. A natural test is to benchmark dWedge against a variant that treats negative coordinates separately on synthetic mixed-sign data.","Because dWedge allocates samples proportionally to column contribution $q_j c_j / z$, its advantage should be largest when inner products are dominated by a few coordinates; in very high dimension with uniform coordinates, the greedy scan may degrade toward random sampling.","The same deterministic sampling idea could be lifted from a matrix-vector product $Xq$ to matrix-matrix products, replacing the top-k MIPS histogram with a top-element histogram, though the paper does not explore that extension."],"forward_implications":["Budgeted top-k MIPS can be solved well by a method whose only preprocessing is sorting each dimension once; no hash tables or LSH parameters need tuning per query.","Diamond sampling's advantage over wedge disappears once the random row draw is replaced by a deterministic greedy pass, since diamond inherits wedge's probability structure and adds basic sampling overhead.","dWedge's two parameters, sample count $S$ and candidate count $B$, give a direct quality–speed knob that LSH-based solvers lack because their trade-off is fixed at construction time.","On the tested recommender data, dWedge beats Greedy-MIPS and LSH solvers in accuracy at equal or better speed, with top-10 recall of 90% and 20x–180x speedups on large datasets."],"supporting_citations":[{"why":"Introduces wedge sampling for approximating matrix multiplication; the paper's central method is a deterministic variant of it.","marker":"[5]"},{"why":"Introduces diamond sampling, the state-of-the-art baseline that the paper decomposes into wedge plus basic sampling.","marker":"[4]"},{"why":"Greedy-MIPS, a principal budgeted MIPS competitor that dWedge is measured against.","marker":"[30]"},{"why":"SimpleLSH, an LSH-based MIPS solver used as a baseline.","marker":"[20]"},{"why":"RangeLSH, an improved LSH baseline that the paper compares against.","marker":"[29]"},{"why":"Source of the Netflix and Yahoo recommender datasets used in the evaluation.","marker":"[7]"},{"why":"Provides the distributional analysis for handling negative inputs via the sign trick.","marker":"[9]"}],"fun_headline_variants":["dWedge: deterministic wedge for budgeted MIPS, 180x faster","Budgeted MIPS: wedge sampling needs fewer samples, runs faster","Wedge beats diamond for budgeted top-k MIPS","dWedge: 180x speedup with 80%+ precision on MIPS","Deterministic wedge sampler: top-k MIPS under budget"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that sampling on absolute values of the data and query, with signs restored only in the final counter increments, preserves the relative ordering of true inner products well enough for dWedge's greedy histogram; the paper's own concentration bound is limited to non-negative inputs and explicitly fails for general cases.","fun_headline_variants_meta":{"raw":{"variants":["dWedge: deterministic wedge for budgeted MIPS, 180x faster","Budgeted MIPS: wedge sampling needs fewer samples, runs faster","Wedge beats diamond for budgeted top-k MIPS","dWedge: 180x speedup with 80%+ precision on MIPS","Deterministic wedge sampler: top-k MIPS under budget"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000795,"raw_usage":{"total_tokens":3526,"prompt_tokens":1000,"completion_tokens":2526,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":2430}},"tokens_in":616,"tokens_out":2526,"duration_ms":19206,"temperature":1.0,"reasoning_tokens":2430,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:33:13.302053+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Generate a synthetic data set with mixed-sign entries where the true maximum inner products are negative or where the highest $|\\text{inner product}|$ items are not the highest inner product items; run dWedge with $S = n/100$ and $B = k$ and measure Precision@k against brute force. If precision falls far below the non-negative case, the sign-trick assumption is the culprit; the paper gives no bound covering this regime.","supporting_citations":[{"cited_title":"Cohen and D","cited_arxiv_id":null,"evidence_quote":"Introduces wedge sampling for approximating matrix multiplication; the paper's central method is a deterministic variant of it."},{"cited_title":"Ballard, T","cited_arxiv_id":null,"evidence_quote":"Introduces diamond sampling, the state-of-the-art baseline that the paper decomposes into wedge plus basic sampling."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Greedy-MIPS, a principal budgeted MIPS competitor that dWedge is measured against."},{"cited_title":"Neyshabur and N","cited_arxiv_id":null,"evidence_quote":"SimpleLSH, an LSH-based MIPS solver used as a baseline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"RangeLSH, an improved LSH baseline that the paper compares against."},{"cited_title":"Cremonesi, Y","cited_arxiv_id":null,"evidence_quote":"Source of the Netflix and Yahoo recommender datasets used in the evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the distributional analysis for handling negative inputs via the sign trick."}],"review_version":1}