기술 요약: MAXSHAPLEY

문제 정의

대규모 언어 모델 (LLM) 을 활용하여 문서를 검색하고 직접적인 답변을 생성하는 생성형 검색 엔진은 콘텐츠 제공자를 위한 기존 인센티브 구조를 붕괴시키고 있습니다. 전통적인 검색이 사용자를 소스 웹사이트로 유도하는 것과 달리, 생성형 검색은 종종 인터페이스 내에서 질문에 답변함으로써 원본 콘텐츠 제작자의 트래픽과 수익을 감소시킵니다. 또한, 생성된 답변을 특정 소스에 귀속시키는 기존 방법들은 종종 신뢰성이 낮거나, 쉽게 조작될 수 있으며, 불투명합니다.

이 논문이 다루는 핵심 과제는 생성된 답변에 대한 기여도에 기반하여 정보 소스에 공정한 크레딧을 귀속시키는 공정하고 인센티브 호환적인 메커니즘을 정의하는 것입니다. 이러한 귀속은 효율성 (Efficiency), 대칭성 (Symmetry), 널 플레이어 (Null Player), 가법성 (Additivity) 과 같은 표준 공정성 공리들을 만족해야 하며, 동시에 지연 시간에 민감한 검색 파이프라인에서 계산적으로 실행 가능해야 합니다. 공정한 할당의 금표준인 샤플리 값 (Shapley value) 에 기반한 기존 솔루션들은 이 맥락에서 계산적으로 처리 불가능합니다. 왜냐하면 일반적으로 소스 부분집합의 지수적 나열이나 반복적인 제거 (ablation) 실험을 요구하기 때문에, 막대한 토큰 비용과 지연 시간을 초래하기 때문입니다.

방법론: MAXSHAPLEY

저자들은 검색된 소스와 생성된 답변 간의 상호작용을 협력 게임으로 모델링하여 공정한 크레딧 귀속을 계산하는 새로운 알고리즘인 MAXSHAPLEY를 제안합니다. 이 방법은 블랙박스 환경에서 작동하며, 검색 LLM 의 내부 로짓 (logits) 이나 확률에 접근할 필요 없이 쿼리, 검색된 소스, 그리고 최종 생성된 답변만을 입력으로 요구합니다.

방법론은 세 가지 주요 단계로 구성됩니다:

1. 키포인트 분해: 귀속용 LLM($\Psi_A$) 이 생성된 답변 $a$를 가중치 $w_j$가 부여된 $n$개의 키포인트 집합 $P = \{p_1, \dots, p_n\}$으로 분해합니다.
2. 지원 점수 산정: 귀속용 LLM 이 각 소스 $s_i$가 각 키포인트 $p_j$를 얼마나 잘 지원하는지 평가하여 지원 점수 $v_{i,j}$를 생성합니다. 이 단계는 $m$개의 소스에 대해 $n \times m$번의 평가 (또는 배치 처리를 통해 그 이하) 가 필요합니다.
3. 최대 - 합 유틸리티 및 정확한 샤플리 계산:
   • 저자들은 합 - 최대 (sum-max) 구조에 기반한 새로운 유틸리티 함수 $U_{MAXSHAPLEY}$를 정의합니다. 소스 부분집합 $I$에 대해, 유틸리티는 해당 부분집합 내의 어떤 소스가 제공하는 각 키포인트에 대한 최대 지원 점수의 가중 합입니다:
     $$U_{MAXSHAPLEY}(I) = \sum_{j=1}^{n} w_j \cdot \max_{i \in I} v_{i,j}$$
   • 이 유틸리티 함수는 소스들의 상호 보완적 정보를 제공하는 협력적 성질과, 중첩된 정보의 경쟁적 성질 (특정 포인트에 대해 가장 좋은 소스만이 유틸리티에 기여함) 을 모델링합니다.
   • 결정적으로, 이 구조는 다항 시간 내에 정확한 샤플리 값 계산을 가능하게 합니다. 문제는 $n$개의 독립적인 "최대 게임 (max-games)"으로 분해됩니다. 각 키포인트에 대해 샤플리 값은 지원 점수를 정렬하고 선형 스캔을 수행함으로써 계산되며, 이는 $O(m \log m)$ 연산입니다. 이는 무차별 대입 방식 샤플리의 지수적 $O(2^m)$ 비용이나 몬테카를로 근사의 샘플링 분산을 피합니다.

주요 기여

