후반 상호작용 검색 모델의 이론적 표현력 정량화와 Signed MaxSim 확장

왜 중요한가

후반 상호작용 방식은 토큰 수준 표현을 유지하여 희귀 용어와 긴 꼬리 표현을 손실 없이 처리할 수 있는 잠재력을 가진다. 본 논문은 이 잠재력을 수학적으로 정량화하여 MaxSim이 비음수 희소 벡터의 내적을 소수의 저차원 임베딩 집합으로 정확히 재현할 수 있음을 증명했다. 또한 부호 정보를 분리해 처리하는 Signed MaxSim이 임의의 실수값 벡터의 내적을 복원함을 입증하여 부정 쿼리와 도메인 외 일반화에서 실질적 이점을 제공함이 실험으로 확인되었다.

핵심 기여

MaxSim으로 비음수 희소 벡터 내적의 정확 복원 증명

MaxSim 연산을 사용해 임의 차원의 비음수 k-희소 벡터 두 개의 내적을 정확히 재구성할 수 있음을 구성적 증명으로 보였다. 이 구성은 각 비제로 좌표를 ℝ3의 임베딩 하나로 대응시키고 문서 쪽에는 추가적인 제로 벡터를 포함해 쿼리 토큰별로 정확한 기여를 확보한다. 결과적으로 late-interaction 방식이 비음수 영역에서 단일 벡터 기반의 표준 내적과 동등하거나 더 넓은 표현력을 가짐이 보장된다.

표준 MaxSim의 실수값 내적 복원이 불가함을 형식화

고정 임베딩 차원과 희소성 보존 제약 하에서는 표준 MaxSim이 실수값 벡터의 모든 내적을 복원할 수 없음을 증명했다. 이론적 근거로 한 차원보다 큰 정사각 행렬의 랭크 제약과 공유 벡터의 한계를 이용해 표준 MaxSim의 근본적 제약을 도출했다. 이 한계는 부호 정보가 매칭 단계 이전에 결합되는 구조적 문제에서 기인한다.

Signed MaxSim 도입으로 임의 실수 내적의 정확 복원 실현

부호와 크기를 분리해 저장하는 표현과 MaxSim의 최대 선택 이후에 부호를 곱하는 Signed MaxSim을 정의해 임의 실수 벡터 간 내적을 정확히 복원할 수 있도록 확장했다. 이 확장은 희소성 보존을 유지하며 쿼리와 문서의 임베딩을 독립적으로 구성할 수 있어 실제 검색 아키텍처 제약과 일치한다. 이론적 정리는 Signed MaxSim이 표준 내적과 동등한 표현력을 가지며 특정 경우에는 우위를 보인다는 점을 보장한다.

MaxSim의 논리적 표현력과 positive CNF 평가 가능성 증명

MaxSim을 가중 Max-OR 집계로 해석하여 각 OR 절을 단일 쿼리 벡터로 인코딩하고 전체 CNF를 절별 합으로 환원할 수 있음을 수식적으로 보였다. 이로써 MaxSim이 동의어 집단과 OR 관계를 자연스럽게 처리하고, 가중치를 이진화하면 positive CNF과 순위 동치(rank equivalent)를 얻을 수 있음을 입증했다. 이 연결은 전통적 불리언 검색과 신경망 기반 late-interaction 방식 사이의 수학적 가교를 제공한다.

핵심 아이디어 이해하기

검색에서 문서와 쿼리를 단일 벡터로 압축하면 고차원 희소성의 위상 정보를 잃기 쉽다. 단일 내적은 고정 차원에서의 선형 대수적 랭크 제약을 받아 d+1개의 직교 개념을 d 차원으로 보존할 수 없으므로 희소 고차원 공간의 내적을 정확히 유지할 수 없다. 이 점이 late-interaction 방식이 장사람 꼬리 표현을 더 잘 유지하는 근본 이유이다.

MaxSim의 핵심 작동 원리는 쿼리의 각 토큰 벡터마다 문서 임베딩 집합에서 최대 내적을 취하고 이 최대값들을 합산하는 것이다. 이 연산은 각 쿼리 토큰이 문서 내에서 가장 강한 대응만 기여하게 하여 동의어 집단을 단일 매칭으로 처리할 수 있다. 논문에서는 이 특성을 이용해 비음수 희소 벡터의 각 좌표를 ℝ3 임베딩으로 매핑하고 문서 측의 다항식 계수 임베딩을 통해 일치 인덱스에서만 양의 값을 내도록 설계했다.

표준 MaxSim은 부호를 내재적으로 합성하므로 음수 기여를 정확히 재현하지 못하는 상황이 존재한다는 점이 중요하다. 이를 해결하기 위해 부호와 크기를 분리해 크기로 매칭을 결정하고 매칭 이후에 부호를 곱해 기여를 복원하는 Signed MaxSim을 제안했다. Signed MaxSim은 매칭 단계의 선택성을 유지하면서 음수 기여를 그대로 반영하므로 부정 쿼리나 제외 조건을 자연스럽게 처리한다.

