Memory-Efficient FastText: A Comprehensive Approach Using Double-Array Trie Structures and Mark-Compact Memory Management

기술 요약: Double-Array Trie 구조와 Mark-Compact 메모리 관리를 이용한 효율적인 FastText 접근 방식

문제 정의

본 논문은 산업 규모의 FastText 구현에서 발생하는 고유한 "서브워드 메모리 장벽(subword memory wall)" 문제를 다룹니다. FastText는 n-gram을 통해 미등록 단어(OOV)에 대한 벡터를 생성하는 능력으로 가치가 높지만, 표준 구현은 n-gram을 임베딩 행으로 매핑하기 위해 해시 버킷(hash buckets)에 의존합니다. 이 방식은 두 가지 공학적 타협을 강요합니다:

1. 임의적 충돌(Arbitrary Collisions): 서로 관련 없는 n-gram들이 동일한 파라미터 행을 공유하도록 강제되어, 특정 n-gram에 충실하지도 않고 디버깅하기도 어려운 표현을 생성합니다.
2. 메모리 스케일링(Memory Scaling): 충돌을 줄이기 위해 해시 버킷의 수를 늘려야 하며, 이는 입력 행렬의 메모리 점유율을 선형적으로 증가시킵니다.

수천만 개의 단어를 가진 대규모 어휘집의 경우, 고유한 n-gram의 수는 수억 개에 달할 수 있습니다. RAM 제약으로 인해 충돌이 없는 정확한 행렬을 저장하는 것은 종종 불가능하지만, 대안인 해싱(hashing)은 통제되지 않는 의미론적 노이즈를 유발합니다. 본 논문은 임의적인 해싱이 피할 수 있는 압축 정책이며, 서브워드 시스템은 왜 행(row)이 공유되었는지 감사(audit)할 수 있어야 한다고 주장합니다.

방법론: "정확성 우선 압축(Exact-Then-Compress)" 원칙

제안된 솔루션은 표준 워크플로우를 역전시킵니다. 학습 전 해싱을 통해 압축하는 대신, 이 방법은 먼저 모든 서브워드에 대해 정확한 정체성을 확립한 후 구조화된 압축을 적용합니다. 파이프라인은 네 가지 주요 단계로 구성됩니다:

1. 충돌 없는 인덱싱 (Double-Array Tries):
   저자들은 단어와 n-gram 모두에 대해 해시 버킷을 Double-Array Trie(DA-trie)로 대체합니다. DA-trie는 결정론적이고 선형 시간 조회를 지원하는 조밀한 배열 표현입니다. 이를 통해 모든 관찰된 n-gram은 압축이 수행되기 전에 고유하고 명시적인 정체성(row ID)을 할당받습니다. 구현은 UTF-8을 인식하여 멀티바이트 문자를 단일 단위로 처리합니다.

2. 구조 제약 기반 행 공유 (Structure-Constrained Row Sharing):
   정확한 정체성이 확립되면, 이 방법은 언어적 규칙성을 활용합니다: n-gram이 긴 접두사(prefix)나 접미사(suffix)를 공유할 때 학습된 벡터의 코사인 유사도가 높은 경우가 많다는 점입니다.

   • 접두사/접미사 병합: 알고리즘은 두 번의 패스를 수행합니다. 첫째, 접두사 트라이(prefix trie)를 순회하여 구조적으로 연관된 이웃을 찾습니다. 둘째, 문자열을 뒤집고 접미사 트라이(suffix trie)를 순회합니다.
   • 유사도 임계값: 병합은 엄격하게 조건부로 이루어집니다. 두 행은 코사인 유사도가 높은 임계값(예: $\tau = 0.999$)을 초과할 때만 병합됩니다. 이는 공유가 임의적인 충돌이 아니라 감사 가능한 근거에 기반함을 보장합니다.

3. Mark-Compact 메모리 관리:
   병합 후, 임베딩 행렬에는 "데드(dead)" 행(더 이상 n-gram에 의해 참조되지 않는 행)과 간극(gap)이 존재하게 됩니다. 저자들은 다음과 같이 mark-compact 가비지 컬렉션 전략을 응용합니다:

   • 살아있는(live) 행들을 식별하고 밀집된 연속적 새 ID를 할당합니다.
   • 간극을 제거하기 위해 행들을 앞으로 이동시킵니다.
   • DA-trie의 터미널 값(terminal values)을 새로운 밀집 ID를 가리도록 업데이트합니다.
     이 결과로 캐시 친화적인 밀집 행렬 레이아웃이 생성됩니다.

