기술 요약: 볼록 완화 (Convex Relaxations) 를 통한 토큰화

문제 정의

토큰화는 자연어 처리 (NLP) 파이프라인의 핵심 구성 요소로, 언어 모델 (LM) 을 위해 바이트 문자열을 토큰 시퀀스로 변환합니다. 최근 연구는 토큰화 압축 효율성과 하류 언어 모델 성능 간의 상관관계를 시사하지만, 최적의 토크나이저를 찾는 것은 NP-하드 문제입니다. 현재 최첨단 방법인 바이트 페어 인코딩 (BPE) 과 유니그램 (Unigram) 은 탐욕 알고리즘에 의존합니다. 이러한 방법들은 결과 어휘의 전역 최적성을 고려하지 않고 국소적으로 최적의 결정 (예: 가장 빈도가 높은 토큰 쌍을 반복적으로 병합) 을 내립니다. 그 결과, 불필요한 중간 토큰을 생성하고 최대 압축을 달성하지 못할 수 있습니다. 본 논문이 다루는 핵심 과제는 탐욕적 휴리스틱의 한계를 넘어 전역적으로 최적의 토크나이저를 어떻게 효율적으로 근사할 수 있는지에 관한 것입니다.

방법론

저자들은 정수 계획법 (IP) 의 볼록 완화에서 유도된 선형 계획법 (LP) 으로 토크나이저 구축을 공식화한 새로운 토큰화 알고리즘인 ConvexTok을 제안합니다.

1. 그래프 공식화

문제는 먼저 데이터셋의 바이트 문자열 내 바이트 간의 위치를 나타내는 유방향 비순환 그래프 (DAG) 상의 최단 경로 문제로 재해석됩니다:

• 정점: 데이터셋의 바이트 문자열 내 바이트 간의 위치를 나타냅니다.
• 간선:
  • 바이트 간선: 인접한 바이트를 연결합니다 (개별 문자를 나타냄).
  • 토큰 간선: 인접하지 않은 정점을 연결하며, 잠재적인 멀티바이트 토큰을 나타냅니다.
• 색칠: 토큰 간선은 나타내는 특정 바이트 시퀀스에 따라 색칠됩니다. 하나의 "색"은 고유한 토큰에 해당합니다.
• 목적: 최대 $K$개의 서로 다른 색 (토큰) 을 사용하여 전체 경로 길이 (압축) 를 최소화하는 시작점에서 끝점까지의 경로를 찾습니다.

2. 정수 계획법 (IP)

그래프 문제는 정수 계획법으로 변환됩니다. 저자들은 자유 간선 (바이트 간선) 과 가격 간선 (토큰 간선) 에 대한 연관 행렬과 색 분할 행렬을 정의합니다. 최적화 변수는 다음을 나타내는 이진 벡터입니다:

• 분할에 사용된 간선 ($f$는 자유, $p$는 가격).
• 어휘에 선택된 색 (토큰) ($c$).
  목적은 유효한 경로를 보장하는 흐름 제약 조건과 선택된 색의 수를 $K$로 제한하는 예산 제약 조건을 준수하면서 전체 경로 길이를 최소화하는 것입니다.

3. 볼록 완화 (LP)

IP 를 푸는 것은 NP-하드이므로, 저자들은 이산 제약 조건 ($x \in \{0, 1\}$) 을 연속 구간 ($x \in [0, 1]$) 으로 완화합니다. 이는 문제를 선형 계획법 (LP) 으로 변환하며, 표준 솔버 (특히 NVIDIA CuOPT 의 PDLP 방법) 를 사용하여 효율적으로 해결할 수 있습니다.

• 토큰화 다면체: 이 완화된 LP 의 해 공간은 잠재적 어휘의 볼록 결합을 나타내는 "부분" 토큰 (분수 값) 을 허용합니다.

4. 반올림 기법

LM 은 이산 어휘를 필요로 하므로, 분수 LP 해를 이산화해야 합니다. 논문은 세 가지 반올림 기법을 제안하고 평가합니다:

• 결정론적 (Det): LP 값이 가장 높은 $K$개의 색을 선택합니다.
• 편향 (Bias): LP 값과 토큰 길이의 비율 ($c / \text{length}(c)$) 로 색을 순위 매겨, 점수가 비슷할 때 짧은 토큰을 선호합니다.
• 정수 전용 (Int): LP 값이 이미 1 에 가까운 색만 선택합니다 (완화에 의해 본질적으로 "강제"됨). 이는 종종 예산 $K$보다 작은 어휘를 초래합니다.

주요 기여