MaxSim이 OR 집계를 구현하는 방식은 정보검색에서의 불리언 논리와 연결된다. 각 OR 절을 단일 쿼리 그룹으로 인코딩하면 내부 최대 연산은 그 절의 최대 가중치 매칭을 선택하고 모든 절의 합은 CNF의 평가와 순위 동치가 된다. 따라서 late-interaction 유사도는 희소한 논리적 조건과 동의어 처리라는 검색의 전통적 요구를 연속적 점수 체계로 통합하는 역할을 한다.

방법론

이론적 증명부는 세 단계로 구성되었다. 첫째, 비음수 벡터에 대해 각 비제로 좌표를 ℝ3의 임베딩 ϕ(i)=(1,i,i^2)^T 에 대응시키고, 문서 측에는 특정 좌표에서만 양의 값을 내도록 다항식 계수 c(i,w)를 구성해 MaxSim 합이 원래 내적과 일치하도록 만들었다. 둘째, 표준 MaxSim의 한계를 보이기 위해 희소성 보존 부호화 하에서 임베딩 차원이 고정일 때 발생하는 랭크 제약을 사용해 일반적 실수값 내적의 재현 불가를 증명했다. 셋째, 부호를 분리해 저장하고 최대 선택 이후 부호를 곱하는 Signed MaxSim을 정의해 임의 실수 벡터의 내적 복원을 완성했다.

다항식 구성에서는 두 가지 기법을 병행했다. 비음수 복원에서는 간단한 이차 함수 p(x)=w-C(x-d)^2 를 사용해 목표 인덱스에서 값 w를 내고 다른 정수 인덱스에서는 음수가 되게 만들었다. 그룹화된 OR 절을 인코딩할 때는 Lagrange 보간 다항식 x_S(t)와 그 근들을 이용한 보정 항 C(y_S(t))^2 를 결합해 목표 키들에서는 지정된 가중치를, 비대상 키들에서는 음수를 내도록 2m 차 다항식을 구성했다. 이 다항식 계수들을 임베딩으로 사용하면 MaxSim의 내적 최대 연산이 곧 Weighted Max-OR를 계산하게 된다.

실험적 검증은 합성 데이터셋에서 이루어졌다. 학습 세팅은 ModernBERT 백본을 공유한 ColBERT 스타일의 late-interaction 구조를 따랐고, Fallon이라 명명한 Signed MaxSim 모델은 추가 MLP로 토큰별 실수형 가중치(부호 포함)를 생성했다. 대비 학습은 인배치 네거티브와 하드 네거티브를 활용한 대조 손실을 사용했고, 평가 벤치마크로 도메인 동일, 어휘 변경, 부정 전용 쿼리 변형을 생성해 일반화와 부정 처리 능력을 측정했다.

주요 결과

이론적 결과는 MaxSim이 비음수 희소 벡터의 내적을 정확히 재현할 수 있으며 Signed MaxSim은 임의 실수값 벡터의 내적을 정확히 복원할 수 있음을 수학적으로 보였다. 실험에서는 합성 데이터 기반의 비교에서 ColBERT(표준 MaxSim)와 Fallon(Signed MaxSim)을 비교했으며 주요 지표에서 Fallon이 우위를 보였다. 특히 Different Vocabulary 환경에서 nDCG@10이 ColBERT 0.597에서 Fallon 1.000으로 상승했고, Negation Only 쿼리에서는 nDCG@10이 ColBERT 0.008에서 Fallon 0.788로 개선되어 부정 처리 문제에서의 구조적 장점을 수치로 입증했다.

In-Domain 평가에서도 Fallon이 소폭 우세를 보였으며 구체적으로 ColBERT의 nDCG@10이 0.982일 때 Fallon은 0.997을 달성했다. 이 결과들은 Signed MaxSim이 학습 분포와 다른 어휘나 쿼리 구성에 대해 더 강건한 일반화 전략을 학습했음을 시사한다. 또한 Negation Only 실험에서 ColBERT의 성능 저하는 MaxSim이 내재적으로 항상 일부 매칭을 찾는 경향으로 인해 제외 조건을 효과적으로 낮은 점수로 반영하기 어렵기 때문임이 관찰되었다.

평가 지표별 경향으로는 P@10과 AP에서도 Fallon이 일관되게 우수했다. AP 값은 상위 1,000개만 조회하는 평가 한계 때문에 일부 케이스에서 제한적 상한을 가지지만, 상대적 향상 폭은 부정 중심 쿼리에서 특히 컸다. 통계적 유의성 검정에서 대부분의 차이는 p<0.01로 유의하였다.

