1. Introduction

대규모 언어모델(LLM)의 보편화와 함께, retrieval 단계의 효율성과 expressivity가 시스템 전반의 성능을 결정하는 핵심 요소로 부상함.
특히 Dense Retrieval, 즉 query와 document를 고정된 차원의 embedding vector로 표현하고 inner product 또는 cosine similarity를 통해 relevance를 계산하는 방식은 문서 검색, RAG, QA 등 다양한 응용 분야에서 표준적 접근으로 자리잡음.
그러나 이러한 single-vector embedding 기반 방식은 점점 복잡해지는 정보 구조와 관계 패턴을 충분히 포착하지 못하는 현상이 관찰됨.
하나의 query가 여러 document를 조합적으로 참조하거나, document 간 정보가 중첩·중복되는 경우 기존 embedding은 그 복합적인 relevance 구조를 적절히 반영하지 못함이 보고됨.
이는 단순히 학습 데이터 부족이나 모델 아키텍처의 한계가 아닌, 고정된 차원의 inner product 공간이 표현할 수 있는 관계의 수학적 한계로 귀결되는 양상임.
본 논문은 이러한 한계를 명확히 규정하기 위해, embedding 기반 retrieval의 표현 가능성(expressivity)을 matrix theory의 관점에서 분석함.
query–document 간 relevance를 이진 행렬 A ∈ {0,1}^{m×n}으로 정의하고, 이 행렬을 내적 형태 B = U·Vᵀ (U, V는 각각 query·document embedding 행렬)로 재현 가능한가를 묻는 문제로 환원함.
이때 embedding 차원 d는 곧 B의 rank로 해석되며, 결국 주어진 relevance 패턴이 주어진 차원에서 표현 가능한가의 여부는 행렬의 최소 rank와 직접적으로 연결됨을 보임.
이를 위해 논문은 세 가지 기여를 제시함.
1. 이론적 정식화
  - "embedding 모델이 표현 가능한 relevance 구조"를 행렬의 부호(sign) 패턴으로 일반화하고, 그 최소 차원을 측정하는 지표로 sign-rank를 도입함.
  - sign-rank를 통해 "embedding 차원 d로 표현 가능한 관계의 수학적 경계"를 제시함.
2. 실험적 검증
  - 모델 구조나 학습 데이터 제약 없이, embedding vector 자체를 최적화하는 free embedding 실험을 수행함.
  - 이를 통해 실제로 특정 차원 이하에서는 loss=0(즉, 완전한 재현)이 불가능함을 관찰함. 해당 임계점이 sign-rank 이론의 하한과 일치함을 확인함.
3. 자연어 확장 및 응용 검증
  - 이론적 설정을 자연어로 확장한 LIMIT dataset을 제안함.
  - 다양한 embedding 모델(E5, Qwen, GritLM, Gemini 등)을 평가한 결과, dense한 relevance 구조에서 성능이 급격히 저하되는 현상을 보임. 이는 sign-rank 기반 한계가 실제 자연어 retrieval 환경에서도 그대로 나타남을 시사함.
본 연구는 결과적으로 Dense Retrieval의 한계가 모델의 성능이 아닌 수학적 구조의 제약에서 비롯됨을 증명함.
embedding 차원의 증가는 일시적 개선을 유도할 수 있으나, 기본적으로 sign-rank로 정의되는 pattern complexity를 초과하는 구조는 어떠한 single-vector embedding으로도 완전 재현이 불가능함을 보임.
따라서 본 논문은 "embedding expressivity의 수학적 경계"를 명확히 제시함과 동시에, 이 한계를 극복하기 위한 대안적 접근 — multi-vector, cross encoder, sparse representation — 의 필요성을 이론과 실험을 통해 제시하는 기반을 마련함.

2. Formalization of Embedding-based Retrieval

임베딩 기반 검색은 query와 document를 고정된 차원의 벡터 공간에 매핑하고, 이들 간의 inner product을 통해 relevance를 계산하는 방식으로 정의됨.
이를 수학적으로 표현하면, query embedding 행렬 U ∈ R^{m×d}, document embedding 행렬 V ∈ R^{n×d}가 존재하며, 점수 행렬(score matrix) B는 다음과 같이 주어짐.
```
B = U * V^T,  B[i,j] = u_i^T * v_j
```
여기서 m은 query의 개수, n은 document의 개수, d는 embedding dimension을 의미함.
B의 각 원소는 query i와 document j의 유사도 점수로 해석되며, embedding dimension d가 곧 rank(B)의 상한(rank(B) ≤ d)을 의미함.
따라서 embedding 차원 d는 곧 점수 행렬이 표현할 수 있는 자유도(degree of freedom)를 결정하는 핵심 요소로 작용함.
이로부터 "주어진 관련성 패턴 A가 특정 차원 d에서 표현 가능한가"라는 문제가, "rank(B)가 최소 몇이어야 A의 구조를 재현할 수 있는가"라는 행렬 이론적 문제로 변환됨.

