SVS Vamana 및 Milvus를 이용한 검색

SVS (Scalable Vector Search)는 Vamana 그래프 알고리즘을 구현한 인텔의 고성능 벡터 검색 라이브러리입니다. Milvus에서는 FAISS 인덱스 패스스루를 통해 SVS Vamana를 이용할 수 있습니다. ` index_type `를 ` FAISS `로 설정하고 ` SVSVamana ` 인덱스 팩토리 문자열을 지정하면, Milvus는 Faiss의 SVS 통합 기능을 통해 인덱스를 구축하고 검색합니다.

Vamana는 DISKANN에서도 사용하는 그래프 구조이지만, SVS Vamana는 전체 그래프를 메모리에 유지합니다. 또한 LeanVec 또는 LVQ를 사용하여 벡터를 압축할 수 있어, 메모리 사용량을 줄이고 검색 속도를 높이는 동시에 매우 높은 리콜률을 달성할 수 있습니다.

필수 조건

• SVS가 활성화된 상태로 소스 코드에서 빌드된 Milvus 3.0.0 이상
• PyMilvus 3.0.0 이상
• LVQ* 또는 LeanVec* 스토리지를 사용하는 경우 Intel CPU가 필요합니다. FP32, FP16 및 SQ8 스토리지는 모든 플랫폼에서 실행됩니다.
• FAISS 인덱스 팩토리 문자열에 대한 이해

LVQ 및 LeanVec 압축은 Intel CPU에서만 실행되며, AVX-512를 지원하는 CPU에서 더 빠르게 실행됩니다. 다른 CPU에서는 LVQ* 및 LeanVec* 팩토리 문자열을 사용할 경우 인덱스 생성이 실패합니다.

SVS Vamana의 작동 방식

Vamana 그래프

SVS Vamana는 단일 계층 근접 그래프를 구축합니다. 각 벡터는 노드이며, 가장 가까운 이웃일 가능성이 높은 벡터들을 연결하는 에지가 있습니다. 그래프를 구축하기 위해 SVS는 각 노드 x에 대해 다음을 수행합니다:

1. 탐욕적 탐색(Greedy search): SVS는 지금까지 구축된 그래프를 탐색하며, 크기 construction_window_size 인 후보 목록을 유지합니다.

2. 인접 노드 제거: 방문한 노드들은 x의 후보 인접 노드가 됩니다. SVS는 x로부터의 거리가 증가하는 순서대로 이 노드들을 고려합니다. 이미 유지된 더 가까운 이웃 n 이 alpha * distance(n, c) <= distance(x, c) 를 만족하는 경우, 후보 c 는 건너뜁니다. 이를 통해 장거리 에지는 유지하고 중복된 단거리 에지는 제거하므로, 검색은 가장 가까운 이웃을 하나씩 차례로 이동하는 대신 그래프를 가로질러 건너뛸 수 있습니다. 그래프의 차수에 도달하면 정리 작업이 중단됩니다.

3. 역방향 에지: x의 새로운 이웃마다 SVS는 x로 돌아가는 역방향 에지를 추가하고, 해당 이웃의 에지 목록이 그래프의 차수를 초과할 경우 이를 제거합니다.

가지치기는 두 단계로 진행됩니다. 첫 번째 단계에서는 ‘ alpha = 1 ’를 사용하고, 두 번째 단계에서는 설정된 ‘ alpha ’를 사용합니다. 그래프 도(degree)와 ‘ construction_window_size ’ 값이 클수록 더 조밀하고 품질이 높은 그래프가 생성되지만, 더 많은 메모리를 사용하고 구축하는 데 더 오랜 시간이 소요됩니다.