기술 상세

MaxSim 수식은 S(U,V)=∑{m∈U} max{t∈V} ⟨m,t⟩ 이다. 여기서 U와 V는 각각 쿼리와 문서의 임베딩 집합을 의미하며 ⟨·,·⟩는 벡터 내적을 나타낸다. 계산 흐름은 각 쿼리 임베딩 m에 대해 문서 임베딩 집합 V에서 내적이 최대가 되는 t를 찾고 그 값을 더해 최종 스코어를 얻는 방식이다. 작은 예로 U가 하나의 쿼리 임베딩 m이고 V가 두 개의 문서 임베딩 t1,t2라면 각각 ⟨m,t1⟩,⟨m,t2⟩를 계산해 더 큰 값을 선택하고 그 값이 최종 기여가 된다. 이 구조는 동일 의미를 가진 다양한 표현 중 단 하나의 최상 매칭만 기여하도록 하므로 OR 성질을 구현한다.

Theorem 3.1의 구성에서는 각 좌표 i에 대해 쿼리 측 임베딩을 u_i ϕ(i)로 두고 문서 측에는 다항식 계수 c(i,v_i)를 배치한다. 다항식 p(x)=c^T φ(x) 는 p(i)=v_i 이고 다른 정수 인덱스에서는 음수가 되게 설계된다. 변수 의미는 i가 좌표 인덱스, u_i와 v_i가 각 좌표의 값, ϕ(i)=(1,i,i^2)^T 가 임베딩 맵이다. 계산 흐름은 u_i ϕ(i)와 각 c(j,v_j) 간의 내적을 계산하면 u_i p(i) 혹은 음수 값을 얻게 되고 최대 연산은 정확한 인덱스 매칭만을 남긴다. 예로 u_i=2, v_i=3이면 해당 쌍의 기여는 6이 되고 다른 j≠i의 기여는 음수가 되어 0이나 음수로 배제된다.

Signed MaxSim 정의는 쿼리 쌍 (m,s_q)와 문서 쌍 (t,s_d)을 사용해 각 쿼리 벡터에 대해 최대를 내는 문서 벡터 t^(m)를 찾고 S_{±}는 ∑ s_q · s_d^(m) · ⟨m,t^(m)⟩ 를 계산한다. 변수 의미는 s_q와 s_d가 각각 쿼리와 문서 임베딩에 연관된 부호 또는 실수 가중치이고 t^(m)는 최대 내적을 유발하는 문서 벡터이다. 처리 흐름은 먼저 크기 기반의 최대 선택으로 매칭 인덱스를 결정하고, 그 후에 선택된 문서 쌍의 부호를 곱해 최종 기여를 결정한다. 작은 숫자 예로 |u_i|=2, |v_i|=3, sgn(u_i)=-1, sgn(v_i)=1 이면 내적 기여는 -6 이 되어 음수 기여가 반영된다.

내적 복원 불가능성 증명은 행렬 랭크 제약을 이용한다. 한스팍(one-sparse) 벡터들에 대해 각 입력 의존적 임베딩이 하나씩 존재할 때 얻어지는 유사도 행렬이 대각행렬이 됨을 보이고, 이 행렬의 랭크가 임베딩 차원보다 커질 수 없음을 이용해 n≤M 제약을 도출한다. 변수 의미는 n이 원래 공간의 표준기저 개수, M이 임베딩 차원이다. 계산 흐름은 쿼리와 문서의 내적 행렬을 U V^T 형태로 보고 rank(UV^T)≤M 이므로 원래 단위 행렬을 복원하려면 n≤M 여야 함을 보이는 식이다. 이 결과는 단일 고정 차원 내적이 고차원 희소 내적을 정확히 보존할 수 없음을 수학적으로 고립시킨다.

한계점

표준 MaxSim은 부호 정보를 매칭 이전에 합성하므로 임의 실수값 벡터의 내적을 고정 임베딩 차원에서 희소성 보존 조건과 함께 정확히 복원할 수 없다는 이론적 한계가 존재한다. 실험 구현에서는 Fallon의 Signed MaxSim이 유의미한 성능 향상을 보였지만 전체 검색을 이용한 정확 점수 계산을 사용했으므로 대규모 환경에서의 근사 인덱싱 기법과의 직접 호환성은 논문 범위 밖으로 남아 있다. 학습 안정성 측면에서 Signed MaxSim 구현은 임베딩 정규화와 가중치 생성 설계가 학습 신호에 민감하여 추가적인 정규화 또는 최적화 기술이 필요할 수 있음을 보고했다.

실무 활용

