Robust Multi-Agent LLMs under Byzantine Faults

기술 요약: 비잔틴 결함 하의 견고한 다중 에이전트 LLM

문제 제기
대형 언어 모델 (LLM) 에이전트들이 협업적 합의를 통해 과제를 해결하기 위해 피어 투 피어 다중 에이전트 시스템 (LLM-MAS) 에 점점 더 많이 배포되고 있습니다. 그러나 이러한 시스템은 치명적인 취약점에 직면해 있습니다. 할루시네이션으로 인해 결함이 발생하거나 의도적인 조작으로 인해 적대적인 비잔틴 에이전트 (불신할 수 있는 에이전트) 들은 정직한 에이전트들을 잘못된 결론으로 이끌 수 있습니다. CP-WBFT 와 같은 기존 접근 방식은 에이전트들이 이웃 응답에 가중치를 부여하기 위해 스스로 보고한 신뢰도 점수에 의존합니다. 이 접근 방식은 근본적으로 결함이 있는데, 비잔틴 에이전트들이 집계 과정을 지배하기 위해 신뢰도 점수를 위조할 수 있기 때문입니다. furthermore, 이전 방법들은 종종 원칙적인 통신 위상을 갖추지 못해, 협업 없이 작동하는 것보다 더 나쁜 성능 저하를 초래합니다. 핵심 과제는 임의적이거나 오해의 소지가 있는 정보를 주입할 수 있는 비잔틴 에이전트들이 존재함에도 불구하고, 정직한 에이전트들이 응답을 반복적으로 정제하고 올바른 합동에 도달할 수 있는 탈중앙화 프로토콜을 설계하는 것입니다.

방법론: 자기 앵커링 합의 (SAC)
저자들은 **자기 앵커링 합의 (Self-Anchored Consensus, SAC)**를 제안합니다. 이는 완전히 탈중앙화된 반복적 필터링 및 정제 프로토콜입니다. 송신자가 보고한 신뢰도를 신뢰하는 이전 방법들과 달리, SAC 는 평가 부담을 수신자에게 전가합니다. 이 프로토콜은 매 라운드마다 네 단계로 운영됩니다:

1. 방송: 각 에이전트는 현재 응답을 이웃들에게 방송합니다.
2. 수신자 측 점수 매기기: 이웃 응답을 수신하면, 각 에이전트 $i$는 자신의 LLM 을 사용하여 각 이웃 $j$에 대해 평가 점수 $s_{i \to j}$를 독립적으로 계산합니다. 이 점수는 쿼리에 대한 이웃 응답의 정확성을 평가하는 검증 프롬프트에서 도출되며, 송신자의 자체 보고 신뢰도와 완전히 분리됩니다.
3. 필터링: 에이전트 $i$는 자신의 자기 점수보다 엄격하게 낮은 점수를 가진 이웃들을 식별합니다. 그런 다음 이 집합에서 $F$개의 가장 낮은 점수를 받은 이웃들을 제거합니다 (여기서 $F$는 비잔틴 이웃 수의 상한선입니다). 이 단계는 잠재적인 악의적이거나 품질이 낮은 입력이 정제되기 전에 제거되도록 보장합니다.
4. 정제: 에이전트 $i$는 원래 쿼리, 현재 응답, 그리고 수신자 측 점수로 가중치가 부여된 유지된 이웃 응답 집합을 사용하여 LLM 을 다시 프롬프트함으로써 응답을 정제합니다.

이론적 프레임워크 및 위상적 조건
정직한 에이전트들이 신뢰할 수 있는 정보를 유지하도록 보장하기 위해, 저자들은 고전적인 비잔틴 내성 합의 이론, 구체적으로 평균 부분 수열 축소 (Mean-Subsequence-Reduced, MSR) 계열 알고리즘과 $r$-내성을 활용합니다.

• $(F+1)$-내성: 저자들은 통신 그래프 $G$가 $(F+1)$-내성을 가진다면, 필터링 메커니즘이 두 가지 중요한 속성을 보장한다고 입증했습니다:
  1. 국소적 회복력: 필터링 후, 모든 정직한 에이전트는 모든 신뢰할 수 있는 에이전트들 간의 최소 점수만큼이나 신뢰할 수 있는 응답을 가진 적어도 하나의 이웃을 유지합니다. 이는 비잔틴 에이전트들이 정제 과정을 오염시키는 것을 방지합니다.
  2. 전역 연결성: 필터링 후에도 정직한 에이전트들로 유도된 부분 그래프는 연결되어 유지됩니다 (구체적으로, 루트가 있는 아웃-브랜칭을 포함합니다). 이는 네트워크 전체에 정보가 분열 없이 올바르게 전파되도록 보장합니다.
