코드의 시간 복잡도(code time complexity) 예측에서 규칙 기반은 일반화에 실패하는 경우가 많습니다. Loop bounds, recursion bases, divide-and-conquer 분할과 같은 미세한 구조적·의미적 변화만으로도 실제 복잡도 클래스가 $O(n) ↔ O(n log n) ↔ O(n^2)$처럼 뒤바뀔 수 있기 때문이다. 따라서 우리는 코드를 이해할 수 있는 LLM을 사용합니다.
그러나 단일 모델(single-model) 기반의 LLM 접근법 (zero/few-shot, CoT, self-consistency 등)은 종종 Degeneration-of-Thought (DoT) 현상을 겪습니다. 즉, 단일 모델은 잘못된 첫 판단을 강화하며 오답에 수렴하기 쉽습니다.
이를 완화하기 위해 제안된 **Multi-Agent Debate(MAD)**는 에이전트 간 Debate을 통해 DoT를 분산시키지만, 다수결과 단일 판정(judge) 의존으로 정답 소수(minority-correct) 의견이 묻히는 문제가 있습니다. 이에 따라 우리는 MEC³O를 제안합니다. 이 방법은 judge 없이 소수 정답 신호를 보존함으로써 기존 MAD의 한계를 해결한 방법론입니다.
MEC³O는 LLM을 시간 복잡도 클래스별 전문가(Expert) 로 지정하고, 토론(Debate) 과 가중 합의(Weighted Consensus) 를 통해 judge 없이 최종 결론을 도출합니다. 이를 통해 단일 모델의 DoT 편향과 기존 MAD의 다수결 편향을 동시에 완화합니다.
MEC³O는 다음 4단계로 이루어집니다: