🤖 AI

XGrammar-2: Efficient Dynamic Structured Generation Engine for Agentic LLMs

XGrammar-2 는 동적 에이전트 LLM 워크로드를 위해 설계된 고효율 구조화 생성 엔진으로, 태그 트리거 구조 전환 및 교차 문법 캐시 재사용을 통해 기존 시스템 대비 6 배 이상 빠른 컴파일과 거의 제로에 가까운 엔드투엔드 오버헤드를 달성합니다.

원저자: Linzhang Li, Yixin Dong, Guanjie Wang, Ziyi Xu, Alexander Jiang, Tianqi Chen

게시일 2026-05-27

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Linzhang Li, Yixin Dong, Guanjie Wang, Ziyi Xu, Alexander Jiang, Tianqi Chen

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

당신이 AI(셰프) 가 되어 매우 엄격한 레시피를 따르려 한다고 상상해 보세요. 때로는 레시피가 단순합니다: "샌드위치를 만드세요." 하지만 AI 에이전트 세계에서는 레시피가 종종 복잡하고 끊임없이 변하는 일련의 지시사항입니다: "문장을 작성한 후, 날씨 도구를 호출하기 위해 JSON 코드 블록으로 전환하고, 다시 문장 작성으로 돌아간 다음, 데이터베이스 쿼리를 위한 특정 형식으로 전환하세요."

문제는 전통적인 "주방"(AI 엔진) 은 하나의 고정된 레시피를 따르는 데는 뛰어나지만, 레시피가 실시간으로 변경되거나 셰프가 수십 가지의 복잡한 형식 사이를 즉시 전환해야 할 때는 어려움을 겪는다는 점입니다. 종종 요리를 시작하기 전에 레시피 책 전체를 처음부터 다시 써야 하므로 모든 것이 느려집니다.

XGrammar-2는 이러한 혼란스럽고 역동적인 요리 시나리오를 위해 특별히 설계된 새롭고 초고효율의 주방 엔진입니다. 간단한 비유를 들어 작동 방식을 설명해 보겠습니다:

1. "마법 스위치"(TagDispatch)

문제: "STOP'이라는 단어가 나타날 때까지 정상적으로 작성하되, 그다음 수학 모드로 전환했다가 다시 돌아오라"는 레시피를 상상해 보세요. 구식 방법으로 이를 수행하는 것은 모든 가능한 단어가 다른 페이지로 이어지는 거대하고 엉킨 설명서를 작성하려는 것과 같습니다. 이는 지저분해지고 방대해집니다.

XGrammar-2 의 해결책: 그들은 TagDispatch라는 기능을 도입했습니다. 이를 마법 스위치나 교통 신호등으로 생각하세요.

AI 는 정상적으로 작성합니다 (초록불).
특정 트리거(예: <function=weather> 태그) 가 나타나는 순간, 신호등은 즉시 빨간불로 바뀌고 엔진은 정확히 어떤 "하위 레시피"(날씨용 JSON 형식) 로 전환해야 하는지 파악합니다.
해당 하위 레시피가 완료되면 신호등이 다시 초록불로 바뀌고 AI 는 정상 작성을 계속합니다.
왜 멋진가요: 거대하고 혼란스러운 설명서를 작성하는 대신, 엔진은 교통 신호등만 따릅니다. 이는 자유로운 텍스트와 엄격한 코드 사이의 전환을 즉각적이고 쉽게 만듭니다.

2. "공유 라이브러리"(Cross-Grammar Cache)

문제: 100 가지 다른 요리를 하고 있다고 상상해 보세요. 90 가지 요리는 정확히 같은 "양파 다지기" 단계를 사용하지만, 구식 엔진은 모든 요리를 완전히 새로운 작업으로 취급합니다. 이는 모든 요리마다 양파 다지는 법을 처음부터 다시 배우는 것입니다. 이는 시간 낭비입니다.

XGrammar-2 의 해결책: 그들은 공유 라이브러리(Cross-Grammar Cache)를 구축했습니다.

최종 요리 (전체 문법) 가 다르더라도 재료와 단계 (하위 구조) 는 종종 동일합니다.
XGrammar-2 는 단계를 살펴봅니다. "아, 비슷한 요리를 위해 양파 다지는 법을 이미 알아냈구나"라고 생각하면 다시 계산하지 않습니다. 대신 라이브러리에서 미리 다진 양파를 가져옵니다.
왜 멋진가요: 엔진이 같은 계산을 반복하는 것을 막습니다. 전체 요청이 다르더라도 이미 수행한 "작업"을 재사용합니다.

