On the Theoretical Limitations of Embedding-Based Retrieval

ArXiv: 2508.21038

🎯 Pitch

A single embedding vector cannot realize more than a tiny fraction of possible document rankings—this limit is combinatorial, not circumstantial. Even on a trivial task where queries simply ask 'who likes Apples?', state-of-the-art models fail to retrieve the correct documents, confirming that no amount of scaling can overcome the geometric ceiling of fixed-dimension dense retrieval.

---

1. Executive Summary

This paper analyzes the fundamental representational limitations of single-vector embedding models for information retrieval, establishing a theoretical lower bound on the embedding dimension required to realize all top-k retrieval sets and empirically validating this bound through both free-vector optimization and a purpose-built benchmark. The core contribution is the LIMIT dataset—a synthetic but realistic retrieval task constructed by assigning random attributes (e.g., "likes Apples") to named persons as documents and issuing simple single-attribute queries (e.g., "who likes Apples?") that stress-tests the combinatorial capacity identified by the theory, demonstrating that even state-of-the-art embedding models (Gemini Embedding, Qwen3 Embed, GritLM, Promptriever) fail dramatically despite the task's trivial nature, with the best single-vector model achieving only 54% recall@2 in the small 46-document setting. The paper establishes that for a given embedding dimension $d$ there exists a hard ceiling on the number of distinct top-k document subsets any embedding model can realize—a ceiling that grows only polynomially with $d$ while the demand for realizable subsets grows combinatorially with corpus size—establishing that single-vector architectures cannot scale to represent arbitrary instruction-following or reasoning-based retrieval tasks regardless of training data quality or model size.

2. Context and Motivation

The Core Problem: Single-Vector Embeddings Have a Hard Combinatorial Ceiling

The fundamental question this paper tackles is deceptively simple: how many distinct retrieval result sets can a single-vector embedding model actually represent? Every query issued to a dense retriever is converted into a vector $u \in \mathbb{R}^d$, compared against document vectors $v_1, \ldots, v_n \in \mathbb{R}^d$ via dot product (or cosine similarity), and the top-k scoring documents are returned. The embedding dimension $d$ is fixed—typically 768, 1024, or at most 4096—while the number of documents $n$ grows arbitrarily, and the set of possible queries a user could issue (especially with instruction-following and reasoning-based retrieval) continues to expand.

This means the model is being asked to assign real-valued scores in $\mathbb{R}^d$ such that for every conceivable query, the $k$ truly relevant documents score higher than the $n-k$ irrelevant ones. That is an enormous number of constraints—growing combinatorially with $n$ and $k$—all packed into a geometry of fixed dimension. The paper's central insight is that this is not merely a practical engineering challenge but a provable impossibility: for any embedding dimension $d$, there is a hard maximum on the number of distinct top-k subsets that can be realized with a guaranteed score margin, and this maximum grows only polynomially in $d$ ($O(\gamma^{-d})$), while the number of possible top-k combinations grows combinatorially as $\binom{n}{k}$. When the latter exceeds the former, some retrieval configurations become geometrically unrepresentable—no matter how the embedding model is trained or how much data it sees.

This gap is an existential threat to the trajectory of the field. As the paper notes (Section 1), embedding models are being tasked with "an ever-increasing set of retrieval tasks," moving from basic keyword matching to "reasoning, instruction-following, coding, and more." Benchmarks like BRIGHT (Su et al., 2024) ask models to retrieve Leetcode problems sharing algorithmic subtasks by reasoning over the problem descriptions. QUEST (Malaviya et al., 2023) combines retrieval criteria with logical operators ($\text{AND}$, $\text{OR}$, $\text{NOT}$), creating ad-hoc combinations of relevance constraints that connect previously unrelated documents. The proliferation of instruction-following retrieval—where the relevance definition changes per-query—means the space of possible top-k sets models must represent is expanding far beyond what static evaluation sets like MTEB (Muennighoff et al., 2022) capture. The paper argues that the community's implicit assumption—that sufficiently large models trained on sufficiently diverse data can handle any instruction—is mathematically wrong.

Why This Matters: Real-World Deployment and Evaluation Integrity

This theoretical limitation has practical consequences at multiple levels:

For model deployment: Web-scale retrieval systems routinely index billions of documents. Even the paper's most optimistic extrapolation from free-embedding experiments (Section 4) suggests that an embedding dimension of 4096 can handle only about 250 million documents with all top-2 combinations—a corpus size already exceeded by production systems. As the paper states in Section 3.0.1:

"For web-scale search, even the largest embedding dimensions with ideal test-set optimization are not enough to model all combinations."

This means that dense retrievers deployed at scale are guaranteed to fail on some queries, even if those queries are perfectly natural and well-formed. The failure mode is invisible under standard evaluation because existing benchmarks sample only a tiny fraction of possible queries.

For evaluation integrity: The paper makes a sharp observation about the disconnect between benchmark coverage and the space of possible queries. Existing retrieval datasets use limited numbers of queries due to annotation cost. The QUEST dataset (Section 5.1) has 325k documents and only 3,357 queries, each with 20 relevant documents. The number of possible top-20 subsets from 325k documents is approximately $7.1 \times 10^{91}$, meaning the evaluation queries cover an infinitesimally small fraction of the combinatorial space. Good performance on existing benchmarks therefore provides no guarantee about performance under novel instructions or reasoning patterns—precisely the capabilities that instruction-following retrieval benchmarks claim to measure. The paper argues this creates a false sense of progress: models can appear to "solve" benchmarks by overfitting to their particular query distributions while being fundamentally incapable of generalizing to the full space of possible retrieval instructions.

For architectural decisions: If single-vector architectures have a hard representational ceiling, the current trajectory of simply scaling embedding dimensions (from 768 to 1024 to 4096) or improving training data quality will eventually hit diminishing returns. The paper positions its findings as a call to explore alternative architectures—cross-encoders, multi-vector representations, sparse models, or entirely new similarity functions—before the field commits further to a paradigm with known limits.

Prior Approaches and Where They Fall Short

The paper identifies several categories of prior work and explains why none adequately addresses the fundamental limitation:

Empirical scaling of dimension and data. The dominant approach has been to increase embedding dimension and improve training data. Models have scaled from BERT-base's 768 dimensions to 1024 (GritLM, E5-Mistral), 2048 (Arctic Embed L), and 4096 (Qwen3 Embed). Training data has expanded to include massive contrastive datasets with hard negatives and instruction-following examples (Wang et al., 2022; Lee et al., 2025; Zhang et al., 2025). This approach implicitly assumes the problem is one of insufficient capacity or data, not intrinsic impossibility. The paper's Theorem 1 shows this assumption is false: for a fixed $d$, there exists an $n$ beyond which no amount of training data or optimization can encode all top-k combinations, because the geometric constraints simply cannot be satisfied.

Matryoshka representation learning (MRL). Kusupati et al. (2022) introduced MRL to allow a single model to produce embeddings at multiple resolutions (e.g., 256, 512, 768, 1024) by training the model to be robust to truncation. This is an important practical technique for storage and speed, but it does not address the fundamental limitation—the maximum representable capacity is still bounded by the full (largest) dimension $d$. MRL trades off between dimension and quality within the feasible region; it does not expand the region itself.

Prior theoretical work on vector limitations. The paper acknowledges foundational work in high-dimensional geometry that informs its analysis. The order-k Voronoi diagram (Voronoi, 1908; Clarkson, 1988) partitions space into regions based on their $k$ nearest neighbors, directly corresponding to retrieval sets. The number of such regions equals the number of distinct top-k retrieval configurations a given point set can realize. However, the paper notes (Section 2.3 and Appendix A) that "this quantity is notoriously difficult to bound tightly" and that constructing order-k Voronoi diagrams is computationally infeasible for $d > 3$. Prior work by Alon et al. (1985) on the sign-rank of set systems provides a related bound, but without a margin requirement, the construction requires infinite precision (Appendix D)—theoretically possible but practically meaningless, since real models must operate with finite numerical precision and handle noise.

Empirical observations of dimension limitations. Reimers & Gurevych (2020) observed that smaller-dimension embeddings produce more false positives at scale, and Ormazabal et al. (2019) showed empirical limitations in cross-lingual settings. Yin & Shen (2018) connected embedding dimension to bias-variance tradeoffs. However, these works treated the limitation as a practical tradeoff—using fewer dimensions hurts quality, so use more—rather than establishing a hard, in-principle bound on what any fixed-dimensional embedding can represent regardless of training quality. The paper's contribution is to show that the limitation is not just about false positive rates or variance; it's about the absolute number of distinguishable retrieval configurations.

Sign-rank analysis without margin. The paper's appendix (Appendix D) provides an alternative theoretical route using sign-rank, which had been applied to related problems by Alon et al. (1985) and later connected to knowledge graph embeddings by Badreddine et al. (2025) and to multi-label classification by Grivas et al. (2024). Without a margin requirement, the sign-rank bound is weaker: it requires only $2k$ dimensions (where $k$ is the maximum number of relevant documents per query) for any qrel matrix, regardless of $n$. This seems to contradict the paper's stronger bound. The resolution—and why the margin is essential—is that the sign-rank construction requires infinite precision in the vector representations. With a margin $\gamma$, the paper forces a gap between relevant and irrelevant scores, which is necessary for practical models that operate with finite numerical precision and must tolerate noise from quantization, gradient-based optimization, and tokenization. In Section 3.0.1, the paper explicitly states:

"A stricter margin requirement (larger $\gamma$) demands higher dimension, since $\log(1 + 1/\gamma)$ decreases with $\gamma$ (feasibility requires $\gamma \leq 1$, so the denominator is at least $\log 2$)."

This connects the theoretical bound to practical concerns: real models need a score gap to be robust, and that gap has a direct cost in required dimension.

How This Paper Positions Itself

The paper frames its contribution through three converging lines of evidence, each supporting the same fundamental claim from a different angle:

Theorem 1 (theoretical): Using a classical sphere-packing volume argument (Conway et al., 1999; Vershynin, 2018), the paper proves that if every $k$-subset of $n$ documents must be realizable as a top-k retrieval set with a score margin of at least $\gamma$, then the embedding dimension must satisfy:

$d \geq \frac{\log \binom{n}{k}}{\log(1 + 1/\gamma)}$

The proof is elegant in its simplicity: each distinct top-k set corresponds to a query vector $u_S$. For any two distinct subsets $S \neq T$, the corresponding query vectors must be at least $2\gamma$ apart in Euclidean distance (since they must separate the scores of documents in $S \setminus T$ from those in $T \setminus S$ by at least $2\gamma$). This gives $\binom{n}{k}$ pairwise-separated vectors on the unit sphere, and a sphere-packing volume argument yields the bound. The result is positioned as an extreme lower bound—real models face additional constraints from gradient-based learning, tokenization, and generalization that will inflate the required dimension further.

Free-embedding experiments (best-case empirical): To demonstrate that the theoretical limitation manifests even under idealized conditions, the paper directly optimizes query and document vectors on the test set using full-batch gradient descent with the InfoNCE loss (Section 4). There is no natural language, no tokenization, no train-test split—the vectors are free parameters optimized to perfectly satisfy the qrel matrix for increasing values of $n$ until optimization fails to achieve 100% accuracy. The critical-n points (where dimension becomes insufficient) are empirically modeled as a cubic polynomial in $d$, and even these idealized experiments require dimensions roughly 4.5× larger than the theoretical lower bound (e.g., $d \geq 18$ for $n=100$ with $k=2$, versus the theoretical bound of 4). This positions the theoretical bound as optimistic and the practical constraints as substantially more severe.

LIMIT dataset (real-world validation): To connect the theory to practice, the paper constructs a synthetic but realistic dataset (Section 5.2) designed to saturate the combinatorial capacity for a small number of documents. By choosing $n=46$ documents (giving $\binom{46}{2} = 1035$ queries, just above 1000) and assigning random attributes as the relevance criterion, the dataset creates a maximally interconnected qrel matrix where every pair of documents is jointly relevant to exactly one query. The task is trivially simple in linguistic terms—queries are just "who likes X?" and documents are just "Name likes X, Y, Z"—yet state-of-the-art embedding models fail dramatically. This positions the limitation not as an abstract mathematical curiosity but as a practically observable phenomenon on a task that requires no complex reasoning, only the ability to represent many distinct retrieval configurations simultaneously.

The paper distinguishes itself from prior work by providing not just empirical observations (like Reimers & Gurevych, 2020) or theoretical analyses without practical instantiation (like Alon et al., 1985), but a complete chain: theory $\rightarrow$ idealized empirical validation $\rightarrow$ real-world benchmark demonstration. The key novelty is showing that these limitations bite on simple, natural queries, not just esoteric or adversarial ones—directly challenging the common assumption cited in the abstract that "these difficulties are exclusively due to unrealistic queries, and those that are not can be overcome with better training data and larger models."

The paper also positions its findings as a cautionary message for the field's current trajectory. As instruction-following, multi-modal, and reasoning-based retrieval push embeddings to represent ever more combinations of documents as relevant, the combinatorial demand on embedding capacity grows super-exponentially. The paper argues that the community should be aware of these limits "both when creating evals and also by using alternate architectures—such as cross-encoders / multi-vector / more expressive similarity functions—when trying to handle the full range of instruction queries" (Section 1). This is a call not to abandon embedding models (which remain useful as first-stage retrievers) but to recognize their fundamental ceiling and invest in architectures that can transcend it.

3. Technical Approach

3.1 Reader Orientation

This paper constructs a three-part analytical framework that proves, empirically validates, and practically demonstrates the existence of a hard combinatorial ceiling on what single-vector embedding models can retrieve. It solves the problem of establishing whether and when embedding-based retrieval must fail—not due to insufficient training, poor data, or suboptimal architecture, but due to fundamental geometric constraints imposed by the embedding dimension—by connecting sphere-packing theorems from high-dimensional geometry to the retrieval task, then stress-testing the bound through idealized optimization experiments and a purpose-built benchmark that makes the failure mode observable on trivially simple natural language.

3.2 Big-Picture Architecture (Diagram in Words)

The analytical machinery has three interconnected components, each providing converging evidence from a different direction:

1. The Dimension Lower Bound (Theorem 1): A mathematical proof using sphere-packing arguments that, given $n$ documents of dimension $d$, a top-$k$ retrieval requirement, and a required score margin $\gamma$, there is a minimum dimension below which not all $\binom{n}{k}$ distinct top-$k$ subsets can be simultaneously realized. This component takes as input the corpus size $n$, the retrieval depth $k$, and the margin $\gamma$, and outputs a necessary condition $d \geq \log\binom{n}{k} / \log(1 + 1/\gamma)$. It establishes in-principle impossibility—a ceiling that no training procedure can exceed.

