Pith. sign in

REVIEW 3 major objections 5 minor 31 references

Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A deterministic variant of wedge sampling can answer budgeted top-k maximum inner product search with high accuracy and large speedups.

desk verdict 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. read the letter →

arxiv 1908.08656 v2 pith:D2PAWJJ6 submitted 2019-08-23 cs.DB cs.IR

Stephan S. Lorenzen , Ninh Pham This is my paper · ORCID
classification cs.DBcs.IR
keywords budgetedmaximuminnerproductsearchwedgesamplingdiamondsampling-basedtop-kretrievaldeterministicheuristicrecommendersystemslocality-sensitivehashing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [3.2, Algorithm 2] 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.
  2. [4.1, Figures 1-3] 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.
  3. [4.3, Figure 2] 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.
minor comments (5)
  1. [Abstract and Section 1.2] 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.
  2. [Figure 2] Figure 2 captions contain typos: 'Bugdet' and 'Samle size.'
  3. [2.3] 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.
  4. [3.2] 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.
  5. [4.4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the theoretical bounds are derived from first principles and the empirical claims are measured against external baselines; the acknowledged sign-trick gap is a limitation, not a circular reduction.

full rationale

I find no load-bearing circular step. Theorem 1 is a standard concentration bound proved from Markov's inequality with the sampling probabilities p1 and p2 defined from the input distribution; the sample-complexity expression is derived algebraically and does not assume the desired ordering of counters. The wedge-versus-diamond comparison uses the diamond bound from Ballard et al. as an external baseline, and the inequality K||q||_1 >= tau follows directly from the stated positivity assumption, so wedge's smaller sample bound is a genuine consequence rather than a restatement. The characterization of diamond as a combination of wedge and basic sampling is an explicit algebraic identity for E[Zi], not an input assumed to prove the paper's claims. dWedge is presented as a heuristic deterministic variant; its accuracy and speedup claims are validated empirically against brute-force search and external algorithms (Greedy-MIPS, SimpleLSH, RangeLSH), and no fitted parameter is renamed as a prediction. The sign-trick extension for negative inputs is explicitly conceded as unanalyzed in Section 3.1 ('For the general cases, Theorem 1 does not hold anymore') and in Section 3.2, and the paper does not invoke Theorem 1 to justify the signed dWedge; this is a correctness and scope limitation, not a circular derivation. The paper contains no load-bearing self-citations: references [4], [9], and [30] are prior work by other authors, so the uniqueness-import and ansatz-smuggling patterns do not apply. Therefore the derivation chain is self-contained and the circularity score is 0.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central theoretical result rests on standard concentration inequalities and a non-negativity assumption. The practical dWedge algorithm introduces no new physical or mathematical entities, but it does depend on user-chosen S and B, an unproven sign-trick extension, and an empirical cost model used to make speedup comparisons fair.

free parameters (2)
  • S (sample count) = S = n/5 to n on Netflix, S = 4,500 on Yahoo, S = n/8 to 2n on Gist
    Chosen per dataset and per experiment to demonstrate trade-offs. The reported precision and speedup numbers depend on this user-selected budget.
  • B (post-processing budget) = B = 100 for most comparisons, B = 40 for Table 1
    Chosen by hand as the number of exact inner products computed on candidates. Jointly with S it defines the claimed cost and accuracy.
assumptions (4)
  • domain assumption X and q are non-negative for Theorem 1 and for the theoretical wedge-versus-diamond comparison.
    Section 2 begins with the assumption of non-negative inputs, and Section 3.1 analyzes 'wedge sampling on non-negative inputs.' The theorem and sample bound hold only in this regime.
  • ad hoc to paper The sign trick preserves enough of the top-k ordering for dWedge on general inputs.
    Section 3.2 executes dWedge on absolute values and increments counters by sign terms, with no proof that top-B by signed counter recovers top-k. The paper explicitly calls dWedge a heuristic.
  • standard math Markov inequality and union bound are valid tools for the concentration proof.
    Used in the proof of Theorem 1 to bound the probability that two counters are ordered incorrectly.
  • domain assumption dWedge's operation cost is modeled as 2S/d + B inner product computations.
    Section 3.2 states the cost is upper bounded by 2S/d + B and calls the model 'very accurate' empirically. This model is used to set S and B and to estimate speedups against Greedy and LSH.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search." pith.science (2026). https://pith.science/paper/D2PAWJJ6

@misc{pith2026190808656,
  author       = {Pith},
  title        = {Pith review of: Revisiting Wedge Sampling for Budgeted Maximum Inner Product Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D2PAWJJ6}},
  note         = {Machine review of arXiv:1908.08656}
}
read the original abstract

