[논문 리뷰] Tokenisation via Convex Relaxations: 전역 최적화로 토크나이저의 한계를 넘다

TL;DR

토크나이제이션은 자연어 처리(NLP)에서 텍스트를 모델이 이해할 수 있는 단위로 분할하는 필수 단계입니다. BPE와 같은 기존 알고리즘은 탐욕적(greedy) 방식으로 작동하여 지역 최적해에 머무르므로, 전역적으로 최적의 어휘를 구성한다고 보장할 수 없습니다. 이 논문은 토크나이저 구축을 볼록 최적화(Convex Optimization) 문제로 재정의하여, 전역 최적에 가까운 어휘를 찾는 ConvexTok 알고리즘을 제안합니다. 실험 결과, ConvexTok은 BPE보다 높은 압축률(더 적은 토큰 수)과 비슷하거나 더 나은 다운스트림 태스크 성능을 보였습니다. 또한, 기존 토크나이저가 이론적 최적해에서 얼마나 벗어났는지 정량적으로 측정할 수 있는 '최적성 격차(optimality gap)'라는 이론적 도구를 제공합니다.

연구 배경 및 동기

NLP 모델의 성능은 토크나이저에 크게 의존합니다. 좋은 토크나이저는 텍스트를 의미 있는 단위로 효율적으로 분할하여 모델의 학습과 추론을 돕습니다. BPE(Byte Pair Encoding)나 Unigram과 같은 서브워드(subword) 토크나이저는 미등록 단어(Out-of-Vocabulary, OOV) 문제를 해결하며 널리 사용되고 있습니다.

하지만 이들의 작동 방식에는 근본적인 한계가 있습니다. BPE를 예로 들면, 매 단계에서 가장 빈번하게 등장하는 토큰 쌍을 병합하는 탐욕적(greedy) 접근법을 사용합니다.

# BPE의 탐욕적 접근 방식 (개념적 예시)
# "unhappiness"라는 단어가 많다고 가정
# 1단계: 'h'+'a' -> 'ha' 병합
# 2단계: 'p'+'p' -> 'pp' 병합
# ...
# 최종: "un", "happi", "ness" 와 같은 토큰이 생성될 수 있음

# 하지만 "unhappy"와 "happiness"가 더 유용한 토큰일 수 있지만,
# 지역적 최적 선택(가장 빈번한 쌍)에 갇혀 이를 찾지 못할 수 있음

이러한 지역적 최적화는 전체 말뭉치 관점에서 전역 최적 어휘 집합을 구성하는 것을 보장하지 못합니다. 즉, '더 나은' 토큰 조합이 존재할 수 있음에도 불구하고 이를 놓칠 수 있습니다. ConvexTok은 이 문제를 해결하기 위해 토크나이저 구축 과정을 하나의 거대한 최적화 문제로 정의하고, **정수 선형 계획법(Integer Linear Programming, IP)**을 통해 전역 최적해를 찾고자 합니다.

연구	방법론	특징 및 한계
BPE	탐욕적 병합 알고리즘	빠르고 구현이 간단하지만, 전역 최적을 보장하지 않음
Unigram	확률 기반 탐욕적 제거	여러 토큰화 후보를 생성하지만, 여전히 탐욕적 접근에 기반함
ConvexTok	볼록 최적화 (LP Relaxation)	전역 최적에 근접한 해를 찾고, 이론적 최적성 평가가 가능함

핵심 기여

볼록 최적화 기반 토크나이저: 토크나이저 구축을 정수 선형 계획법으로 공식화하고, 이를 선형 계획법으로 완화(relaxation)하여 전역 최적에 가까운 어휘 사전을 구축하는 새로운 프레임워크를 제안합니다.
이론적 최적성 평가: 특정 토크나이저가 이론적인 최적해로부터 얼마나 떨어져 있는지(optimality gap)를 정량적으로 평가할 수 있는 도구를 제공합니다. 이를 통해 BPE가 최적해에서 약 1.5% 벗어나 있음을 실험적으로 보였습니다.
압축률 및 성능 개선: BPE 대비 더 나은 압축률(더 적은 토큰 수)을 달성했으며, 다양한 다운스트림 태스크에서 비슷하거나 더 나은 성능을 기록했습니다.