1. 공식화: 논문은 다면체 기법을 통해 토크나이저 구축을 선형 계획법으로 공식화한 최초의 사례를 제공하며, 토큰화를 색칠된 그래프의 최단 경로 문제와 명시적으로 연결합니다.
2. 알고리즘 (ConvexTok): BPE 와 같은 탐욕적 접근법에서 내재된 국소 최적점을 피하고 전역적으로 최적의 토크나이저를 근사하는 새로운 알고리즘을 도입합니다.
3. 최적성 인증: LP 해는 주어진 데이터셋에서 어떤 토크나이저가 달성할 수 있는 압축에 대한 증명 가능한 하한을 제공합니다. 이를 통해 연구자들은 특정 토크나이저 (예: BPE 또는 ConvexTok) 가 이론적 최적점에 얼마나 가까운지 인증할 수 있습니다.
4. 반올림 분석: 논문은 분수 LP 해를 기능적인 토크나이저로 변환하기 위해 세 가지 서로 다른 반올림 전략을 체계적으로 평가합니다.

실험 결과

저자들은 ClimbMix400B 데이터셋과 GPT 스타일 디코더 전용 트랜스포머를 사용하여 다양한 어휘 크기 (8k 에서 256k) 에 대해 BPE 와 ConvexTok 을 평가했습니다.

• LP 해의 질: 어휘 크기가 증가함에 따라 LP 해는 점점 더 정수적 (0 또는 1 에 가까움) 이 되어, 더 큰 규모에서는 최적 토큰 선택이 덜 모호함을 시사합니다.
• 최적성 간격: LP 하한은 기존 토크나이저가 놀라울 정도로 최적에 가깝다는 것을 보여줍니다. 일반적인 어휘 크기 (128k, 256k) 에서 BPE 와 ConvexTok 변형 모두 최적 압축 한계 내에서 1% 이내에 있습니다.
• 내재적 지표:
  • Bias 반올림 기법은 어휘 활용도, 타입 - 토큰 비율, 압축률과 같은 내재적 지표에서 BPE 및 기타 기법보다 일관되게 우수한 성능을 발휘했습니다.
  • BPE는 데이터의 서로 다른 무작위 부분집합에서 재학습될 때 ConvexTok 변형보다 더 안정적인 것으로 나타났으며, 이는 아마도 빈도 기반의 국소적 특성 때문일 것입니다.
• 언어 모델링 성능:
  • 바이트당 비트 (BpB): 결정론적 (Det) 반올림 기법은 특히 큰 어휘 크기에서 BPE 를 종종 능가하며 일관되게 최고의 BpB 점수를 달성했습니다.
  • 하류 작업 (CORE): 하류 벤치마크 (추론, 다중 선택, 상식) 에 대한 결과는 혼재되었습니다. ConvexTok 변형이 BPE 와 경쟁력이 있었지만, 모든 작업과 모델 깊이에 걸쳐 일관되고 유의미한 우위를 보이지는 않았습니다.
• 안정성: BPE 는 ConvexTok 에 비해 학습 데이터 샘플링에 대해 더 높은 안정성을 보였으나, 정수 전용 반올림 기법은 다른 ConvexTok 변형보다 더 높은 안정성을 보여주었습니다.

중요성과 주장

논문은 전역적으로 최적화된 토큰화가 국소적 탐욕 병합 기반 방법의 유망한 대안이라고 주장합니다. 주요 중요성은 다음에 있습니다:

1. 전역적 토큰화 해결: 토큰화를 탐욕적 휴리스틱이 아닌 볼록 최적화를 통해 접근할 수 있음을 입증합니다.
2. 성능 인증: 어떤 토크나이저가 이론적 최적점으로부터 얼마나 먼지를 측정하기 위한 엄격한 하한을 제공합니다. 저자들은 실험적으로 표준 어휘 크기에서 현재 방법론들이 이미 이 최적점에 매우 가깝다는 (1% 이내) 것을 발견했습니다.
3. 압축 개선: BPE 가 이미 거의 최적에 가깝지만, 특정 반올림 기법 (예: Bias) 은 약간 더 나은 내재적 압축 지표를 제공할 수 있음을 보여줍니다.

저자들은 하류 작업 개선에 대해서는 겸손한 입장을 유지하며, BpB 는 일관되게 개선되었지만 하류 CORE 작업에서의 이득은 덜 일관적임을 지적합니다. 그들은 그들의 방법이 이론적으로 우월한 프레임워크와 인증 가능한 한계를 제공하지만, 현재 대규모 언어 모델 학습의 맥락에서 BPE 와 같이 고도로 튜닝된 탐욕적 방법 대비 실제 이득은 점진적이라고 결론지었습니다.