기술 요약: 점진적 BPE 토큰화 (Incremental BPE Tokenization)

문제 정의

현대적인 대규모 언어 모델(LLM) 파이프라인은 바이트 페어 인코딩(Byte Pair Encoding, BPE)에 크게 의존합니다. 그러나 현재의 최첨단 구현체들(예: Hugging Face의 tokenizers, OpenAI의 tiktoken)은 주로 오프라인 프로세스로 설계되어 있습니다. 이들은 정형화된 토큰화를 생성하기 전에 전체 입력 시퀀스 또는 사전 분할된 청크를 완전히 관찰해야 합니다. 이러한 구조적 한계는 토큰화와 모델 프리필링(pre-filling)을 병렬이 아닌 순차적으로 실행하게 만들어, 스트리밍 및 롱 컨텍스트 추론 시나리오에서 지연 시간(latency)을 유발합니다.

또한, 기존 구현체들은 전체 입력을 대상으로 병합(merge)을 선택하기 위해 힙 기반의 우선순위 큐에 의존하는 경우가 많아, 본질적으로 전역적(global)이며 바이트 단위 업데이트에 적응하기 어렵습니다. 일부 도구들은 병합 비용을 제한하기 위해 정규식 기반의 사전 분할을 사용하기도 하지만, 이 방식은 취약할 수 있으며, 극단적인 문자 반복과 같은 병리적 입력(pathological inputs)에 대해 성능 저하나 스택 고갈을 초-래할 수 있습니다. 예를 들어, 일부 도구는 $O(n^2)$의 동작을 보입니다.

방법론

저자들은 입력 텍스트의 모든 접두사(prefix)에 대한 BPE 토큰화 결과를 실시간으로 유지하는 점진적 BPE 토큰화를 위한 새로운 알고리즘을 제안합니다. 이 접근 방식은 BPE의 구조적 특성에 근거하며 다음과 같은 몇 가지 핵심적인 알고리즘 혁신을 도입합니다.

1. 구조적 기초

• 접두사 일관성 (Prefix Consistency): 유효한 BPE 토큰화는 자유롭게 절단될 수 있다는 성질을 활용하여, 이 알고리즘은 성장하는 문자열의 토큰화를 더 짧은 접두사의 이전 유효한 토큰화를 확장하는 방식으로 모델링하며, 재계산을 수행하지 않습니다.
• 마지막 토큰 ($\theta(s)$): 알고리즘은 현재 문자열 $s$의 "마지막 토큰"을 유지하는 데 집중합니다. 전체 토큰화는 마지막 토큰들의 시퀀스로 암시적으로 인코딩되며, 이는 백트래킹을 통해 검색 가능합니다.
• Successor Forest & Suffix-Successor Tree: 어휘집(vocabulary)은 정규화된 토큰들로 구성되어 Successor Forest라는 위상적 구조를 형성합니다. 임의의 입력에 대해, 새로운 마지막 토큰을 위한 탐색 공간은 모든 잠재적 접미사 토큰을 조직화하는 Suffix-Successor Tree 내로 제한됩니다.

2. 단조 경로 성질 (The Monotonic Path Property)

핵심적인 이론적 기여는 단조 경로 성질로, 임의의 입력 문자열에 대해 마지막 토큰 역할을 할 수 있는 접미사 토큰의 집합이 Suffix-Successor Tree 내에서 단일하고 연속적인 경로를 형성함을 확립합니다. 이 경로는 루트(원자적 토큰)에서 시작하여 진정한 마지막 토큰 $\theta(s)$까지 확장됩니다. 이 성질은 탐색 공간을 전체 트리에서 단일 경로로 축소하여 효율적인 검증을 가능하게 합니다.

3. 알고리즘 구현

점진적 업데이트 프로세스는 두 단계로 구성됩니다.

1. 탐색 공간 식별: 지속 가능한 제곱근 타일링(persistent square-root tiling)으로 증강된 Aho–Corasick 오토마타를 사용하여, $O(1)$ 시간 내에 가장 긴 접미사 토큰 $\tau(sc)$를 식별하고, 이를 통해 경계가 되는 Suffix-Successor Tree를 정의합니다.
2. 경로 확장 탐색: 가장 깊은 유효 노드를 찾기 위해 알고리즘은 **센트로이드 분해(Centroid Decomposition)**를 채택합니다. 알고리즘은 높이가 $O(\log |\tau|)$인 사전 계산된 Centroid Search Tree (CST)를 순회합니다. 각 단계에서 알고-리즘은 DFS 선형화 구간을 사용하여 접두사 마지막 토큰 조건(도달 가능성 및 우선순위 지배력 확인)을 검증합니다. 이를 통해 $O(\log |\tau|)$ 시간 내에 유효한 경로의 방향을 결정할 수 있습니다.

