기술 요약: 토큰 공간 압축을 통한 제약된 디코딩 가속화 (CFGZIP)

문제 정의

대규모 언어 모델 (LLM) 은 종종 JSON, XML 또는 도메인별 프로그래밍 언어와 같은 특정 구조에 부합하는 텍스트 생성이 요구됩니다. LLM 은 학습 데이터에서 발견되는 일반적인 형식에서는 잘 수행되지만, 새로운 또는 복잡한 형식에서는 어려움을 겪습니다. 구문적 정확성을 보장하기 위해 제약된 디코딩 (Constrained Decoding) 엔진이 사용됩니다. 이러한 엔진은 컨텍스트 자유 문법 (CFG) 을 사용하여 각 생성 단계에서 무효한 토큰을 마스킹합니다.

그러나 현재 최첨단 (SoTA) 문법 엔진 (예: XGrammar2) 은 상당한 성능 병목 현상에 직면해 있습니다. 최적화되어 있더라도, 이러한 엔진은 모든 디코딩 단계에서 전체 토큰 어휘에 대해 토큰을 유효성 검사해야 합니다. 복잡한 CFG(예: C++ 또는 사용자 정의 언어) 의 경우, 이로 인해 prohibitive 한 오버헤드가 발생하여, 제약 없는 생성에 비해 추론 지연 시간이 2 배에서 10 배까지 증가합니다. 이러한 지연 시간은 복잡한 문법을 포함하는 대규모 애플리케이션에서 제약된 디코딩을 실행 불가능하게 만듭니다.

방법론: CFGZIP

저자들은 CFGZIP 을 소개합니다. 이는 정확성을 희생하지 않고 문법 엔진의 단계별 실행 시간을 단축하기 위해 토큰 검색 공간을 압축하도록 설계된 오프라인 기술입니다.

핵심 개념: 동치 클래스

CFGZIP 의 근본적인 통찰력은 어휘 내의 많은 토큰이 특정 CFG 에 대해 **교환 가능 (interchangeable)**하다는 것입니다. 두 토큰 $t$와 $u$가 "구문적으로 합동 (syntactically congruent)"이라면, 언어 $L(G)$의 모든 유효한 문자열에서 유효성에 영향을 주지 않고 서로 바꿀 수 있습니다. 결과적으로, 문법 엔진은 모든 개별 토큰을 검증하는 대신 동치 클래스당 하나의 대표 토큰의 유효성만 확인하면 됩니다.

파이프라인

1. 오프라인 사전 계산:

   • 근사화: 임의의 CFG 에 대한 정확한 구문 합동성은 결정 불가능하므로, CFGZIP 은 **이동 동치 (Displacement Equivalence, $\sim_{L(G)}$)**라고 불리는 계산 가능한 근사값을 계산합니다.
   • 메커니즘: CFG 를 Greibach 정규형 (GNF) 으로 변환하여 푸시다운 오토마타 (PDA) 를 활용합니다. 각 토큰에 대해 시스템은 해당 토큰이 PDA 에서 유발하는 입력/출력 스택 전이의 집합인 "이동 (displacement)" $\Delta_G(t)$를 계산합니다. 동일한 이동 집합을 가진 토큰들은 동일한 동치 클래스로 그룹화됩니다.
   • 최적화: 이 계산을 계산적으로 실현 가능하게 만들기 위해 저자들은 사전 계산된 **스택 인접 관계 (stack-adjacency relation)**를 사용하여 스택 백트래킹 연산을 제한함으로써 대규모 문법에서의 메모리 폭주를 방지합니다.
   • 캐싱: 시스템은 토큰 ID 를 클래스 ID 로 매핑하고, 각 클래스의 "대표"로 바이트 단위로 가장 짧은 토큰을 선택합니다. 이러한 매핑은 디스크에 캐시됩니다.

2. 추론 시간 연산:

   • 어휘 축소: 문법 엔진은 전체 토큰 어휘가 아닌 동치 클래스 대표의 어휘로 초기화됩니다.
   • 토큰 매핑: LLM 이 토큰을 샘플링할 때, CFGZIP 은 이를 해당 클래스 대표로 매핑하고 파서 상태를 업데이트하기 위해 이 대표를 문법 엔진에 전달합니다.
   • 마스킹: 문법 엔진은 더 작은 대표 집합에 대한 유효성 마스크를 생성합니다. 그런 다음 이 마스크는 "수집 (gathered)"되어 원래 LLM 로짓에 적용됩니다. 이 연산은 GPU 에서 병렬화 가능하며 최소한의 오버헤드를 초래합니다.

