Learning query encoders can be exponentially hard even when vector retrieval is geometrically easy
_reachsumit · x · 2026-10-05
A new arXiv paper (2610.02749) studies a new notion of geometric capacity — the maximum recall achievable by a frozen document index. Empirically, single-vector query encoders fall far below what document indices can support on real benchmarks. Theoretically, the authors construct a retrieval task where a perfect query encoder is representable by a small one-hidden-layer ReLU network, yet any statistical-query learner provably needs exponentially many queries to beat the random baseline k/n. The upshot: benchmarks hold substantial unrealized capacity, and learnability of query encoders is fundamentally hard.
More from Research
- Muennighoff presents infinite test-time scaling and prefix sliding work at MIT NLP Seminar — Muennighoff · 2026-10-11
- Symmetric cryptanalysis took 6,677 research-years, 6.4x all lattice work combined — matthew_d_green · 2026-10-11
- 10th grader used free Muse to produce 3 verified math preprints in 8 hours — EastConsequence3792 · 2026-10-11
- ML interatomic potentials reveal fast Li+ conduction mechanism in glassy antiperovskites — TimothyDuignan · 2026-10-11
- Bittensor subnet Metanova uses competition-driven AI drug discovery with robot labs — const_reborn · 2026-10-11
- Lean4 proofs are not a silver bullet: consistency gaps, soundness bugs, and flawed benchmarks — elie · 2026-10-11