Suffix-Constrained Greedy Search Algorithms for Causal Language Models

이 논문은 최종 답변이 엄격한 템플릿을 따르도록 강제하여 파싱을 용이하게 하고 정확도를 높이는 '접미사 제약 탐욕 검색 (suffix-constrained greedy search)' 알고리즘을 제안합니다.

핵심

이 논문은 **거대 언어 모델 **(LLM)에 대한 연구입니다.

한마디로 요약하자면: "AI 가 복잡한 추론을 하되, 마지막 답만은 우리가 정한 규칙에 딱 맞게 나오도록 장난감을 만들어낸 방법"입니다.

이 내용을 일상적인 비유로 쉽게 설명해 드릴게요.

---

1. 문제: "AI 는 너무 말이 많아요!"

우리가 AI 에게 수학 문제를 풀게 하면, AI 는 보통 이런 식으로 답변합니다.

"자, 이 문제를 풀어보죠. 6 개의 감자로 36 개의 감자튀김이 나온다면... (중략) ...그래서 정답은 576 입니다. 아, 그리고 감자튀김은 정말 맛있죠. 다음엔..."

여기서 문제가 생깁니다.
우리가 컴퓨터 프로그램으로 이 답을 자동으로 받아쓰려고 할 때, AI 가 "정답은 576 입니다"라고 말한 뒤에 또 다른 이야기를 덧붙이거나, 아예 말을 끝내지 못하고 "감자튀김은..."이라고 계속 떠들다가 시간이 다 되어 멈추면, 컴퓨터는 **"정답이 뭐지?"**하고 헤매게 됩니다.

기존의 방법들은 AI 에게 "답만 말해"라고 강요하면, AI 가 추론하는 과정 (이유 설명) 을 생략해서 오히려 틀린 답을 내놓거나, 반대로 "답만 말해"라는 지시를 무시하고 장황하게 늘어놓는 문제가 있었습니다.

2. 해결책: "마지막 문장만 규칙대로" (Suffix-Constrained Generation)

이 논문은 아주 똑똑한 해결책을 제시합니다.
"AI 가 자유롭게 생각할 수는 있지만, 마지막에 '정답'을 쓸 때는 우리가 정한 딱딱한 규칙을 지켜야 한다고 약속하는 것"입니다.

이를 **'접미사 제약 **(Suffix-Constrained)이라고 부릅니다.

🍳 요리사 비유

이 상황을 **요리사 **(AI)와 **요리사 **(AI)로 비유해 볼까요?

• 기존 방식: 요리사에게 "요리해 줘"라고 하면, 그는 요리를 하다가 마지막에 "이제 접시에 담을게"라고 말하고는, 갑자기 "아, 그리고 오늘 날씨가 좋네요"라고 말하며 접시를 넘겨줍니다. 우리는 그 접시에서 정작 필요한 요리를 찾기 위해 헤매야 합니다.
• 이 논문의 방식: 요리사에게 "네가 원하는 대로 요리를 하되, **마지막 한 접시만은 내가 준 그릇 **(규칙)이라고 말합니다.
  • 요리사는 자유롭게 재료를 섞고 맛을 볼 수 있습니다 (자유로운 추론).
  • 하지만 마지막에 요리를 그릇에 담을 때는, 그 그릇의 모양 (규칙) 에 맞춰야만 합니다.
  • 만약 요리사가 그릇에 담지 않고 다른 걸 말하려 하면, 시스템이 "아니, 그릇에 담아!"라고 부드럽게 하지만 확실하게 잡아줍니다.

3. 어떻게 작동할까요? (두 개의 가설을 동시에 추적)

이 논문은 AI 가 답을 낼 때 두 가지 시나리오를 동시에 상상하는 알고리즘을 개발했습니다.

1. **자유로운 생각 **(Greedy Hypothesis) AI 가 "아무 말이나" 계속하는 시나리오입니다.
2. **규칙을 지키는 생각 **(Constrained Hypothesis) AI 가 "규칙에 맞춰 답을 쓰는" 시나리오입니다.

이 두 가지를 동시에 지켜보다가, **"어? 지금 AI 가 규칙을 지키기 시작할 만한 타이밍 **(분기점)을 포착합니다.

• 만약 AI 가 규칙을 지키기 시작하면, 그 시점부터는 무조건 규칙대로만 답을 쓰게 만듭니다.
• 만약 AI 가 규칙을 지키다가 헷갈려서 엉뚱한 말을 하면, 그 시점을 '페널티'로 기록하고, 더 좋은 시나리오로 갈아타는 것입니다.

이 과정을 **포크 **(Bifurcation)라고 부릅니다. 두 갈래 길이 갈라질 때, 더 나은 길을 선택하는 것입니다.

4. 왜 이게 중요한가요?

