💬 NLP

Tokenisation over Bounded Alphabets is Hard

이 논문은 이진 및 단항 사례를 포함한 유한 알파벳에 대한 토큰화가 근본적으로 NP-완전(NP-complete)이자 APX-하드(APX-hard)임을 증명함으로써, 그 계산적 난해성이 큰 입력 알파벳의 결과물이 아니라 내재적인 장벽임을 확립하고 현재의 실용적인 알고리즘에서 휴리스틱 접근 방식이 필요한 이유를 설명한다.

원저자: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

게시일 2026-08-11

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Violeta Kastreva, Philip Whittington, Dennis Komm, Tiago Pimentel

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 친구에게 비밀 메시지를 보내려고 한다고 상상해 보세요. 하지만 메시지를 보낼 수 있는 유일한 방법은 단어를 미리 승인된 작은 조각들로 나누는 것뿐입니다. 만약 당신이 "superduper"라는 단어를 보낸다면, 친구의 사전에는 그 단어 전체가 아닌 "super"와 "duper"라는 두 개의 조각만 들어있기 때문에, 단어를 "super"와 "duper"로 나누어 보내야 할 수도 있습니다. 이것이 바로 컴퓨터에게 인간의 언어를 이해하도록 가르치는 첫 단계인 **토큰화(tokenization)**의 핵심입니다. 컴퓨터가 문장을 읽기 전에, 먼저 이 문장을 관리 가능한 '토큰'(레고 블록 같은 것)으로 잘게 나누어야 합니다. 목표는 가능한 한 적은 수의 블록을 사용하여 메시지를 더 짧고 빠르게 만드는 것입니다. 이것을 **압축(compression)**이라고 합니다. 책 한 권을 더 적은 수의 블록으로 압축할 수 있다면, 컴퓨터는 이를 더 빠르게 읽고 더 효율적으로 학습할 수 있습니다. 수년 동안 과학자들은 이 과정을 자동으로 수행하기 위해, 마치 눈앞에 보이는 가장 큰 레고 조각을 움켜쥐는 아이처럼 영리하고 탐욕적인 알고리즘을 만들어 왔습니다. 하지만 한 가지 큰 의문이 남아 있었습니다. 어떤 텍스트든 완벽하게 자를 수 있는 수학적으로 최적인 방법이 존재할까요, 아니면 우리는 그저 "적당히 괜찮은" 추측에 머물러 있는 것일까요?

"Tokenisation Over Bounded Alphabets Is Hard"라는 제목의 이 논문은 그 질문의 심연을 파고듭니다. ETH 취리히와 소피아 대학교 연구진으로 구성된 저자들은, 규칙이 아무리 단순하더라도 완벽한 절단 방법을 찾는 것이 실제로 컴퓨터에게 악몽과 같은 일인지 증명하고자 했습니다. 그들은 두 가지 주요 절단 방식에 집중합니다. 하나는 최적의 레고 블록 세트(어휘 사전)를 한꺼번에 선택하는 **직접 토큰화(Direct Tokenisation)**이고, 다른 하나는 단일 문자로 시작하여 더 이상 붙일 데가 없을 때까지 쌍을 계속 붙여 나가는 **상향식 토큰화(Bottom-Up Tokenisation)**입니다. 이 이야기의 큰 반전은, 그들이 이 방법들을 무한하고 혼란스러운 모든 인간의 소리 알파벳이 아니라, 컴퓨터에서 실제로 사용하는 아주 작은 고정 집합인 이진법(전등 스위치처럼 0과 1만 존재하는 방식)과 단항법(동일한 구슬이 줄지어 있는 것처럼 단 하나의 기호만 존재하는 방식)을 대상으로 테스트했다는 점입니다.