2. Free-Embedding Optimization Experiments: An idealized empirical framework where query and document vectors are treated as directly optimizable parameters (no tokenization, no language model, no train-test split). The optimizer is given the target relevance matrix and attempts to find vectors satisfying all top-$k$ constraints via full-batch gradient descent with the InfoNCE loss. The system identifies the critical-n value—the maximum number of documents for which optimization can still achieve 100% accuracy—as a function of dimension $d$. This component validates that the theoretical limitation is real under best-case optimization conditions and produces an empirical scaling curve that extrapolates to practical dimension sizes.

3. The LIMIT Dataset and Model Evaluation Pipeline: A synthetic retrieval benchmark constructed to saturate the combinatorial capacity for a small, tractable number of documents. It assigns latent attributes (e.g., "likes Apples") to named persons as documents, then generates all $\binom{n}{k}$ queries that ask for persons possessing a specific attribute, where each query has exactly $k=2$ relevant documents. The dataset is instantiated in natural language using simple templates, and state-of-the-art embedding models are evaluated on their ability to score relevant documents above irrelevant ones. This component demonstrates that the theoretical limitation manifests on real models processing real text, even when the linguistic task is trivial.

Information flows from theory to idealized validation to practical demonstration: the mathematical bound predicts that failure must occur at some scale; the free-embedding experiments show where it occurs under optimal conditions; the LIMIT benchmark shows that it actually occurs with current models on a simple task, confirming that real models operate far from the theoretical optimum.

3.3 Roadmap for the Deep Dive

• First, the formal problem setup and Theorem 1 proof — this establishes the vocabulary (unit vectors, margin $\gamma$, realized $k$-subsets) and the geometric argument that leads to the dimension lower bound, which is the conceptual spine of the entire paper.
• Second, the free-embedding optimization framework — this translates the abstract bound into an empirical methodology, explaining how the critical-$n$ experiments are designed, what optimizer and loss are used, and how the results are modeled and extrapolated, bridging theory and practice.
• Third, the LIMIT dataset construction pipeline — this details the step-by-step procedure for generating a realistic natural language dataset that saturates the combinatorial capacity, including the attribute generation process, document and query creation, and the design choices that make the task simultaneously simple and hard.
• Fourth, the model evaluation setup — this covers which models are evaluated, how dimensions are varied (including Matryoshka truncation), what metrics are reported, and the rationale for including non-single-vector baselines (BM25, ColBERT, TF-IDF) as comparison points.
• The order moves from abstract to concrete: theory $\rightarrow$ idealized optimization $\rightarrow$ realistic benchmark, which is the logical sequence the paper itself follows and which allows each component to motivate and contextualize the next.

3.4 Detailed, Sentence-Based Technical Breakdown

This is a theoretical analysis and empirical validation paper whose core idea is that the embedding dimension $d$ imposes a fundamental ceiling on how many distinct top-$k$ retrieval configurations any single-vector model can represent, and that this ceiling is already within reach of real-world retrieval demands.

---

The Formal Problem Setup and Score Margin Definition

The paper models the retrieval task geometrically. A set of $n$ documents is represented as unit vectors $v_1, \ldots, v_n \in \mathbb{R}^d$ on the $d$-dimensional unit sphere. Queries are also unit vectors $u \in \mathbb{R}^d$. Relevance of document $j$ to query $i$ is modeled by the dot product $\langle u_i, v_j \rangle$, which for unit vectors equals the cosine of the angle between them and ranges from $-1$ (maximally dissimilar) to $+1$ (maximally similar). The model returns the $k$ documents with the highest dot products as the retrieval result.

The paper introduces the concept of a score margin $\gamma > 0$ to formalize what it means for a retrieval configuration to be "realized." A $k$-subset $S \subseteq [n] = \{1, 2, \ldots, n\}$ is said to be realized with margin $\gamma$ if there exists a unit query vector $u_S$ such that:

$\min_{i \in S} \langle u_S, v_i \rangle \geq \max_{j \notin S} \langle u_S, v_j \rangle + 2\gamma$

where $\min_{i \in S} \langle u_S, v_i \rangle$ is the score of the lowest-scoring relevant document, $\max_{j \notin S} \langle u_S, v_j \rangle$ is the score of the highest-scoring irrelevant document, and $2\gamma$ is the enforced gap between them.

What it computes: the condition checks whether there exists a query vector that separates the relevant set $S$ from all other documents by a clean score buffer of size $2\gamma$. The innermost minimum $\min_{i \in S} \langle u_S, v_i \rangle$ identifies the weakest relevant document—the one hardest to pull above the threshold. The innermost maximum $\max_{j \notin S} \langle u_S, v_j \rangle$ identifies the strongest irrelevant document—the one most likely to intrude into the top-$k$. The inequality demands that even the weakest relevant document outscore the strongest irrelevant document by at least $2\gamma$. The factor of 2 is a mathematical convenience stemming from the sum-of-differences argument in the proof; the effective score gap felt by any individual document is $\gamma$.

Why this form: without a margin requirement, models could cheat by placing relevant and irrelevant scores arbitrarily close together—mathematically possible with infinite-precision real numbers but practically meaningless because finite numerical precision, gradient noise, and model approximation errors would cause frequent ranking inversions. The margin $\gamma$ forces the configuration to be robust to small perturbations, reflecting the reality that deployed models must produce reliable rankings despite quantization (e.g., product quantization for approximate nearest neighbor search), floating-point rounding, and the inherent stochasticity of gradient-based training. The paper explicitly states that $\gamma = 0.1$ (giving a score gap of $2\gamma = 0.2$) is "approximately standard for models based on empirical usage" (Section 3.0.1). Since dot products between unit vectors lie in $[-1, 1]$, the maximum possible score gap is $2$, so the margin must satisfy $0 < \gamma \leq 1$ for the condition to be feasible.

---

Theorem 1: The Dimension Lower Bound

The paper's central theoretical result is a necessary condition on the embedding dimension $d$ for a set of document vectors to realize all possible $k$-subsets as top-$k$ retrieval results with margin $\gamma$:

$\binom{n}{k} \leq \left(1 + \frac{1}{\gamma}\right)^d$

and consequently, rearranging by taking the logarithm of both sides:

$d \geq \frac{\log\binom{n}{k}}{\log\left(1 + 1/\gamma\right)}$

where $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ is the binomial coefficient counting the number of distinct $k$-subsets from $n$ documents, $\gamma \in (0, 1]$ is the margin parameter from the realizability condition in equation (1), and $d$ is the minimum required embedding dimension.

What it computes: the inequality places a lower bound on $d$ given $n$, $k$, and $\gamma$. The numerator $\log\binom{n}{k}$ grows roughly as $k \log(en/k)$ for $n \gg k$—that is, super-linearly in $k$ and logarithmically in $n$. The denominator $\log(1 + 1/\gamma)$ is a constant determined by the margin requirement: when $\gamma = 0.1$, this is $\log(11) \approx 2.398$; when $\gamma = 0.5$, it drops to $\log(3) \approx 1.099$; when $\gamma \to 1$, it approaches $\log(2) \approx 0.693$. The ratio gives the minimum dimension needed so that $\binom{n}{k}$ distinct query vectors can all be pairwise separated by at least $2\gamma$ on the unit sphere.

Why this form: the bound is derived from a sphere-packing volume argument, which is the standard technique in high-dimensional geometry for establishing capacity limits. The intuition is geometric: each distinct $k$-subset $S$ requires its own query vector $u_S$ that "activates" exactly those $k$ documents. For any two distinct subsets $S \neq T$, their query vectors $u_S$ and $u_T$ must be at least $2\gamma$ apart in Euclidean distance, because they must separate documents that are in one set but not the other. This means the $\binom{n}{k}$ query vectors are pairwise $2\gamma$-separated points on the surface of the unit sphere. Disjoint balls of radius $\gamma$ centered at each query vector all fit inside a larger ball of radius $1 + \gamma$ (since each query is at distance 1 from the origin, and the $\gamma$-ball around it extends at most $\gamma$ outward). The volume of the union of small balls cannot exceed the volume of the containing large ball, giving:

$\binom{n}{k} \cdot \gamma^d \leq (1 + \gamma)^d$

The factor $\gamma^d$ comes from the volume of a $d$-dimensional ball of radius $\gamma$, and $(1 + \gamma)^d$ from the containing ball of radius $1 + \gamma$; the dimension-dependent constant $C_d$ in the ball volume formula $C_d r^d$ cancels from both sides. Dividing through by $\gamma^d$ yields $\binom{n}{k} \leq ((1 + \gamma)/\gamma)^d = (1 + 1/\gamma)^d$. Taking logarithms isolates $d$.

The proof technique is constructive in its simplicity—it requires no assumptions about the document vectors beyond being unit-norm, no assumptions about the query vectors beyond being unit-norm and satisfying the margin condition, and no assumptions about the optimization procedure. The bound is therefore universal: any set of normalized vectors in $\mathbb{R}^d$ that realizes all $k$-subsets with margin $\gamma$ must satisfy the inequality. The paper notes that the bound is "an extreme lower bound" because real models face additional constraints—gradient-based learning dynamics, tokenization of natural language, the need to generalize rather than memorize—that will further inflate the required dimension beyond what the geometric packing argument alone demands.

The paper provides a numerical instantiation in Table 1 (Section 3.0.1) using $\gamma = 0.1$, showing for example that a corpus of $n=10^5$ documents with $k=10$ requires $d \geq 329$; with $n=10^6$ and $k=10$, $d \geq 425$; with $n=10^{11}$ and $k=10$, $d \geq 100$. The growth is logarithmic in $n$ but the constants are substantial, and the paper emphasizes that practical models using dimensions of 768–4096 are already within range of these bounds for large-scale corpora. Since real-world constraints may multiply these numbers, the paper argues that "even a small multiple of this lower bound would make the embedding dimension requirement infeasible" (Section 3.0.1).

---

The Free-Embedding Optimization Framework

To empirically validate that the theoretical limitation is real—and not merely an artifact of the proof technique—the paper designs an optimization experiment under the most favorable possible conditions. The key idea is to remove every practical constraint that real embedding models face and see whether the dimension bound still holds.

Setup. A set of $n$ document vectors and $m$ query vectors, all in $\mathbb{R}^d$, are initialized randomly and then treated as directly optimizable parameters. Unlike real models, there is no language model backbone, no tokenization, no shared encoder that must map text to vectors—each query and each document has its own dedicated vector that can move freely in $\mathbb{R}^d$ during optimization. The target relevance matrix is the test set itself: each query is assigned a specific set of $k$ relevant documents, drawn from all $\binom{n}{k}$ possible combinations. This means the optimizer sees the evaluation task directly; there is no train-test split, no generalization requirement, no out-of-distribution concern. The goal is to find vectors that achieve 100% retrieval accuracy on this exact set of queries—if this fails for a given $(n, d)$, then any real model with constraints will certainly fail.

Optimization procedure. The vectors are optimized using the Adam optimizer (Kingma & Ba, 2014) with full-batch gradient descent. Each gradient update computes the loss over all correct triples simultaneously—that is, all query-relevant_document pairs, with all other documents serving as in-batch negatives. The loss function is the InfoNCE loss (Oord et al., 2018):

$\mathcal{L}_{\text{total}} = -\frac{1}{M} \sum_{i=1}^{M} \log \frac{\sum_{d_r \in R_i} \exp(\text{sim}(q_i, d_r) / \tau)}{\sum_{d_k \in D} \exp(\text{sim}(q_i, d_k) / \tau)}$

where $M$ is the number of queries (equal to $\binom{n}{k}$ for the all-combinations experiments), $R_i$ is the set of $k$ documents relevant to query $i$, $D$ is the set of all $n$ documents, $\text{sim}(q_i, d_j) = \langle q_i, d_j \rangle$ is the dot product (equivalent to cosine similarity for unit vectors), and $\tau$ is a temperature parameter controlling the sharpness of the softmax distribution.

What it computes: for each query $i$, the loss computes the log-softmax over all documents, restricted to the relevant ones. The numerator sums the exponentiated, temperature-scaled similarities of the $k$ relevant documents. The denominator sums the exponentiated similarities of all $n$ documents. The fraction is the model's estimated probability that a randomly chosen relevant document is indeed relevant. The negative logarithm converts this into a loss: when the model assigns high probability to the truly relevant documents (making the fraction close to 1), the loss is low; when the model fails to distinguish relevant from irrelevant documents, the loss is high. The outer average normalizes across all $M$ queries.

Why this form: the InfoNCE loss is the standard contrastive objective in dense retrieval training and was chosen because "in preliminary experiments, we found that InfoNCE performed best, beating MSE and Margin" (Section 4). The full-batch setting (all documents in the denominator) eliminates the approximation error introduced by negative sampling—the model sees every possible contrast between a relevant document and every irrelevant document at every step. This is the strongest possible training signal. The temperature $\tau$ controls the concentration of the softmax: low temperatures make the loss focus more on hard negatives (irrelevant documents that currently score highly), while high temperatures spread attention more uniformly. The paper uses unit vectors enforced via projected gradient descent, meaning after each gradient step the vectors are projected back onto the unit sphere, consistent with the theoretical analysis and standard practice in embedding model training.

Early stopping and critical-n determination. The paper trains until there is no improvement in the loss for 1000 iterations, then checks whether the vectors achieve 100% retrieval accuracy (all $M$ queries return exactly their $k$ designated relevant documents in the top-$k$ positions). The critical-n for a given dimension $d$ is the largest $n$ for which this optimization succeeds. The paper fixes $k=2$ (the smallest nontrivial retrieval depth) and varies $n$ upward from a small starting value, incrementing by 1, until optimization fails. This produces a set of $(d, \text{critical-}n)$ pairs.

Results and empirical modeling. Figure 2 (Section 4) plots the critical-$n$ values for $d$ ranging from 4 to 45. The paper fits a cubic polynomial regression to these points:

$y = -10.5322 + 4.0309 d + 0.0520 d^2 + 0.0037 d^3$

where $y$ is the predicted critical-$n$ and $d$ is the embedding dimension, achieving $r^2 = 0.999$.

What it computes: the polynomial maps an embedding dimension $d$ to the maximum number of documents $n$ for which all $\binom{n}{2}$ top-2 combinations can be simultaneously realized via direct vector optimization. The cubic form (rather than linear or quadratic) was selected empirically as the best fit to the observed critical points. The $r^2$ value of 0.999 indicates near-perfect fit to the measured data.

Why this form: the cubic is purely empirical—it is not derived from the theoretical bound but fitted to the observed optimization behavior. The paper uses it to extrapolate to larger embedding dimensions that are computationally infeasible to evaluate directly (since $\binom{n}{k}$ grows rapidly). The extrapolation gives critical-$n$ values of approximately: 500,000 for $d=512$, 1.7 million for $d=768$, 4 million for $d=1024$, 107 million for $d=3072$, and 250 million for $d=4096$. These numbers represent the optimistic best case—the maximum corpus size for which any embedding model of that dimension could possibly handle all top-2 retrieval combinations, assuming it could directly optimize the vectors on the test set without any of the constraints real models face.

