On the Theoretical Limitations of Embedding-Based Retrieval

Orion Weller; Michael Boratko; Iftekhar Naim; Jinhyuk Lee

Source-linked AI summary

On the Theoretical Limitations of Embedding-Based Retrieval

Orion Weller, Michael Boratko, Iftekhar Naim, Jinhyuk Lee

arXiv:2508.21038v22025년 8월 28일cs.IRcs.CLcs.LG

TL;DR

이 논문은 단순하고 현실적인 query에서도 single-vector embedding이 근본적인 retrieval 한계에 직면하는지 묻고, dimension 기반 제약을 증명하며, 그 결과로 구성한 LIMIT dataset에서 state-of-the-art model이 실패함을 보인다.

문제
embedding의 한계가 비현실적인 query에서만 발생하는지, 아니면 단순하고 현실적인 retrieval task에서도 지속되는지는 분명하지 않다.
방법
이 논문은 learning theory와 high-dimensional geometry를 연결해 embedding dimension의 lower bound를 도출한 뒤, free embedding과 LIMIT dataset으로 이를 검증한다.
결과
고정된 dimension의 embedding은 일부 top-k document 조합을 표현할 수 없으며, state-of-the-art model도 단순하고 현실적인 LIMIT dataset을 해결할 수 없다.
시사점 및 한계
retrieval이 더 많은 top-k 조합을 표현해야 할수록 single-vector embedding은 근본적인 표현 한계에 도달한다.
시사점 및 한계
이론적 결과는 single-vector model을 대상으로 하며, multi-vector architecture나 일부 오류를 허용하는 설정으로 반드시 확장되지는 않는다.

Abstract

from arXiv · show

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

1 서론

본 연구는 단일 벡터 검색의 근본적 한계를 규명하며, 단순하고 현실적인 질의에서도 embedding 차원이 반환 가능한 top-k 문서 조합을 제한한다는 점을 보인다. Free-embedding 실험과 LIMIT dataset은 이러한 한계가 최선의 최적화 조건에서도 지속되며 state-of-the-art 모델에 도전이 된다는 사실을 보여준다.

동기: Instruction-following 검색은 임의의 질의에 대한 임의의 관련성 정의를 embedding이 표현하도록 점점 더 요구하며, 검색 시스템이 지원해야 하는 조합의 범위를 확장한다.서론은 이러한 추세를 각 입력을 단일 벡터로 표현하는 초기 dense retrieval 시스템과 대비한다.
이론적 동기: Embedding 차원은 근본적 한계를 부과한다. 어떤 차원 d에 대해서든 어떤 질의로도 반환할 수 없는 top-k 문서 조합이 존재한다.이 분석은 고차원 기하와 neural retrieval을 연결해 관련 문서와 질의 조합을 표현하는 데 필요한 차원의 하한을 도출한다.
최선 조건의 실증 분석: Test data에서 embedding을 직접 최적화하면 문서 수가 모든 조합을 encoding할 차원의 capacity를 초과하는 critical point가 확인된다.이 free-embedding 설정은 특정 training dataset이나 model architecture 탓으로 실패를 돌리지 않고 이론적 한계를 검증한다.
LIMIT dataset: 단순한 검색 질문으로 구성되었음에도, 이러한 한계에서 구축한 현실적인 natural-language dataset인 LIMIT에서 state-of-the-art embedding models조차 어려움을 겪는다.Embedding 차원이 작은 모델은 표준 optimization 기법으로 LIMIT를 실질적으로 해결하지 못한다.
시사점: 이러한 한계는 범위가 좁거나 overfit된 benchmark에서는 숨겨질 수 있으므로, 더 폭넓은 평가와 cross-encoder, multi-vector model, 더 풍부한 similarity function 같은 대안이 필요하다.이 권고는 instruction query와 관련성 정의의 전체 범위를 처리해야 하는 시스템을 대상으로 한다.

2 관련 연구

