- Apple 연구진이 고정된 벡터 데이터베이스와 실제 질의 분포를 바탕으로 작은 신경망을 미리 학습해 최대 내적 검색(MIPS) 의 추론 속도와 정확도를 높이는 방법을 개발함
- 기존 중심점 기반 검색은 클러스터 내부의 최적 키를 놓칠 수 있음. SupportNet은 클러스터별 최상의 일치 점수를 예측해 질의를 더 적합한 클러스터로 보냄
- KeyNet은 질의를 최적 키에 가까운 벡터로 변환해 기존 IVF 인덱스에 전달함. Natural Questions 실험에서 대형 모델은 질의 변환 시간을 포함해 99% 재현율에 도달하는 시간을 최대 약 8배 단축함
- 이 접근은 모든 가능한 입력보다 실제로 들어오는 질의 분포에 맞춰 검색을 최적화함. 고정된 키 집합에 대한 일회성 학습 비용을 부담하는 대신 반복 검색 비용을 줄임
- 추론 속도가 병목이면 KeyNet, 재순위화나 임곗값 처리에 쓸 보정된 점수도 필요하면 SupportNet이 적합함
- 최대 내적 검색(MIPS) 은 추천 시스템, 검색, 검색 증강 생성(RAG)의 핵심 연산으로, 질의 벡터와 가장 잘 맞는 키 벡터를 데이터베이스에서 찾음
- 검색된 키에 연결된 원본 데이터를 질의 처리에 사용하며, RAG에서는 보통 질문에 가장 적합한 문서를 질의 앞에 붙임
- 키가 수백만 개, 벡터 차원이 수천 개로 늘면 전수 비교 비용이 크게 증가함
- 기존 근사 방법은 클러스터링과 양자화로 정확도와 속도를 절충함
- 주로 키 집합의 기하학적 특성으로 인덱스를 만들며, 질의가 키와 유사하다고 느슨하게 가정하거나 질의 특성을 고려하지 않음
- RAG의 짧은 사용자 질문과 길고 정보가 풍부하며 선별된 문서를 나타내는 키는 상당히 다름
- 실제 서비스의 많은 MIPS 시스템은 안정적이고 특성이 잘 알려진 질의 분포를 가진 기존 사용자층을 대상으로 하지만, 질의에 무관한 범용 방법은 이 신호를 활용하지 못함
- 가능한 모든 입력보다 자주 들어올 입력에 맞춰 방법을 설계하면 계산 자원을 더 효율적으로 배분할 수 있음
- ICML 2026 발표 논문 Amortizing Maximum Inner Product Search with Learned Support Functions의 방법은 고정된 키 데이터베이스에 대해 작은 신경망을 오프라인에서 한 번 학습함
- 전형적인 질의가 어떤 키에 대응하는지 미리 학습하는 비용을 지불하고, 추론 시 더 빠르고 정확하게 검색함
- 일반적인 MIPS 시스템은 키 n개를 훨씬 적은 수인 k개 클러스터로 나누고, 질의를 각 중심점과 비교한 뒤 유망한 클러스터 내부를 전수 검색함
- 클러스터 크기가 균등하다면 두 번째 단계의 비교 대상은 약 n/k개로, 이 단계는 전체 n개 비교보다 약 k배 적은 연산이 필요함
- 하지만 중심점에 의한 라우팅은 정확한 방법이 아님
- 클러스터 중심점만으로는 내부 키의 분포를 반영할 수 없음
- 자신의 중심점에서 멀리 떨어진 키가 질의와는 가까울 수 있음
- 이때 해당 클러스터의 중심점 점수가 낮으면 클러스터를 건너뛰어 실제 최적 키를 놓침
- 질의를 키 집합 내 최대 내적 값으로 매핑하는 함수는 볼록해석에서 연구해 온 지지 함수(support function) 임
- 볼록 함수이므로 입력 볼록 신경망(ICNN) 으로 근사할 수 있음
- 질의 위치에서 지지 함수의 기울기는 최적 일치 키를 반환함
- 각 클러스터의 정확한 지지 함수를 알면, 중심점과의 거리 대신 그 클러스터 안의 어떤 키가 질의와 얼마나 잘 맞는지에 따라 정확하게 라우팅할 수 있음
- 학습은 관련 질의 분포에서 입력을 표본 추출하고, 전수 검색으로 최적 점수나 최적 키를 계산해 저장하는 방식으로 진행함
- 이렇게 만든 지도학습 데이터에 회귀를 적용해 신경망이 질의에서 정답 출력을 재현하도록 학습함
- 지지 함수를 완벽하게 근사한다면 같은 신경망에 자동 미분을 적용해 최적 키도 얻을 수 있음
- 실제 실험에서는 점수 예측과 키 예측에 각각 특화한 별도 신경망을 학습하는 편이 가장 효과적이었음
- SupportNet은 제약을 느슨하게 적용한 ICNN으로 지지 함수를 직접 학습함
- 문제의 볼록 구조에 부합하며, 클러스터별 지지 함수를 계산해 라우팅 품질을 높이는 데 강점이 있음
- KeyNet은 질의를 입력받아 최적 일치 키 벡터를 직접 예측함
- 볼록성을 명시적으로 강제하지는 않지만, 동차 함수에 대한 Euler 정리에서 유도한 일관성 손실로 예측이 지지 함수의 기하학적 구조를 따르도록 함
- 하나의 SupportNet이 k개 클러스터의 지지 함수를 함께 학습해 점수 k개를 한 번에 출력함
- 중심점과 얼마나 가까운지가 아니라, “이 클러스터의 최적 키가 이 질의에 얼마나 잘 맞는가”를 근사해 높은 점수의 클러스터로 라우팅함
- 실험에는 일반 상식 질문과 문서 구절을 연결한 검색 벤치마크인 Natural Questions 를 사용함
- 실험 데이터베이스는 고유 구절 약 260만 개, 클러스터 128개로 구성함
- 모델 크기 XS/S/M/L은 각각 데이터베이스 크기의 1%/5%/10%/20%이며, 깊이는 모두 16개 층임
- 라우팅 재현율은 실제 최적 키가 있는 클러스터가 탐색 대상으로 선택된 질의의 비율임
- 상위 s개 클러스터를 전수 검색하며 s를 1, 2, 4, 8, …, 128로 늘려 비교함
- 128개 클러스터를 모두 탐색하면 모든 방법의 재현율이 1에 도달함
- 신경망 실행 비용까지 포함한 비교에서 소형 SupportNet은 95% 라우팅 재현율에 1.74ms로 도달해 중심점 방식의 3.36ms보다 약 1.9배 빨랐음
- 대형 모델은 같은 1.74ms에 97% 재현율을 달성함
- 신경망 실행 비용을 제외하고 탐색 범위만 비교하면, 데이터베이스의 5% 를 검색할 때 학습 라우터의 재현율은 약 90~93%, 중심점 방식은 87.5%였음
- 중형 M 모델은 92.6%를 기록함
- 실험에서 SupportNet은 같은 지연시간에 더 높은 재현율을, 또는 같은 재현율에 더 낮은 지연시간을 제공함
- SupportNet이 역파일 인덱스(IVF)의 중심점 라우팅을 대체하는 반면, KeyNet은 기존 IVF를 유지한 채 앞단에서 질의 재작성을 수행함
- 최적 키가 있을 것으로 예측한 임베딩 위치로 질의를 변환한 뒤, 최적화된 IVF 인덱스가 그 위치를 검색하게 함
- 학습에는 표본 질의와 전수 검색으로 구한 최적 키의 쌍을 사용함
- KeyNet도 XS/S/M/L을 데이터베이스 크기의 1%/5%/10%/20% 로 구성하고, 모두 16개 층으로 평가함
- 지연시간에는 질의 변환과 검색을 모두 포함하며, 원본 질의 기준선에는 검색 시간만 포함함
- 대형 모델은 99% 재현율에 0.23ms로 도달해 원본 질의의 1.8ms 대비 최대 약 8배 빨랐음
- 평가한 모든 크기에서 이후 검색의 속도 향상이 전처리 비용을 상쇄함
- 데이터베이스의 0.001% 만 탐색할 때 KeyNet 변환 질의의 재현율은 89~97%, 원본 질의는 86%였음
- 대형 L 모델은 96.7%를 기록함
- 99% 재현율에 필요한 탐색 비율은 0.009%로, 원본 질의의 0.10%보다 탐색 키 수가 최대 약 11배 적었음
- Natural Questions를 FAISS IVF 로 검색한 실험에서는 전체 검색 예산 범위에서 KeyNet의 예측 키를 사용하는 편이 원본 질문보다 우수했음
- 연구한 다른 데이터셋에서도 같은 추세를 확인함
- 정성적 비교로 질문 “What is Matchbox Twenty?”를 포함한 Natural Questions 사례 5개의 원본 질의와 변환 질의의 상위 3개 검색 결과를 비교함
- KeyNet은 추론 속도가 병목이고 최적 키의 근사치만 필요할 때 적합함
- SupportNet은 재순위화, 임곗값 처리, 후속 작업에 사용할 보정된 점수가 필요하거나, 작은 모델을 써야 할 만큼 계산 자원이 제한적일 때 경쟁력이 있음
- 두 모델은 유사한 방식으로 학습하고 기존 근사 검색 인프라에 통합할 수 있으며, 질의 패턴의 완만한 분포 변화에도 비교적 견고함
- 키 집합이 매우 큰 시스템에서는 두 모델의 결합이 필요할 수 있음
- 전체 클러스터를 대상으로 SupportNet 라우터를 학습하고, 각 클러스터에 KeyNet을 하나씩 두어 기존 인덱스의 검색을 가속하는 구성임
- 비용 상각형 MIPS(amortized MIPS) 는 질의 분포를 미리 아는 환경에서 검색 해법을 신경망 가중치에 저장함
- 일회성 학습 비용을 빠르고 가벼운 추론과 교환하며, 실제 처리할 질의에 맞춘 학습 기반 검색 시스템을 구현하는 접근임