최적의 Tokenizer를 찾는 방법

이론적으로 최적의 Tokenization을 찾는 것은 매우 어려운 문제(intractable)이지만, 실제로는 해결 가능한 영역에 있습니다. 이는 마치 **Traveling Salesman Problem(TSP)**을 Cutting-plane 기법으로 해결하는 것과 유사합니다.

기존의 **BPE(Byte-Pair Encoding)**는 수십 년 된 탐욕적(greedy) 압축 알고리즘입니다. 하지만 최근 연구는 Tokenization을 정수 선형 계획법(Integer Linear Programming, ILP) 문제로 연결하여 접근합니다.

이 모델의 핵심 구조는 다음과 같습니다:

• Color variable: 데이터셋의 모든 고유한 서브스트링에 대해 할당되며, 해당 시퀀스가 Vocabulary에 포함되면 1, 아니면 0의 값을 가집니다.
• Edge variable: 데이터셋 내 각 토큰 발생 지점에 할당되며, 해당 위치에서 특정 토큰이 사용되면 1의 값을 가집니다.
• Constraints: Vocabulary 크기를 고정하고, 데이터셋이 단 하나의 유효한 방식으로 토큰화되도록 Flow constraints를 적용합니다.

다만, 이러한 최적화 결과가 반드시 실무적으로 유용하지 않을 수 있는 이유도 존재합니다. 기존 SOTA 방식이 이미 최적값에 매우 근접해 있으며, 훈련 데이터에 최적화된 Tokenizer가 테스트 데이터에서는 일반화 성능이 떨어질 수 있기 때문입니다.