Executive Summary

RAG를 붙이거나 추천을 돌리는 조직은 벡터를 계속 쌓는다. 문서가 늘고 상품이 늘고 대화 기록이 쌓이는 만큼 임베딩도 늘어난다. 그래서 벡터 DB를 운영하는 쪽은 어느 시점엔가 같은 질문 앞에 선다. 지금 1천만 건인 인덱스가 내년에 1억 건이 되면 검색에 드는 자원은 얼마나 늘어나는가. 이 질문에 답할 때 거의 모두가 같은 전제를 쓴다. 그래프 인덱스는 데이터가 늘어도 검색이 로그로만 느려진다는 것.

이 글이 다루는 논문은 그 전제를 실험대에 올린다. 「A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search」, 2026년 9월 2일 arXiv에 올라온 프리프린트이고 저자 세 명은 모두 토론토대학교 소속이다. 벡터 DB 벤더에 속한 저자는 없다.

먼저 용어를 고정해 둔다. 이 글에서 말하는 검색 비용은 질의 한 번에 수행하는 거리 계산 횟수다. 응답 시간(ms)도 메모리도 클라우드 요금도 아니다. 논문이 그렇게 정한 이유는 명시돼 있다. 실제 시간으로 재면 캐시 방출, 프리페치, 하드웨어 최적화된 거리 계산 같은 구현의 특성이 알고리즘의 성질과 뒤섞이기 때문이다. 거리 계산 횟수는 그래프 순회에서 지배적인 비용이면서 구현에 덜 흔들린다.

1.1데이터가 늘면 재현율이 먼저 떨어진다

논문의 첫 실험은 이미 알려진 현상을 확인하는 것으로 시작한다. 인덱스 파라미터를 그대로 둔 채 데이터만 키우면, 질의당 거리 계산 횟수는 조금 늘고 재현율은 크게 떨어진다. 재현율(recall)은 진짜 최근접 이웃 가운데 검색이 실제로 찾아낸 비율이다. 이유는 직관적이다. 데이터가 커지면 질의 근처에 놓인 점이 많아지고, 빔 탐색(beam search)은 더 느리게 수렴하며, 진짜 최근접 이웃은 후보 목록의 자리를 두고 더 많은 경쟁을 치른다. 검색 품질이 조용히 나빠지는 것이다.

그래서 현장에는 이런 관행이 생겼다. 주기적으로 정확 검색을 돌려 재현율을 재고, 목표에 못 미치면 탐색 후보 목록 크기(ef_search)를 올리고, 다시 재고, 목표에 닿을 때까지 반복한다. 논문은 이 관행이 벤더 문서와 최근 연구에 폭넓게 적혀 있다고 인용하며 서술한다. 이 관행이 중요한 이유는 그것이 곧 논문의 실험 설계가 되기 때문이다. 재현율을 목표에 붙들어 놓고 데이터를 키우면 흔들리는 쪽이 품질에서 비용으로 옮겨 간다. 그 비용이 어떤 곡선을 그리는가가 이 논문의 질문이다.

그래프 인덱스가 질의를 어떻게 걷는지, 삭제된 문서의 연결이 왜 그래프에 남는지는 페블러스 블로그가 벡터 DB의 삭제와 유령 메아리를 다룬 글에서 한 번 풀었다. 같은 저장소를 보안 각도로 본 글은 임베딩 번역과 벡터 DB의 공격면에 있다. 이 글은 그 저장소가 자랄 때의 비용 곡선만 본다.

논문은 1절의 한 소제목을 "The Logarithmic Folklore"라고 붙였다. 로그 확장이라는 통념을 가리키는 말이다. 논문의 정리에 따르면 이 통념은 두 갈래로 나뉜다. 정확하게 구성한 그래프에 대해서는 증명이 붙은 주장이 있고, 실무에서 쓰는 휴리스틱 인덱스에 대해서는 주장만 있고 증명이 없다. 우리가 실제로 돌리는 것은 후자다.

그렇다면 근거로 인용되는 원 논문은 무엇을 쟀을까. 이 대목은 새 논문의 요약을 그대로 옮기는 대신 HNSW 원 논문(Malkov & Yashunin, arXiv:1603.09320 v4)을 직접 열어 확인했다. 두 가지가 사실이었다.

2.1확장을 잰 실험은 그림 한 벌이 전부였다

HNSW 원 논문에서 데이터 크기를 바꿔 가며 확장 곡선을 그린 실험은 Fig. 12(b)와 (c) 한 벌이다. 대상은 8차원 무작위 초입방체에서 뽑은 합성 벡터였고, 10-NN 검색이며, 재현율을 0.95로 고정한 조건이었다. 그리고 원 논문의 표현은 로그라는 단정이 아니라 "not worse than logarithmic", 즉 로그보다 나쁘지 않다는 상한 서술이었다.

