PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Theoretical Limitations of Embedding-Based Retrieval

Orion Weller, Michael Boratko, Iftekhar Naim, Jinhyuk Lee

arXiv:2508.21038v2cs.IRcs.CLcs.LG

TL;DR

The paper asks whether single-vector embeddings face fundamental retrieval limits even for simple realistic queries, proves dimension-based constraints, and shows state-of-the-art models fail on the resulting LIMIT dataset.

  • Problem

    It is unclear whether embedding limitations arise only from unrealistic queries or can persist for simple realistic retrieval tasks.

  • Method

    The paper connects learning theory and high-dimensional geometry to derive embedding-dimension lower bounds, then tests them with free embeddings and the LIMIT dataset.

  • Results

    Fixed-dimensional embeddings cannot represent some top-k document combinations, and even state-of-the-art models cannot solve the simple realistic LIMIT dataset.

  • Takeaways & Limitations

    As retrieval requires representing more top-k combinations, single-vector embeddings reach a fundamental representational limit.

  • Takeaways & Limitations

    The theoretical results concern single-vector models and do not necessarily extend to multi-vector architectures or settings allowing some mistakes.

Abstract

from arXiv · show

Vector embeddings have been tasked with an ever-increasing set of retrieval tasks over the years, with a nascent rise in using them for reasoning, instruction-following, coding, and more. These new benchmarks push embeddings to work for any query and any notion of relevance that could be given. While prior works have pointed out theoretical limitations of vector embeddings, there is a common assumption that these difficulties are exclusively due to unrealistic queries, and those that are not can be overcome with better training data and larger models. In this work, we demonstrate that we may encounter these theoretical limitations in realistic settings with extremely simple queries. We connect known results in learning theory, showing that the number of top-k subsets of documents capable of being returned as the result of some query is limited by the dimension of the embedding. We empirically show that this holds true even if we directly optimize on the test set with free parameterized embeddings. Using free embeddings, we then demonstrate that returning all pairs of documents requires a relatively high dimension. We then create a realistic dataset called LIMIT that stress tests embedding models based on these theoretical results, and observe that even state-of-the-art models fail on this dataset despite the simple nature of the task. Our work shows the limits of embedding models under the existing single vector paradigm and calls for future research to develop new techniques that can resolve this fundamental limitation.

1 INTRODUCTION

This work identifies fundamental limits of single-vector retrieval, showing that embedding dimension bounds which top-k document combinations can be returned, even for simple realistic queries. Free-embedding experiments and the LIMIT dataset demonstrate that these limits persist in best-case optimization and challenge state-of-the-art models.

  • Motivation: Instruction-following retrieval increasingly asks embeddings to represent arbitrary relevance definitions for arbitrary queries, expanding the combinations that retrieval systems must support.The introduction contrasts this trend with earlier dense retrieval systems that represent each input as a single vector.
  • Theoretical motivation: Embedding dimension imposes a fundamental limit: for any dimension d, some top-k document combinations cannot be returned by any query.The analysis connects high-dimensional geometry with neural retrieval to derive a lower bound on the dimension required to represent relevant-document and query combinations.
  • Best-case empirical analysis: Directly optimizing embeddings on test data confirms a critical point where the number of documents exceeds the dimension’s capacity to encode all combinations.This free-embedding setup tests the theoretical limit without attributing failure to a particular training dataset or model architecture.
  • LIMIT dataset: Even state-of-the-art embedding models struggle on LIMIT, a realistic natural-language dataset built from these limitations despite its simple retrieval questions.Models with small embedding dimensions are practically unable to solve LIMIT using standard optimization techniques.
  • Implications: These limitations can remain hidden by narrow or overfit benchmarks, motivating broader evaluations and alternatives such as cross-encoders, multi-vector models, and richer similarity functions.The recommendation targets systems expected to handle the full range of instruction queries and relevance definitions.

2 RELATED WORK

Embedding retrieval has expanded from text-only web search to instruction-following, multimodal, domain-diverse, and reasoning-focused tasks. Prior work studied empirical embedding limitations and geometric nearest-neighbor structure, while this work connects embedding dimension to realizable top-k sets and extends the analysis across single-vector modalities.

  • Embedding models have progressed from simple text-only web search to instruction-following and multimodal representations, following advances in pretrained and multimodal language models.
  • Although the analysis focuses on textual representations, its claims apply to single-vector embeddings across modalities and domains as representational demands grow through instructions or multimodality.
  • Retrieval models now cover diverse domains, instructions, and reasoning over queries, shifting embedding models beyond basic keyword matching.
  • Prior studies documented empirical limitations involving false positives, cross-lingual settings, and embedding-dimension bias-variance tradeoffs, whereas this work theoretically links dimension to realizable top-k sets.
  • Geometric retrieval research includes order-k Voronoi diagrams, while this work instead asks what dimension is required to realize all k-subsets with a guaranteed score margin.