주요 특성

• 무손실: 압축은 수학적으로 무손실임이 증명되었습니다. CFGZIP 이 장착된 엔진의 출력은 원래 엔진의 출력과 바이트 단위로 동일합니다.
• 엔진 독립성: 이론적으로는 모든 문법 엔진과 호환되지만, 논문은 XGrammar2 에 초점을 맞추고 있습니다.
• 오프라인: 무거운 계산은 토크나이저/CFG 쌍당 한 번만 수행되며, 추론 중에는 실질적인 오버헤드가 발생하지 않습니다.

실험 결과

저자들은 Llama-3.2-3B, Qwen3-4B, gpt-oss-20B 에서 XGrammar2 와 결합된 CFGZIP 을 JSON 스키마, XML, C++, 그리고 Bython(사용자 정의 중괄호 기반 Python 변형)이라는 네 가지 작업에 대해 평가했습니다.

• 지연 시간 감소: CFGZIP 은 문법 엔진의 오버헤드를 **1~2 차수 (orders of magnitude)**만큼 감소시켰습니다.
  • **C++**의 경우, 총 추론 시간이 거의 반으로 줄었습니다.
  • Bython(복잡하고 리소스가 부족한 언어) 의 경우, 총 제약 생성 시간이 약 7.5 배 감소했습니다.
• 정확성: CFGZIP 은 100% 구문적 정확성을 유지했습니다 (베이스라인 엔진과 바이트 단위로 동일).
  • 기능적 정확성: 제약된 디코딩은 기능적 정확성을 크게 향상시켰으며, 특히 제약 없는 모델이 어려움을 겪었던 Bython 작업에서 두드러졌습니다 (예: GPT-20B 의 기능적 정확성이 10.8% 에서 46.9% 로 향상됨).
• 압축 비율: 이 기술은 Llama-3B/C++ 의 경우 40:1에서 GPT-20B/JSON 의 경우 800:1에 이르는 압축 비율을 달성하여 엔진이 처리해야 하는 어휘 크기를 극적으로 줄였습니다.

중요성과 주장

이 논문은 CFGZIP 이 복잡한 CFG 에 대해 대규모로 제약된 디코딩을 실행 가능하게 만든다고 주장합니다.

• 격차 해소: 최첨단 엔진은 JSON 과 같은 단순한 문법에는 효율적이지만, C++ 과 같은 복잡한 문법에는 처리 불가능한 지연 시간을 초래합니다. CFGZIP 은 이러한 오버헤드를 거의 무시할 수 있는 수준까지 줄여, 이러한 어려운 경우에 제약된 디코딩의 성능 이점을 가능하게 합니다.
• 비용 효율성: 결과는 작은 저비용 모델의 경우, 높은 기능적 정확성을 달성하기 위해 더 큰 모델을 사용하는 대신 제약된 디코딩이 실현 가능한 대안이 될 수 있음을 시사합니다.
• 실용성: 무거운 작업을 오프라인 사전 계산 단계로 분리함으로써, CFGZIP 은 속도 저하 없이 복잡한 도메인별 언어에 대한 엄격한 준수가 필요한 실시간 애플리케이션을 가능하게 합니다.

한계점

저자들은 CFGZIP 이 모든 시나리오에 대한 만능 해결책이 아니라고 지적합니다.

• 동적 컨텍스트: 오프라인 사전 계산 시간 (수 초에서 수 분) 으로 인해, llguidance 와 같은 엔진이 이미 매우 최적화된 동적 단일 사용 CFG(예: 즉흥적 JSON 스키마 또는 함수 호출) 에는 덜 적합합니다.
• 엔진 호환성: 이론적으로는 엔진 독립적이지만, 현재 구현은 Python 기반이며 XGrammar2 와 통합되어 있습니다. Python 바인딩이 부재한 llama.cpp 와 같은 C++ 전용 엔진이나 transformers-cfg 의 왼쪽 재귀 문법과 같이 특정 CFG 를 지원하지 않는 엔진과는 호환되지 않습니다.
• 범위: 이 방법은 코드 생성에 사용되는 것과 같은 정적이고 크며 복잡한 CFG 에 가장 적합합니다.