Pith. sign in

REVIEW 2 major objections 5 minor 37 references

Any continuous relevance function can be recovered from finite support-item scores alone, turning a heavy ranker into lightweight embeddings for candidate retrieval.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review

2026-07-12 01:56 UTC pith:ORU2U7FG

load-bearing objection Solid, usable extension of Yadav CUR: uniform-approx theorem + better support selection + real production wins with a tiny model. the 2 major comments →

arxiv 2607.03515 v1 pith:ORU2U7FG submitted 2026-07-03 cs.IR cs.LG

Relevance-Based Embeddings: Lightweight Candidate Retrieval via Heavy-Ranker Calls

Kirill Shevkunov , Andrey Ploskonosov , Liudmila Prokhorenkova This is my paper
classification cs.IR cs.LG
keywords candidate retrievalrelevance-based embeddingscross-encoder approximationsupport itemsdual encodersapproximate nearest neighborCUR decompositioninformation retrieval
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

When you must find the best items for a query under an expensive relevance model, exhaustive search is impossible and ordinary dual-encoder embeddings lose pairwise features. This paper shows you can instead describe every query by its scores against a small fixed set of support items, and every item by its scores against a small set of support queries. Those relevance vectors become the inputs to two light neural nets whose inner product approximates the original heavy ranker arbitrarily closely. The authors prove the approximation is uniform for any continuous relevance on compact spaces, and they show that carefully chosen support sets (especially a greedy L2 method or cluster centers) beat random selection. On entity-linking, question-answering and production recommendation data the resulting lightweight embeddings match or exceed strong dual encoders while using far fewer trainable parameters and no hand-engineered features.

Core claim

Under mild topological conditions any continuous relevance function R can be uniformly approximated to arbitrary precision by the inner product of two neural networks that see only the relevance vectors of a finite support set of items and of queries. Consequently a heavy black-box ranker can be turned into high-quality, ANN-searchable embeddings without ever training a separate dual encoder from scratch.

What carries the argument

Relevance-based embeddings (RBE): the maps e_I(i)=f_I(R(i,S_Q)) and e_Q(q)=f_Q(R(S_I,q)) whose inner product approximates R; the uniform-approximation theorem (Theorem 3.2) that guarantees such maps exist via the Stone–Weierstrass algebra generated by the elementary relevance functions.

Load-bearing premise

The relevance function must be continuous and the spaces of queries and items must be compact; if either fails the uniform-approximation guarantee no longer holds.

What would settle it

On a compact continuous relevance task, measure whether HitRate of RBE with a few hundred support items approaches the HitRate of exhaustive heavy-ranker search as the support size grows; if the gap stays large the claimed approximation power is false.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Any existing black-box ranker can be converted into an ANN index without training a second heavy dual-encoder model.
  • Pairwise features that dual encoders cannot use become automatically available through the relevance vectors.
  • Support-set choice (cluster centers or L2-greedy) becomes a first-class design lever that measurably improves retrieval quality.
  • Model size collapses from hundreds of millions of parameters to tens of thousands while still matching production dual-encoder quality on recommendation tasks.
  • New items can be embedded on the fly by scoring them against the fixed support queries, without re-training.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same support-relevance construction could serve as a drop-in feature layer for any downstream model that currently relies on dual-encoder embeddings (e.g., category prediction or diversity re-ranking).
  • Because the heavy ranker is treated as a black box, the method is immediately portable to any domain where a strong pairwise scorer already exists but a fast first-stage index does not.
  • If support items are chosen once offline, the online cost is only a few dozen heavy-ranker calls per query—comparable to the re-ranking budget already paid by dual-encoder pipelines.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper proposes relevance-based embeddings (RBE) for candidate retrieval: each query (item) is represented by its scores under a heavy ranker R against a fixed support set of items (queries); lightweight maps f_I and f_Q then turn those vectors into embeddings whose inner product approximates R. Theorem 3.1 shows that a regularized CUR factorization of the relevance matrix converges in L2 under mild integrability; Theorem 3.2 shows that, for continuous R on compact spaces, neural maps of the relevance vectors can uniformly approximate R to arbitrary precision (Stone-Weierstrass + universal approximation). Support-set selection is studied (random, popular, clustering, diversity, and an l2-greedy CUR-MSE procedure). Experiments on five ZESHEL domains, MS MARCO, and two production recommenders (RecGames, RecMusic) show that RBE with non-random supports and trainable maps improves HitRate over AnnCUR and, under fair heavy-ranker budgets, over production dual encoders and AXN.