2.1 관련성 행렬 A의 정의

retrieval 과정의 이상적인 목표는 query–document pair의 relevance를 완벽히 반영하는 행렬 A ∈ {0,1}^{m×n}를 재현하는 것임.
A의 각 원소 A[i,j]는 다음과 같이 정의됨.
- A[i,j] = 1 → query i에 대해 document j가 relevant함.
- A[i,j] = 0 → query i에 대해 document j가 non-relevant함.
실제 retrieval 시스템의 목적은 B = U * V^T로부터 얻은 점수행렬이 A의 패턴을 정확히 반영하도록 만드는 것임.
이때 A의 구조적 복잡도(structural complexity)가 높을수록, 즉 relevance 관계가 얽혀 있을수록 B의 rank가 높아야 함.

2.2 표현 가능성의 세 가지 수준

embedding 모델이 A를 "얼마나 정확히 재현할 수 있는가"를 정량화하기 위해 세 가지 수준의 표현 조건을 정의함.

Row-wise Order-preserving (rank_rop A)
- 정의: query i에 대해 relevant document의 점수는 non-relevant document의 점수보다 항상 커야 함. 모든 i, 모든 j,k에 대해
```
A[i,j] > A[i,k] → B[i,j] > B[i,k]
```
- 의미: query별 순위(ranking)가 올바르게 보존되는 조건.
- embedding 모델이 relevance ordering을 완벽히 반영할 때 성립함.
Row-wise Thresholdable (rank_rt A)
- 정의: query마다 다른 threshold τ_i가 존재하여 relevance를 정확히 분리할 수 있는 경우.
```
τ_i ∈ R,
A[i,j] = 1 → B[i,j] > τ_i,
A[i,j] = 0 → B[i,j] < τ_i
```
- 의미: 각 query가 자체적인 cutoff를 통해 relevant와 non-relevant를 나눌 수 있는 구조.
- 실제 embedding 모델의 표현 가능성과 가장 밀접하게 대응하는 조건임.
Globally Thresholdable (rank_gt A)
- 정의: 모든 query에 대해 하나의 공통 threshold τ로 relevance를 분리할 수 있는 경우.
```
τ ∈ R,
A[i,j] = 1 → B[i,j] > τ,
A[i,j] = 0 → B[i,j] < τ
```
```
 의미: 모든 query–document 관계가 단일 기준선에서 분리 가능한 가장 강한 조건.
```
- 현실적으로 성립하기 어렵지만, 이론적 상한선을 정의하는 기준으로 사용됨.

2.3 조건 간 관계

위 세 조건은 포함 관계로 연결됨. Globally Thresholdable → Row-wise Thresholdable → Row-wise Order-preserving
즉, 전역 임계값 분리가 가능하다면 각 행에서도 분리 가능하고, 각 행이 분리 가능하면 당연히 순서 보존이 성립함.
이로부터 rank 관계는 다음과 같이 정리됨.
```
rank_rop(A) = rank_rt(A) ≤ rank_gt(A)
```
Proposition 1은 Row-wise Order-preserving과 Row-wise Thresholdable이 실제로 동일함을 증명함.
- 직관: 각 행에서 relevant 점수 집합과 non-relevant 점수 집합이 항상 분리되어 있다면, 그 사이에 threshold τ_i를 항상 둘 수 있음.
- 반대로, threshold τ_i가 존재한다면 relevant 점수가 항상 더 크므로 순서 보존이 성립함.
따라서 실제 embedding expressivity 분석에서는 rank_rt(A)만 고려하면 충분함.

2.4 임베딩 차원과 행렬 rank의 대응

embedding 모델의 점수 행렬 B = U * V^T은 항상 rank(B) ≤ d를 만족함.
이는 embedding 차원 d가 행렬 B가 표현할 수 있는 구조적 복잡도의 상한임을 의미함.
다시 말해, A의 복잡도가 높아져 rank_rt(A)가 커진다면, 그만큼 더 큰 d가 필요함.
이 관계를 통해 embedding 모델의 근본적 한계를 formal하게 정의할 수 있음. d < rank_rt(A) → embedding 모델로는 A의 패턴을 완전 재현할 수 없음.
이후 장에서는 이를 일반화한 개념으로 sign-rank를 도입하여, embedding expressivity의 수학적 하한(lower bound)을 제시함.

3. Formalization of Expressivity via Sign-Rank

