기술 요약: LLM 기반 코드 생성의 불확실성 정량화를 위한 RISCOSET

문제 정의

대형 언어 모델 (LLM) 은 코드 생성에 increasingly 사용되고 있지만, 할루시네이션과 유해하거나 편향된 출력 생성으로 인해 고위험 애플리케이션에서의 배포가 제한됩니다. 컨포멀 예측 (Conformal Prediction, CP) 은 분포-free 보장을 갖춘 불확실성 정량화를 위한 프레임워크를 제공하지만, 이를 코드와 같은 구조화된 생성 작업에 적용하는 것은 어렵습니다.

기존 접근 방식인 코드를 위한 PAC(Probably Approximately Correct) 예측 세트 (Khakhar et al., 2023) 는 두 가지 중요한 한계에 직면해 있습니다:

1. 단조성 제약 (Monotonicity Constraints): 이들은 위험과 예측 세트 크기 간의 강한 단조성 가정에 의존합니다. 이는 허용 가능한 부분 프로그램의 공간을 제한하여, 종종 너무 많은 코드 노드를 제거하는 비최적 해를 초래합니다.
2. 단일 레이블 가정 (Single-Label Assumption): 이들은 단일 레이블 분류를 위해 설계되었습니다. 그러나 코드 생성은 본질적으로 다중 레이블 문제로, 문법적으로 다른 여러 프로그램이 동일한 올바른 시맨틱을 가질 수 있습니다. 기존 방법들은 이러한 다중성을 수용하지 못해 후보 공간을 심각하게 제한합니다.

방법론: RISCOSET

저자들은 LLM 기반 코드 생성에 대한 위험 제어 예측 세트를 구축하기 위해 문제를 다중 레이블 분류 작업으로 재정의하고 Learn Then Test (LTT) 프레임워크 (Angelopoulos et al., 2025) 를 활용하는 RISCOSET을 제안합니다.

핵심 구성 요소

1. 다중 레이블 재정의 및 구조화된 위험 (Multi-Label Reframing & Structured Risk):
   단조성을 강제하는 대신, RISCOSET 은 시맨틱 정확도에 기반한 구조화된 위험 함수를 정의합니다. 주어진 입력에 대해, 향상된 레이블 집합 $\tilde{Y}$에서 적어도 하나의 올바른 프로그램을 포함하는 예측 세트 (부분 프로그램 또는 AST 서브트리로 표현됨) 를 생성하는 것이 목표입니다. 경험적 위험은 예측 세트가 올바른 프로그램 집합과 교차하지 않는 보정 인스턴스의 비율로 정의됩니다.

2. 부분 프로그램 최적화 (Optimization for Partial Programs):
   예측 세트를 생성하기 위해, 이 방법은 생성된 코드의 추상 구문 트리 (AST) 에서 노드를 제거하는 최적화 문제를 풉니다.

   • 목적: 남은 부분 프로그램의 총 불확실성 (음수 로그 확률) 이 임계값 $\lambda$를 초과하지 않도록 보장하면서 가능한 한 많은 노드를 유지합니다.
   • 제약 조건: 솔루션은 트리 연결성 (부모가 제거되면 자식도 제거되어야 함) 과 허용 가능한 서브트리 제거 수 ($t_{max}$) 의 제한을 만족해야 합니다. 핵심적으로, 이 최적화는 PAC 방법에서 발견되는 엄격한 단조성 제약을 제거하여 더 큰 실현 가능한 레이블 공간을 허용합니다.

3. 다중 가설 검정 (LTT):
   RISCOSET 은 위험을 제어하는 최적의 매개변수 $\hat{\lambda}$를 선택하기 위해 LTT 프레임워크를 사용합니다.

   • $\lambda$의 선택을 다중 가설 검정 문제로 취급합니다.
   • 후보 $\lambda$ 값 집합에 대해 경험적 구조화된 위험을 기반으로 $p$-값을 계산합니다.
   • Family-Wise Error Rate (FWER) 제어 알고리즘을 사용하여, 높은 신뢰도 ($1-\delta$) 로 위험이 사용자가 지정한 허용 오차 $\alpha$ 아래에 유지되도록 보장하는 유효한 매개변수 집합 $\Lambda_{valid}$를 식별합니다.