여기에 한정을 붙여야 한다. HNSW 논문 전체가 저차원 합성 데이터로만 검증된 것은 아니다. 5.2절부터 5.4절까지는 SIFT·GIST·GloVe 같은 실제 데이터셋에서 폭넓게 성능을 비교한다. 크기를 바꿔 가며 확장을 잰 실험만 놓고 보면 8차원 합성 벡터 하나였다는 것이 정확한 서술이다.

2.2저자들은 최대 실험의 이탈을 이미 적어 두었다

더 흥미로운 것은 같은 논문의 5.4절이다. 2억 건 규모의 SIFT 데이터셋, 임베딩 차원 128, 그 논문에서 가장 큰 실험이다. 저자들은 질의 시간의 확장 곡선을 그려 놓고 그 옆에 이렇게 적었다.

2018년에 이미 적혀 있던 문장이다. 다만 여기서 과장하지 않는 것이 중요하다. HNSW 저자가 말한 높은 차원은 임베딩 차원 128을 가리키는 맥락이고, 새 논문이 곡선의 주인공으로 지목한 내재 차원과 같은 양이 아니다. 두 논문이 같은 말을 했다고 쓰면 틀린다. 원 논문이 한 일은 최대 실험에서 이탈을 보고 차원 탓으로 짐작한 데까지다. 그 짐작을 어떤 차원인지까지 특정하고 곡선의 모양을 수식으로 세운 것이 8년 뒤 이 논문이다.

Vamana 쪽 사정은 또 다르다. 새 논문에 따르면 Vamana 원 논문은 정확하게 구성한 그래프에서 탐욕 검색의 단계 수가 로그라는 논증을 폈을 뿐, 데이터 크기에 따른 검색 비용을 측정한 적이 없다.

2.3업계 문서로 옮겨 간 것은 결론뿐이었다

새 논문은 이 주장이 업계 문서와 서베이로 퍼져 확정된 성질처럼 재진술되고 있다고 적는다. 그 문서들을 직접 열어 확인했다. 여섯 곳 모두 실제로 로그, 또는 로그를 몇 번 곱한 크기인 다항로그로 확장을 서술하고 있었다. 다만 진술의 강도가 같지 않다. 아래는 각 문서의 원문 표현과 그 성격이며, 조회일은 2026년 9월 5일이다. Milvus만 라이브 페이지가 봇 차단으로 열리지 않아 2026년 5월 12일 웨이백 스냅숏을 썼다.

마지막 줄이 이 섹션의 그림을 완성한다. Redis 문서는 자기가 주장하는 대신 원 논문을 따옴표로 인용한다. 벤더가 논문을 인용하고, 그 논문이 근거로 삼은 확장 실험이 8차원 합성 벡터였다는 사슬이 한 문서 안에서 그대로 보인다. 참고로 새 논문이 이 문서들을 나열한 목록은 1절과 2절이 서로 다르다. Milvus·Weaviate·Pinecone·Redis·OpenSearch가 공통이고, 여기에 1절은 FAISS를, 2절은 Elastic을 더한다.

옮겨 가지 않은 것이 무엇인지를 한 장으로 정리하면 아래와 같다.

논문은 여기에 한 가지를 더한다. 이 주장이 오래 검증되지 않은 이유가 벤치마크의 관행에 있다는 것이다. 벤치마크는 대개 재현율과 비용의 맞바꿈을 한 가지 데이터 크기에서 재고, 재현율을 고정한 채 크기별 비용을 재지 않는다고 논문은 적는다. 이 대목은 논문의 주장이며, 각 벤치마크의 실제 프로토콜을 우리가 따로 확인하지는 않았다.

실험 설계는 앞서 말한 실무 관행을 그대로 옮겨 놓은 것이다. 재현율을 고정한다는 것은 각 크기마다 목표 재현율에 닿는 가장 작은 탐색 후보 목록 크기를 찾아 그때의 거리 계산 횟수를 기록한다는 뜻이다. 그런 다음 데이터를 키우고 다시 같은 일을 한다. 정답은 데이터 전체를 훑는 정확 검색으로 만들었다.