Embedding retrieval은 text-only web search에서 instruction-following, multimodal, domain-diverse, reasoning-focused task로 확장됐다. 선행 연구는 empirical embedding limitation과 geometric nearest-neighbor structure를 연구했으며, 본 연구는 embedding dimension을 실현 가능한 top-k set과 연결하고 single-vector modality 전반으로 분석을 확장한다.

Embedding model은 pretrained 및 multimodal language model의 발전에 따라 단순한 text-only web search에서 instruction-following과 multimodal representation으로 발전했다.
분석은 textual representation에 초점을 맞추지만, 표현 요구가 instruction이나 multimodality를 통해 증가함에 따라 그 주장은 modality와 domain 전반의 single-vector embedding에 적용된다.
Retrieval model은 이제 다양한 domain, instruction, query에 대한 reasoning을 다루며, embedding model을 기본적인 keyword matching을 넘어선 수준으로 확장한다.
선행 연구는 false positive, cross-lingual setting, embedding-dimension의 bias-variance tradeoff와 관련된 empirical limitation을 기록한 반면, 본 연구는 dimension을 실현 가능한 top-k set과 이론적으로 연결한다.
Geometric retrieval 연구에는 order-k Voronoi diagram이 포함되지만, 본 연구는 guaranteed score margin을 두고 모든 k-subset을 실현하려면 어떤 dimension이 필요한지를 묻는다.

3 벡터 임베딩의 표현 용량

이 절에서는 모든 k-부분집합을 margin γ와 함께 실현하는 데 필요한 임베딩 차원에 대한 sphere-packing 하한을 제시한다. 중간 정도의 margin만으로도 필요한 차원이 실제 임베딩 차원을 초과할 수 있으며, 실제 학습 및 모델링 제약을 고려하면 요구사항은 더욱 까다로워진다.

설정과 정리: Theorem 1은 모든 k-부분집합을 margin γ와 함께 실현하는 데 필요한 unit document 및 query vector의 차원에 하한을 부여하며, feasibility를 위해서는 0 < γ ≤ 1이 필요하다.이 하한은 모든 k-부분집합이 지정된 margin으로 실현 가능하다는 가정에서 도출된다.
증명: 증명에서는 서로 다른 k-부분집합을 pairwise 2γ-separated query vector로 대응시키고, d차원에서 disjoint-ball volume packing을 사용해 하한을 얻는다.서로 다른 부분집합 S와 T에 대해 score-gap 제약은 ||u_S − u_T|| ≥ 2γ를 함의한다. 반지름 γ인 공을 반지름 1 + γ인 공 내부에 packing하면 차원 제약을 얻는다.
수치 대입: γ = 0.1이면, 큰 n과 k에서 도출되는 하한은 web-scale search에 사용되는 차원을 이미 초과할 수 있다.Table 1에 수치 대입 결과가 제시되지만, 제공된 본문에는 개별 셀 값이 나타나 있지 않다.
수치 대입: γ가 커질수록 log(1 + 1/γ)가 γ에 따라 감소하므로 더 높은 차원이 요구되며, feasibility를 위해서는 여전히 γ ≤ 1이 필요하다.따라서 더 엄격한 score-gap 요구사항은 차원 부담을 가중한다.
결과: 실제 요구사항은 더 심각하다. search embedding은 대개 1k 차원 미만이고, 가장 큰 research embedding도 약 4096 차원이며, learning, generalization, tokenization, quantization이 추가 제약을 부과하기 때문이다.이 절은 기하학적 결과를 극단적인 하한으로 규정하며, 작은 배수 증가만으로도 요구사항이 실현 불가능해질 수 있다고 지적한다.

4 경험적 연결: 최선의 경우 최적화

이 절에서는 문서와 query embedding을 자연어 제약 없이 직접 최적화하는 가장 강한 최적화 설정에서 이론적 차원 제한을 검증한다. 문서 수를 늘려 저차원 embedding이 모든 top-2 조합을 표현하지 못하는 지점을 찾고, 그 결과로 얻은 임계값을 polynomial trend로 모델링한다.