4. 선택적 실행 전략 (Selective Execution Strategy):
   코드 생성은 다중 레이블이므로, 보정 과정은 여러 후보 프로그램을 샘플링하고 테스트 케이스 실행을 통해 검증해야 하므로 계산 비용이 많이 듭니다. 이를 완화하기 위해 RISCOSET 은 선택적 실행 전략을 도입합니다:

   • 불확실성 점수 (예: 퍼플렉시티) 를 사용하여 테스트 실행이 필요한 샘플링된 프로그램을 결정합니다.
   • 불확실성이 낮은 프로그램은 실행 없이 올바른 것으로 수용되고, 불확실성이 높은 프로그램은 검증됩니다.
   • 이 전략은 중요도 샘플링과 Hoeffding 부등식을 사용하여 오류 상한을 추정하여, 계산 비용을 크게 줄이면서도 레이블 오류율을 제어된 경계 $\epsilon$ 내에 유지하도록 보장합니다.

주요 기여

1. RISCOSET 프레임워크: 구조화된 코드 생성에 LTT 프레임워크를 처음 적용하여, PAC 기반 접근 방식보다 약한 제약 조건을 가진 다중 레이블 문제로 예측 세트 구축을 재정의했습니다.
2. 구조화된 위험 최적화: 제한적인 단조성 가정 없이 위험 제어 보장을 만족하면서 유지된 정보를 최대화하는 부분 프로그램 (AST 서브트리) 생성을 위한 새로운 최적화 공식화입니다.
3. 효율적인 보정: 비점근적 오류 경계에 의해 지원되는 위험 제어와 레이블 검증의 계산 비용 간의 균형을 맞추는 선택적 실행 전략입니다.
4. 실증적 검증: 세 가지 LLM (Deepseek-Coder, Qwen2.5-Coder, Llama3.1) 과 세 가지 데이터셋 (HumanEval, MBPP, APPS) 에서 이 방법의 효과를 입증한 포괄적인 실험입니다.

실험 결과

저자들은 RISCOSET 을 PAC 예측 세트 접근 방식 및 탐욕적 변형 (greedy variant) 을 포함한 최첨단 베이스라인과 비교 평가했습니다.

• 노드 제거 감소: RISCOSET 은 동일한 수준의 위험 제어를 유지하면서 베이스라인에 비해 제거된 AST 노드 수를 크게 줄였습니다. 예를 들어, $\alpha=0.15$인 MBPP 데이터셋에서 이 방법은 가장 좋은 경쟁자 대비 코드 제거를 24.5% 줄였습니다.
• 커버리지 보장: 구성된 예측 세트는 일관되게 목표 경계 ($1-\alpha$) 를 초과하는 커버리지율을 달성하여 이론적 위험 제어 보장을 검증했습니다.
• 모델 확장성: 이 방법은 코드 전용 모델 (Qwen2.5-Coder) 과 범용 모델 (Llama3.1) 모두에서 잘 수행되었으며, 더 강력한 생성 모델일수록 성능이 향상됨을 보여주었습니다.
• 선택적 실행 효율성: 선택적 실행 전략은 레이블 오류율 $\epsilon=0.1$에서 약 30% 의 프로그램에 대한 실행을 피하는 등 테스트 케이스 실행이 필요한 프로그램의 비율을 성공적으로 줄이면서 목표 임계값 이상의 커버리지를 유지했습니다.

중요성 및 주장

이 논문은 구조화된 코드 생성 작업에 LTT 프레임워크를 처음 도입한 연구라고 주장합니다. 주요 중요성은 기존 PAC 기반 방법의 한계를 해결하는 데 있으며, 다음과 같습니다:

• 강한 단조성 가정의 필요성을 제거하여 후보 프로그램의 공간을 확장하고 불필요한 코드 제거를 줄입니다.
• 코드 생성의 다중 레이블 특성 (단일 작업에 대한 여러 유효한 솔루션) 을 자연스럽게 수용합니다.
• 코드와 같은 구조화된 도메인에서 실패하는 독립성 가정에 의존하지 않고 생성된 코드 세트의 정확성에 대한 엄격한 통계적 보장을 제공합니다.

저자들은 코드 생성에 초점을 맞추고 있지만, 제안된 방법은 불확실성 정량화가 중요한 다른 구조화된 예측 문제에도 적용 가능하다고 결론지었습니다. 그들은 보정 단계의 계산 오버헤드를 인정하지만, 선택적 실행 전략이 이 비용을 효과적으로 완화한다고 강조합니다.