On the Theoretical Limitations of Embedding-Based Retrieval

이 논문은 임베딩 차원에 의해 토크-k 문서 집합의 표현이 이론적으로 제한된다는 사실을 증명하고, 단순한 작업에서도 최첨단 모델이 이를 극복하지 못함을 보여주어 단일 벡터 패러다임의 근본적 한계를 지적합니다.

핵심

이 논문은 **"벡터 임베딩 (Vector Embedding)"**이라는 기술이 가진 숨겨진 한계를 아주 흥미로운 방식으로 밝혀낸 연구입니다.

간단히 말해, **"컴퓨터가 문서를 이해하는 방식에 근본적인 '물리적' 한계가 있다"**는 것을 증명했습니다.

이 복잡한 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 배경: 컴퓨터는 어떻게 문서를 이해할까요?

지금 우리가 쓰는 검색 엔진이나 AI 는 문서를 이해할 때, 그 내용을 **숫자 목록 (벡터)**으로 바꿉니다. 마치 문서를 "3 차원 공간에 있는 점"으로 표현하는 것처럼요.

• 예시: "사과"라는 문서는 (0.1, 0.9, 0.2) 같은 좌표로, "바나나"는 (0.8, 0.1, 0.3) 같은 좌표로 저장됩니다.
• 원리: 두 점 사이의 거리가 가까우면, 컴퓨터는 "이 두 문서는 비슷하다"고 판단합니다.

최근에는 이 기술이 더 발전해서, "사과와 오렌지를 모두 좋아하는 사람 찾기"처럼 복잡한 지시 (Instruction) 도 수행할 수 있다고 믿어졌습니다.

2. 문제 제기: "모든 조합을 표현할 수 있을까?"

연구자들은 궁금해했습니다. "컴퓨터가 문서를 숫자 점으로만 표현한다면, 사용자가 원하는 '모든 가능한 조합'을 찾아낼 수 있을까?"

예를 들어, 도서관에 책이 100 권 있다고 칩시다.

• "사과가 나오는 책"을 찾는 건 쉬울 수 있습니다.
• 하지만 "사과가 나오면서, 동시에 '오렌지'는 안 나오는데, '바나나'는 나오는 책"을 찾는 건 어떨까요?
• 더 나아가, "사과, 오렌지, 바나나, 포도, 수박..." 등 100 권의 책 중 어떤 2 권의 조합이든 사용자가 지시하면 그걸 찾아낼 수 있을까요?

3. 핵심 발견: "우주 공간의 한계" (이론적 증명)

논문의 저자들은 수학 (기하학) 을 이용해 놀라운 사실을 증명했습니다.

"문서를 표현하는 숫자의 개수 (차원, Dimension) 가 정해져 있다면, 그 공간 안에 모든 가능한 조합을 넣을 수는 없다."

🍊 비유: 좁은 방과 수많은 손님

• 방 (Embedding Space): 컴퓨터가 문서를 넣는 공간입니다. 이 방의 크기는 **숫자 개수 (차원)**로 결정됩니다. (예: 1024 차원 = 1024 개의 벽이 있는 방)
• 손님 (Document Combinations): 사용자가 찾을 수 있는 모든 문서 조합입니다. 문서가 조금만 많아져도 조합의 수는 기하급수적으로 늘어납니다. (우주에 있는 원자 수보다 많을 수도 있습니다!)

결론: 방이 아무리 커도 (차원이 높아도), 손님이 너무 많으면 모든 손님이 동시에 들어갈 수 있는 자리를 마련해 줄 수 없습니다. 어떤 특정 조합은 "방이 꽉 차서" 절대 찾아낼 수 없게 됩니다.

이는 단순히 AI 가 똑똑하지 않아서가 아니라, 수학적으로 불가능한 일이라는 뜻입니다.

4. 실험: "최고의 상황에서도 실패했다"