방법: Free embedding optimization은 자연어 제약 없이도 과제를 수행할 수 있는지 검증하기 위해 gradient descent로 문서 및 query vector를 직접 갱신한다.Free embedding으로 문제를 해결할 수 없다면, 현실적인 retrieval model도 해결할 수 없다.
실험 설정: 실험에서는 random unit-vector 문서 및 query matrix, full-batch InfoNCE training, in-batch negative로 사용되는 모든 다른 문서, 그리고 normalization을 위한 projected gradient descent를 사용한다.갱신에는 Adam을 사용하며, improvement가 멈추면 early stopping을 적용한다.
실험 설정: 연구에서는 k = 2로 설정하고, 최적화가 실패할 때까지 각 embedding dimension d에 대해 n을 증가시키며, 이후 trend를 외삽하기 위해 polynomial regression line을 적합한다.top-k 조합의 수가 combinatorial하게 증가하므로 더 큰 n, k, d는 피한다.
결과: Figure 2는 dimensionality가 모든 top-2 조합을 표현하기에 지나치게 작아지는 critical n을 보고하고, 그 polynomial trend line을 보여준다.도표에 표시된 critical-n 값은 이론적 제한을 경험적으로 검증한 결과다.

5 실증적 연결: REAL-WORLD DATASETS

LIMIT dataset은 단순한 query를 사용해 모든 top-k document 조합을 표현하는 어려움을 드러내며, state-of-the-art embedding model도 task가 단순함에도 고전한다. dimensionality와 대안적 architecture를 활용하면 성능이 향상되지만, 현재 접근법 중 이 한계를 명확히 해결하는 방법은 없다.

Dataset Construction: LIMIT는 관련 없는 어려움을 유발하는 복잡한 query operator 대신, 단순한 query와 document를 사용해 top-k set의 조합을 직접 겨냥한다.dataset은 50k개의 document, 1000개의 query, query당 두 개의 relevant document로 구성되며, 46-document subset은 1000개를 조금 넘는 top-2 조합을 포괄한다.
Results: Model은 LIMIT에서 심각하게 고전한다. full-setting system은 recall@100에서 여전히 20% 미만이며, 46-document version은 recall@20에서도 해결되지 않는다.이 결과는 query와 document가 매우 단순한데도 나타난다.
Results: 성능은 embedding dimensionality에 결정적으로 의존하며, dimensionality가 클수록 결과가 향상된다. 또한 instruction-diverse한 Promptriever는 더 좁은 task로 학습된 model보다 우수한 성능을 보인다.저자들은 더 폭넓은 instruction training을 통해 model이 embedding space를 더 많이 활용할 수 있다고 제안한다.
Alternative Architectures: GTE-ModernColBERT는 single-vector model을 크게 앞서지만 LIMIT를 해결하기에는 여전히 부족한 반면, BM25는 거의 완벽한 score에 근접한다.Multi-vector 및 sparse architecture는 expressivity와 applicability 사이에서 trade-off를 보인다. 반면 reranker는 동일한 embedding-dimension 한계가 없기 때문에 LIMIT를 더 쉽게 해결한다.
Implications: 결과는 single-vector model이 embedding dimension에 의해 근본적으로 제한되며, 충분히 많은 top-k 조합을 표현하려면 toy가 아닌 dataset에서 실행 불가능할 정도로 큰 dimensionality가 필요함을 보여준다.46-document LIMIT instance는 free embedding을 사용하면 12 dimensions에 embedding할 수 있지만, 기존 model은 여전히 낮은 성능을 보여 추가적인 architectural weakness가 있음을 시사한다.

6 결론

이 논문은 LIMIT를 도입해 embedding model의 근본적 한계를 드러내고, 고정된 embedding dimension과 실현 불가능한 top-k document set을 연결한다. 최선의 vector optimization 상황을 포함해 이 한계를 이론적·경험적으로 보이며, 이를 state-of-the-art model의 현실적이고 단순한 task와 연결한다.