제안 방법론

ConvexTok의 목표는 **"주어진 말뭉치를 토큰화했을 때 총 토큰의 개수가 최소가 되도록, 크기가 $V$ 인 어휘 사전을 선택하는 것"**입니다. 이를 수학적으로 모델링하면 다음과 같습니다.

1. 정수 선형 계획법 (IP) 공식화

이 문제는 모든 가능한 토큰 후보와 모든 가능한 분할 방법을 고려해야 하는 매우 복잡한 조합 최적화 문제입니다. 이를 다음과 같은 정수 선형 계획법(IP) 문제로 공식화할 수 있습니다.

결정 변수:
- $v_t$ : 후보 토큰 $t$ 가 최종 어휘에 포함되면 1, 아니면 0.
- $u_s$ : 말뭉치의 문자열(또는 단어) $s$ 를 토큰화하는 데 사용되는 토큰의 수.
목적 함수:
$\min_{\mathbf{v}, \mathbf{u}} \sum_{s \in \mathcal{S}} \text{freq}(s) \cdot u_s$
이는 말뭉치 전체의 총 토큰 수를 최소화하는 것을 의미합니다. $\text{freq}(s)$ 는 문자열 $s$ 의 빈도입니다.
주요 제약 조건:
1. 어휘 크기 제약: 최종 어휘의 크기는 $V$ 를 넘을 수 없다. $\sum_{t \in \mathcal{V}_{\text{candidate}}} v_t \le V$
2. 유효 토큰화 제약: 모든 문자열 $s$ 는 선택된 어휘( $v_t=1$ 인 토큰들)만으로 분할될 수 있어야 한다. 이 제약은 $u_s$ 와 $v_t$ 를 연결합니다.
3. 이진 변수 제약: $v_t, u_s$ 는 정수(여기서는 0 또는 1)여야 한다.

2. 선형 계획법 완화 (LP Relaxation)

위 IP 문제는 경우의 수가 너무 많아 NP-hard, 즉 현실적인 시간 안에 풀기 매우 어렵습니다. 따라서 논문에서는 핵심적인 아이디어인 **완화(relaxation)**를 적용합니다.

변수가 0 또는 1의 값만 가질 수 있다는 이진 제약을 0과 1 사이의 실수를 가질 수 있도록 완화합니다. $v_t \in \{0, 1\} \quad \rightarrow \quad v_t \in [0, 1]$ 이렇게 변환된 문제를 선형 계획법(Linear Programming, LP) 문제라고 하며, 이는 다항 시간 내에 전역 최적해를 구할 수 있습니다.

3. 라운딩 (Rounding)

LP 문제의 해는 $v_t=0.7$ 과 같이 '부분적인' 값을 가집니다. 이를 실제 어휘 사전(0 또는 1)으로 변환하기 위해 라운딩 과정이 필요합니다. 논문에서는 세 가지 기법을 제안합니다.

Deterministic: LP 해( $v_t$ 값)가 높은 상위 $V$ 개의 토큰을 선택합니다.
Biased Sampling: 각 토큰을 $v_t$ 값에 비례하는 확률로 샘플링합니다.
Integer: LP 해를 기반으로 더 정교한 방법(projected gradient ascent)을 사용해 정수 해를 찾습니다.

실험 설정

데이터셋: 4000억 토큰 규모의 ClimbMix400B 영어 텍스트 데이터셋을 사용했습니다.
평가 지표:
- BpB (Bits per Byte): 텍스트 압축률을 나타내는 지표. 낮을수록 동일한 텍스트를 더 적은 정보로 표현, 즉 더 효율적인 토크나이저임을 의미합니다.
- CORE Score: 7개의 다운스트림 태스크(요약, 질의응답 등) 성능을 종합한 점수.
비교 대상: 널리 사용되는 BPE 알고리즘과 비교했습니다.

파라미터	값
어휘 크기	32,768, 65,536, 131,072
평가 지표	BpB, CORE Score