검색 시 SVS는 그래프를 탐욕적(greedy) 방식으로 탐색하며, 지금까지 확인된 가장 가까운 후보들을 ‘ search_window_size ’에 저장합니다. 다음에는 항상 가장 가까운 미방문 후보를 탐색합니다. 현재 노드의 모든 이웃이 쿼리로부터 ‘ search_window_size ’ 내 최악의 후보보다 더 멀리 떨어져 있을 때 검색이 종료됩니다. ‘ ’의 크기를 늘리면 그래프의 더 많은 부분을 탐색하게 되어 리콜률은 높아지지만, 지연 시간도 증가합니다.

LeanVec 압축

LeanVec은 벡터당 차원 수와 차원당 비트 수를 모두 줄입니다. LeanVec 인덱스는 각 벡터에 대해 두 가지 표현을 유지합니다:

• 1차(차원 축소): 벡터를 더 적은 차원으로 선형 투영한 것입니다. 그래프 검색은 이 1차 데이터셋을 대상으로 수행되므로, 대부분의 거리 계산은 저차원 공간에서 이루어집니다. 이를 통해 연산 및 메모리 대역폭 요구 사항이 모두 감소합니다. 기본적으로 차원 축소 비율은 원래 차원의 절반입니다(dim / 2).

• 보조(전체 차원): 벡터의 원래 차원입니다. SVS는 차원 축소로 인해 손실된 정확도를 회복하기 위해, 이 보조 데이터셋을 기준으로 1차 그래프 검색에서 반환된 후보들을 재순위화합니다.

두 표현 모두 LVQ (국소 적응형 벡터 양자화)를 통해 양자화됩니다. 팩토리 문자열의 저장소 구성 요소가 인코딩 방식을 선택합니다. 예를 들어, LeanVec4x8 는 1차 데이터셋의 경우 차원당 4비트를, 2차 데이터셋의 경우 차원당 8비트를 사용합니다. 재순위 지정 단계에서도 전체 정밀도 벡터를 읽지 않습니다.

기본적으로 LeanVec은 인덱싱된 벡터와 쿼리에 대해 별도의 투영을 학습하여, 인덱싱된 벡터와 다른 분포에서 비롯된 쿼리(분포 외, OOD)를 지원합니다. 이는 텍스트-이미지 검색과 같은 크로스 모달 워크로드에서 특히 효과적이며, 쿼리가 인덱싱된 벡터와 동일한 분포에서 비롯된 경우에도 잘 작동합니다. Milvus는 아직 투영 계산을 위해 쿼리를 전달하는 방법을 지원하지 않으므로, 현재는 기본 벡터만 사용됩니다. OOD 훈련은 빌드 시간을 증가시킵니다. 쿼리 성능을 다소 희생하더라도 빌드 속도를 높이려면 ` ood_training `을 ` False`로 설정하십시오.

LVQ 압축

차원이 약 512 미만인 데이터셋의 경우, 차원 축소를 생략하고 LVQ 양자화만으로 압축하는 것이 더 효과적일 수 있습니다. LeanVec과 마찬가지로, LVQ 인덱스는 빠른 검색을 위한 기본 표현과 재순위를 위한 잔차 표현을 유지합니다. 예를 들어, LVQ4x4 는 기본 표현에 4비트를, 잔차 표현에 4비트를 사용합니다. LVQ4x0 및 LVQ8x0 는 재순위 단계를 생략하므로, 리콜이 워크로드에 충분히 양호한 경우 쿼리 속도가 빨라집니다.

팩토리 문자열 선택

SVS Vamana 팩토리 문자열은 SVSVamana<degree>[,<storage>] 형식을 따르며, 여기서 <degree> 은 그래프 내 노드당 최대 에지 수를 나타냅니다.

SVSVamana64,LeanVec4x8 이는 좋은 출발점입니다. 그 다음에는:

• 메모리 비용을 어느 정도 감수하고 리콜률을 높이려면, _<dim> 접미사를 사용하여 LeanVec 차원을 늘리십시오.

• 리콜 성능을 다소 희생하더라도 메모리 사용량을 줄이려면 LeanVec의 차원을 낮추십시오.

