PHP에서 HNSW 벡터 검색 구현: 코사인 유사도 한계를 넘는 방법

PHP로 벡터 검색을 구현해 보신 분이라면 이런 경험이 있을 겁니다.
“임베딩은 잘 만들었는데, 검색 속도가 너무 느리다…”

기본적인 코사인 유사도 방식은 벡터 하나를 쿼리로 넣고, 수천·수만 개의 벡터를 하나씩 전부 비교합니다. 데이터가 조금만 커져도 바로 병목이 생기죠. 이 문제를 해결하기 위해 등장한 알고리즘이 바로 HNSW(Hierarchical Navigable Small World)입니다.

이 글에서는 PHP에서 HNSW를 어떻게 이해하고, 어떻게 구현(혹은 활용)할 수 있는지, 그리고 실제로 어떤 파라미터를 어떻게 튜닝해야 하는지까지 전 과정을 정리합니다. 예시는 PHP 오픈 소스 프로젝트 Vektor를 염두에 두고 설명하되, 개념 자체는 어떤 PHP 프로젝트에서도 그대로 응용할 수 있도록 구성했습니다.

HNSW가 뭐고, 왜 PHP 벡터 검색에 필요할까?

먼저 “왜 굳이 HNSW를 써야 하는가?”부터 정리해 보겠습니다.

코사인 유사도 기반 벡터 검색의 기본 방식은 단순합니다.
쿼리 벡터 하나를 기준으로 전체 문서 벡터를 쭉 훑으며, 각 벡터와의 코사인 유사도를 계산하고, 그중 상위 K개를 뽑습니다. 시간 복잡도로 쓰면 대략 O(N × d) 정도입니다.
N은 벡터 개수, d는 벡터 차원 수죠. 데이터가 10만 개, 50만 개가 넘어가면 이 방식은 사실상 실시간 검색에 맞지 않습니다.

여기서 HNSW가 등장합니다. HNSW는 “정확한” 최근접 이웃(Nearest Neighbor)이 아니라, 대부분의 경우 “거의 같은” 결과를 훨씬 빠르게 찾는 근사 최근접 이웃(Approximate Nearest Neighbor, ANN) 알고리즘입니다.

핵심 아이디어는 단순합니다.

“모든 벡터를 매번 다 보지 말고,
미리 잘 연결된 그래프를 만들어 두고,
필요한 후보들만 따라가며 찾자.”

이때 HNSW는 벡터들을 여러 계층(Level) 으로 나눈 그래프 구조를 사용합니다. 그리고 이 구조 덕분에 탐색 시간이 O(log N) 수준으로 줄어듭니다. 벡터 데이터베이스와 검색 엔진(OpenSearch, Elasticsearch, Milvus, Pinecone 등)이 HNSW를 채택하는 이유도 바로 이 “규모가 커져도 버텨주는” 특성 때문입니다¹².

PHP라고 예외는 아닙니다.
RAG 시스템, 추천 시스템, 개인화 검색 등을 PHP로 만들고 있다면, HNSW를 쓰는 순간 다음과 같은 변화가 생깁니다.

데이터 수가 10배, 100배 늘어나도 검색 속도가 크게 느려지지 않음
PHP 애플리케이션 레벨에서 직접 ANN을 제어할 수 있음
외부 벡터 DB 없이도, PHP 안에서 “벡터 인덱스”를 관리할 수 있음

이제 구체적으로 HNSW 구조와 동작을 살펴보겠습니다.

고속도로에서 골목길로: HNSW 구조를 직관적으로 이해하기

HNSW를 이해할 때 가장 유명한 비유가 있습니다.
“고속도로 → 국도 → 골목길”로 내려가며 목적지를 찾아가는 방식입니다.

이 비유를 PHP 벡터 검색에 맞게 다시 풀어보면 이렇습니다.

가장 높은 레벨: 고속도로 레벨
여기는 노드(벡터)가 많지 않습니다.
대신 서로 멀리 떨어진 지점들을 빠르게 연결하는 “큰 길” 역할을 합니다.
이 레벨에서 쿼리 벡터와 어느 정도 비슷한 지점까지 단숨에 이동합니다.
중간 레벨: 국도 레벨
조금 더 많은 벡터가 있습니다.
여기서는 고속도로에서 내려와, 쿼리와 더 가까운 벡터들을 향해 점점 좁혀 가는 역할을 합니다.
Level 0: 골목길 레벨 (바닥 레벨)
모든 벡터가 이 레벨에 있습니다.
최종적으로 이 레벨에서 상위 K개의 최근접 이웃을 골라냅니다.