1. 알고리즘적 혁신: 이 논문은 생성형 검색을 위해 특별히 설계된 샤플리 기반 귀속 알고리즘인 MAXSHAPLEY 를 소개합니다. 이는 일반적인 커버리지 게임 (coverage games) 클래스에서 파생된 최대 함수 샤플리 부분문제에 대한 정확하고 효율적인 $O(m \log m)$ 알고리즘을 제공합니다.
2. 블랙박스 효율성: 반복적인 컨텍스트 제거나 로그 가능도 (log-likelihood) 접근에 의존하는 기존 컨텍스트 귀속 방법 (예: ContextCite, KernelSHAP) 과 달리, MAXSHAPLEY 는 귀속용 LLM 에 대한 블랙박스 접근만 필요로 하며 반복적인 생성 실험을 피합니다.
3. 실증적 검증: 저자들은 MAXSHAPLEY 가 정확한 샤플리 계산 (FullShapley) 과 비교할 만한 귀속 품질을 달성하고 인간 주석과 강력한 정렬을 보이며, 계산 자원의 일부만 소비함을 입증했습니다.
4. 오픈 리소스: 저자들은 오픈소스 코드, HotPotQA, MuSiQUE, MS-MARCO 의 수동으로 재주석된 부분집합, 그리고 교육용 데모를 공개했습니다.

실험 결과

저자들은 MAXSHAPLEY 를 세 가지 멀티홉 QA 데이터셋인 HotPotQA, MuSiQUE, MS-MARCO에서 평가했습니다.

• 효율성 대 품질 트레이드오프: MAXSHAPLEY 는 FullShapley 가 필요로 하는 토큰의 **5.4%**만을 사용하면서도 MuSiQUE 에서 0.88 의 자카드 지수 (Jaccard index) 를 달성하여 FullShapley 와 비교 가능한 성능을 보였습니다. 가장 강력한 샤플리 근사 기준인 KernelSHAP 과 비교할 때, MAXSHAPLEY 는 7% 미만의 토큰 비용으로 인간 주석과 유사한 정렬을 달성했습니다.
• 진실값 (Ground Truth) 과의 상관관계: MAXSHAPLEY 는 HotPotQA 와 MuSiQUE 에서 FullShapley 와 강한 순서 상관관계 (Kendall's $\tau_b$) 를 보입니다. MS-MARCO 에서는 중간 정도의 상관관계를 보이지만, 이 데이터셋의 소스 콘텐츠가 더 노이즈가 많기 때문에 모든 샤플리 방법들이 성능 저하를 보였습니다.
• 안정성: 전체 답변 제거를 반복하는 대신 국소적 의미 판단 (소스 - 키포인트 쌍 점수화) 을 사용함으로써, MAXSHAPLEY 는 표현 방식이나 소스 순서에 따라 의미적으로 동일한 답변이 다른 점수를 받는 LLM 을 심판자로 한 평가에서 흔히 관찰되는 점수 불안정성을 완화합니다.
• 확장성: MAXSHAPLEY 의 토큰 소비량은 소스 수에 따라 선형적으로 증가하는 반면, KernelSHAP 은 초선형 (super-linear) 확장성을 보입니다.

중요성과 주장

이 논문은 MAXSHAPLEY 가 인센티브 호환적인 생성형 검색을 향한 실용적인 경로를 제공한다고 주장합니다. 크레딧 귀속을 위한 공정하고 계산적으로 효율적이며 블랙박스인 방법을 제공함으로써, AI 생성 답변 시대에 콘텐츠 제공자들이 직면한 "멸종 위기적 사건"을 해결합니다.

저자들은 자신의 작업을 생태계의 필수적인 진화로 위치시키며, 광고주에게 이익을 주고 유기적 제공자에게는 그렇지 않은 스폰서 검색 경매를 넘어, 생성된 답변의 유틸리티에 대한 실제 기여도에 기반하여 콘텐츠 제공자가 보상받는 모델로 전환해야 한다고 역설합니다. 이 방법은 공정성의 공리적 요구사항 (샤플리 값) 을 만족하면서도, 실시간 검색 환경에서 그러한 귀속을 이전에는 불가능하게 만들었던 계산적 장벽을 극복합니다. 저자들은 겸손하게도, 이 방법이 견고하지만 블랙박스 가정 하에 작동하며, 향후 연구는 다수의 독립적인 소스로부터의 상호 검증 증거를 명시적으로 보상하는 화이트박스 귀속이나 유틸리티 함수를 탐구할 수 있다고 언급합니다.