3. "Just-in-Time" 셰프 (JIT 컴파일)

문제: 옛날에는 한 입도 요리하기 전에 엔진이 모든 요청에 대해 레시피 책 전체를 읽어야 했습니다. 레시피가 거대하다면 (500 가지 가능한 도구를 가진 도구 호출 요청처럼), 엔진은 요리가 시작되기 전까지 책 읽는 데 몇 초를 그냥 보내게 됩니다.

XGrammar-2 의 해결책: 그들은 Just-in-Time(JIT) 방식을 사용합니다.

먼저 책 전체를 읽는 대신, 셰프는 지금 필요한 페이지만 읽습니다.
AI 가 처음 몇 단어를 생각하는 동안 ("prefill" 단계), 엔진은 조용히 레시피의 다음 몇 페이지를 준비합니다.
왜 멋진가요: 준비 시간을 숨깁니다. AI 가 다음 단어를 말 할 준비가 되면, 엔진은 이미 다음 단계를 준비해 둡니다. 이로 인해 복잡한 작업에서도 "첫 번째 단어"가 거의 즉시 나타납니다.

4. "압축된 지도"(Repetition State Compression)

문제: 일부 레시피에는 "이 동작을 1,000 번 반복하라"는 반복적인 단계가 있습니다. 구식 엔진은 각 단계마다 1,000 개의 별도 점을 그리는 지도를 그리려 합니다. 이 지도는 거대해지고 모든 것을 느리게 만듭니다.

XGrammar-2 의 해결책: 그들은 Repetition State Compression을 사용합니다.

1,000 개의 점을 그리는 대신, 하나의 큰 "루프" 화살표를 그리고 "여기를 1,000 번 돌아라"고 말합니다.
왜 멋진가요: AI 가 단계를 반복해야 하는 횟수에 상관없이 지도를 작고 간단하게 유지합니다. 이로 인해 엔진이 긴 목록이나 루프에 매몰되는 것을 방지합니다.

결과: 무엇을 발견했나요?

이 논문은 이 새로운 엔진을 현재 가장 좋은 방법들과 비교하여 테스트했습니다:

속도: 이전 엔진보다 레시피(문법) 를 6 배 더 빠르게 컴파일합니다.
효율성: AI 응답 시간에 거의 지연이 추가되지 않습니다. AI 가 그 존재조차 느끼지 못할 정도로 빠릅니다.
호환성: SGLang 및 vLLM 과 같은 인기 있는 AI 시스템과 원활하게 작동하며, 도구 호출이나 엄격한 응답 형식 따르기 같은 복잡한 작업을 문제없이 처리합니다.

요약하자면, XGrammar-2는 질문에 답하기 전에 모든 책을 다시 정리해야 하는 느리고 경직된 사서에서, 정답이 어디에 있는지 정확히 알고 이전 지식을 재사용하며 리듬을 잃지 않고 즉각적으로 주제를 전환하는 초고속 유연한 비서로 AI 의 두뇌를 업그레이드하는 것과 같습니다.

기술 요약: XGrammar-2

문제 정의

현대 대규모 언어 모델 (LLM) 에이전트는 도구 호출 및 응답 프로토콜을 위해 **동적 구조 생성 (dynamic structured generation)**에 점점 더 의존하고 있습니다. 출력 스키마가 정적이며 사전에 알려진 전통적인 구조 생성 작업과 달리, 에이전트 워크로드는 상당한 **구조적 동적성 (structural dynamism)**을 보입니다:

요청 간 동적성 (Inter-request Dynamism): 각 요청은 서로 다른 도구 및 스키마 세트 (종종 도구별 접근 제어 포함) 를 노출할 수 있어, 가능한 출력 문법의 조합적 공간이 매우 커집니다. 요청 수준에서 전체 문법을 캐싱하는 기존 엔진은 비효율적이 되어, 비용이 많이 드는 요청별 전처리를 강요하고 첫 번째 토큰 도달 시간 (TTFT) 을 증가시킵니다.
요청 내 동적성 (Intra-request Dynamism): 단일 요청 내에서 모델은 트리거 (예: 특정 도구 이름 또는 채널 태그) 에 따라 자유 형식 텍스트와 구조화된 하위 문법 간에 전환해야 합니다. 이러한 조건부 전환을 표준 Backus-Naur Form (BNF) 또는 확장 BNF (EBNF) 로 표현하는 것은 번거롭고 비효율적이며, 도구 수가 증가함에 따라 확장성이 떨어집니다.