앞선 장에서는 embedding 모델의 표현 가능성을 행렬 A의 rank로 정의했음.
그러나 실제 embedding 모델은 점수의 절대값보다 부호(sign), 즉 "어떤 document가 더 높은 점수를 받는가"만이 중요함.
relevance 행렬 A를 단순히 0과 1로 다루는 대신, 부호 패턴으로 변환하는 것이 보다 자연스러움.
이때 등장하는 개념이 sign-rank이며, 이는 embedding 모델이 표현할 수 있는 관계 구조의 근본적 하한(lower bound)을 수학적으로 정의함.

3.1 0/1 행렬에서 부호 행렬로의 변환

relevance 행렬 A ∈ {0,1}^{m×n}을 ±1 부호 행렬 M으로 변환함.
```
M = 2A − 1
```

변환 결과:

A[i,j] = 1 -> M[i,j] = +1
A[i,j] = 0 -> M[i,j] = −1

기존의 조건을 재작성

A[i,j] = 1 -> B[i,j] > τ_i
A[i,j] = 0 -> B[i,j] < τ_i

sign(B[i,j] − τ_i) = M[i,j]

이 변환은 query별 임계값 τ_i를 제거하고, 모든 relevance 관계를 0 기준으로 정렬함.
즉, 각 query의 분포를 0을 중심으로 평행 이동시켜 row-wise distribution shift를 수행하는 것과 동일한 효과를 가짐.
이 과정을 통해 embedding 모델의 표현 한계를 임계값이 아닌 부호 패턴의 관점에서 단일화할 수 있음.

3.2 Sign-Rank의 정의와 의미

부호 행렬 M의 sign-rank는 다음과 같이 정의됨.

 rank_±(M) = min { rank(B) : sign(B[i,j]) = M[i,j] for all i,j }

즉, M과 동일한 부호 패턴을 갖는 실수 행렬 B 중, rank가 최소인 행렬의 rank를 의미함.
sign-rank는 "이 부호 패턴을 표현할 수 있는 최소 차원"을 정량화하는 지표로, embedding expressivity의 수학적 하한(lower bound)을 규정함.
embedding 모델이 표현할 수 있는 모든 relevance 관계는 sign-rank로 정의되는 영역 안에 포함됨.
따라서 sign-rank는 임계값 조정이 아닌 **부호 일관성(sign consistency)**만으로 표현 가능한 패턴의 복잡도를 결정함.

3.3 핵심 부등식

sign-rank와 embedding 모델의 표현 가능성 간의 관계는 다음과 같은 부등식으로 정리됨.
```
rank_±(2A − 1) − 1 ≤ rank_rt(A) = rank_rop(A) ≤ rank_gt(A) ≤ rank_±(2A − 1)
```
각 항의 의미는 다음과 같음.
- rank_±(2A − 1): 0 임계값에서 완전 분리 가능한 최소 차원 (sign-rank).
- rank_rt(A): 행별 threshold를 허용한 embedding 모델의 최소 차원.
- rank_gt(A): 전역 threshold 하나로 분리 가능한 embedding 모델의 최소 차원.
부등식의 직관은 다음과 같음.
- 임계값을 0으로 고정하면 rank가 최대 1 증가함 (rank_± − 1 ≤ rank_rt).
- 전역 threshold는 가장 강한 제약이므로 rank_gt ≤ sign-rank.
결과적으로 embedding expressivity의 범위는 sign-rank ±1 구간으로 수렴함.

3.4 Embedding Dimension의 의미

embedding 모델의 점수 행렬 B = U * V^T는 항상 rank(B) ≤ d를 만족함.
따라서 embedding dimension d는 행렬이 표현할 수 있는 자유도의 상한이며, sign-rank(M)보다 작으면 해당 부호 패턴을 만족시키는 B는 존재하지 않음.
즉, d < sign-rank(M) → 어떤 embedding 모델로도 sign(B) = M을 만족시킬 수 없음.
이는 optimization 실패나 데이터 부족이 아닌, **선형 공간의 구조적 제약(structural constraint)**으로 인한 표현 불가능성임.
embedding expressivity는 다음과 같이 구분됨.
- d ≥ sign-rank(M): 완전 표현 가능 (full expressivity zone)
- d < sign-rank(M): 표현 불가능 (inexpressibility zone)
sign-rank는 embedding expressivity의 수학적 하한이며, embedding dimension은 이 한계를 만족하는지를 결정하는 **운영적 변수(operational parameter)**로 작용함.

3.5 Gradient 관점에서의 해석

