Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification

Motivation

• Known: 기존 연구들은 reward model로 후보를 스코어링한 뒤 상위 후보만 verifier로 검증하는 generate-rank-verify 파이프라인을 다양한 도메인(수학 추론, 코드 생성)에서 활용해왔으며, 일부는 difficulty predictor를 학습해 inference-time budget을 조절하는 접근을 취했다.
• Gap: 고정된 (Nrew, Nver) 정책은 prompt별 난이도 차이에 대응하지 못해 쉬운 문제에는 과도한 비용을, 어려운 문제에는 부족한 탐색을 초래하며, 난이도 예측기 기반 방법은 배포 시 분포 변화에 취약하여 reward-verifier 관계가 알려지지 않은 상황에서 online하게 적응할 수 있는 이론적으로 보장된 정책이 부재하다.
• Why: LLM inference-time search는 latency, GPU compute, API 비용 측면에서 실질적 비용 문제이며, 수학 올림피아드나 경쟁 프로그래밍 등 최신 고난도 태스크에서 generate-rank-verify 파이프라인이 핵심적으로 사용되므로, 이론적 최적성과 실용적 적응성을 모두 갖춘 알고리즘은 실제 배포 비용을 크게 절감할 수 있다.
• Approach: 저자들은 문제를 generative active search라는 학습이론적 틀로 정식화하여, 알려진 score distribution과 success function 하에서의 distribution-aware 최적 정책을 dynamic programming으로 특성화하고, 미지의 환경에서는 monotonicity 가정 하에 shellwise adaptive 알고리즘 ADAP를 제안해 constant-factor 근사를 증명한다.

Achievement

Figure 2.

1. Distribution-aware 최적 정책 특성화: score distribution Dx와 success function h*_x가 알려진 이상적 세팅에서, verifier를 통과할 확률이 임계값을 넘을 때만 검증하는 단순한 threshold 형태의 최적 정책을 dynamic programming으로 도출했다(Theorem 4.2).
2. ADAP 알고리즘 및 이론적 보장: dyadic 스케일로 generation과 verification 개수를 점진적으로 늘리는 shellwise online 알고리즘 ADAP를 제안하고, monotonicity 가정 하에서 모든 feasible (Dx, h*_x)에 대해 distribution-aware 최적 대비 constant factor 이내의 기대 비용을 달성함을 증명했다(Theorem 5.2).
3. 하한 이론 및 centered star number: centered star number라는 새로운 복잡도 척도를 도입해 구조적 가정 없이는 어떤 online 정책도 최적 대비 임의로 큰 비용을 지불할 수 있음을 보이고, min{s0, cver/crew}로 특징되는 matching upper/lower bound를 제시했으며 active search와 active learning 간의 분리(separation)도 보였다.
4. 실증적 검증: HMMT 수학 추론과 LiveCodeBench 경쟁 프로그래밍에서 ADAP가 동일 성공률 달성 시 고정 정책 대비 HMMT에서 2.9배, LiveCodeBench에서 5.5배 낮은 평균 비용을 달성했고, 난이도 예측기반 oracle 베이스라인 DAPk에도 근접한 성능을 보였다.

How

Figure 3. Top: success rate vs. cost budget for the best Uni-

• 각 prompt에 대해 generator와 reward model이 유도하는 미지의 score distribution Dx와 score-conditioned success function h*_x를 정의하여 cost-sensitive first-positive search 문제를 정식화
• crew, cver로 각각 생성/스코어링 비용과 verifier 호출 비용을 모델링하고 총 비용 J = crewNrew + cverNver 최소화를 목표로 설정
• Dx, h*_x가 알려진 이상적 세팅에서 dynamic programming으로 최적 정책이 threshold 규칙임을 증명
• h*_x가 reward score에 대해 non-decreasing이라는 monotonicity 가정 하에, dyadic scale로 sample pool과 verification 수를 점진적으로 늘리는 shellwise 알고리즘 ADAP 설계 및 constant-factor 근사 보장 증명
• centered star number라는 복잡도 척도 도입, binary concept class에 대해 matching upper/lower bound 도출 및 active learning과의 separation 증명
• HMMT(수학), LiveCodeBench(코딩)에서 exact answer matching과 hidden-test execution을 verifier로 사용해 고정 정책, 난이도 계층화 oracle DAPk, SAMPLEAWARE 등과 비교 실험 수행

Originality

• generate-rank-verify 문제를 cost-sensitive first-positive search로서의 generative active search라는 새로운 학습이론적 틀로 정식화
• 알려진 분포 하 최적 정책을 dynamic programming으로 특성화하고 이를 실용적 online 알고리즘으로 근사하는 이론-실무 결합 접근
• centered star number라는 새로운 복잡도 척도를 도입하여 구조적 가정의 필요성을 학습이론적으로 정당화
• active search와 active learning 사이의 이론적 separation을 규명한 점이 독창적

Limitation & Further Study

• ADAP의 이론적 보장은 h*_x가 reward score에 대해 non-decreasing이라는 monotonicity 가정에 강하게 의존하는데, 실제 reward model이 이 가정을 만족하지 않는 경우(예: reward hacking, 노이즈가 심한 reward model)에 대한 견고성 분석이 제한적일 수 있음
• 실험이 수학 추론(HMMT)과 경쟁 프로그래밍(LiveCodeBench) 두 도메인에 국한되어 있어, 더 다양한 태스크(예: 개방형 대화, 다단계 도구 사용)로의 일반화 가능성은 추가 검증이 필요
• cost ratio cver/crew=10을 기본값으로 사용했는데, 실제 서비스 환경에서의 비용 구조는 훨씬 다양하고 동적일 수 있어 이에 대한 추가 강건성 검증이 요구됨
• centered star number 기반 하한이 이론적으로는 우아하지만 실제 reward-verifier 관계의 복잡도를 사전에 추정하기 어려운 실무적 한계 존재

Evaluation

총평: 이론적 엄밀성과 실용적 알고리즘 설계를 균형있게 결합한 견고한 연구로, inference-time compute 배분이라는 실질적 문제에 학습이론적 통찰을 제공하는 의미 있는 기여를 한다. 다만 monotonicity 가정에 대한 의존성과 제한된 도메인에서의 검증은 향후 확장 연구의 여지를 남긴다.