저자들은 "아마도 훈련 데이터가 부족해서 그런 게 아닐까?"라고 생각했습니다. 그래서 가장 이상적인 상황을 만들어 실험해 봤습니다.

• 실험 설정: 자연어 (사람 말) 를 쓰지 않고, 오직 숫자 (벡터) 만을 직접 만들어서 테스트했습니다. 즉, AI 가 "이건 정답이다"라고 알고 있는 데이터에 맞춰서 벡터를 직접 최적화하는 상황입니다. (가장 편한 조건)
• 결과: 그래도 실패했습니다! 문서가 일정 개수만 넘어가면, 아무리 벡터를 잘 조정해도 모든 조합을 찾아내는 게 불가능해졌습니다.

5. LIMIT 데이터셋: "너무 쉬워서 오히려 어려운 퀴즈"

이론을 증명하기 위해 LIMIT라는 새로운 테스트 데이터를 만들었습니다.

• 내용: "조니는 사과를 좋아하고, 오비드는 토끼를 좋아한다" 같은 아주 단순한 사실만 나열된 데이터입니다.
• 질문: "사과를 좋아하는 사람은 누구인가?"
• 결과: 최신 AI 모델 (GritLM, Gemini 등) 이 이 아주 단순한 질문에도 완전히 망가졌습니다.
  • 왜일까요? 질문이 단순해서가 아니라, "사과 + 토끼"를 동시에 만족하는 조합을 찾아내는 것이, 그 모델의 숫자 공간 (차원) 에는 물리적으로 들어갈 수 없는 자리였기 때문입니다.

6. 대안은 무엇일까?

그렇다면 우리는 포기해야 할까요? 아닙니다. 논문의 결론은 다음과 같습니다.

1. 단일 벡터 (Single Vector) 의 한계: 문서를 하나의 점으로만 표현하는 방식은 더 이상 확장되지 않습니다.
2. 새로운 접근법 필요:
   • Cross-Encoders: 문서를 한 번에 비교하는 방식 (비행기 두 대를 나란히 세워 비교하는 것).
   • Multi-vector: 문서를 여러 개의 점으로 나누어 표현하는 방식 (한 문서를 여러 개의 조각으로 쪼개서 비교).
   • Sparse Models: 단어 하나하나를 세는 전통적인 방식 (BM25) 이 오히려 이 문제에서는 더 잘 작동하기도 했습니다.

📝 요약: 이 논문이 우리에게 주는 메시지

"컴퓨터가 문서를 '하나의 점'으로만 표현하는 한, 아무리 똑똑한 AI 를 만들어도 모든 질문을 답할 수는 없습니다. 수학적으로 '자리'가 없기 때문입니다. 이제 우리는 문서를 더 복잡하고 유연하게 표현하는 새로운 방법을 찾아야 합니다."

이 연구는 AI 업계에 "더 큰 모델, 더 많은 데이터"만으로는 해결되지 않는 근본적인 물리적 한계가 있음을 경고하며, 새로운 기술적 돌파구를 모색하라고 촉구하고 있습니다.

기술 요약

논문 요약: ON THE THEORETICAL LIMITATIONS OF EMBEDDING-BASED RETRIEVAL (임베딩 기반 검색의 이론적 한계에 대하여)

이 논문은 ICLR 2026 에 발표된 것으로, 현재 정보 검색 (IR) 분야에서 널리 사용되는 단일 벡터 임베딩 (Single-vector Embedding) 모델이 가지는 근본적인 이론적 한계를 규명하고 있습니다. 저자들은 임베딩 차원 (dimension) 이 고정되어 있을 때, 특정 조합의 문서들을 'Top-k' 결과로 반환하는 것이 수학적으로 불가능한 경우가 존재함을 증명했습니다.

1. 문제 정의 (Problem)