이 논문의 주요 결론은 "아니요, 완벽한 해결책을 쉽게 찾을 수 없습니다"라는 단호한 답변입니다. 저자들은 가장 단순한 알파벳(예를 들어 0과 1로만 이루어진 세상)을 사용하더라도, 텍스트를 압축하는 최적의 방법을 찾는 것이 **NP-완전(NP-complete)**이며 **APX-하드(APX-hard)**임을 증축합니다. 쉬운 말로 풀이하자면, 아무리 많은 컴퓨팅 파워를 쏟아부어도 최선의 결과를 보장할 수 있는 빠르고 효율적인 알고리즘은 존재하지 않는다는 뜻입니다. 이는 단순히 문제가 어렵다는 것을 넘어, 근본적으로 어려운 문제입니다. 저자들은 이 어려움이 인간 언어의 복잡성이나 거대한 알파벳 때문에 발생하는 것이 아님을 명시적으로 밝힙니다. 대신, 그들은 이 장벽이 가장 단순하고 제한적인 시나리오에서도 존재한다는 것을 보여줍니다. 나아가, 그들은 주요 수학적 미스터리(P = NP)가 해결되지 않는 한, 합리적인 시간 내에 완벽한 답에 "가까이" 가는 것조차 불가능하다는 것을 증명합니다. 즉, 최적의 해답에 임의로 가까워질 수 있는 다항 시간 근사 스킴(PTAS)은 존재하지 않습니다.

연구진은 또한 알파벳이 단 하나의 기호만 있는 단항(unary) 사례(예를 들어 "a"라는 글자로만 이루어진 메시지)도 다룹니다. 당신은 "글자가 하나뿐이라면 얼마나 쉽겠어?"라고 생각할지도 모릅니다. 놀랍게도, 그들은 이 경우에도 텍스트를 자르는 최적의 방법을 찾는 것이 **강한 NP-완전(strongly NP-complete)**임을 증명합니다. 이는 매우 무거운 수학적 결과로, 이 난제가 단순히 방대한 데이터 세트에서 비롯된 특이 현상이 아니라, 텍스트를 최적으로 압축하려는 논리 자체에 내재되어 있음을 시사합니다.

그렇다면 이것이 미래에 어떤 의미를 가질까요? 이 논문은 문제를 해결할 새로운 마법 같은 알고리즘을 제시하지 않습니다. 대신, 우리가 오늘날 사용하는 BPE(Byte-Pair Encoding)나 UnigramLM 같은 도구들이 왜 휴리스틱(heuristic)—즉, 완벽한 답을 계산하는 대신 영리한 지름길과 추측을 사용하는 방식—이 될 수밖에 없는지를 설명합니다. 저자들은 완벽한 답을 찾는 것이 계산적으로 불가능하기 때문에, 연구자들이 "최적의 토크나이저"라는 성배를 쫓는 것을 멈추고, 대신 증명 가능할 정도로 우수한 근사법을 구축하는 데 집중해야 한다고 주장합니다. 완벽함으로 가는 문은 잠겨 있고 열쇠는 존재하지 않습니다. 우리가 할 수 있는 최선은 우리가 가진 가장 좋은 도구가 무엇인지 배우는 것입니다.

문제 정의
최근의 이론적 연구는 데이터셋에 대한 최적의 토크나이저를 찾는 것이 NP-완전(NP-complete)임을 입증했다. 그러나 이러한 기존 결과들은 토큰화가 무제한으로 큰 알파벳 위에서 작동한다는 가정에 의존한다. 실제 자연어 처리에서 토크나이저는 고정된 크기의 유한한 알파벳(예: 크기가 256인 바이트, 크기가 약 170,000인 유니코드 문자, 또는 크기가 2인 이진/비트 문자열) 위에서 작동한다. 알파벳 크기가 상수로 제한될 때도 토큰화의 계산적 난해함이 지속되는지는 여전히 미해결 과제로 남아 있다. 본 논문은 유한한 알파벳 위에서의 토큰화 복잡도를 분석함으로써 이 간극을 메우며, 특히 이진(크기 2) 및 단항(크기 1) 알파벳에 대해 최적의 토크나이저를 효율적으로 찾을 수 있는지 조사한다.

방법론
저자들은 입력 알파벳 $\Sigma$ 의 크기가 $n$ 인 $n$ -진 토큰화 문제를 정의한다. 저자들은 두 가지 자연스러운 변형된 토큰화 방식을 분석한다:

직접 토큰화(Direct Tokenisation): 데이터셋에 적용되었을 때 총 압축 길이를 최소화하는 크기 $K$ 의 어휘집 $S$ 를 찾는 것.
상향식 토큰화(Bottom-up Tokenisation): 데이터셋에 순차적으로 적용되는 $K$ 개의 병합 연산 시퀀스를 찾아 총 압축 길이를 최소화하는 것.