d ≥ sign-rank일 때, sign 패턴을 만족하는 B가 존재하므로 loss → 0으로 수렴함.
반면, d < sign-rank일 경우 sign(B) = M을 만족시키는 해가 존재하지 않아 loss가 plateau 상태에 머무름.
이 영역에서는 gradient가 점차 0에 가까워지지만 실제로는 해 공간이 비어 있음.
따라서 sign-rank는 단순한 복잡도 지표가 아니라, **gradient descent가 수렴할 수 있는 최소 차원 경계(minimal convergence dimension)**로 작용함.
이러한 구조적 한계는 optimizer나 hyperparameter와 무관하게 존재함.

3.6 요약

relevance 행렬 A를 부호 행렬 M = 2A − 1로 변환하면 query별 임계값을 제거한 0 기준의 분리 문제로 환원됨.
sign-rank(M)은 이 부호 패턴을 재현할 수 있는 최소 행렬 rank이며, embedding 차원의 하한으로 작용함.
임계값을 제거하면 rank가 최대 1 증가하므로, embedding expressivity는 sign-rank ±1 구간으로 정의됨.
embedding dimension d가 sign-rank보다 작을 경우 구조적으로 sign(B) = M을 만족시키는 해가 존재하지 않음.
sign-rank는 embedding 모델의 표현력 한계를 수학적으로 규정하며, gradient 기반 학습이 수렴 가능한 최소 차원을 결정함.
다음 장에서는 이러한 이론적 경계를 실제 embedding 학습 실험을 통해 검증함.

4. Free Embedding Experiment

앞 장에서는 sign-rank가 embedding expressivity의 이론적 하한임을 보였지만, sign-rank를 직접 계산하는 것은 NP-hard 문제이기 때문에 이론적 분석만으로는 실제 한계를 관찰하기 어려움.
따라서 free embedding이라는 실험적 접근을 통해, sign-rank 이론이 실제 embedding 학습 과정에서 어떻게 드러나는지를 실증적으로 검증함.
free embedding은 모델 구조나 데이터 제약 없이, embedding 공간 자체의 표현 한계를 관찰함으로써 sign-rank가 단순한 수학적 정의를 넘어 실제 표현 한계로 작동함을 보이는 데 목적이 있음.

4.1 실험 개념

free embedding의 핵심은 이론적으로 계산 불가능한 sign-rank를 실험적으로 추정하는 것.
embedding dimension d를 고정하고, 주어진 relevance matrix A를 완전히 재현할 수 있는지:
```
sign(B) = 2A − 1을 만족시키는 U, V가 존재하는지를 확인함.
```
만약 어떤 d에서 loss = 0으로 수렴하지 않는다면, 이는 해당 d가 sign-rank보다 작다는 것을 의미함.
이 접근은 실제 모델 구조나 학습 데이터의 영향을 배제하고 embedding 표현력의 한계를 "순수하게" 측정하기 위한 실험적 프록시(empirical proxy)로 기능함.

4.2 실험 설정

query 개수를 m, document 개수를 n으로 설정하고, top-k 조합 형태의 synthetic relevance matrix A를 생성함.
각 query는 정확히 k개의 document만을 relevant로 가지며, A의 구조는 조합적으로 dense하도록 설계됨.
embedding dimension d를 여러 값으로 설정하고, U ∈ R^{m×d}, V ∈ R^{n×d}를 직접 최적화함.
학습은 InfoNCE loss를 사용하며, relevance ordering을 최대한 보존하도록 학습함.
```
A[i,j] = 1 -> B[i,j] > B[i,k]
A[i,j] = 0 -> B[i,j] < B[i,k]
```
full-batch gradient descent를 사용하여 stochastic 요인을 제거하고, 순수하게 embedding dimension에 따른 표현 가능성을 관찰함.
loss가 0으로 수렴하지 않는 최소 차원을 기록하여 sign-rank의 실증적 하한(empirical lower bound)으로 사용함.

4.3 임계점 관찰

실험 결과, embedding dimension d를 고정한 채 document 개수 n을 점차 증가시킬 때 일정 지점 이후 loss=0이 불가능해지는 critical n이 존재함이 확인됨.
이는 "주어진 차원 d로 표현 가능한 relevance 구조의 최대 복잡도"를 의미함.
```
d < sign-rank(2A − 1) → loss > 0
d ≥ sign-rank(2A − 1) → loss → 0
```
이 관계는 sign-rank 이론이 실제 embedding 학습의 loss landscape에 반영됨을 보여줌.

4.4 결과 분석

dimension이 작을수록 critical n이 작게 나타나며, 낮은 차원에서는 단순한 부호 패턴만 표현 가능함.
dimension을 늘리면 더 큰 n에서도 loss=0이 가능해지며, 표현 가능한 구조 복잡도(complexity)가 증가함.
실험적으로 critical n과 embedding dimension d의 관계는 3차 다항 근사(cubic relationship)로 설명되며, 이는 이론적 sign-rank 증가 곡선과 거의 일치함.
즉, sign-rank가 embedding dimension의 최소 요구치를 결정하고, d < sign-rank일 때는 어떤 initialization에서도 완전한 재현이 불가능함이 관찰됨.
이러한 패턴은 optimization failure가 아니라 **embedding 공간의 구조적 제약(structural infeasibility)**을 반영함.