6 결론: LIMIT는 고정 차원 embedding이 가능한 일부 top-k document set을 실현할 수 없음을 보여 주어 embedding model의 근본적 한계를 부각한다.논문은 이 연결을 이론적으로 정립하고, vector 자체를 최선의 경우로 optimization하여 경험적으로 검증한다.
6 결론: 이 연구는 현실적이고 단순한 task instance를 구성해 기존 state-of-the-art embedding model에 도전함으로써 이러한 이론적 한계를 실제 retrieval과 연결한다.

제한점 · ORDER-K VORONOI 영역과의 관계

이론적 연결은 embedding model이 표현할 수 없는 조합을 식별하는 한편, retrieval의 top-k 출력과 order-k Voronoi 영역을 연결한다. 이러한 제한은 single-vector model에 대해 확립되었지만, 정확한 실패 사례와 다른 architecture에 대한 적용 가능성은 아직 해결되지 않았다.

제한점: 이론적 결과가 single-vector model에서 multi-vector architecture로 반드시 확장되는 것은 아니다.non-single-vector model에 대한 초기 실증 결과는 제시되지만, 이론적 연결을 확장하는 일은 향후 과제로 남아 있다.
제한점: 분석에서는 사용자가 일부 오류를 허용하는 설정, 예를 들어 조합의 다수만 retrieval하는 경우도 여전히 미해결로 남아 있다.제시된 논의는 이 근사 retrieval 설정에 이론적 결과가 부족하다는 점을 지적한다.
제한점: 일부 조합은 embedding model로 표현할 수 없지만, 어떤 조합이 실패할지는 이론으로 사전에 결정할 수 없다.따라서 일부 instruction-following 또는 reasoning task는 완벽하게 해결될 수 있는 반면, 다른 task는 증명 가능하게 해결 불가능하다.
ORDER-K VORONOI 영역과의 관계: order-k Voronoi graph는 k개의 최근접 이웃이 S에 속한 특정 n개 점의 집합인 점들로 구성된다.이 정의는 논문의 결과를 Clarkson (1988)과 비교하는 데 사용되는 기하학적 대상을 제시한다.
ORDER-K VORONOI 영역과의 관계: 각 order-k Voronoi 영역은 하나의 retrieved top-k result set에 대응한다.이 대응은 기하학적 최근접 이웃 영역을 retrieval 출력과 직접 연결한다.
ORDER-K VORONOI 영역과의 관계: 고유한 Voronoi 영역의 수는 retrieval에서 반환될 수 있는 조합의 수와 같다.이 비교는 order-k Voronoi 영역에 대한 Clarkson’s (1988) bounds가 논문의 retrieval 분석과 어떻게 연결되는지 설명한다.

B 하이퍼파라미터 및 컴퓨트 세부사항

실험은 표준 MTEB inference 설정, MultipleNegativesRankingLoss를 사용한 SentenceTransformers training, 그리고 전체 데이터셋 batch 최적화에 적합한 GPU/TPU 컴퓨트를 사용한다.

Inference: Inference에는 기본 MTEB length 설정을 사용하며, 데이터셋 문서가 약 100 tokens를 포함하므로 적절하다.
Training: Training에는 MultipleNegativesRankingLoss를 사용한 SentenceTransformers, full-dataset batches, 중복이 없는 in-batch negatives, 5e-5 learning rate, 그리고 5 epochs를 사용한다.LIMIT training set은 test set에 맞추기 위해 2.5k에서 2k examples로 축소한다.
Compute: LIMIT inference와 training은 A100 GPUs에서 실행하며, free-embedding 실험은 주로 H100 GPUs와 더 큰 N 및 더 높은 VRAM 최적화를 위한 TPU v5s를 사용한다.

C FREE EMBEDDINGS를 위한 SIGMOID LOSS FUNCTION

저자들은 sigmoid-loss free-embedding 실험이 margin을 가정하지 않은 설정에 비해 더 낮은 차원에서 해결될 수 있다고 지적한다. 반면 최상의 결과는 margin을 최대화하는 InfoNCE를 사용했을 때 얻어졌다. 이러한 차이는 learnability에 관한 미해결 질문을 부각한다.