격자의 크기가 이 논문의 무게다. 데이터셋 여덟 개, 재현율 목표 네 단계(90%·95%·97.5%·99%)에 인덱스 종류마다 설정 열여섯 가지가 곱해진다. 설정은 노드당 연결 수(M)를 16·32·64·128로, 구축 후보 목록 크기(ef_construction)를 100·200·400·800으로 조합한 것이다. 인덱스는 HNSW와 Vamana 두 종류이고, Vamana의 느슨함 파라미터 α는 기본값 1.2로 두었다. 1.5와 2로 바꿔 봐도 확장성은 달라지지 않았다는 각주가 붙어 있다. 노드의 연결 수가 대개 상한 M에서 포화하기 때문이다. 몇 개를 찾을지(k)도 1·5·10·20으로 바꿔 보았는데 지수가 의미 있게 달라지지 않아 k=10만 보고한다고 논문은 적는다. 지면 사정으로 그림에는 열여섯 설정 중 네 개만 실렸고, 나머지는 비슷하게 움직였다는 서술만 있다.

3.1로그였다면 곡선은 아래로 휘어야 했다

결과를 읽는 방법은 단순하다. 가로축과 세로축을 모두 로그로 그렸을 때 곡선이 직선이면 거듭제곱이다. 로그 확장이었다면 데이터가 두 배가 될 때마다 거리 계산이 일정한 양만 더해지므로 곡선은 아래로 휘어야 한다. 논문의 관찰은 대부분의 곡선이 휘지 않고 곧게 뻗었다는 것이다. 논문은 이 곡선에 선형보다 느린 거듭제곱 법칙(Sublinear Power Law)이라는 이름을 붙였다. 질의당 거리 계산 횟수가 데이터 크기 N의 c제곱에 비례하고, 이때 c는 0과 1 사이의 상수다.

지수를 밀어 올리거나 끌어내리는 요인도 같은 그림에서 읽힌다. 재현율 목표가 높을수록 지수가 오르고, 구축 후보 목록 크기와 노드당 연결 수가 클수록 지수가 내려간다. 그리고 데이터셋이 어려울수록 지수가 커지는 경향이 있다. 논문은 어려움의 대리 지표로 내재 차원을 쓰는데, 예로 든 대비가 GloVe와 SIFT다. 100만 건 시점에서 잰 내재 차원이 32.4와 19.2로 갈리고, 같은 재현율에서 GloVe 쪽 지수가 더 높았다.

3.2쉬운 질의와 어려운 질의로 갈라도 마찬가지였다

같은 데이터셋 안에서도 질의마다 난이도가 다르다. 논문은 질의를 국소 내재 차원(LID) 기준으로 줄 세운 뒤 상위 20%와 하위 20%를 갈라 실험을 다시 돌렸다. SIFT·DEEP·GloVe에서 어려운 쪽 무리의 내재 차원은 쉬운 쪽보다 각각 7.9·9.6·11.0 포인트 이상 높았다. 두 무리의 지수는 서로 달랐지만, 양쪽 다 직선이었다. 질의 난이도는 곡선의 기울기를 바꿀 뿐 곡선의 종류까지 바꾸지는 못했다.

3.310억 건까지 키운 실험은 조건이 좁다

격자 실험은 SIFT·DEEP·SpaceV에 대해 1억 건에서 상한을 두었다. 총 실험 시간을 1주일 안팎으로 묶기 위해서였다. 그래서 논문은 실험을 따로 더 돌린다. 세 데이터셋을 10만 건에서 10억 건까지 키우며 같은 측정을 반복한 것이다. 이 실험의 조건은 좁다. 데이터셋 세 개, 알고리즘은 Vamana 하나, 설정도 구축 후보 목록 100·연결 수 32 한 가지뿐이다. Vamana를 고른 이유는 HNSW보다 메모리를 적게 써서 가장 큰 규모까지 갈 수 있어서였다. 이 규모에서는 설정 하나짜리 인덱스가 300GB에서 1TB를 차지하고 구축에 며칠이 걸린다.

결과는 이렇다. SIFT와 DEEP의 곡선은 10억 건까지 계속 곧게 뻗었다. SpaceV만 곡선의 기울기가 내려갔다. 다만 이 데이터셋에는 조건이 더 붙어 있다. 같은 점이 여러 번 들어 있어서, 다른 데이터셋과 공정하게 견주려고 논문이 중복을 걷어내고 질의 집합도 기반 데이터에서만 뽑았다고 각주에 적는다.

3.4지수의 차이가 예산에서 어떻게 보이나

지수 하나가 계획에서 얼마나 다른 숫자를 만드는지는 곱해 보면 드러난다. 아래 표는 데이터가 몇 배로 늘 때 질의당 거리 계산 횟수가 몇 배가 되는지를 지수별로 적은 것이다. 논문에 없는 표이며, 우리가 N의 c제곱을 직접 계산해 만들었다.

