When Does a Partitioned ANN Index Need Active Re-Partitioning Under Drift?  A Characterization and Benchmark 

기술 요약: 드리프트(Drift) 발생 시 파티션된 ANN 인덱스의 능동적 재파티셔닝이 필요한 시점은 언제인가?

문제 정의
근사 근접 이웃(ANN) 인덱스는 지속적인 삽입, 삭제 및 모델 업데이트로 인해 데이터 분포가 변화하는 비정상성 코퍼스(non-stationary corpora)를 처리하는 경우가 점점 늘어나고 있다. Quake, Ada-IVF, GTI, CrackIVF, SPFresh 등 시스템 연구 분야의 지배적인 전제는 정적 파티션이 데이터 드리프트에 의해 노후화되어, 능동적으로 재파티셔닝(분할, 병합, 재클러스터링 또는 크래킹을 통해)하지 않으면 리콜(recall) 붕괴가 발생한다는 것이다. 본 논문은 이러한 전제의 보편성에 의문을 제기하며, 구체적으로 어떤 드리프트 조건에서 능동적 재파티셔닝이 실제로 필요한지, 반대로 정적 인덱스가 약간 조정된 프로브 예산(probe budget)만으로도 드리프트를 흡수할 수 있는 경우는 언제인지를 묻는다.

방법론
저자들은 기존 시스템들의 헤드 투 헤드 벤치마크를 수행하는 대신, 유지보수 비용과 재구축 비용 간의 트레이드오프를 규명하기 위해 통제된 매칭 리콜 하네스(matched-recall harness)를 구축하였다. 주요 방법론적 구성 요소는 다음과 같다:

• 매칭 리콜 프로토콜(Matched-Recall Protocol): 비용 노브(예: 프로브 예산 $b$)를 고정하고 리콜을 측정하는 기존 벤치마크와 달리, 이 프로토콜은 리콜 하한선(0.90)을 고정하고 이를 달-성하기 위한 최소 프로브 예산($b_{needed}$)과 지연 시간(latency)을 측정한다. 이는 변화하는 커버리지(예: 파티션 분할이 고정된 $b$가 커버하는 질량을 감소시키는 현상)의 혼란 효과로부터 유지보수 비용을 격리한다.
• 워크로드 생성기: 저자들은 매개변수화된 드리프트 축을 사용한다:
  • Turnover ($\tau$): 라이브 세트가 교체되는 비율.
  • Update Rate ($u$): 쿼리 대비 업데이트의 비율.
  • Correlation ($\rho$): 데이터 드리프트와 쿼리 드리프트의 디커플링.
  • Bounded Window: 카디널리티는 일정하게 유지되면서 분포가 회전하는 모드로, 규모 효과(scale effects)로부터 드리프트를 격리한다.