구조적으로 보면 HNSW는 “층층이 쌓인 그래프”입니다.

각 벡터는 어느 최고 레벨까지 올라갈지를 랜덤하게 부여받고
그 레벨부터 아래 레벨까지 모두에 등장합니다.
각 레벨에서 해당 벡터는 주변의 다른 벡터들과 최대 M개까지만 연결됩니다.

PHP 입장에서 이걸 구현한다고 생각해 보면, 결국 이런 구조가 됩니다.

levels[레벨번호]마다 개별 그래프 혹은 인접 리스트를 가지고 있고
각 노드는 id, vector, neighbors 목록을 갖습니다.
그리고 전체 구조에는 “가장 높은 레벨의 진입 노드(entry point)”가 저장됩니다.

이 구조 덕분에 HNSW는 다음을 동시에 만족합니다.

위쪽 레벨에서는 노드 수가 적으니 빠르게 먼 거리를 이동할 수 있고
아래로 내려갈수록 밀도가 높아지며 더 정교하게 탐색할 수 있습니다.

결과적으로, 전체 벡터를 전부 보는 대신 일부 후보들만 보면서도 거의 최적의 이웃을 찾게 되는 것이죠.

PHP에서 HNSW 탐색 과정: $ef로 제어하는 검색 품질

이제 PHP 코드로 HNSW를 검색한다고 가정하고, 단계별로 정리해 보겠습니다.
여기서 중요한 파라미터가 바로 $M과 $ef입니다.

$M : 각 노드가 가질 수 있는 최대 연결 수(최대 이웃 수)
$ef : 검색 시 유지하는 “후보 리스트” 크기 (exploration factor)

1. 위 레벨에서 시작해, 한 레벨씩 내려오기

검색 과정은 항상 “가장 높은 레벨의 entry point”에서 시작합니다.

최고 레벨에서 랜덤 또는 지정된 entry point를 하나 선택합니다.
현재 노드에서 이웃 노드들을 살펴보며,
쿼리 벡터에 더 가까운 노드가 있는 한 계속 이동합니다.
더 이상 나아질 수 없을 때,
그 노드를 다음 레벨의 시작점으로 삼고 한 층 내려갑니다.
Level 0 직전까지 이 과정을 반복합니다.

이 단계에서 사용하는 검색 방식은 흔히 “탐욕적(greedy) 탐색”입니다.
매번 “지금보다 더 가까운 이웃”만 고르는 방식이라 구현도 비교적 단순합니다.

2. Level 0에서 $ef를 활용해 K개 결과 뽑기

Level 0에 도착하면 이제 모든 벡터가 이 레벨에 존재합니다.
여기서부터가 진짜 HNSW 검색의 핵심입니다.

우선 entry point를 기준으로, 우선순위 큐(대개 최대 힙 두 개)를 준비합니다.
- 하나는 “아직 탐색할 후보들(candidate)”
- 하나는 “현재까지 발견된 이웃들(best)”입니다.
후보 큐의 크기를 $ef로 제한합니다.
즉, 동시에 고려하는 후보 벡터의 수가 $ef입니다.
루프를 돌며 다음을 반복합니다.
- 후보 중에서 쿼리에 가장 가까운 노드를 꺼내고
- 그 노드의 이웃들을 확인한 뒤, 아직 방문하지 않은 노드들을 후보 큐에 넣습니다.
- 단, 큐 크기가 $ef를 넘으면, 가장 멀리 있는 후보부터 제거합니다.
더 이상 “지금까지 찾은 최악의 이웃보다 더 나은 후보”가 없을 때 종료합니다.
마지막에 best 큐에 남은 것 중 상위 K개를 결과로 반환합니다.

여기서 $ef는 다음과 같은 의미를 가집니다.

$ef를 크게 잡으면
- 더 많은 후보를 탐색하므로
- 정확도(Recall)는 올라가고
- 검색 속도는 느려집니다.
$ef를 작게 잡으면
- 소수의 후보만 보니
- 속도는 빨라지고
- 대신 최적 이웃을 놓칠 가능성이 커집니다.

