근사 최근접 검색 — HNSW 인덱스로 벡터 검색 가속화

근사 최근접 검색 — HNSW 인덱스로 벡터 검색 가속화

벡터 공간에서 최근접 이웃 검색을 빠르게 하려면 텐서 필드에 HNSW 인덱스 를 추가하면 돼요. Vespa는 Hierarchical Navigable Small World 그래프 알고리즘(논문)의 변형을 구현했어요.

출처: https://docs.vespa.ai/en/querying/approximate-nn-hnsw.html

HNSW 인덱스 활성화

근사 매칭을 쓰려면 텐서 필드 정의에 index 지시가 필요해요. 문서 스키마는 HNSW가 켜진 여러 텐서 필드를 선언할 수 있습니다.

field image_embeddings type tensor<float>(i{},x[512]) {
  indexing: summary | attribute | index
  attribute {
    distance-metric: angular
  }
  index {
    hnsw {
      max-links-per-node: 16
      neighbors-to-explore-at-insert: 100
    }
  }
}

field text_embedding type tensor<float>(x[384]) {
  indexing: summary | attribute | index
  attribute {
    distance-metric: prenormalized-angular
  }
  index {
    hnsw {
      max-links-per-node: 24
      neighbors-to-explore-at-insert: 200
    }
  }
}

위 스니펫에서 image_embeddings는 문서당 여러 벡터를, text_embedding은 문서당 하나 벡터를 인덱싱해요. 두 필드는 서로 다른 distance-metric과 HNSW 설정을 쓰는데, 파라미터는 정확도·메모리·인덱싱 성능 사이의 트레이드오프를 만듭니다.

  • max-links-per-node: 값이 클수록 리콜 정확도가 높아지지만 메모리·인덱싱·검색 비용도 늘어요.
  • neighbors-to-explore-at-insert: 값이 클수록 리콜 정확도가 높아지지만 인덱싱 비용이 늘어요.

예를 들어 검색 시점 파라미터 hnsw.exploreAdditionalHits를 늘리면 낮은 조합은 recall@10 약 70%, 높은 조합은 약 92%에 도달합니다.

근사 vs 정확 검색

HNSW 인덱스가 켜진 텐서 필드에서 approximate 어노테이션으로 근사 또는 정확(브루트포스) 검색을 선택할 수 있어요.

{
  "yql": "select * from doc where {totalTargetHits: 10, approximate:false}nearestNeighbor(image_embeddings,query_image_embedding)",
  "hits": 10,
  "input.query(query_image_embedding)": [0.21,0.12,....],
  "ranking.profile": "image_similarity"
}

기본적으로 HNSW 인덱스가 있는 필드는 approximate가 true예요. approximate:false로 정확 검색을 해 overlap@k를 계산하면 근사 검색의 정확도 손실을 정량화할 수 있어요. 정확 검색은 기본 질의 타임아웃(500ms)이 너무 짧을 수 있으니 조정해야 합니다.

필터와 결합

nearestNeighbor 연산자는 다른 필터·질의 조건과 결합할 수 있어요. 두 가지 전략이 있습니다.

  • pre-filtering(기본) — 필터를 먼저 적용한 뒤 ANN
  • post-filtering — ANN으로 후보를 줄인 뒤 필터

approximate-threshold와 post-filter-threshold로 랭크 프로필에서 설정할 수 있어요.

메모리·확장

Vespa 텐서 필드는 인메모리 구조이고 HNSW 그래프도 마찬가지예요. 메모리 비용을 줄이는 효과적인 방법은 벡터 값의 크기를 줄이는 거예요. 텐서 셀 값 타입에는 int8(1바이트), bfloat16(2바이트), float(4바이트), double(8바이트)가 있어요. float를 bfloat16으로 바꾸면 정확도 손실은 거의 없이 비용이 거의 절반으로 줄어듭니다.

HNSW 탐욕 검색 알고리즘은 서브리니어(거의 log(N))라서, 단순 벡터 검색 앱에서는 노드당 벡터 수를 늘리는 쪽으로 볼륨을 스케일업하는 게 좋아요.

더 알아보기