최근 정보 검색은 BM25 와 같은 희소 (sparse) 모델에서 신경망 기반의 밀집 (dense) 임베딩 모델로 빠르게 전환되었습니다. 특히 최근에는 복잡한 지시 (instruction-following) 나 추론 (reasoning) 을 요구하는 검색 태스크가 등장하며, 임베딩 모델이 모든 쿼리와 관련성 정의 (relevance definition) 를 처리해야 한다는 압력이 커지고 있습니다.

그러나 기존 연구들은 이러한 임베딩 모델의 실패를 주로 훈련 데이터의 부족이나 모델 크기의 한계로 해석했습니다. 본 논문은 임베딩의 차원 (dimension) 자체가 가지는 수학적 한계가 존재하며, 이는 더 많은 데이터나 더 큰 모델로도 해결할 수 없는 근본적인 문제임을 주장합니다. 즉, 임베딩 차원 $d$가 고정되어 있으면, $n$개의 문서 중 $k$개의 문서를 선택하는 모든 가능한 조합 (Top-k subsets) 을 표현하는 것이 불가능한 경우가 발생한다는 것입니다.

2. 방법론 (Methodology)

저자들은 이론적 증명, 최적화 실험, 그리고 실제 데이터셋 평가를 통해 이 주장을 검증했습니다.

2.1 이론적 하한선 도출 (Theoretical Lower Bound)

고차원 기하학 (High-dimensional geometry) 과 구 포장 (Sphere-packing) 이론을 활용하여 임베딩 차원에 대한 하한선을 수학적으로 증명했습니다.

• 가정: $n$개의 문서와 $k$개의 관련 문서 조합을 임베딩 차원 $d$로 표현하며, 관련 문서와 비관련 문서 사이에 $\gamma$만큼의 마진 (score gap) 이 존재해야 한다고 가정합니다.
• 결과 (Theorem 1): 모든 $k$-서브셋을 마진 $\gamma$로 표현하기 위해 필요한 임베딩 차원 $d$는 다음과 같은 하한을 가집니다.
  $$d \ge \frac{\log \binom{n}{k}}{\log(1 + 1/\gamma)}$$
  이 식은 문서 수 $n$과 선택할 문서 수 $k$가 증가함에 따라 필요한 차원이 기하급수적으로 증가함을 보여줍니다.

2.2 최적의 경우 실험 (Best-Case Optimization)

실제 언어 모델의 제약 (토큰화, 일반화 등) 을 배제하고 임베딩 벡터 자체를 직접 최적화하는 실험을 수행했습니다.

• Free Embedding: 자연어 문맥 없이, 테스트 세트의 쿼리 - 문서 관련성 (qrel) 행렬을 만족하도록 벡터를 직접 경사 하강법 (Gradient Descent) 으로 최적화했습니다.
• Critical Point: 문서 수 $n$을 증가시키며 임베딩 차원 $d$가 부족해져서 100% 정확도를 달성할 수 없는 지점 (Critical-n) 을 찾았습니다.
• 결과: 이론적 하한선보다 훨씬 높은 차원이 필요함을 확인했으며, $n$과 $d$ 사이의 관계는 3 차 다항식으로 모델링되었습니다.

2.3 LIMIT 데이터셋 구축 및 평가

이론적 한계를 검증하기 위해 LIMIT라는 새로운 데이터셋을 구축했습니다.

• 구성: 매우 단순한 자연어 쿼리 (예: "Jon 은 사과를 좋아함", "Leslie 는 사탕을 좋아함") 와 문서로 구성되었습니다.
• 특징: 모든 가능한 Top-k 조합 (예: "사과와 사탕을 좋아하는 사람") 을 포함하도록 설계되어, 임베딩 모델이 모든 조합을 표현할 수 있는지 테스트합니다.
• 평가: MTEB 벤치마크에서 최상위 성능을 보이는 최신 임베딩 모델 (GritLM, Gemini Embed, Qwen3 Embed 등) 과 BM25, ColBERT 등의 대안 모델을 평가했습니다.

3. 주요 기여 (Key Contributions)

