토큰화에 대한 분할 커버 접근법

토큰화(Tokenization)

토큰화는 문자열을 고정된 크기의 K 어휘에서 가져온 토큰으로 인코딩하는 과정이다. 현재 가장 널리 사용되는 토큰화 알고리즘은 Byte-Pair Encoding(BPE)이다. BPE는 토큰화를 압축과 병합 연산을 반복하여 수행한다.

토큰화는 LLM 아키텍처의 핵심적인 구성 요소로서 토큰화의 중요성이 강조되고 있다.LLM 모델들은 고정 길이 컨텍스트 윈도우를 사용하기 때문에 더 나은 압축 성능을 제공하는 토크나이저를 사용할 경우, 동일한 컨텍스트 윈도우에서 더 많은 정보를 담을 수 있다. 따라서 LLM이 더 많은 토큰을 효율적으로 처리하도록 개선할 수 있다.

압축 문제

본 논문에서는 입력 데이터를 토큰화할 때, 생성되는 토큰 개수를 최소화하는 방식으로 접근해야 한다. 즉 "압축 문제"는 토큰화를 데이터 압축과 유사한 방식으로 접근하겠다는 의미이다.

왜 토큰화 과정에서 압축이 되어야 하는가?
압축의 목표는 입력 데이터를 더 작은 크기로 변환하면서도 원래 의미를 유지하는 것이다. 텍스트 데이터를 가능한 작은 수의 토큰으로 변환하면서 의미를 최대한 유지하는 것이 토큰화의 목표이라면 앞서 언급한 컨텍스트 윈도우의 효율성을 고려할 때, 토큰화는 토큰 수를 최소화해야 할 필요성이 있다.

컨트리뷰션

1. 토큰화는 반드시 병합 패턴(Merge)를 할 필요가 없으며, 단순히 효율적으로 코퍼스를 표현할 수 있는 최적의 토큰 집합을 선택하는 과정이다. 본 연구에서는 특정한 병합 순서를 강제하지 않고 해결책을 제시하고자 한다.

2. Pair 병합없이 동작하는 알고리즘 GreedTok 제안
   GreedTok은 단순히 선택된 토큰들의 순서만을 필요로 하기 때문에 병합과정을 필요로 하지 않는다.

실험 결과
4개의 실험 데이터셋에서 BPE대비 평균 3%, 최대 5% 더 적은 토큰 수를 사용하여 압축 효율이 높았다. 동일한 압축 비율을 달성하기 위해 GreedTok은 평균적으로 BPE보다 13% 적은 토큰 수만 필요하다.

GreedTok

Challenges in designing an efficient algorithm for Problem 1

토큰화 문제는 NP-hard 임을 증명하였다. NP-hard 문제에 대해 효율적인 알고리즘을 개발하는 과정에서는 정확성, 실행시간, 품질 사이에서 절충이 필요하다. NP-hard는 비결정적 다항 시간 내에서 풀 수 있는 것보다 더 어렵거나 같은 수준의 문제를 의미한다.
NP문제보다 같거나 더 어려운 난이도의 문제군을 가르키는 개념이다.
본 연구에서는 대규모 데이터셋에서 현실적으로 실행 가능한 토큰화 솔루션을 개발하는 것을 목표로 하고 있으므로, 고정 매개변수 해석 알고리즘을 설계하는 방법은 포기하고, 다항 시간 내에서 실행되는 근사 해법을 개발하는 방향으로 접근한다.

해당 논문의 해설을 참조하면 토큰화 문제는 기존의 최적화 방법으로 해결하기 어렵다. 따라서 새로운 방법(GreedTok)을 제안하고 실험적으로 검증한다.

GreedTok 설계

혼합 정수 프로그램(Mixed Integer Program,MIP)으로 문제1(토큰화 문제)를 해결할 수 있음을 보인다.

Cover(W,S)
단어 W에서 인접한 단일 문자를 결합하여 집합 S 내의 토큰을 형성할 수 있는 최대 개수를 의미한다.