• 공유된 그라운드 트루스(Shared Ground Truth): 콘텐츠 키 기반의 정확한 그라운드 트루스를 체크포인트마다 한 번씩 계산하여 모든 실험군(static, split/merge, recluster, rebuild)이 공유하도록 함으로써 공정한 비교를 보장한다.
• 사전 등록된 킬 게이트(Pre-Registered Kill-Gates): 실패하는 가설을 "구조"하는 것을 방지하기 위해 일련의 검증 가능한 기준을 채택한다. 만약 특정 가설(예: "graph-in-leaf가 정적 승리이다")이 게이트를 통과하지 못하면, 연구는 파라미터를 조정하여 긍정적인 결과를 강제하는 대신 방향을 전환한다.
• 테스트된 실험군:
  • Static (C0): 유지보수 없음, 툼스톤(tombstone) 삭제 사용.
  • Maintenance Variants: 드리프트 트리거 방식의 split/merge, 카디날리티 트리거 방식의 split, 점진적 재중심화(incremental re-centering).
  • Reference (R): 품질 베이스라인 역할을 하는 인-아키텍처 풀 리클러스터(rebuild from scratch).
  • External Check: 동일한 트레이스에 대해 외부 검증을 위해 실제 Quake 아티팩트(OSDI'25)를 실행함.

주요 결과

1. 중간 정도의 드리프트에서의 정적 충분성(Static Sufficiency):
   중간 정도의 성장/교체(SIFT1M, GIST1M)가 발생하는 데이터셋에서, 툼스톤 삭제를 사용하는 정적 파티션은 유지보수된 변형 모델들과 동일한 프로브 예산으로 0.90 리콜 하한선을 유지한다. 이 영역에서는 능동적 유지보수가 불필요하며, 프로브 예산의 "여유(slack)"가 드리프트를 흡수한다.

2. Graph-in-Leaf는 정적 승리가 아니다:
   그래프-인-리프(graph-in-leaf) 하이브리드 인덱스는 정적 리콜-QPS 프런티어에서 평면 HNSW(flat HNSW)에 의해 파레토 우위에 있다. 이는 정적 탐색 이점을 제공하지 않으며, 오직 더 빠른 빌드 시간만을 제공할 뿐이다.

3. 영역 경계 (회전 드리프트):
   실제 규모 제어된 회전 윈도우(MS-Turing-10M) 데이터셋에서, 정적 파티션은 실질적으로 성능이 저하된다. 분포가 회전함에 따라 요구되는 프로브 예산($b_{needed}$)이 64에서 112 이상으로 상승한다. 이 영역에서는 재중심화(re-centering)가 진정으로 필요하다.

4. 점진적 재중심화 vs. 풀 리빌드:
   회전 드리프트 영역에서, 저렴한 점진적 재중심화는 풀 리클러스터와 동일한 리콜 품질(동일한 $b_{needed}$)을 약 1/6의 재생 비용으로 달성한다.

   • 총 소유 비용(TCO): 현실적인 쿼리 집약적 워크로드에서 점진적 재중심화와 풀 리빌드는 TCO 측면에서 동등하다. 점진적 재중심화가 엄격하게 승리하는 경우는 업데이트 집약적 워크로드뿐이다.
   • 리빌드 선호 교차점 부재: 본 논문은 풀 리빌드가 더 우월해지는 교차점($u^* \approx 4.7$)이 존재한다는 이전의 주장을 반박하며, 이를 신선한 빌드 레이턴시를 오래된 인덱스에 잘못 귀속시킨 결과와 순차적 타이밍 드리프트의 산물로 식별하였다.

5. 외부 검증 (Quake):
   동일한 트레이스에서 실제 Quake 시스템을 실행한 결과, 영역 경계가 확인되었다: Quake는 제한된 스캔 분율 내에서 리콜 하한선을 유지한다. 그러나 기본 사이즈 트리거 정책은 인덱스를 파편화하여(nlist를 13배 증가시킴) 높은 유지보수 비용을 초래한 반면, 제어된 재중심화는 적은 예산으로 효율적으로 유지되었다.

기여

1. 통제된 벤치마크: 데이터/쿼리 드리프트를 분리하고 영역별 그라운드 트루스를 제공하는 매개변수화된 드리프트 워크로드 및 매칭 리콜 프로토콜.
2. 영역 맵(Regime Map): "정적 충분" 영역(중간 정도의 성장/교체)과 "재중심화가 도움이 되는" 영역(회전 드리프트)을 구분하는 특성화.
3. 의사결정 규칙: 실무자를 위한 가이드:
   • 중간 정도의 성장: 정적 상태를 유지하고, 툼스톤 삭제와 약간 더 큰 프로브 예산을 사용하라.
   • 회전 드리프트: 재중심화하되, 풀 리빌드 대신 점진적 재중심화를 사용하라.
   • 트리거 선택: 드리프트 기반 트리거와 카디날리티 기반 트리거는 리콜 차이가 없으므로, 엔지니어링 편의성에 따라 선택하라.
4. 설명 프레임워크: 드리프트가 흡수 가능한지 아니면 재파티셔닝을 강제하는지를 설명하는 "프로브 예산 여유(probe-budget slack)" 모델 ($\sigma < b$).
5. 정직한 부정적 결과(Negative Results): 그래프-인-리프가 정적 승리가 아니라는 점과, 재중심화 없는 split/merge는 드리프트를 줄이는 것이 아니라 인덱스를 파편화할 뿐이라는 점 등 업계의 과잉 주장들을 바로잡음.

의의 및 주장
본 논문은 주요 기여가 새로운 유지보수 알고리즘이 아니라 영역 맵과 의사결정 규칙이라고 주장한다. 또한 "드리프트가 능동적 재파티셔닝을 필 necessarily 한다"는 전제는 조건부임을 강조한다.

• 여유 영역(Slack regime) (중간 정도의 드리프트)에서 유지보수는 정답성의 필수가 아니라, 종종 불필요한 비용 트레이드오프이다.
• 강제 영역(Forced regime) (회전 드리프트)에서 유지보수는 필요하지만, 풀 리빌드는 피할 수 있다. 점진적 재중심화는 풀 리빌드의 훨씬 적은 비용으로 동일한 리콜 품질을 달성한다.
• 본 논문은 매칭 리콜 및 컨텐션 제어 프로토콜이 유지보수의 필요성과 비용에 대한 잘못된 결론(예: 고정 예산 비교)을 초래했던 기존의 혼란 효과를 방지한다는 점에서 그 자체로 중요한 기여라고 강조한다.

저자들은 자신들의 연구가 모든 드리프트 모드(예: 순수 소멸 드리프트 또는 실제 쿼리 드리프트 트레이스)를 해결했다고 주장하지 않으며, 연구 결과가 특정 인덱스 제품군(k-means 라우터와 HNSW/flat leaves를 갖는 구조) 및 테스트된 드리프트 크기에 국한됨을 명시한다.