1. 임베딩 모델의 근본적 한계에 대한 이론적 근거: 임베딩 차원이 고정되어 있을 때, 표현 가능한 Top-k 문서 조합의 수에 한계가 있음을 수학적으로 증명했습니다.
2. 최적화 관점의 실증적 분석: 자연어 제약이 없는 'Free Embedding' 최적화 실험을 통해, 이론적 한계가 실제 최적화 과정에서도 유효함을 입증했습니다.
3. LIMIT 데이터셋 개발: 단순한 쿼리임에도 불구하고 최상위 모델들이 실패하는 새로운 평가 기준을 제시했습니다. 이는 기존 벤치마크가 임베딩 모델의 한계를 숨기고 있음을 보여줍니다.

4. 실험 결과 (Results)

• 이론적 한계: 웹 규모 검색에 사용되는 일반적인 임베딩 차원 (1024~4096) 은 대규모 문서 집합에서 모든 Top-k 조합을 표현하기에 턱없이 부족합니다.
• Free Embedding 실험: $n=100$ 문서, $k=2$인 경우에도 이론적 하한선 (약 4 차) 보다 훨씬 높은 18 차 이상이 필요했으며, 실제 모델은 이보다 더 많은 차원을 필요로 합니다.
• LIMIT 데이터셋 평가:
  • 단일 벡터 모델: 최신 모델들조차 LIMIT 데이터셋에서 극도로 낮은 성능을 보였습니다. (예: 46 개의 문서만 있는 작은 버전에서도 Recall@20 을 달성하지 못함).
  • 차원의 영향: 임베딩 차원이 클수록 성능이 향상되었지만, 여전히 100% 를 달성하지는 못했습니다.
  • 대안 모델:
    • BM25 (Lexical): 높은 차원성으로 인해 단일 벡터 모델보다 훨씬 좋은 성능을 보였으나, 동의어 (Synonym) 처리가 필요한 경우 성능이 급격히 저하되는 한계가 있었습니다.
    • Cross-Encoder (Gemini 2.5 Pro): 모든 문서를 한 번에 처리하는 리랭커는 LIMIT 태스크를 100% 성공적으로 해결했습니다. 이는 임베딩 차원의 제약을 받지 않는 아키텍처의 우월성을 보여줍니다.
    • Multi-vector (ColBERT): 단일 벡터 모델보다 성능이 좋았지만, 여전히 완벽한 해결은 아니었습니다.

5. 의의 및 결론 (Significance & Conclusion)

이 논문은 정보 검색 커뮤니티에 중요한 경고를 보냅니다.

• 벤치마크의 한계: 기존 벤치마크는 가능한 쿼리 공간의 극히 일부만을 테스트하며, 모델이 과적합 (overfitting) 된 상태일 수 있습니다. LIMIT 과 같은 데이터셋은 임베딩 모델이 표현할 수 없는 '조합의 폭발 (combinatorial explosion)'을 드러냅니다.
• 아키텍처의 전환 필요성: 단일 벡터 임베딩 (Dense Retrieval) 은 지시 기반 검색이나 복잡한 논리 연산이 필요한 태스크에서 근본적인 한계에 부딪힙니다.
• 미래 방향:
  • Cross-Encoder: 재랭킹 단계에서 필수적이며, 모든 조합을 처리할 수 있는 능력을 가집니다.
  • Multi-vector / Sparse Models: 더 표현력 있는 아키텍처가 필요합니다.
  • 새로운 기술: 단일 벡터 패러다임 내에서 이 문제를 해결할 수 있는 새로운 기법 (예: Hyperencoders 등) 이 필요합니다.

결론적으로, 임베딩 모델의 성능 향상이 계속되더라도 임베딩 차원의 물리적 한계로 인해 특정 태스크는 영원히 해결되지 않을 수 있으며, 이를 인식하고 더 표현력 있는 아키텍처를 연구해야 함을 강조합니다.