기술 요약: 제약 적응형 거절 샘플링 (Constrained Adaptive Rejection Sampling, CARS)

1. 문제 정의

언어 모델(LM)은 문법적으로 유효한 코드를 생성하거나, 데이터 스키마를 준수하거나, 화학 구조를 생성하는 것과 같이 엄격한 의미적 또는 구문적 제약을 충족해야 하는 애플리케이션에 점점 더 많이 배치되고 있습니다. 제약된 생성의 핵심 과제는 두 가지 상충하는 요구 사항 사이에서 균형을 맞추는 것입니다:

1. 충실도(Fidelity): 샘플은 근사치가 아니라 제약 조건이 주어진 LM의 실제 조건부 분포($P_L$)를 정확히 따라야 합니다.
2. 효율성(Efficiency): 유효한 샘플을 생성하기 위해 필요한 LM 순방향 패스(forward pass)의 횟수를 최소화해야 합니다.

기존의 접근 방식은 세 가지 범주로 나뉘며, 각 방식은 두 가지 기준을 동시에 충족하지 못합니다:

• 정확하지만 비효율적임: 표준 거절 샘플링(Rejection Sampling, RS)은 진정한 제약된 분포로부터 편향되지 않은 샘플을 생성하지만, 구조화된 도메인(예: 수락률 <1%)에서 대다수의 후보를 버리게 되어 계산 비용이 매우 높습니다.
• 효율적이지만 편향됨: 탐욕적 제약 디코딩(Greedy Constrained Decoding, GCD)은 생성 중에 유효하지 않은 토큰을 마스킹하여 유효성을 강제합니다. 효율적이기는 하지만, 이는 LM의 조건부 분포를 명백히 왜곡하며, 종종 다운스트림 성능을 저하시키고 종료에 실패할 가능성이 있습니다.
• 점근적으로 정확하지만 불안정함: MCMC 또는 순차 몬테카를로(Sequential Monte Carlo, SMC)와 같은 방법은 한계치에서 올바른 분포로 수렴하지만, 원칙적인 정지 규칙을 제공하지 않습니다. 초기 샘플은 임의로 편향될 수 있으며, 효율성은 하이퍼파라미터 튜닝과 안정화에 필요한 반복 횟수에 크게 의존합니다.

본 논문은 프로그램 퍼징(fuzzing)이나 분자 발견과 같이 다양한 유효 샘플 세트가 필요한 도메인에서, 정확성(진정한 분포를 보존)과 분할 상환 효율성(fidelity를 희생하지 않으면서 시간이 지남에 따라 효율성을 개선)을 모두 갖춘 알고리즘에 대한 공백이 존재한다고 주장합니다.

2. 방법론: 제약 적응형 거절 샘플링 (CARS)

CARS는 거절 샘플링의 충실도와 적응형 가지치기(adaptive pruning)의 효율성을 결합한 정확한 샘플링 알고리즘입니다. 이는 적응형 거절 샘플링(ARS)을 기반으로 구축되었으나, 제약의 구조를 활용하여 단순히 거절된 샘플뿐만 아니라 유효하지 않은 연속된 전체 계열(families of invalid continuations)을 제거하도록 확장되었습니다.

핵심 메커니즘

알고리즘은 샘플링 과정 중에 발견된 유효하지 않은 접두사(invalid prefixes)($W$) 집합을 유지합니다. 이 접두사들을 저장하기 위해 Trie 자료 구조를 사용하며, 이를 통해 이들을 피하도록 샘플링 분포($R_W$)를 동적으로 재형성합니다.

1. 초기화: 알고리즘은 빈 유효하지 않은 접두사 집합($W = \emptyset$)으로 시작합니다.
2. 샘플링: 각 반복마다 알고리즘은 재가중치 분포 $R_W$로부터 시퀀스를 샘플링합니다. 이 분포는 $W$에 속한 접두사를 확장하지 않는 시퀀스들에 대해 정규화함으로써 원래의 LM 분포 $P$로부터 유도됩니다.
   • 형식적으로, 접두사 $u$에 대해, 이를 유효한 시퀀스로 확장할 확률은 $p_u$로 추적됩니다. 만약 $u$가 알려진 유효하지 않은 접두사를 확장한다면, $p_u = 0$입니다.
   • 접두사 $u$에 대한 토큰 $a$의 샘플링 확률은 다음과 같이 조정됩니다: $R_W(ua | u) = P(ua | u) \cdot \frac{p_{ua}}{p_u}$.
3. 적응형 가지치기 (핵심 혁신): 시퀀스가 생성되면, CARS는 단순히 거절된 문자열만을 기록하는 것이 아니라(표준 ARS의 경우), 생성된 시퀀스의 모든 유효하지 않은 접두사와 그들의 모든 유효하지 않은 연속형을 식별합니다.
   • 구체적으로, 시퀀스 $w$가 생성되면, CARS는 유효한 언어 $L$에 속하지 않는 $w$의 가장 짧은 접두사 $u$를 $W$에 추가합니다.
   • 결정적으로, 또한 $ua \notin prefix(L)$인 모든 확장 $ua$(여기서$a$는 토큰)를$W$에 추가합니다.
   • 이 과정은 미래의 추출에서 유효하지 않은 하위 트리(sub-trees) 전체의 확률 질량을 효과적으로 "차감"합니다.
4. 업데이트: Trie는 새로운 유효하지 않은 접두사를 반영하도록 업데이트되며, 확률 값($p_u$)은 상위로 전파됩니다. 이를 통해 미래의 샘플이 이러한 유효하지 않은 경로를 다시 방문하지 않도록 보장하며, 수락률을 단조 증가시킵니다.