4.5 Loss Landscape 해석

free embedding에서 loss surface는 두 구간으로 명확히 나뉨.
- d ≥ sign-rank: loss가 안정적으로 0에 수렴하며, 표현 가능한 영역(full expressivity zone).
- d < sign-rank: loss가 plateau 상태로 머물며 수렴하지 않는 영역(inexpressibility zone).
후자의 경우 gradient norm은 작지만, sign(B)=2A−1을 만족시키는 feasible solution이 존재하지 않음.
즉, loss=0 불가능은 학습 실패가 아니라 **이론적으로 존재하지 않는 해 공간(empty solution space)**에서 비롯됨.
이 관찰은 sign-rank가 단순한 복잡도 개념이 아니라, gradient 기반 학습이 수렴 가능한 최소 차원을 결정하는 **실질적 수렴 경계(empirical convergence boundary)**임을 입증함.

4.6 요약

sign-rank는 이론적으로 embedding expressivity의 하한을 정의하지만, 직접 계산은 NP-hard함.
free embedding은 이 한계를 실험적으로 근사하여, embedding 차원별 표현 가능성을 관찰할 수 있도록 함.
실험 결과, 임베딩 차원이 작을수록 특정 규모 이상에서 loss=0이 불가능해지며, 그 임계점이 sign-rank 하한과 정확히 일치함을 확인함.
이 현상은 optimization 문제라기보다 구조적으로 표현 불가능한 영역을 의미함.
따라서 free embedding은 NP-hard한 sign-rank 계산 문제를 경험적으로 추정하는 실험적 방법이며, sign-rank가 실제 embedding 학습에서의 표현 한계와 수렴 한계를 동시에 규정함을 보여줌.
다음 장에서는 이러한 이론적·실험적 관찰을 실제 자연어 query–document 관계에 확장하기 위해, LIMIT dataset을 구축하고 sign-rank 복잡도가 실제 retrieval 성능에 미치는 영향을 분석함.

5. Empirical Validation with the LIMIT Dataset

sign-rank가 embedding expressivity의 이론적 하한임을 증명하고, free embedding 실험을 통해 이 한계가 실제 optimization 과정에서도 그대로 드러남을 확인함.
그러나 해당 실험은 synthetic 조합 환경에서 수행되었기 때문에, 실제 자연어 기반 retrieval 환경에서도 동일한 현상이 나타나는지를 검증할 필요가 있음.
이를 위해 LIMIT (Language-based Investigation of Matrix-Induced Thresholds) 데이터셋을 구축하여, 자연어 쿼리–문서 관계에서 sign-rank 복잡도가 embedding 모델 성능에 미치는 영향을 검증함.

5.1 데이터셋 설계

LIMIT는 기존 IR 벤치마크보다 훨씬 높은 qrel matrix 밀도(density)와 평균 query 연결 강도(query strength)를 가지도록 설계됨.
예를 들어 LIMIT의 평균 query strength는 28.4로, HotpotQA의 0.11이나 SciFact의 0.42보다 수백 배 높음.
이러한 높은 연결성은 곧 query–document 관계가 강하게 얽혀 있다는 의미이며, sign-rank 복잡도가 매우 높은 구조를 유도함.
즉, LIMIT는 embedding 모델이 구조적으로 분리(linearly separable)하기 어려운 부호 패턴을 포함하도록 의도적으로 설계된 데이터셋임.

5.2 실험 설정

여러 대표적 dense embedding 모델(E5, GritLM, Gemini, Qwen3 등)을 동일한 retrieval 파이프라인에서 평가함.
각 모델은 동일한 쿼리–문서 세트에서 top-k retrieval을 수행하고, Recall@2/10/100을 계산함.
baseline으로 BM25와 multi-vector 기반 GTE-ModernColBERT를 포함하여 구조적 대안을 비교함.
평가 지표로는 NDCG와 Recall을 사용하며, sign-rank 복잡도에 따른 성능 저하를 분석함.

5.3 주요 결과