우리 산술이다. 맨 오른쪽 열은 비교 기준선으로 둔 값이며, 100만 건에서 출발해 거리 계산이 log N에 비례한다고 가정했을 때의 배수다. 논문이 겨냥하는 대상은 정확히는 다항로그이므로 이 열을 논문이 말하는 로그라고 읽으면 안 된다. 가장 관대한 로그 가정에서도 이만큼 벌어진다는 정도로만 쓸 수 있다.

벡터 하나의 크기를 줄이는 이야기는 페블러스 블로그가 학습 없는 벡터 압축을 다룬 글에서 한 적이 있다. 두 이야기는 곱해진다. 압축은 이 표의 상수를 줄이고, 이 논문은 지수를 말한다.

논문은 로그 확장을 폐기하지 않는다. 적용 구간을 붙인다. 데이터가 충분히 커지면 곡선은 결국 완만해지고, 그때부터는 기존의 다항로그 주장이 맞다는 것이 논문의 결론이다. 그렇다면 그 전환은 언제 오는가. 여기서 직관과 어긋나는 관찰이 나온다.

4.1확실히 꺾인 것은 데이터셋 하나였다

비용 곡선이 분명하게 꺾인 것은 SpaceV 하나다. 10억 건까지 키우자 기울기가 내려갔다. OpenAI 임베딩에 대해서는 격자 실험의 일부 곡선이 적합된 거듭제곱보다 아주 약간 아래로 처지는 것처럼 보인다고 논문이 적는데, 곧바로 판정을 유보한다. "Only larger dataset sizes can tell whether the drift is real." 더 큰 규모라야 그 처짐이 진짜인지 알 수 있다는 뜻이고, OpenAI는 이미 기본 데이터셋 전체를 쓰고 있어 더 키울 수가 없다. 초록은 전환이 두 데이터셋에서 나타났다고 요약하지만 본문이 더 조심스럽다.

그런데 이 둘을 나란히 놓으면 규모의 논리가 무너진다. 전체가 232만 건뿐인 OpenAI 임베딩은 자기 크기의 끝에서 처지는 조짐을 보였고, 10억 건까지 키운 SIFT와 DEEP은 끝까지 곧게 뻗었다. 100만 건 시점에서 잰 내재 차원은 OpenAI가 46.5로 가장 높고 SIFT가 19.2로 낮은 축에 든다. 내재 차원이 더 높은 쪽이 먼저 꺾이고 더 낮은 쪽이 10억 건까지 안 꺾인 것이다. 논문이 여기 붙인 설명은 한 줄뿐이다. SpaceV와 OpenAI에서 본 둔화가 그 두 데이터셋만의 성질은 아니며, 다른 데이터셋도 충분히 큰 규모까지 키울 수 있었다면 같은 전환을 봤으리라는 것. 그러나 왜 하필 이 둘이 먼저였는지는 논문이 따로 설명하지 않는다. 우리도 이유를 지어내지 않고 사실만 나란히 둔다.

4.2내재 차원은 데이터셋의 상수가 아니다

곡선의 모양을 설명하는 이론은 다섯 걸음으로 이어진다. 첫째, 검색 비용은 질의 주변의 좁은 영역에 놓인 점의 개수가 지배한다. 논문은 빔 탐색을 질의 근처까지 다가가는 지름길 단계와 질의 주변을 뒤져 진짜 최근접 이웃을 찾는 이웃 탐색 단계로 나누는데, 측정한 모든 경우에서 이웃 탐색 단계가 비용의 80% 이상을 차지했다.

둘째, 그 영역을 반지름 비율로 (1+ε)배 넓히면 안에 들어오는 점의 개수는 (1+ε)를 내재 차원만큼 거듭제곱한 값에 비례한다. 정리 1이다. 셋째가 이 논문의 핵심 한 줄이다. 밑에 해당하는 (1+ε)를 N의 거듭제곱 꼴로 고쳐 쓰면, 점의 개수는 N의 지수 (d_int / log N) × log(1+ε) 제곱에 비례하는 형태가 된다. log N에 대한 지수는 곧 N에 대한 거듭제곱이다.

(1+ε)라는 비율이 규모에 따라 흔들리지 않는다는 것이 이 논증의 전제인데, 논문은 그것도 따로 잰다. 데이터가 커지면 질의에서 이웃까지의 거리가 전부 같은 비율로 줄어들어 안쪽과 바깥쪽 영역이 함께 수축하므로 반지름의 비는 유지된다. 실제로 방문한 노드들의 정규화 거리 분포를 그려 보면 데이터 크기를 바꿔도 거의 겹친다.

