Adaptive Stopping for Multi-Turn LLM Reasoning

논문 제목: 적응적 정지로 다중 턴 LLM 추론을 위한 MiCP (Multi-Turn Language Models with Conformal Prediction)

1. 문제 제기 (Problem Statement)

최근 대형 언어 모델 (LLM) 은 복잡한 질문에 답하기 위해 단일 응답 생성을 넘어 다중 턴 (Multi-turn) 추론 및 상호작용 (예: 적응형 검색 증강 생성 (Adaptive RAG), ReAct 에이전트) 에 의존하고 있습니다. 이러한 방식은 정보를 반복적으로 검색하고 추론하여 정확도를 높이지만, **"언제 멈춰야 하는가 (When to stop?)"**라는 새로운 도전을 제기합니다.

• 기존 접근법의 한계: 현재는 임계값 (confidence threshold) 이나 고정된 턴 수 (fixed turn budget) 와 같은 휴리스틱 규칙에 의존합니다. 이는 형식적인 보장 (formal guarantee) 을 제공하지 못합니다.
  • 너무 일찍 멈추면: 충분한 정보를 수집하지 못해 잘못된 답변을 내놓을 수 있습니다.
  • 너무 늦게 멈추면: 불필요한 검색과 추론으로 인해 지연 (latency) 과 비용이 증가하며, 오히려 오류가 누적될 수 있습니다.
• 표준 Conformal Prediction (CP) 의 부재: 기존 CP 는 단일 모델 출력에 적용되어 최종 예측 집합이 정답을 포함할 확률을 보장하지만, 턴 수에 따라 종료 시점이 달라지는 다중 턴 파이프라인에는 적용되지 않았습니다. 각 턴마다 독립적으로 CP 를 적용하면 전체적인 커버리지 보장이 깨지거나 샘플링 비용이 기하급수적으로 증가하는 문제가 발생합니다.

2. 방법론 (Methodology: MiCP)

저자들은 **MiCP (Multi-Turn Language Models with Conformal Prediction)**라는 새로운 프레임워크를 제안했습니다. 이는 다중 턴 LLM 추론을 위한 최초의 CP 프레임워크로, 턴별 신뢰도 추정, 적응형 조기 종료, 최종 예측 집합 구성의 세 가지 핵심 요소로 구성됩니다.

• 단계 1: 검색 필터링 (Retrieval Filtering)

  • 각 턴에서 검색된 문서 중 관련성이 낮은 문서를 필터링하여 컨텍스트 오염을 방지합니다.
  • 금방 (Gold) 문서가 최소한 $1-\alpha_{ret}$ 비율로 유지되도록, 모든 턴에서 검색된 문서의 최대 관련성 점수를 기반으로 CP 임계값을 보정합니다.

• 단계 2: 오류 예산 할당 및 순차적 조기 종료 (Error Budget Allocation & Early Stopping)

  • 핵심 아이디어: 전체 오류 예산 ($\alpha$) 을 모든 턴에 균등하게 나누는 것이 아니라, 질문의 난이도와 턴의 단계에 따라 오류 예산을 동적으로 할당합니다.
  • 쉬운 질문은 초기 턴에서 빠르게 종료하고, 어려운 질문은 후속 턴에 더 많은 오류 예산을 남겨두어 추가 추론을 허용합니다.
  • 불확실성 신호: LLM 이 샘플링한 답변 분포의 **정규화 엔트로피 (Normalized Entropy, NE)**를 사용하여 불확실성을 측정합니다.
  • 종료 결정: 각 턴 $t$에서 계산된 NE 점수가 해당 턴에 할당된 CP 임계값 ($\hat{q}_t$) 을 초과하면 모델을 종료합니다.
  • 수식적 보장: 전체 과정에 걸쳐 정답이 포함되거나, 신뢰할 수 없는 경우 "답변 불가 (Can't Answer)"를 선택할 때 전체 커버리지 $1-\alpha$를 보장하도록 설계되었습니다.