LIMIT에서 dense embedding 모델의 성능은 기존 데이터셋 대비 극적으로 하락함.
- Qwen3 Embed, Gemini Embed, E5 등 대부분의 dense 모델은 Recall@10이 3% 이하로 수렴함.
- 반면 BM25와 GTE-ModernColBERT는 각각 90.4%, 34.6%로 유지되어, 구조적으로 더 높은 sign-rank 복잡도를 처리할 수 있음을 보임.
LIMIT의 소규모 태스크(N=46)에서의 성능 변화.
- embedding dimension을 32~4096으로 증가시켜도 Recall@20이 0.8을 넘지 못함.
- 이는 데이터 규모가 작더라도 sign-rank가 embedding dimension보다 높을 경우 구조적으로 분리가 불가능함을 실증함.
- BM25 및 ColBERT와 같은 hybrid 또는 multi-vector 구조만이 부분적으로 문제를 해결함.
요약하면, embedding dimension을 아무리 늘려도 sign-rank가 더 큰 영역에서는 loss=0으로 수렴하지 않으며, free embedding 실험에서 관찰된 임계점 현상이 실제 자연어 retrieval 환경에서도 동일하게 재현됨.

5.4 도메인 시프트 검증

성능 저하가 단순한 도메인 불일치(domain shift) 때문일 가능성을 배제하기 위해, 동일한 embedding 모델을 LIMIT의 train/test 분할에 대해 직접 학습시킴.
그 결과, train split으로 학습한 모델은 Recall@10이 2.8% 수준으로 매우 낮았으며, test split에서만 과적합(overfitting)을 통해 높은 성능에 근접함.
즉, poor performance의 원인은 도메인 적응의 문제나 데이터 분포 차이가 아니라, **embedding 구조 자체의 sign-rank 한계로 인한 표현 불가능성(inexpressibility)**임을 확인함.
이 결과는 free embedding 실험의 "loss plateau" 현상과 정합되며, 실제 모델도 sign-rank 경계 아래에서는 구조적으로 수렴할 수 없음을 시사함.

5.5 BEIR vs LIMIT 비교

동일한 embedding 모델을 BEIR와 LIMIT 두 데이터셋에서 평가한 결과를 비교함.
BEIR에서는 모든 dense 모델이 R@100 ≈ 60% 내외의 안정적 성능을 보이나, LIMIT에서는 대부분 10% 이하로 급락함.
- Snowflake Arctic 55.22 → 3.3
- E5-Mistral 57.07 → 8.3
- Gemini Embed 62.65 → 10.0
- Qwen3 Embed 62.76 → 4.8
이는 동일한 모델 구조에서 단지 qrel 복잡도(sign-rank 수준)만 높아져도 성능이 급격히 붕괴함을 명확히 보여줌.
free embedding의 결과와 비교하면, 실제 모델들이 작동 불가능해지는 구간이 sign-rank로 예측된 임계점과 거의 일치함.

5.8 대안 모델들

LIMIT 실험은 단일 벡터 기반 embedding 모델이 높은 sign-rank 복잡도를 가진 관계 구조를 표현하지 못함을 보여주었음.
이에 따라 embedding의 표현 한계를 극복하기 위한 세 가지 대안 구조를 제시함
Cross-Encoder, Multi-Vector, Sparse Retrieval

5.8.1 Cross-Encoder

cross-encoder는 쿼리와 문서를 단일 입력으로 결합하여 비선형 상호작용을 직접 학습하는 방식으로, embedding dimension에 의한 rank 제약을 받지 않음.
논문에서는 long-context reranker Gemini-2.5-Pro를 LIMIT small setting (46개 문서, 1,000개 쿼리)에 적용하여 평가함.
Gemini-2.5-Pro는 한 번의 forward pass로 1,000개 쿼리 모두를 100% 정확하게 해결했으며, 동일 환경에서 가장 성능이 높았던 dense embedding 모델의 Recall@2가 60% 미만인 것과 대조적임.
따라서 cross-encoder는 sign-rank 제약을 완전히 회피하지만, 문서 수가 많은 대규모 retrieval 1단계(first-stage)에는 계산량이 지나치게 크다는 한계를 가짐.

5.8.2 Multi-Vector Models

multi-vector 모델은 각 문서나 쿼리를 여러 개의 벡터로 표현하고, MaxSim 연산으로 매칭 점수를 계산함으로써 표현력을 확장함.
LIMIT 데이터셋에서 multi-vector 기반 모델은 backbone이 더 작음에도 불구하고 single-vector dense 모델보다 훨씬 높은 성능을 달성함.
이는 각 벡터가 부분적인 부호 패턴을 담당함으로써 sign-rank 복잡도를 효과적으로 분산시킬 수 있음을 시사함.
다만, instruction-following이나 reasoning이 요구되는 복합 질의에서는 multi-vector 표현이 얼마나 일반화될 수 있는지는 아직 미지수로 남음.

5.8.3 Sparse Models

