💬 NLP

Mitigating Bias in Locally Constrained Decoding via Tractable Proposals

본 논문은 텐서화된 유한 오토마타와 회로 곱셈을 통해 다루기 쉬운 전역적 제약 프로포절을 구축함으로써 국소적으로 제약된 디코딩에서의 편향을 완화하는 일반적인 접근 방식을 제안하며, 이를 통해 함수 호출(function calling) 및 SQL 생성과 같은 태스크에서 더 적은 입자(particle)를 사용하여 타겟 분포로 더 빠르게 수렴하는 효율적인 순차 몬테카를로 샘플링을 가능하게 한다.

원저자: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

게시일 2026-06-02

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Meihua Dang, Linxin Song, Honghua Zhang, Jieyu Zhao, Guy Van den Broeck, Stefano Ermon

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 매우 창의적이지만 약간은 무질서한 이야기꾼(대규모 언어 모델, LLM)에게 JSON 코드 형식이나 특정 SQL 데이터베이스 쿼리처럼 매우 엄격한 규칙을 따르는 이야기를 쓰도록 가르치려 한다고 상상해 보세요.

문제는 이 이야기꾼이 곁가지로 새는 것을 좋아한다는 점입니다. 단순히 "규칙을 어기지 마"라고만 말하면, 처음에는 괜찮아 보이지만 결국에는 제대로 끝맺음을 할 수 없는 문장을 시작할 수도 있습니다.

다음은 이 문제를 해결하는 방법을 간단한 비유를 들어 설명한 논문의 내용입니다.

1. 옛날 방식: "근시안적인" 가이드 (LCD)

이야기꾼이 미로 속을 걷고 있다고 상상해 보세요. 기존 방식(Locally Constrained Decoding 또는 LCD)은 바로 다음 단계만을 바라보는 가이드와 같습니다.

작동 방식: 다음 단계가 벽에 부딪힐 것 같아 보이면 가이드가 이를 차단합니다.
결함: 이 가이드는 "근시안적"입니다. 가이드는 당장 다음 단계는 안전해 보이는 경로를 허용할 수 있지만, 이는 세 단계 뒤에 막다른 길로 이어질 수 있습니다. 이야기꾼은 잘 가고 있다고 생각하며 계속 걷지만, 결국 마지막에 이르러서야 정해진 단어 제한 내에 이야기를 끝낼 수 없다는 사실을 깨닫게 됩니다. 그러면 이야기를 처음부터 다시 쓰거나 망가진 이야기를 만들어내야 합니다.

2. 새로운 방식: "전체 지도" (GCD)

저자들은 **Globally Constrained Decoding (GCD)**라는 새로운 방식을 제안합니다.

비유: 이 가이드는 단순히 다음 단계를 보는 것이 아니라, 미로 전체의 완전한 지도를 가지고 있으며 출구까지 남은 단계가 정확히 몇 단계인지 알고 있습니다.
작동 방식: 이야기꾼이 발을 내딛기 전에 가이드는 확인합니다: "이 길로 가면, 남은 단계 안에 실제로 출구에 도달할 수 있는가?"
결과: 만약 대답이 "아니오"라면, 가이드는 즉시 그 경로를 차단합니다. 이는 당신이 어떤 경로를 선택하더라도, 당신이 항상 유효한 결말에 도달할 수 있음을 보장합니다. 마치 목적지에 제시간에 도착할 수 있는 경로만을 보여주는 GPS를 가진 것과 같습니다.

3. "스마트한" 지도: 확률 추가 (P-GCD)

"전체 지도"(GCD)는 막다른 길을 피하는 데는 훌륭하지만, 모든 유효한 경로를 동일하게 취급합니다. 이 방식은 이야기꾼이 어떤 경로를 선호하는지, 혹은 어떤 경로가 더 좋은 이야기일 가능성이 높은지는 알지 못합니다.

비유: 이야기꾼에게는 자신만의 선호하는 걷는 방식이 있습니다. 기본적인 지도는 단순히 "이 경로는 유효하다"라고 말할 뿐입니다. 새로운 **Probabilistic GCD (P-GCD)**는 "이 경로는 유효하며, 또한 이야기꾼이 가장 좋아할 만한 경로이다"라고 말합니다.
작동 방식: 저자들은 "전체 지도"(규칙)와 "메모리 모델"(이야기꾼의 뇌를 단순화한 모델)을 결합합니다. 이 둘을 서로 곱합니다.
결과: 이제 가이드는 단순히 나쁜 경로를 차단하는 것에 그치지 않고, 유효하면서도 품질이 높은 경로로 이야기꾼을 부드럽게 유도합니다. 이는 스토리텔링 과정을 훨씬 더 효율적으로 만듭니다.

