벡터 검색 성능: 리콜의 부상

기존 검색 패러다임에 거리 기반 유사도 점수를 사용하는 벡터 검색(KNN)을 도입하려면 '관련성 있는' 결과에 대한 사고 방식과 이를 측정하는 방법에 변화가 필요했습니다. 

텍스트 기반 인덱스 사용 TF-IDF 를 채점 메커니즘으로 사용하며, 고정된 단어 모음(여기서는 파티션에 있는 문서)이 주어지면 검색 결과가 여러 검색에서 동일하게 유지됩니다.

반면, KNN 검색은 동일한 수준의 무능력. 결과는 다음과 같습니다. 대략적인쿼리마다 다른 경우가 많습니다. 이 문서에서는 정확한 검색에서 대략적인 검색으로 전환하는 검색 팀에 대해 설명합니다. 그 과정에서 그 이유에 대한 질문에 답합니다. 대략적인 결과가 새로운 표준이 될 수 있습니다. 그리고 어느 정도의 근사치가 허용되는지 알아보세요.

무대 설정 

각 검색 인덱스 파티션은 Bleve 인덱스는 여러 개의 잽 세그먼트로 구성됩니다(세분화된 아키텍처), 각 세그먼트에는 벡터 인덱스가 포함됩니다. 이들은 블레브 인덱스에 대한 병합 루틴에 의해 주기적으로 압축됩니다.

검색 용도 FAISS 를 사용하여 벡터 인덱스 생성, 학습, 검색 및 기타 관련 기능을 사용할 수 있습니다. 

현재 카우치베이스 검색에서 사용하는 인덱스는 크게 두 가지 클래스입니다:

1. 1. 플랫 인덱스 - 배열에 벡터를 저장하는 것과 비슷한 방식으로 전수 검색을 수행합니다.
   2. IVF 인덱스 - 중심 기반 인덱스는 데이터 집합을 클러스터링(이 경우 KMeans)한 다음 해당 클러스터를 채우는 작업을 포함합니다.

KNN 소개 

앞서 언급했듯이, 테스트 소프트웨어(그리고 마찬가지로 중요한 우리의 사고방식!)는 정확한 점수를 매기는 경향이 있었습니다. 텍스트 기반 검색은 근본적으로 철저한 반전된 인덱스는 파티션의 문서에 있는 모든 토큰을 포함한다는 점에서 다릅니다. 반전된 인덱스의 모든 문서는 다음과 같습니다. 적격 를 입력하면 검색됩니다. 

이에 비해 구심점 기반 벡터 인덱스입니다, 적격 벡터 풀을 제한합니다. 각 쿼리마다 동일할 수도 있고 그렇지 않을 수도 있는 특정 클러스터만 검색하여 바로 검색할 수 있습니다. 즉, 주어진 쿼리에 대해 잠재적으로 시간이 많이 소요되는 전수 검색을 근사치 검색과 교환할 수 있습니다.  

('리콜'이라는 단어에 잠시 당황했다면 잠시만 기다려 주세요. 곧 설명해 드리겠습니다).

처음에 검색 공간을 제한한다는 점을 고려할 때 '올바르게 클러스터링'하는 것이 중요합니다. 

검색의 첫 번째 단계 중 하나는 검색할 클러스터의 수와 클러스터를 선택하는 것입니다. 클러스터 수가 너무 적으면 잠재적으로 유사한 벡터를 놓칠 수 있습니다. 클러스터 수가 너무 많으면 검색 품질은 상대적으로 조금 향상되지만 검색 대기 시간이 크게 늘어납니다. 

검색 품질에 사용되는 메트릭은 다음과 같습니다. 리콜 - 반환된 결과 중 객관적으로 쿼리 벡터에 가장 가까운 결과가 몇 퍼센트인지를 나타냅니다. 쿼리 벡터에 가장 가까운 벡터 집합을 기준 진실이라고 하며, 회상도를 측정할 때 기준선으로 사용됩니다. KNN 점수는 두 벡터 사이의 거리이므로 다음과 같습니다. 다른 문서와 독립적으로 를 파티션에 포함시킬 수 있으며, 더 중요한 것은 독립적으로 평가된 실측 데이터와 결과를 객관적으로 비교할 수 있다는 점입니다. 