cover(W="scaredy",S={"care","edy"})=4
4개의 문자(c,a,r,e)를 결합하여 S 내의 유효한 토큰 형성한다. 그러나 e를 2번 사용할 수 없으므로 4+3=7은 아니다.

partition(W,S∪B)
단어 W를 S 및 B 내 토큰으로 나누었을 때 필요한 최소 분할 수를 의미한다.
단어 W = "scaredy"
토큰 집합 S∪B = {"care","edy",s,c,a,r,e,d,y}
가능한 분할 : s_care_d_y
즉 이러한 경우는 partition(W="scaredy",S∪B)=4가 된다.

최소화 목표(Minimization Objective)

위의 정의를 통해
∣W∣+1=partition(W,S∪B)+cover(W,S)
위와 같은 수식을 얻을 수 있다. 이를 바탕으로 MIP 기반 최소화 목표를 구성할 수 있으며 알고리즘을 설계할 수 있다.

다항 시간 탐욕적 알고리즘(GreedTok)

해당 알고리즘은 두 단계로 구성된다.

1. 토큰 집합 S를 후보 집합 T에서 선택하는 과정
2. 선택한 토큰 집합 S를 사용하여 단어 W를 토큰화하는 과정

후보 토큰 집합 T 생성 및 선택 과정

corpus 내 단어 W들에서 길이가 2 이상인 부분 문자열 고려하여 후보 토큰 집합 T 생성 후 f(S)를 정의한다.
*f(s) = MIP에서 최적화 목표 값
T ∈ T\S를 반복 탐색하여 가장 적합한 토큰 τ를 선택하여 S에 추가
이 과정을 사전 크기 K에 도달할 때 까지 반복한다.
이러한 과정에서 S 내의 토큰 순서가 형성된다.

단어 W를 토큰화 하는 과정

단어 W 내의 단일 문자를 한 번씩 순회하면서, 연속된 문자 패턴을 확인하고 우선순위에 따라 가능한 토큰들을 정렬한다.

시간복잡도 분석

1. 후보 집합 T에서 최적 토큰 집합 S를 선택하는 과정
   BPE의 시간복잡도보다 큼-> 가능한 모든 문자열 T를 탐색하는 추가적인 과정이 포함되기 때문이다.

2. 단어 W를 토큰화하는 과정
   BPE의 복잡도 O(n^2)보다 약간 더 큼
   GreedTok -> O(n^2 * logM)
   정렬 연산을 추가적으로 수행하기 때문이다.

벤치마크

이론적 시간복잡도는 BPE보다 높지만 현실적인 NLP 응용에서 충분히 효율적일 것이다.
이를 위해서 저자는 GreedTok의 인코딩 성능을 평가하기 위해 100K 개의 토큰으로 이루어진 사전을 사용했다. 위키피디아에서 70k 개의 텍스트 문서(약 9700만 단어)로 이루어진 데이터셋을 인코딩한다. 유사한 연산환경에서 GreedTok은 스레드당 초당 70만 ~ 80만 단어를 처리할 수 있음을 보였다.

결론

본 연구에서는 토큰화 문제가 NP-hard 임을 증명하고 GreedTok을 제안하여 실험적으로 검증한 결과, 기존 BPE보다 우수한 압축 효율을 제공함을 입증했다.

Open problem

• BPE는 상용적인 토큰화 알고리즘이지만, 실용적이고 효율적이지 않다.
• 토크나이저없이 동작하는 아키텍처 등장
  이러한 모델들은 바이트 단위 정보를 활용하여 토큰화 수행. GreedTok을 활용하여 비트 단위 병합 여부를 예측 작업에 적용할 수 있을 것이다.
• GreedTok이 큰 어휘 크기 K에 대해 0.9 근사 비율을 달성하는 사실은 확인했으나, 이에 대한 수학적 증명이 부족