임베딩 기반 검색의 숨겨진 함정

왜 AI가 단순한 질문을 놓치게 될까?

안녕하세요! 정보 검색(IR) 세계에서 벡터 임베딩(예: 텍스트를 숫자 벡터로 변환해 유사도 계산)은 요즘 핫한 그리고, 흔한 기술이죠. 구글 검색부터 챗GPT 같은 AI 어시스턴트까지, 이 녀석들이 복잡한 지시어(“파이썬 코드로 동적 프로그래밍 문제 찾아줘”)나 논리적 쿼리(“과들루프의 나방 or 곤충 or 절지동물”)를 처리하려고 애쓰고 있어요. 하지만 Google deepmind의 “On the Theoretical Limitations of Embedding-Based Retrieval​”은 이런 임베딩 모델의 ‘근본적 한계’를 이야기합니다. 이 한계가 “더 큰 모델과 데이터로 해결되겠지”라는 낙관론을 깨부수고, 극도로 단순한 쿼리에서도 드러난다는 거예요. 마치 “사과 좋아하는 사람 누구야?” 같은 질문에서 AI가 엉뚱한 답을 내놓는 상황을 상상해 보세요. 이걸 이론적으로 증명하고, 실험으로 보여주며, 새 데이터셋까지 만들어서 “아, 이게 문제구나!” 하게 해줍니다.

임베딩 모델의 황금 시대와 숨겨진 그림자

과거 IR은 BM25 같은 희소(sparse) 방법으로 키워드 매칭에 의존했지만, 이제는 BERT나 Gemini 같은 신경망 기반 ‘밀집 임베딩’이 주인공이에요. 쿼리와 문서를 d차원 벡터로 바꿔 내적으로 유사도를 계산하죠. 새로운 데이터셋에도 잘 일반화되고, 지시어 팔로잉(instruction-following)이나 코딩, 추론 같은 고급 작업까지 커버하려 해요. 예를 들어, BRIGHT나 QUEST 같은 벤치마크는 “LeetCode 문제에서 동적 프로그래밍 사용하는 다른 문제 찾아!“처럼 복잡한 관련성을 요구하죠.

하지만 문제는 이겁니다. 이런 모델이 모든 가능한 쿼리와 관련성 정의를 다룰 수 있을까요? 논문은 “아니요, 불가능해요!“라고 말합니다. 기존 연구들은 “비현실적 쿼리 때문”이라고 했지만, 여기선 현실적이고 단순한 쿼리에서도조차도 한계가 온다는 걸 증명해요.이유는 벡터 공간의 기하학적 제약 때문임을 밝혔어요.

이차원이 모든 걸 결정짓는 ‘마법의 숫자’

핵심은 ’사인 랭크(sign-rank)’라는 수학 개념이에요. 간단히 말해, 쿼리-문서 관련성 행렬 A(0/1로 relevancy 표시)를 벡터 임베딩으로 표현하려면, 임베딩 차원 d가 관련성 행렬의 사인 랭크만큼 커야 해요. 구체적으로:

정의: top-k 검색에서, 쿼리 i에 대한 관련 문서 집합(예: k=2로 두 문서)은 A 행렬의 패턴으로 표현돼요. 이걸 벡터로 매핑하면, B = U^T V (U: 쿼리 벡터, V: 문서 벡터)로 점수를 계산하죠. row-wise order-preserving rank (rank_rop A)는 A의 순서를 보존하는 최소 d예요.

증명: binary A에 대해 rank_rop A = rank_rt A (thresholdable rank), 그리고 sign-rank(2A - 1) - 1 rank_rop A sign-rank. 즉, d가 작으면 일부 top-k 조합(예: 특정 두 문서 쌍)을 절대 반환할 수 없어요! 고정 d에서 무한한 조합 중 일부는 ‘죽은 공간’에 갇히는 거죠.

웹 규모(수백만 문서)에서 k=2만 해도 조합 수가 우주 원자 수(10^82)보다 커요. d=4096(최신 모델 수준)으로는 2.5억 문서 정도가 한계 – 그 이상은 불가능하다는 거죠.