너무 많은 양(근사치): 0.06에서 90+까지 주행 리콜:

이 모든 지식으로 무장한 저희는 리콜 테스트를 시작하기로 결정했습니다. 초기 테스트 결과, 정확히 0~0.06에 가까운 놀랍도록 낮은 리콜률을 보였습니다. 

벡터 인덱스 검색을 FAISS에 오프로드했지만, 우리 쪽에서 처리해야 할 몇 가지 측면이 있었습니다. 그 중 하나가 문서 ID를 벡터에 매핑하는 것이었습니다. 검색은 각 문서 번호를 고유한 벡터 해시에 매핑합니다. 이 해시는 다음과 같이 전달됩니다. FAISS에 대한 사용자 지정 ID 를 사용하여 벡터를 사용자 정의 ID에 매핑하는 기능을 활용하면 검색 시 사용자 정의 ID가 반환됩니다. 벡터(각각 크기가 같은)가 큰 벡터로 연결되고 ID도 연결된다는 점을 고려할 때, 순서를 올바르게 지정하면 벡터와 ID의 매핑이 결정됩니다. 내부적으로 FAISS는 해시맵을 사용하여 벡터와 해당 ID를 저장합니다.

자세히 살펴보니 병합 중에 인덱스를 재구축할 때 무작위로 정렬된 ID를 벡터에 매핑하고 있었기 때문에 결과 집합이 본질적으로 무작위로 생성되었습니다. 이는 플랫 인덱스와 IVF 인덱스 모두에 영향을 미쳤습니다. 주문 를 사용하여 결과를 검색할 수 있습니다. 

다른 병합 경로 수정과 함께 주문 문제가 해결되자 리콜 건수는 약 70건으로 급증했습니다. 이제 우리는 올바른 방향으로 나아가고 있었고, 우리를 괴롭히는 근본적인 버그는 없었습니다. 저희는 조정할 수 있는 노브를 살펴보기 시작했습니다. 

회전 손잡이 - 센트로이드 및 N프로브

초기 전략은 1만 개 이상의 벡터를 가진 모든 벡터 인덱스에 대해 고정된 수(100개)의 중심을 사용했습니다. 이는 본질적으로 1백만 개의 벡터를 2만 개의 벡터와 동일하게 취급하는 것이었습니다.

FAISS 클러스터링 기본값은 클러스터당 최소(39개) 및 최대(256개) 포인트 수입니다. 나머지 포인트는 서브샘플링됩니다. 최대 100 * 256 = 25600개의 벡터에는 100개의 센트로이드로 충분할 수 있지만 그 이상의 벡터에는 과도한 리콜에 반영된 것처럼 서브샘플링이 일어나고 있었습니다. 우리에게 필요한 것은 데이터 집합에 따라 확장되는 중심값에 대한 공식이었습니다.

최적화하고자 하는 대상: Recall@K인덱싱과 검색 대기 시간이 너무 길어지지 않도록 하세요. 

설정

설정은 매우 간단했습니다. 스크립트를 통해 FAISS 인덱스를 생성하고(훈련 및 ID 추가) 쿼리하는 방식으로, 미리 알고 있는 실측 결과를 사용했습니다. 저는 SIFT10K 및 SIFT1M 데이터 세트의 원본 종이 유클리드 거리를 사용하여 실측 벡터를 제공했기 때문입니다. recall@K는 각각 100/10만 개 이상의 쿼리에 대한 평균 호출 횟수입니다.

구심점 증가

첫 번째 단계는 클러스터 수를 조정하는 것이었습니다.

Sift1M 결과 - 10,000건의 쿼리

Sift10k 결과 - 100개의 쿼리

인사이트

1. 1. 현재 기준선은 0.61의 리콜을 보여 주며, 이는 확실히 개선될 수 있습니다.
   2. 리콜 감소 센터로이드 수가 증가합니다. 
   3. 검색 시간이 줄어드는 이유는 다음과 같습니다. 현지화 강화 교육 시간이 늘어나는 경우에도 마찬가지입니다.

반대로 더 많은 수의 벡터가 있는 더 큰 셀에서 검색해야 하므로 훈련 시간이 짧더라도 검색 시간이 길어집니다.

이제 중심이 증가하면 리콜에 부정적인 영향을 미친다는 사실이 밝혀졌으니, 왜 그런지 직관적으로 이해해 보겠습니다.

