분할 트리(Split Trees)를 이용한 토큰화

우리는 새로운 재귀적 추론 절차(recursive inference procedure) 하에서 압축을 직접 최적화하는 서브워드 토큰화(subword tokenization) 방법인 Tokenization with Split Trees (ToaST)를 소개합니다. ToaST는 어떠한 어휘 사전(vocabulary)과도 독립적으로, 미리 계산된 바이트 n-gram 빈도수를 사용하여 각 프리토큰(pretoken)을 완전 이진 트리(full binary tree)로 탐욕적(greedily)으로 분할합니다. 어휘 사전이 주어지면, 추론 과정은 각 분할 트리를 재귀적으로 내려가며 각 경로에서 도달하는 첫 번째 어휘 사전 내 노드(in-vocabulary node)를 방출합니다. 어휘 사전 선택은 이 추론 절차 하에서 모든 분할 트리에 대한 총 토큰 수를 최소화하는 정수 계획법(Integer Program, IP)으로 공식화됩니다. 선형 계획법(Linear Programming, LP) 완화(relaxation)는 실제 적용 시 정수 값에 가깝게 나타나며, 증명 가능한 근사 최적(near-optimal) 어휘 사전을 생성합니다. 훈련 시간은 경험적으로 분할 트리의 수에 따라 이차 함수적으로(quadratically) 증가합니다. 영어 텍스트에 대해 ToaST는 어휘 사전 크기가 40,960 이상일 때 BPE, WordPiece, UnigramLM과 비교하여 토큰 수를 11% 이상 줄였으며, 이 토크나이저를 사용하는 모델의 추론 토큰 수를 줄임으로써 유효 컨텍스트 길이(effective context length)를 확장합니다. 또한 ToaST는 이러한 베이스라인들보다 일반적인 단일 바이트 토큰을 더 적게 사용하여 Renyi 효율성(Renyi efficiency)을 크게 개선했습니다. 1.5B 파라미터 언어 모델을 훈련하는 실험에서 ToaST는 가장 높은 CORE 점수를 달성하였으며, 세 가지 중 두 가지에서 유의미한 차이를 보이며 베이스라인보다 2.6%~7.6% 높은 성능을 기록했고, 22개의 개별 작업 중 13개에서 가장 좋은 점수를 기록했습니다.