Faster Superword Tokenization

이 논문은 대규모 언어 모델 (LLM) 에 널리 사용되는 서브워드 토크나이저인 바이트 페어 인코딩 (BPE) 의 한계를 극복하고, 기존 'Superword' 알고리즘 (BoundlessBPE, SuperBPE) 의 훈련 속도를 획기적으로 개선한 방법을 제안합니다.

주요 내용은 다음과 같습니다.

1. 문제 제기 (Problem)

• BPE 의 한계: 기존 BPE 는 사전 토큰화 (pre-tokenization) 경계를 넘지 못하도록 제한되어 있어, 완전한 단어 이상의 구 (phrase) 단위로 토큰을 생성할 수 없습니다. 이는 압축률과 토큰 분포의 균일성 측면에서 비효율적입니다.
• Superword 의 필요성: BoundlessBPE 와 SuperBPE 는 이 제한을 완화하여 인접한 사전 토큰들을 합쳐 '슈퍼워드 (superword)'를 형성함으로써 BPE 의 성능을 개선했습니다.
• 훈련 속도의 병목 현상: 그러나 기존 구현체들은 슈퍼워드 후보를 찾기 위해 모든 문서의 원본 토큰 시퀀스를 메모리에 보관해야 했습니다. 이로 인해 훈련 속도가 매우 느렸습니다 (예: 1GB 데이터 기준 BoundlessBPE 는 4.7 CPU 일 소요). 이는 대규모 데이터셋 학습을 실용적으로 불가능하게 만드는 주요 장벽이었습니다.

2. 방법론 (Methodology)

저자들은 두 가지 핵심 기법을 통해 훈련 속도를 획기적으로 높였습니다.

• 슈퍼머지 후보 집계 (Supermerge Candidate Aggregation):

  • 기존 BPE 가 사전 토큰을 빈도수로 집계하여 메모리 효율을 높인 것처럼, 저자들은 슈퍼머지 후보 (2 개 이상의 연속된 사전 토큰) 역시 빈도수로 집계할 수 있음을 증명했습니다.
  • 이를 통해 전체 문서를 메모리에 로드할 필요 없이, 집계된 후보들만 사용하여 훈련할 수 있게 되었습니다.
  • 스크립트별 사전 토큰화: 중국어, 일본어 등 공백이 없는 언어의 경우, 각 문자를 3 바이트 단위의 개별 사전 토큰으로 분리하여 처리합니다. 이는 부분 바이트 (partial byte) 가 섞여 의미 없는 토큰이 생성되는 것을 방지하고, 슈퍼머지 후보 생성을 가능하게 합니다.

• 2 단계 BoundlessBPE 알고리즘:

  • 1 단계 (일반 BPE 학습): 집계된 사전 토큰을 사용하여 목표 어휘 크기까지 일반 BPE 병합 규칙을 학습합니다.
  • 2 단계 (슈퍼머지 학습): 1 단계에서 학습된 일반 병합 규칙과 집계된 슈퍼머지 후보들을 비교합니다. Algorithm 1 에 따라 각 단계에서 일반 병합과 슈퍼머지 중 카운트가 더 높은 것을 선택하여 최종 어휘를 구성합니다.
  • 이 2 단계 방식은 원래의 BoundlessBPE 와 동일한 결과를 내면서도, SuperBPE 와의 구조적 유사성을 통해 하이퍼파라미터 (슈퍼머지 수) 를 자동으로 결정할 수 있게 합니다.

3. 주요 기여 (Key Contributions)

1. 훈련 속도 개선: 슈퍼머지 후보 집계와 2 단계 구조를 도입하여, 1GB 데이터셋 기준 훈련 시간을 4.7 일 (약 400,000 초) 에서 603 초 (BoundlessBPE) 및 593 초 (SuperBPE) 로 단축했습니다. 이는 600 배 이상의 속도 향상입니다.
2. 오픈소스 구현체 공개: Python(참조용) 과 Rust(고속용) 로 구현된 BoundlessBPE 와 SuperBPE 코드를 오픈소스로 공개합니다. Rust 구현체는 Python 대비 빠른 속도를 제공하며, 두 구현체는 동일한 결과를 생성합니다.
3. 추론 (Inference) 최적화: 사전 토큰이 어휘에 이미 포함되어 있다면 병합을 생략하는 '단축 (shortcut)' 기법을 도입하여 추론 속도를 Python 기준 2.8 배, Rust 기준 1.6 배 향상시켰습니다.
4. 비효율적 토큰 생성 방지: 비공백 언어 (한자, 가나 등) 에 대한 스크립트별 토큰화 전략을 제안하여, UTF-8 유효성을 해치는 부분 바이트 토큰 생성을 방지했습니다.

4. 실험 결과 (Results)

• 훈련 시간: 100 만 개의 MiniPile 문서 (약 1GB) 를 대상으로 한 실험에서, Rust 기반의 새로운 구현체는 기존 Python 기반 BoundlessBPE 에 비해 압도적인 성능 차이를 보였습니다.
  • 기존 BoundlessBPE (Python): ~11,683 초 (약 3.2 시간)
  • 개선된 BoundlessBPE (Rust): ~3,440 초 (약 57 분)
  • 개선된 SuperBPE (Rust): ~3,372 초
  • 참고: 논문 초록에서는 1GB 데이터 기준 603 초/593 초라고 언급했으나, Figure 5 의 1M 문서 (약 1GB) 기준 Rust 실행 시간은 약 3,400 초 수준으로 나타났습니다. 이는 구현 최적화 수준이나 측정 기준에 따른 차이로 보이며, 핵심은 '수십 배에서 수백 배의 속도 향상'입니다.
• 모델 성능: 제안된 2 단계 BoundlessBPE 는 원본 알고리즘과 동일한 어휘와 병합 규칙을 생성하므로, 기존 연구 (Liu et al., 2025 등) 에서 보고된 SuperBPE 의下游 (downstream) 작업 성능 향상 (정확도 4.0% 개선 등) 이 그대로 유지됩니다.

5. 의의 (Significance)

이 연구는 Superword 기반 토크나이징의 실용적 장벽이었던 '훈련 시간' 문제를 해결했습니다. 이전에는 대규모 데이터셋으로 Superword 모델을 학습하는 것이 비현실적이었으나, 이제는 합리적인 시간 내에 학습이 가능해졌습니다. 이는 BPE 의 한계를 넘어 더 효율적이고 압축률이 높은 토크나이저를 대규모 LLM 에 적용할 수 있는 길을 열었으며, 오픈소스로 제공되는 고속 구현체를 통해 연구자와 실무자들이 즉시 활용할 수 있게 되었습니다. 또한, 단일 스레드 기반의 현재 구현에서 병렬화 (parallelization) 를 추가하면 추가적인 속도 향상이 기대된다고 결론지었습니다.