그리고 내재 차원이 자란다는 대목은 실측으로 뒷받침된다. 논문은 국소 내재 차원(LID)을 대리 지표로 삼아 데이터 크기별로 쟀다. 대부분의 데이터셋에서 LID는 로그 축에 대해 거의 직선으로 올라간다. 즉 log N과 나란히 자란다. 예외가 둘인데, OpenAI는 여전히 오르되 기울기가 점점 줄고, SpaceV는 오르다가 거의 평평해진다. 비용 곡선에서 갈라진 그 두 데이터셋이 LID 곡선에서도 갈라진다.

4.3검색을 어렵게 만드는 차원은 따로 있다

데이터셋 여덟 개를 한 표에 놓으면 두 차원이 서로 다른 양이라는 것이 한눈에 보인다. 임베딩 차원은 임베딩 모델이 정하는 벡터의 길이이고, 내재 차원은 그 벡터들이 실제로 놓인 구조의 차원이다.

임베딩 차원과 내재 차원은 논문 Table 2의 값이다. 크기 열은 논문에 없어 원 데이터셋 문서에서 확인했다. GloVe는 ann-benchmarks 표준 배포본 기준 1,183,514건이고 논문이 직접 밝힌 값이 아니다. Wiki-all은 88M·10M·1M 세 변형이 있는데 논문이 어느 것을 썼는지 적지 않았다. Rand64는 이 논문이 64차원 단위구 위 균등분포에서 직접 생성한 합성 데이터라 공개 배포본이 없고 개수도 논문에 적혀 있지 않다.

표에서 두 줄만 보면 된다. Rand64는 임베딩 차원이 64인데 내재 차원이 40.2이고, GIST는 임베딩 차원이 960인데 42.5다. 벡터가 길다고 검색이 어려워지는 것이 아니다. 다만 Rand64는 균등분포에서 뽑은 합성 데이터라 실제 데이터의 사례로 인용할 수 없다. 논문의 계수 표에서도 이 데이터셋 혼자 양 끝값을 차지한다.

내재 차원이 비용을 지배하는 현상은 검색만의 일이 아니다. 페블러스 블로그가 디퓨전 모델이 저차원 분포를 학습하는 방식을 다룬 글에서 정리한 것도 같은 양이 표본 복잡도를 지배한다는 이야기였다.

지수가 상수라면 그 상수는 무엇이 정하는가. 논문은 측정된 지수를 세 가지 요인의 합으로 모형화한다. 데이터셋과 알고리즘마다 계수를 따로 적합했고, 식은 이렇다.

재현율이 지수 안에 로그로 들어간다는 사실이 실무에 주는 함의가 크다. 재현율 목표를 90%에서 99%로 올리면 ln(1/δ)가 2.30에서 4.61로 두 배가 되고, 그만큼 지수가 오른다. 재현율 목표는 오늘의 응답 시간을 올리는 데서 그치지 않고 내년의 성장 곡선 기울기까지 고른다는 뜻이다.

5.1재현율 한 단계가 지수를 얼마나 올리나

논문 본문에는 지수 c의 구체적인 값이 인쇄돼 있지 않다. 적합된 값은 그림 속 곡선 끝에만 적혀 있다. 그래서 아래 표는 논문의 식과 계수 표를 그대로 써서 우리가 계산한 값이다. 조건은 HNSW, 구축 후보 목록 크기 200, 노드당 연결 수 32로 고정했다.

논문의 식과 Table 4-a 계수로 우리가 계산한 값이다. 조건은 HNSW·구축 후보 목록 200·연결 수 32이며, 조건이 바뀌면 값도 바뀐다. 합성 데이터인 Rand64는 뺐다. 값의 폭이 0.17에서 0.66까지 벌어지므로 한 값을 벡터 검색의 지수라고 대표 삼을 수 없다.

GloVe 한 줄만 따라 읽어도 이야기가 된다. 같은 데이터, 같은 인덱스, 같은 설정에서 재현율 목표만 90%에서 99%로 올리면 지수가 0.311에서 0.518로 오른다. 앞 섹션의 배수 표와 같은 방식으로 계산하면, 데이터가 100배가 될 때의 비용 배수가 4.2배에서 10.9배로 갈린다. 회의실에서 재현율 목표를 한 단계 올릴 때 실제로 결정되는 것은 이쪽이다.

이 모형에는 한계도 있다. 지수 모형의 결정계수는 평균 0.88이다. 측정된 지수의 변동 가운데 88%를 설명한다는 말이고, 뒤집으면 12%는 설명하지 못한다. 한편 목표 재현율에 닿으려면 탐색 후보 목록을 얼마나 키워야 하는지를 잇는 별도의 관계식은 결정계수가 0.98을 넘어 훨씬 단단하다.