sparse retrieval(BM25, SPLADE 등)은 본질적으로 매우 높은 차원의 벡터 공간을 사용함으로써 sign-rank 제약을 완화함.
BM25는 LIMIT 데이터셋에서도 Recall@10 ≈ 90% 이상을 유지하며 dense embedding보다 훨씬 강건한 성능을 보임.
이는 sparse 표현의 고차원성(d >> 4096)이 embedding space의 rank 한계를 실질적으로 제거하기 때문임.
그러나 sparse 모델은 비유사적(non-lexical) 또는 추론 기반(instruction-following) 질의에서는 적용이 제한되며, 논문에서도 "이 방향은 향후 연구 과제로 남긴다"고 언급함.

5.8.4 요약

dense embedding 모델은 제한된 차원 d로 인해 sign-rank 복잡도가 높은 관계 구조를 표현하지 못함.
cross-encoder는 완전한 비선형 상호작용을 통해 이 문제를 해결하지만 계산비용이 크고, multi-vector 모델은 구조적으로 더 효율적인 타협점을 제공함.
sparse retrieval은 차원을 확장해 sign-rank 제약을 완화하지만, 의미적 추론 능력이 부족함.
따라서 향후 retrieval 시스템은 multi-vector + reranking hybrid 방향으로 진화할 가능성이 높으며, 이는 LIMIT 결과가 제시하는 구조적 함의를 뒷받침함.

5.6 시사점

LIMIT 실험은 sign-rank가 embedding expressivity의 이론적 경계일 뿐 아니라, 실제 자연어 retrieval에서 성능 붕괴를 야기하는 **실증적 한계(empirical limit)**임을 입증함.
dense embedding 기반 retrieval은 sign-rank 복잡도가 높은 관계 구조를 표현할 수 없으며, 이로 인해 loss=0 수렴이 불가능하고 ranking 품질이 급격히 악화됨.
이러한 구조적 한계를 극복하기 위해서는
- multi-vector representation,
- cross-encoder reranking,
- hybrid retrieval (dense + sparse) 등의 구조적 대안이 필요함.
결론적으로, sign-rank는 단순한 수학적 지표가 아니라, **embedding 모델이 표현할 수 있는 관계 구조의 실제 경계(expressivity boundary)**를 정의하며, LIMIT 실험은 이 이론이 현실적 환경에서도 그대로 작동함을 실증적으로 보여줌.

5.7 요약

free embedding 실험에서 관찰된 sign-rank 임계점은, LIMIT 데이터셋 실험에서 실제 성능 붕괴로 재현됨.
dense embedding 모델은 low sign-rank 영역에서는 정상 동작하지만, sign-rank 복잡도가 높아지면 구조적으로 collapse하며, dimension 확장은 이를 근본적으로 해결하지 못함.
cross-encoder나 multi-vector, hybrid 모델만이 이러한 한계를 부분적으로 완화함.
따라서 sign-rank는 embedding expressivity의 이론적·경험적 하한으로 기능하며, LIMIT 실험은 그 현실적 타당성을 입증함.

6. Discussion and Implications

sign-rank를 통해 embedding expressivity의 이론적 한계가 명확히 존재함을 보였고, free embedding 실험과 LIMIT 데이터셋 실험을 통해 이 한계가 실제 학습 및 자연어 retrieval 환경에서도 그대로 관찰됨을 확인함.

6.1 embedding expressivity의 본질적 제약

sign-rank는 embedding 모델이 표현할 수 있는 관계 구조의 복잡도를 결정짓는 수학적 하한으로, 이는 모델의 크기나 학습 데이터의 양과는 무관한 구조적 제약임.
embedding dimension이 커질수록 일부 단순한 관계는 표현 가능하지만, sign-rank가 embedding 공간의 선형 표현력(linear expressivity)을 초과하는 영역에서는 어떤 parameter 조합(U, V)으로도 완전한 분리가 불가능함.
free embedding 실험은 이론적 하한이 실제 optimization에서 "loss plateau"로 나타나는 과정을 직접적으로 보여주며, sign-rank가 수학적 개념이 아닌 실질적 수렴 경계(empirical convergence boundary) 로 작동함을 입증함.
이러한 제약은 모델 구조를 바꾸지 않는 이상 극복할 수 없으며, 이는 dense retrieval이 가진 표현력의 근본적 한계로 귀결됨.

6.2 Dense Embedding Retrieval의 붕괴 원인

LIMIT 실험에서 관찰된 급격한 성능 붕괴는 단순히 도메인 적응 실패나 데이터 편향 때문이 아니라, sign-rank 복잡도가 embedding 차원의 한계를 초과했기 때문임.
BEIR와 LIMIT의 성능 차이는 같은 모델 구조에서도 관계 구조의 복잡도만 증가하면 성능이 급락한다는 점을 명확히 보여줌.
즉, dense embedding 모델의 실패는 비선형성의 부족(non-linearity deficiency) 과 고차원 부호 패턴(sign pattern)의 선형적 재현 불가능성에서 비롯됨.