기존의 제약된 디코딩 방법 (예: XGrammar, Outlines, llguidance) 은 이러한 동적성을 처리하는 데 어려움을 겪습니다. 이들은 동적 도구 세트에는 부적합한 사전 전체 문법 컴파일을 요구하거나, 단일 생성 스트림 내의 자유 텍스트와 구조적 제약의 교차를 처리할 효율적인 메커니즘이 부족합니다.

방법론

XGrammar-2 는 동적 에이전트 워크로드를 위해 특별히 설계된 구조 생성 엔진입니다. 이 아키텍처는 태그 트리거 구조 전환에 대한 1 차 지원과 서로 다른 출력 구조를 가진 요청 간 세밀한 재사용이라는 두 가지 핵심 설계 원칙에 기반합니다.

1. TagDispatch: 동적 디스패치 의미론

요청 내 동적성을 해결하기 위해 XGrammar-2 는 자유 형식 텍스트와 구조화된 하위 문법 간 효율적인 전환을 가능하게 하는 문법 내재 기능인 TagDispatch를 도입합니다.

메커니즘: TagDispatch 는 태그–문법 쌍 $(t_i, G_i)$ 의 목록과 중지 문자열 집합으로 매개변수화됩니다.
작동: 엔진은 두 가지 모드로 작동합니다:
- 디스패칭 모드: 엔진은 생성된 텍스트에 대해 등록된 태그를 점진적으로 매칭하기 위해 Aho–Corasick (AC) 자동화를 사용하면서 일반 텍스트를 허용합니다.
- 디스패치 모드: 태그가 매칭되면 엔진은 해당 하위 문법 $G_i$ 로 전환합니다. $G_i$ 가 완료되면 제어권이 디스패칭 모드로 돌아갑니다.
장점: 이는 복잡한 조건부 논리를 거대한 EBNF 규칙에 인코딩할 필요성을 제거하여 문법 크기와 컴파일 복잡성을 크게 줄입니다.

2. 교차 문법 캐시 (Cross-Grammar Cache)

요청 간 동적성을 해결하기 위해 XGrammar-2 는 공통 하위 구조를 공유하는 서로 다른 문법 간에 토큰 마스크 캐시를 재사용하기 위해 교차 문법 캐시를 구현합니다.

과제: 규칙 참조와 순환을 포함할 때 두 유한 상태 기계 (FSM) 가 동등한지 판단하는 것은 어렵습니다. 또한 토큰 마스크 캐시는 FSM 구조뿐만 아니라 해당 FSM 이 참조되는 방식 (문맥 확장) 에도 의존합니다.
해결책: 시스템은 계층적 해싱 알고리즘을 사용합니다:
- FSM 참조 그래프를 구성합니다.
- 비순환 부분에 대해서는 참조된 FSM 의 해시를 포함하여 하향식 (bottom-up) 으로 구조적 해시를 계산합니다.
- 순환 참조의 경우 고유한 구조 식별자를 보장하기 위해 임시 해시를 사용한 후 순환 해시 정제를 수행합니다.
재사용 전략: 새로운 문법 상태가 발견되면 시스템은 전역 캐시 풀을 확인합니다. 완벽한 일치 (동일한 FSM 및 룩어헤드) 가 발견되면 캐시를 재사용합니다. 부분 일치 (동일한 FSM, 다른 룩어헤드) 만 존재하는 경우, 시스템은 불확실한 토큰을 재확인하고 캐시를 업데이트합니다.

3. Earley 기반 적응형 토큰 마스크 캐시

이전 버전에서 사용된 푸시다운 자동화 (PDA) 를 벗어나 XGrammar-2 는 적응형 토큰 마스크 캐시를 위해 Earley 파서를 활용합니다.

근거: PDA 상태는 비결정적 문법에서 기하급수적으로 커질 수 있습니다. Earley 파서는 복잡한 컨텍스트 프리 문법에 더 효율적인 부분 파싱 상태 (프런티어) 집합을 유지합니다.
구현: 캐시는 스캔 가능한 상태 (scannable states) (다음 심볼이 터미널인 상태) 에 대해서만 구축됩니다. 스캔 불가능한 상태는 런타임에서 예측 및 완료 작업을 통해 확장됩니다. 토큰은 허용됨, 거부됨, 또는 컨텍스트 의존적으로 분류되며, 후자의 경우 런타임 컨텍스트 확인이 필요합니다.

