XGrammar-2: 에이전트 LLM의 동적 구조적 생성을 위한 TagDispatch와 Cross-Grammar 캐시

요약

LLM이 JSON·함수 호출·도구 응답을 반드시 지켜야 하는 스키마 형식으로 출력하려면, 모델이 토큰을 생성할 때마다 어휘 전체를 검사해 문법에 어긋나는 토큰을 실시간으로 차단해야 한다. 이 구조적 생성(Structured Generation) 과정을 효율적으로 처리하는 엔진이 xGrammar다. 2024년 11월 MLC AI 팀이 공개한 원본 xGrammar는 푸시다운 오토마톤(PDA)과 적응형 토큰 마스크 캐시로 추론 오버헤드를 거의 0에 가깝게 줄였다. 2026년 1월 arXiv에 등재되고 같은 해 5월 ACM CAIS '26에서 발표된 XGrammar-2는 에이전트 환경에서의 핵심 과제, 즉 단일 응답 안에서 문법이 동적으로 바뀌는 상황을 해결한다. TagDispatch로 태그 기반 구조 전환을 지원하고, Cross-Grammar Cache로 서로 다른 문법 간 서브구조 재사용을 실현해, 이전 대비 컴파일 속도 6배 향상과 서빙 오버헤드 제로에 가까운 성능을 달성했다. vLLM, SGLang, TRT-LLM, MLC-LLM 등 주요 서빙 프레임워크가 xGrammar를 기본 백엔드로 채택하고 있다.

배경: 구조적 생성이 왜 어려운가

어휘 마스킹의 비용

LLM은 각 디코딩 스텝에서 어휘 크기(보통 32,000~128,000 토큰) 전체에 걸친 로짓 벡터를 출력한다. 구조적 생성은 이 로짓에서 현재 문법 상태에 허용되지 않는 토큰의 로짓을 마이너스 무한대로 덮어써 샘플링이 항상 문법에 맞는 토큰을 선택하도록 강제한다. 이 마스킹 계산이 순진하게 구현되면 디코딩 스텝마다 수만 개 토큰을 검사하는 연산이 추가되어, 소형 모델에서는 추론 속도를 2~3배 저하시킬 수 있다.

에이전트 환경의 추가 과제

단순 챗봇은 응답 전체를 하나의 JSON 스키마로 고정할 수 있다. 하지만 에이전트는 하나의 응답 안에서 여러 번 도구를 호출하고, 각 호출마다 다른 인자 스키마를 따라야 한다. 예컨대 web_search(query: str)를 호출하다가 code_exec(code: str, timeout: int)로 전환되는 식이다. 기존 엔진은 문법 컴파일 비용을 요청 시작 시 한 번 지불하는 구조여서, 중간에 새 문법이 등장하면 지연이 재발생했다.

그림 1. 구조적 생성 파이프라인 — 매 토큰마다 문법 엔진이 마스크를 생성해 로짓에 적용

xGrammar 원본 아키텍처

컨텍스트 자유 문법(CFG)과 푸시다운 오토마톤

구조적 생성의 이론적 기반은 컨텍스트 자유 문법(CFG)다. JSON은 CFG로 정확하게 기술되며, JSON Schema나 Pydantic 모델은 CFG 규칙 집합으로 컴파일된다. xGrammar는 CFG를 푸시다운 오토마톤(PDA)으로 변환해 실행한다. PDA는 스택을 가진 유한 상태 기계(FSM)로, CFG 규칙의 재귀 구조를 표현할 수 있다.

스택 상태: 파싱 진행 중 열린 구조(배열, 객체, 중첩 등)를 스택에 저장
상태 전이: 생성된 토큰마다 PDA 상태가 갱신되고 다음 허용 상태가 결정됨
문법 수용: PDA가 종료 상태에 도달하면 응답이 완성된 문법 구조를 가짐

적응형 토큰 마스크 캐시 (Adaptive Token Mask Cache)