3 REPRESENTATIONAL CAPACITY OF VECTOR EMBEDDINGS

The section establishes a sphere-packing lower bound on the embedding dimension required to realize every k-subset with margin γ. Even moderate margins yield requirements exceeding practical embedding dimensions, which become still more demanding under real-world learning and modeling constraints.

  • Setup and theorem: Theorem 1 lower-bounds the dimension needed for unit document and query vectors to realize every k-subset with margin γ, where feasibility requires 0 < γ ≤ 1.The bound is derived under the assumption that every k-subset is realizable with the specified margin.
  • Proof: The proof maps distinct k-subsets to pairwise 2γ-separated query vectors and uses disjoint-ball volume packing in d dimensions to obtain the lower bound.For distinct subsets S and T, the score-gap constraints imply ||u_S − u_T|| ≥ 2γ; packing balls of radius γ inside a ball of radius 1 + γ yields the dimension constraint.
  • Numerical instantiation: For γ = 0.1, the resulting lower bounds can already exceed dimensions used in web-scale search for large n and k.Table 1 provides the numerical instantiation, although the supplied passage does not expose its individual cell values.
  • Numerical instantiation: Larger γ demands higher dimension because log(1 + 1/γ) decreases with γ, while feasibility still requires γ ≤ 1.A stricter score-gap requirement therefore strengthens the dimensional burden.
  • Consequences: Practical requirements are more severe because search embeddings are usually below 1k dimensions, the largest research embeddings are around 4096, and learning, generalization, tokenization, and quantization add constraints.The section characterizes its geometric result as an extreme lower bound and notes that even a small multiplicative increase can make the requirement infeasible.

4 EMPIRICAL CONNECTION: BEST CASE OPTIMIZATION

This section tests the theoretical dimension limitation under the strongest possible optimization setting, where document and query embeddings are directly optimized without natural-language constraints. Experiments increase the number of documents until low-dimensional embeddings fail to represent all top-2 combinations, with the resulting critical values modeled by a polynomial trend.

  • Method: Free embedding optimization directly updates document and query vectors with gradient descent, testing whether the task is feasible even without natural-language constraints.If free embeddings cannot solve the problem, realistic retrieval models cannot solve it either.
  • Experimental Settings: The experiments use random unit-vector document and query matrices, full-batch InfoNCE training, all other documents as in-batch negatives, and projected gradient descent for normalization.Adam performs the updates, and early stopping is used when improvement stops.
  • Experimental Settings: The study uses k = 2 and increases n for each embedding dimension d until optimization breaks, then fits a polynomial regression line to extrapolate the trend.Larger n, k, and d are avoided because the number of top-k combinations grows combinatorially.
  • Results: Figure 2 reports the critical n at which dimensionality becomes too small to represent all top-2 combinations and shows its polynomial trend line.The plotted critical-n values are the empirical test of the theoretical limitation.

5 EMPIRICAL CONNECTION: REAL-WORLD DATASETS

The LIMIT dataset uses simple queries to expose the difficulty of representing all top-k document combinations, and state-of-the-art embedding models struggle despite the task’s simplicity. Performance improves with dimensionality and alternative architectures, but no current approach clearly resolves the limitation.

  • Dataset Construction: LIMIT targets combinations of top-k sets directly, using simple queries and documents rather than difficult query operators that introduce unrelated challenges.The dataset uses 50k documents, 1000 queries, and two relevant documents per query; its 46-document subset covers just over 1000 top-2 combinations.
  • Results: Models severely struggle on LIMIT: full-setting systems remain below 20% recall@100, while the 46-document version is unsolved even at recall@20.The result holds despite trivially simple queries and documents.
  • Results: Performance depends crucially on embedding dimensionality, with larger dimensions improving results; instruction-diverse Promptriever also performs better than models trained on narrower tasks.The authors suggest broader instruction training may enable models to use more of their embedding space.
  • Alternative Architectures: GTE-ModernColBERT substantially outperforms single-vector models but remains far from solving LIMIT, whereas BM25 approaches near-perfect scores.Multi-vector and sparse architectures trade off expressivity and applicability, while rerankers solve LIMIT more easily because they lack the same embedding-dimension limitation.
  • Implications: The results indicate that single-vector models are fundamentally limited by embedding dimension, and sufficiently many top-k combinations would require infeasibly large dimensions for non-toy datasets.The 46-document LIMIT instance can be embedded in 12 dimensions with free embeddings, yet existing models still perform poorly, indicating additional architectural weaknesses.

6 CONCLUSION