Significance. If the claims hold, the work supplies a theoretically grounded, lightweight alternative to dual-encoder candidate selection that can exploit pairwise features unavailable to pure two-tower models, while requiring far fewer trainable parameters (~50K vs hundreds of millions). The uniform-approximation guarantee (Theorem 3.2) and the L2 guarantee for regularized CUR (Theorem 3.1) are clean existence results under standard hypotheses; the empirical gains on both academic and production data, with explicit accounting for the m support calls in the re-ranking budget, make the method immediately usable. Code and data release further strengthen reproducibility. The contribution is therefore both conceptual (relevance vectors as universal features) and practical (better candidate quality at lower model size).

major comments (2)
  1. Section 5 / Tables 4–5: the production comparison is the strongest practical claim, yet only point estimates are reported for DE, AXN_DE and RBE. Appendix E.4 supplies means and standard deviations solely for random AnnCUR. Without analogous variability (or at least multiple random seeds / support-set draws) for the production HitRate curves, it is hard to judge whether the reported crossovers (X=200 on RecGames1, X=100 on RecMusic) are stable. Adding error bars or a short multi-seed table would make the claim load-bearing rather than suggestive.
  2. Section 3.4 and Appendix B: the l2-greedy procedure optimizes the CUR MSE on train queries (Eq. 3), which is not the final HitRate metric. While Table 1 shows it is the best among the tested heuristics, the paper never verifies that the selected supports remain near-optimal once the trainable maps f_I, f_Q are fitted (Table 2). A short ablation that re-optimizes or re-ranks supports under the final listwise loss would confirm that the theoretically motivated selection still drives the neural RBE gains.
minor comments (5)
  1. Notation: R(i,SQ) and R(SI,q) are introduced cleanly, but the matrix R(SI,SQ) is sometimes written without parentheses; a single consistent notation would help.
  2. Figure 1 caption is terse; a one-sentence description of the color coding (support vs test) would make the visualization self-contained.
  3. Appendix A.2 (sphere reduction) is interesting but unused in the experiments; either cite it in the main text when discussing ANN indexes or move it to a remark.
  4. Table 3 reports approximate parameter counts; giving exact figures (or a short breakdown of the MLP widths) would make the “lightweight” claim sharper.
  5. A few typos: “proceesing” (p. 3), “the the” (Appendix A.1), and inconsistent capitalization of HitRate vs HR.

Circularity Check

0 steps flagged

No significant circularity: existence theorems are independent density arguments; empirical claims use held-out evaluation.

full rationale

The load-bearing theoretical claim (Theorem 3.2) is an existence result proved from first principles via the Stone-Weierstrass theorem applied to the algebra generated by the elementary relevance functions ri and rq, followed by the universal approximation property of MLPs (Appendix A.1). The construction does not fit any parameter to the target quantity being approximated, nor does it redefine the target in terms of the approximant. Theorem 3.1 likewise supplies an L2 guarantee for regularized CUR under an integrability assumption, again without circular reduction. Support-item selection (including l2-greedy) optimizes a CUR MSE surrogate on training queries only; the final reported metric is HitRate on held-out queries after training the neural maps fI, fQ. The single self-citation (Shevkunov & Prokhorenkova 2021) is used only for a parenthetical remark on the limitations of the inner product and is not invoked in any proof or experimental claim. Comparisons against AnnCUR, dual encoders and AXN are external and use independent re-ranking budgets. Consequently the derivation chain contains no self-definitional step, no fitted-input-as-prediction, and no load-bearing self-citation.

Axiom & Free-Parameter Ledger

3 free parameters · 3 axioms · 0 invented entities

The central claim rests on standard functional-analysis facts (Stone-Weierstrass, universal approximation of MLPs) plus the modeling assumption that the expensive ranker is continuous on compact spaces. Support-set size and embedding dimension are free design choices; no new physical or mathematical entities are postulated.