5.2질의 곡선을 눕히면 구축 곡선이 선다

식을 보면 손쉬운 해법이 떠오른다. 노드당 연결 수와 구축 후보 목록 크기를 올리면 두 항이 음수이므로 지수가 내려간다. 그래프를 촘촘하게 만들면 빔 탐색이 더 적은 도약으로 질의의 이웃에 닿기 때문이다.

그런데 논문은 삽입 비용도 같은 방식으로 모형화한다. 삽입 역시 빔 탐색을 돌려 새 점의 이웃을 찾는 일이라 같은 거리 계산이 지배한다. 구축 쪽 모형에서 노드당 연결 수는 N의 지수를 올리는 자리에 들어간다. 그래프를 촘촘히 할수록 구축 비용이 데이터 크기에 대해 더 가파르게 자란다는 뜻이다. 질의 곡선을 눕히는 손잡이가 구축 곡선을 세우는 손잡이이기도 하다.

구축 후보 목록 크기를 두 배로 하면 평균 삽입 비용이 약 1.8배가 된다. 이 문단의 수치는 모두 논문이 직접 인쇄한 값이다. 구축 쪽 후보 목록 지수는 합성 데이터를 빼면 0.80에서 0.92 사이인데, 이는 질의 쪽 후보 목록 지수보다 0.07에서 0.16 높은 값이다. 삽입이 후보 목록 크기에 더 민감한 이유로 논문은 역방향 링크 재배선을 든다. 새 점을 이웃으로 받아 줄 노드가 이미 연결 수 상한에 닿아 있으면 연결을 다시 짜야 하고, 그 과정에서 추가 거리 계산이 생긴다.

구축 지수의 절대값을 우리가 계산해 인쇄하지 않은 데는 이유가 있다. 논문의 계수를 식에 그대로 넣으면 구축 지수가 1보다 작게 나오는 조합이 생긴다. N개를 넣는 비용이 N보다 느리게 자란다는 뜻이라 물리적으로 성립하지 않는다. 논문이 시험하지 않은 구간을 넘겨짚어서 생기는 일도 아니다. GIST는 시험한 연결 수 네 값 어디에서도 1을 넘지 않는다(우리 계산). 적합의 인공물로 보는 편이 맞고, 그래서 이 절에서는 방향만 쓴다.

검색 비용의 곡선은 결국 사람이 기다리는 시간으로 나타난다. 페블러스 블로그가 에이전트가 모델보다 데이터를 더 오래 기다린다는 관찰을 다룬 글에서 본 것이 그 기다림이다.

지금까지가 실측과 그 실측을 설명하는 모형이었다. 논문은 여기에 형식 증명을 붙인다. 이 부분은 무엇이 증명됐고 무엇이 남았는지를 갈라 읽어야 실무에 쓸모가 있다.

6.1증명은 이상화된 구성 위에 선다

증명의 대상은 실제로 배포되는 인덱스 그대로가 아니다. 논문은 서술을 간명하게 하려고 SNG라는 정확한 구성을 대상으로 삼고, 그 인덱스를 구축하는 비용은 공짜로 친다고 명시한다. 실무에서 쓰는 휴리스틱 버전에 대해서도 같은 결론이 선다고 적지만, 조건이 둘 붙는다. 하나는 성긴 구간에 한한다는 것이고, 다른 하나는 각 노드의 이웃을 고를 때 후보 목록의 크기에 제한이 없어야 한다는 것, 즉 구축 후보 목록이 무한한 경우다. 실증 부분은 실제 구현으로 돌린 결과이지만 이론 부분은 이런 이상화 위에 서 있다.

6.2가장 많이 쓰는 인덱스가 미증명 쪽에 있다

초록은 정확한 구성과 차수 제한 구성 양쪽에 대해 거듭제곱과 결국의 전환을 증명했다고 요약한다. 본문은 더 조심스럽다. 구간별 비용을 정리한 표의 각주가 그 온도차를 그대로 보여 준다. 표의 식들은 일부 그래프 인덱스에 대해서는 상한이 아니라 하한이며 딱 맞지 않을 수 있고, 표의 식이 딱 맞는 것은 정확하게 구성한 Vamana뿐이라고 적혀 있다. SNG의 비용 하한은 다항로그 항보다 크다는 예도 각주에 있다.

이 논문은 2026년 9월 2일에 올라온 프리프린트이고, 동료심사나 학회 게재에 관한 정보는 확인되지 않는다. 재현용 코드나 측정 로그도 함께 공개되지 않았다. 자금 출처와 이해상충에 관한 진술도 논문에 없다. 저자 세 명이 모두 대학 소속이라 벤더 편향을 의심할 이유는 없지만, 독립적으로 검증된 결과라고 쓸 수 있는 단계도 아니다.

