Reducing Hallucinations in LLM-Generated Code via Semantic Triangulation

1. 문제 정의 (Problem)

LLM 은 자연어 설명을 실행 가능한 코드로 변환할 수 있지만, 생성된 프로그램에는 종종 **환각 (Hallucination)**으로 인한 버그나 취약점이 포함됩니다.

• 기존 접근법의 한계:
  • 다수결 투표 (Plurality Voting): 여러 샘플 중 가장 빈번한 답을 선택하는 방식입니다. 하지만 LLM 은 상관된 오류 (Correlated Errors) 를 일으키는 경향이 있어, 잘못된 답이 다수일 경우 이를 증폭시킵니다.
  • 생성된 테스트/명세 (Generated Tests/Specs): LLM 이 생성한 테스트 케이스나 자동화된 명세 (Hoare Triple 등) 를 검증 도구로 사용합니다. 그러나 이 '증거 (Witness)'도 동일한 LLM 이 생성했기 때문에, 잘못된 논리를 공유하여 오류를 잡아내지 못하고 오히려 잘못된 코드를 지지할 가능성이 높습니다.
  • 메타모픽 테스트 (Metamorphic Testing): 문제를 재해석하거나 변형하여 일관성을 확인하지만, LLM 이 미세한 변화에도 동일한 오류를 반복하는 경우 효과가 제한적입니다.
• 핵심 과제: LLM 이 생성한 여러 코드 샘플 중 어떤 것이 정답인지, 그리고 어떤 검증 방법 (Plausibility Witness) 이 가장 높은 신뢰도를 제공하는가를 규명하는 것입니다. 특히, 정답이 여러 개일 수 있는 '부정확 (Inexact)'한 문제나 정답 확률이 매우 낮은 문제에서의 신뢰성 확보가 어렵습니다.

2. 방법론: 의미적 삼각측량 (Methodology: Semantic Triangulation)

저자들은 LLM 의 오류를 상관관계에서 해리 (Dissociate) 시키기 위해 의미적 삼각측량 프레임워크를 제안합니다. 이는 수사관이 용의자의 진술을 서로 다른 각도에서 검증하여 거짓말을 찾아내는 원리와 유사합니다.

2.1 핵심 개념

• 해리된 문제 변환 (Dissociative Transformation): 원래 문제 $d$를 $d'$로 변환하되, $d'$를 해결하기 위해 본질적으로 다른 알고리즘이 필요하도록 설계합니다. (예: 정렬 문제 $\rightarrow$ 역정렬 문제, 출력 생성 $\rightarrow$ 입력 역추적).
• 이중 조건 (Theoretical Requirements): 변환된 문제와 원래 문제의 해를 연결하는 관계 $\phi$는 다음 두 가지 조건을 만족해야 합니다.
  1. 일대일 대응 유도 (Bijection-inducing): 원래 문제의 각 오류 클래스가 변환된 문제의 고유한 오류 클래스로 매핑되어야 합니다. 이를 통해 LLM 이 두 문제에서 우연히 동일한 오류를 낼 확률을 낮춥니다.
  2. 정확도 결합 (Correctness-coupling): 원래 문제의 정답이 변환된 문제의 정답으로 매핑되어야 합니다.

2.2 구체적 구현 (4 가지 방법)

저자들은 이 프레임워크를 구현하기 위해 4 가지 구체적인 삼각측량 방법을 개발했습니다.

1. 문제 역전 (Problem Inversion): 입력과 출력의 역할을 뒤집는 문제 (예: $f(x)=y$를 구하는 문제 $\rightarrow$ $f(x)=y$를 만족하는 $x$를 구하는 문제).
2. 부분 역전 (Partial Inversion): 인자 중 하나만 역전하여 부분 역함수를 구하는 문제.
3. 답변 열거 (Answer Enumeration): 주어진 입력에 대해 가능한 모든 정답을 나열하는 문제.
4. 문제 분해 (Problem Decomposition): 스트림 처리 문제를 요소 단위로 분해하여 검증.

이 방법들은 ENUM-SINV(열거된 답과 역함수 간의 일관성 확인) 와 같은 하이퍼속성 (Hyperproperty) 을 사용하여, 서로 다른 문제에서 생성된 솔루션이 일관된지 검증합니다.

3. 주요 기여 (Key Contributions)

1. 이론적 기반: LLM 환각을 수학적 모델로 정의하고, 의미적 삼각측량이 다수결 투표보다 정답을 찾을 확률을 이론적으로 높인다는 것을 증명했습니다. (재배열 부등식 활용)
2. 실용적 프레임워크 (just-tri-it): 위 이론을 바탕으로 한 도구 just-tri-it을 구현했습니다. 이 도구는 문제를 자동으로 변환하고, 생성된 솔루션들을 삼각측량하여 정답을 선별하거나 거절 (Abstention) 합니다.
3. 형식적 증명: Lean 을 사용하여 제안된 4 가지 삼각측량 방법이 이론적 요구사항 (일대일 대응, 정확도 결합) 을 만족함을 기계적으로 검증했습니다.
4. 부정확 문제 해결: 기존 방법들이 정답이 하나라고 가정하는 것과 달리, **여러 개의 유효한 정답이 존재하는 문제 (Inexact Problems)**에서도 일관되게 작동합니다.

4. 실험 결과 (Results)

LiveCodeBench 와 CodeElo(부정확 문제 포함) 벤치마크에서 GPT-4o, DeepSeek-V3, Gemini 2.5 Flash 등 최신 모델로 평가되었습니다.

• 신뢰도 향상: 기존 방법 (테스트 생성, 자동 명세, 다수결 등) 대비 정답을 선택할 확률이 평균 24% 증가했습니다.
• 선택/거절 (Selection-or-Abstention) 성능:
  • 정답 확률이 낮아도 (0.07 수준) 정답을 찾아내는 능력이 뛰어납니다.
  • **거절 F1 점수 (Abstention F1 Score)**가 기존 최강 베이스라인 대비 26% 더 높았습니다.
  • 신뢰할 수 없는 코드를 선택하지 않고 거절하는 능력 (Reliable Accuracy) 이 8% 향상되었습니다.
• 부정확 문제 대응: CodeElo 의 부정확 문제에서 기존 방법들은 성능이 급격히 떨어졌으나, just-tri-it은 모든 모델에서 일관된 높은 성능을 유지했습니다.
• 비용: 삼각측량은 추가적인 토큰 소모 (약 4.9 배) 와 시간 (약 2.5 배) 이 들지만, 코드 생성의 신뢰성을 확보하기 위한 합리적인 트레이드오프로 평가됩니다.

5. 의의 및 결론 (Significance)

• 블랙박스 검증의 새로운 패러다임: LLM 의 내부 구조를 변경하지 않고, 생성된 코드의 '의미적 일관성'을 교차 검증함으로써 신뢰도를 높이는 최초의 체계적인 프레임워크입니다.
• 오류 상관관계 극복: LLM 이 특정 패턴의 오류를 반복하는 경향을, 본질적으로 다른 알고리즘이 필요한 변환 문제를 통해 우회하여 해결했습니다.
• 실무 적용 가능성: "Vibe Coding" (코드 리뷰 없이 LLM 코드만 사용하는 것) 이 늘어나는 상황에서, 개발자가 생성된 코드를 신뢰할 수 있도록 자동화된 검증 도구를 제공합니다.

이 연구는 LLM 기반 코드 생성의 신뢰성 문제를 해결하기 위해, 단순한 테스트 생성을 넘어 문제 자체의 구조를 변형하여 논리적 일관성을 검증하는 새로운 접근법을 제시했다는 점에서 의의가 큽니다.