본 논문은 대규모 언어 모델(LLM)이 코드 조각이나 형식화된 데이터와 같이 정확한 구문 규칙을 준수하는 구조화된 출력을 생성하도록 하는 문제를 다룹니다. 문법 제약 디코딩(GCD)은 지정된 문맥 자유 문법(CFG)에 속하지 않는 출력으로 이어질 토큰을 마스킹하여 LLM 출력이 이러한 규칙과 일치하도록 보장합니다. 기존 GCD 알고리즘은 사운드니스를 보장하기 위해 LLM 서브워드 토크나이저가 주어진 CFG의 토큰과 어떻게 정렬되는지 계산하고 이 정보를 기반으로 토큰 마스크를 계산해야 하며, 이는 매우 비효율적입니다. 본 논문은 기존 접근 방식보다 17.71배 빠른 오프라인 전처리를 제공하면서 온라인 마스크 계산의 최첨단 효율성을 유지하는 새로운 GCD 알고리즘과 구현을 제시합니다.