그리고 결론 문장을 오독하지 않는 것이 중요하다. 논문은 로그 확장이 틀렸다고 말하지 않는다. "Our experiments and theory confine this claim to scales beyond a transition point." 그 주장을 전환점 너머의 규모로 가둔다는 표현이다. 전환점 아래에서는 거듭제곱이고, 대부분의 실무 데이터셋은 자기 전체 크기까지 그 구간에 머문다는 것이 논문의 요약이다.

6.3용량 계획을 다시 세운다면

이 논문을 계획서의 언어로 옮기면 점검 목록이 나온다. 새 인프라 없이 지금 가진 임베딩만으로 시작할 수 있는 항목부터 놓았다.

1. 우리 데이터의 국소 내재 차원을 크기를 바꿔 가며 잰다. 한 번 재고 상수로 쓰면 이 논문의 요지를 놓친다. 논문이 쓴 방법은 무작위 질의 500개와 여섯 가지 k 값에 대해 최근접 이웃 거리의 최대우도 추정량을 적용하는 것이었다.
2. 그 값이 데이터 크기의 로그와 나란히 자라는지 본다. 자라고 있으면 아직 성긴 구간이고, 비용은 거듭제곱으로 늘어난다고 봐야 한다.
3. 재현율 목표를 먼저 정한다. 목표가 정해져야 지수를 가늠할 수 있다. 90%와 99%는 지수 안의 항이 두 배 차이다.
4. 그 지수로 내년 데이터 규모의 질의 비용을 환산한다. 데이터 배수의 c제곱이 곧 비용 배수다.
5. 같은 파라미터가 구축 비용에 주는 반대 방향의 효과를 함께 본다. 질의 곡선만 보고 그래프를 촘촘히 하면 삽입 쪽에서 대가를 치른다.
6. 질의가 문서와 다른 분포에서 온다면, RAG에서 흔한 경우인데, 논문은 겹치는 매니폴드 가운데 가장 높은 내재 차원이 비용 증가를 지배한다고 적는다. 여러 매니폴드의 평균으로 뭉개면 안 되고 그중 최댓값을 기준으로 잡아야 한다.

측정 도구와 그 비용까지는 이 글이 안내하지 않는다. 논문이 쓴 방법을 옮기는 데서 멈춘다.

페블러스는 데이터를 진단하고 품질 성적서를 발급하는 일을 한다. 검색 인프라의 비용 곡선이 우리 일과 닿는 지점은 분명하다. 이 논문이 곡선의 주인으로 지목한 것은 인덱스가 아니라 데이터다.

7.1진단은 값의 문제에서 분포의 문제로 넓어진다

AI-Ready Data는 모델이 바로 먹을 수 있는 형태의 데이터를 다룬다. 벡터 검색에서 그 형태를 좌우하는 것이 임베딩을 몇 개 모았느냐보다 그 임베딩이 놓인 데이터의 성질이라는 것이 이 논문의 실질적 함의다. 같은 100만 건이라도 내재 차원이 다르면 성장 곡선이 다르고, 예산도 다르게 잡혀야 한다. 기존 진단이 결측과 중복과 라벨 오류처럼 값의 문제를 봤다면, 여기서 늘어나는 것은 분포의 문제다. 이 데이터가 자기 분포를 얼마나 드러냈는가. 이 질문이 DataClinic의 진단 항목으로 들어온다.

7.2품질은 그 데이터가 놓인 구조이기도 하다

품질을 값의 정확성만으로 보면 이 논문의 관찰이 보이지 않는다. 데이터가 어떤 구조 위에 놓였는가도 품질이다. 이 논문은 그 구조적 성질이 검색 비용의 성장 곡선을 지배한다는 것을 실측으로 보였다. 데이터를 더 모으는 결정이 곧 비용 곡선을 고르는 결정이 되는데, 대부분의 조직은 자기 데이터의 이 성질을 재 본 적이 없다. 데이터가 먼저라는 이야기가 이번에는 검색 인프라 예산의 언어로 돌아온다.

7.3인덱스부터 바꾸자는 대화는 순서가 틀렸다

6.3절의 점검 목록이 그대로 실무 처방이다. 강조점은 순서에 있다. 인덱스를 바꾸는 일부터 검토하면 대화가 제품 비교에서 멈춘다. 크기를 바꿔 가며 내재 차원을 재는 일은 새 인프라 없이 기존 임베딩만으로 할 수 있고, 그 결과가 성긴 구간인지 조밀 구간인지를 먼저 알려 준다. 그리고 벤더 문서의 로그라는 단어를 계획서에 그대로 옮겨 적지 않는 것, 벤치마크 수치가 한 가지 크기에서 잰 값이라는 것을 아는 것. 두 가지는 오늘 오후에 할 수 있는 일이다.