sigmoid loss와의 비교: CLIP과 같은 vision-language model의 sigmoid-loss free-embedding 실험은 margin을 가정하지 않은 저자들의 설정에 비해 더 낮은 차원에서 해결될 수 있다.이 비교는 동시 연구인 Bangachev et al. (2025)에 기인한다.
learnability에 대한 시사점: 가능한 가장 넓은 margin을 추구하는 InfoNCE를 사용했을 때 저자들이 얻은 가장 강력한 성능은 loss로 유도된 margin이 learnability에 영향을 줄 수 있음을 시사한다.저자들은 이러한 설정들이 서로 다른 이유에 관한 추가 질문을 제기하며, 더 깊은 이해가 필요하다고 말한다.

D SIGN-RANK를 이용한 증명 · D.1 형식화 · D.2 이론적 경계

이 논문은 질의별 relevance ordering을 보존하는 score matrix의 최소 rank로 retrieval capacity를 형식화한 뒤, 이 양을 thresholdability 및 sign rank와 연결한다. Binary relevance matrix에서는 행별 ordering과 thresholding이 일치하지만, sign rank는 margin을 가정하지 않으므로 더 약한 차원 요건을 제공한다.

D SIGN-RANK를 이용한 증명: Sign-rank proof는 margin을 가정하지 않으므로 더 약한 차원 요건을 제공하지만, 변환된 relevance matrix의 sign rank는 k에만 의존한다.이 증명은 retrieval representation을 고전적인 sign rank와 연결하지만 양의 separation margin은 부과하지 않는다.
D.1 형식화: Embedding retrieval은 query vector u_i와 document vector v_j로 모델링되며, 각 쌍의 score는 u_i^T v_j로 계산되므로 relevant document가 irrelevant document보다 높은 순위에 있어야 한다.Ground-truth relevance matrix A는 각 document가 각 query와 관련 있는지를 기록한다.
D.1 형식화: Query vector와 document vector를 이어 붙이면 score matrix B = U^T V가 되며, 따라서 가능한 최소 embedding dimension은 모든 행의 relevance ordering을 보존하는 score matrix의 최소 rank와 같다.이는 row-wise order-preserving rank를 vector embedding에 적합한 capacity measure로 정당화한다.
D.1 형식화: Row-wise thresholdable rank는 각 query에 대해 별도의 threshold τ_i를 사용하는 반면, globally thresholdable rank는 모든 query에 하나의 threshold τ를 요구한다.두 정의 모두 relevant score는 threshold보다 높고 irrelevant score는 threshold보다 낮아야 한다고 요구한다.
D.2 이론적 경계: Binary relevance matrix A에서는 rankrop A equals rankrt A이므로, relevant document를 irrelevant document보다 높게 정렬하는 것은 query-specific threshold로 이들을 분리하는 것과 동치다.Binary ordering에서는 모든 relevant score가 모든 irrelevant score보다 높으므로 각 행에 separating threshold를 둘 수 있다는 점에서 이 동치가 성립한다.
D.2 이론적 경계: Sign rank는 entry sign이 ±1 matrix와 일치하는 real matrix의 rank 중 최솟값으로 정의되며, binary relevance matrix는 2A − 1_m×n의 형태로 변환된다.Zero threshold는 relevant document에 대응하는 positive-sign entry와 irrelevant document에 대응하는 negative-sign entry를 분리한다.
D.2 이론적 경계: Threshold와 sign-rank 양은 rank가 최대 하나만큼 다르다: rankgt A ≤ rank±(2A − 1_m×n) ≤ rankrt A + 1.첫 번째 부등식은 zero에서의 global thresholding으로부터 따르고, 두 번째 부등식은 row-threshold vector를 rank-one correction으로 빼서 얻어진다.

D.3 결과 · D.4 MTEB와의 상관관계

결과 절에서는 이진 retrieval objective를 정확히 표현하는 데 필요한 embedding dimension을 상한하며, 일반적으로 실용적이지 않은 sign-rank 구성을 설명한다. BEIR와 비교하면 LIMIT 성능은 대체로 상관되지 않지만, 더 작은 모델은 두 데이터셋 모두에서 성능이 더 낮다.