이론적 특성

• 정확성(Exactness): CARS는 대상 제약 분포 $P_L$로부터 정확하게 샘플을 생성합니다. 재가중치는 확률 질량이 유효한 시퀀스들 사이에서 올바르게 재분배되도록 보장합니다.
• 단조성(Monotonicity): $W$가 커짐에 따라 수락률은 단조롭게 개선됩니다.
• 수익 체감(Diminishing Returns): 샘플당 제거되는 기대 확률 질량은 비증가(non-increasing)합니다. 이는 실질적인 휴리스틱을 시사합니다: 일단 Trie가 유의미한 확률 질량을 제거하는 것을 멈추면, 효율성 손실 없이 후속 샘플링을 위해 분포를 "동결(freeze)"할 수 있습니다.

3. 주요 기여

1. 알고리즘 설계: 제약 구조를 활용하여 유효하지 않은 접두사 연속형을 가지치기함으로써 정확성과 실질적인 효율성을 달과내는 새로운 제약된 LM 생성 알고리즘인 CARS를 도입했습니다.
2. 이론적 보장: CARS가 진정한 제약된 분포로부터 샘플링한다는 것과, 그 적응형 업데이트가 유효한 샘플을 생성할 확률을 단조 증가시킨다는 것을 증명했습니다.
3. 실증적 검증: 다양한 도메인에 걸쳐 샘플링 효율성(유효 샘플당 적은 LM 순방향 패스)과 샘플 다양성 측면에서 CARS가 기존 방법들을 능가함을 입증했습니다.

4. 실험 결과

저자들은 네 가지 모델(Llama-3.1-8B/70B, Qwen2.5-7B/14B)을 사용하여 세 가지 뚜렷한 도메인에서 CARS를 평가했습니다.

A. 문법 기반 퍼징 (Grammar-Based Fuzzing)

• 작업: 퍼저의 코드 커버리지를 극대화하기 위해 다양하고 유효한 프로그램 시드(JSON, SQL, XML)를 생성합니다.
• 결과: CARS는 RS, ARS, RSFT보다 훨씬 적은 생성 횟수로 100개의 유효한 샘플 목표를 달성했습니다. 예를 들어, 문법 프롬프트가 없는 XML 생성에서 CARS는 약 440번의 생성이 필요했던 반면, RS/ARS는 목표에 도달하지 못했습니다(>2,000번 필요).
• 영향: CARS가 생성한 시드는 GCD(7,115) 및 MCMC(7,965)보다 높은 라인 커버리지(~7,985 라인)를 달성하였으며, 이는 분포적 충실도가 더 나은 다운스트림 성능으로 이어진다는 것을 보여줍니다.

B. 분자 합성 (Molecular Synthesis)

• 작업: 특정 화학 클래스(Acrylates, Chain Extenders, Isocyanates)에 대한 유효한 SMILES 문자열 생성.
• 결과: 100개의 유효한 분자를 생성하는 데 있어 CARS는 RS보다 4.3배, ARS보다 1.3배 적은 샘플이 필요했습니다. 또한 정확한 방법들 중 가장 높은 유효성 및 다양성 점수를 기록했습니다.
• 충실도: CARS의 KL 발산(KL divergence)은 MCMC보다 1.5배, AWRS보다 1.8배 낮았으며, 이는 진정한 분포에 대한 우수한 준수 능력을 나타냅니다.

C. Text-to-SQL 생성

• 작업: 자연어 질문으로부터 SQL 쿼리 생성 (Spider 데이터셋).
• 결과: CARS는 모든 방법 중 가장 높은 실행 정확도(0.578)를 달성했습니다. RS보다는 1.85배, ARS보다는 1.28배 적은 샘플이 필요했습니다.
• 비교: GCD와 같은 근사 방법들이 더 빨랐지만(쿼리당 1.00 샘플), 낮은 정확도(0.525)를 보였습니다. CARS는 GCD보다 높은 정확도를 제공하면서도 샘ales 수는 1.1배 수준만을 요구하여 최적의 트레이드오프를 제공했습니다.

5. 의의 및 주장

본 논문은 CARS가 LM의 정확한 제약 분포로부터 샘플링하는 새로운 최첨단(state-of-the-art) 기술을 설정한다고 주장합니다. 그 의의는 정확성과 효율성 사이의 근본적인 트레이드오프를 해결하는 데 있습니다:

• RS와 달리, CARS는 실무에서 분할 상환 효율적(amortized-efficient)이므로 많은 다양한 샘플이 필요한 작업에 적용 가능합니다.
• GCD 및 기타 근사 방법들과 달리, CARS는 진정한 LM 분포를 보존하여 다운스트림 성능(예: 퍼징 커버리지, 화학적 다양성, SQL 실행 정확도)이 분포적 왜곡으로 인해 저하되지 않도록 보장합니다.

저자들은 CARS가 접두사 체크가 가능하고 가지치기에 매우 유익한(예: 문맥 자유 문법) 제약 조건이 있을 때 가장 효과적이라고 언급합니다. 유효하지 않은 입력 공간이 공유 접두사 없이 많은 독립적인 저확률 하위 공간으로 구성된 시나리오에서는 ARS 대비 이점이 완만할 수 있으며, 근사 방법이 여전히 실용적인 대안이 될 수 있습니다. 그러나 대부분의 구조화된 생성 작업에 대해, CARS는 원칙적이고 정확하며 효율적인 솔루션을 제공합니다.