Efficient Vector Search in the Wild: One Model for Multi-K Queries

이 논문은 다양한 K 값의 벡터 검색 쿼리에 대해 높은 정확도와 성능을 유지하면서도 전처리 비용을 크게 절감하는 새로운 학습 기반 검색 방법인 OMEGA 를 제안합니다.

핵심

🌟 OMEGA: "한 번만 배우면 모든 걸 해결하는" 지능형 검색의 새로운 시대

이 논문은 벡터 데이터베이스(Vector Database)에서 일어나는 복잡한 검색 문제를 해결하는 새로운 방법, OMEGA를 소개합니다.

쉽게 말해, **"하나의 모델로 모든 상황 **(K 값)을 만드는 기술입니다.

---

🧐 문제: 왜 기존 방식은 힘들었을까요?

벡터 검색은 마치 **"가장 비슷한 사진 10 장을 찾아달라" **(K=10)거나 **"가장 비슷한 사진 1 장만 찾아달라" **(K=1)는 요청을 처리하는 것과 같습니다.

기존의 지능형 검색 시스템 (학습된 모델) 은 다음과 같은 치명적인 약점이 있었습니다:

1. 한 가지 상황에만 특화됨: "사진 10 장을 찾아주는 법"을 배운 모델은 "사진 1 장만 찾아달라"는 요청을 받으면 엉뚱하게 많은 사진을 뒤적거리느라 시간이 오래 걸립니다. 반대로 "1 장"을 찾아주도록 훈련된 모델은 "10 장"을 찾으려 할 때, 필요한 만큼 뒤적이지 않아 정확한 답을 놓쳐버립니다.
2. 훈련 비용이 너무 비쌈: 모든 경우의 수 (K=1, K=10, K=100 등) 에 맞춰 모델을 따로따로 훈련시키려면, 데이터베이스를 준비하는 시간 (전처리 시간) 이 2 배, 3 배 이상 늘어납니다. 이는 마치 식당이 메뉴 하나하나마다 별도의 주방을 꾸미는 것과 같아 비효율적입니다.

💡 해결책: OMEGA 의 마법 같은 아이디어

OMEGA 는 이 문제를 두 가지 핵심 아이디어로 해결합니다.

1. "1 등만 찾는 법"을 배워, 모든 순위를 예측하다 🏆

OMEGA 는 K=1(가장 가까운 것 1 개만 찾기)만 훈련합니다.

• 비유: 마치 "가장 맛있는 음식 하나를 찾는 법"을 완벽하게 배운 미식가입니다.
• 작동 원리: 이 미식가가 "가장 맛있는 음식 3 개를 찾아줘"라고 하면, 다음과 같이 합니다.
  1. 가장 맛있는 음식 (1 등) 을 찾습니다.
  2. 그 음식을 식탁에서 **가려둡니다 **(마스크).
  3. 남은 음식들 중에서 다시 "가장 맛있는 것"을 찾습니다 (이게 2 등).
  4. 다시 가리고, 또 찾습니다 (이게 3 등).
• 핵심: "1 등만 찾는 법"을 알면, 가려진 상태에서도 다음 순위를 찾을 수 있다는 것입니다. 기존 모델들은 '거리'라는 숫자만 보고 판단했는데, OMEGA 는 **거리가 어떻게 변해가는지 **(궤적, Trajectory)를 보고 판단하므로, 가려진 음식이 있어도 방향을 잃지 않습니다.

2. "통계적 예측"으로 불필요한 검색을 줄이다 🔮

매번 모델을 호출해서 "이게 1 등일까?"라고 물어보면 시간이 걸립니다. OMEGA 는 통계적 법칙을 이용합니다.

• 비유: 예측 가능한 날씨처럼 생각하세요. "지금까지 20 개의 후보를 봤는데, 100 번째 후보가 나올 확률은 50% 정도야"라는 통계 테이블이 미리 준비되어 있습니다.
• 작동 원리: 모델을 계속 호출할 필요 없이, "지금까지 찾은 결과만 봐도 통계상 100 개를 다 찾았을 확률이 충분해!"라고 판단되면, 검색을 바로 멈춥니다. 이렇게 하면 모델을 부르는 횟수를 크게 줄여 속도를 높입니다.

---

🚀 OMEGA 가 가져온 변화

이 기술은 실제 알리바바 (Alibaba) 의 데이터베이스와 여러 공개 데이터셋에서 테스트되었습니다.

• ⚡ 속도: 기존 최신 기술보다 6~33% 더 빠릅니다. (같은 정확도를 유지하면서)
• 💰 비용: 모델을 훈련시키는 데 드는 시간 (전처리 비용) 을 기존의 16~30% 수준으로 줄였습니다.
• 🎯 유연성: "1 개를 찾아줘"든 "1,000 개를 찾아줘"든, 하나의 모델로 모두 처리할 수 있습니다.