Signed MaxSim은 부정이나 제외 조건을 명시적으로 포함하는 쿼리에서 문서를 적절히 패널티하기 위한 구조적 수단을 제공한다. 이로 인해 도메인 변화나 어휘 차이가 큰 환경에서 기존 MaxSim 기반 시스템보다 더 견고한 순위 결과를 산출할 가능성이 높다. 다만 본 연구에서는 지표 검증을 위해 전체 검색을 통한 정확한 점수 계산을 사용했으므로, 대규모 인덱스에서의 근사 검색 알고리즘 설계가 추가로 필요하다.

검색 시스템에서 부정 조건이 포함된 자연어 쿼리를 정확히 처리해야 하는 상황
도메인 외 일반화와 긴 꼬리 어휘를 많이 포함하는 코퍼스에서의 견고한 순위 확보
동의어·유사어 그룹을 단일 절로 묶어 과도한 중복 보상을 피하려는 랭킹 설계

코드 공개 여부: 비공개

키워드

MaxSim(MaxSim 유사도)Signed MaxSim(Signed MaxSim)Late-Interaction(후반 상호작용)k-sparse vector(k-희소 벡터)Conjunctive Normal Form(합취형 논리식)

용어 해설

MaxSim 유사도(MaxSim): — 쿼리와 문서를 각각 여러 개의 토큰 임베딩 집합으로 표현한 뒤, 각 쿼리 임베딩에 대해 문서 임베딩 집합에서의 최대 내적을 합산하는 유사도 연산이다. 각 쿼리 토큰이 문서에서 가장 잘 맞는 토큰만 기여하게 하여 동의어나 대체 표현을 단일 매칭으로 처리하는 성격을 가진다. 계산은 쿼리 집합을 순회하며 각 쿼리 벡터마다 문서 집합에서 최대값을 선택하는 방식으로 이루어지며, 희소 표현을 보존하는 장점이 있다.
부호 분리 MaxSim(Signed MaxSim): — 기존 MaxSim의 최대 연산을 유지하되 각 임베딩에 부호(sign)를 별도로 저장하여 최대 선택 이후에 부호를 곱해 최종 기여를 복원하는 확장 기법이다. 크기와 부호를 분리해 크기로 매칭을 결정하고 부호로 양·음 기여를 반영하므로 부정 쿼리나 음수 내적을 정밀하게 처리할 수 있다. 이 방식은 실수값 벡터의 내적을 희소성 보존 조건 하에서 정확히 재현할 수 있도록 설계되었다.
후반 상호작용(Late-Interaction): — 쿼리와 문서를 토큰 단위로 분해하여 각 토큰마다 별도 임베딩을 생성하고, 최종 유사도는 토큰 임베딩 사이의 집합 연산으로 계산하는 검색 아키텍처 범주를 가리킨다. 단일 벡터 방식과 달리 토큰 수준 정보를 유지하므로 희귀 용어나 긴 꼬리 표현을 보존하기에 유리하다. ColBERT가 대표적인 예로, MaxSim 계열 유사도를 사용해 토큰 매칭을 집계한다.
k-희소 벡터(k-sparse vector): — 차원은 매우 크거나 무한해도 비제로 성분의 개수가 최댓값 k로 제한된 벡터를 뜻한다. 검색 문맥에서는 문서나 쿼리에서 실제로 등장하는 키워드 개수가 k 이하인 경우를 모델링하며, 이 희소성은 표현 축소와 매칭 설계에서 핵심 역할을 한다. 논문에서는 이러한 k-희소 벡터의 내적을 소수의 저차원 임베딩 집합으로 정확히 재현하는 가능성을 중심으로 다루었다.
합취형 논리식(Conjunctive Normal Form): — 여러 개의 OR 절을 AND로 연결한 형태의 논리 표현으로, 검색에서는 각 절이 하나 이상의 대체 표현을 포함하고 모든 절을 만족하는 문서를 찾는 방식으로 해석된다. 본문에서는 MaxSim이 절별로 최대를 취해 OR 역할을 수행하고 절들의 합을 통해 CNF 평가와 순위 동치성을 얻을 수 있음을 구축했다. 이 정리는 동의어 처리와 절 기반 사용자 의도를 순위 계산에 직접 반영하는 근거가 된다.

후반 상호작용 검색 모델의 이론적 표현력 정량화와 Signed MaxSim 확장

왜 중요한가

핵심 기여

핵심 아이디어 이해하기

방법론

주요 결과

기술 상세

한계점

실무 활용

키워드

용어 해설

관련 토론

댓글

관련 기사

5천 문서에서는 HNSW보다 완전탐색이 빨랐다

왜 중요한가

핵심 기여

핵심 아이디어 이해하기

방법론

주요 결과

기술 상세

한계점

실무 활용

키워드

관련 토론

댓글

관련 기사

5천 문서에서는 HNSW보다 완전탐색이 빨랐다