Top-k maximum inner product search (MIPS) is a central task in many machine learning applications. This paper extends top-k MIPS with a budgeted setting, that asks for the best approximate top-k MIPS given a limit of B computational operations. We investigate recent advanced sampling algorithms, including wedge and diamond sampling to solve it. Though the design of these sampling schemes naturally supports budgeted top-k MIPS, they suffer from the linear cost from scanning all data points to retrieve top-k results and the performance degradation for handling negative inputs. This paper makes two main contributions. First, we show that diamond sampling is essentially a combination between wedge sampling and basic sampling for top-k MIPS. Our theoretical analysis and empirical evaluation show that wedge is competitive (often superior) to diamond on approximating top-k MIPS regarding both efficiency and accuracy. Second, we propose a series of algorithmic engineering techniques to deploy wedge sampling on budgeted top-k MIPS. Our novel deterministic wedge-based algorithm runs significantly faster than the state-of-the-art methods for budgeted and exact top-k MIPS while maintaining the top-5 precision at least 80% on standard recommender system data sets.

Figures

Figures reproduced from arXiv: 1908.08656 by the authors.

Figure 1
Figure 1. Comparison of accuracy and speedup between dWedge, dDiamond, Wedge and Diamond on Netflix-200 and Netflix-300 when fixing B = 100 and varying S. generators. For each sampling scheme, we consider two corresponding variants, including Wedge, Diamond, dWedge and dDiamond. We measure their perfor￾mance on Precision@10 value and speedup over the brute-force search where we varied the sample size S and fix B = 100 for pos… view at source ↗
Figure 2
Figure 2. Comparison of accuracy and speedup between dWedge and Greedy when fixing S = 10, 000 and varying B on Netflix-200 (a, b); fixing S = 4, 500 and varying B on Netflix-300 (c, d); fixing S = 4, 500 and varying B on Yahoo (e, f); and fixing B = 200 and varying S on Gist (g, h). most 40% on Netflix-200. On Yahoo in [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Comparison of accuracy and speedup between dWedge (S = n/100 for Yahoo, S = 2n for Gist), SimpleLSH and RangeLSH when fixing B = 100 and varying h. LSH estimation: For the first strategy, the LSH time complexity is domi￾nated by the hash evaluation, i.e. O (dh), and the linear cost of Hamming distance computation, i.e. O (nh), where h is the code length. In practice, we can use the Eigen library with fast matrix-vec… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    T. D. Ahle, R. Pagh, I. P. Razenshteyn, and F. Silvestri. On the Complexity of Inner Product Similarity Join. In PODS, pages 151–164, 2016

    work page 2016

  2. [2]

    Abuzaid, G

    F. Abuzaid, G. Sethi, P. Bailis, and M. Zaharia. To index or not to index: Optimizing exact maximum inner product search. In ICDE, pages 1250–1261, 2019

    work page 2019

  3. [3]

    Bachrach, Y

    Y. Bachrach, Y. Finkelstein, R. Gilad-Bachrach, L. Katzir, N. Koenigstein, N. Nice, and U. Paquet. Speeding up the Xbox recommender system using a Euclidean transformation for inner-product spaces. In RecSys, pages 257–264, 2014

    work page 2014

  4. [4]

    Ballard, T

    G. Ballard, T. G. Kolda, A. Pinar, and C. Seshadhri. Diamond sampling for approximate maximum all-pairs dot-product (MAD) search. In ICDM, pages 11–20, 2015

    work page 2015

  5. [5]

    Cohen and D

    E. Cohen and D. D. Lewis. Approximating matrix multiplication for pattern recognition tasks. J. Algorithms , 30(2):211–252, 1999

    work page 1999

  6. [6]

    Covington, J

    P. Covington, J. Adams, and E. Sargin. Deep neural networks for Youtube recom- mendations. In RecSys, pages 191–198, 2016

    work page 2016

  7. [7]

    Cremonesi, Y

    P. Cremonesi, Y. Koren, and R. Turrin. Performance of recommender algorithms on top-n recommendation tasks. In RecSys, pages 39–46, 2010

    work page 2010

  8. [8]

    T. L. Dean, M. A. Ruzon, M. Segal, J. Shlens, S. Vijayanarasimhan, and J. Yagnik. Fast, accurate detection of 100,000 object classes on a single machine. In CVPR, pages 1814–1821, 2013

    work page 2013

Show all 31 references
  1. [9]

    Q. Ding, H. Yu, and C. Hsieh. A fast sampling algorithm for maximum inner product search. In AISTATS 2019, pages 3004–3012, 2019. 16 S. Lorenzen and N. Pham

    2019

  2. [10]

    Drineas, R

    P. Drineas, R. Kannan, and M. W. Mahoney. Fast monte carlo algorithms for matrices I: Approximating matrix multiplication. SIAM J. Comput. , 36(1):132–157, 2006

    2006

  3. [11]

    Fetaya, O

    E. Fetaya, O. Shamir, and S. Ullman. Graph approximation and clustering on a budget. In AISTATS, 2015

    2015

  4. [12]

    Har-Peled, P

    S. Har-Peled, P. Indyk, and R. Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of Computing , 8(1):321–350, 2012

    2012

  5. [13]

    Y. Hu, Y. Koren, and C. Volinsky. Collaborative filtering for implicit feedback datasets. In ICDM, pages 263–272, 2008

    2008

  6. [14]

    Huang, G

    Q. Huang, G. Ma, J. Feng, Q. Fang, and A. K. H. Tung. Accurate and fast asymmetric locality-sensitive hashing scheme for maximum inner product search. In KDD, pages 1561–1570, 2018

    2018

  7. [15]

    Koenigstein, G

    N. Koenigstein, G. Dror, and Y. Koren. Yahoo! music recommendations: Modeling music ratings with temporal dynamics and item taxonomy. In RecSys, pages 165–172, 2011

    2011

  8. [16]

    Y. Koren. Collaborative filtering with temporal dynamics. In KDD, pages 447–456, 2009

    2009

  9. [17]

    Koren, R

    Y. Koren, R. M. Bell, and C. Volinsky. Matrix factorization techniques for recom- mender systems. IEEE Computer , 42(8):30–37, 2009

    2009

  10. [18]

    H. Li, T. N. Chan, M. L. Yiu, and N. Mamoulis. FEXIPRO: Fast and exact inner product retrieval in recommender systems. In SIGMOD, pages 835–850, 2017

    2017

  11. [19]

    S. T. Mai, X. He, N. Hubig, C. Plant, and C. B¨ ohm. Active density-based clustering. In ICDM, pages 508–517, 2013

    2013

  12. [20]

    Neyshabur and N

    B. Neyshabur and N. Srebro. On symmetric and asymmetric LSHs for inner product search. In ICML, pages 1926–1934, 2015

    1926

  13. [21]

    P. Ram, D. Lee, and A. G. Gray. Nearest-neighbor search on a time budget via max-margin trees. In SDM, pages 1011–1022, 2012

    2012

  14. [22]

    Rendle, C

    S. Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thieme. BPR: Bayesian personalized ranking from implicit feedback. In UAI, pages 452–461, 2009

    2009

  15. [23]

    Russakovsky, J

    O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpa- thy, A. Khosla, M. S. Bernstein, A. C. Berg, and F. Li. ImageNet large scale visual recognition challenge. IJCV, 115(3):211–252, 2015

    2015

  16. [24]

    Shamir and N

    O. Shamir and N. Tishby. Spectral clustering on a budget. In AISTATS, pages 661–669, 2011

    2011

  17. [25]

    Shrivastava and P

    A. Shrivastava and P. Li. Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). In NIPS, pages 2321–2329, 2014

    2014

  18. [26]

    Spring and A

    R. Spring and A. Shrivastava. Scalable and sustainable deep learning via randomized hashing. In KDD, pages 445–454, 2017

    2017

  19. [27]

    Teflioudi and R

    C. Teflioudi and R. Gemulla. Exact and approximate maximum inner product search with LEMP. TODS, 42(1):5:1–5:49, 2017

    2017

  20. [28]

    Weber, H

    R. Weber, H. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB, pages 194–205, 1998

    1998

  21. [29]

    X. Yan, J. Li, X. Dai, H. Chen, and J. Cheng. Norm-ranging LSH for maximum inner product search. In NeurIPS, pages 2956–2965, 2018

    2018

  22. [30]

    H. Yu, C. Hsieh, Q. Lei, and I. S. Dhillon. A greedy approach for budgeted maximum inner product search. In NIPS, pages 5459–5468, 2017

    2017

  23. [31]

    Zilberstein

    S. Zilberstein. Using anytime algorithms in intelligent systems. AI Magazine , 17(3):73–83, 1996

    1996

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.