대형 벡터 검색 시스템에서도 이 ef 파라미터가 “속도 vs 정확도”를 제어하는 핵심 스위치로 사용됩니다³. PHP 구현에서도 완전히 동일한 역할을 하며, Vektor 역시 $ef 값을 외부에서 조정할 수 있게 제공합니다.

맵 생성과 삽입: PHP에서 HNSW 그래프를 만드는 방법

검색만큼 중요한 것이 그래프를 어떻게 구축하느냐입니다.
HNSW는 삽입 과정에서도 나름의 규칙을 갖고 있고, 이를 제대로 따라야 검색 성능이 나옵니다.

1. 레벨을 어떻게 정하나? — 무작위성 기반 계층 구성

새로운 벡터 하나를 삽입할 때, HNSW는 먼저 이 벡터의 최대 레벨을 정합니다.

여기서 중요한 점이 하나 있습니다.
레벨은 완전히 랜덤이 아니라, “높은 레벨일수록 드물게” 배정되도록 설계됩니다.

간단히 말해:

대부분의 노드는 Level 0에만 존재
일부는 Level 1까지,
더 소수는 Level 2까지,
극소수만 가장 높은 레벨까지 올라갑니다.

이렇게 해야 위에서 말한 “고속도로 → 골목길” 구조가 자연스럽게 만들어집니다.
그래서 HNSW는 로그와 난수를 활용한 수식을 사용해 레벨을 정합니다.
PHP 코드에서는 보통 다음과 같은 구조를 가집니다.

0과 1 사이의 난수 하나를 뽑고
로그 함수를 이용해 레벨을 계산한 뒤
최대 레벨 값 이상으로는 올라가지 않게 min()으로 제한

이런 방식으로 생성된 레벨 값에 따라, 해당 노드를 그 레벨부터 아래 레벨까지 모두에 삽입합니다.

2. 각 레벨에 노드를 연결하는 방법: $M과 efConstruction

HNSW 삽입 과정은 검색과 상당히 비슷합니다.

그래프의 entry point에서 시작해,
새 벡터와 가장 가까운 노드를 향해 위에서 아래로 탐색합니다.
새 노드가 가질 최대 레벨부터 시작해,
각 레벨에서 “가까운 이웃을 찾는 탐색”을 수행합니다.
각 레벨마다 새 노드를 주변 노드들과 연결합니다.
이때 한 노드가 가질 수 있는 이웃 수는 최대 $M개입니다.

여기서 삽입 품질에 영향을 주는 파라미터가 하나 더 있습니다.

efConstruction (PHP 구현에서는 $efConstruction 또는 삽입용 $ef로 표기 가능)
- 새 노드를 삽입할 때 참고하는 후보 리스트 크기
- 클수록 그래프 구조가 더 잘 형성되지만, 삽입 속도는 느려짐

간단히 정리하면:

$M : 그래프가 얼마나 촘촘한지(엣지 밀도)를 결정
efConstruction : 삽입 시 얼마나 꼼꼼히 주변 이웃을 찾아줄 것인지 결정

PHP에서 HNSW를 직접 구현하거나 Vektor의 설정을 튜닝할 때는 보통 다음과 같은 전략을 씁니다.

소규모 데이터(수천 ~ 수만)
- $M : 8~16
- efConstruction : 50~200
대규모 데이터(수십만 이상)
- $M : 16~32 이상
- efConstruction : 200~800

수치 자체는 데이터 분포와 하드웨어에 따라 달라지지만, “더 촘촘하게, 더 꼼꼼하게” 만들수록 검색 정확도는 올라가고, 구축 시간과 메모리 사용량은 늘어납니다³.

PHP 코드 관점에서 보는 HNSW 구현 전략 (Vektor 예시)

이제 실제 PHP 구현 관점에서 어떤 식으로 HNSW를 활용할 수 있는지 감을 잡아보겠습니다.
여기서는 개념을 설명하기 위한 의사 코드 스타일로 설명합니다.

1. 기본 클래스 구조 상상해 보기

PHP에서 HNSW를 구현한다면, 대략 다음과 같은 구조가 됩니다.

VectorNode
- int $id
- array $vector
- int $maxLevel
- array $neighborsByLevel (레벨별 이웃 목록)
HnswIndex
- int $M
- int $ef (검색용)
- int $maxLevel
- array $entryPoint
- array $levels (레벨별 노드 저장)

여기에 다음 메서드들이 필요합니다.

insert(array $vector, int $id)
search(array $queryVector, int $k): array
(옵션) saveToFile() / loadFromFile() – 인덱스를 디스크에 저장

