본 논문은 대규모 언어 모델(LLM) 에이전트의 복잡하고 다양해지는 응용 분야에 따라 구조화된 출력(코드, 함수 호출, 에이전트 명령 등)에 대한 수요가 증가함에 따라, LLM 추론에서 구조화된 생성의 효율적인 처리가 중요해짐을 지적합니다. 기존의 구문 분석 방식인 Context-Free Grammar(CFG)는 유연성이 뛰어나지만, 실행 시 모든 어휘의 토큰에 대해 여러 스택 상태를 거쳐야 하므로 성능 저하가 발생합니다. 이를 해결하기 위해 본 논문에서는 XGrammar를 제안합니다. XGrammar는 어휘를 컨텍스트에 독립적인 토큰과 종속적인 토큰으로 나누어 사전 검사 및 런타임 해석을 최적화하고, 문법 컨텍스트 확장 및 컨텍스트 독립적 토큰 감소 변환, 효율적인 영속적 스택 구현, LLM 추론 엔진과의 공동 설계를 통해 CFG 실행 속도를 크게 향상시킵니다. 실험 결과, XGrammar는 기존 솔루션보다 최대 100배 빠른 속도를 달성하며, LLM 추론 엔진과 결합하여 거의 제로 오버헤드의 구조적 생성을 가능하게 합니다.
