본 논문은 대규모 언어 모델(LLM)의 테스트 시간 계산에 대한 증명 가능한 확장 법칙을 갖는 두 가지 단순하고 원칙적이며 실용적인 알고리즘을 제안합니다. 첫 번째 알고리즘은 두 단계의 노크아웃 방식 알고리즘으로, 입력 문제가 주어지면 먼저 여러 후보 솔루션을 생성한 다음 노크아웃 토너먼트를 통해 최종 출력을 집계합니다. LLM이 0이 아닌 확률로 정답을 생성하고 정답과 오답을 비교하는 데 무작위 추측보다 나은 성능을 낸다고 가정하면, 이 알고리즘의 실패 확률은 테스트 시간 계산이 증가함에 따라 지수적으로 또는 거듭제곱 법칙으로(확장 방식에 따라 다름) 0으로 감소한다는 것을 이론적으로 증명합니다. 두 번째 알고리즘은 두 단계의 리그 방식 알고리즘으로, 각 후보는 단일 상대방에게 패배하여 제거되는 대신 여러 상대방에 대한 평균 승률로 평가됩니다. 유사하지만 더 강력한 가정 하에, 이 알고리즘의 실패 확률 또한 테스트 시간 계산이 증가함에 따라 지수적으로 0으로 감소한다는 것을 증명합니다. 두 알고리즘 모두 최소한의 구현을 위해 블랙박스 LLM만 필요하며(예: 검증자나 보상 모델 없음) 실제 응용 프로그램에 매력적이고 다양한 작업에 쉽게 적용할 수 있습니다. 다양한 모델과 데이터 세트를 사용한 광범위한 실험을 통해 제안된 이론을 검증하고 두 알고리즘의 뛰어난 확장 속성을 보여줍니다.