오픈 소스인 Vektor 역시 비슷한 개념을 기반으로 구현되어 있으며, 실제 코드와 테스트 케이스를 보면 HNSW의 삽입, 검색, 파라미터 동작 방식을 PHP 스타일로 이해하기 좋습니다.

2. 검색 품질 튜닝: $ef와 $M을 어떻게 잡을까?

PHP 애플리케이션에 HNSW를 붙여 실제로 RAG나 추천 시스템을 만든다고 가정해 봅시다.
실무에서 가장 많이 하는 작업이 바로 파라미터 튜닝입니다.

간단한 기준은 다음과 같습니다.

속도가 최우선인 경우
- $ef를 작게, $M도 적당히 낮게
- 예: $M = 8, $ef = 32, efConstruction = 100
정확도가 더 중요한 경우 (예: 검색 결과를 그대로 유저에게 보여주는 경우)
- $ef를 크게, $M도 높게
- 예: $M = 16~32, $ef = 100~200, efConstruction = 300~800

대형 시스템에서의 연구 결과를 보면, HNSW는 파라미터를 잘 잡았을 때 full scan 대비 수십 배 빠르면서도 동일한 이웃을 찾아내는 수준까지 올라갈 수 있습니다³⁴. PHP에서도 벡터 수만~수십만 단위라면 체감되는 차이가 상당할 것입니다.

정리 및 시사점: PHP에서도 “진짜 벡터 검색”을 하고 싶다면

지금까지 내용을 한 번 정리해 보겠습니다.

첫째, 코사인 유사도 + 전체 스캔 방식은 확장성이 없다는 것이 핵심입니다.
데이터가 조금만 커져도 PHP 애플리케이션 레벨에서 감당하기 어렵습니다.

둘째, HNSW는 계층적 그래프를 이용해 탐색 범위를 O(log N) 수준으로 줄여 주는 ANN 알고리즘입니다.
위 레벨에서는 큰 점프, 아래 레벨에서는 정교한 탐색, 가장 아래(Level 0)에서는 $ef만큼의 후보를 깊이 탐색해 상위 K개를 뽑아 냅니다.

셋째, PHP에서 HNSW를 사용할 때 중요한 파라미터는 $M과 $ef, 그리고 efConstruction입니다.

$M : 각 노드의 최대 이웃 수 → 그래프 밀도 & 검색 품질에 영향
$ef : 검색 시 후보 큐 크기 → 속도 vs 정확도의 핵심 스위치
efConstruction : 인덱스 구축 품질 vs 구축 비용 조절

넷째, HNSW는 이미 다양한 벡터 DB, 검색 엔진, 관계형 DB까지 폭넓게 채택되고 있는 사실상 표준 그래프 기반 인덱스입니다²⁴. PHP에서 벡터 검색을 직접 구현하든, 외부 DB를 붙이든, HNSW를 이해하고 있으면 시스템 설계와 튜닝에 큰 도움이 됩니다.

실용적인 조언을 몇 가지 덧붙이면:

처음에는 작은 데이터셋(수천 개)으로 $M, $ef를 여러 조합으로 바꿔 보며,
“검색 속도”와 “정답 벡터와의 거리”를 비교해 보는 것이 좋습니다.
RAG 시스템에서는 “완벽한 최근접 이웃”보다 “충분히 관련 있는 이웃을 빨리 찾는 것”이 더 중요하므로, full scan과 HNSW 결과가 100% 일치하지 않아도 괜찮습니다.
PHP 단독 구현이 부담스럽다면, 먼저 Vektor의 구현을 참고해 구조를 익힌 뒤, 필요 시 C/Go 기반 라이브러리를 FFI 등으로 붙이는 것도 좋은 선택입니다.

HNSW는 처음엔 다소 복잡해 보이지만,
“위에서 아래로 내려가며 점점 좁혀 가는 그래프 탐색”이라는 큰 그림만 잡고 보면 생각보다 단순합니다.

이제 코사인 유사도 루프를 돌리며 CPU를 태우는 대신,
PHP에서도 제대로 된 벡터 인덱스를 써볼 차례입니다.

참고

¹AI & Vectors | Supabase Docs

²Distribution-Aware Exploration for Adaptive HNSW Search

³Demystifying HNSW: The Graph Algorithm Powering Vector Databases

⁴Distribution-Aware Exploration for Adaptive HNSW Search