4. Just-In-Time (JIT) 컴파일

크고 동적인 문법의 높은 컴파일 비용을 완화하기 위해:

전략: 전체 토큰 마스크 캐시를 사전에 구체화하는 대신 XGrammar-2 는 구성 가능한 JIT 시스템을 사용합니다.
실행: 프리필링 (prefilling) 단계 동안 시스템은 특정 상태에 대한 캐시 생성 비용을 추정합니다. 프리필링 중 가장 시간이 많이 소요되는 $K$ 개의 상태를 우선적으로 컴파일하여 컴파일을 프리필링과 중첩합니다. 나머지 상태는 디코딩 단계에서 온디맨드로 컴파일되어 마스크 생성을 디코딩과 중첩합니다. 이를 통해 컴파일 지연을 숨기는 것을 목표로 합니다.

5. 반복 상태 압축

JSON 스키마에서 흔히 볼 수 있는 반복 구조 (예: MinLength, MaxItems) 를 처리하기 위해:

문제: 반복 규칙의 단순한 확장은 반복 횟수에 비례하여 문법 상태가 선형적으로 증가하게 합니다.
해결책: 엔진은 반복 상태를 압축합니다. 큰 반복 범위의 경우, 구조를 기본 규칙을 $t$ 번 반복한 시퀀스로 변환한 후, 나머지 범위를 나타내는 압축된 상태를 뒤따르게 합니다. 이는 반복 제한과 관계없이 상태 수를 상수로 제한하여 캐시 크기와 불확실성을 크게 줄입니다.

주요 결과

BFCL-v3 및 JSONSchemaBench 와 같은 데이터셋을 사용하여 다양한 모델 (Qwen, Llama 시리즈) 에서 XGrammar-2 를 최신 엔진 (XGrammar, llguidance, Outlines) 과 비교하는 실험이 수행되었습니다.

컴파일 속도: XGrammar-2 는 동적 환경에서 기존 구조 생성 엔진보다 6 배 이상 빠른 컴파일을 달성합니다. 예를 들어, XGrammar 가 동적 문법을 컴파일하는 데 1000ms 이상이 소요된 반면, XGrammar-2 는 약 10ms 를 달성했습니다.
종단 간 오버헤드: 이 시스템은 현대 LLM 서비스 시스템에서 거의 제로에 가까운 종단 간 오버헤드를 발생시킵니다. 함수 호출 시나리오에서 제약 생성 (XGrammar-2) 과 비제약 생성 간의 지연 시간 격차는 6% 미만이었습니다.
처리량: XGrammar-2 는 다양한 배치 크기와 모델 규모에서 XGrammar 보다 우수한 토큰 처리량을 보여주었습니다 (예: 배치 크기 16 에서 Llama-3.2-1B 기준 2.5 배 처리량 향상).
확장성: 교차 문법 캐시 메모리 오버헤드는 낮게 유지되며, 요청 수 대신 사용된 고유 도구의 총 수에 따라 확장되어 동적 환경에서 메모리 폭발을 방지합니다.
Ablation 연구: JIT 를 제거하면 전처리 시간이 8.1 배 증가했고, 교차 문법 캐시를 제거하면 마스크 생성 시간이 크게 증가했으며, 반복 상태 압축은 긴 꼬리 반복 사례에서 전처리 시간을 99.6 배 줄였습니다.

중요성 및 주장

이 논문은 XGrammar-2 가 에이전트 애플리케이션을 지원하기 위해 LLM 서비스 시스템에 필요한 진화를 제공한다고 주장합니다. 동적 도구 세트 처리를 정적 문법 컴파일에서 분리함으로써 다음을 가능하게 합니다:

신뢰성: 사후 수정에 의존하지 않고 구조적 유효성 (예: OpenAI Harmony 응답 형식, 도구 호출 스키마) 을 엄격하게 강제합니다.
효율성: 컴파일 및 런타임 비용이 정적 워크로드와 비교 가능한 동적 워크로드를 서비스할 수 있는 능력.
채택: 이 엔진은 SGLang 및 vLLM과 같은 오픈소스 프레임워크에 통합되어 프로덕션급 추론 시스템에서의 실용적 타당성을 입증했습니다.

저자들은 XGrammar-2 를 모델 학습 기술의 대체제가 아닌, 기존 파인튜닝 또는 프롬프팅 전략과 결합하여 복잡한 에이전트 시나리오에서 견고하고 구조화된 출력을 보장할 수 있는 보완적인 추론 시간 엔진으로 위치시킵니다.