6.3 Sign-Rank 관점에서 본 Retrieval 설계의 전환

sign-rank 분석은 단일 벡터 기반 dense retrieval의 한계를 수학적으로 정식화했으며, 이는 향후 retrieval 시스템 설계가 반드시 구조적 다중 표현(multirepresentational structure) 으로 이동해야 함을 시사함.
가능한 방향은 다음과 같음.
1. Multi-Vector Representation: 문서 또는 쿼리를 다중 벡터로 분해하여 서로 다른 의미 영역(subspace)을 독립적으로 표현함. 이 접근은 각 벡터가 부분 sign 패턴을 담당함으로써 전체 sign-rank를 효과적으로 낮춤.
2. Cross-Encoder Architecture: query–document를 결합 입력으로 처리하여 비선형 상호작용을 직접 학습함으로써, sign-rank 제약을 회피함.
3. Hybrid Retrieval (Dense + Sparse): sparse term 기반 검색을 dense semantic representation과 결합하여, 구조적으로 다른 공간에서 처리함.
이러한 방법들은 모두 "embedding 공간을 선형 rank 제약에서 해방시키는 전략"이라는 공통점을 가짐.

6.4 Sign-Rank와 학습 안정성의 관계

sign-rank는 단순히 표현 가능성을 규정할 뿐 아니라, 학습 안정성과 수렴 특성에도 영향을 미침.
d < sign-rank 영역에서는 loss surface가 평평한 plateau 형태로 고정되며, gradient norm은 작지만 유효한 descent 방향이 존재하지 않음.
이는 optimization이 non-convexity에 의한 불안정이 아니라 feasibility 부족(infeasibility) 에서 비롯된다는 점을 의미함.
반면, d ≥ sign-rank 영역에서는 loss surface가 급격히 convex하게 변화하며, 학습이 빠르게 수렴함.
이 현상은 free embedding 실험의 loss 곡선과 실제 모델 학습 곡선의 형태가 동일함을 통해 실증적으로 확인됨.

6.5 Sign-Rank와 데이터 복잡도의 연결

LIMIT 데이터셋의 qrel matrix는 높은 밀도(density)와 상호 연결성(interconnectivity)을 가지며, 이로 인해 sign-rank 복잡도가 비정상적으로 높음.
이는 실제 기업 문서, 법률 조항, 특허 등 고유사·고중복 도메인에서 동일하게 나타나는 구조적 특성과 일치함.
즉, sign-rank 복잡도는 단순히 수학적 성질이 아니라 도메인 복잡도(domain complexity) 를 정량적으로 측정할 수 있는 지표로 해석 가능함.
retrieval 모델의 실패는 결국 "sign-rank가 높아지는 데이터 환경으로의 이행"과 동반됨.

6.6 향후 연구 방향

모든 Combination을 명확하게 구분하는 것이 구조적으로 불가능 하다는 것은 잘 증명된 것 같음.
그러나 딥러닝 기반의 방식들은 기본적으로 어느정도의 오차를 수반하고, 현실에서도 오차가 없는 것 보다는 오차가 감내 가능한 수준인가가 핵심임.
그렇다면 모든 것을 완벽히 구분하지 않고, 어느 정도의 오분류를 허용한다고 가정을 완화하면 어떻게 되는지가 궁금함
- 오분류를 허용한 만큼 선형적으로 필요한 임베딩 차원수가 감소하는 것인지
- 혹은 약간의 오분류만 허용해도 필요한 임베딩 차원 수가 기하급수적으로 감소하는 것인지
- 전자일 경우, 이 연구의 임팩트가 훨씬 더 커질 것 같음

6.7 요약

sign-rank는 embedding expressivity의 수학적 경계이자, 실제 모델의 수렴 가능성을 결정하는 경험적 지표로 작용함.
dense retrieval 모델은 sign-rank 복잡도가 높은 영역에서 구조적으로 표현 불가능한 부호 패턴에 직면하며, 이는 곧 성능 붕괴로 이어짐.
free embedding 및 LIMIT 실험은 이론적 한계와 실증적 관찰이 완전히 일치함을 보여주며, dense embedding 구조가 가진 근본적 한계를 입증함.
향후 retrieval 시스템은 sign-rank 제약을 우회하기 위해 multi-vector, cross-encoder, hybrid retrieval 등의 구조적 확장을 필수적으로 도입해야 함.
최종적으로, 본 연구는 embedding expressivity의 한계를 수학적·경험적으로 통합하여 설명한 첫 시도이며, retrieval의 구조적 이론화(structural theory of retrieval) 를 위한 기초를 마련함.