Connection to theoretical bound. The paper notes that the free-embedding results require dimensions substantially larger than Theorem 1 predicts. For $n=100$, $k=2$, and $\gamma=0.1$, Theorem 1 gives a lower bound of $d \geq \log\binom{100}{2} / \log(11) = \log(4950) / 2.398 \approx 3.57$, so $d \geq 4$. However, the free-embedding experiments show that even with full test-set optimization, $d=18$ is needed to solve $n=100$—a factor of roughly $4.5\times$ the theoretical minimum. The paper attributes this multiplier to the constraints of gradient-based optimization (InfoNCE loss landscape, Adam dynamics, projection onto the unit sphere) and to the finite numerical precision of floating-point arithmetic. This multiplier is the justification for claiming that the theoretical bounds in Table 1, already large, should be considered "grossly underestimated."

---

The LIMIT Dataset Construction Pipeline

To demonstrate that the theoretical limitation affects real embedding models on natural language tasks, the paper constructs LIMIT, a synthetic retrieval benchmark designed to saturate the combinatorial capacity for a small number of documents. The construction proceeds in several carefully documented stages (Section 5.2, Figure 1).

Stage 1: Determine the document count $n$ and query count $m$. The paper targets exactly $m = 1000$ queries (to maintain statistical significance while keeping evaluation fast) with $k = 2$ relevant documents per query (both for simplicity and to mirror common retrieval benchmarks like Natural Questions and HotpotQA). Since the number of distinct top-2 subsets from $n$ documents is $\binom{n}{2} = n(n-1)/2$, the smallest $n$ yielding at least 1000 queries is $n = 46$, since $\binom{46}{2} = 1035$. The paper therefore sets $n = 46$ documents for the core (small) version of LIMIT, giving $1035$ queries—just above the 1000 target. A full version with $n = 50,000$ documents is also created, where only 46 documents are relevant to any query (the remaining $49,954$ are distractors that are never relevant), and the same 1035 queries are used.

What this choice achieves: by setting $n=46$ and making every possible pair of documents relevant to exactly one query, the qrel matrix achieves maximum combinatorial density. Every document is connected to every other document through exactly one shared query. There is no subset of documents that could be grouped together without conflicting with some existing query's requirement. This is precisely the condition that stresses the embedding dimension—the model must simultaneously maintain 1035 distinct pairwise separations in $\mathbb{R}^d$.

Stage 2: Generate the attribute pool. The paper uses Gemini 2.5 Pro to generate a list of "attributes a person could like" (e.g., "Apples," "Hawaiian pizza," "Scuba diving"). The initial list is then cleaned iteratively by "asking it to remove duplicates/hypernyms, while also checking the top failures with BM25 to ensure no overlap," producing a final pool of 1850 distinct attributes (Section 5.2). The cleaning step ensures that attributes are semantically distinct—no two attributes should be near-synonyms that a model might conflate, since the task relies on exact attribute matching to determine relevance. The BM25 check catches cases where the synthetic attributes might accidentally overlap lexically with person names or other text elements.

Why attributes and not other relevance signals: the paper chooses the attribute-based mapping ("who likes X?") because it is "plentiful and doesn't present issues w.r.t. other items: one can like Hawaiian pizza but dislike pepperoni, all preferences are valid" (Section 5.2). This means any assignment of attributes to persons is logically consistent—there are no contradictory constraints like "Jon is a parent of Mary" and "Mary is a parent of Jon" that would arise with relational mappings. The space of possible attribute assignments is therefore unconstrained and can be freely randomized.

Stage 3: Construct the qrel matrix and assign attributes. The paper creates a qrel matrix where each query $q$ is associated with a unique attribute $a_q$ and exactly two relevant documents $d_i, d_j$, both of which list $a_q$ among their liked attributes. The assignment proceeds as follows (detailed in Section 5.2 and illustrated in Figure 1):

1. Each of the 1035 queries is assigned a unique attribute drawn without replacement from the 1850-attribute pool. This ensures no two queries share the same attribute, keeping queries distinct.
2. For each query, two distinct documents are selected as the relevant set. Since every pair of the 46 documents must be relevant to exactly one query, this is equivalent to taking all $\binom{46}{2}$ unordered document pairs and assigning one unique attribute-query to each pair.
3. Each document receives the attributes associated with all queries for which it is relevant. Since each document appears in exactly 45 pairs (paired with every other document once), each document lists exactly 45 attributes as its "likes."
4. Additional attributes are randomly sampled and assigned to bring all 50,000 documents in the full version to the same number of attributes (45), ensuring uniform document length. Documents that are never relevant to any query (the $49,954$ distractors) receive 45 randomly chosen attributes that do not appear in any query, making them permanently irrelevant.

Stage 4: Instantiate as natural language. Each document is rendered as a sentence of the form "[First Name] [Last Name] likes [Attribute 1], [Attribute 2], ..., [Attribute 45]." where first and last names are drawn from open-source name lists. Each query is rendered as "who likes [Attribute]?" The paper imposes two realism constraints: (1) documents should be short (fewer than 50 attributes, i.e., "around 100 tokens"), keeping the task computationally lightweight and avoiding long-context challenges that would confound the dimension limitation, and (2) each query asks for only one item, keeping the linguistic complexity to a minimum.

Why this construction produces a hard task: the central design principle is that the qrel matrix is maximally interconnected. Because every pair of documents shares exactly one query, and every query connects exactly two documents, the resulting bipartite query-document graph is a complete graph on the document side—every document is related to every other document through a distinct query. Any embedding model must therefore arrange the 46 document vectors in $\mathbb{R}^d$ such that for each of the 1035 queries, a corresponding query vector can pull exactly its two designated documents above all others. This is exactly the combinatorial condition that Theorem 1 bounds: the model must realize $\binom{46}{2} = 1035$ distinct top-2 subsets simultaneously. The simplicity of the language—short sentences, no syntax complexity, no reasoning required—isolates the combinatorial capacity limitation from other confounding factors like language understanding difficulty or domain shift.

The synonym variant. To demonstrate that lexical matching is not a panacea, the paper creates a variant of LIMIT-small where all attributes in the corpus are replaced with synonyms (e.g., "glasses" becomes "spectacles") generated by Gemini 2.5 Pro, with the constraint that synonyms do not match any other existing synonyms or original items. This variant reduces lexical overlap between queries and documents while preserving the exact same qrel matrix structure, testing whether models rely on keyword matching rather than semantic understanding.

---

Model Evaluation Setup

Models evaluated. The paper evaluates a representative set of state-of-the-art single-vector embedding models spanning different dimensions, training paradigms, and backbone architectures (Section 5.2):

• E5-Mistral 7B (Wang et al., 2022; 2023): Mistral-7B backbone, instruction-tuned, dimension up to 4096.
• GritLM 7B (Muennighoff et al., 2024): Mistral-7B backbone, trained for both generation and embedding, dimension up to 4096.
• Promptriever Llama3 8B (Weller et al., 2024b): Llama-3-8B backbone, instruction-trained with prompt-based retrieval, dimension up to 4096.
• Qwen3 Embed (Zhang et al., 2025): Qwen backbone, dimension up to 4096, trained with MRL.
• Gemini Embedding (Lee et al., 2025): Gemini backbone, dimension up to 3072, trained with MRL.
• Snowflake Arctic Embed Large v2.0 (Yu et al., 2024): dimension up to 4096, trained with MRL.

The paper also includes non-single-vector baselines for comparison: BM25 (lexical sparse retrieval, implemented via bm25s, Lù 2024), GTE-ModernColBERT (multi-vector late interaction, Chaffin 2025a; Chaffin & Sourty 2024), and a custom token-wise TF-IDF model that tokenizes each unique attribute as a separate vocabulary item (built as a diagnostic tool to confirm that the dataset construction is correct—it achieves 100% recall by construction since attributes map one-to-one to tokens).