매 스텝마다 전체 어휘를 PDA로 검사하면 오버헤드가 크다. xGrammar의 핵심 최적화는 각 CFG 상태를 세 그룹으로 미리 분류하는 것이다.

그룹	설명	처리
항상 허용	현재 상태에서 어떤 컨텍스트에서도 유효한 토큰	캐시에 미리 저장
항상 거부	어떤 컨텍스트에서도 유효하지 않은 토큰	캐시에 미리 저장
컨텍스트 의존	현재 입력 상태에 따라 허용 여부가 달라지는 소수 토큰	런타임에만 검사

이 분류 덕분에 런타임에 검사해야 할 토큰 수가 어휘의 수% 수준으로 줄어든다. GPU 커널과 CPU 쓰레드에서 병렬로 캐시 조회를 수행해 디코딩 파이프라인과 오버랩된다.

XGrammar-2: 에이전트 환경을 위한 재설계

XGrammar-2는 2026년 1월 arXiv(2601.04426)에 등재되고 5월 ACM CAIS '26에서 발표됐다. 원본 대비 두 가지 핵심 문제를 해결했다.

문제 1: 응답 중간에 문법이 바뀐다

에이전트 LLM은 하나의 응답 스트림 안에서 여러 도구를 순서대로 호출한다. 각 도구 호출은 서로 다른 JSON 스키마를 따른다. 기존 엔진은 요청마다 단일 문법을 컴파일하는 구조여서, 문법 전환이 일어나면 전체를 재컴파일해야 했다.

TagDispatch는 이 문제를 해결하는 첫 번째 핵심 메커니즘이다. 개발자가 응답 포맷 안에 <tool_call_search>, <tool_call_exec> 같은 구조 전환 태그를 정의하면, 문법 엔진이 태그를 만나는 순간 다음에 적용할 문법을 즉시 전환한다. 재컴파일 없이 사전에 등록된 문법 집합을 태그로 디스패치하는 방식이다.

생각 텍스트
자유 텍스트 문법

→

<tool_call_search>
TagDispatch 발동

→

{"query": "..."}
search 스키마 적용

→

<tool_call_exec>
다시 TagDispatch

→

{"code": "..."}
exec 스키마 적용

TagDispatch 동작 예시 — 에이전트 응답 스트림에서 태그가 문법을 전환

문제 2: 요청마다 비슷한 문법을 반복 컴파일한다

서비스에 등록된 도구가 수백 개라도 실제 스키마는 공통 서브구조를 많이 공유한다. 예컨대 string, integer, nullable<T>, array<T> 같은 기본 타입은 모든 스키마에 반복된다.

Cross-Grammar Cache는 서브구조 단위로 컴파일 결과를 캐시해 문법 간에 재사용하는 메커니즘이다. 새 스키마를 컴파일할 때 이미 캐시된 서브구조가 있으면 합성만 하면 된다. 여기에 JIT(Just-In-Time) 컴파일을 결합해 자주 쓰이는 문법 경로를 런타임에 기계어로 변환하고, Earley 파서로 적응형 토큰 마스크 캐시의 갱신 효율을 높였다.

결과: 이전 엔진 대비 컴파일 속도 6배 향상, 서빙 오버헤드는 사실상 0.

그림 2. xGrammar vs XGrammar-2 구조 비교 — TagDispatch·Cross-Grammar Cache·JIT이 추가된 지점

프로덕션 서빙 프레임워크 통합 현황

프레임워크	xGrammar 통합 버전	기본 백엔드 여부
vLLM	0.6.3+ (2024.12)	✅ 기본 (guidance 대체)
SGLang	0.4+	✅ 기본
TensorRT-LLM	0.12+	✅ 지원
MLC-LLM	0.18+	✅ 기본 (자체 개발팀)

vLLM에서 구조적 출력을 사용할 때 guided_decoding_backend를 명시하지 않으면 xGrammar가 자동으로 선택된다. JSON Schema, Pydantic 모델, 정규식(regex), EBNF 문법을 모두 지원한다.

JSON Schema 방식

from vllm import LLM, SamplingParams
from pydantic import BaseModel