실험 결과 분석

ConvexTok은 모든 어휘 크기에서 BPE보다 뛰어난 압축률(더 낮은 BpB)을 달성했습니다. 특히 어휘 크기가 커질수록 BPE와의 격차가 더욱 벌어져, 대규모 어휘에서 ConvexTok의 장점이 두드러졌습니다.

어휘 크기	BPE (BpB)	ConvexTok-Int (BpB)	개선율
32,768	2.891	2.872	0.66%
65,536	2.783	2.755	1.01%
131,072	2.696	2.656	1.48%

다운스트림 성능을 측정한 CORE 점수에서도 ConvexTok은 BPE와 비슷하거나 약간 더 나은 성능을 보였습니다. 이는 ConvexTok이 단순히 압축만 잘하는 것이 아니라, 생성된 토큰이 모델의 언어 이해 능력에도 긍정적인 영향을 미칠 수 있음을 시사합니다.

비판적 평가

계산 비용: ConvexTok의 가장 큰 한계는 LP 문제를 풀어야 하므로 BPE에 비해 계산 비용과 시간이 훨씬 많이 든다는 점입니다. 대규모 말뭉치와 후보 어휘에 적용하기 위해서는 상당한 계산 자원이 필요합니다.
일관되지 않은 성능 향상: 모든 다운스트림 작업에서 BPE를 압도하는 성능을 보이지는 않았습니다. 이는 토크나이저의 개선이 특정 태스크에만 유효할 수 있음을 의미합니다.
구현의 복잡성: BPE에 비해 알고리즘이 복잡하여 일반 사용자가 직접 구현하고 적용하기에는 진입 장벽이 있습니다.

실무 적용 가이드

ConvexTok은 계산 비용을 감수하고서라도 최고의 성능을 추구해야 하는 상황에 적합합니다.

언제 BPE/Unigram을 사용해야 하는가?
- 빠른 프로토타이핑이 필요할 때
- 계산 자원이 제한적인 환경
- 대부분의 일반적인 NLP 프로젝트
언제 ConvexTok을 고려해야 하는가?
- 대규모 언어 모델(LLM)을 처음부터 사전 학습(pre-training)할 때
- 토크나이저의 미세한 차이가 최종 모델 성능에 큰 영향을 미치는 경우
- 계산 자원이 풍부하고, 최고의 성능을 내는 것이 최우선 목표일 때

# 개념적 비교
def build_bpe_tokenizer(corpus, vocab_size):
    # 1. 초기 어휘로 문자 집합 설정
    # 2. 정해진 횟수만큼 반복:
    #    - 말뭉치에서 가장 빈번한 토큰 쌍을 찾음
    #    - 해당 쌍을 새로운 토큰으로 병합하여 어휘에 추가
    return vocab

def build_convextok_tokenizer(corpus, vocab_size):
    # 1. 말뭉치에서 후보 토큰 집합 생성
    # 2. 토크나이저 문제를 LP 문제로 공식화
    #    - 목적: 총 토큰 수 최소화
    #    - 제약: 어휘 크기 V 이하
    # 3. LP 솔버를 사용하여 최적해(실수 값) 계산
    # 4. 라운딩을 통해 최종 어휘(이진 값) 결정
    return final_vocab

결론

ConvexTok은 기존의 탐욕적 방식에서 벗어나, 토크나이저 구축에 전역 최적화라는 새로운 관점을 제시한 혁신적인 연구입니다. 수학적으로 견고한 프레임워크를 통해 더 효율적인 토크나이저를 만들 수 있음을 보였고, 기존 방식의 한계를 정량적으로 측정할 수 있는 길을 열었습니다. 높은 계산 비용이라는 실용적인 장벽이 있지만, 향후 LLM의 성능을 극한까지 끌어올리기 위한 중요한 연구 방향이 될 것입니다.

참고 자료

논문 링크: Tokenisation via Convex Relaxations (arXiv:2405.12132)
코드 저장소: google-deepmind/convextok (GitHub)
관련 자료: Hugging Face Tokenizers Documentation

[논문 리뷰] Tokenisation via Convex Relaxations