KNN과 근사 최근접 이웃 — 벡터 검색은 어떻게 빨라지나

분류 방법 중 가장 직관적인 것이 KNN이다. 학습이라는 단계가 아예 없고, "비슷한 걸 찾아서 따라 한다"가 전부다. 단순한 만큼 한계도 분명하다. 무엇이 단순하고 어디서 막히는지, 그리고 그 막힘을 푸는 근사 검색까지 정리한다.

KNN — 비슷한 예시의 다수결

KNN(k-Nearest Neighbors, k-최근접 이웃)은 정답이 붙은 예시들을 모아두고, 새 입력이 오면 가장 가까운 예시 k개를 찾아 다수결로 답을 정한다.

비유하면 라벨이 붙은 사진첩이다. 처음 보는 음식 사진을 들고 사진첩에서 "제일 닮은 사진 5장"을 찾는다. 그중 3장이 "비빔밥"이면 비빔밥이라고 답한다. 모델을 훈련하는 단계가 없다. 보관해 둔 예시와 비교만 한다.

컴퓨터가 "닮음"을 재려면 먼저 사진을 임베딩(embedding, 의미가 담긴 숫자 벡터)으로 바꿔야 한다. 그다음 벡터끼리의 거리나 코사인 유사도로 가까움을 잰다. 임베딩이 무엇인지는 별도 글에서 다룬다. 여기서는 "사진 한 장 = 벡터 한 개"라고만 보면 된다.

단순함의 대가 — 검색 속도

KNN의 핵심 비용은 검색이다. 새 벡터가 들어올 때마다 저장된 모든 예시 벡터와 거리를 재야 한다.

정확한 검색(Exact Search): 모든 레퍼런스 벡터와 일일이 거리를 계산한다. 복잡도는 O(N·D)다(N = 저장된 벡터 수, D = 벡터 차원). 벡터가 수천 개까지는 현실적이지만, 수십만~수백만 개가 되면 한 번 검색에 너무 오래 걸린다. 사진첩이 두꺼워질수록 한 장 한 장 다 넘겨봐야 하는 것과 같다.

근사 최근접 이웃 — O(log N)으로 줄이기

그래서 나온 것이 근사 최근접 이웃(ANN, Approximate Nearest Neighbor)이다. "정확히 가장 가까운 것"을 약간 포기하는 대신 훨씬 빠르게 "거의 가장 가까운 것"을 찾는다.

대표 구조가 HNSW(Hierarchical Navigable Small World)다. 이름이 길지만 아이디어는 지하철 노선도에 가깝다. 모든 역(벡터)을 한 층에 두지 않고 여러 층의 그래프로 쌓는다.

• 위층: 역이 드물고 멀리멀리 연결된 급행 노선. 목적지 근처까지 단번에 점프한다.
• 아래층: 역이 촘촘한 완행 노선. 목적지 주변에서 정밀하게 좁힌다.

검색은 위층에서 대충 방향을 잡고 점점 아래층으로 내려가며 좁힌다. 모든 역을 훑지 않으므로 탐색 복잡도가 O(log N)으로 줄어든다. 대신 100% 정확하지는 않다. 진짜 최근접 이웃을 가끔 놓친다(recall@10 기준 보통 9599%, 즉 상위 10개 중 9599%를 정확히 회수). FAISS, Annoy 같은 라이브러리가 이런 구조를 구현한다.

방식	검색 복잡도	정확도	적합한 규모
Exact Search	O(N·D)	100%	수천 벡터
HNSW (ANN)	O(log N)	95~99%	수십만~수억 벡터

폰에 올릴 때의 진짜 문제 — 인덱스 크기

KNN/ANN을 온디바이스(폰 안에서 직접 실행)로 가져가면 속도보다 크기가 먼저 발목을 잡는다. 예시 벡터를 전부 폰에 들고 있어야 하기 때문이다.

숫자로 따져보자. ViT-B/32 임베딩은 512차원 float32다. float32 한 개가 4바이트이므로 벡터 하나는 512 × 4 = 2KB다.

• 음식 150종 × 종마다 레퍼런스 20장 = 3,000개 벡터
• 3,000 × 2KB = 6MB (원본 벡터만)
• 여기에 HNSW 그래프 구조의 오버헤드가 더해지면 실제 인덱스 파일은 15~25MB 수준

문제는 크기 자체보다 구조적 비용이다. 이 인덱스는 모델 가중치 파일과 별개로 폰에 함께 배포해야 한다. 그리고 인식할 음식 종류가 늘 때마다 인덱스를 다시 빌드해서 앱 업데이트로 내보내야 한다. 지식이 "모델 안"이 아니라 "별도 데이터 파일 안"에 있기 때문에 생기는 비용이다.

이점과 트레이드오프

KNN/ANN의 이점은 유연함이다. 학습이 없으니 예시(사진)만 추가하면 그 자리에서 인식 범위가 늘어난다. 새 카테고리를 위해 재학습할 필요가 없다.

감수하는 것은 다음과 같다.

• 저장 비용: 모든 예시 벡터를 보관해야 한다. 카테고리가 늘수록 인덱스가 커진다.
• 배포 비용: 인덱스를 모델과 별도로 관리·갱신·배포해야 한다.
• 근사의 부정확성: ANN은 빠른 대신 가끔 진짜 최근접을 놓친다.
• 품질이 예시에 의존: 레퍼런스 사진의 품질과 대표성이 그대로 정확도가 된다.

정리하면 KNN은 "데이터를 더하면 바로 늘어나는 유연함"과 "그 데이터를 전부 들고 다녀야 하는 비용"을 맞바꾼 방법이다. 폰처럼 자원이 제한된 환경에서는 이 인덱스 보관 비용이 부담이 되어, 지식을 모델 가중치 안에 담는 분류기를 택하는 경우가 많다. 그 모델을 폰에 올리는 포맷과 압축은 다른 글에서 다룬다.