English · 한국어
성능과 동작 원리¶
성능¶
정확한 k-NN은 행 수의 제곱에 비례합니다. 행 수가 두 배가 되면 시간은 대략 네 배가 되고,
10만 행 전체 감사(--sample 0)는 노트북에서 수 분이 걸립니다.
k-NN 계산은 행 수와 무관하게 거리 행렬을 1GiB 안팎으로 유지하도록 행 블록 크기를 조절합니다. 나머지 계산은 행렬의 float32 복사본 몇 벌을 쓰므로 최대 메모리는 행 수 × 차원에 비례해 행렬 크기의 약 네 배까지 커집니다.
감사의 실행 시간과 Python이 추적한 최대 메모리는 다음과 같습니다(입력 행렬 자체는 별도로 더 필요합니다).
| 행 수 | 차원 | 초 | 최대 메모리 (입력 제외) |
|---|---|---|---|
| 10,000 | 384 | 1.3 | 0.40 GiB |
| 10,000 | 768 | 2.0 | 0.41 GiB |
| 10,000 | 1,536 | 3.6 | 0.44 GiB |
| 50,000 | 384 | 17 | 1.63 GiB |
| 50,000 | 768 | 23 | 1.70 GiB |
| 50,000 | 1,536 | 36 | 1.84 GiB |
| 100,000 | 384 | 65 | 1.71 GiB |
| 100,000 | 768 | 86 | 1.85 GiB |
| 100,000 | 1,536 | 130 | 3.45 GiB |
| 200,000 | 768 | 338 | 3.46 GiB |
| 200,000, 기본 표본 10만 | 768 | 85 | 2.14 GiB |
8 vCPU AMD EPYC 7R13에서 BLAS 스레드 8개로 잰 값입니다(NumPy 단일 프로세스, 군집 구조의 합성 코퍼스, k=10). 별도 프로세스에서 3회 반복한 중앙값과 이 1회 측정의 차이는 2% 이내였고, OS가 본 최대 메모리와의 차이도 0.04 GiB 이내였습니다.
- 시간은 5만 행 이상에서 행 수가 두 배가 될 때 3.5~3.9배 늘어 n²에 가깝습니다.
- 메모리는 384·768차원에서는 5만 행 이후 거의 변하지 않다가(k-NN 블록 크기가 n에 따라 줄어들기 때문) 1,536차원과 20만 행에서 한 단계 올라갑니다.
- 기본값인 10만 행 표본은 어떤 코퍼스든 비용을 10만 행 수준으로 묶어 둡니다.
--queries는 질의 묶음마다 코퍼스를 한 번 더 훑고,metric_mismatch는 벡터 길이가 다를 때만 k-NN을 한 번 더 계산합니다.
원하는 규모에서 직접 다시 재려면 다음을 실행합니다.
python examples/benchmark_scale.py --rows 50000 100000 --dim 768 # 위 감사 표
python examples/benchmark_sweep.py # 인덱스 스윕
두 스크립트 모두 --corpus 옵션(clustered, isotropic, anisotropic, duplicates, lowrank,
zipf)을 받고 실행 환경 정보를 JSON에 함께 기록합니다.
표본 감사¶
블록 계산이 제한하는 것은 메모리이지 연산량이 아닙니다. 정확한 k-NN은 여전히 n² × 차원에 비례하는 곱셈이 필요하므로, 768차원 100만 행은 10만 행의 약 100배가 듭니다.
그 규모의 코퍼스는 기본 표본(또는 --sample-repeats로 표본 여러 개)을 감사하고, --sample 0은
전체 행이 꼭 필요한 항목에만 쓰십시오. 표본 감사는 표본에 대한 설명입니다. 전체 행이 필요한
항목은 다음과 같습니다.
| 항목 | 표본으로 얻는 것 | 전체 행이 필요한 경우 |
|---|---|---|
| anisotropy, effective_rank, rogue_dimensions, norms, metric_mismatch, distance_concentration | 분포 추정치. 20만 × 384 코퍼스에서 표본 10만·5만·2만 모두 전체 값과 2.3% 이내로 같았고 판정도 같았음 | 없음 |
| hubness, antihubs | 하한값. k-출현 빈도는 밀도가 높을수록 쏠리므로 같은 코퍼스라도 표본이 작으면 hubness가 낮게 나옴(20만 행 전체 2.6 warn, 4분의 1 표본 1.15, 10분의 1 표본 0.16). fail이 아닌 판정은 inconclusive로 표시 |
코퍼스 자체의 hubness를 잴 때 |
| collapse | 표본 안에서 확인된 중복 비율. 중복 쌍의 두 행이 모두 뽑혀야 세므로 표본 비율 × 전체 비율의 0.96~1.03배가 나옴. 판정은 이를 되돌려 추정한 전체 비율로 내리되, 전체 행에서 센 완전 복제 비율보다 작게 잡지 않음 | 모든 근접 중복을 세거나 나열할 때 |
| outliers | 작은 표본에서 실제보다 많이 잡힘(10분의 1 표본에서 3.9배). ok가 아닌 판정은 inconclusive로 표시 |
모든 이상치를 찾을 때 |
| connectivity | 표본으로 만든 k-NN 그래프의 섬. 코퍼스의 섬은 대부분 보이지 않음(전체 행의 37%가 섬인 코퍼스가 4분의 1 표본에서는 0.08%). fail이 아닌 판정은 inconclusive로 표시 |
항상. 표본으로는 판단할 수 없음 |
| ann_recall | 표본에서는 불가. 행 번호가 ANN 파일과 맞아야 함 | 항상 (--sample 0) |
| query_gap, query_shift, query_hubness, ood_queries | 표본에서 구한 기준 거리. 질의는 모두 평가. query_gap은 표본이 작을수록 함께 커지는 두 거리의 비율이고, query_shift는 표본 크기가 같은 기준선과만 비교 | 없음 |
그래서 표본 감사는 다음과 같이 처리합니다.
evidence_scope를sampled로 둡니다(모든 행을 감사했으면full). 코퍼스 전체를 대신할 수 없는 판정, 즉 불확정(inconclusive) 항목과--sample-repeats를 썼을 때의 불안정 항목을needs_full_audit에 나열합니다. JSON을 받는 쪽은 항목별 주의 문구를 읽지 않아도 이 두 키로 게이트를 걸 수 있습니다.- 표에서 inconclusive로 표시한 판정들이
inconclusive_findings목록으로 들어갑니다. - 그 판정들은 텍스트 출력에서는
INCONCLUSIVE (sampled)로, gate 줄에서는 이름으로 표시됩니다. - collapse 판정은
details.estimated_full_share로 내립니다(아래 참고). - 각 항목의 설명문에도 이 주의 사항이 숫자 바로 옆에 붙습니다.
estimated_full_share는 표본 비율로 되돌려 추정한 전체 비율이고, 전체 행에서 센 완전 복제
행의 비율(details.full_corpus_exact_copy_share)이 더 크면 그 값을 씁니다. 완전 복제는 행마다
해시 하나로 전체 코퍼스에서 싸게 셀 수 있어서, 표본이 놓친 드문 복제도 셉니다. 완전 복제가
아닌 근접 중복은 표본 안에서만 보입니다.
20만 행 수치는
검증 결과에서 가져왔고, tests/test_regression_injection.py가 같은 성질을
6천 행 규모에서 매번 검사합니다.
모든 수치는 감사한 행에 대해 정확합니다. vecscope는 정확한 이웃 탐색을 근사 탐색으로 대체하지 않으며, 근사가 들어가는 곳은 행의 선택뿐입니다.
동작 원리¶
vecscope는 행렬 전체의 정확한 k-NN을 한 번만 계산하고, 모든 진단을 그 결과에서 끌어냅니다.
- k-출현 빈도 분포에서 hubness와 antihubs를 구합니다.
- 최근접 이웃 거리에서 collapse, outliers, distance_concentration을 구합니다.
- k-NN 그래프에서 connectivity를 구합니다.
- 무작위 쌍과 공분산 스펙트럼에서 anisotropy, effective_rank, rogue_dimensions를 구합니다.
- 벡터 길이에서 norms를 구합니다.
- metric_mismatch는 내적 기준 k-NN을 한 번 더 계산해 비교하되, 벡터 길이가 모두 같으면 건너뜁니다.
- ANN 이웃 파일이 있으면 정확한 이웃과 비교해 재현율을 구합니다.
질의 임베딩이 있으면 코퍼스를 대상으로 정확 검색을 한 번 더 수행해 질의 측 항목을 구합니다.
같은 입력에는 언제나 같은 결과가 나옵니다. 시드가 고정되어 있고, 이웃은 근사 없이 정확하게 계산하며, 학습된 모델이나 네트워크 통신도 수행하지 않습니다. 같은 파일을 두 번 감사하면 JSON이 완전히 일치합니다.
정확한 k-NN은 행 수의 제곱에 비례하는 비용이 들기 때문에, 10만 행을 넘는 입력은 --sample 0을
지정하지 않는 한 고정 시드로 뽑은 표본만 감사합니다.