Embedding dimension variation. For models trained with Matryoshka Representation Learning (MRL, Kusupati et al., 2022), the paper evaluates at multiple truncated dimensions by taking the first $d$ coordinates of the full embedding: 32, 64, 128, 256, 384, 512, 768, 1024, 2048, 3072, and 4096 (the specific set varies by model's maximum dimension). For models not trained with MRL, "this will result in sub-par scores," but the paper includes these truncated evaluations anyway to demonstrate the impact of dimensionality on performance. Stars in the figures (Figures 3, 4) indicate models explicitly trained with MRL.

Evaluation metrics. The primary metrics are Recall@$k$ for $k \in \{2, 10, 100\}$ in the full setting (50k documents) and $k \in \{2, 10, 20\}$ in the small setting (46 documents). Recall@$k$ measures the fraction of the 2 relevant documents that appear in the top-$k$ retrieved results, averaged over all 1035 queries. The paper notes that Recall@2 is the strictest metric—it requires both relevant documents to be in the exact top-2 positions—while Recall@10 and Recall@100 are progressively more lenient, measuring whether the model places relevant documents anywhere near the top of the ranking.

Why these models and metrics: the selection spans the current state-of-the-art in terms of both model scale (7B–8B parameters) and embedding dimension (up to 4096), covering both MRL-trained and non-MRL-trained variants to assess whether MRL's dimension flexibility helps or hurts on this task. The inclusion of BM25 and ColBERT provides baselines from alternative architectural paradigms to test whether the limitation is specific to single-vector models or affects all retrieval architectures. The recall metrics at multiple cutoffs allow diagnosis of failure modes: low Recall@2 but higher Recall@10 suggests the model partially distinguishes relevant from irrelevant documents but cannot achieve perfect separation; uniformly low recall at all cutoffs suggests complete failure of the embedding space to capture the relevance structure.

Training on LIMIT. To test whether poor performance is due to domain shift (models not having seen attribute-listing documents during training) rather than intrinsic difficulty, the paper fine-tunes lightonai/modernbert-embed-large (Chaffin, 2025c) on either a synthetically generated training set (using non-test-set attributes to create similar-looking examples, 2500 examples trimmed to 2000) or directly on the LIMIT test set (Section 5.2, Figure 5). Training uses the SentenceTransformers library (Reimers & Gurevych, 2019) with the MultipleNegativesRankingLoss, full-dataset batch size, a no-duplicates sampler to prevent in-batch positives from contaminating negatives, learning rate $5 \times 10^{-5}$, and 5 epochs. Embedding dimensions are varied during training by projecting the hidden layer down to the specified size rather than using MRL post-hoc. The contrast between training-set and test-set performance diagnoses the source of difficulty: if training on in-domain data helps, the problem is domain shift; if only test-set memorization works (analogous to the free-embedding setting), the problem is intrinsic representational capacity.

Cross-encoder evaluation. The paper evaluates Gemini-2.5-Pro (Comanici et al., 2025) as a reranker on the small setting (46 documents) by providing all 46 documents and all 1000 queries in a single prompt, asking the model to output the relevant documents for each query in one generation (Section 5.3). This tests whether the task is solvable with an architecture that does not rely on fixed-dimensional vector comparisons—cross-encoders can attend over all document-query pairs jointly and are not constrained by a single embedding dimension. The result (100% accuracy) confirms that the task is not inherently ambiguous or ill-posed; it is specifically hard for embedding-based retrieval.

4. Key Insights and Innovations

Innovation 1: The Combinatorial Ceiling Is a Provable Impossibility, Not a Training Challenge

The paper's most fundamental intellectual contribution is recasting the scaling difficulty of dense retrieval from an empirical optimization problem into a geometric impossibility result. Prior to this work, the dominant narrative in the embedding community was that models fail on complex retrieval tasks because of insufficient training data, suboptimal contrastive objectives, or models that are too small—all problems addressable by scaling up. Works like Reimers & Gurevych (2020) observed that smaller embeddings produce more false positives at scale, but framed this as a practical tradeoff (use larger dimensions for better quality). The implicit assumption, as the paper states in its abstract, was that difficulties "can be overcome with better training data and larger models."

Theorem 1 demolishes this assumption. By connecting the retrieval task to classical sphere-packing bounds, the paper proves that for any fixed embedding dimension $d$, there exists a corpus size $n$ beyond which no assignment of document vectors can realize all top-$k$ subsets—regardless of how the model is trained, how much data it sees, or what loss function is optimized. The bound is universal: it applies to any set of unit vectors in $\mathbb{R}^d$, making no assumptions about the optimization procedure, the training distribution, or the model architecture. The key conceptual move is the introduction of the margin parameter $\gamma$, which forces the analysis beyond the sign-rank approach of Alon et al. (1985). Without a margin, the sign-rank construction can represent any qrel matrix in only $2k$ dimensions—but requires infinite precision, making it practically meaningless. The margin $\gamma$ encodes the reality that deployed models must tolerate quantization, gradient noise, and floating-point imprecision, and its presence transforms the bound from a theoretical curiosity into a practical ceiling.

This is a fundamental shift, not incremental: it changes the question from "how can we train models to handle more retrieval combinations?" to "at what corpus scale must single-vector architectures necessarily fail?" The answer—provided numerically in Table 1 and extrapolated to practical dimension sizes—shows that web-scale corpora already exceed what even the largest embedding dimensions can represent for moderate $k$. The practical implication is that scaling embedding dimensions (from 768 to 1024 to 4096) or improving training data cannot escape a hard geometric ceiling. The paper connects this to the Johnson-Lindenstrauss lemma by inversion: while JL gives a sufficient dimension to preserve pairwise distances, Theorem 1 gives a necessary dimension to realize retrieval sets, and the necessary condition grows combinatorially while the sufficient condition grows only logarithmically. This reframes the entire research program around single-vector architectures as one with a known, provable endpoint.

Innovation 2: Difficulty as Combinatorial Saturation, Not Linguistic Complexity

The paper introduces a diagnostic concept that fundamentally reorients how the field should think about retrieval hardness. Traditional benchmarks escalate difficulty by increasing linguistic complexity: multi-hop reasoning (HotpotQA), logical operators (QUEST), long-context understanding (BRIGHT), or domain-specific jargon. The implicit model is that harder tasks require deeper language understanding, and better language models will eventually solve them.

The LIMIT dataset breaks this coupling entirely. The linguistic task is trivial—queries are "who likes X?" and documents are "Name likes X, Y, Z"—yet state-of-the-art embedding models fail catastrophically, with the best single-vector model (Promptriever) achieving only 54.3% Recall@2 even in the 46-document setting (Figure 4). The task requires no reasoning, no multi-hop inference, no domain knowledge. What makes it hard is purely combinatorial: the qrel matrix is constructed so that every pair of the $n$ documents is relevant to exactly one query, creating exactly $\binom{n}{2}$ distinct top-2 subsets that must be simultaneously realizable in the embedding space. The graph density and average query strength metrics in Appendix F (Table 2) formalize this: LIMIT's qrel graph density (0.085) and average query strength (28.5) are orders of magnitude higher than standard datasets like NQ (both 0) or HotpotQA (0.000037 and 0.11 respectively).

This is a diagnostic innovation, not a new method. It provides a clean probe that isolates combinatorial capacity from other sources of difficulty. The paper demonstrates this isolation through the domain-shift experiment (Figure 5): training a model on in-domain examples (synthetically generated attribute-listing documents) provides negligible improvement, while training directly on the test set allows overfitting and solves the task. This proves that the failure is not about unfamiliar language patterns—it is intrinsic to the representational capacity of the embedding space. The synonym variant (Figure 6) further isolates lexical matching from combinatorial capacity, showing that BM25's advantage vanishes when keyword overlap is removed, while single-vector models (which attempt semantic matching) suffer less degradation. The conceptual contribution is the separation of retrieval hardness into two orthogonal axes: linguistic difficulty (how hard the text is to understand) and combinatorial density (how many distinct retrieval configurations must coexist). The field has focused almost exclusively on the former; this paper argues the latter is the more fundamental bottleneck as instruction-following and reasoning-based retrieval proliferate.

Innovation 3: The Margin as the Bridge Between Theory and Practice

The paper makes a subtle but crucial conceptual move by centering the score margin $\gamma$ as the parameter that connects geometric impossibility results to practical model behavior. The theoretical bound in Theorem 1 depends inversely on $\log(1 + 1/\gamma)$: as $\gamma \to 0$ (no margin), the denominator grows without bound, making the required dimension arbitrarily small—consistent with the sign-rank result that any qrel matrix is representable in $2k$ dimensions if infinite precision is allowed. As $\gamma$ grows (larger required gap), the required dimension increases sharply.

The insight is that $\gamma$ is not a free parameter the theorist chooses for convenience; it is imposed by the real world. Finite numerical precision, quantization for approximate nearest neighbor search, stochasticity in gradient-based optimization, and tokenization noise all demand that relevant and irrelevant documents be separated by a non-trivial score buffer for the ranking to be reliable. The paper's empirical choice of $\gamma = 0.1$ (a score gap of $2\gamma = 0.2$ on the $[-1, 1]$ range) is described as "approximately standard for models based on empirical usage" (Section 3.0.1). This operationalizes the margin, turning it from an analytical convenience into an empirically measurable property of deployed systems.

The free-embedding experiments (Section 4, Figure 2) provide the empirical validation of this bridge. Even under idealized conditions—direct vector optimization on the test set, full-batch gradient descent, no tokenization—the achieved dimensions are roughly 4.5× larger than the theoretical lower bound (e.g., $d \geq 18$ needed for $n=100$ versus the theoretical $d \geq 4$). This gap is the cost of gradient-based learnability: the InfoNCE loss landscape, Adam dynamics, and projection onto the unit sphere all impose additional geometric constraints beyond the pure packing argument. The paper does not claim to theoretically characterize this multiplier, but the empirical documentation of its existence is itself a contribution—it tells practitioners that theoretical bounds should be multiplied by a substantial factor (the paper suggests roughly 4–5×) for practical planning. The extrapolation from the cubic fit (critical-$n$ of ~250M for $d=4096$) provides a concrete, if empirically derived, ceiling on what the largest current embedding models can handle with all top-2 combinations.

This contribution is incremental in its theoretical machinery (sphere-packing is standard) but fundamental in its conceptual reframing: it positions the margin not as a proof-technical detail but as the central design constraint linking geometric capacity to engineering reality. Future work on alternative architectures or loss functions can be evaluated by how they affect this margin—a loss that achieves equivalent accuracy with a smaller margin effectively increases representational capacity without changing $d$.

Innovation 4: The Necessity (and Limitations) of Architectural Pluralism

The paper's final intellectual contribution is a structured empirical argument that single-vector architectures are not just practically limited but categorically insufficient for the retrieval demands the field is moving toward, and that different architectural paradigms have qualitatively different failure modes. This is not a claim that embedding models are useless—the paper explicitly notes they remain useful for first-stage retrieval—but rather a demonstration that the current monoculture around single-vector dense retrievers cannot serve as a universal solution.

The evidence is the comparative evaluation in Figures 3, 4, and 6, which reveals a three-way tradeoff with no architecture dominating:

BM25 (sparse lexical) achieves 97.8% Recall@2 on LIMIT-small (Table 4), essentially solving the task. This works because BM25's effective dimension is the vocabulary size—tens of thousands of dimensions—giving it enormous combinatorial capacity. But Figure 6 shows this advantage is brittle: when attributes are replaced with synonyms, BM25 drops by over 89%, falling below most single-vector models. Sparse lexical models have high capacity but no semantic generalization. The paper explicitly notes that "it is less clear how to apply sparse models to instruction-following and reasoning-based tasks where there is no lexical or even paraphrase-like overlap" (Section 5.3).

GTE-ModernColBERT (multi-vector late interaction) achieves 83.5% Recall@2 on LIMIT-small—substantially better than single-vector models but far from perfect. Multi-vector models gain expressivity by representing each token with its own vector and using MaxSim for scoring, increasing the effective representational capacity without increasing a single embedding's dimension. But the paper notes these models are "not generally used for instruction-following or reasoning-based tasks" (Section 5.3), leaving open whether their advantages transfer to the settings where combinatorial capacity is most stressed.

Gemini-2.5-Pro (cross-encoder) achieves 100% accuracy by jointly attending over all document-query pairs, having no fixed-dimensional bottleneck. This confirms the task is solvable with sufficient architectural expressivity, but cross-encoders are too expensive for first-stage retrieval at scale.

Single-vector models sit in an uncomfortable middle: they have some semantic generalization (hence outperform BM25 on the synonym variant) but are bounded by their embedding dimension (hence fail dramatically on LIMIT even at Recall@100). The dimension-dependent scaling in Figures 3 and 4 (performance monotonically improving with dimension for most models) directly visualizes the capacity constraint.

The conceptual contribution is not a new architecture but an architectural diagnostic framework—showing that the question is not "which model is best?" but "which combination of architectures can cover the full space of retrieval demands?" The paper argues that as instruction-following and reasoning-based benchmarks expand the space of possible queries, single-vector models will increasingly encounter their combinatorial ceiling, and the community needs to invest in alternatives (cross-encoders, multi-vector models, hybrid sparse-dense approaches, or novel architectures like hyperencoders) before the limitation becomes a deployment crisis. This is a reframing of the research agenda: from optimizing within a paradigm with known bounds to developing new paradigms that transcend those bounds.

The significance of this argument is that it is empirically grounded rather than purely theoretical. The LIMIT dataset provides a concrete, reproducible stress test that any proposed architecture can be evaluated against. An architecture that scores well on standard benchmarks but fails on LIMIT has a demonstrable combinatorial capacity limitation; one that performs well on both has arguments for genuine representational superiority. This transforms the paper's theoretical analysis into a practical evaluation tool.

5. Experimental Analysis

Evaluation Methodology

• Dataset. The primary evaluation dataset is LIMIT, a synthetic retrieval benchmark constructed by the authors (Section 5.2). The small version contains $n = 46$ documents and $m = \binom{46}{2} = 1035$ queries (each with exactly $k = 2$ relevant documents), while the full version adds $49,954$ distractor documents (never relevant to any query) for a total of 50,000 documents with the same 1035 queries. A synonym variant of the small version replaces all corpus attributes with non-overlapping synonyms to reduce lexical overlap. The paper also references existing datasets (QUEST, BRIGHT, NQ, HotpotQA, SciFact, FollowIR Core17) for comparative qrel graph analysis in Appendix F (Table 2).

• Base model(s). Six state-of-the-art single-vector embedding models spanning different backbones, dimensions, and training paradigms: E5-Mistral 7B (Mistral-7B backbone, Wang et al., 2022; 2023), GritLM 7B (Mistral-7B backbone, Muennighoff et al., 2024), Promptriever Llama3 8B (Llama-3-8B backbone, Weller et al., 2024b), Qwen3 Embed (Zhang et al., 2025), Gemini Embedding (Lee et al., 2025), and Snowflake Arctic Embed Large v2.0 (Yu et al., 2024). These span embedding dimensions from 1024 to 4096. Three non-single-vector baselines are also evaluated: BM25 (lexical sparse retrieval via bm25s, Lù 2024), GTE-ModernColBERT (multi-vector late interaction, Chaffin 2025a; Chaffin & Sourty 2024), and a custom token-wise TF-IDF model. For the fine-tuning experiments (Figure 5), lightonai/modernbert-embed-large (Chaffin, 2025c) is used. For the cross-encoder comparison (Section 5.3), Gemini-2.5-Pro (Comanici et al., 2025) is evaluated.

• Metrics. The primary metric is Recall@$k$ for $k \in \{2, 10, 100\}$ on the full LIMIT (50k documents) and $k \in \{2, 10, 20\}$ on LIMIT-small (46 documents). Recall@$k$ measures the fraction of the 2 relevant documents that appear in the top-$k$ retrieved results, averaged over all 1035 queries. Recall@2 is the strictest metric, requiring both relevant documents in the exact top-2 positions. For the free-embedding experiments (Section 4), the metric is binary: whether optimization achieves 100% retrieval accuracy (all queries return exactly their designated relevant documents in the top-$k$).

• Baselines. BM25 serves as the sparse lexical baseline, representing an architecture with extremely high effective dimensionality (vocabulary size). GTE-ModernColBERT serves as the multi-vector late-interaction baseline. The token-wise TF-IDF model (which tokenizes each unique attribute as a separate vocabulary item) serves as a diagnostic oracle baseline—it achieves 100% recall by construction since attributes map one-to-one to tokens, confirming the dataset construction is correct. For the domain-shift experiment (Figure 5), training on the synthetic training set versus training on the test set provides a baseline for distinguishing intrinsic difficulty from domain shift. For the FLOPs-matched comparison context, the cross-encoder Gemini-2.5-Pro (achieving 100% on LIMIT-small) serves as an upper bound on what is achievable with sufficient architectural expressivity.

• Generation budget / compute accounting. There is no generation budget in the traditional sense, as embedding-based retrieval does not involve sequential token generation. The relevant compute accounting is the embedding dimension $d$—the paper systematically varies this from 2 to 4096 by truncating embeddings (using Matryoshka-style truncation for models trained with MRL, marked with stars in figures, and naive truncation for others). For the free-embedding experiments (Section 4), compute is measured by the tuple $(n, d)$ where full-batch gradient descent is run to convergence. The paper does not compare FLOPs across architectures; the dimension $d$ serves as the universal capacity proxy. For the training experiments (Figure 5), compute is standard fine-tuning for 5 epochs with full-dataset batch size. For the cross-encoder evaluation, a single forward pass processes all 46 documents and 1000 queries simultaneously.

• Cross-validation / statistical protocol. There is no cross-validation in the conventional sense. The LIMIT dataset has a single test split of 1035 queries (all $\binom{46}{2}$ combinations). For the domain-shift experiment (Figure 5), the "train" split is synthetically generated using non-test-set attributes (2500 examples, trimmed to 2000 to match test set size), and the "test" split is the official LIMIT test set. The free-embedding experiments (Figure 2) use a deterministic protocol: for each dimension $d$, the number of documents $n$ is increased by 1 until optimization fails to reach 100% accuracy, with early stopping at 1000 iterations of no loss improvement; the critical-$n$ is recorded and fitted with a cubic polynomial ($r^2 = 0.999$). The paper notes (Appendix F, Table 2) that LIMIT's qrel graph density (0.085) and average query strength (28.5) are substantially higher than existing datasets (NQ: 0 and 0; HotpotQA: 0.000037 and 0.11; FollowIR Core17: 0.026 and 0.59), positioning LIMIT as an outlier on these combinatorial metrics.

Main Quantitative Results

Free-Embedding Optimization: Empirical Validation of the Dimension Bound

The free-embedding experiments (Section 4, Figure 2, Table 6) establish that even under idealized optimization—direct vector optimization on the test set with full-batch InfoNCE, no tokenization, no generalization requirement—the embedding dimension $d$ imposes a hard limit on the number of documents $n$ for which all $\binom{n}{2}$ top-2 combinations can be simultaneously realized.

For $k = 2$ and dimensions ranging from $d = 4$ to $d = 45$, the critical-$n$ values (Table 6) grow from $n = 10$ at $d = 4$ to $n = 626$ at $d = 45$. The fitted cubic polynomial $y = -10.5322 + 4.0309 d + 0.0520 d^2 + 0.0037 d^3$ achieves $r^2 = 0.999$, indicating near-perfect fit. Extrapolating to practical embedding dimensions yields: critical-$n$ of approximately 500,000 for $d = 512$, 1.7 million for $d = 768$, 4 million for $d = 1024$, 107 million for $d = 3072$, and 250 million for $d = 4096$.

Critically, even these best-case critical-$n$ values are substantially higher than Theorem 1's theoretical lower bound. For $n = 100$ and $\gamma = 0.1$, Theorem 1 requires $d \geq 4$, but the free-embedding experiments require $d \geq 18$—a factor of approximately 4.5×. The paper attributes this gap to "constraints on gradient learning or other LM-based constraints (e.g. tokenization, generalization)" (Section 3.0.1). The practical implication is that theoretical bounds from sphere-packing should be multiplied by a substantial factor for deployment planning.

The paper notes that the full-batch InfoNCE loss was chosen because "in preliminary experiments, we found that InfoNCE performed best, beating MSE and Margin" (Section 4), and that "we found similar results with SGD, but we use Adam for speed and similarity with existing training methods." For sigmoid-based loss functions (Appendix C), the paper references concurrent work by Bangachev et al. (2025) suggesting that free-embedding experiments "can be solved in fewer dimensions than in our setting (assuming no margin)," indicating that loss function choice interacts with the effective margin and thus the required dimension. The paper leaves this tension unresolved, noting "we welcome further insight into this question."

LIMIT-Small Results: State-of-the-Art Models Fail on a Trivially Simple Task

Figure 4 and Table 4 present results on LIMIT-small (46 documents, 1035 queries). The headline finding is stark: no single-vector model achieves even 60% Recall@2, despite the task requiring no reasoning, no complex syntax, and no domain knowledge.

At the full (untruncated) embedding dimensions:

• Promptriever Llama3 8B (4096-dim): 54.3% Recall@2, 90.0% Recall@10, 97.7% Recall@20
• GritLM 7B (4096-dim): 38.4% Recall@2, 75.4% Recall@10, 90.5% Recall@20
• Gemini Embed (3072-dim): 33.7% Recall@2, 72.4% Recall@10, 87.9% Recall@20
• E5-Mistral 7B (4096-dim): 29.5% Recall@2, 68.1% Recall@10, 85.2% Recall@20
• Qwen3 Embed (4096-dim): 19.0% Recall@2, 52.3% Recall@10, 73.8% Recall@20
• Snowflake Arctic L (4096-dim): 19.4% Recall@2, 54.9% Recall@10, 76.0% Recall@20

In contrast, the non-single-vector baselines perform substantially better:

• BM25: 97.8% Recall@2, 100.0% Recall@10, 100.0% Recall@20
• GTE-ModernColBERT: 83.5% Recall@2, 97.6% Recall@10, 99.1% Recall@20

The dimension-dependent scaling within each model family reveals a monotonic relationship: for Promptriever, Recall@2 climbs from 6.1% at $d = 32$ to 54.3% at $d = 4096$; for GritLM, from 7.8% to 38.4%; for Gemini Embed, from 6.3% to 33.7%. This is the direct empirical signature of the combinatorial capacity limitation—performance improves with dimension but remains far from saturation even at 4096 dimensions, despite the tiny corpus size (46 documents). The fact that models trained with more diverse instruction data (Promptriever) outperform those with more focused training suggests that broader training "allows them to use more of their embedding space" (Section 5.2), but the improvement is quantitative (roughly 2× over the weakest models) rather than qualitative—no model solves the task.

Interestingly, models trained with MRL (Gemini Embed, Qwen3 Embed, Snowflake Arctic L; marked with stars in Figure 4) do not consistently outperform those without MRL at the full dimension. Promptriever (no MRL) substantially outperforms all MRL-trained models. The paper hypothesizes that "models trained with more diverse instruction, such as Promptriever, perform better, perhaps because their training allows them to use more of their embedding space (compared to models which are trained with MRL and on a smaller range of tasks that can perhaps be consolidated into a smaller embedding manifold)." This is an important nuance: MRL's explicit pressure to perform well at small dimensions may inadvertently compress the embedding manifold, reducing effective capacity even at full dimension.

The gap between Recall@2 and Recall@20 reveals a partial-separation phenomenon: even models with poor Recall@2 (e.g., Qwen3 Embed at 19.0%) achieve substantially higher Recall@20 (73.8%), meaning relevant documents are somewhat distinguished from irrelevant ones—they cluster in the top portion of the ranking—but the model cannot achieve the precise pairwise separation needed to place both relevant documents in the exact top-2 positions. This is consistent with the theoretical picture: approximate separation (relevant documents scoring above most irrelevant ones) requires less capacity than exact pairwise separation for all 1035 queries simultaneously.

LIMIT Full Results: Scaling to 50k Documents Exacerbates the Failure

Figure 3 and Table 5 show results on the full LIMIT (50,000 documents, with 49,954 distractors never relevant to any query). The performance collapse is even more dramatic:

At the full embedding dimensions (Recall@2 / Recall@10 / Recall@100):

• Promptriever Llama3 8B (4096-dim): 3.0% / 6.8% / 18.9%
• GritLM 7B (4096-dim): 2.4% / 4.1% / 12.9%
• Gemini Embed (3072-dim): 1.6% / 3.5% / 10.0%
• E5-Mistral 7B (4096-dim): 1.3% / 2.2% / 8.3%
• Qwen3 Embed (4096-dim): 0.8% / 1.8% / 4.8%
• Snowflake Arctic L (4096-dim): 0.4% / 0.8% / 3.3%

These numbers are near floor—even at Recall@100, no single-vector model retrieves more than 19% of relevant documents. The performance ranking is preserved from the small setting (Promptriever best, followed by GritLM, then Gemini Embed), but the absolute scores are dramatically lower. This is expected: the distractors increase the number of documents the model must push below the relevant ones, requiring the embedding space to simultaneously separate 2 relevant documents from 49,998 irrelevant ones for each of 1035 queries—a much more demanding geometric constraint than separating 2 from 44.

BM25 remains strong: 85.7% Recall@2, 90.4% Recall@10, 93.6% Recall@100. The drop from 97.8% (small version) to 85.7% (full version) in Recall@2 reflects the challenge of adding 49,954 distractors, but BM25's lexical matching still correctly identifies most relevant documents. GTE-ModernColBERT achieves 23.1% Recall@2, 34.6% Recall@10, 54.8% Recall@100—better than any single-vector model but far from BM25 and far from solving the task.

The dimension-dependent scaling in the full setting shows that at small dimensions (32–128), all models achieve near-zero recall—the problem is essentially unsolvable. Performance becomes measurable only above ~256–512 dimensions, and even at 4096, it remains in single digits for Recall@2. This reinforces the theoretical message: for a fixed corpus size, there is a minimum dimension below which the task is completely impossible, and current models operate in a regime where increasing dimension provides diminishing but non-zero returns.

Domain Shift Analysis: The Failure Is Intrinsic, Not Distributional

Figure 5 and Table 3 show the results of fine-tuning modernbert-embed-large on either the synthetic LIMIT training set or directly on the LIMIT test set, with embedding dimensions varied during training by projecting the hidden layer.

Training on the test set (analogous to free-embedding optimization): The model can overfit and achieve high performance. At $d = 1024$, it reaches 96.5% Recall@2, 99.8% Recall@10, and 100.0% Recall@100 on LIMIT-small. Even at $d = 32$, it achieves 85.5% Recall@2—substantially better than any off-the-shelf model at any dimension (the best being Promptriever at 54.3%). The monotonic dimension scaling is clear: from 85.5% at $d = 32$ to 96.5% at $d = 1024$, with most of the gain achieved by $d = 256$ (94.2%).

Training on the training set (in-domain but non-overlapping attributes): Performance is near zero regardless of dimension. At $d = 1024$, the model achieves only 1.0% Recall@2, 2.8% Recall@10, and 11.2% Recall@100—marginally above zero and dramatically worse than test-set training. Even at $d = 32$, training-set performance is 0.0% across all recall cutoffs. There is a very slight upward trend with dimension (0.0% → 1.0% Recall@2, 0.0% → 2.8% Recall@10), but the absolute numbers confirm that in-domain training data does not materially help.

The paper interprets this as definitive evidence that "poor performance is not due to domain shift" (Section 5.2). If the problem were unfamiliar language patterns (attribute-listing documents), training on similar examples would provide substantial improvement. The near-zero training-set performance demonstrates that the model cannot learn to represent the qrel structure from examples alone—the limitation is in the representational capacity of the fixed-dimensional embedding space, not in the training distribution. The test-set training success confirms the free-embedding result: if the model is allowed to memorize the exact query-document pairs (overfitting to the test tokens), it can solve the task, but this corresponds to direct optimization of vectors on the test qrel matrix, not to learning a generalizable mapping from text to relevance.

A notable observation: even with test-set overfitting, the real model at $d = 64$ achieves lower performance than the free-embedding experiments at the same dimension (which solved $n = 46$ at $d \geq$ approximately 19 based on the cubic fit). The paper states that "real models with 64 dimensions still cannot completely solve the task, implying real models perform significantly worse than the bounds shown in §4" (Section 5.2). At $d = 64$, test-set training achieves only 90.4% Recall@2, not 100%, confirming that the LM backbone, tokenization, and gradient-based training with SentenceTransformers impose additional constraints beyond the free-embedding setting.

Synonym Variant: Lexical Models Are Brittle; Single-Vector Models Are More Robust but Still Limited

Figure 6 compares LIMIT-small with LIMIT-small-synonym (all attributes replaced with non-overlapping synonyms). The key numbers (Recall@2):

• BM25: 97.8% → 8.5% (drop of 89.3 percentage points, or −91.3% relative)
• GTE-ModernColBERT: 83.5% → 25.6% (drop of 57.9 percentage points, or −69.3%)
• Promptriever 8B: 54.3% → 14.3% (drop of 40.0 percentage points, or −73.7%)
• GritLM 7B: 38.4% → 15.1% (drop of 23.3 percentage points, or −60.7%)
• E5-Mistral 7B: 29.5% → 11.6% (drop of 17.9 percentage points, or −60.7%)
• Qwen3 Embed: 19.0% → 10.6% (drop of 8.4 percentage points, or −44.2%)
• Snowflake Arctic: 19.4% → 8.5% (drop of 10.9 percentage points, or −56.2%)

The pattern reversal is striking. BM25 goes from best to worst among the reported models. Single-vector models, while still performing poorly in absolute terms, degrade proportionally less: Qwen3 Embed drops by 44.2% relative, while BM25 drops by 91.3%. The paper interprets this as evidence that single-vector models "attempt semantic matching" and therefore partially survive the synonym substitution, while BM25's exact keyword matching is completely defeated. However, no model performs well: the best synonym-variant Recall@2 is GritLM at 15.1%, far below usable thresholds.

GTE-ModernColBERT occupies an intermediate position: it drops substantially (to 25.6%) but remains the best model on the synonym variant, suggesting that its multi-vector representation provides some robustness to synonym substitution while retaining more capacity than single-vector models.

The synonym experiment isolates two dimensions of the limitation. First, it confirms that BM25's success on the original LIMIT is due entirely to lexical overlap—it is not performing any semantic matching. Second, it shows that single-vector models' partial success on the original LIMIT is also partly attributable to lexical cues (since they also degrade on the synonym variant), but they retain some semantic generalization ability that BM25 lacks. This tradeoff—lexical models have high capacity but no semantic generalization; single-vector models have some semantic generalization but low capacity—is the central architectural tension the paper highlights.

Cross-Encoder Results: The Task Is Solvable with Sufficient Architectural Expressivity

Section 5.3 reports that Gemini-2.5-Pro, given all 46 documents and all 1000 queries in a single prompt and asked to output the relevant documents for each query in one generation, achieves 100% accuracy on LIMIT-small. The paper states: "We find that it can successfully solve (100%) all 1000 queries in one forward pass. This is in contrast to even the best embedding models with a recall@2 of less than 60% (Figure 4)."

This result serves as an existence proof: the task is not inherently ambiguous or impossible. A model with sufficient architectural expressivity—in this case, a cross-encoder that can jointly attend over all document-query pairs without compressing them into fixed-dimensional vectors—can represent the relevance structure perfectly. The failure of embedding models is therefore specifically attributable to the single-vector bottleneck, not to the dataset design or task ambiguity.

The paper does not report cross-encoder results on the full LIMIT (50k documents), presumably because the 50k-document context exceeds practical input lengths for a single forward pass, though this is not explicitly stated. The paper also does not evaluate cross-encoders as rerankers on top of first-stage embedding retrieval—the cross-encoder is given all 46 documents directly, not a candidate set—so this result demonstrates solvability in principle rather than a practical deployment architecture.

Ablation Studies and Robustness Checks

Embedding dimension (MRL truncation): Figures 3 and 4 systematically vary the embedding dimension from 32 to the full dimension (1024–4096) for all models, revealing monotonic improvement with dimension for most models (the clearest example being Promptriever, which climbs from 6.1% to 54.3% Recall@2 in the small setting). Models trained with MRL (Gemini Embed, Qwen3 Embed, Snowflake Arctic L) show more graceful degradation at small dimensions but do not necessarily achieve higher performance at full dimension—in fact, the non-MRL Promptriever substantially outperforms all MRL-trained models at full dimension. For models not trained with MRL, truncation "results in sub-par scores" but still shows the dimension-dependence trend. This ablation confirms dimension as the critical capacity parameter and reveals that MRL training may trade off peak capacity for multi-resolution robustness.

Training on LIMIT train vs. test (domain shift check): Training modernbert-embed-large on the synthetic LIMIT training set (non-overlapping attributes) produces near-zero performance (≤1.0% Recall@2 at $d = 1024$), while training on the test set produces 96.5% Recall@2 at $d = 1024$ (Figure 5, Table 3). This rules out domain shift as the explanation for poor off-the-shelf performance: even models explicitly fine-tuned on in-domain examples cannot learn the relevance structure. The paper states this "indicates the issue is not domain shift" but rather that "the task is intrinsically hard" (Section 5.2).

Original vs. synonym attributes (lexical overlap check): The synonym variant of LIMIT-small (Figure 6) tests whether models rely on lexical matching. BM25 drops from 97.8% to 8.5% Recall@2 (−91.3%), confirming its performance is purely lexical. Single-vector models drop proportionally less (e.g., Qwen3 Embed: 19.0% → 10.6%, −44.2%), demonstrating some semantic generalization. GTE-ModernColBERT drops from 83.5% to 25.6% but remains the best model on the synonym variant, suggesting multi-vector representations balance capacity and semantic robustness.

Corpus size: small (46 docs) vs. full (50k docs): Comparing Figures 3 and 4 reveals the effect of adding distractor documents. The 46-document setting is already challenging (best Recall@2: 54.3%), but the 50k-document setting reduces all single-vector models to single-digit Recall@2 (best: 3.0%). BM25 degrades from 97.8% to 85.7%, remaining strong. This confirms that capacity limitations are exacerbated by corpus size—the embedding space must simultaneously push more irrelevant documents below the relevant ones, requiring finer geometric separation.

Model training paradigm (MRL vs. non-MRL, instruction diversity): Comparing Promptriever (non-MRL, instruction-diverse training) to MRL-trained models (Gemini Embed, Qwen3 Embed, Snowflake Arctic L) at full dimension shows Promptriever outperforming by wide margins (54.3% vs. 19.0–33.7% Recall@2 in the small setting). The paper hypothesizes that "models trained with more diverse instruction, such as Promptriever, perform better, perhaps because their training allows them to use more of their embedding space." This is not a controlled ablation (models differ in backbone, training data, and objectives simultaneously), but it raises the hypothesis that MRL's pressure to perform at small dimensions may compress the embedding manifold and reduce effective capacity.

Single-vector vs. multi-vector vs. sparse architecture: The inclusion of GTE-ModernColBERT and BM25 as architectural alternatives (Figures 3, 4, 6) constitutes a structural ablation of the single-vector paradigm. Multi-vector (ColBERT) substantially outperforms single-vector but underperforms sparse (BM25) on the original LIMIT. On the synonym variant, the ranking reverses: ColBERT best, then single-vector, then BM25 worst. This three-way tradeoff is the paper's central architectural argument—no single paradigm dominates.

Graph density and average query strength metrics: Appendix F (Table 2) computes two qrel graph metrics and compares LIMIT to existing datasets. LIMIT's graph density (0.085) is 3.3× higher than the next-highest dataset (FollowIR Core17: 0.026) and orders of magnitude above NQ (0), HotpotQA (0.000037), and SciFact (0.001). LIMIT's average query strength (28.5) is 48× higher than FollowIR Core17 (0.59). The paper states these metrics "suggest (although cannot definitively prove) that datasets with higher values here will be harder for retrieval models to represent" and positions LIMIT as an extreme outlier on the combinatorial density axis.

Loss function (InfoNCE vs. MSE vs. Margin): In the free-embedding experiments (Section 4), the paper notes that "in preliminary experiments, we found that InfoNCE performed best, beating MSE and Margin." This is a pragmatic choice, not a systematic ablation. The paper acknowledges (Appendix C) that concurrent work by Bangachev et al. (2025) found sigmoid loss functions can solve free-embedding experiments in fewer dimensions than InfoNCE (assuming no margin), and notes "we welcome further insight into this question." This is an important caveat: the critical-$n$ values in Figure 2 may be loss-function-specific, not purely geometric.

Critical Assessment

Claim 1: "For a fixed embedding dimension d there will be some set of documents such that certain sets are unattainable as top-k sets." This is the central theoretical claim, and Theorem 1 provides a rigorous proof under the margin condition. However, the theorem proves existence of a bound, not tightness—the actual dimension required in practice is substantially higher, as the free-embedding experiments demonstrate (4.5× multiplier). The claim is therefore supported in principle, but the paper's numerical instantiations (Table 1) should be understood as lower bounds, not precise predictions of where real models will fail. The claim holds for any $\gamma > 0$; a model operating with effectively $\gamma \approx 0$ (infinite precision) would evade the bound, which is why the margin is the crucial conceptual bridge to practice. The paper's empirical choice of $\gamma = 0.1$ is described as "approximately standard" but no citation or measurement is provided to support this—it is an expert estimate, not an empirical determination. A more rigorous approach would measure the effective margin of deployed models (e.g., the average score gap between relevant and irrelevant documents on standard benchmarks) and use that to calibrate the bound. Without this calibration, the exact numerical predictions (e.g., $d \geq 425$ for $n = 10^6$, $k = 10$) are illustrative rather than prescriptive.

Claim 2: "State-of-the-art embedding models fail dramatically on the LIMIT dataset despite the simple nature of the task." Strongly supported by Figures 3 and 4. The best single-vector model (Promptriever) achieves only 54.3% Recall@2 on the 46-document version and 3.0% on the 50k version—failure by any reasonable standard. The domain-shift experiment (Figure 5) robustly demonstrates this is not a training distribution issue. The synonym experiment (Figure 6) shows the limitation persists even when lexical overlap is removed. However, the paper evaluates only 6 single-vector models, all from the 7B–8B parameter class with similar backbone architectures (decoder-only LMs fine-tuned for embedding). A broader evaluation including encoder-only models (e.g., BGE, Stella), models at different scales (e.g., 0.3B, 1.5B, 30B+), and models with fundamentally different training objectives (e.g., generative retrievers, ColBERT-style late interaction at larger scales) would strengthen the claim that this is a universal failure of single-vector architectures rather than a failure of a particular training paradigm. The paper's argument would be more convincing if it included a model that is explicitly designed for high-dimensional semantic structure (e.g., models trained with very high-dimensional embeddings, or models using multiple embeddings per document).

Claim 3: "The free-embedding experiments show that the bound holds empirically even under best-case optimization." Supported with qualifications. The cubic fit ($r^2 = 0.999$) is excellent, and the extrapolation to practical dimensions provides concrete (if approximate) capacity estimates. However, several aspects weaken this claim:

• The experiments use only $k = 2$ and the InfoNCE loss with a particular temperature. Appendix C acknowledges that sigmoid loss functions may achieve different critical-$n$ values. The claim that these results represent the "best case" is therefore loss-function-conditional—there may exist loss functions that pack more combinatorial configurations into the same dimension.
• The experiments terminate at $d = 45$ due to the combinatorial explosion in $\binom{n}{2}$ queries (at $n = 626$, this is 195,625 queries, each requiring full-batch computation against all documents). The cubic fit extrapolates far beyond the measured range: from $d = 45$ to $d = 4096$, a factor of ~90×. The $r^2$ on the measured range does not guarantee accuracy of this extrapolation; the true relationship may deviate from cubic at higher dimensions.
• The experiments use random initialization and a particular optimizer (Adam). The paper does not report whether results are consistent across random seeds, so the reported critical-$n$ values may have unreported variance.
• The paper does not compare the experimental critical-$n$ to the theoretical bound quantitatively (e.g., fitting a multiplier and showing it is stable across $d$). The 4.5× figure is based on a single point ($n = 100$), and the multiplier may itself depend on $n$ or $d$.

Claim 4: "Embedding dimension is the limiting factor, as demonstrated by monotonic improvement with dimension." Broadly supported by the dimension-sweep results in Figures 3 and 4, where most models show monotonic improvement with increasing dimension. However, there are exceptions: some models plateau or show non-monotonicity (e.g., Snowflake Arctic L is flat at 19.4% for dimensions 1024–4096; E5-Mistral shows a slight decline from 29.9% to 29.5% from 3072 to 4096). These plateaus suggest that beyond a certain point, dimension is not the bottleneck for those specific models—other factors (training data, objective, backbone capacity) become limiting. The paper does not explore why some models plateau while others continue improving, which would provide insight into what non-dimensional factors affect combinatorial capacity.

Missing experiments that would strengthen the paper:

• Varying $k$: All LIMIT experiments use $k = 2$. Showing that performance degrades with increasing $k$ (at fixed $n$) would provide a direct test of the $\binom{n}{k}$ dependence in Theorem 1. The free-embedding experiments with $k = 3, 5, 10$ would allow fitting empirical scaling laws in both $n$ and $k$.
• Varying $n$ continuously: The paper evaluates only at $n = 46$ and $n = 50,000$. A sweep of intermediate corpus sizes (e.g., 100, 500, 1000, 5000, 10000 documents) would show how performance degrades as the combinatorial demand increases, producing empirical capacity curves that could be compared to the theoretical bound.
• Varying margin $\gamma$: The theoretical bound depends on $\gamma$, but the paper never measures or varies it empirically. Evaluating models at different temperature values (which affect the effective margin in InfoNCE) or directly measuring the score gap distribution on LIMIT would connect the theoretical parameter to observables.
• Bi-encoder with larger dimension: Evaluating a model specifically trained with very high-dimensional embeddings (e.g., 8192 or 16384 dimensions) would test whether dimension scaling alone can solve the problem or whether other constraints (backbone capacity, training dynamics) dominate.
• Reranking pipeline: The paper evaluates cross-encoders as standalone solvers but does not evaluate the standard production architecture: embedding model for first-stage retrieval (e.g., retrieve top-100) followed by cross-encoder reranking. This combination is how most deployed systems handle capacity limitations in practice, and evaluating it on LIMIT would connect the theoretical analysis to practical mitigation strategies.
• Statistical significance: No confidence intervals or error bars are reported for any experimental results. With 1035 queries, the standard error on a proportion near 50% is approximately 1.5 percentage points. Differences of 1–2 percentage points between models at similar dimensions may not be statistically reliable.

Conditional nature of claims: The claim that embedding models have a "fundamental limitation" is conditional on the requirement that models must realize all possible top-$k$ subsets with a fixed margin. Real-world retrieval does not require this—users do not uniformly query all $\binom{n}{k}$ combinations, and relevance patterns in natural data are highly structured (documents cluster by topic, queries target specific clusters). The LIMIT dataset constructs a worst-case qrel matrix with maximum combinatorial density, which may be extremely unlikely to occur in natural retrieval tasks. The paper's Appendix F metrics show LIMIT is an extreme outlier on graph density, and the paper does not demonstrate that any real-world retrieval benchmark approaches this density. The limitation is therefore fundamental in the worst case but may not be binding in practice if natural retrieval distributions occupy a low-combinatorial-density region of the space. The paper acknowledges this implicitly by noting that "academic benchmarks test only a small amount of the queries that could be issued" and that instruction-following retrieval is moving toward more combinatorial query spaces, but it does not quantify how close current or near-future benchmarks are to the capacity ceiling. This gap—between worst-case impossibility and typical-case feasibility—is the central open question the paper leaves unanswered.

6. Limitations and Trade-offs

The Difficulty Estimation Overhead Is Prohibitive in Practice

The theoretical bound (Theorem 1) and the LIMIT dataset demonstrate that there exists a combinatorial ceiling on what single-vector embeddings can represent, but the paper does not provide a method for determining, for an arbitrary corpus and query distribution, whether that ceiling is actually binding. This is the practical deployment question: given my corpus of $n$ documents, my embedding dimension $d$, and the types of queries my users issue, am I in the regime where the limitation matters?

The paper acknowledges this gap implicitly throughout. Section 3.0.1 states that the theoretical bounds "are already greater than those currently used for web-scale search" and that "even a small multiple of this lower bound would make the embedding dimension requirement infeasible," but this is a statement about worst-case realizability (all $\binom{n}{k}$ subsets), not about whether typical query distributions in deployed systems approach this worst case. The free-embedding experiments (Section 4) provide critical-$n$ values for the all-combinations setting, but real retrieval corpora do not distribute queries uniformly over all $\binom{n}{k}$ subsets—queries cluster around topics, relevance patterns are structured, and document embeddings exhibit low intrinsic dimension. The paper's own metrics in Appendix F (Table 2) show that LIMIT's qrel graph density (0.085) and average query strength (28.5) are orders of magnitude above standard datasets (NQ: 0 and 0; HotpotQA: 0.000037 and 0.11; FollowIR Core17: 0.026 and 0.59), confirming that LIMIT represents an extreme outlier on the combinatorial density axis.

The consequence is that a practitioner cannot look at the paper's numbers and determine whether their specific deployment is safe. The theoretical bound provides a necessary condition for realizability of all subsets, but real deployments need a sufficient condition for realizability of their query distribution—a much weaker requirement that the paper does not characterize. The free-embedding critical-$n$ values (e.g., 250M documents at $d = 4096$ for all top-2 combinations) sound alarming for web-scale search, but if the actual query distribution requires realizing only a tiny fraction of $\binom{n}{2}$ combinations—say, a few million highly structured query patterns—the effective capacity requirement could be orders of magnitude smaller. The paper never measures the typical combinatorial density of real retrieval workloads, nor does it provide tools for practitioners to do so. The graph density and average query strength metrics in Appendix F are a step in this direction, but they are presented as descriptive comparisons rather than as diagnostic tools with calibrated thresholds. A practitioner looking at their own qrel matrix's graph density of, say, 0.01 would not know whether this is "safe" or "dangerous" based on the paper's analysis.

The paper partially mitigates this by noting that instruction-following and reasoning-based retrieval are moving toward higher combinatorial density—"this has pushed the focus of embedding models from basic keyword matching to embeddings that can represent the full semantic meaning of language" (Section 2.2)—but this is an argument about trend direction, not about current proximity to the ceiling. Section 5.3 suggests alternative architectures (cross-encoders, multi-vector, sparse) as potential solutions, but does not provide a framework for deciding when to switch architectures. The paper identifies the limitation's existence but leaves the deployment-relevant question—"am I hitting it?"—unanswered.

The Paper Evaluates a Single Retrieval Depth ($k = 2$) and a Narrow Difficulty Range

All LIMIT experiments, and all free-embedding experiments, use exactly $k = 2$ relevant documents per query. The paper justifies this as "both for simplicity in instantiating and to mirror previous work (i.e. NQ, HotpotQA, etc.)" (Section 5.2). While this choice is reasonable for an initial benchmark, it restricts the empirical evidence to a single point on the $(n, k)$ plane, leaving the scaling behavior in $k$—which Theorem 1 predicts should be super-linear—entirely uncharacterized empirically.

Theorem 1's bound depends on $\log\binom{n}{k}$, which for $n \gg k$ grows roughly as $k \log(en/k)$. This means increasing $k$ from 2 to 10 should increase the required dimension by a factor of approximately 5 for large $n$. But the paper provides no empirical validation of this prediction. The free-embedding experiments (Section 4, Figure 2) only sweep $n$ at fixed $k = 2$; the LIMIT dataset only constructs queries with exactly two relevant documents; the model evaluations (Figures 3, 4) only report Recall@$k$ for fixed $k = 2$ in the relevance set. This means the paper cannot answer questions like: at what $k$ does a model with $d = 1024$ start failing on the 46-document setting? Does the dimension-dependence curve in Figure 4 shift as $k$ increases, and if so, how? Is the critical-$n$ scaling in Figure 2 consistent with the $\log\binom{n}{k}$ dependence for $k > 2$?

The consequence is that the paper's headline claim—"for a fixed embedding dimension $d$ there will be some set of documents such that certain sets are unattainable as top-$k$ sets"—is demonstrated only for $k = 2$, the smallest nontrivial retrieval depth. For $k = 1$, the problem reduces to nearest-neighbor classification, which is known to be realizable in $d = 1$ dimension. For $k = 100$, the combinatorial demand grows dramatically, but the paper provides no evidence about where practical models fail. The paper's Table 1 extrapolates the theoretical bound to larger $k$ (e.g., $d \geq 425$ for $n = 10^6$, $k = 10$), but these are purely theoretical numbers with no corresponding free-embedding or LIMIT-style validation. Given that the free-embedding experiments already show a 4.5× multiplier over the theoretical bound for $k = 2$, the $k = 10$ practical requirements could be substantially larger than Table 1 suggests, but no data exists to calibrate this.

There is no mitigation attempted. The paper does not discuss varying $k$ as future work, nor does it acknowledge that the $k = 2$ restriction limits the generality of the empirical conclusions. The LIMIT dataset construction explicitly chooses $k = 2$ and does not provide a recipe or code for generating datasets with different $k$, making it difficult for subsequent work to fill this gap without reimplementing the entire pipeline.

The Reported Gains Are Worst-Case; Typical-Case Capacity May Be Higher

The theoretical analysis (Theorem 1) and the LIMIT dataset construction both assume the most adversarial possible distribution of queries: every $k$-subset of documents must be simultaneously realizable as a top-$k$ retrieval result. This worst-case assumption is methodologically clean—it provides an unambiguous lower bound—but it is also maximally pessimistic. Real retrieval tasks almost never require all $\binom{n}{k}$ combinations. Queries are not uniformly distributed over the power set of documents; they cluster in semantic regions, and documents that are never jointly relevant to any natural query effectively require no joint separation in the embedding space.

The paper acknowledges this implicitly when it notes that "existing retrieval datasets typically use a static evaluation set with limited numbers of queries, as relevance annotation is expensive to do for each query" and that "the 3k queries in QUEST can only cover an infinitesimally small part of the qrel combination space" (Section 5.1). But it interprets this as a deficiency of existing evaluation—a sampling problem that hides the true difficulty—rather than as evidence that natural retrieval distributions may be intrinsically low-combinatorial-density. The paper argues that "with the rise of search agents, we see greater usage of hyper-specific queries" and that "it is possible to sub-select any top-k relevant set with the right operators if the documents are sufficiently expressive" (Section 5.1), implying that instruction-following retrieval will eventually explore the full combinatorial space. But this is a speculative claim about future query distributions, not an empirical demonstration about current ones.

The consequence is that the paper's strongest claim—that single-vector models have a "fundamental limitation" that makes them "categorically insufficient for the retrieval demands the field is moving toward"—may overstate the practical severity of the bound. If natural query distributions (even with instruction-following) only ever require realizing a structured subset of top-$k$ combinations—for example, those corresponding to coherent semantic categories rather than arbitrary set intersections—then the effective capacity requirement is substantially lower than the worst-case bound. The embedding space can reuse its representational budget: documents that are never jointly queried don't require mutually consistent separation, and the geometric constraints are far looser. The paper provides no characterization of the "typical-case" capacity—how many top-$k$ subsets can be realized when the subsets are drawn from a realistic distribution rather than exhaustively enumerated—and therefore cannot distinguish between "single-vector models will fail on some adversarial queries" (true and proven) and "single-vector models will fail on typical instruction-following queries at scale" (unproven).

There is no direct mitigation. The paper's Appendix F (Table 2) provides comparative graph density metrics showing LIMIT is an extreme outlier, which implicitly acknowledges the gap, but the text does not discuss typical-case capacity or propose methods to estimate it. Section 2.3 mentions that "the number of such regions is equal to the number of unique retrieval sets of size $k$, however this quantity is notoriously difficult to bound tightly," indicating that even theoretical characterization of non-worst-case settings is challenging—but the paper does not attempt to address this.

The Paper Does Not Measure or Vary the Margin $\gamma$, Leaving the Theory–Practice Bridge Incomplete

The theoretical bound (Theorem 1) is parameterized by the score margin $\gamma$, which controls the required separation between relevant and irrelevant documents. The paper states that $\gamma = 0.1$ (score gap $2\gamma = 0.2$) is "approximately standard for models based on empirical usage" (Section 3.0.1), but provides no measurement, no citation, and no sensitivity analysis to support this value. The margin is the crucial parameter that connects the geometric theory to practical model behavior: a model that achieves clean separation with $\gamma = 0.01$ requires far more dimension than one that can operate with $\gamma = 0.001$. The entire numerical instantiation of Theorem 1 (Table 1) and the claim that "these bounds are already larger than what is used in practice" depend on the choice of $\gamma$.

The paper never empirically measures the effective margin of deployed models. What is the distribution of score gaps between the lowest-scoring relevant document and the highest-scoring irrelevant document on standard benchmarks? How does this gap change with corpus size, embedding dimension, and model architecture? Does the empirical margin correspond to $\gamma = 0.1$, or is it substantially smaller (which would make the theoretical bound less binding) or larger (which would make it more binding)? Without this measurement, the numerical predictions in Table 1 are uncalibrated. The paper uses $\gamma = 0.1$ because it yields the specific denominator $\log(1 + 1/0.1) = \log(11) \approx 2.398$, producing clean numerical examples, but this is an illustrative choice, not an empirical determination.

The free-embedding experiments (Section 4) implicitly encode a particular effective margin through the choice of InfoNCE loss and its temperature parameter. The paper notes (Appendix C) that "in concurrent work by Bangachev et al. (2025), they show that for vision-language embedding models like CLIP (that more commonly use sigmoid loss functions) that the free-embedding experiments can be solved in fewer dimensions than in our setting (assuming no margin)." This directly implicates the loss function and its implicit margin in determining the practical capacity, but the paper does not systematically vary the loss function or its temperature in the free-embedding experiments to quantify this effect. The critical-$n$ values in Figure 2 may be specific to InfoNCE with a particular temperature, and different training objectives could shift the curve significantly—potentially making the capacity ceiling either more or less restrictive than the paper reports.

The consequence is that a key claim—that practical models "already exceed what even the largest embedding dimensions can represent"—rests on an unvalidated parameter. If deployed models operate with an effective $\gamma$ substantially smaller than 0.1 (e.g., because they tolerate some ranking inversions or because approximate nearest neighbor indices smooth over small score differences), the theoretical bound would predict much larger feasible corpus sizes, potentially moving the ceiling beyond current deployment scales. Conversely, if the effective $\gamma$ is larger (e.g., because quantization or model miscalibration demands wider score gaps), the ceiling would be lower than Table 1 indicates. Without measuring $\gamma$, the paper cannot distinguish between these scenarios.

The paper does not mitigate this limitation. It notes in Section 3.0.1 that "a stricter margin requirement (larger $\gamma$) demands higher dimension, since $\log(1 + 1/\gamma)$ decreases with $\gamma$," but does not discuss uncertainty in the $\gamma = 0.1$ estimate or suggest methods for measuring the effective margin of a deployed model. The paper's argument that "even a small multiple of this lower bound would make the embedding dimension requirement infeasible" acknowledges the uncertainty but does not resolve it.

Only One Dataset Construction Strategy Is Explored; Alternate Mappings Could Be Easier or Harder

The LIMIT dataset instantiates combinatorial saturation through a specific mapping: latent attributes (e.g., "likes Apples") are assigned to documents, and queries ask for documents possessing a specific attribute. This is described as "just one way, designed to be realistic and simple" and the paper notes that "our framework allows for any way of instantiation—not stuck to this arbitrary natural language design" (Section 5.2). However, the paper evaluates only this single instantiation strategy, leaving open the question of how sensitive the empirical results are to the choice of mapping from the abstract qrel matrix to natural language text.

Different instantiations of the same abstract combinatorial structure could produce different empirical difficulty for embedding models. The attribute-listing format produces documents that are long lists of semantically unrelated concepts ("Jon Durben likes Quokkas and Apples"), which may be an unusual text distribution for models trained primarily on natural prose. This could interact with the embedding model's representational capacity in ways that amplify or suppress the combinatorial limitation: if the model struggles to encode list-structured text efficiently in its embedding space, the effective capacity for representing the qrel structure may be lower than for a more natural mapping. Conversely, a mapping that produces more coherent documents (e.g., short biographies that indirectly imply the attributes) might allow the model to leverage linguistic structure to compress the qrel information, potentially achieving higher effective capacity.

The domain-shift experiment (Figure 5) partially addresses this by showing that training on in-domain attribute-listing examples does not materially improve performance—suggesting the text format itself is not the primary bottleneck. But this experiment uses the same attribute-listing format for both training and evaluation, so it tests format familiarity, not whether a different text format would change the fundamental capacity requirements. The paper does not create an alternative instantiation of the same qrel matrix (e.g., using natural sentences like "Jon enjoys spending time with quokkas and eating apples" instead of lists) and test whether performance differs. The synonym experiment (Figure 6) varies the attribute vocabulary but preserves the list structure, so it doesn't address the mapping format question.

The consequence is that the paper's claim that LIMIT is "realistic" (Section 5.2) is asserted rather than validated against alternative realizations. A skeptical practitioner could argue that the specific mapping chosen exaggerates the difficulty by producing unnatural text that embedding models weren't designed to handle, and that a more natural mapping of the same abstract qrel structure might be substantially easier. Without comparing at least two different surface realizations of the same underlying combinatorial structure, the paper cannot definitively attribute the failure to combinatorial capacity rather than to an interaction between combinatorial demand and text format.

The paper does not attempt to mitigate this directly, though the domain-shift experiment (Figure 5) provides circumstantial evidence that format isn't the dominant factor. The paper's invitation to explore "any way of instantiation" (Section 5.2) implicitly acknowledges the limitation and invites future work to test alternative mappings.

The Paper Evaluates Only 7B–8B Decoder-Only Models Fine-Tuned for Embedding; Architectural Generality Is Unproven

The six single-vector models evaluated on LIMIT (Section 5.2) share a common lineage: they are all decoder-only language models in the 7B–8B parameter range (Mistral-7B, Llama-3-8B, or similar), fine-tuned specifically for embedding via contrastive learning. This is a representative sample of the current state-of-the-art as measured by MTEB, but it is not a comprehensive survey of single-vector architectures. Several important categories are absent:

Encoder-only models (BERT-family): Models like BGE-base/large, Stella, or all-MiniLM, which use bidirectional attention and are trained primarily for sentence embeddings, may exhibit different capacity scaling due to their different inductive biases. Encoder-only models typically produce more structured embedding spaces due to their bidirectional context and masked language modeling pretraining. Whether this translates to higher or lower combinatorial capacity on LIMIT is unknown.

Models at different scales: Smaller models (0.3B, 1.5B) might fail harder on LIMIT, providing a clearer dimension-dependence signal. Larger models (30B, 70B) might have higher effective capacity even at the same embedding dimension, if their stronger language understanding allows more efficient use of the available dimensions. The paper's finding that Promptriever (Llama-3-8B) substantially outperforms other 7B models suggests model capacity matters beyond raw embedding dimension, but the paper doesn't disentangle backbone size, training data, and training paradigm.

Models with very high embedding dimensions: The maximum dimension evaluated is 4096 (Qwen3 Embed, Promptriever, GritLM, E5-Mistral, Arctic). Models specifically trained with higher-dimensional embeddings (e.g., 8192 or 16384) could push the empirical capacity ceiling further and reveal whether the dimension-dependence curve continues monotonically or plateaus.

The paper states that it "believe[s] this model is representative of the capabilities of many contemporary LLMs" (Section 4, regarding PaLM 2-S* in the related context), and the LIMIT evaluation covers "state-of-the-art embedding models" (Section 5.2), but this is a convenience sample rather than a principled stratification of the architecture space. The failure of six related models on LIMIT provides strong evidence that current widely-used decoder-only embedding models have limited combinatorial capacity, but weaker evidence that single-vector embeddings in general are fundamentally bounded in a way that no training paradigm or architecture within the single-vector framework can overcome. A hypothetical encoder-only model trained with a specialized objective designed to maximize combinatorial capacity might perform substantially better, and the paper provides no test to rule this out.

The consequence is that the paper's architectural argument—that the community should move toward cross-encoders, multi-vector, sparse, or hybrid approaches (Section 5.3)—rests on the assumption that the observed failure is intrinsic to single-vector representations rather than to the specific training recipes of current models. If a differently-trained single-vector model could solve LIMIT, the argument for abandoning single-vector architectures weakens considerably: the problem would be training methodology, not geometric capacity. The paper does not attempt to train such a model (beyond the fine-tuning experiment in Figure 5, which shows even test-set overfitting doesn't achieve 100% at $d = 1024$ for the ModernBERT backbone, but only reaches 96.5% Recall@2, and doesn't explore higher dimensions for this backbone).

The paper partially mitigates this through the free-embedding experiments (Section 4), which show that even vectors directly optimized on the test qrel matrix require dimension proportional to the combinatorial demand. Since the free-embedding setting is strictly more powerful than any learned model (no tokenization, no generalization, direct gradient access to the target), it establishes a ceiling that applies to all single-vector architectures. However, the critical-$n$ values from free embeddings (e.g., $n \approx 100$ for $d = 18$, extrapolated to $n \approx 4M$ for $d = 1024$) suggest that the 46-document LIMIT should be easily solvable at $d = 1024$ in the free-embedding setting (critical-$n$ would be far above 46), yet the fine-tuned model in Figure 5 achieves only 96.5% Recall@2 at $d = 1024$. This gap confirms that real models are far from the free-embedding upper bound, but the paper does not analyze why—whether it's tokenization, the LM backbone's representational limits, the training procedure, or some other factor—and therefore cannot predict whether improved training within the single-vector paradigm could close this gap.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper introduces a hard geometric ceiling into a field that has been operating under an implicit assumption of unlimited scalability. The shift is from treating embedding-based retrieval failures as optimization problems—insufficient data, suboptimal loss functions, models too small—to recognizing them as in-principle impossibility results for any fixed-dimensional vector representation. This is not an incremental refinement of existing scaling trends; it is a reframing of the research program's fundamental assumptions. Before this work, the community's response to harder retrieval tasks (instruction-following, reasoning, multi-modal) was to scale up: larger backbones, more training data, higher embedding dimensions. The paper demonstrates that this trajectory has a known, provable endpoint—and that for web-scale corpora with combinatorially dense query distributions, that endpoint may already be within reach.

The magnitude of the shift is substantial but bounded. The paper does not show that single-vector embeddings are obsolete or that current models are failing in deployment. It shows that the architecture has a capacity limit—a maximum number of distinct retrieval configurations representable at a given dimension—and that this limit can be saturated by constructing a maximally interconnected qrel matrix. The LIMIT dataset is proof by existence: there exists at least one retrieval task, expressible in trivially simple natural language, that state-of-the-art embedding models cannot solve. The theoretical bound (Theorem 1) generalizes this from "this particular task" to "any task requiring more than $\gamma^{-d}$ distinct top-k subsets," establishing that the limitation is architectural rather than incidental.

This reconciles several tensions in the literature. The apparent contradiction between the success of dense retrievers on standard benchmarks (MTEB, BEIR) and their struggles on instruction-following and reasoning benchmarks (BRIGHT, QUEST, FollowIR) is explained not by insufficient training but by combinatorial density. Standard benchmarks sample an infinitesimal fraction of possible query-document relevance patterns (Section 5.1: QUEST's 3,357 queries cover $7.1 \times 10^{91}$ possible top-20 subsets), ensuring that even models near their capacity ceiling can find adequate approximate solutions. Instruction-following benchmarks, by expanding the space of possible relevance definitions, increase the number of distinct retrieval configurations models must realize, pushing them closer to—or past—their geometric limits. The paper's Appendix F formalizes this: LIMIT's graph density (0.085) and average query strength (28.5) are orders of magnitude above existing datasets, and performance degrades correspondingly.

The paper also resolves the tension between empirical observations that "smaller embeddings have more false positives" (Reimers & Gurevych, 2020) and the community's response of simply increasing dimension. The theoretical bound shows that dimension scaling provides only logarithmic relief in $n$ while the combinatorial demand grows polynomially—increasing $d$ from 768 to 4096 buys at most a factor of $(1 + 1/\gamma)^{4096 - 768} \approx 11^{3328}$ in representable subsets for $\gamma = 0.1$, which sounds enormous but is swamped by the combinatorial growth of $\binom{n}{k}$ for large $n$. The paper's own free-embedding extrapolation (critical-$n$ of ~250M for $d = 4096$ with all top-2 combinations) shows that even the largest current dimensions are marginal for web-scale deployment.

The research directions that become more attractive are those that transcend the single-vector bottleneck: cross-encoder architectures (which the paper shows solve LIMIT perfectly on the small setting), multi-vector representations (ColBERT's 83.5% Recall@2 on LIMIT-small vs. the best single-vector's 54.3%), sparse or hybrid sparse-dense models, and fundamentally new similarity functions that are not restricted to dot products in $\mathbb{R}^d$. The research directions that become less attractive are those that attempt to squeeze more representational capacity out of single-vector architectures through better training alone—the paper's domain-shift experiment (Figure 5) demonstrates that in-domain training provides negligible improvement, and the free-embedding experiments show that even idealized optimization hits the geometric ceiling. Scaling embedding dimensions further (to 8192, 16384) provides only polynomial relief against a combinatorial problem, making it an arms race with diminishing returns. The paper positions verifier/model quality improvement and loss function design as still valuable but bounded in what they can achieve within the single-vector paradigm.

Perhaps most importantly, the paper introduces a new evaluation philosophy for retrieval benchmarks. The existing paradigm—collect a static set of query-document pairs and measure recall—is shown to be fundamentally incapable of detecting capacity limitations, because any fixed evaluation set covers only a microscopic fraction of the combinatorial space. The LIMIT methodology—construct a corpus and query set that saturates the capacity bound for a small, tractable $n$, then measure whether models can achieve the theoretically possible performance—provides a diagnostic that directly probes geometric limitations rather than linguistic ones. This reframes benchmark design from "collect realistic queries" to "construct queries that stress the architecture's known failure modes," complementing existing benchmarks rather than replacing them.

Follow-Up Research This Work Enables

Measuring the effective margin $\gamma$ of deployed models to calibrate the theoretical bound. The paper's Theorem 1 is parameterized by $\gamma$, which the paper sets to 0.1 as an "approximately standard" value without measurement. A direct empirical calibration would: (1) take a deployed embedding model on a standard benchmark, (2) for each query, compute the score gap between the lowest-scoring relevant document and the highest-scoring irrelevant document (the empirical analog of the $2\gamma$ gap in equation 1), (3) fit a distribution to these gaps, and (4) use the lower percentiles (e.g., 5th or 10th percentile gap) as the effective $\gamma$ that the model needs to maintain for robust ranking. This would transform Theorem 1 from an illustrative bound into a calibrated predictive tool: for a given model's effective $\gamma$, what corpus size $n$ and retrieval depth $k$ saturate dimension $d$? The experiment would also reveal whether $\gamma$ varies systematically with corpus size (likely increasing as more distractors demand finer separation), model architecture (cross-encoder vs. bi-encoder), or training paradigm (InfoNCE vs. sigmoid loss). The paper's free-embedding experiments already provide the methodology for testing whether the calibrated bound predicts actual failure points—compare the empirically measured critical-$n$ to the bound using the measured $\gamma$.

Varying $k$ systematically in both free-embedding and LIMIT experiments to validate the $\binom{n}{k}$ dependence. The paper's entire empirical analysis fixes $k = 2$, but Theorem 1 predicts the required dimension scales as $\log\binom{n}{k} \approx k \log(en/k)$. A direct test would replicate the free-embedding critical-$n$ experiments (Section 4, Figure 2) for $k = 3, 5, 10$ and compare the empirical scaling to the theoretical prediction. If the critical-$n$ for $k = 10$ at $d = 100$ follows the $k \log(en/k)$ scaling, this validates the theorem's structural dependence; if it deviates (e.g., the effective multiplier over theory increases with $k$), this reveals additional constraints from gradient-based optimization. A parallel LIMIT-style dataset for, say, $k = 5$ with $n = 15$ (giving $\binom{15}{5} = 3003$ queries, a tractable evaluation size) would test whether the failure patterns observed at $k = 2$ generalize. The paper's attribute-assignment framework (Section 5.2) generalizes naturally: each query is assigned a unique attribute, and each attribute is assigned to exactly $k$ documents, with the assignment covering all $\binom{n}{k}$ combinations. The construction cost is the combinatorial explosion in queries—$\binom{n}{k}$ grows rapidly—but for small $n$ this is manageable.

Characterizing the typical-case capacity gap: how many top-$k$ subsets can be realized when queries follow realistic distributions? The paper's analysis is worst-case: all $\binom{n}{k}$ subsets must be realizable. Real retrieval distributions are highly structured—documents cluster by topic, queries target specific clusters, and the effective number of distinct retrieval configurations is far smaller than the combinatorial maximum. A strong follow-up would: (1) measure the number of actually realized top-$k$ subsets in existing benchmarks (by embedding all documents, issuing all test queries, and counting distinct retrieval result sets), (2) compare this to the theoretical capacity $\gamma^{-d}$ for the models' embedding dimensions, and (3) determine how much headroom remains before hitting the ceiling. This would require access to model embeddings and a systematic sweep of query variations (not just the provided test queries), potentially using synthetic query generation to explore the neighborhood of existing queries. The paper's graph density and average query strength metrics (Appendix F, Table 2) are a starting point but don't directly measure realizability—they measure qrel structure, not whether that structure is geometrically feasible. The critical question is: at current benchmark scales and query distributions, are we operating at 1%, 10%, or 90% of the theoretical capacity ceiling? The answer determines whether the limitation is an immediate concern or a distant horizon.

Training a single-vector model specifically to maximize combinatorial capacity and testing whether it solves LIMIT. The paper evaluates off-the-shelf models trained for general retrieval performance, not for maximizing the number of realizable top-$k$ configurations. A targeted experiment would: (1) take a strong embedding backbone (e.g., a 7B-parameter decoder-only LM), (2) construct a training dataset designed to expand representational capacity—perhaps by generating synthetic queries that systematically connect previously unrelated documents (using logical operators as in QUEST, or by randomly pairing documents and creating queries that are exclusively relevant to those pairs), (3) train with a loss function that explicitly encourages large margins between relevant and irrelevant documents (e.g., a margin-based triplet loss with a high margin parameter), and (4) evaluate on LIMIT. If a capacity-optimized model significantly outperforms Promptriever (54.3% Recall@2 on LIMIT-small) and approaches the free-embedding critical-$n$ predictions (which suggest $n = 46$ should be easily solvable at $d = 1024$), this would demonstrate that the limitation is partly training-methodology-dependent rather than purely geometric. If even a capacity-optimized model fails, this strengthens the case that the ceiling is architectural and that alternative paradigms are necessary. The experiment would also illuminate whether MRL training (which the paper hypothesizes compresses the embedding manifold and reduces peak capacity) is indeed harmful for combinatorial tasks, by comparing MRL-trained and non-MRL-trained versions of the same backbone on LIMIT.

Developing and evaluating hybrid architectures that combine single-vector first-stage retrieval with capacity-expanding components. The paper's architectural comparisons (Figures 3, 4, 6) reveal a three-way tradeoff with no dominant paradigm: BM25 (high capacity, no semantic generalization), single-vector (some semantic generalization, low capacity), multi-vector (intermediate on both axes). A natural follow-up is to evaluate pipelines that combine these: (1) single-vector retrieval to get a candidate set, followed by a multi-vector (ColBERT) reranker on the top-$K$ candidates—does the multi-vector stage recover the combinations the single-vector stage missed? (2) Sparse (BM25) first-stage retrieval followed by single-vector reranking—does the high-recall lexical stage provide a candidate set that the semantic model can then refine, avoiding the combinatorial bottleneck? (3) Hybrid single-vector + sparse representations where the final score is a weighted combination of dense and sparse similarities—does this effectively increase the representational dimension? The LIMIT dataset is ideal for these experiments because the combinatorial structure is known and controllable: one can vary the fraction of queries that require novel document pairings vs. those that cluster in obvious semantic groups, and measure how different pipeline architectures handle the transition. The paper already provides the single-vector and BM25 baselines; extending to pipelined architectures with the same metrics (Recall@2, @10, @20 on LIMIT-small and full) would directly quantify the capacity gains from hybridization.

Extending the LIMIT methodology to other modalities (vision, code, multi-modal) to test generality of the dimension bound. The paper's theoretical analysis (Theorem 1) is modality-agnostic—it applies to any retrieval task where items are represented as unit vectors in $\mathbb{R}^d$ and relevance is scored by dot product. The LIMIT dataset is text-only, but the construction logic (assign latent attributes to items, generate all $\binom{n}{k}$ queries, instantiate in natural language) generalizes directly to other modalities: for vision, attributes could be visual features (e.g., "contains a red object," "has a dog") and documents/images could be synthetic compositions; for code, attributes could be algorithmic properties (e.g., "uses recursion," "has O(n log n) complexity") and documents could be code snippets. A multi-modal LIMIT (e.g., images paired with text descriptions, where the latent attributes are shared across modalities) would test whether multi-modal embedding models (like CoPali or DSE) face the same capacity ceiling and whether cross-modal interactions provide additional representational capacity (e.g., a visual feature that is hard to express in text might be easier to encode in the image embedding, effectively increasing the usable dimension). The paper's text-only scope is acknowledged as a limitation, and extending to other modalities would test the claim that "as the space of things to represent grows (through instructions or multi-modality) they will increasingly run into these theoretical limitations" (Section 2.1).

Practical Applications and Downstream Use Cases

Benchmark auditing and capacity-aware evaluation for retrieval model selection. Organizations evaluating embedding models for deployment typically use benchmarks like MTEB that sample a fixed set of queries. The LIMIT methodology provides a complementary stress test: before deploying a model with embedding dimension $d$ on a corpus of size $n$, evaluate it on a LIMIT-style dataset constructed with $n' = n$ (or a scaled-down version if $n$ is large) to determine whether the model is operating near its capacity ceiling. If the model achieves near-perfect recall on LIMIT-small but degrades on LIMIT-full, the deployment is capacity-limited and may fail unpredictably when users issue novel or combinatorially unusual queries. If the model performs poorly even on LIMIT-small, the embedding dimension is insufficient for the retrieval depth $k$ required, and the deployment should either reduce $k$ (e.g., retrieve more candidates for downstream reranking), increase dimension, or switch to a multi-vector or hybrid architecture. The paper's finding that Promptriever (54.3% Recall@2) substantially outperforms Qwen3 Embed (19.0% Recall@2) on LIMIT-small, despite both having dimension 4096, provides a concrete example: two models with identical theoretical capacity can differ by 2.8× in realized capacity due to training methodology, and LIMIT-style evaluation detects this difference where standard benchmarks might not.

Design of instruction-following retrieval systems with predictable failure boundaries. Systems that allow users to specify arbitrary relevance criteria through natural language instructions (the paradigm of FollowIR, BRIGHT, and instruction-tuned embedding models) are particularly vulnerable to the combinatorial ceiling, because each new instruction type can create previously unseen combinations of relevant documents. The paper's analysis implies that an instruction-following retrieval system with embedding dimension $d$ has a hard upper bound of approximately $(1 + 1/\gamma)^d$ distinct retrieval configurations it can realize. System designers can use this to establish a "query complexity budget": if the expected number of distinct instruction types over the system's lifetime exceeds this bound, single-vector retrieval will eventually fail on some instructions, and the architecture should include fallback mechanisms (e.g., routing combinatorially unusual queries to a cross-encoder or multi-vector reranker, or decomposing complex instructions into simpler sub-queries that each stay within the capacity budget). The paper's Table 1 provides concrete numbers: for $\gamma = 0.1$ and $d = 1024$, the capacity is approximately $11^{1024} \approx 10^{1066}$ configurations—astronomically large and unlikely to be exhausted in practice—but the effective capacity under gradient-based learning is far lower (the 4.5× multiplier observed in free-embedding experiments effectively reduces $d$ to $\approx 227$ in "usable" dimensions, giving capacity $\approx 11^{227} \approx 10^{236}$, still enormous). The practical ceiling comes not from exhausting absolute capacity but from the interaction between the required number of simultaneously active configurations (documents that must be jointly separable) and the embedding's ability to pack them into $\mathbb{R}^d$ with sufficient margin. The LIMIT dataset operationalizes this: at $n = 46$ and $k = 2$, the model must maintain 1035 simultaneously active pairwise separations, and current models fail at 4096 dimensions.

Informing the architecture roadmap for web-scale and multi-modal search systems. Large-scale search deployments (web search, enterprise document search, product search) routinely index billions of documents and must handle an open-ended set of user queries. The paper's free-embedding extrapolation—critical-$n$ of ~250M for $d = 4096$ with all top-2 combinations—suggests that even the largest current embedding dimensions are marginal for billion-document corpora if the query distribution approaches combinatorial saturation. While real query distributions are far from worst-case, the trend toward instruction-following, multi-modal, and agent-driven search (where automated agents issue many systematically varied queries) increases the combinatorial load. The practical implication is that engineering teams planning for 2–5 year horizons should invest in architectures that transcend the single-vector bottleneck now, rather than waiting for the ceiling to be hit in production. The paper's comparisons (Figures 3, 4, 6) provide a quantitative basis for this investment: ColBERT-style multi-vector models achieve 83.5% Recall@2 on LIMIT-small vs. 54.3% for the best single-vector model, a 1.5× improvement in realized capacity, while BM25 achieves 97.8% at the cost of semantic generalization. Hybrid architectures that combine sparse lexical retrieval (for high capacity) with dense or multi-vector reranking (for semantic matching) are the most immediately deployable path to transcending the single-vector ceiling, and the paper provides the evaluation framework for comparing candidate hybrid designs.

Synthetic data generation for capacity-expanding contrastive training. The paper's LIMIT construction methodology—generating a maximally interconnected qrel matrix and instantiating it with simple natural language—provides a recipe for creating training data that specifically targets the combinatorial capacity bottleneck. Current contrastive training for embedding models relies on naturally occurring query-document pairs (from search logs, QA datasets, or synthetic generation mimicking natural distributions), which tend to have low combinatorial density (Table 2: NQ graph density 0, HotpotQA 0.000037). Training on these distributions teaches models to represent the relevance patterns that occur frequently, but does not pressure them to expand their representational capacity to handle unusual or combinatorially dense query patterns. A capacity-expanding training regimen would mix standard contrastive data with LIMIT-style synthetic data—constructed with systematically increasing $n$ and $k$ to gradually expand the set of jointly realizable retrieval configurations—and measure whether this improves performance on combinatorially challenging benchmarks (LIMIT itself, but also instruction-following benchmarks like FollowIR and BRIGHT that have higher-than-average graph density). The risk, which the paper's MRL analysis hints at, is that capacity-expanding training might trade off against performance on typical queries by spreading the embedding manifold too thin; this tradeoff would need to be explicitly managed.

When to Prefer This Method

The paper does not propose a method in the sense of a new training algorithm, model architecture, or retrieval technique that a practitioner would "prefer" over alternatives. It provides a theoretical analysis, an empirical validation framework, and a diagnostic benchmark. The architectural alternatives discussed in Section 5.3—cross-encoders, multi-vector models, sparse models—are not compared through a systematic decision framework with explicit tradeoff conditions. The paper notes that "all of these options have various trade-offs and none provide a clear path to solving this problem as-is" and leaves the resolution to future work. A forced "prefer A when X, prefer B when Y" decision matrix would impose structure the paper itself does not provide; the paper's contribution is identifying that the capacity limitation exists and how to measure it, not prescribing which alternative to adopt under which conditions. The practical decision rules for architecture selection based on combinatorial capacity are a natural follow-up that the paper enables but does not itself deliver.