📝 한 줄 요약

OMEGA는 "가장 가까운 것 하나만 찾는 법"을 완벽하게 익힌 뒤, 가려진 상태에서도 다음 순위를 찾아내는 능력과 통계적 예측을 결합하여, 하나의 모델로 모든 검색 요청을 빠르고 정확하게 처리하는 혁신적인 기술입니다.

이제 벡터 검색은 더 이상 "하나의 상황에 맞춰 훈련된 딱딱한 시스템"이 아니라, 어떤 상황에도 유연하게 적응하는 똑똑한 비서가 된 것입니다! 🤖✨

기술 요약

1. 문제 정의 (Problem Statement)

벡터 데이터베이스는 추천 시스템, RAG(검색 증강 생성) 등 다양한 분야에서 핵심 역할을 하고 있으며, 근사 최근접 이웃 검색 (ANNS) 이 주요 연산입니다. 기존 그래프 기반 인덱스 (HNSW 등) 는 고정된 검색 예산 (search budget) 을 사용하여 모든 쿼리에 동일한 깊이의 검색을 수행합니다. 이는 다음과 같은 딜레마를 초래합니다.

• 정확도 - 지연 시간 트레이드오프: 고정된 예산은 일부 쿼리에는 과검색 (over-search, 지연 시간 증가) 을, 다른 쿼리에는 과소검색 (under-search, 정확도 저하) 을 유발합니다.
• 학습 기반 검색 (Learned Search) 의 한계: 최근 학습된 모델 (예: DARTH, LAET) 은 특정 $K$값 (결과 개수) 에 대해 검색을 조기 종료하여 지연 시간을 줄이고 정확도를 유지하는 데 성공했습니다.
• 실제 환경의 Multi-K 문제: 실제 클라우드 환경 (알리바바 등) 에서는 하나의 컬렉션이 다양한 $K$값을 가진 쿼리를 처리합니다.
  • 특정 $K$로 훈련된 모델은 다른 $K$에 적용 시 정확도 저하 (더 큰 $K$의 경우) 또는 성능 저하 (더 작은 $K$의 경우, 과검색 발생) 를 겪습니다.
  • 모든 $K$에 대해 별도의 모델을 훈련하거나 하나의 모델이 모든 $K$를 커버하도록 훈련시키려면 전처리 비용 (Preprocessing cost) 이 기하급수적으로 증가합니다. 이는 실제 배포에 치명적입니다.

2. 제안 방법론: OMEGA

저자들은 OMEGA(One-Model Efficient Generalized ANNS) 를 제안합니다. 이는 단일 모델 ($K=1$) 만 훈련하여 임의의 $K$ 쿼리에 대해 높은 정확도와 낮은 지연 시간을 달성하는 $K$-일반화 가능한 (K-generalizable) 학습 기반 검색 방법입니다.

핵심 아이디어

1. Top-1 모델의 재사용 및 동적 정제 (Dynamic Refinement):

   • $K=1$ (최상위 1 개) 에 대해 훈련된 모델을 기반으로, $K$개의 결과를 찾기 위해 $K$번의 Top-1 검색을 반복 수행합니다.
   • 마스크 (Masking) 기법: 이미 찾은 Top-1 벡터를 검색 공간에서 가리고 (마스크), 남은 벡터들 중에서 새로운 Top-1 을 찾음으로써 Top-2, Top-3... Top-K 를 순차적으로 도출합니다.
   • 이는 Top-K 문제를 $K$개의 Top-1 문제로 환원시키는 전략입니다.

2. 도전 과제 해결:

   • 과제 1: 효과적인 베이스 모델 훈련 (Feature Engineering):
     • 기존 모델 (DARTH 등) 이 사용하는 '최소 거리 (minimal distance)' 같은 특징은 마스크가 적용된 후 (Top-1 을 찾은 후) 신뢰도가 떨어집니다.
     • 해결책: 거리 궤적 (Distance Trajectory) 특징을 도입합니다. 검색 과정에서 방문한 벡터들의 거리 감소 추이 (pattern) 는 Top-1 이든 Top-2(마스크 후의 Top-1) 이든 유사한 패턴을 보입니다. 이 궤적 특징을 학습하면 마스크가 적용된 상태에서도 모델이 일반화되어 작동합니다.
   • 과제 2: 모델 호출 오버헤드 감소:
     • $K$개의 Top-1 을 찾기 위해 모델을 $K$번 호출하면 오버헤드가 커질 수 있습니다.
     • 해결책: 통계적 예측 (Statistical Forecast) 을 사용합니다. 현재까지 찾은 Top-N 개의 결과가 주어졌을 때, 나머지 Top-K 결과가 검색 집합에 포함될 확률 분포를 오프라인에서 프로파일링 (Lookup Table) 합니다.
     • 모델 호출 없이 이 통계적 확률만으로 목표 Recall 을 달성할 수 있다고 판단되면 검색을 조기 종료합니다.