The paper introduces LIMIT to expose a fundamental limitation of embedding models, linking a fixed embedding dimension to unattainable top-k document sets. It shows this limitation theoretically and empirically, including under best-case vector optimization, and connects it to realistic simple tasks for state-of-the-art models.

  • 6 CONCLUSION: LIMIT highlights a fundamental embedding-model limitation by showing that fixed-dimensional embeddings cannot realize some possible top-k document sets.The paper establishes this connection theoretically and tests it empirically through best-case optimization of the vectors themselves.
  • 6 CONCLUSION: The work connects these theoretical limits to practical retrieval by constructing realistic, simple task instances that challenge existing state-of-the-art embedding models.

LIMITATIONS · A RELATIONSHIP TO ORDER-K VORONOI REGIONS

The theoretical connection identifies combinations that embedding models cannot represent, while relating retrieval’s top-k outputs to order-k Voronoi regions. These limitations are established for single-vector models, but their exact failure cases and applicability to other architectures remain unresolved.

  • LIMITATIONS: The theoretical results do not necessarily extend from single-vector models to multi-vector architectures.Initial empirical results for non-single-vector models are provided, but extending the theoretical connections remains future work.
  • LIMITATIONS: The analysis also leaves open settings where users permit some mistakes, such as retrieving only a majority of combinations.The supplied discussion identifies this approximate-retrieval setting as lacking theoretical results.
  • LIMITATIONS: Some combinations cannot be represented by embedding models, although the theory cannot determine in advance which combinations will fail.Consequently, some instruction-following or reasoning tasks may be solved perfectly, while other tasks are provably unsolvable.
  • A RELATIONSHIP TO ORDER-K VORONOI REGIONS: An order-k Voronoi graph consists of points whose k nearest neighbors are a particular set of n points in S.This definition provides the geometric object used to compare the paper’s results with Clarkson (1988).
  • A RELATIONSHIP TO ORDER-K VORONOI REGIONS: Each order-k Voronoi region corresponds to one retrieved top-k result set.The mapping connects geometric nearest-neighbor regions directly to retrieval outputs.
  • A RELATIONSHIP TO ORDER-K VORONOI REGIONS: The number of unique Voronoi regions equals the number of combinations that could be returned for retrieval.This comparison explains how Clarkson’s (1988) bounds on order-k Voronoi regions relate to the paper’s retrieval analysis.

B HYPERPARAMETER AND COMPUTE DETAILS

The experiments use standard MTEB inference settings, SentenceTransformers training with MultipleNegativesRankingLoss, and GPU/TPU compute suited to full-dataset batch optimization.

  • Inference: Inference uses default MTEB length settings, which are suitable because the dataset documents contain around 100 tokens.
  • Training: Training uses SentenceTransformers with MultipleNegativesRankingLoss, full-dataset batches, duplicate-free in-batch negatives, a 5e-5 learning rate, and 5 epochs.The LIMIT training set is reduced from 2.5k to 2k examples to match the test set.
  • Compute: LIMIT inference and training run on A100 GPUs, while free-embedding experiments mainly use H100 GPUs and TPU v5s for larger N and higher-VRAM optimization.

C SIGMOID LOSS FUNCTION FOR FREE EMBEDDINGS

The authors note that sigmoid-loss free-embedding experiments can be solved in fewer dimensions than their setting without a margin, while their best results used InfoNCE to maximize the margin. This difference highlights unresolved questions about learnability.

  • Comparison with sigmoid loss: Sigmoid-loss free-embedding experiments for vision-language models such as CLIP can be solved in fewer dimensions than the authors’ setting when no margin is assumed.This comparison is attributed to concurrent work by Bangachev et al. (2025).
  • Implications for learnability: The authors’ strongest performance with InfoNCE, which seeks the widest possible margin, indicates that loss-induced margins may affect learnability.They identify additional questions about why these settings differ and call for further insight.

D PROOF USING SIGN-RANK · D.1 FORMALIZATION · D.2 THEORETICAL BOUNDS