4. 서빙 레이아웃 (Serving Layout):
   최종 모델은 메타데이터, DA-trie, 그리고 압축된 임베딩 행렬을 포함하는 단일 바이너리 파일로 직렬화됩니다. 이 파일은 메모리 맵(mmap) 로딩을 지원하여, OS가 워커 프로세스 간에 페이지를 공유할 수 있게 하며, 정확한 단어 및 서브워드 행의 평균을 통해 단어 벡터를 빠르고 낮은 지연 시간으로 재구성할 수 있게 합니다.

핵심 기여

• Exact-Then-Compress 파이프라인: 정체성 매핑(DA-tries), 파라미터 공유(유사도 제약 병합), 서빙 레이아웃(mark-compact)을 분리하여 임의적인 해시 충돌을 제거하는 새로운 설계를 제시합니다.
• DA-Trie 통합: UTF-8 인식 열거를 포함하여, 단어와 n-gram 모두에 DA-trie를 사용한 충돌 없는 FastText 인덱싱을 공식화했습니다.
• 이중 패스 압축 알고리즘: 언어적 구조를 사용하여 안전한 압축 기회를 찾는 접두사 및 접미사 행 공유 알고리즘을 통해 비용이 많이 드는 전역 최근 이웃(nearest-neighbor) 탐색을 피합니다.
• 프로덕션 준비 완료 구현: 메모리 맵 서빙을 지원하는 확장된 C++ FastText 프로토타입을 통해, 하이브리드 검색 시스템을 위한 결정론적 렉시컬 메모리 계층을 제공합니다.

실험 결과

이 방법은 3,010만 개의 고유 단어와 2억 8,740만 개의 고유 n-gram을 포함하는 대규모 중국어 어휘 벤치마크에서 평가되었습니다.

• 메모리 절감: 압축된 모델은 메모리 사용량을 기존 Hash-Bucket FastText의 145.2 GB에서 28.9 GB로 줄였습니다. 이는 기존 FastText 대비 5.0배, 완전 압축되지 않은 해시 프리(hash-free) 베이스라인 대비 9.9배의 감소를 나타냅니다.
• 로딩 속도: 더 작고 연속적인 파일 크기와 페이지 폴트 감소 덕분에 콜드 로드(cold load) 시간이 12.3분에서 3.2분으로 개선되었습니다.
• 품질 보존: 압축된 모델은 단어 유사도, 유추(analogy), 텍스트 분류 및 개체명 인식(NER) 작업 전반에서 압축되지 않은 해시 프리 모델과 0.3 포인트 이내의 차이를 유지하며 품질을 보존했습니다. 특히, 모든 작업에서 기존 해시 버킷 베이스라인보다 우수한 성능을 보여, 임의적인 충돌을 제거하는 것이 모든 파라미터를 유지하는 것보다 유익함을 입증했습니다.
• 서빙 성능: 프로덕션 스타일 벤치마크에서 제안된 모델은 p95 지연 시간을 34% 감소(47ms에서 31ms로)시켰고, 처리량(throughput)을 58% 증가(850에서 1340 requests/sec로)시켰습니다.

의의 및 주장

본 논문은 이 연구를 현대 LLM 임베딩의 대체재가 아닌, "LLM 시대"를 위한 보완적 인프라 구성 요소로 포지셔닝합니다.

• 렉시컬 메모리 계층 (Lexical Memory Layer): 저자들은 압축 가능하고 충돌이 없는 서브워드 테이블이 결정론적이고 검사 가능하며 저렴한 "렉시컬 메모리 계층" 역할을 한다고 주장합니다. 이 계층은 대규모 인코더가 일관성 없게 처리할 수 있는 롱테일 엔티티(이름, 오타, 식별자 등)를 처리하거나, 1단계 리콜(recall), 특징 생성에 이상적입니다.
• 감사 가능성 (Auditability): 불투명한 해시 충돌을 명시적인 구조적 공유로 대체함으로써, 엔지니어가 왜 두 행이 병합되었는지 정확히 추적할 수 있게 하여 압축 과정을 측정 가능하고 재현 가능하게 만듭니다.
• 하이브리드 검색 (Hybrid Retrieval): 이 방법은 RAG(검색 증강 생성) 파이프라인의 특정 간극을 메웁니다. 즉, 대규모 임베딩 인덱스의 높은 갱신 비용이나 메모리 오버헤드 없이, 덴스 리트리버(dense retriever) 및 스파스 확장 모델(sparse expansion model)과 결동할 수 있는 작고 예측 가능하며 다국어 지원이 가능한 렉시컬 기질을 제공합니다.

결론적으로, 본 논문은 산업용 NLP 시스템에 있어 "불투명한 충돌을 명시적 정체성으로 교체한 다음, 드러난 구조를 사용하여 압축한다"는 패턴이 경제적인 배포와 견고한 롱테일 커버리지를 위한 실질적인 경로를 제공한다고 밝히고 있습니다.