데이터 세트의 크기가 고정되어 있는 경우, 중심체의 수를 늘리면 각 클러스터의 문서 수가 줄어들 수 있습니다. 더 작은 클러스터를 사용하면 전체적으로 더 적은 수의 벡터 검색 를 클릭하고 가장 가까운 K 벡터를 선택합니다.

따라서 클러스터 수가 증가하면 그에 따라 검색되는 클러스터 수가 증가합니다.

n프로브 증가

Sift1M - 10,000건의 쿼리

Sift10k - 100개의 쿼리

인사이트

1. 1. 1M 데이터 집합의 경우 다음과 같은 이유로 기준 리콜이 낮습니다. nprobe = 1.
      • 이 문제가 해결되면 서브샘플링에도 불구하고 리콜이 빠르게 증가하여 더 이상 문제가 되지 않습니다.
      • 하지만, 기억력이 뛰어나면 검색 지연 시간도 길어집니다. 
   2. 10,000개 데이터 세트의 경우, 기준 리콜은 1백만 데이터 세트만큼 낮지는 않지만 여전히 우려되는 문제입니다.
      • 이 역시 쉽게 해결할 수 있는 문제입니다. nprobe. 

그런 다음 nlist 및 nprobe를 결정하는 기본값이 다음과 같이 변경되었습니다:

리콜 문제에 대한 해결책을 성공적으로 찾은 후 팀원들은 이렇게 느꼈습니다:

벡터 인덱스 조정하기

카우치베이스 벡터 인덱스를 조정하는 것은 결코 쉬운 일이 아닙니다.

벡터 검색에서 리콜/레이턴시 트레이드오프는 매우 중요한 문제이므로 사용자가 원하는 방식에 따라 어느 정도 유연성을 부여하고 싶었습니다. 이해하기 쉽고 직관적인 것과 같은 사용자 측면의 고려 사항과 함께, 미래 보장(이전 버전과의 호환성) 및 세그먼트화된 아키텍처는 API에 몇 가지 제한을 수반했습니다.

각 세그먼트는 서로 다른 수의 벡터를 가진 벡터 인덱스입니다. 쿼리 시점에 사용자가 데이터 배포를 인지하지 못하는 경우 를 세그먼트 수준은 말할 것도 없고 파티션 수준에서도 사용할 수 있습니다. 돌연변이의 특성(예: 삭제 횟수가 많은 경우)에 따라 벡터의 수는 상당히 다양할 수 있습니다. 세그먼트를 병합할 때 따라서 일률적인(- 세그먼트) 접근 방식을 적용할 수 없습니다..  

또한 이전 버전과의 호환성을 위해서는 노브는 FAISS 인덱스 유형에 특정되지 않습니다. 구현에 사용되는 인덱스 유형을 변경하더라도 대부분의 경우 사용자로부터 추상화되어야 하는 영역이기 때문입니다. 예를 들어, 사용자가 nprobe 또는 nlist 는 매우 IVF 인덱스에 특화되어 있으며 벡터 검색을 지원하는 인덱스 유형이 변경되면 큰 변화가 될 것입니다. 

사용자가 다음을 수행할 수 있도록 허용 최적화할 메트릭을 토글합니다. (리콜/지연)이 적합합니다. 리콜에 대한 튜닝은 IVF 인덱스와 HNSW 인덱스에 대해 다르게 수행되지만, 리콜은 둘 다에 적용 가능하며 세그먼트 수준에서 튜닝할 수 있습니다. 위의 데이터에서 n프로브를 두 배로 늘리면 검색 시간이 두 배로 늘어나지만 그에 상응하는 리콜 증가는 몇 포인트에 불과합니다. 따라서 지연 시간을 최적화할 때, 검색 시간을 절반으로 줄이려면 nprobe 를 사용하면 리콜에 큰 타격 없이 지연 시간을 개선할 수 있습니다. 

사용자가 리콜과 대기 시간 간에 전환할 수 있는 인덱스 정의 설정은 다음과 같습니다. 벡터_인덱스_최적화_포함. 이 설정은 공식 문서에 문서화되어 있습니다. 

카우치베이스 벡터 검색 공간에 대한 더 많은 심층 분석과 개발 소식은 계속 지켜봐 주세요!