7.4규모를 늘리기 전에 데이터의 성질부터 잰다

벡터를 압축해 저장 비용을 줄인 이야기가 상수의 문제였다면, 이번 글은 지수의 문제다. 둘 다 같은 질문의 두 판형이다. 임베딩을 얼마나 모을지 묻기 전에, 그 임베딩이 놓인 데이터가 어떤 구조인지를 먼저 묻는다. 데이터의 성질을 먼저 재고 규모는 그다음에 늘리는 순서, 이 글이 닿는 곳은 거기다.

본문의 수치는 세 갈래다. 실험 조건과 계수는 1번 논문의 전문에서 직접 대조해 옮겼고, 확장 실험의 조건과 이탈 관찰은 2번 논문의 전문에서 확인했다. 업계 문서의 표현은 각 문서를 직접 열어 축자로 옮겼으며 조회일을 함께 적었다. 지수의 구체적 값은 어느 문헌에도 인쇄돼 있지 않아 1번 논문의 식과 계수로 우리가 계산했다.

이 보고서의 뼈대 (1차 원문 대조)

• 1.Sajad Faghfoor Maghrebi, Navid Eslami, Niv Dayan (University of Toronto). "A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search." arXiv: 2609.02143, v1 2026년 9월 2일 제출, 17쪽 10그림, cs.DB. 본문의 실험 설계, Table 2·3·4, 정리 1과 따름정리 2, 5절의 비용 모형, 6절 결론 인용은 이 전문에서 확인했다. 동료심사 정보와 공개 코드는 확인되지 않는다.
• 2.Yu. A. Malkov, D. A. Yashunin. "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs." arXiv: 1603.09320, v4 2018년 8월 14일, cs.DS. 확장 실험의 조건(Fig. 12, 8차원 합성 벡터, 재현율 0.95 고정)과 5.4절의 "the scaling deviates from the pure logarithm" 문장을 이 판본에서 확인했다. 저널 게재본은 별도로 확인하지 않았다.

업계 문서 (축자 확인, 2026년 9월 5일 조회)

• 3.Milvus. "Index Explained." milvus.io/docs/index-explained.md. 라이브 페이지가 봇 차단으로 열리지 않아 2026년 5월 12일 웨이백 스냅숏에서 확인했다.
• 4.Weaviate. "Vector Indexing." weaviate.io/developers/weaviate/concepts/vector-index.
• 5.Pinecone. "Hierarchical Navigable Small Worlds (HNSW)." pinecone.io/learn/series/faiss/hnsw. 여섯 문서 가운데 유일하게 다항로그 가능성을 표기에 열어 둔다.
• 6.Redis. "How Hierarchical Navigable Small World (HNSW) Algorithms Can Improve Search." redis.io/blog/how-hnsw-algorithms-can-improve-search. 자기 주장 대신 2번 논문을 따옴표로 인용한다.
• 7.OpenSearch. "k-NN Performance Tuning." docs.opensearch.org/1.0/search-plugins/knn/performance-tuning.
• 8.Elastic. "Vector search and kNN implementation guide, API edition." elastic.co/search-labs/blog/vector-search-implementation-guide-api-edition. 여섯 문서 가운데 유일하게 조건절을 단다.

데이터셋 (크기 확인)

• 9.SIFT1B (Jégou et al. 2011), DEEP1B (Babenko & Lempitsky 2016), SpaceV1B (Microsoft 2021). 각 10억 건이라는 사실은 1번 논문 3.3절이 직접 적는다.
• 10.OpenAI-ArXiv (big-ann-benchmarks 배포본). 2,321,096건, 1536차원, 질의 2만 건. 1번 논문의 참고문헌 항목에 수치가 인쇄돼 있다.
• 11.GloVe-100 (ann-benchmarks 표준 배포본). 1,183,514건, 100차원, 질의 1만 건, 각도 거리. 2026년 9월 5일 조회. 1번 논문이 직접 밝힌 값이 아니다.
• 12.GIST1M (TEXMEX corpus, INRIA/IRISA). 100만 건, 960차원, 질의 1,000건. 2026년 9월 5일 조회.
• 13.Wiki-all (RAPIDS cuVS 문서). 88M·10M·1M 세 변형이 있고 1번 논문의 참고문헌 항목은 88M 버전을 설명한다. 실험에 쓴 변형이 무엇인지는 본문에 명시돼 있지 않다.