free parameters (3)
  • support-set size |SI|=|SQ|=100
    Fixed by hand for all experiments; larger sets improve approximation but raise heavy-ranker cost.
  • embedding dimension and MLP widths
    Chosen so that total trainable parameters stay ~50 k; not derived from theory.
  • regularization lambda for CUR_lambda
    Appears in the L2 theorem; set small enough for the approximation claim.
axioms (3)
  • domain assumption Query and item spaces are compact topological spaces and R is continuous (or R^4 integrable for the L2 result).
    Stated at the opening of Theorems 3.1 and 3.2; required for uniform and L2 approximation.
  • standard math MLPs with non-polynomial activations are universal approximators on compact sets.
    Invoked via Cybenko/Leshno citations in the proof of Theorem 3.2.
  • standard math Stone-Weierstrass theorem: the algebra generated by elementary relevance functions is dense in C(IR x QR).
    Core step of the proof in Appendix A.1.

reviewed 2026-07-12 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Relevance-Based Embeddings: Lightweight Candidate Retrieval via Heavy-Ranker Calls." pith.science (2026). https://pith.science/paper/ORU2U7FG

@misc{pith2026260703515,
  author       = {Pith},
  title        = {Pith review of: Relevance-Based Embeddings: Lightweight Candidate Retrieval via Heavy-Ranker Calls},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ORU2U7FG}},
  note         = {Machine review of arXiv:2607.03515}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

In many machine learning applications, the most relevant items for a query should be efficiently retrieved. The relevance function is usually an expensive similarity model, making the exhaustive search infeasible. A typical solution is to train another model that separately embeds queries and items to a vector space, where similarity is defined via the dot product or cosine similarity. This allows one to search the relevant items through fast approximate nearest neighbor search at the cost of some reduction in quality. To compensate for this reduction, the found items (candidates) are re-ranked by the expensive ranking model. In this paper, we investigate an alternative approach to candidate selection that utilizes the scores of the expensive model to improve the representations of queries and items. The idea is to describe each query (item) by its relevance to a set of support items (queries) and use these new representations to obtain query (item) embeddings. We theoretically prove that such embeddings are powerful enough to approximate any complex similarity model (under mild conditions). We also investigate the choice of support items, which is a crucial ingredient of the proposed approach. The experiments on diverse academic and production datasets illustrate the power of our method.

Figures

Figures reproduced from arXiv: 2607.03515 by Andrey Ploskonosov, Kirill Shevkunov, Liudmila Prokhorenkova.

