RLVR에서 '공짜 점심'은 없다: 전략 특화 하에, 모든 pass@1 향상은 특정 프롬프트의 비용을 초래하며, pass@k 교차점에는 엄격한

논문: https://arxiv.org/abs/2610.39295 코드 + 검증 패키지 (논문의 모든 숫자는 스크립트에 의해 확인됨): https://github.com/yliusci/no-free-lunch-rlvr 브라우저 진단 도구: https://huggingface.co/spaces/yliusci/passk-price

저는 RLVR 논문들에서 같은 패턴을 반복적으로 발견했습니다: RL 모델은 pass@1에서는 우수하지만, 큰 k 값에서는 기본 모델이 따라잡거나 능가합니다 (Yue et al. 2025 및 다수의 후속 연구). 저는 이것이 더 많은 훈련으로 해결되는 문제인지 아니면 구조적인 문제인지를 알고 싶었습니다. 이 논문은 이론 논문이며 새로운 훈련 실행은 없습니다.

설정: RLVR을 기본 정책에 대한 지수 기울임(exponential tilt)으로 모델링합니다. (이는 미러 디센트(mirror descent)의 경우 정확하며, 시뮬레이션에서 일치하는 엔트로피 수준에서는 GRPO가 이로부터 3e-4 TV(Total Variation) 범위 내에 머무릅니다.)

결과: 공짜 점심은 없습니다. 배타적 특화 하에서, pass@1을 높이는 모든 업데이트는 특정 프롬프트에서의 성공률을 엄격하게 낮춥니다. 정확한 조건은 Stiemke 쌍대성 명제(Stiemke duality statement)입니다 (전략 적합도를 동일하게 만드는 프롬프트에 대한 엄격히 양수인 가격). 각 프롬프트에서 최고의 전략이 되는 것이 증명적으로 충분하지 않습니다: 공짜 점심을 가진 3x3 반례가 존재합니다. 바로 pass@k 가격입니다.

손실(loss)이 가장 어려운 프롬프트에 도달하면, 교차점(crossover)이 강제됩니다. 교차점의 수는 프롬프트별 성공 변화량의 부호 변동(sign variation)으로 제한됩니다 (Karlin 총 양수성). 이 경계는 1회부터 6회까지의 교차점에 대해 엄격하며, 순서 보존(order-preserving)의 경우 정확히 한 번의 교차점을 제공하여 알려진 단일 교차점 결과를 복구합니다. 이는 결함이 아니라 경계입니다.

프롬프트별 하한선(per-prompt floor)을 설정하면, 제약된 업데이트는 최적의 pass@1 대 pass@k 트레이드오프를 추적합니다. 프롬프트별 손실을 금지하면 교차점과 그에 따른 전체 pass@1 향상이 사라집니다. 동일한 기울임은 식별 가능한 지수를 가진 엔트로피-성능 법칙(entropy-performance law)을 제공합니다.

실용적인 부분: 기본 성공률 및 RL 프롬프트별 성공률(이미 모든 평가 로그에 있음)만으로 교차점 횟수, 경계, 그리고 가격(최악의 pass@k 손실)을 읽어낼 수 있습니다.

Omni-MATH에 대해 발표된 GRPO 수치(2607.20543에서 전사되었으므로 참고용일 뿐임)를 보면, k=64와 k=256 사이에 하나의 교차점을 발견합니다. 제가 반박을 예상하는 부분은 다음과 같습니다: 공유 전략 모델(shared-strategy model)은 개체군 한계 추상화(population-limit abstraction)이며, 강제 교차점(forced crossover)은 커버리지 가정(coverage assumption)이 필요합니다 (논문에서는 실패하는 영역을 제시하고 있습니다). 저는 사람들이 2개 이상의 교차점을 관찰한 프롬프트별 로그(per-prompt logs)를 정말 보고 싶습니다. 왜냐하면 그것이 강화학습(RL) 재정렬 프롬프트 난이도의 특징(signature)이기 때문입니다. submitted by /u/SwimmingAmbition5148 [link] [comments]