4. "입자" 경주 (SMC)

이 방법들을 테스트하기 위해 연구자들은 **Sequential Monte Carlo (SMC)**라는 기법을 사용합니다.

비유: 안개 낀 숲속에서 최적의 경로를 찾으려고 한다고 상상해 보세요. 한 명의 사람을 보내는 대신, 100개의 "입자"(탐험가) 무리를 보냅니다.
옛날 방식: 근시안적인 가이드와 함께라면, 많은 탐험가가 길을 잃거나 막다른 길에 부딪히기 때문에 수천 명의 탐험가를 보내야 합니다.
새로운 방식: "전체 지도"와 "스마트 지도"가 있으면 탐험가들이 올바른 궤도를 유지합니다. 가이드가 나쁜 옵션들을 조기에 걸러내는 능력이 훨씬 뛰어나기 때문에, 완벽한 경로를 찾는 데 훨씬 적은 수의 탐험가만 필요합니다.

5. "형태 변환" 기술 (Tensorization)

이 논문의 기술적 돌파구 중 하나는 "지도"를 다루는 방식입니다.

문제: 복잡한 규칙(예: JSON 스키마)은 수백만 개의 경로를 가진 지도를 만들 수 있습니다. 보통 컴퓨터는 표준 프로세서로 이러한 지도를 그리려 할 때 과부하가 걸립니다.
해결책: 저자들은 이러한 복잡한 지도를 현대적인 그래픽 카드(GPU)에 완벽하게 들어맞는 **수학적 블록(텐서)**으로 변환했습니다.
비유: 이는 거대하고 지저 व्यवस्थित한 종이 지도 더미를 가져와서 슈퍼컴퓨터가 즉각적으로 읽을 수 있는 컴팩트하고 고속인 디지털 칩으로 접는 것과 같습니다. 이를 통해 매우 복잡한 규칙에 대해서도 "전체 지도"를 눈 깜짝할 사이에 계산할 수 있습니다.

결과 요약

연구진은 이 방법들을 세 가지 실제 작업에 테스트했습니다:

함수 호출 (Function Calling): AI가 컴퓨터 함수를 호출할 때 올바른 형식(예: JSON)을 갖추도록 하는 것.
키워드 생성 (Keyword Generation): 이야기에 특정 단어들이 반드시 포함되도록 하는 것.
SQL 생성 (SQL Generation): 구문론적으로 올바른 데이터베이스 쿼리를 작성하는 것.

결론:

신뢰성: 새로운 방식은 단어 제한 내에서 이야기가 올바르게 끝나도록 보장하는 반면, 기존 방식은 결승선에서 자주 실패했습니다.
효율성: 동일한 품질의 결과를 얻기 위해, 새로운 방식은 기존 방식보다 **현저히 적은 수의 "탐험가"(입자)**를 필요로 했습니다.
속ness: "스마트 지도"(P-GCD)는 계산량이 조금 더 많지만 여 still 실용적인 수준으로 빠르며, "전체 지도"(GCD)는 기존 방식만큼이나 빠릅니다.

요약하자면, 이 논문은 AI에게 "전체 지도"와 "스마트한 유도"를 제공하여, 길을 잃거나 시간을 낭비하거나 망가진 코드를 생성하지 않고도 엄격한 규칙을 따를 수 있게 해줍니다.

기술 요약: 가측 제안(Tractable Proposals)을 통한 국소적 제약 디코딩의 편향 완화

문제 정의

대규모 언어 모델(LLM)은 JSON 스키마, 유효한 SQL 쿼리 또는 특정 함수 호출 형식과 같은 논리적 또는 구조적 제약을 엄격하게 준수하는 출력을 생성하는 데 종종 실패합니다. 지시어 튜닝(Instruction tuning)과 선호도 최적화(Preference optimization)가 일반적인 정렬(Alignment)을 개선했지만, "강한(hard)" 제약을 강제하는 데에는 여전히 신뢰할 수 없습니다.

기존 방식은 두 가지 주요 한계점에 직면해 있습니다:

거절 샘플링(Rejection Sampling): 편향은 없으나, 복잡한 제약 조건에 대해서는 수용률이 매우 낮아 계산적으로 비실용적입니다.
국소적 제약 디코딩(Locally Constrained Decoding, LCD): 이 표준적인 접근 방식은 각 단계에서 제약을 즉각적으로 위반하는 토큰을 마스킹합니다. 그러나 이는 두 가지 결정적인 결함을 가집니다:
- 편향(Bias): 미래의 유효성을 고려하지 않고 현재 시점에서 미시적으로 토큰을 마스킹함으로써 모델의 기저 분포를 왜곡하며, 이는 샘플링 편향으로 이어집니다.
- 종료 보장 부재(No Termination Guarantee): LCD는 국소적 유효성만을 보장합니다. 시퀀스는 국소적으로는 유효할 수 있으나(예: 닫히지 않은 JSON 중괄호), 고정된 토큰 예산 $n$ 내에 제약을 만족하지 못할 수 있습니다.

