Beyond Majority Voting: LLM Aggregation by Leveraging Higher-Order Information

Motivation

• Known: 기존 multi-agent LLM reasoning(LLM debate, LLM council 등) 연구는 주로 majority voting을 사용해 여러 LLM의 답변을 하나로 집계했으며, 이는 zero-order 방법으로 모델 간 이질성(heterogeneity)과 상관관계(correlation)를 고려하지 않는다.
• Gap: MV는 모든 에이전트를 동등하게 취급하여 각 LLM의 실제 정확도 차이와 답변 간 상관관계라는 higher-order information을 활용하지 못하며, 이러한 정보를 이론적으로 정당화된 방식으로 활용하는 label-free, training-free 집계 방법이 부재했다.
• Why: 멀티 에이전트 LLM의 집단적 정확도를 개선하는 것은 LLM debate, prediction market, prediction-as-a-service 등 다양한 실세계 응용에서 중요하며, ground-truth label 없이도 신뢰도 높은 집계를 가능하게 하는 이론적으로 최적인 방법을 제공하는 것은 실용적, 학술적으로 큰 의미를 가진다.
• Approach: 저자들은 information aggregation 이론에 뿌리를 둔 formal model을 세우고, 각 LLM의 정확도를 아는 경우에 대해 Bayesian-optimal한 선형 가중 집계기 OW를 유도하며, 정확도 정보 없이 답변 간 상관관계만으로 동작하는 ISP를 설계한다.

Achievement

Figure 2. Accuracy of different LLMs across the three datasets.

1. Optimal Weight(OW) 알고리즘: 각 LLM의 정확도 x_i에 sigmoid-like 함수 σ_K(x)=e^x/(K-1+e^x)의 역함수 값을 가중치 w_i로 사용하는 선형 집계기를 제안하고, 이것이 동일한 정보 접근 조건에서 어떤 (선형 또는 비선형) 집계기보다도 기대 정확도를 최대화하는 Bayesian-optimal 집계기임을 증명했다.
2. 단일 LLM 대비 우월성 증명: mild assumptions 하에서 OW로 구성된 Bayesian-optimal 집계기가 임의의 단일 LLM보다 엄밀하게 높은 정확도를 갖는다는 것을 이론적으로 보였다.
3. Inverse Surprising Popularity(ISP) 알고리즘: Prelec et al.(2017)의 surprising popularity rule을 counterfactual하게 변형하여, ground-truth label 없이 second-order 정보(답변 간 상관관계)만으로 MV보다 우월한 정확도를 갖는 집계기를 설계했다.
4. 실용적 근사 알고리즘 OW-L, OW-I 제안: 접근 불가능한 실제 정확도 x_i를 second-order 정보로 근사 추정하여 OW에 적용하는 두 가지 실용적 변형을 제시하고, ISP를 독립적 집계기 또는 정확도 추정기로 함께 활용 가능함을 보였다.
5. 다양한 실험적 검증: 합성 데이터셋, UltraFeedback, MMLU 벤치마크, 실세계 헬스케어 데이터셋 ARMMAN에서 제안 알고리즘들이 MV 등 표준 기준선을 일관되게 능가함을 실증했으며, 특히 OW-L과 OW-I가 서로 강한 일관성을 보이며 최고 성능을 달성했다.

How

• 정답 없는 질문 집합에서 각 질문의 정답을 K개 후보 중에서 예측하는 문제로 모델링하고, N개의 LLM 에이전트로부터 얻은 예측 A_1,...,A_N과 정답 S*의 결합분포 P0를 정의
• 사전 정보 P0(S*)에 대한 지식이 없다는 prior-free 가정 하에, 라벨을 무작위로 shuffle하는 전처리를 적용해 오차 분포에 통계적 균일성(statistical uniformity)을 부여(Proposition 2.1)하고 이 과정이 정보 손실 없음을 부록에서 증명
• LLM 에이전트의 정확도 x_i = P0[A_i = S*]를 first-order information으로 정의하고, 이를 안다는 가정 하에 σ_K(x) = e^x/(K-1+e^x) 함수의 역함수 값을 가중치로 사용하는 선형 집계기 OW를 도출, 이것이 Bayesian-optimal임을 증명
• 정확도 정보 없이 LLM 답변 간 상관관계(second-order information)만을 이용해, Prelec et al.(2017)의 surprising popularity rule을 반전(counterfactual variant)시킨 ISP 알고리즘을 설계
• 실제 정확도를 second-order 정보로부터 추정하여 OW에 대입하는 두 실용 알고리즘 OW-L, OW-I를 구성
• 합성 데이터(기술적 가정과 정확히 일치하는 시뮬레이션), UltraFeedback, MMLU, ARMMAN 데이터셋에서 제안 방법과 MV를 비교하는 실험을 수행

Originality

• 다중 LLM 답변 집계 문제를 information aggregation 이론(Austen-Smith & Banks, Frongillo et al. 등) 관점에서 formal하게 정식화하고, LLM 특유의 문제 구조(대칭적 사전 신념, shuffle 전처리 등)를 활용해 closed-form Bayesian-optimal 해를 유도한 점이 독창적임
• 기존 surprising popularity rule을 "역(inverse)" 방향으로 변형한 ISP를 제안하여, ground-truth label 없이도 second-order correlation만으로 MV를 능가하는 이론적 보장을 제공한 것은 새로운 기여임
• Mixture-of-Experts(MoE)와 명확히 구분되는 문제 설정(내부 표현 대신 최종 출력 집계)을 제시하며, label-free·training-free라는 실용적 제약 하에서 이론과 실증을 동시에 다룬 프레임워크를 제시함

Limitation & Further Study

• OW는 이론적으로 최적이지만 실제 정확도 x_i를 알기 위해서는 많은 ground-truth 질문이 필요하다는 근본적 한계가 있으며, 이를 우회하기 위한 OW-L, OW-I 근사 방법의 추정 오차가 이론적 최적성을 얼마나 훼손하는지에 대한 정량적 분석이 부족해 보임
• ISP는 second-order information만 활용하지만 여전히 mild assumptions(예: 에이전트 간 특정 상관구조, symmetric prior 등)에 의존하며, 이러한 가정이 실제 다양한 LLM 조합에서 어느 정도 위반될 수 있는지에 대한 강건성 분석이 제한적일 수 있음
• 실험이 UltraFeedback, MMLU, ARMMAN 등 특정 벤치마크에 한정되어 있어, 더 다양한 도메인(예: 개방형 생성 과제, 멀티턴 대화)으로의 일반화 가능성에 대한 추가 검증이 필요함
• K(후보 답 개수)가 커질수록 ISP와 MV의 성능 차이가 사라진다는 Figure 1의 결과는 ISP의 실용적 이점이 특정 K 범위에 제한될 수 있음을 시사하며, 이에 대한 심화 논의나 대안이 후속 연구로 요구됨

Evaluation

총평: 이론적 최적성 증명과 실용적 근사 알고리즘, 다양한 실험적 검증을 균형 있게 갖춘 견실한 연구로, label-free 멀티 LLM 집계 문제에 새로운 이론적 토대를 제공한다는 점에서 학술적, 실용적 가치가 높다.