The paper formalizes retrieval capacity as the minimum rank of a score matrix that preserves query-wise relevance ordering, then connects this quantity to thresholdability and sign rank. For binary relevance matrices, row-wise ordering and thresholding coincide, while sign rank yields a weaker dimension requirement because it assumes no margin.

  • D PROOF USING SIGN-RANK: The sign-rank proof provides a weaker dimension requirement because it assumes no margin, although the sign rank of the transformed relevance matrix depends only on k.The proof connects retrieval representations to classic sign rank but does not impose a positive separation margin.
  • D.1 FORMALIZATION: Embedding retrieval is modeled with query vectors u_i and document vectors v_j, scoring each pair by u_i^T v_j so relevant documents should outrank irrelevant ones.The ground-truth relevance matrix A records whether each document is relevant to each query.
  • D.1 FORMALIZATION: Concatenating query and document vectors gives a score matrix B = U^T V, making the smallest feasible embedding dimension equal to the minimum rank of a score matrix that preserves every row’s relevance ordering.This motivates the row-wise order-preserving rank as the relevant capacity measure for vector embeddings.
  • D.1 FORMALIZATION: The row-wise thresholdable rank uses separate thresholds τ_i for each query, whereas globally thresholdable rank requires one threshold τ across all queries.Both definitions require relevant scores above the threshold and irrelevant scores below it.
  • D.2 THEORETICAL BOUNDS: For binary relevance matrix A, rankrop A equals rankrt A, so ordering relevant documents above irrelevant ones is equivalent to separating them with query-specific thresholds.The equivalence follows because binary ordering places every relevant score above every irrelevant score, allowing a separating threshold in each row.
  • D.2 THEORETICAL BOUNDS: Sign rank is defined as the least rank of a real matrix whose entry signs match a ±1 matrix, and the binary relevance matrix is converted to this form as 2A − 1_m×n.A zero threshold separates positive-sign entries corresponding to relevant documents from negative-sign entries corresponding to irrelevant documents.
  • D.2 THEORETICAL BOUNDS: The threshold and sign-rank quantities differ by at most one rank: rankgt A ≤ rank±(2A − 1_m×n) ≤ rankrt A + 1.The first inequality follows from global thresholding at zero, while the second follows by subtracting the row-threshold vector as a rank-one correction.

D.3 CONSEQUENCES · D.4 CORRELATION WITH MTEB

The consequences section bounds the embedding dimension needed to exactly represent binary retrieval objectives and describes a sign-rank construction that is impractical in general. Compared with BEIR, LIMIT performance is generally uncorrelated, although smaller models perform worse on both.

  • D.3 CONSEQUENCES: Exact retrieval objectives can be characterized by lower and upper bounds on embedding dimension under row-wise ordering, row-wise thresholding, or global thresholding.
  • D.3 CONSEQUENCES: At least rank±(2A −1_m×n) −1 dimensions are required to exactly capture a binary relevance matrix A.
  • D.3 CONSEQUENCES: At most rank±(2A −1_m×n) dimensions always suffice to exactly capture the same binary relevance relationships.
  • D.3 CONSEQUENCES: The cyclotomic polynomial construction of Alon et al. (1985) implies that any qrel matrix has sign-rank at most 2k, where k is the largest per-query document count.
  • D.3 CONSEQUENCES: The construction can be adapted to normalized vectors with one additional dimension, but generally requires infinite precision and is therefore impractical.
  • D.4 CORRELATION WITH MTEB: In Figure 7, LIMIT performance is generally not correlated with BEIR performance, while smaller models such as Arctic Embed perform worse on both, likely because of embedding dimension and pretrained knowledge.

F METRICS MEASURING QREL GRAPH DENSITY · G TABLE FORMS OF FIGURES

The paper introduces graph-based metrics showing that LIMIT’s qrel structure is substantially denser and queries more strongly connected than those of standard IR datasets. It also provides tabular counterparts for several figures, including results on LIMIT, its small version, fine-tuning, and free-embedding experiments.

  • F METRICS MEASURING QREL GRAPH DENSITY: The two metrics treat the qrel matrix as a graph and distinguish LIMIT from standard IR datasets.The paper presents Graph Density and Average Query Strength as complementary measurements of qrel structure.
  • F METRICS MEASURING QREL GRAPH DENSITY: The qrel matrix becomes a document graph in which documents connect when they are relevant to a common query.Graph density is the edge count divided by the maximum possible number of undirected edges; density 1 is complete and near 0 is sparse.
  • F METRICS MEASURING QREL GRAPH DENSITY: Average Query Strength measures how strongly queries connect through shared relevant documents by averaging each query node’s incident edge-weight sum.Query similarity may use Jaccard similarity of relevant documents.
  • F METRICS MEASURING QREL GRAPH DENSITY: LIMIT has substantially higher qrel graph-density metrics than standard IR datasets, including query similarity of 28 versus 0.6 or lower elsewhere.Comparisons use test sets from NQ, HotpotQA, SciFact, and FollowIR Core17; instruction-following datasets are the closest alternatives.
  • F METRICS MEASURING QREL GRAPH DENSITY: The authors’ ablations suggest, but do not definitively prove, that datasets with higher metric values are harder for retrieval models to represent.This interpretation is stated as an empirical implication of the dataset comparisons.
  • G TABLE FORMS OF FIGURES: Section G maps Figure 3 to Table 5, Figure 4 to Table 4, Figure 2 to Table 6, and Figure 5 to Table 3.These tables provide tabular forms of the corresponding figures.
  • G TABLE FORMS OF FIGURES: The tabular materials cover fine-tuning, LIMIT, LIMIT small, and critical n values across embedding dimensions; Table 7 additionally reports BEIR versus LIMIT results.Table 7 is identified as comparable to Figure 7.
Loading 2508.21038v2…