• 저차원 벡터의 경우, ` LVQ8`를 사용해 보세요.

• 인텔(Intel)이 아닌 CPU에서는 FP16 또는 SQ8 를 사용하십시오.

인덱스 구축

다음 예제는 그래프 차수 64 및 LeanVec 압축을 사용하여 SVS Vamana 인덱스를 구축합니다. 인덱스를 구축하기 전에 설정 블록을 확장하고 실행하십시오.

import random

from pymilvus import DataType, MilvusClient

client = MilvusClient(uri="http://localhost:19530")
collection_name = "svs_vamana_example"

if client.has_collection(collection_name):
    client.drop_collection(collection_name)

rng = random.Random(42)
vectors = [[rng.random() for _ in range(256)] for _ in range(3000)]

schema = client.create_schema(auto_id=False, enable_dynamic_field=False)
schema.add_field("id", DataType.INT64, is_primary=True)
schema.add_field("vector", DataType.FLOAT_VECTOR, dim=256)

client.create_collection(collection_name=collection_name, schema=schema)

client.insert(
    collection_name=collection_name,
    data=[{"id": i, "vector": vector} for i, vector in enumerate(vectors)],
)
client.flush(collection_name=collection_name)

index_type 을 FAISS 로 설정하고, faiss_index_name 를 사용하여 SVS Vamana 레시피를 선택하십시오.

index_params = client.prepare_index_params()
index_params.add_index(
    field_name="vector",
    index_name="svs_vamana_index",
    index_type="FAISS",
    metric_type="L2",
    params={
        # SVSVamana64 -> Vamana graph degree 64
        # LeanVec4x8  -> 4-bit primary, 8-bit secondary
        # _128        -> LeanVec dim 128 (omit the suffix for dim / 2)
        "faiss_index_name": "SVSVamana64,LeanVec4x8_128",
        "construction_window_size": 200,  # build-time search width
        "ood_training": True,             # OOD on (default)
    },
)

client.create_index(collection_name=collection_name, index_params=index_params)
client.load_collection(collection_name=collection_name)

인덱스 검색

search_window_size 는 HNSW에서` ef `가 하는 것처럼 리콜과 지연 시간 간의 균형을 조절합니다. ` search_buffer_capacity `를 최소한 동일한 값으로 설정하십시오. 두 항목의 인덱스 기본값은 모두 10이며, SVS는 ` search_window_size `가 ` search_buffer_capacity`보다 큰 검색을 거부합니다.

search_params = {
    "params": {
        "search_window_size": 100,      # wider = higher recall, lower QPS
        "search_buffer_capacity": 100,  # must be >= search_window_size
    }
}

res = client.search(
    collection_name=collection_name,
    data=[vectors[0]],
    anns_field="vector",
    limit=10,
    search_params=search_params,
)

limit 가 search_window_size 보다 크면, SVS는 해당 검색에 대해 limit 까지 창 크기를 늘립니다.

SVS Vamana 매개변수

다음 빌드 매개변수는 params 의 add_index() 에 faiss_index_name 바로 옆에 지정됩니다. 인덱스가 구축된 후에는 이 매개변수를 변경할 수 없습니다.

다음 검색 매개변수는 ` search_params.params`에 포함됩니다. 또한 이를 빌드 매개변수로 설정할 수도 있으며, 이 경우 해당 매개변수가 설정되지 않은 검색에 대해 인덱스가 사용하는 기본값이 변경됩니다.

자세히 알아보기

• 일반적인 팩토리-스트링 계약, 제한 사항 및 오류 처리에 대해서는 FAISS 인덱스 패스스루 참조 문서를 읽어보십시오.
• DISKANN의 디스크 기반 Vamana 구현과 비교해 보세요.
• 빌드 세부 정보, 성능 튜닝 및 기본 C++ API에 대해서는 SVS 저장소를 참조하십시오.