• 단계 3: 최종 예측 집합 구성

  • 조기 종료 시점까지 수집된 모든 고신뢰도 답변 클러스터를 포함합니다.
  • 모든 턴을 소진해도 신뢰도가 낮으면 "Can't Answer" 라벨을 포함하여 커버리지 보장을 유지합니다.

• 새로운 평가 지표 (Composite Metric)

  • 커버리지 유효성과 효율성 (턴 수, 비용) 간의 균형을 평가하는 새로운 목적 함수 ($L$) 를 도입했습니다. 이는 정답을 더 적은 턴으로 맞춘 경우를 보상하고, 불필요한 추론이나 잘못된 추론을 패널티로 부과합니다.

3. 주요 기여 (Key Contributions)

1. MiCP 프레임워크 제안: 다중 턴 LLM 추론에 적용 가능한 최초의 CP 프레임워크로, 형식적인 커버리지 보장을 유지하면서 적응형 조기 종료를 가능하게 합니다.
2. 다단계 오류 할당 전략: 전체 오류 예산을 턴별로 분배하여, 모델이 각 단계에서 종료 여부를 결정하되 전체적인 커버리지 보장을 해치지 않도록 합니다.
3. 새로운 평가 지표: 신뢰성 (Coverage Validity) 과 효율성 (Efficiency) 을 동시에 측정하는 지표를 도입하여 다중 턴 시스템의 성능을 종합적으로 평가합니다.
4. 광범위한 실험 검증: 적응형 RAG 와 ReAct 에이전트 모두에서 단일 홉 및 멀티 홉 질문 답변 벤치마크를 통해 유효성을 입증했습니다.

4. 실험 결과 (Results)

저자들은 Natural Questions (NQ), TriviaQA, HotpotQA, MuSiQue, 2WikiMultiHopQA 등 5 가지 벤치마크와 Gemma-2-9B, Qwen3.5-9B, GPT-4o-mini 등 3 가지 LLM 을 사용하여 실험을 수행했습니다.

• 커버리지 보장 (RQ1): 검색 단계와 최종 예측 집합 모두에서 목표한 $1-\alpha$ 커버리지 보장을 성공적으로 달성했습니다. (그림 2, 3 참조)
• 효율성 향상 (RQ2):
  • 턴 수 감소: 기존 고정 턴 방식 (No Early Stop) 대비 평균 턴 수를 크게 줄였습니다 (예: HotpotQA 에서 약 2.56 턴 vs 3.00 턴).
  • 예측 집합 크기 축소: 불필요한 후기 턴의 노이즈가 포함된 답변을 제거하여 예측 집합의 크기를 줄였습니다.
  • 비용 절감: 턴 수 감소로 인해 추론 비용과 지연 시간이 감소했습니다.
• 그리드 서치 최적화 (RQ3): 제안된 목적 함수에 대한 그리드 서치를 통해 오류 예산 할당을 최적화함으로써, 단순한 평균 턴 수 최적화보다 더 합리적인 조기 종료 결정을 내리는 것을 확인했습니다.

5. 의의 및 결론 (Significance & Conclusion)

이 연구는 **고위험 분야 (금융, 의료 등)**에서 LLM 의 신뢰성을 보장하면서도 비용을 절감할 수 있는 실용적인 솔루션을 제시합니다.

• 이론적 기여: 다중 턴 추론이라는 동적 환경에 Conformal Prediction 을 적용하는 이론적 기반을 마련했습니다.
• 실용적 가치: 불필요한 검색과 추론을 줄여 LLM 에이전트의 운영 비용을 낮추면서도, "정답을 놓치지 않음 (Coverage Guarantee)"과 "불확실한 경우 거절 (Abstention)"이라는 두 가지 목표를 동시에 달성합니다.
• 확장성: 적응형 RAG 뿐만 아니라 ReAct 와 같은 다양한 다중 턴 에이전트 아키텍처에 적용 가능한 범용적인 프레임워크입니다.

결론적으로 MiCP 는 LLM 이 "얼마나 많은 정보를 수집할지"와 "언제 멈출지"에 대한 불확실성을 수학적으로 관리하여, 효율성과 신뢰성을 동시에 극대화하는 새로운 패러다임을 제시합니다.