Figure 1
Figure 1. Figure 1: RBE visualization: support queries are red, support items are yellow; test queries are blue, and their relevance scores for the support items are used to approximate the remaining values. 3.3. Relevance-Based Embeddings In this section, we propose extending the CUR-based ap￾proximation by allowing transformations of relevance vec￾tors, e.g., with a neural architecture. With such embeddings, we prove a stro… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 3 linked inside Pith

  1. [1]

    and Indyk, P

    Andoni, A. and Indyk, P. Near-optimal hashing algorithms for near neighbor problem in high dimension. Communications of the ACM, 51 0 (1): 0 117--122, 2008

    2008

  2. [2]

    ANN-Benchmarks : A benchmarking tool for approximate nearest neighbor algorithms

    Aum \"u ller, M., Bernhardsson, E., and Faithfull, A. ANN-Benchmarks : A benchmarking tool for approximate nearest neighbor algorithms. Information Systems, 87: 0 101374, 2020

    2020

  3. [3]

    MS MARCO : A human generated machine reading comprehension dataset

    Bajaj, P., Campos, D., Craswell, N., Deng, L., Gao, J., Liu, X., Majumder, R., McNamara, A., Mitra, B., Nguyen, T., Rosenberg, M., Song, X., Stoica, A., Tiwary, S., and Wang, T. MS MARCO : A human generated machine reading comprehension dataset. arXiv preprint arXiv:1611.09268, 2016

    Pith/arXiv arXiv 2016

  4. [4]

    Bentley, J. L. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18 0 (9): 0 509--517, 1975

    1975

  5. [5]

    Approximate nearest neighbor search under neural similarity metric for large-scale recommendation

    Chen, R., Liu, B., Zhu, H., Wang, Y., Li, Q., Ma, B., Hua, Q., Jiang, J., Xu, Y., Deng, H., and Zheng, B. Approximate nearest neighbor search under neural similarity metric for large-scale recommendation. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management, pp.\ 3013--3022, 2022

    2022

  6. [6]

    Deep neural networks for YouTube recommendations

    Covington, P., Adams, J., and Sargin, E. Deep neural networks for YouTube recommendations. In Proceedings of the 10th ACM Conference on Recommender Systems, pp.\ 191--198, 2016

    2016

  7. [7]

    Approximation by superpositions of a sigmoidal function

    Cybenko, G. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2 0 (4): 0 303--314, 1989

    1989

  8. [8]

    and Freund, Y

    Dasgupta, S. and Freund, Y. Random projection trees and low dimensional manifolds. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp.\ 537--546, 2008

    2008

  9. [9]

    and Sinha, K

    Dasgupta, S. and Sinha, K. Randomized partition trees for exact nearest neighbor search. In Proceedings of the 26th Annual Conference on Learning Theory, volume 30, pp.\ 317--337, 2013

    2013

  10. [10]

    Deep image retrieval: Learning global representations for image search

    Gordo, A., Almaz \'a n, J., Revaud, J., and Larlus, D. Deep image retrieval: Learning global representations for image search. In European Conference on Computer Vision, pp.\ 241--257. Springer, 2016

    2016

  11. [11]

    a tter, S., Althammer, S., Schr \

    Hofst \"a tter, S., Althammer, S., Schr \"o der, M., Sertkan, M., and Hanbury, A. Improving efficient neural ranking models with cross-architecture knowledge distillation. arXiv preprint arXiv:2010.02666, 2020

    Pith/arXiv arXiv 2010

  12. [12]

    Learning deep structured semantic models for web search using clickthrough data

    Huang, P.-S., He, X., Gao, J., Deng, L., Acero, A., and Heck, L. Learning deep structured semantic models for web search using clickthrough data. In Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, pp.\ 2333--2338, 2013

    2013

  13. [13]

    Poly-encoders: Architectures and pre-training strategies for fast and accurate multi-sentence scoring

    Humeau, S., Shuster, K., Lachaux, M.-A., and Weston, J. Poly-encoders: Architectures and pre-training strategies for fast and accurate multi-sentence scoring. In International Conference on Learning Representations, 2020

    2020

  14. [14]

    and Motwani, R

    Indyk, P. and Motwani, R. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pp.\ 604--613, 1998

    1998

  15. [15]

    Dense passage retrieval for open-domain question answering

    Karpukhin, V., O g uz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W.-t. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pp.\ 6769--6781, 2020

    2020

  16. [16]

    Kowalski, G. J. Information retrieval systems: theory and implementation. Springer, 2007

    2007

  17. [17]

    Y., Pinkus, A., and Schocken, S

    Leshno, M., Lin, V. Y., Pinkus, A., and Schocken, S. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Networks, 6 0 (6): 0 861--867, 1993

    1993

  18. [18]

    Trans-Encoder : unsupervised sentence-pair modelling through self- and mutual-distillations

    Liu, F., Jiao, Y., Massiah, J., Yilmaz, E., and Havrylov, S. Trans-Encoder : unsupervised sentence-pair modelling through self- and mutual-distillations. In International Conference on Learning Representations, 2022

    2022

  19. [19]

    Zero-shot entity linking by reading entity descriptions

    Logeswaran, L., Chang, M.-W., Lee, K., Toutanova, K., Devlin, J., and Lee, H. Zero-shot entity linking by reading entity descriptions. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp.\ 3449--3460, 2019

    2019

  20. [20]

    TwinBERT : Distilling knowledge to twin-structured compressed BERT models for large-scale retrieval

    Lu, W., Jiao, J., and Zhang, R. TwinBERT : Distilling knowledge to twin-structured compressed BERT models for large-scale retrieval. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp.\ 2645--2652, 2020

    2020

  21. [21]

    Sparse, dense, and attentional representations for text retrieval

    Luan, Y., Eisenstein, J., Toutanova, K., and Collins, M. Sparse, dense, and attentional representations for text retrieval. Transactions of the Association for Computational Linguistics, 9: 0 329--345, 2021

    2021

  22. [22]

    Mahoney, M. W. and Drineas, P. CUR matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106 0 (3): 0 697--702, 2009

    2009

  23. [23]

    Malkov, Y. A. and Yashunin, D. A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42 0 (4): 0 824--836, 2020

    2020

  24. [24]

    and Babenko, A

    Morozov, S. and Babenko, A. Relevance proximity graphs for fast relevance retrieval. arXiv preprint arXiv:1908.06887, 2019

    Pith/arXiv arXiv 1908

  25. [25]

    Searching in metric spaces by spatial approximation

    Navarro, G. Searching in metric spaces by spatial approximation. The VLDB Journal, 11: 0 28--46, 2002

    2002

  26. [26]

    Scikit-learn: Machine learning in P ython

    Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., and Duchesnay, E. Scikit-learn: Machine learning in P ython. Journal of Machine Learning Research, 12: 0 2825--2830, 2011

    2011

  27. [27]

    V., and Gulin, A

    Prokhorenkova, L., Gusev, G., Vorobev, A., Dorogush, A. V., and Gulin, A. CatBoost : unbiased boosting with categorical features. Advances in Neural Information Processing Systems, 31, 2018

    2018

  28. [28]

    X., Dong, D., Wu, H., and Wang, H

    Qu, Y., Ding, Y., Liu, J., Liu, K., Ren, R., Zhao, W. X., Dong, D., Wu, H., and Wang, H. RocketQA : An optimized training approach to dense passage retrieval for open-domain question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp.\ 5835--5847, 2021

    2021

  29. [29]

    and Gurevych, I

    Reimers, N. and Gurevych, I. Sentence-BERT : Sentence embeddings using siamese BERT -networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp.\ 3982--3992, 2019

    2019

  30. [30]

    and Prokhorenkova, L

    Shevkunov, K. and Prokhorenkova, L. Overlapping spaces for compact graph representations. Advances in Neural Information Processing Systems, 34: 0 11665--11677, 2021

    2021

  31. [31]

    Scalable zero-shot entity linking with dense entity retrieval

    Wu, L., Petroni, F., Josifoski, M., Riedel, S., and Zettlemoyer, L. Scalable zero-shot entity linking with dense entity retrieval. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pp.\ 6397--6407, 2020

    2020

  32. [32]

    A bi-metric framework for efficient nearest neighbor search

    Xu, H., Indyk, P., and Silwal, S. A bi-metric framework for efficient nearest neighbor search. In The 1st Workshop on Vector Databases, 2025

    2025

  33. [33]

    Efficient nearest neighbor search for cross-encoder models using matrix factorization

    Yadav, N., Monath, N., Angell, R., Zaheer, M., and McCallum, A. Efficient nearest neighbor search for cross-encoder models using matrix factorization. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp.\ 2171--2194, 2022

    2022

  34. [34]

    Efficient k-NN search with cross-encoders using adaptive multi-round CUR decomposition

    Yadav, N., Monath, N., Zaheer, M., and McCallum, A. Efficient k-NN search with cross-encoders using adaptive multi-round CUR decomposition. In Findings of the Association for Computational Linguistics: EMNLP 2023, pp.\ 8088--8103, 2023

    2023

  35. [35]

    Adaptive retrieval and scalable indexing for k-NN search with cross-encoders

    Yadav, N., Monath, N., Zaheer, M., Fergus, R., and McCallum, A. Adaptive retrieval and scalable indexing for k-NN search with cross-encoders. In International Conference on Learning Representations, 2024

    2024

  36. [36]

    Modelling domain relationships for transfer learning on retrieval-based question answering systems in e-commerce

    Yu, J., Qiu, M., Jiang, J., Huang, J., Song, S., Chu, W., and Chen, H. Modelling domain relationships for transfer learning on retrieval-based question answering systems in e-commerce. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp.\ 682--690, 2018

    2018

  37. [37]

    and Stratos, K

    Zhang, W. and Stratos, K. Understanding hard negatives in noise contrastive estimation. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp.\ 1090--1101, 2021

    2021

This paper was first reviewed by grok-4.5 on July 12, 2026.