• 이 논문은 이 설정에서 $F$개의 국소 비잔틴 에이전트의 영향을 제한하기 위해 $(F+1)$-내성이 필수 조건임을 증명하여, 임의적인 위상 선택에 대한 수학적 근거를 제시합니다.

주요 기여

1. 자기 앵커링 합의 (SAC): 취약한 송신자 보고 신뢰도를 수신자 측 평가와 자연어 상호작용에 맞춘 MSR 에서 영감을 받은 필터링 메커니즘으로 대체하는 완전히 탈중앙화된 알고리즘의 도입.
2. 그래프 이론적 보장: 비잔틴 영향력을 제한하고 정답으로 수렴할 수 있도록 보장하기 위한 이론적 기초로서 $(F+1)$-내성 조건을 확립.
3. 실증적 검증: SAC 가 다양한 통신 위상 (MERG, 완전 그래프, Erdős–Rényi) 과 추론 벤치마크에서 비잔틴 영향력을 효과적으로 억제하는 반면, 이전 방법들은 적대적 조건 하에서 붕괴됨을 입증.

실험 결과
저자들은 두 가지 까다로운 벤치마크인 MATH500(4 단계 기호 추론) 과 Commonsense170k(이질적 상식 추론) 에서 SAC 를 평가했습니다. 설정은 $n=7$개의 에이전트 (4 개의 강력한 정직한 에이전트, 2 개의 약한 정직한/결함 에이전트, 1 개의 적대적 비잔틴 에이전트) 와 $F=3$을 포함했습니다.

• 기선 방법의 성능 저하: 기선 방법인 CP-WBFT 는 비잔틴 영향력 하에서 치명적인 실패를 겪었습니다. MATH500 에서 이는 $-10.4\%$에서 $-24.8\%$까지의 부정적인 비잔틴 결함 내성 개선 (BFTI) 을 보였는데, 이는 협업이 에이전트의 단독 능력보다 성능을 저하시켰음을 의미합니다. 강력한 에이전트들이 크게 끌어내려졌습니다 (예: 정확도가 $84\%$에서 $49\%$로 하락).
• SAC 의 효과: 반면, SAC 는 모든 위상에서 MATH500 에서 $+3.8\%$에서 $+7.6\%$의 양의 BFTI 를 달성했습니다. 이는 강력한 에이전트들의 성능을 유지하면서 약한 에이전트들의 성능을 향상시키는 데 성공했습니다.
• 내성 지표: SAC 는 "정직한 다수" (정직한 에이전트 다수가 정답에 동의하는 쿼리의 비율) 를 높게 유지하여, CP-WBFT 의 $36.7\%$에서 $46.7\%$에 비해 MATH500 에서 $83.3\%$에서 $96.7\%$에 도달했습니다.
• 안정성: 라운드별 분석은 CP-WBFT 의 오염이 첫 번째 라운드에서 즉시 발생하여 지속되었음을 보인 반면, SAC 는 점진적인 저하 없이 반복을 통해 안정적이거나 향상된 정확도를 보임을 보여주었습니다.

의의 및 주장
이 논문은 현재 탈중앙화 LLM 협업의 주요 취약점이 송신자 보고 신뢰도에 대한 의존성이며, 이는 적대적 조작을 위한 공격 표면을 만든다고 주장합니다. 수신자 측 평가로 전환함으로써 SAC 는 비잔틴 에이전트들이 신뢰 신호를 조작할 수 있는 능력을 제거합니다. furthermore, 이 작업은 위상 설계가 단순한 휴리스틱이 아니라 수학적 필수 조건임을 강조합니다. $(F+1)$-내성을 충족시키는 것은 비잔틴 영향력을 제한하는 데 필수적입니다. 저자들은 탈중앙화 LLM 협업이 신뢰할 수 있으려면, 시스템이 수신자 측 신뢰 평가와 내성 인식 네트워크 위상을 통합해야 한다고 결론지었습니다. 이 논문은 한계를 인정하며, 현재 평가는 작은 크기 ($n=7, 9$) 의 정적 네트워크와 단일 턴 응답으로 제한되며, 내성은 수신자의 점수 함수 품질에 의존한다고 명시합니다.