본 논문은 대규모 언어 모델(LLM)의 출력이 엄격한 구조적 또는 문법적 제약 조건을 준수하도록 하는 문제를 해결하기 위해, Earley 알고리즘 기반의 새로운 동적 가지치기 전략인 ZapFormat을 제안합니다. ZapFormat은 Earley 알고리즘의 유효하지 않거나 중복된 상태를 실시간으로 식별하고 제거하여 메모리 사용량을 줄이고, 상태 캐시를 사용하여 다수의 질의에 대한 구조적 생성 속도를 높입니다. 새로운 제약된 디코딩 엔진인 Formatron에 ZapFormat을 구현하여 JSON 생성, JSON 스키마 유효성 검사, 의미 분석 등의 구조적 생성 작업에 대한 실험을 통해, Formatron이 높은 정확도의 준수 출력을 유지하면서 최첨단 구현에 비해 최대 2배의 추론 속도 향상을 달성함을 보여줍니다. Formatron은 다양한 LLM 아키텍처에 적용 가능하며, 오픈 소스로 공개되었습니다.