class Person(BaseModel):
    name: str
    age: int

llm = LLM(model="meta-llama/Llama-3.1-8B-Instruct")
params = SamplingParams(
    guided_decoding={
        "json": Person.model_json_schema()
    }
)
output = llm.generate(prompts, params)

EBNF 문법 방식 (더 유연)

grammar = r"""
root   ::= "yes" | "no"
"""
params = SamplingParams(
    guided_decoding={"grammar": grammar}
)

vLLM에서 구조적 출력 활성화하는 방법

성능 특성과 운영 고려사항

오버헤드 측정

xGrammar의 마스크 생성 비용은 대부분의 시나리오에서 추론 레이턴시의 1% 미만이다. 다만 다음 경우에는 오버헤드가 커질 수 있다.

첫 컴파일 비용: 처음 만나는 스키마는 PDA를 생성해야 하므로 수십 ms 지연 가능. 요청 시작 전에 서버가 공통 스키마를 워밍업(pre-compile)해 두는 것이 권장된다.
매우 복잡한 문법: 수천 개의 선택지가 있는 enum, 깊이 중첩된 재귀 구조는 어휘 분류 사전 계산 비용이 높아진다.
컨텍스트 의존 토큰 비율: 스키마의 특성에 따라 컨텍스트 의존 토큰 비율이 달라지며, 이 비율이 높으면 런타임 검사 부담이 늘어난다.

XGrammar-2 이후 운영 팁

TagDispatch 문법 레지스트리: 자주 사용하는 도구 스키마를 서버 시작 시 모두 등록해 Cross-Grammar Cache를 미리 채운다.
JIT 워밍업: 첫 요청 전에 핵심 문법으로 dry-run 추론을 실행해 JIT 컴파일을 완료한다.
스키마 정규화: 사용자 입력 JSON Schema를 캐시 키가 일치하도록 정규화(필드 정렬, 공백 제거)한다. 같은 스키마도 직렬화가 다르면 캐시 미스가 발생한다.
fallback 모니터링: 정규식이나 특수 문법이 xGrammar에서 지원되지 않을 경우 guidance 백엔드로 fallback된다. 이 빈도를 지표로 노출해 모니터링한다.

한계와 열린 질문

Open question: XGrammar-2의 Cross-Grammar Cache가 도구가 수천 개인 대규모 에이전트 시스템에서 메모리를 얼마나 소비하는지, 최적 캐시 퇴출 정책이 무엇인지에 대한 체계적인 실측 데이터가 아직 부족하다.

Open question: Diffusion LLM처럼 자동회귀 방식이 아닌 모델에 CFG 기반 구조적 생성을 적용하는 방법은 아직 연구 단계다. 양방향 어텐션 구조에서 PDA 상태를 어떻게 추적할지에 대한 합의가 없다.

JSON Schema가 아닌 세만틱 제약(예: "도시 이름만 출력")은 CFG로 표현하기 어렵다. 이 경우 여전히 후처리 검증과의 조합이 필요하다.

References

Lianmin Zheng et al., XGrammar: Flexible and Efficient Structured Generation Engine for Large Language Models (arXiv:2411.15100, 2024-11): https://arxiv.org/abs/2411.15100
MLC AI Blog, "Achieving Efficient, Flexible, and Portable Structured Generation with XGrammar" (2024-11-22): https://blog.mlc.ai/2024/11/22/achieving-efficient-flexible-portable-structured-generation-with-xgrammar
Ruihang Lai et al., XGrammar-2: Dynamic and Efficient Structured Generation Engine for Agentic LLMs (arXiv:2601.04426, ACM CAIS '26, 2026): https://arxiv.org/abs/2601.04426
vLLM Structured Outputs documentation: https://docs.vllm.ai/en/latest/features/structured_outputs/
XGrammar GitHub repository: https://github.com/mlc-ai/xgrammar
Red Hat Developer article on structured outputs in vLLM (2025-06-03): https://developers.redhat.com/articles/2025/06/03/structured-outputs-vllm-guiding-ai-responses