시스템 아키텍처

• 오프라인 (전처리): 인덱스 압축 (Compaction) 시 Top-1 모델만 훈련하고, 통계적 확률 테이블을 생성합니다.
• 온라인 (서빙): 쿼리가 들어오면 Top-1 모델을 사용하여 순차적으로 Top-K 를 찾되, 통계적 예측을 통해 불필요한 모델 호출과 검색 단계를 생략합니다.

3. 주요 기여 (Key Contributions)

1. 최소 전처리 비용으로 Multi-K 지원: 기존 방식은 여러 $K$에 대한 모델을 훈련하거나 큰 $K$를 커버하는 모델을 훈련해야 했으나, OMEGA 는 단일 Top-1 모델 훈련 시간만으로도 임의의 $K$를 지원합니다. 이는 전처리 비용을 기존 대비 16~30% 수준으로 획기적으로 줄입니다.
2. 거리 궤적 (Distance Trajectory) 특징의 발견: 마스크가 적용된 상태에서도 일반화되는 새로운 특징을 발견하여, Top-1 모델을 Top-K 검색에 효과적으로 재사용할 수 있게 했습니다.
3. 통계적 예측을 통한 오버헤드 최적화: 모델 호출 횟수를 줄이기 위해 확률 분포 기반의 예측 로직을 도입하여, 불필요한 검색 단계를 제거했습니다.
4. 오픈소스 및 실제 배포: OMEGA 는 오픈소스로 공개되었으며, 알리바바의 오픈소스 벡터 데이터베이스인 Zvec에 통합되고 있습니다.

4. 실험 결과 (Results)

알리바바의 실제 프로덕션 데이터셋과 공개 데이터셋 (BIGANN, DEEP, GIST 등) 에서 다양한 Multi-K 트레이스를 사용하여 평가했습니다.

• 지연 시간 (Latency):
  • 동일한 전처리 비용 (Single K 모델 훈련) 기준: 기존 학습 기반 방법 (DARTH, LAET) 대비 6~33% 낮은 평균 지연 시간을 달성했습니다.
  • 최적의 지연 시간 달성 시: 기존 방법들이 최적의 성능을 내기 위해 필요한 전처리 시간의 16~30% 만으로 달성했습니다.
• 정확도 (Recall):
  • 모든 $K$값에 대해 목표 Recall(0.95) 을 유지했습니다. 기존 방법들은 $K$가 커질수록 정확도가 떨어지거나, $K$가 작을 때 과검색으로 인해 지연 시간이 증가하는 문제가 있었습니다.
• 총 CPU 비용:
  • 전처리 비용은 낮고 서빙 비용 (지연 시간 감소) 이 낮아, 전체적인 CPU 사용량 (전처리 + 서빙) 을 기존 방법 대비 4~24% 감소시켰습니다.
• Ablation Study:
  • 거리 궤적 특징이 일반화 성능에 결정적임을 확인했습니다.
  • 통계적 예측 (Forecast) 기법이 모델 호출 횟수를 줄여 지연 시간을 추가로 22~49% 개선함을 보였습니다.

5. 의의 및 결론 (Significance)

OMEGA 는 "실제 환경 (In the Wild)" 에서 발생하는 복잡한 Multi-K 벡터 검색 문제를 해결하는 첫 번째 솔루션입니다.

• 경제성: 벡터 데이터베이스 제공자들은 전처리 비용 (인덱스 컴팩션 및 모델 훈련) 을 사용자에게 청구하지 않는 경우가 많습니다. OMEGA 는 이 비용을 최소화하면서도 높은 성능을 제공하여 서비스 비용을 절감합니다.
• 실용성: 단일 모델로 다양한 $K$를 처리함으로써 시스템의 복잡성을 줄이고, 동적인 워크로드 변화에 유연하게 대응할 수 있습니다.
• 기술적 진보: 학습된 모델이 특정 $K$에 국한되지 않고, 통계적 특징과 재사용 전략을 통해 범용적으로 작동할 수 있음을 증명했습니다.

결론적으로, OMEGA 는 학습 기반 벡터 검색의 실용성을 한 단계 높여, 대규모 클라우드 환경에서 고품질의 벡터 검색 서비스를 가능하게 하는 중요한 기술적 도약입니다.