D.3 결과: Exact retrieval objective는 row-wise ordering, row-wise thresholding 또는 global thresholding에서 embedding dimension의 하한과 상한으로 특성화할 수 있다.
D.3 결과: 이진 relevance matrix A를 정확히 포착하려면 최소 rank±(2A −1_m×n) −1개의 dimension이 필요하다.
D.3 결과: 동일한 이진 relevance relationship을 정확히 포착하는 데는 최대 rank±(2A −1_m×n)개의 dimension이면 항상 충분하다.
D.3 결과: Alon et al. (1985)의 cyclotomic polynomial 구성은 모든 qrel matrix의 sign-rank가 최대 2k임을 함의한다. 여기서 k는 query당 document 수의 최댓값이다.
D.3 결과: 이 구성은 추가 dimension 하나를 사용해 normalized vector에 맞게 조정할 수 있지만, 일반적으로 infinite precision이 필요하므로 실용적이지 않다.
D.4 MTEB와의 상관관계: Figure 7에서 LIMIT 성능은 BEIR 성능과 대체로 상관되지 않지만, Arctic Embed 같은 더 작은 모델은 두 데이터셋 모두에서 성능이 더 낮으며, 이는 embedding dimension과 pretrained knowledge 때문일 가능성이 높다.

F QREL 그래프 밀도를 측정하는 METRICS · G FIGURE의 TABLE 형식

이 논문은 LIMIT의 qrel 구조가 표준 IR 데이터셋보다 훨씬 조밀하고 query 간 연결성이 강함을 보여주는 graph 기반 metrics를 제시한다. 또한 LIMIT, LIMIT small, fine-tuning, free-embedding 실험 결과를 포함해 여러 figure에 대응하는 표 형식도 제공한다.

F QREL 그래프 밀도를 측정하는 METRICS: 두 metrics는 qrel matrix를 graph로 취급해 LIMIT와 표준 IR 데이터셋을 구분한다.논문은 qrel 구조를 상호보완적으로 측정하는 Graph Density와 Average Query Strength를 제시한다.
F QREL 그래프 밀도를 측정하는 METRICS: qrel matrix는 공통 query에 대해 relevant한 경우 document들이 연결되는 document graph가 된다.Graph density는 edge 수를 가능한 undirected edge의 최대 개수로 나눈 값이며, density 1은 complete graph, 0에 가까운 값은 sparse graph를 뜻한다.
F QREL 그래프 밀도를 측정하는 METRICS: Average Query Strength는 각 query node의 incident edge-weight 합을 평균내어, shared relevant documents를 통해 query들이 얼마나 강하게 연결되는지 측정한다.Query similarity에는 relevant documents의 Jaccard similarity를 사용할 수 있다.
F QREL 그래프 밀도를 측정하는 METRICS: LIMIT는 표준 IR 데이터셋보다 qrel graph-density metrics가 훨씬 높으며, 다른 데이터셋의 0.6 이하에 비해 query similarity가 28에 이른다.비교에는 NQ, HotpotQA, SciFact, FollowIR Core17의 test set이 사용되며, instruction-following 데이터셋이 가장 가까운 대안이다.
F QREL 그래프 밀도를 측정하는 METRICS: 저자들의 ablation은 metric 값이 높은 데이터셋일수록 retrieval model이 표현하기 더 어려울 수 있음을 시사하지만, 이를 결정적으로 입증하지는 않는다.이 해석은 데이터셋 비교에서 도출된 경험적 함의로 제시된다.
G FIGURE의 TABLE 형식: Section G는 Figure 3을 Table 5에, Figure 4를 Table 4에, Figure 2를 Table 6에, Figure 5를 Table 3에 대응시킨다.이 표들은 해당 figure의 표 형식이다.
G FIGURE의 TABLE 형식: 표 자료는 fine-tuning, LIMIT, LIMIT small, embedding dimension에 따른 critical n 값을 다루며, Table 7은 BEIR versus LIMIT 결과도 추가로 보고한다.Table 7은 Figure 7에 대응하는 것으로 식별된다.