이 문제를 해결하기 위해, 제약된 분포 $p_{lm}(\cdot \mid C)$ 로부터 샘플링하기 위한 SMC(Sequential Monte Carlo) 프레임워크가 제안되었으며, 여기서 LCD를 제안 분포(Proposal distribution)로 사용하고 가중치를 재조정하여 타겟 분포로 수렴하도록 합니다. 그러나 SMC의 수렴 속도는 제안의 품질에 의해 병목 현상이 발생합니다. LCD는 미래의 유효한 완성을 위한 확률적 정보를 결여하고 있고 유한한 예산 내에서의 제약 만족을 보장하지 못하기 때문에 약한 제안(weak proposal)입니다.

방법론

저자들은 제약된 분포 $p_{lm}(\cdot \mid C)$ 로부터 가측 제안(Tractable proposals)과 잠재 함수(Potential functions)를 구축하기 위한 일반적인 접근 방식을 제안합니다. 핵심 혁신은 제약을 유한 오토마타(Finite Automata)로 표현하고, 효율적인 GPU 실행을 위해 텐서 연산을 활용하는 것입니다.

1. 전역적 제약 디코딩 (Globally Constrained Decoding, GCD)

GCD는 모든 생성된 토큰이 남은 토큰 예산 $n$ 내에서 유효한 완성을 이끌어낼 수 있도록 보장함으로써 LCD를 개선합니다.

텐서화된 유한 오토마타(Tensorized Finite Automata): 오토마타(FA)로 인코딩된 제약(특히 NFA 및 DFA)은 텐서 표현(전이 행렬 $T_{out}, T_{in}$ 및 방출 행렬 $B_f$ )으로 컴파일됩니다. 이를 통해 GPU 상에서 효율적인 실행이 가능합니다.
전방-후방 추론(Forward-Backward Inference):
- 전방 과정(Forward Process): 접두사 $x_{1:t-1}$ 를 관찰한 후 도달 가능한 FA 상태 집합을 계산합니다.
- 후방 과정(Backward Process): 특정 상태가 정확히 $n-t$ 단계 내에 수락 상태(Accepting state)에 도달할 수 있는지 여부를 계산합니다.
전역 마스킹(Global Masking): 토큰은 남은 예산 내에서 유효한 지속(Continuation)을 허용하는 상태로 이어지는 경우에만 허용됩니다. 이는 길이 $n$ 으로 생성된 모든 시퀀스가 제약 $C$ 를 만족함을 보장합니다.

2. 확률적 전역 제약 디코딩 (Probabilistic GCD, P-GCD)

GCD는 제약 만족을 보장하지만, 그 마스크는 이진적(유효/무효)이며 LLM 하에서의 유효한 완성 가능성을 무시합니다. P-GCD는 확률적 정보를 통합하여 이를 해결합니다.

HMM 증류(HMM Distillation): LLM의 분포는 선행 연구(Zhang et al., 2023)를 따라 은닉 마르코프 모델(HMM)로 근사됩니다.
회로 곱셈(Circuit Multiplication): 텐서화된 FA(에지 위의 unnormalized HMM으로 간주됨)를 증류된 HMM과 함께 회로 곱셈 알고리즘을 사용하여 곱합니다. 이는 FA와 HMM의 공유된 대수적 구조를 활용합니다.
곱 분포(Product Distribution): 결과물인 곱 분포 $p_{prod}$ 는 FA의 엄격한 논리적 제약과 LLM의 확률적 선호도를 모두 포착합니다.
제안 및 잠재력(Proposal and Potential):
- 제안( $q_{pgcd}$ ): $p_{prod}$ 로부터 도출된 제약된 다음 토큰 확률을 사용하여 각 단계에서 LM 분포의 가중치를 재조정합니다.
- 잠재력( $\phi_{pgcd}$ ): SMC에서 입자(Particles)의 가중치를 LM의 접두사 확률과 HMM의 제약 만족 예측값의 곱으로 가중 처리합니다.

3. 효율적인 구현

저자들은 거대한 크로네커 곱(Kronecker-product) 행렬을 명시적으로 생성하지 않기 위해 텐서 네트워크 연산(특히 Kronecker-vec 항등식)을 활용합니다. 이는 전이 단계의 계산 비용을 $O((HE)^2)$ 에서 $O(H^2E + HE^2)$ 로 줄여( $H$ 는 HMM 은닉 크기, $E$ 는 FA 에지 수), 효율적인 자기회귀 생성(Autoregressive generation)을 가능하게 합니다.