4. 이기적 출력 메커니즘 (Eager Output Mechanism)

진정한 스트리밍을 지원하기 위해, 저자들은 이기적 출력(eager output) 알고리즘을 도입합니다. 이 알고리즘은 토큰화 트리의 "활성 프런티어(Active Frontier)"—즉, 미래의 토큰의 부모가 될 가능성이 있는 접두사들의 범위—를 식별합니다. 이러한 후보들의 동적 서브그래프를 유지함으로써, 시스템은 경계가 불변(invariant)하게 되는 즉시(즉, 모든 활성 경로가 가상 루트의 단일 자식으로 수렴할 때), 토큰을 방출하여 모델 추론과의 완전한 파이프라이닝을 가능하게 합니다.

주요 기여

• 알고리즘 복잡도: 제안된 알고리즘은 각 입력 바이트를 최대 토큰 길이 $t$에 대한 $O(\log_2 t)$의 엄격한 최악의 경우 시간 복잡도로 처리합니다. 이는 길이 $n$인 입력에 대해 전체적으로 $O(n \log_2 t)$의 복잡도를 가집니다.
• 스트리밍 능력: 이 방법은 표준 BPE 단계의 교체 가능한 드롭인(drop-in) 대체제로 기능하며, 주변 전처리 단계의 정확성을 변경하지 않고도 스트리밍 설정에서 효율적인 부분 토큰화를 가능하게 합니다.
• 이기적 출력: 이기적 출력 메커니즘의 도입은 토큰화 경계가 해결되는 즉시 토큰을 방출하여 실시간 스트리밍과 모델 추론 간의 파이프라이닝을 가능하게 합니다.
• 견고성: 병리적 입력에 대해 $O(n^2)$으로 저하될 수 있는 기존 도구들과 달리, 이 접근 방식은 안정적인 성능 보장을 유지합니다.
• 전체 접두사 지원: "Fill-in-the-middle" 작업이나 "토큰 힐링(token healing)"과 같이 모든 접두사의 토큰화에 접근해야 하는 시나리오를 자연스럽게 지원합니다.

결과

저자들은 알고리즘을 Rust로 구현하였으며, 이를 Hugging Face의 tokenizers 및 OpenAI의 tiktoken과 벤치마킹하였습니다.

• 처리량 (Throughput): 이 점진적 접근 방식은 특히 정규식 기반의 사전 토큰화가 없는 시나리오(예: CodeLlama)에서 Hugging Face의 토크나이저 대비 최대 $\sim 3\times$의 엔드 투 엔드 속도 향상을 달성했습니다.
• 병리적 입력에 대한 지연 시간: 광범위한 반복이 포함된 입력에서 tiktoken은 $O(n^2)$ 복잡도와 일치하는 처리량 저하를 보였습니다. 반면, 제안된 방법은 안정적인 처리량을 유지하여 이러한 병리적 사례에서 상당한 지연 시간 감소를 입증했습니다.
• 이기적 출력 오버헤드: 이기적 출력 메커니즘은 비이기적 점진적 버전과 비교하여 엔드 투 엔드 처리량에서 약 **10%**의 오버헤드를 발생시키며, 저자들은 이 비용이 I/O 또는 추론과 파이프라이닝되는 시스템에서 상쇄될 수 있다고 언급했습니다.

의의 및 주장

본 논문은 BPE 토큰화가 표준 BPE와 정확한 의미적 호환성을 유지하면서도 엄격한 최악의 경우 보장과 함께 점진적으로 수행될 수 있음을 보여줍니다.

저자들은 자신들의 연구가 이론적 형식주의(접두사 안정성을 시사하는)와 실제 엔지니어링(전역적, 오프라인 처리에 의존해 온) 사이의 간극을 메운다고 주장합니다. $O(n \log_2 t)$ 복잡도를 제공함으로써, 이 연구는 다음을 가능하게 합니다:

1. 지연 시간 감소: 토큰화를 모델 추론과 완전히 파이프라이닝할 수 있게 하여, 스트리밍 추론에서의 순차적 병목 현상을 제거합니다.
2. 시스템 견고성: 현재의 토크나이저가 가진 $O(n^2)$ 취약점을 악용하는 설계된 입력(예: DoS 공격)에 의한 알고리즘 복잡도 공격의 위험을 완화합니다.
3. 파이프라인 최적화: 글로벌 BPE 비용을 제한하기 위해 설계된 특정 사전 분할 단계를 알고리즘적으로 불필요하게 만들어, 더 깔끔하고 효율적인 파이프라인 설계를 가능하게 합니다.

저자들은 결론적으로, 엄격한 알고리즘적 보장을 실질적인 지연 시간 이점으로 변환함으로써 더욱 견고하고 응답성이 뛰어나며 에너지 효율적인 LLM 파이프라인을 위한 길을 열었다고 밝히고 있습니다.