• 정답을 100% 확실히 뽑아낼 수 있습니다: AI 가 아무리 말을 많이 해도, 마지막에 "정답: 576"이라는 규칙을 따르기만 하면, 컴퓨터는 그 부분을 딱 잘라내서 바로 사용할 수 있습니다.
• 성능이 오히려 좋아집니다: 놀랍게도, 답을 규칙에 맞춰서 내도록 강제한다고 해서 AI 의 추론 능력이 떨어지지 않습니다. 오히려 AI 가 헷갈려서 말을 멈추거나 (시간 초과), 엉뚱한 말을 덧붙이는 실수를 줄여서 정답률이 더 높아졌습니다.
• 어떤 모델에도 적용 가능: 이 방법은 AI 를 다시 훈련시킬 필요 없이, 기존에 있는 어떤 AI 모델에도 바로 적용할 수 있습니다.

5. 결론

이 논문은 "AI 에게는 자유롭게 생각하게 하되, 마지막 결과물은 우리가 원하는 형식으로 깔끔하게 정리하게 만드는 기술을 개발했습니다.

마치 유아원 선생님이 아이들에게 "자유롭게 놀아도 돼!"라고 말하지만, "놀이 끝날 때는 장난감을 제자리에 정리해야 해!"라고 가르치는 것과 같습니다. 덕분에 아이들은 창의적으로 놀면서도, 방은 항상 정리되어 있고 다음 사람이 들어오기 편해집니다.

이 기술 덕분에 AI 가 수학 문제를 풀거나 복잡한 질문을 할 때, 우리가 그 답을 자동으로 받아쓰는 일이 훨씬 쉬워지고 정확해졌습니다.

기술 요약

1. 문제 정의 (Problem)

대규모 언어 모델 (LLM) 은 추론 능력을 갖추고 있어 수학 문제 해결 및 다양한 예측 작업에 널리 사용되지만, 자유 형식 (free-form) 의 자연어 출력에서 최종 답을 자동으로 추출하는 것은 여전히 큰 과제로 남아 있습니다.

• 추출의 어려움: LLM 이 생성한 텍스트는 다양한 스타일적 마커, 긴 추론 과정, 그리고 답의 다양한 표현 방식을 포함할 수 있습니다. 이로 인해 정규 표현 (regex) 등을 이용한 패턴 매칭 기반의 답 추출은 신뢰성이 낮아집니다.
• 기존 방법의 한계:
  • 프롬프트 지시: 프롬프트에 형식 지시를 포함하더라도 모델이 지시를 무시하거나, 답을 생성한 후 추가 설명을 덧붙여 추출을 실패하게 만들 수 있습니다.
  • 평가자 LLM (Judge LLM): 더 큰 모델을 평가자로 사용하는 방식은 일관성 부족, 위치 편향, 재현성 부재 등의 문제가 있습니다.
  • 전체 제약 생성 (Full Constrained Generation): 처음부터 끝까지 문법 (Grammar) 으로 출력을 강제하는 방식은 모델의 자유로운 추론 능력을 저해하여 성능이 크게 떨어집니다.

핵심 문제: 모델이 초반에는 자유롭게 추론할 수 있게 하되, 출력의 끝부분 (Suffix) 에만 엄격한 형식 (템플릿) 을 강제하여 최종 답을 항상 파싱 가능하게 만드는 방법은 무엇인가?

---

2. 제안 방법론 (Methodology)

저자들은 이를 해결하기 위해 **Suffix-Constrained Generation (접미사 제약 생성)**을 도입하고, 이를 위한 효율적인 Greedy Search 알고리즘들을 제안합니다.

2.1. Suffix-Constrained Grammar

• 모델의 전체 출력은 V* × lang(G)로 정의됩니다. 여기서 V*는 자유로운 추론 토큰들의 시퀀스이고, lang(G)는 정해진 문법 (예: "The answer is: <답>") 을 따르는 최종 답 부분입니다.
• Proposition 1 (핵심 통찰): 단순히 전체 문법을 Suffix-Constrained Grammar로 정의하고 기존 제약 생성 알고리즘을 적용하면, 초기 단계에서 제약이 전혀 작용하지 않아 (next_G(y) = V) 모델이 원하는 형식으로 끝내지 못하게 됩니다. 즉, 기존 방식은 이 문제에 적용 불가능합니다.

2.2. 제안 알고리즘들

저자들은 Beam Size 를 최대 2 로 제한하여 계산 비용을 최소화하는 여러 Greedy Search 변형 알고리즘을 제안합니다.

1. Greedy Pipeline (간단한 접근법):

   • 먼저 표준 Greedy Search 로 자유 추론을 수행합니다.
   • 생성이 끝난 후, 마지막 토큰을 제거하고 새로운 프롬프트로 변환하여 제약 문법 하에서 다시 생성을 시작합니다.
   • 구현이 간단하지만, 첫 번째 단계에서 생성 예산 (Budget) 을 초과하면 실패할 수 있습니다.

2. Constrained Hypothesis Beam Search (이중 Hypothesis):

   • Greedy Hypothesis (y): 자유 추론을 계속하는 가설.
   • Constrained Hypothesis (r ⊙ a): 특정 시점 (r) 에서부터 제약된 답 (a) 을 생성하기 시작하는 가설.
   • 두 가설의 점수를 비교하여, 제약 가설의 점수가 더 낮으면 Greedy 가설을 기반으로 새로운 제약 가설로 교체합니다.
   • 단점: 자유 추론 가설이 훨씬 높은 확률을 가지므로, 제약 가설이 자주 교체되어 생성 예산을 다 채우기 전에 종료되지 못하거나 (Looping), 유효한 답을 생성하지 못할 수 있습니다.