이론적으로 “d를 키우면 OK”지만, 실전에서 d=4096은 이미 거대해요. 게다가 사인 랭크는 계산조차 어렵지만, 논문은 “free embedding”으로 상한을 추정할 수 있다고 해요. (이 부분은이론가만 이해가..쩝)

‘최선의 경우’ 최적화 – 이론이 현실로!

이론만 적어놓은 게 아니에요. 논문은 free embedding 실험으로 증명해요: 쿼리/문서 벡터를 자유롭게(자연어 제약 없이) 테스트셋 qrel 행렬에 직접 최적화(InfoNCE 손실, Adam 옵티마이저). k=2로 n(문서 수)을 늘리다 실패하는 ‘critical-n’ 포인트를 찾았어요.

실험 결과 critical-n은 d의 3차 다항식으로 모델링했고요 (y = -10.53 + 4.03d + 0.052d² + 0.0037d³, r²=0.999). 예를 들어 d=512 50만 문서, d=4096 2.5억 문서 한계를 실험했더니 웹 검색 규모(수억 문서)에서 실패 확정임을 확인했대요. 이건 “테스트셋 오버피팅”조차 한계가 있다는 뜻이라느데요. 실제 모델은 이보다 더 못해요.

현실세계 데이터셋 LIMIT – 단순함의 역설

이론+추상 실험만으로는 부족하죠? 그래서 LIMIT 데이터셋을 만들었어요. 50k 문서(이름 + 랜덤 ‘좋아함’ 속성,“Jon likes apples, Hawaiian pizza”), 1k 쿼리(“Who likes X?”), k=2 관련성으로 구성되어 있어요. 46개 핵심 문서의 모든 top-2 조합(1035개)을 커버하는 ‘dense’ qrel 행렬 – 다른 데이터셋(예: NQ, HotpotQA)보다 그래프 밀도 10배 이상 높아요!

• 작은 버전 (N=46): recall@20조차 90% 미만. d가 커질수록 성능 (Promptriever 97% vs. 작은 d 50% 미만).

• 전체 버전 (N=50k): SOTA 모델(Gemini Embed, GritLM, Qwen3 Embed 등) recall@100 <20%! BM25(희소 모델)는 93%로 잘하지만, 임베딩은 폭망을 했대요.

도메인 시프트 아님 – 훈련셋으로 fine-tune 해도 10% 미만, 테스트셋 오버피팅만 100%

qrel 패턴 ablation- ’dense(모든 조합)’이 제일 어렵 (GritLM 61% 10%)

MTEB/BEIR와 상관성 없음 – 과적합된 벤치마크가 한계를 숨겼어요.

마무리: 임베딩의 시대는 끝이 아닌 업그레이드 의 시간

논문은 단일 벡터 패러다임의 한계를 강조하며, 지시어 기반 검색(OR 연산 등)이 늘면 더 문제될 거라고 해요. 대안으로 아래를 제시합니다.

• 크로스-인코더 (Gemini-2.5-Pro): LIMIT small에서 100% 성공하지만 계산 비용이 많이 들어 대규모 1단계 검색엔 부적합

• 멀티-벡터 (ColBERT): 60% 정도로 더 낫지만 지시어/추론에 미지수

• 희소 모델 (BM25): 고차원으로 조합 잘 커버하지만 지시어엔 약함

임베딩 모델은 훌륭하지만, “모든 조합”을 다룰 순 없어요. 평가 벤치마크 디자인 시(LIMIT처럼) 조합 다양성을 고려하고, 하이브리드 접근(임베딩 + reranker)을 추천해요. 미래 연구로는 d 증가 대신 멀티-벡터나 이론 확장을 제안합니다.

이 논문 읽고 나니, AI 검색의 ‘블랙박스’가 조금 더 투명해지네요. 만약 IR 연구자라면 LIMIT 데이터셋을 다운로드해서 직접 테스트해 보세요 – 당신의 모델이 얼마나 ‘한정적’인지 알게 될 거예요! 저도 해보려구요.