주요 기여

GCD 및 P-GCD 프레임워크: 토큰 예산 내에서 제약 만족을 보장하며, SMC를 위한 가측 제안 및 잠재력을 제공하는 GCD와 P-GCD를 도입했습니다.
GPU 상의 텐서화된 오토마타: Outlines나 XGrammar와 같은 기존 프레임워크의 CPU 중심적 한계를 극복하고, 효율적인 GPU 네이티브 추론을 위해 유한 오토마타(NFA 포함)를 텐서화한 첫 번째 제안입니다.
NFA 지원: 복잡한 제약(예: 변수 매개변수가 있는 함수 호출)의 경우 NFA가 DFA보다 기하급 filet하게 더 간결할 수 있음을 입증했습니다. 이는 DFA 구축이 메모리 오버플로우를 유발할 수 있는 실제 에이전트 애플리케이션에 대한 확장성을 보장합니다.
SMC와의 통합: (P-)GCD가 LCD 기반 제안보다 SMC 수렴을 크게 가속화하여, 타겟 분포에 도달하기 위해 훨씬 적은 수의 입자를 필요로 함을 보여주었습니다.

실험 결과

저자들은 세 가지 벤치마크인 xLAM(함수 호출), CommonGen(키워드 기반 생성), Spider(Text-to-SQL)에서 (P-)GCD를 평가했습니다.

함수 호출 (xLAM):
- (P-)GCD는 동일한 입자 수에서 LCD보다 실질적으로 높은 정확도를 달성했습니다.
- P-GCD는 GCD보다 지면 샘플링(Rejection sampling)의 실제 분포에 더 빠르게 수렴하였으며, 이는 확률적 정보의 이점을 강조합니다.
- 제약 만족도: GCD와 P-GCD는 모든 입자 예산에서 100% 제약 만족도를 달성한 반면, LCD는 중간 정도의 예산(예: JSON의 경우 ~95%)에서도 제약 만족에 실패했습니다.
- 효율성: LCD와 GCD는 완만한 오버헤드(1.08× 및 1.10× 느려짐)를 보였습니다. P-GCD는 HMM 계산으로 인해 더 느렸지만(3.11× ~ 10.2×), 여로 실행 가능한 수준이었습니다.
키워드 생성 (CommonGen): P-GCD를 제안과 잠재력 모두로 사용했을 때, LCD에 비해 BLEU 점수와 수렴 속도가 크게 향면되었습니다.
Text-to-SQL (Spider): GCD와 P-GCD는 다양한 입자 예산에 걸쳐 LCD보다 실행 정확도를 개선했으며, 특히 중간 정도의 예산에서 두드러졌습니다.
NFA vs. DFA: 복잡한 스키마(예: 가변 길이 함수 매개변수)의 경우 NFA는 크기가 선형적으로 증가하는 반면 DFA는 기하급수적으로 증가함을 실험으로 확인했습니다. Spider SQL 문법의 경우, DFA 구축은 토큰 수준에서 OOM(Out-of-Memory) 오류를 일으켰으나, NFA는 실행 가능한 상태(~32k 상태)를 유지했습니다.

의의 및 주장

본 논문은 국소적 제약 디코딩이 상당한 샘플링 편향을 유발하며 유한한 토큰 예산 내에서 제약 만족을 보장하지 못한다고 주장합니다. (P-)GCD를 제안함으로써 저자들은 다음과 같은 솔루션을 제공합니다:

유효성 보장: 생성된 모든 시퀀스(길이 $n$ )가 제약을 만족하도록 보장하여 LCD의 실패 사례를 제거합니다.
편향 감소: 확률적 정보(P-GCD를 통해)와 전역적 탐색(Global lookahead)을 통합함으로써, 제안 분포가 타겟 조건부 분포에 더 가깝게 근사하도록 합니다.
효율성 개선: SMC 프레임워크 내에서 (P-)GCD는 LCD 기반 접근 방식보다 훨씬 적은 수의 입자를 사용하여 타겟 분포로 수렴하며, 이를 통해 고품질 제약 생성의 계산 비용을 줄입니다.

이 연구는 논리적 제약(오토마타를 통해)과 확률적 모델링(HMM을 통해)을 GPU 효율적인 방식으로 결합함으로써, 함수 호출 및 코드 생성과 같이 엄격한 구조적 준수가 필요한 애플리케이션에서 신뢰할 수 있는 제약 만족 생성을 위한 기초적인 단계로서 자리매김하고 있습니다.