3. Bifurcation Penalty (분기 패널티) - 제안된 핵심 알고리즘:

   • 원리: 확률 기반의 점수 비교 대신, **자유 추론 토큰과 제약 시작 토큰 사이의 확률 차이 (Penalty)**를 기준으로 가설 교체를 결정합니다.
   • 메커니즘:
     • 현재 Greedy 가설에서 제약 문법의 시작 토큰을 선택할 때 발생하는 확률 손실 (Penalty) 을 계산합니다.
     • 이 패널티가 현재 저장된 제약 가설의 패널티보다 작으면, 해당 지점에서 새로운 제약 가설을 시작합니다.
     • Last Hypothesis Selection: 알고리즘 종료 시, 가장 낮은 패널티를 가진 가설을 선택하는 대신, 마지막으로 생성된 유효한 제약 가설을 선택합니다. 이는 모델이 예산을 초과하기 전에 유효한 답을 생성할 확률을 높입니다.
   • 장점: 모델이 자유 추론을 하다가도, 답을 생성할 확률이 충분히 높아지는 시점에 자동으로 형식 제어로 전환되도록 유도하며, 생성 예산 내에서 유효한 답을 보장합니다.

---

3. 주요 기여 (Key Contributions)

1. Suffix-Constrained Generation 개념 도입: LLM 의 추론 과정은 자유롭게 하되, 최종 답만 엄격하게 파싱 가능한 형식으로 강제하는 새로운 생성 패러다임을 정립했습니다.
2. 이론적 한계 증명: 기존 제약 생성 방법론이 접미사 제약 문제에는 적용할 수 없음을 Proposition 1 을 통해 수학적으로 증명했습니다.
3. 효율적 알고리즘 개발: Beam Size 를 2 로 제한하여 계산 비용을 최소화하면서도, Bifurcation Penalty를 활용한 Greedy Search 알고리즘을 제안했습니다.
4. 실험적 검증: OLMo 2 모델 (1B, 13B, Pre-trained, Instruction-tuned) 을 사용하여 수학 (GSM8K, MATH500, SVAMP) 및 객관식 질문 (ARC, CommonsenseQA) 데이터셋에서 성능을 검증했습니다.

---

4. 실험 결과 (Results)

• 성능 향상: 제안된 Bifurcation Penalty (Last Hypothesis Selection) 알고리즘은 거의 모든 작업과 모델에서 Unconstrained Greedy Search보다 우수한 성능을 보였습니다.
  • 특히 Instruction-tuned (IT) 모델에서 답 추출 실패 (형식 오류, 추가 설명 등) 를 해결하여 정확도를 높였습니다.
  • Pre-trained (PT) 모델의 경우, 무제한 생성 시 예산 초과로 인한 반복 생성 (Looping) 문제를 해결하여 유효한 답을 추출할 수 있게 했습니다.
• 비교 분석:
  • Greedy Pipeline: 좋은 성능을 보이지만, 첫 단계에서 예산을 초과할 경우 실패합니다.
  • Constrained Only (추론 생략): 객관식 (MCQ) 작업에서는 성능이 좋았으나, 복잡한 추론이 필요한 수학 작업에서는 성능이 급격히 저하되었습니다. 이는 추론 과정이 답의 정확성에 필수적임을 시사합니다.
  • Minimum Penalty Selection: 짧은 출력을 선호하여 수학 문제에서 중간 결과만 도출하거나 답을 건너뛰는 경향이 있어 성능이 낮았습니다.
• 결론: 제안된 방법은 추론의 정확성을 유지하면서 **답 추출의 확실성 (Deterministic Extraction)**을 동시에 달성했습니다.

---

5. 의의 및 결론 (Significance)

• 신뢰성 있는 LLM 평가: LLM 의 출력을 자동으로 평가할 때, 복잡한 파싱 오류나 실패를 없애고 결정론적 (Deterministic) 으로 정답을 추출할 수 있는 기반을 마련했습니다.
• 시스템 통합 용이성: 복잡한 파이프라인이나 시스템에서 LLM 을 사용할 때, 출력 형식 불일치로 인한 오류를 방지하여 안정성을 높입니다.
• 저비용 고효율: Beam Search 의 복잡도를 높이지 않고 (Beam Size 2), Greedy Search 기반의 경량화된 알고리즘을 제안하여 실제 적용 비용을 낮췄습니다.
• 모델 능력 보완: 지시 따르기 (Instruction-following) 능력이 약한 모델이나 Pre-trained 모델에서도 형식 제어를 통해 안정적인 성능을 끌어올릴 수 있음을 보여주었습니다.

이 논문은 LLM 의 자유로운 추론 능력과 기계적 파싱의 엄격함을 조화시키는 새로운 접근법을 제시하여, LLM 을 실제 응용 시스템에 통합하는 데 중요한 기여를 합니다.