본 논문은 제약 조건이 있는 언어 모델 생성에 대한 기존의 국소 제약 디코딩(LCD) 방식의 두 가지 주요 문제점, 즉 (i) 모든 토큰에 대한 제약 조건 평가의 높은 비용과 (ii) 전역 분포 왜곡 문제를 해결하는 새로운 알고리즘을 제시합니다. 기존 LCD 방식은 매 시간 단계마다 토큰을 순차적으로 샘플링하며 제약 조건 위반을 방지하지만, 어휘 사전 크기가 클 경우 모든 토큰에 대한 제약 조건 검사가 계산적으로 비효율적이고, 국소적인 정보만으로 토큰을 샘플링하여 전역 최적해를 찾지 못하는 문제가 있습니다. 본 논문에서 제안하는 알고리즘은 적응적 기각 샘플링을 통해 제약 조건 평가 횟수를 획기적으로 줄이고, 추가적인 비용으로 중요도 가중치를 정확하게 추정하여 순차적 몬테카를로 알고리즘을 통해 국소 제약 적용의 단점을 보완합니다. text-to-SQL, 분자 합성, 목표 추론, 패턴 매칭, JSON 등 다양한 영역에서의 실험을 통해 기존 최고 성능 기법보다 우수한 성능과 효율성을 보임을 입증합니다. 또한, 이 방법의 실행 시간 효율성은 제약 없는 LM과 제약 있는 LM 간의 차이에 따라 동적으로 변하며, 더 나은 모델일수록 실행 시간 개선 효과가 크다는 것을 이론적, 실험적으로 분석합니다.