사용된 목적 함수는 압축 길이(인코딩 후의 총 토큰 수)이며, 이는 모델 학습 및 추론 비용과 상관관계가 있다. 저자들은 다음과 같은 표준 복잡도 이론적 기법을 사용하여 난해성을 입증한다:

NP-난해성(NP-Hardness): 알려진 NP-난해 문제(구체적으로 3-OCC-MAX2SAT 및 Vertex Cover)로부터 다항 시간 환원을 통해 증명된다.
APX-난해성(APX-Hardness): APX-완전 문제로부터 L-환원(L-reductions, 근사 보존 환원)을 통해 증명된다. 이는 해당 문제들이 PTAS(다항 시간 근사 스킴) 클래스에 속하지 않음을 보여주며, 즉 P = NP가 아닌 한 다항 시간 내에 임의로 정밀하게 근사할 수 없음을 의미한다.
갭 문제(Gap Problems): 저자들은 명시적인 근사 난해성 상수를 도출하기 위해 문제의 갭 버전을 정의한다.

주요 기여 및 결과

이진 토큰화는 APX-hard이다:
본 논문은 이진 직접 토적인 방식과 이진 상향식 토큰화 방식 모두가 APX-hard임을 증명한다.

직접 케이스: 이진 직접 토큰화는 (P = NP가 아닌 한) 근사 비율 $\rho < 1.000002$ 로 다항 시간 내에 근사될 수 없음이 밝혀졌다.
상향식 케이스: 마찬가지로, 이진 상향식 토큰화는 $\rho < 1.0000001$ 의 난해성 상수를 가진 APX-hard이다.
이 결과들은 가장 단순한 비자명한 알파벳인 이진 알파벳에서도 최적의 토크나이저를 찾는 것은 계산적으로 난해하며, 다항 시간 알고리즘이 최적값에 임의로 가까운 근사를 보장할 수 없음을 시사한다.

단항 토큰화는 강한 NP-완전(Strongly NP-complete)이다:
저자들은 이론적으로 가장 "쉬운" 변형인 단항 케이스(알파벳 크기 1)를 조사한다.

저자들은 단항 직접 토큰화가 강한 NP-완전임을 증명한다. 이는 Vertex Cover 문제로부터의 환원을 통해 이루어진다. 이 증명은 난해성이 입력 표현(문자열 대 문자열 길이)의 부산물이 아니라 문제 구조 자체에 내재되어 있음을 확립한다.
단항 상향식 토큰화의 경우, 저자들은 최적 쌍 인코딩(Optimal Pair Encoding, OPE) 토큰화라고 알려진 변형이 Addition Chain 문제로부터 (적어도) 약한 NP-완전(weakly NP-complete)임을 입증한다. 표준 단항 상향식 토큰화의 복잡도는 본 연구에서 미해결 과제로 남겨두었다.

난해성의 계층 구조:
본 논문은 다음과 같은 명확한 계층 구조를 확립한다: 만약 $n$ -진 토큰화가 난해하다면, $n' > n$ 인 모든 $n'$ -진 토큰화 역시 난해하다. 결과적으로, 이진 및 단항 케이스에 대한 난해성 결과는 모든 더 큰 유한 알파벳(바이트 및 유니코드 알파벳 포함)으로 당연히 확장된다.

의의 및 주장
본 논문은 이러한 결과가 토크나이저 복잡성에 대한 이해를 근본적으로 변화시킨다고 주장한다. 단항 및 이진 알파벳에서도 토큰화가 여전히 난해함을 증명함으로써, 저자들은 계산적 난해함이 대규모 알파벳이나 복잡한 병합 연산의 부산물이 아님을 보여준다. 대신, 이는 데이터를 토큰화를 통해 최적으로 압축하려는 문제에 내재된 근본적인 장벽이다.

이러한 발견은 현재의 실용적인 알고리즘들, 예를 들어 Byte-Pair Encoding (BPE) 및 UnigramLM이 왜 정확한 최적화 대신 휴리스틱과 탐욕적(greedy) 전략에 의존하는지에 대한 이론적 근거를 제공한다. 본 논문은 결론적으로, 최적의 토크나이저를 정확히 찾는 것은 어떤 비자명한 데이터셋 크기에 대해서도 불가능할 가능성이 높으므로, 향후 연구는 증명 가능한 수준의 좋은 근사 알고리즘을 개발하거나 문제의 제약 조건을 완화하는 데 집중해야 한다고 제언한다.

유사한 논문