On the Theoretical Limitations of Embedding-Based Retrieval
Authors: Orion Weller
Michael Boratko
Iftekhar Naim
Jinhyuk Lee
Venue: ICLR 2026 Poster (2026)
Keywords: retrieval
embeddings
limitations
theoretical
dataset
evaluation
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We show theoretically and empirically that there are limitations to single vector embedding models

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

Published as a conference paper at ICLR 2026
ON THE THEORETICAL LIMITATIONS OF EMBEDDING- BASED RETRIEVAL
Orion Weller Michael Boratko' Iftekhar Naim!
Jinhyuk Lee!
'Google DeepMind, PJohns Hopkins University
owellerêcs juu. edu,
iee.lerress.............iteeeeee jinnyykkeeegooggle.com
ABSTRACT
Vector embeddings have been tasked with an ever-increasing set of retrieval tasks over the years, with nascent rise in using them for reasoning. caaruction-follwinng coding, and more. These new benchmarks push embeddings work for any query and any notion of relevance that could be given. While prior works have pointed out theoretical limitations of vector embeddings, there is a common assumption that these difficulties exclusively due to unrealistic queries, and those that are not can be overcome with better training data and larger models. In this work, we demonstrate that may encounter these theoretical limitations in realistic settings with extremely simple queries. We connect known results in learning theory, showing that the number of top-k subsets of documents capable of being returned as the result of some query is limited by the dimension of the embedding. We empirically show that this holds true even we directly optimize on the test set with free parameterized embeddings. We then create realistic dataset called LIMIT that stress tests embedding models based on these theoretical results, and observe that even state-of-the of-the-art models fail on this dataset despite the simple nature of the task. Our work shows the limits embedding models under the existing single vector paradigm and calls for future research to develop new techniques that can resolve this fundamental limitation.
INTRODUCTION
Over the last two decades, information retrieval (IR) has moved from models dominated by sparse techniques (such as BM25 Robertson et al.] (995)) to those that use neural language models (LM)
as their backbones (Lee al. 2019: Craswell al. 2020; Izacard et al. 2021 Wang al.) 2022).
These neural models are predominantly used in a single vector capacity, where they output a single embedding representing the entire input (also known dense retrieval). These embedding models are capable of generalizing to new retrieval datasets and have been tasked with solving increasingly
complicated retrieval problems (Thakur al. 202 Enevoldsen et al. 2025 Lee et 2025).
In recent years this has been pushed even further with the rise of instruction-follooinng retrieval benchmarks, where models are asked to represent any relevance definition for any query (Weller
et al., 2025a Song et al. 2025 Xiao et al. 2024 Su et al. 2024). For example, the QUEST dataset (Malaviya et al. (023) uses logical operators to combine different concepts, studying the difficulty of retrieval for complex queries (e.g., "Moths or Insects or Arthropods of Guadeloupe"). On the
other hand, datasets such as BRIGHT (Su al. 2024) explore the challenges arising from different definitions of relevance by defining relevance in ways that require reasoning. One subtask includes reasoning over a given Leetcode problem (the query) to find other Leetcode problems that share subtask (e.g. others problems using dynamic programming). Although models cannot solve these benchmarks yet, the community has proposed these problems in order to push the boundaries of what dense retrievers capable which is now implicitly every task that could be defined.
Rather than proposing empirical benchmarks to gauge what embedding models can achieve, we seek to understand at more fundamental level what the limitations are. Since embedding models use

---

Published as a conference paper at ICLR 2026
Query-Document Relevance
LIMIT: real-world instantiation
d
dg d 0g
dg
d dg
d
Who likes Quokkas?
Random Attributes
Jon
Ovid
Lestie
Jon Durben likes Quokkas and Apples.
Quokiaas
Ovid Rahm likes Quokkas and Rabbits.
22
Apples
9g
Leslie Laham likes Apples and Candy.
Can embeddings represent combinations of relevance?
Figure 1: A depiction of the LIMIT dataset creation process, based theoretical limitations. We test all combinations of relevance for N documents (i.e. in the figure, all combinations of relevance for three documents with two relevant documents per query) and instantiate it using simple mapping.
vector representations in geometric space, there exist well-studied fields of mathematical research (Papadimitriou & Sipser 1982) that could be used to analyze these representations.
Our work aims bridge this gap, connecting known theoretical results in linear algebra with modern advancements in neural information retrieval. We draw upon research in high-dimensional geometry to provide lower bound on the embedding dimension needed to represent a given combination of relevant documents and queries. Specifically, we show that for given embedding dimension d there exist top-k combinations of documents that cannot be returned no matter the query highlighting a theoretical and fundamental limit to embedding models.
To show that this theoretical limit is true for any retrieval model or training dataset, we test setting where the vectors themselves are directly optimized with the test data. This allows to empirically show how the embedding dimension enables the solving of retrieval tasks. We find that there exists a crucial point for each embedding dimension (d) where the number of documents is too large for the embedding dimension to encode all combinations. We then gather these crucial points for a variety of d and show that this relationship can be modeled empirically with polynomial function.
We also go one step further and construct a realistic but simple dataset based on these theoretical limitations (called LIMIT) Despite the simplicity of the task (e.g., who likes Apples and Jon likes Apples,
.). we find is very difficult for even saaeeoff-he-an embedding models (Lee et al. 2025 Zhang al. 2025) MTEB (Enevoldsen al. 2025), and practically impossible for models with small embedding dimensions using standard optimization techniques.
Overall, our work contributes: (1) a theoretical basis for the fundamental limitations of embedding models, (2) best-case empirical analysis showing that this proof holds for any dataset instantiation (by free embedding optimization), and (3) simple real-world natural language instantiation called LIMIT that even state-of
embedding models cannot solve.
These results imply interesting findings for the community: on one hand we see neural embedding models becoming immensely successful. However, academic benchmarks test only small amount of the queries that could issued (and these queries are often overfitted to), hiding these limitations. Our work shows that as the tasks given to embedding models require returning ever-increasing combinations of top-k relevant documents (e.g., through instructions connecting previously unrelated documents with logical operators), we will reach limit of combinations they can represent.
Thus, the community should aware of these limitations, both when creating evals and also by using alternate architectures-sude as cross-encoders / multi-vector / more expressive similarity functions when trying to handle the full range of instruction queries, i.c. any query and relevance definition.
Data and code available httpp:://ggithib.comm/////////// deepnn nd/1 imi
2

---

Published as a conference paper at ICLR 2026
2
RELATED WORK
2.1 NEURAL EMBEDDING MODELS
There has been immense progress on embedding models in recent years (Lee et al. 2019 Craswell
al.) 2020 SeehnamGhader et al. 2024). moving from simple web search (text-only) to advanced
Dnstruction-folloiing following and multi-modal representations. These models generally followed advance-
ments in language models, such as pre-trained LMs (Hoffmann al. 2022), multi-modal LMs (Li
et al.
2024 Team 2024), and advancements in instruction- mnstruction-folloiing (Zhou et al.] 2023 Ouyang
al.
2022 J. Some the prominent examples in retrieval include CoPali (Faysse al.
(024) and
DSE
(Ma et al. 2024) which focus on multimodal embeddings, Instructor (Su et al.
2022 and
FollowIR (Weller et al. 2024a) for instruction following, and GritLM (Muennighoft et al.
2024 and
Gemini Embeddings (Lee et al. 2025) for pre-trained LMs turned embedders.
Our work, though focused solely on textual representations for simplicity, applies to all modalities of single vector embeddings for any domain of dataset. As the space of things to represent grows (through instructions or modliitodllity) they will increasingly run into these theoretical limitations.
2.2 EMPIRICAL TASKS PUSHING THE LIMITS OF DENSE RETRIEVAL.
Retrieval models have been pushed beyond their initial use cases to handle a broad variety of areas.
Notable works include efforts to represent wide group of domains Thakur et al.
202T Lee et al.
2024). diverse set of instructions (Weller et al.) 2024a Zhou et al.
2024 Oh et al. 2024; Weller al. 2025bb, and to handle reasoning over the queries (Xiao et al. 2024 Su al. 2024 This
has pushed the focus of embedding models from basic keyword matching to embeddings that can represent the full semantic meaning of language. As such, it more common than ever to connect what were previously unrelated documents into the top-k relevant set increasing the number of combinations that models must be able to represent. This has motivated our interest in understanding the limits of what embeddings can represent, as current work expects it to handle every task.
Previous work has explored empirically the limits of models: Reimers & Gurevych (2020) showed that smaller dimension embedding models have more false positives, especially with larger-scale corpora. Ormazabal et al. (2019) showed the empirical limitations of models in the cross-lingus setting and Yin & Shen (2018) showed how embedding dimensions relate the In contrast, our work provides a theoretical connection between the embedding dimension and the top-k sets it retrieve, while also showing empirical limitations.
tradeoff.
2.3 THEORETICAL LIMITS OF VECTORS IN GEOMETRIC SPACE
Understanding and finding nearest neighbors in semantic space has a long history in mathematics research, with early work such as the Voronoi diagram being studied as far back as 1644 and formalized in 1908 (Voronoi [908). The order-k version of the Voronoi diagram (i.e. the Voronoi diagram partitioning the space into regions based on their closest & points) is obviously connected to information retrieval and has been studied for many years (Clarkson 1988). 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 (Bohler et al. 2015 Lee 1982
Chen et all, 2023).
We approach this problem from different angle, asking not how many k-subsets given configuration realizes, but rather what embedding dimension is necessary to realize all lo-sbbsets with a guaranteed score margin. By applying classical pphekig- volume argument (Vershynin) 2018 Conway et al. 1999), we obtain a lower bound on the embedding dimension in terms of n,, k, and the margin ?y Our result is conceptually related to the Johnson-Lindenstran gives a sufficient dimension to preserve pairwise distances among n points; in contrast, our bound gives a necessary dimension realize all retrieval sets with margin. The role of the margin in controlling the complexity of realizable configurations also parallels classical results in statistical learning theory, including the fat-shattering dimension (Kearns & Schapire 1994) and margin-based generalization bounds for linear classifiers (Bartlett 2002 Vapnik 1998), where larger margins similarly constrain the capacity of the hypothesis class.
lemma (Johnson et al. 1984). which
YYou can imagine easy way to connect any two documents merely by using logical operators, i.c. X and Y.
3

---

Published as a conference paper at ICLR 2026
3 REPRESENTATIONAL CAPACITY OF VECTOR EMBEDDINGS
In this section we formally define the minimum embedding dimension required to satisfy given retrieval objective, and draw on classical sphere-packing results from high-dimensional geometry to establish a lower bound. We note that this will be an extreme lower bound, as practical models have deal with other constraints such learning through gradient descent and using LM tokenization.
Setup. Let ....... On E Rd be unit document vectors, and let queries be unit vectors E Rd. Fix y > 0. A k-subset 8 S [n] is realized with margin y if there exists unit query us such that
min 0x) 2 max Uj) + 27. RES
148
Since (u, 0²) E [- for unit vectors, any score gap is at most 2, hence equation is feasible only for 0 < S 1. Throughout, log denotes the natural logarithm.
Theorem 1 (Dimension lower bound). Assume S k < and that every k-subser S [ [n]] is realized with margin 7 as equation Then
))
log (+)
S 1 (1+-)
hence
d
log 1 + 1/7)
Proof. Fix two distinct k-subsets S * and choose E S T and j E T S. Applying equation to 8 and T gives
(us, U/ 10--1) Uz) 2 27
(wr, Vj - 04) 2 2ny
Adding yields (us - Mr, 0;) 2 4y, By Cauchy-Schwarz Schwarz and (universally, for any unit vectors)
||u, - S ||2 || 2, we obtain luus urll 2 2y. Thus the M = (*) unit queries {us} are pairwise -7-pprrrte so the open balls (u,,, are disjoint. Moreover, since ||us|| = 1, each B(us. _ (0, 7), and therefore
M vo((Bal)) & vol(Ba
Using vol(Ba(r)) = Ca rd for constant Ca depending only on d (which cancels), we get Myd + 7/4 , i.e. (7) S ((1+)//)) 1/7) Rearranging yields equation
Corpus size
k
h
10
À 100
k 1000
10a
trivial
103
23
135
trivial
10*
33
233
1354
10
10
42
329
2334
10
12
52
425
3296
107
61
521
4257
10a
16
71
617
5217
10a
6177
10aD
19
90
809
7137
10
100
905
8098
Table 1: Lower bounds for embedding dimension from Theorem 1 for 7 = 0.1. When n and & are both 1000, the result is trivial because (1000) = (there only one k-subset, hence no "irrelevant" already greater
items separate). We see for large & and values these dimension requirements than those currently used for web-scale search. If these numbers are inflated by a small multiple due to constraints gradient learning or other L.--haeed constraints (e.g. tokenization, generalization) these bounds are outside of any reasonable embedding dimension.
For simplicity, nearly all SoTA retrieval models unit vectors.
4

---

Published as a conference paper at ICLR 2026
3.0.1 IMPLICATIONS
Numerical instantiation We can illustrate the effects of this lower bound using 7 0.1 (score gap 2y = 0.2), which is approximately standard for models based on empirical usage. Thus, equation becomes 2 |log (2) log 11 with table for various & and n values in Table
For >> h, log (2) logg(en/ /)), so equation 2
forces
k llg(en//)) log(1 + 1/7)
d = Ω
A stricter margin requirement (larger ?) demands higher dimension, since log(1 + 1/7) decreases with y (feasibility requires 7 S 1, so the denominator is least log 2).
Consequences Due space and speed requirements. most embeddings used for web-scale search are quantized or truncated (c.g. through Matryoshka embeddings (Kusupati et al. 2022)) to less than 1K dimensions, while the largest embeddings used in research are around 4096 (Zhang al.) 2025). We see that even with a moderate margin, which is needed to handle noise from messy data or quantization, the lower bounds in Table | can already be larger than what used in practice.
Additional constraints on real-world models (such as needing to generalize, learn from gradient descent, and use natural language and tokenization) will make the dimension required in practice much higher. As Table I shows, even small multiple of this lower bound would make the embedding dimension requirement infeasible. This multiple seems well-founded, as we will show in the next section from the best-case optimization setting (e.g. free embeddings).
4 EMPIRICAL CONNECTION: BEST CASE OPTIMIZATION
Having established a theoretical limitation of embedding models based on their embedding dimension d, we seek to show that this holds empirically also.
To show the strongest optimization case possible, we design experiments where the vectors themselves are directly optimizable with gradient descent We call this "free embedding" optimization, as the embeddings are free to be optimized and not constrained by natural language, which imposes constraints on any realistic embedding model. Thus, this shows whether embedding model to solve this problem: if the free embedding optimization cannot solve the problem, real retricval models will not be able to either. It is also worth noting that we do this by directly optimizing the embeddings over the target qrel matrix (test set). This will not generalize to new dataset, but is done to show the highest performance that could possibly occur.
feasible for any
Experimental Settings We create random document matrix (size n) and a random query matrix with top-k sets (of all combinations, i.e. size m = (K)), both with unit vectors. We then directly optimize for solving the constraints with the Adam optimizer (Kingma & Bal 2014 B Each gradient update is a full pass through all correct triples (i.e. full dataset batch-size) with the InfoNCE loss function (Oord et al. 2018 with all other documents as in in-batch negatives (i.e. full dataset in batch). As nearly all embedding models use normalized vectors, we do also (via projected gradient descent). We perform early stopping when there is improvement in the loss for 1000 iterations. We gradually increase the number of documents (and thus the binomial amount of queries) until the optimization is no longer able to solve the problem (i.e. achieve 100% accuracy). We call this the critical-n point.
We focus on relatively small sizes for n, k. and d due to the combinatorial explosion of combinations with larger document values (i.e. 50k docs with top-k of 100 gives 7.7e+311 combinations, which would be equivalent to the number of query vectors of dimension d in that free embedding experiment).
"This could also be viewed an embedding model where each query/doc We found similar results with SGD, but we use Adam for speed and similarity with existing training methods. 'In preliminary experiments, found that InfoNCE performed best, beating MSE and Margin. As
separate vector via lookup.
directly optimizing the vectors with full-dataset batches, this Lunal = TV ΣM log Σa,c exp(sim(g (22)7)
Σd-ER, exp(sim(gade de 1/+)
where 7) is all does, d, is the relevant documents for query gs and de are the non-relevant documents. For experiments with sigmoid learning functions (c.g. [Bangachev al. 2025), see Appendix
5

---

Published as a conference paper at ICLR 2026
We use lo 2 and increase by one for each d value until it breaks. We fit polynomial regression line to the data so we can model and extrapolate results outwards.
Results Figure 2 shows that the curve fits
600
Critical Points
3rd degree polynomial curve, with formula y 110.5322 + 4.0309d + 0.0520d + 0.0037d
Regression (Degree 3)
0r999. Extrapolating this curve outward gives the critical-n values (for embedding size); 500k (512), 1.7m (768), 4m (1024), 107m (3072), 250m (4096). We note that this is the best case: real embedding model cannot di- rectly optimize the query and document vectors to match the test qrel matrix (and is constrained by factors such "modeling natural language"), The results also show that the lower bounds in gross underestimate
400
Critical
200
10
20
30
40
Figure 2: The critical-n value where the dimensionality too small to successfully represent all the top-2 combinations. We plot the trend line as polynomial function.
the previous section of real-world performance, as Table I shows see
lower bound of 4 for 100 whereas the free embeddings needing d > 18 (e.g. a 4.5 multiplier even in the no-generalization or natural language case). Overall, these numbers already show that for web-scale search, even the largest embedding dimensions with ideal test-set optimization are not enough to model all combinations.
EMPIRICAL CONNECTION:
DATASETS
The free embedding experiments provide empirical evidence that our theoretical results hold true. However, they still are abstract what does this mean for real embedding models? In this section we (1) draw connections from this theory to existing datasets and (2) create a trivially simple yet extremely difficult retrieval task for existing SOTA models.
5.1 CONNECTION TO EXISTING DATASETS
Existing retrieval datasets typically use static evaluation set with limited numbers of queries, as relevance annotation is expensive to do for each query. This means practically that the space of queries used for evaluation is very small sample the number of potential queries. For example, the QUEST dataset (Malaviya et al. 2023) has 325k documents and queries with 20 relevant documents per query, with total of 3357 queries. The number of unique top-20 document sets that could be returned with the QUEST corpus would be (325k) which equal to 7.1e+91 (larger than the estimate of atoms in the observable universe, 10 Thus, the 3k queries in QUEST can only cover infinitesimally small part of the qrel combination space.
20
Although not possible to instantiate all combinations when using large-scale corpora, search evaluation datasets are proxy for what any user would ask for and ideally would be designed to test many combinations, as users will do. In many cases, developers of new evaluations simply choose fewer queries due cost computational expense of evaluation. For example, QUEST's query "Novels from 1849 or George Sand novels" combines two categories of novels with the "OR" operator one could instantiate new queries to relate concepts through OR inn other categories together. Similarly, with the rise of search agents, we see greater usage of typer-speciff queries: BrowseComp Wei et al. 2025) has 5+ conditions per query, including range operators. With these tools, it is possible sub-select any top-k relevant set with the right operators if the documents sufficiently expressive (i.c. non- non-trivial). Thus, that existing datasets choose to only instantiate some of these combinations is mainly for practical reasons and not because of lack of existence.
In contrast to these previous works, we seek to build a dataset that evaluates all combinations of top-k sets for a small number of documents. Rather than using difficult query operators like QUEST, BrowseComp, etc. (which are already difficult for reasons outside of the qrei matrix) we choose very simple queries and documents highlight the difficulty of representing all top-k sets themselves.

---

Published as a conference paper at ICLR 2026
@
Recall@10
Recall@100
0.8
0.6
Score
0.4
0.2
0.0
5121024
2048
3072
4096
32 5121024
2048
3072
4096
512
2048
3072
4096
Embed Dim
Embed Dim
Embed Dim
E5 Mistral 7B Snowflake Arctic
GritLM 7B
Qwen3 Embed
BM25
Promptriever Llama3 8B
Gemini Embed
GTE CoBERT
Figure 3: Scores on the LIMIT task. Despite the simplicity of the task we see that SOTA models struggle. We also see that the dimensionality of the model is limiting factor and that as the dimension increases, so does performance. Even multi-vector models struggle. Lexical models like BM25 do very well due to their higher dimensionality. Stars indicate models trained with MRL.
5.2 THE LIMIT DATASET
Dataset Construction In order to have a natural language version this dataset, we need some way to map combinations of documents into something that could be retrieved with query. One simple way to do this is to create a synthetic version with latent variables for queries and documents and then instantiate with natural language. For this mapping, we choose use attributes that someone could like (i.e. Jon likes Hawaian pizza, sports cars, etc. ) as they are plentiful and don't 't present issues w.r.t other items: one can like Hawaiaan pizza but dislike pepperoni, all preferences are valid. We then enforce two constraints for realism: (1) users shouldn' 't have too many attributes, thus keeping the documents short (less than 50 per user) and (2) each query should only ask for one item to keep the task simple (i.e. "who likes X"). We gather list of attributes person could like through prompting Gemini 2.5 Pro. We then clean it to a final 1850 items by iteratively asking it to remove duplicates/hyyemmymss while also checking the top failures with BM25 to ensure no overlap.
We choose to use 50k documents order to have hard but relatively small corpus and 1000 queries to maintain statistical significance while still being fast to evaluate. For each query, choose to use two relevant documents (i.c. k==2), both for simplicity in instantiating and to mirror previous work (i.c. NQ HotpotQA, etc. (Kwiatkowski et al. 2019 Yang et al. 2018
Our last step is to choose a qrel matrix to instantiate these attributes. Although we could not prove the hardest qrel matrix definitively with theory, intuit that our theoretical results imply that the more interconnected the qrel matrix is (e.g. dense with all combinations) the harder it would be for models to represent. Following this, we use the qrel matrix with the highest number of documents for which all combinations would be just above 1000 queries for top-k of 2 (46 docs, since (t0) is 1035, the smallest above 1k).
We then assign random natural language attributes the queries, adding these attributes to their respective relevant documents (c.f. Figure We give each document a random first and last name from open-source lists of names. Finally, we randomly sample new attributes for each document until all documents have the same number of attributes. As this setup has many more documents than those that are relevant to any query (46 relevant documents, 49.95k non-relevant any query) we also create "small" version with only the 46 documents that are relevant to one of the 1000 queries.
Models We evaluate the state-of-the-art embedding models including GritLM (Muennighoff et al.) 2024), Qwen 3 Embeddings (Zhang et al. 2025), Promptriever (Weller et al., 2024b). Gemini Embeddings (Lee et al. 2025). Snowflake Aretic Embed Large v2.0 Yuu al. 2024), and E5-
TThis is just one way, designed to be realistic and simple. However, framework allows for any way of instantiation stuck to this arbitrary natural language design.
7

---

Published as a conference paper at ICLR 2026
Recall@2
Recall@10
Recall@20
1.0
0.8
Score
0.6
0.4
0.2
0.0
32 512 1024
2048
3072
4096
32 5121024
2048
3072
4096
32 5121022 1024
2048
3072
4096
Embed Dim
Embed Dim
Embed Dim
E5-Mistral 7B
CritLM 7B
Qwen3 Embed
BM25
Snowflake Arctic
Promptriever Llama3 8B
Gemini Embed
CTE ModERRCOIBERT
Figure 4: Scores on the LIMIT small task (N=46) over embedding dimensions. Despite having just 46 documents, models struggle even with recall 10 and cannot solve the task even with recall @ 20.
These models range in embedding dimension (1024 to 4096) as well as in training style (instruction-based hard negative optimized, etc.). We also evaluate three non-single vector models to show the distinction:
Mistral Instruct (Wang al. 2022
2023
BM25 (Robertson et al.. T995 Lu 2024).
Iie-ModernCoBBRT Chafffin 2025a
Chaffin & Sourty 2024 and a token-wise TD-IDF
We show results at the full embedding dimension and also with truncated embedding dimension (typically used with matryoshka learning, aka MRL (Kusupati et al. 2022 For models not trained with MRL this will result in sub-par scores, thus, models trained with MRL are indicated with stars in the plots. However, as there are LLMs with an embedding dimension smaller than 384, include MRL for all models to small dimensions (32) to show the impact of embedding dimensionality.
Results Figure shows the results the full LIMIT while Figure shows the results the small (46 document) version. The results are surprising models severely struggle even though the task is trivially simple. For example, in the full setting models struggle to reach even 20% recall @ 100 and in the 46 document version models cannot solve the task even with recall @ 20.
We see that model performance depends erucially the embedding dimensionality (better performance with big- ger dimensions). Interestingly, 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 smaller embedding manifold).
1.0
Recall@2
0.6
Trained on: Test
0.4
Train
0.0
For alternative architectures, GTT--MddemColBEERTT does significantly better than single-vector models (although far from solving the task) while BM25 comes close to perfect scores. Both of these alterative architectures (sparse and multi-vector) offer various trade-offs, see $5.3 for analysis.
32128
256 384 512
768
1024
Embed Dim
Figure 5: Training LIMIT train does not significantly help, indicating the issue not domain shift. But models can solve it if they overfit to the test set.
Is this Domain Shift? Although our queries look similar standard web search queries, wondered whether there could be some domain shift causing the low performance. If so, we would expect that training on a training set of similar examples would significantly improve performance. On the other hand, the task was intrinsically hard, training on the training set would provide little help whereas training on the test would allow the model overfit to those tokens (similar the free embeddings).
To test this we take an off-the-see the-shelf embedding model and train it on either the training set (created synthetically using non-test set attributes) or the official test of LIMIT. We use lightonai
large (Chaftin 2025c) and fine-tune it on these splits, us-
9This model turns each unique item into token and then does TF-IDE. We build it to show that it gets 100% all tasks (as it reverse engineers dataset construction) and thus we do not include in future charts.
8

---

Published as a conference paper at ICLR 2026
100
97.8
LIMIT-Small
Recall
83.5
LIMIT-Small Synonyms
75
54.3
50
38.4
25
10.6
25.6
12.8
14.3
15.1
19.4
19.0
11.6
BM25
GTE-COIBERT Promptriever 88
GriLLM 7B
ES-Mistral 7B
Snowilake Arctic Qwen3 Embed
Figure 6: Comparing scores on LIMIT small vs LIMIT small (synonym). Using synonyms makes the task harder so all models perform worse. However, the lexical model (BM25) drops nearly 90%, performing worse than most sngle-vector models on the synonym version of LIMIT. Thus, lexical models have weaknesses of their own (see Section 5.3 for more discussion) and are not a panacea.
ing the full dataset for in batch negatives (excluding positives) using TratenncTransfommer (Reimers & Gurevych 2019). We show range of dimensions by projecting the hidden layer down to the specified size during training (rather than using MRL).
Figure S shows the model trained on the training set cannot solve the problem, although it does very minor improvement from near zero recall @ 10 to up to 2.8 recall@) 10. The lack of performance gains when training in-domain indicate that poor performance is not due domain shift. By training the model on the test set we see it can learn the task, overfitting on the tokens in the test queries. This aligns with our free embedding results, that it is possible overfit to the N 12 dimensions. However, it is notable that the real models with 64 dimensions still cannot completely solve the task, implying real models perform significantly worse than the bounds shown in $
version with only
What about Non-Lexical Matches? Our previous results show that lexical models greatly outperform their neural counterparts. However, this not to imply that lexical models are panacea- although they have higher dimensionality than single-vector models, they have other shortcomings.
We illustrate this by creating a version of LIMIT-small that replaces all items in the corpus with their synonyms, reducing the amount of lexical overlap. We ask Gemini 2.5 Pro to come up with synonyms that don't match any other existing synonyms or original items, by using either scientific names, if necessary hypernyms. This creates mapping like "glasses" to "spectacles", etc We repeat the previous experiment on LIMIT-small (synonyms) and compare to LIMIT-small in Figure 6 We find that all models drop in performance the task is now more difficult, but BM25 drops the most and now underperforms the neural models (e.g. BM25 drops more than 89% whereas Qwen3 embedding drops 38.9%). Thus, we can see that although lexical models have strengths like higher dimensionality, they are limited by their keyword-only matching ability. We expand more upon their strengths and weaknesses for Instruction-followee
similar meanings,
in Section 5.3
Implications Single-vecte models are fundamentally limited by their embedding dimension. The LIMIT dataset particular instantiation, with very simple queries and documents, designed to highlight this property. This small version of LIMIT can be embedded in just 12 dimensions (as seen the free embeddings experiments), yet all models fail to perform well, suggesting other architectural weaknesses. Irrespective of the architecture involved, however, our framework can scale the dataset'ss difficulty to consistently demonstrate this fundamental limitation.
5.3 ALTERNATIVES TO EMBEDDING MODELS
Our previous results show both theoretically and empirically that embedding models cannot represent all combinations of documents in their top-k sets, making them unable to represent and solve some retrieval tasks. As current embedding models have grown larger (e.g. up to 4096), this has helped reduce negative effects for smaller dataset sizes. However, with enough combinations of top-k sets the dimensionality would have to increase to an infeasible size for non-toy datasets. Thus, although they are useful for first stage results, more expressive retriever architectures will be needed.
Cross-Encodes Although not suitable for first stage retrieval at scale, they are already typically used to improve first stage results. LIMIT challenging for rerankers also? We evaluate a long context reranker, Gemini-2.5. 2.r-Poo (Comanici et al. 2025) on the small setting as comparison. We give Gemini all 46 documents and all 1000 queries at once, asking to output the relevant documents for each query with one generation. We find that it can successfully solve (100%) all 1000 queries in one forward pass. This contrast to even the best embedding models with a recall @2 of less than
We that doesn't remove all lexical overlap due items like "Scuha Diving" > "Underwater Diving"

---

Published as a conference paper at ICLR 2026
60% (Figure D. Thus not have the same limitations based on embedding dimension.
that LIMIT is easy for oftte-o-tthe-are reranker models, which do
Multi-vector models Multi-vector models are more expressive through the use of multiple vectors per sequence combined with the MaxSim operator (Khattab & Zaharia 2020). These models show promise the LIMIT dataset, with scores greatly above the single-vector models despite using smaller backbonn (ModernBERT, Warner et al. (2024)). However, these models are not generally used for instruction-following or reasoning- exist), leaving it an open question to how well multi-vector techniques will transfer to these tasks.
tasks (see (see Chaffin (2025b) as one of the few that
Sparse models Sparse models (both lexical and neural) can be thought of single vectors but with very high dimensionality. This dimensionality helps BM25 avoid the problems of the neural embedding models as seen Figure 3 Since the d of their vectors high, they can scale to many more combinations than their dense vector counterparts. However, it is less clear how to apply sparse models to instruction-folloiing and reasoning- based tasks where there no lexical or even paraphrase-lik liie overlap. We leave this direction (and hybrid sparse/dense solutions) to future work.
We note that all these options have various trade-offs and none provide clear path to solving this problem as-is. We leave it to future work to develop new techniques to mitigate these issues: perhaps through one of these alterative categories or through new ideas around single-vector models that can resolve the underlying issue (potentially through techniques such as hyperencoders (Killingback ct al. 2025) or other future work on single vector architectures yet to be developed).
CONCLUSION
We introduce the LIMIT dataset, which highlights fundamental limitation of embedding models. We provide a theoretical connection which shows that, for fixed embedding dimension there will be some set of documents such that certain sets unattainable top-k sets. We show these theoretical results hold empirically, through best case optimization of the vectors themselves, and make a practical connection to existing state-of-the-art models by creating a realistic and simple instantiation of the theory, called LIMIT, that these models cannot solve. Our results imply that the community should reconsider how instruction-based retrieval will impact future retrievers.
LIMITATIONS
Although our experiments provide theoretical insight for the most common type of embedding model (single vector) they do not hold necessarily for other architectures, such as multi-vector models. Although we showed initial empirical results with non-single vector models, we leave it to future work to extend our theoretical connections these settings. We also did not show theoretical results for the setting where the user allows some mistakes, e.g. capturing only the majority of the combinations. We leave putting a bound on this scenario to future work and would invite the reader to examine works like Ben-David et al. (2002).
We have shown the theoretical connection that proves that some combinations cannot be represented by embedding models, however, we cannot prove apriori which types of combinations they will fail on. Thus, possible that there are some instruction-oollwwe perfectly, however, do know that there exists some tasks that they will never be able to solve.
or reasoning tasks they can solve
ACKNOWLEDGMENTS
We thank Tanmaya Dabral, Zhongli Ding, Anthony Chen, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova for their helpful feedback. We thank Kiril Bangachev, Guy Bresler, Iliyas Noman, Yury Polyanskiy, Antonio Vergari, Adam Lopez, and Andreas Grivas for pointers to work on sign-rank.
REFERENCES
Noga Alon, Peter Frankl, and Vojtech Rodl. Geometrical realization of set systems and probabilistic communication complexity. In 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pp. 277-280. IEFE, 1985.
10

---

Published as a conference paper at ICLR 2026
Samy Badreddine, Emile van Kricken, and Luciano Serafini. Breaking rank bottlenecks in knowledge graph embeddings. arXiv preprint arXiv:2506.2227, 2025.
Kiril Bangachev, Guy Bresler, llyaas Noman, and Yury Polyanskiy. Global minimizers of sigmoid contrastive loss. arXiv preprint wrrXiv:2509.85555 2025.
Peter L Bartlett.
The sample complexity pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE transactions on Information Theory, 44(2):525-53 2002.
Parishad Behnam Vaibhav Adlakha, Marius Mosbach, Dzmitry Bahdanau, Nicolas Chapados, and Siva Reddy. Llm2vec: Large language models are secretly powerful text encoders. arXiv preprint arXiv:2404.05561. 2024.
Shai Ben-David, Nadav Eiron, and Hans Ulrich Simon. Limitations of learning via embeddings in euclidean half spaces. Journal of Machine Learning Research, 3(Nov):441 1-11, 2002.
Cecilia Bohler, Panagiotis Cheilaris, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, and Maksym Zavershynskyi. On the complexity of higher order abstract voronoi diagrams. Com- putational Geometry, 48(8):539 151, 2015. ISSN 0925-7721. doi: https///doi.rr//00.0100
Nomgeo.2015.04.000 URL https:/ //w::///wwwwwwo/ http://wwwww...ceeeeee.c rect http:eetcccoccccceeeeeerrrciaaaa
pl1/5092577211500333
Antoine Chaffin. Gie-moderncolbert, 2025a. URL http:sss//uugggggfcc./////gggggt
GTE- 11E-ModernCoJBERT-
Antoine Chaffin. Reason-moderncolbeet,, 2025b.
URL https://huggingface
Antoine Chaffin. Modeenbertemmbeellagge, 2025c.
URL https://huggigffaee co/
LigitEonal/modernbbett embed- large
Antoine Chaffin and Raphaël Sourty. Pylate: Flexible training and retrieval for late interaction models, 2024. URLhttpp. http:///g.....cccooooooaaaan////
Bi Yu Chen, Huihuang Huang, Hui-Ping Chen, Wenxuan Liu, Xuan- Yan Chen, and Tao Jia. Efficient algorithm for constructing order voronoi diagrams in road networks. ISPRS International Journal of Geo- Reo-Information, 12(4):172, 2023.
Kenneth L Clarkson. Applications of random sampling in computational geometry, ii. In Proceedings of the fourth annual symposium on Computational geometry, pp. 1-11, 1988.
Gheorghe Comanici, Eric Bieber, Mike Schackermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint urXiv:2507.06261, 2025.
John H Conway, Chaim Goodman-Strauss, and Sloane. Recent progress in sphere packing. Current Developments in Mathematics, 1999(1):37-76, 1999.
Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Ellen M Voorhees. Overview of the trec 2019 deep leaming track. arXiv preprint arXiv:2003.07820, 2020.
Kenneth Enevoldsen, Isaac Chung, Imene Kerboua, Márton Kardos, Ashwin Mathur, David Stap, Jay Gala, Wissam Siblini, Dominik Krzeminski,, Genta Indra Winata, al. Mmteb; Massive multilingual text embedding benchmark. arXiv preprint 25Xi:2502.11599 2025.
Manuel Faysse, Hugues Sibille, Tony Wu, Bilel Omrani, Gautier Viaud, Céline Hudelot, and Pierre Colombo. Colpali: Efficient document retrieval with vision language models. arXiv preprint arXiv:2407.01449, 2024.
Andreas Grivas, Antonio Vergari, and Adam Lopez. Taming the sigmoid bottleneck: Provably argmaxable sparse multi-label classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 12208-12216, 2024.

---

Published as a conference paper at ICLR 2026
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv: 2022.
Gautier Izacard, Mathilde Caron, Lucas Hosseini, Sebastian Riedel, Piotr Bojanowski, Armand Joulin, and Edouard Grave. Unsupervised dense information retrieval with contrastive learning. arXiv preprint arXiv:2112.09111 2021.
William Johnson, Joram Lindenstrauss, et Extensions lipschitz mappings into hilbert space. Contemporary mathematics, 26(189-206):1, 1984.
Michael J Kearns and Robert E Schapire. Efficient distribution--fee learning probabilistic concepts.
Journal of Computer and System Sciences, 48(3):464 497, 1994.
Omar Khattab and Matei Zaharia. Colbert:
Efficient and effective passage search via contextualized late interaction over bert. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pp. 49,48, 2020.
Julian Killingback, Hansi Zeng, and Hamed Zamani. Hypencoder: Hypernetworks for information retrieval. In Proceedings of the 48th International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 2372-2383, 2025.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
Aditya Kusupati, Gantavya Bhatt, Aniket Rege, Matthew Wallingford, Aditya Sinha, Vivek Ra- manujan, William Howard-Snyder, Kaifeng Chen, Sham Kakade, Prateek Jain, et al. Matryoshka representation learning. Advances in Neural Information Processing Systems, 35:30233-30249, 2022.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. Natural questions: benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:453 466, 2019.
Der-Tsai Lee. On k-nearest neighbor voronoi diagrams in the plane. IEEE transactions computers, 100(6):478-487, 1982.
Jinhyuk Lee, Zhuyun Dai, Xiaoqi Ren, Blair Chen, Daniel Cer, Jeremy R Cole, Kai Hui, Michael Boratko, Rajvi Kapadia, Wen Ding, et al. Gecko: Versatile text embeddings distilled from large language models. arXiv preprint urXiv:2403.20322 2024.
Jinhyuk Lee, Feiyang Chen, Sahil Dua, Daniel Cer, Madhuri Shanbhogue, Iftekhar Naim, Gus- tavo Hernández Abrego, Zhe Li, Kaifeng Chen, Henrique Schechter Vera, et al. Gemini embedding: Generalizable embeddings from gemini. arXiv preprint 0rX1v:2503.07881, 2025.
Kenton Lee, Ming-Wei Chang, and Kristina Toutanova. Latent retrieval for weakly supervised open domain question answering. In Anna Korhonen, David Traum, and Lluís Marquez (eds.), Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 6086-6096 Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653. v1/P19-1612. htRb:t:s:: https:://aaaaaattaaaeeeeo wwtpp/l.oropp... 9616/
Chunyuan Li, Zhe Gan, Zhengyuan Yang. Jianwei Yang, Linjie Li, Lijuan Wang, Jianfeng Gao, et al. Multimodal foundation models: From specialists to general-purposs assistants. Foundations and Trends@ in Computer Graphics and Vision. 16(1-2):1-214, 2024.
Xing Han Lù. Bm25s: Orders of magnitude faster lexical search via eager sparse scoring. arXiv preprint arXiv:2407.036/3 2024.
Xueguang Ma, Sheng- Chich Lin, Minghan Li, Wenhu Chen, and Jimmy Lin. Unifying multimodal retrieval via document screenshot embedding. arXiv preprint arXiv:2406.1 /251, 2024.
12

---

Published as a conference paper at ICLR 2026
Chaitanya Malaviya, Peter Shaw, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Quest: A retrieval dataset of entity-seeking queries with implicit set operations. arXiv preprint arXiv:2305.11694, 2023.
Niklas Muennighoff, Nouamane Tazi, Loic Magne, and Nils Reimers. Mteb: Massive text embedding benchmark. arXiv preprint arXi::2210.077 2022.
Niklas Muennighoff, SU Hongjin, Liang Wang, Nan Yang, Furu Wei, Tao Yu, Amanpreet Singh. and Douwe Kiela. Generative representational instruction tuning. In ICLR 2024 Workshop: How Far Are We From AGI, 2024.
Hanseok Oh, Hyunji Lee, Seonghyeon Ye, Haebin Shin, Hansol Jang, Changwook Jun, and Minjoon Seo. Instructir: A benchmark for instruction following of information retrieval models. arXiv preprint arXiv:2402. 14334, 2024.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive 2018.
coding. arXiv preprint
Aitor Ormazabal, Mikel Arterxe, Gorka Labaka, Aitor Soroa, and Eneko Agirre. Analyzing the limitations of cross-lingual word embedding mappings. arXiv preprint arXiv:1906.0544 05407, 2019.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang. Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730- 27744, 2022.
Christos H Papadimitriou and Michael Sipser. Communication complexity. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp. 196-200, 1982.
Rohan Paul, Haw-Shiuan Chang, and Andrew McCallum. Multi-facet universal schema. In Pro- ceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, pp. 909-919, 2021.
Nils Reimers and Iryna Gurevych. Sentence-bert Sentence embeddings using siamese nett-networks. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 11 2019. WRLLhttss://aree httpa//wwwww.gaa//a/aaaaaaaaaa/e
orq. abs/ 1908
10084
Nils Reimers and Iryna Gurevych. The curse of dense low-dimensional information retrieval for large index sizes. arXiv preprint arXiv:2012. 2020.
Stephen E Robertson, Steve Walker, Susan Jones, Micheline M Hancock-Beaulien Mike Gatford, et al. Okapi at trec-3. Nist Special Publication Sp, 109:109, 1995.
Tingyu Song, Guo Gan, Mingsheng Shang, and Yilun Zhao. Ifir: A comprehensive benchmark for evaluating mnstruction-follwwii in expert-domain information retrieval. arXiv preprint arXiv:2503.04664 2025.
Hongjin Su, Weijia Shi, Jungo Kasai, Yizhong Wang, Yushi Hu, Mari Ostendorf, Wen-tau Yih, Noah Smith, Luke Zettlemoyer, and Tao Yu. One embedder, any task: Instruction-finetune text embeddings. arXiv preprint arXiv:2212.0m 02.4411,, 2022.
Hongjin Su, Howard Yen, Mengzhou Xia, Weijia Shi, Niklas Muennighoff, Han-yu Wang, Haisu Liu, Quan Shi, Zachary S Siegel, Michael Tang, et al. Bright: A realistic and challenging benchmark for reasoning-intertn intensive retrieval. arXiv preprint arXiv:2407.1288. 2024.
Chameleon Team. Chameleon: lixed-modal carly-fusion foundation models. arXiv preprint
arXiv:2405.09877, 2024.
Nandan Thakur, Nils Reimers, Andreas Rücklé, Abhishek Srivastava, and Iryna Gurevych. Beir: A heterogenous benchmark for zero-shot evaluation information retrieval models. arXiv preprint /044:2200400666 2021.
13

---

Published as a conference paper at ICLR 2026
Nandan Thakur, Jimmy Lin, Sam Havens, Michael Carbin, Omar Khattab, and Andrew Drozdov. Freshstack: Building realistic benchmarks for evaluating retrieval on technical documents. arXiv preprint arXiv:2504.13128, 2025.
Vladimir Vapnik. Statistical Learning Theory now plays a more active role: after the general analysis of learning processes, the research in the area of synthesis of optimal algorithms was started. These studiex, however, do not belong to history yet. They are a subject of today's research activities. PhD thesis, These studies, however, do not belong to history yet. They are subject o.... 1998.
....
Roman Vershynin. High- figh-dimenssooall probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Georges Voronoi. Nouvelles applications des paramètres continus à la théorie des formes quadra- tiques. deuxième mémoire. recherches sur les parallélloèdres primitifs. Journal für die reine und angewandle Mathematik (Crelles Journal), 1908(134):198--1)
1908.
David Wadden, Shanchuan Lin, Kyle Lo, Lucy Lu Wang, Madeleine Zuylen, Arman Cohan, and Hannaneh Hajishirzi. Fact or fiction: Verifying scientific claims. arXiv preprint arXiv:2004. 14974, 2020.
Liang Wang, Nan Yang, Xiaolong Huang, Binxing Jiao, Linjun Yang, Daxin Jiang, Rangan Majumder, and Furu Wei. Text embeddings by arXiv:2212.03533, 2022.
contrastive pre-training. arXiv preprint
Liang Wang, Nan Yang. Xiaolong Huang, Linjun Yang, Rangan Majumder, and Furu Wei. Improving text embeddings with large language models. arXiv preprint arXiv:2401.00368 2023.
Benjamin Warner, Antoine Chaffin, Benjamin Clavié, Orion Weller, Oskar Hallström, Said Taghadouini, Alexis Gallagher, Raja Biswas, Faisal Ladhak, Tom Aarsen, et al. Smarter, bet- ter, faster, longer: A modern bidirectional encoder for fast, memory efficient, and long context finetuning and inference. arXiv preprint arXiv:2412.13665 2024.
Jason Wei, Zhiqing Sun, Spencer Papay, Scott McKinney, Jeffrey Han, Isa Fulford, Hyung Won Chung, Alex Tachard Passos, William Fedus, and Amelia Glaese Browsecomp: A simple yet challenging benchmark for browsing agents. arXiv preprint arXiv:2504. 12516, 2025.
Orion Weller, Benjamin Chang, Sean MacAvaney, Kyle Lo, Arman Cohan, Benjamin Van Durme, Dawn Lawrie, and Luca Soldaini. Followir: Evaluating and teaching information retrieval models to follow instructions. arXiv preprint 2rXiv:2403.15246 2024a.
Orion Weller, Benjamin Van Durme, Dawn Lawrie, Ashwin Paranjape, Yuhao Zhang, and Jack Hessel. Promptriever: cntruction-trainnd retrievers can be prompted like language models. arXiv preprint arXiv:2409. 1111224999111166 11136, 2024b.
Orion Weller, Benjamin Chang, Eugene Yang, Mahsa Yarmohammadi, Sam Barham, Sean MacA- vaney, Arman Cohan, Luca Soldaini, Benjamin Van Durme, and Dawn Lawrie mfollowir: a multilingual benchmark for instruction following in retrieval. arXiv preprint arXiv:2501.1926. 2025a.
Orion Weller, Kathryn Ricci, Mare Marone, Antoine Seq vs seq: An open suite of paired encoders and decoders. arXiv preprint 1rXiv:2507.11412 2025b.
Antoine Chaffin, Dawn Lawrie, and Benjamin Van Durme.
Orion Weller, Kathryn Ricci, Eugene Yang, Andrew Yates, Dawn Lawrie, and Benjamin Van Durme. Rank1: Test-time compute for reranking in information retrieval. arXiv preprint arXiv:2502.1 18418, 2025c.
Chenghao Xiao, G Thomas Hudson, and Noura Al Moubayed. Rar-b: Reasoning as retrieval benchmark. arXiv preprint arXiv:2404.0633 2024.
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio. William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. arXiv preprint arXiv: / 1809. 189000 2018.
14

---

Published as a conference paper at ICLR 2026
Zi Yin and Yuanyuan Shen. information processing systems, 31, 2018.
On the dimensionality of word embedding. Advances in neural
Puxuan Yu, Luke Merrick, Gaurav Nuti, and Daniel Campos. Arctic-embed 2.0: Multilingual retrieval without compromise. arXiv preprint arXiv:2412.04500 2024.
Yanzhao Zhang, Mingxin Li, Dingkun Long, Xin Zhang, Huan Lin, Baosong Yang. Pengjun Xie, An Yang, Dayiheng Liu, Junyang Lin, Fei Huang, and Jingren Zhou. Qwen3 embedding: Advanc- ing text embedding and reranking through foundation models. arXiv preprint arXiv:2506.05176. 2025.
Jeffrey Zhou, Tianjian Lu, Swaroop Mishra, Siddhartha Brahma, Sujoy Basu, Yi Luan, Denny Zhou, and Le Hou. Instruction-following evaluation for large language models. arXiv preprint arXiv:2311.07911, 2023.
Jianqun Zhou, Yuanlei Zheng, Wei Chen, Qianqian Zheng, Zeyuan Shang, Wei Zhang, Rui Meng, and Xiaoyu Shen. Beyond content relevance: Evaluating instruction following in retrieval models. ArXiv, abs/2410.23841, 2024. URL https: //api. weemannicscoooa..rgggoooo 273077855
15


Reviews:
[{"review_id": "Hb2vZk6fp2", "reviewer": "Reviewer_i6hx", "summary": "This paper provides fundamental limitation analysis of embedding models for IR, and shows that the such analysis results hold for many dataset instantiation.", "questions": "The main goal of information retrieval is to improve the performance of a ranked list of documents in response to given a query. It is unclear how such theory analysis can help to boost the ranking performance. The motivations of finding the minimum embedding dimension are not convincing.\n\nThe row-wise order-preserving rank of A, as defined in Definition 1, is strictly constrained, where for **all** i, j, and k, they need to be subject to: if $A_{ij} > A_{ik}$ then $B_{ij}>$B_{ik}$. Can we relax the constraint? Let’s say: such that for xx present of i, j, k, if $A_{ij} > A_{ik}$ then $B_{ij}>$B_{ik}$?\n\nIn some IR task, the relevance scores can be set to be, e.g., 0 (non-relevant), 1 (relevant), 2 (highly relevant), i.e., using graded scores rather than binary scores to denote the relevance. Accordingly, in Definition 2, can we set A to be $A\\in \\{0, 1, 2\\}^{m\\times n}$ for instance?\n\n Are there any other limitations that the authors can provide theory analysis when applying embedding space for neural IR techniques?\n\nWhat are the main differences between previous work that works on embedding dimension compression for embeddings used in IR tasks and the analysis the authors provide here?\n\nSome writing/descriptions are not self-included and confusing. E.g., in the introduction section, the authors claim “Since embedding models use vector representations in geometric space, there exists well-studies fields of mathematical research (Papadimitriou & Sipser, 1982) that xx x”. The concept “mathematical research” is not self-included in this sentence.\n\nIs the dataset publicly available for other researchers used in the experiments?", "limitations": "", "rating": 4, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The paper is well-written and easy to follow.\nThe experiments are well designed.\nIt is necessary to provide in-depth analysis for embedding models used for IR", "weaknesses": "See the below questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Rc36iSoP15", "reviewer": "Reviewer_n8vt", "summary": "This paper presents a significant theoretical and empirical challenge to the standard single-vector embedding paradigm for information retrieval. The authors argue that as embedding models are tasked with increasingly complex, instruction-based retrieval scenarios, they are running into a fundamental theoretical limit, not just a practical one that can be solved by larger models or more data. The core theoretical contribution is to formally connect the representational capacity of an embedding model to the sign-rank of the query-document relevance (qrel) matrix. The authors prove that for any fixed embedding dimension d, there is a hard upper bound on the number of unique top-k relevant document sets a model can represent, meaning some combinations of relevant documents are impossible to retrieve, regardless of the query.\n\nTo validate this theory, the paper introduces two key empirical results. First, it demonstrates using a \"free embedding\" optimization (a best-case scenario without natural language constraints) that this dimensional limitation is real and predictable. Second, it introduces LIMIT, a new benchmark dataset designed to be a simple, natural language instantiation of a task with a high-sign-rank qrel matrix. Experiments show that even state-of-the-art SOTA embedding models fail catastrophically on LIMIT. The work concludes that the community must reconsider the fundamental limitations of the current dense retrieval paradigm for future instruction-following tasks", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The primary strength of this paper is its formal theoretical grounding combined with a rigorous empirical validation. Moving the discussion from a vague sense of \"difficulty\" to a concrete mathematical limitation (by connecting embedding capacity to the sign-rank of the qrel matrix) is a novel and important contribution for the field.\n2. The LIMIT dataset is a significant contribution. It is not just another retrieval benchmark but a cleverly designed probe specifically built to empirically validate the paper's theoretical claims.\n3. The paper is well-written, clear, and addresses a fundamental assumption in the IR/NLP community.", "weaknesses": "1. While the simplicity of the LIMIT dataset is a strength for the theoretical argument, it is also a potential weakness. The synthetic nature of the task (\"who likes X?\") and the explicit construction of an all-combinations qrel matrix make it unclear how often such high-sign-rank relevance structures appear in organic, real-world benchmarks (e.g., MS MARCO, BEIR). The paper claims instruction-following will create these, but doesn't demonstrate that existing complex benchmarks already suffer from this problem.\n2. The theoretical argument is based on the inability to represent all possible $\\binom{n}{k}$ top-k combinations. In practice, a model only needs to represent the subset of combinations that can be expressed by plausible natural language queries. This set is likely much smaller than the theoretical maximum. The paper doesn't fully bridge the gap between \"all possible\" and \"all plausible\" combinations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "914Qwkwemm", "reviewer": "Reviewer_8eB8", "summary": "With the ubiquitous use of embedding models, the authors look at theoretical limits for use of vector embeddings which cannot be overcome with increase of training data. They setup their mathematical propositions and hypothesize from the same about limitations of dense embedding models for retrieval tasks. They create a new dataset and use that to experiment. Their results indicate that the scores can be extremely poor for their settings even after training.", "questions": "1. I understand experimentally it is not possible to extend the experiments in Figure 2 beyond the numbers given, but are there any theoretical or empirical reasons to expect the equation can be extended to hundreds of times from about 50 to 4096?\n2. Will LIMIT be/is publicly available ?\n3. please address the concerns in the weaknesses section.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "It is important in today's time with the ubiquitous use of embedding models, to carefully understand their limitations. The authors take both a theoretical and experimental approach to this very important problem.\n\n1. The mathematical  formulation of the problem is strong.\n2. The authors create a new dataset LIMIT  and use that for their work.\n3. The authors establish that for tasks defined in LIMIT dense embedding models perform extremely poorly.", "weaknesses": "The experimental results are interesting. However, one must ask a pertitent question - are the authors being too pessimistic in their overall claims by creating a dataset and choosing a task which are incompatible with each other? Fundamentally, they have a dataset which is not semantic based and is a word matched based and they have an approach via dense vector embedding search which is unsuitable for this. This mismatch of choice clearly shows by the significant superiority of colbert and the near perfect match of BM25. This indicates experimenting with a wrong approach for a problem - like the cliched \"if the only tool you have is a hammer ..\" . \n\nThe fact that BM25 is hard to outperform on keyword heavy tasks is well researched in the literature [1-4] are examples from a quick search. I am sure a more focussed search will bring up more results.\n\nSo the question that one wonders after reading the paper - is are the claims in the abstract \"Our work shows the limits of\nembedding models under the existing single vector paradigm and calls for future research to develop new techniques that can resolve this fundamental limitation\" are substantiated only by misplaced mapping of experiment and dataset. Their claim on LIMIT being a realistic dataset is valid but it is NOT a dataset well suited for the approach chosen. If this paper purpose was to establish to the practioner / reseacher that do not use embedding models blindly for any task it will be a very well experimented result despite the citations below. However the authors claims are far more stronger which therefore need a stronger and better experimental paradigm. \n\nTheir extremely poor numbers of Recall are also an indication of a wrong technique to a problem and is potentially misleading to a reader who may not be as dilligent - one cannot deny the success of embedding models (the authors do not) but their results leave one wondering what went wrong. \n\n[1] BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models — Thakur et al., 2021.\n\n[2] Match Your Words! / A Thorough Examination on Lexical Matching in Neural IR — Formal (T. Formal), 2021/2022.\n\n[3] Salient Phrase Aware Dense Retrieval — “Can a Dense Retriever Imitate a Sparse One?” — Chen et al., 2021/2022 (SPAR).\n\n[4] A Thorough Examination on Zero-shot Dense Retrieval](https://aclanthology.org/2023.findings-emnlp.1057/) (Ren et al., Findings 2023)\n\nMinor comment:-\n\nI note here details on writing and clarity.\n\n1. the d in figure 2 is obtained by the hp-tuning. d is also used in definition of rank_{rt}. Line 166 defines d to be the dimension. I understand they are related but the d in figure 2 is effectively the din line 166.  maybe a different variable would have been easier.\n2. line 356 refers to appendix C but this does not exist in the pdf.\n3. \"1000 queries to maintain statistical significance while still being fast to evaluate\" - statistical significance is a bit loosely used.\n4. \"For example, in the full setting models struggle to reach even 20% recall@100 and in the 46 document version models cannot solve the task even with recall@20\" - I cannot find two sets of results.\n5. Line 457 mentions a Figure 5 which is not present in the document.\n6. I struggled deciphering the colours in figure 3 and which model is colbert and which is BM25.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)