작은 LLM은 더 오래 생각하면 큰 모델을 이길까: Test-Time Compute 원 논문 해부

2단계 열다섯 번째 논문. 이 글은 Charlie Snell, Jaehoon Lee, Kelvin Xu, Aviral Kumar의 Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters (arXiv v1 PDF, 2024-08-06)를 직접 읽고 썼다. 논문이 다룬 **test-time compute(추론 시 계산량)**는 “모델을 다시 학습하지 않고, 실제 질문을 받은 뒤 더 많은 후보를 생성·검증·수정하는 데 쓰는 계산”이다. 핵심은 모든 질문에 같은 방식으로 오래 생각시키지 말고, base LLM(기본 언어 모델)에게 그 질문이 얼마나 어려운지에 따라 계산 방식과 예산을 다르게 배분하자는 것이다.

이 글에서 얻을 답과 범위

앞 글 FlashAttention은 같은 attention을 GPU memory에서 더 잘 실행하는 방법이었다. 이 글의 질문은 실행 kernel보다 한 단계 위다.

같은 LLM, 같은 질문, 같은 총 token/FLOPs 예산이라면

한 번만 답하게 할까?
답 64개를 독립적으로 뽑아 좋은 것을 고를까?
이전 답을 보고 차례대로 고쳐 쓰게 할까?
중간 풀이 단계를 채점하며 tree search를 할까?

그리고 쉬운 문제와 어려운 문제에 정말 같은 답이 맞을까?

이 논문은 “더 길게 답하면 항상 좋아진다”를 주장하지 않는다. MATH라는 수학 추론 benchmark(벤치마크, 정해진 기준으로 성능을 재는 문제 묶음)와 PaLM 2-S*라는 특정 model에서, 질문 난이도·generation budget(생성 예산)·verifier 품질에 따라 최적 전략이 달랐다고 보인다. 원 논문 §3–§8이 근거다.

이 글을 다 읽으면 다음을 설명할 수 있어야 한다.

1. test-time compute와 pretraining compute(사전학습 계산)는 각각 언제, 무엇에 돈·GPU 시간·지연 시간을 쓰는가?
2. proposer(후보 답을 만드는 쪽)와 verifier(후보 답을 평가·선택하는 쪽)는 왜 서로 다른 두 손잡이인가?
3. Best-of-N, PRM(Process Reward Model, 과정 보상 모델) search, beam search, lookahead search, sequential revision(순차 수정)은 후보 공간을 어떻게 다르게 탐색하는가?
4. 논문의 compute-optimal strategy(계산 최적 전략) 수식에서 q, y*, N, θ, Target은 무엇인가?
5. “난이도별 routing”이 정답을 미리 아는 cheating이 되지 않으려면 무엇이 필요하며, 이 논문은 무엇을 아직 해결하지 못했는가?
6. “작은 모델이 14배 큰 모델을 이겼다”가 어느 조건의 FLOPs-matched evaluation(동일 FLOPs 비교)이고, 왜 일반 법칙이 아닌가?
7. 백엔드·DBA가 실제 서비스에 이 아이디어를 넣을 때 어느 데이터·metric·budget·failure path를 운영해야 하는가?

범위와 버전: arXiv 2408.03314v1만 다룬다. arXiv metadata는 이 논문이 2024-08-06 제출된 v1 하나임을 보인다. 본문은 §2–§8과 Appendix C–J을 중심으로 읽었고, arXiv e-print LaTeX source도 확인했다. 논문은 PaLM 2-S*와 MATH 실험을 공개하지만, 공개 e-print bundle에는 Python·notebook·shell·CUDA 실행 파일이 없고 본문 TeX에도 공식 code repository URL이 없다. 따라서 아래의 순수 Python 실험은 논문 benchmark 재현이 아니라 수식과 routing 규칙을 이해하기 위한 직접 검산이다. 2025년 이후의 reasoning model, o1 계열, DeepSeek-R1, test-time RL(추론 중 강화학습), tool agent 성능과 이 논문의 수치를 섞지 않는다.

먼저 외울 한 문장

Test-time compute는 모델에 새 지식을 주입하는 마법이 아니다. 이미 풀 수 있는 문제에서 후보를 넓게 찾고, 답을 고치고, 검증해 더 좋은 답을 고를 기회를 늘리는 비용이다. 정답 후보를 거의 만들지 못하는 아주 어려운 문제, 틀린 verifier, 과도한 지연 예산에서는 더 많이 돌려도 해결되지 않는다.

왜 필요한가: “큰 model 하나 + 한 번 생성”만으로는 계산 예산을 잘 못 쓴다

12살 비유: 시험지 한 장을 바로 제출할지, 풀이 종이를 더 쓸지

수학 시험에서 10분이 있다. 선택지가 있다.

방법 A: 문제를 보고 답안 한 장을 바로 낸다.
방법 B: 답안 8장을 따로 풀어 보고, 선생님이 가장 좋아 보이는 한 장을 고른다.
방법 C: 첫 답안을 쓴 뒤, 틀린 곳을 찾아 7번 고친다.
방법 D: 풀이의 한 줄마다 선생님에게 “여기까지 맞나?”를 물으며
         유망한 풀이 가지를 남기고 나머지를 버린다.

문제가 2+2라면 D는 낭비다. 이미 A가 충분하다. 반대로 첫 줄부터 어떤 정리를 써야 할지 모르는 어려운 문제라면, 한 답을 문장만 다듬는 C보다 서로 다른 풀이 방향을 여러 개 내는 B가 나을 수 있다. 하지만 선생님이 틀린 풀이를 높게 점수 준다면 D는 오히려 틀린 길을 더 열심히 판다.

LLM도 같다. 한 번의 decoding(디코딩, 다음 token을 하나씩 생성하는 추론)만 쓰는 기본 방식은 싸고 빠르다. 반면 reasoning task(추론 과제)는 여러 candidate(후보), 자기 수정, verifier, search를 쓰면 성공률이 올라갈 여지가 있다. 문제는 추가 계산을 어디에 얼마나 쓸지다.

training-time과 test-time은 같은 “GPU 사용량”이지만 시간·비용 구조가 다르다

이 구분은 특히 서비스 설계에서 중요하다. model parameter를 두 배로 키우면 training 비용만 늘어나는 것이 아니다. 매 요청 decoding도 더 비싼 model으로 돈다. 반대로 작은 model에 test-time compute를 쓰면 해당 요청의 latency·GPU 시간을 크게 늘린다. 원 논문 §7는 이 두 장부를 FLOPs로 맞춰 비교하려 했다.

“생성 token을 많이 쓰기”는 하나의 방법이 아니라 여러 선택의 조합이다

N=64 generation이라고 해도 다음은 서로 다르다.

parallel 64개:       64개의 독립 풀이를 뽑는다. 넓게 탐색한다.
sequential 64번:     앞 답을 context에 넣어 64번 고친다. 한 길을 깊게 판다.
beam search:         매 풀이 단계에서 후보 prefix를 채점하고 일부만 확장한다.
lookahead search:    다음 몇 step을 미리 굴려 본 뒤 현재 prefix를 채점한다.

따라서 “chain-of-thought를 길게 쓰자”만으로는 policy(정책, 어떤 순서·규칙으로 계산 예산을 쓰는지)가 정해지지 않는다. 이번 논문의 기여는 이 선택들을 proposer와 verifier라는 두 축, 그리고 **질문별 난이도에 따른 allocation(배분)**으로 정리한 데 있다.

무엇인가: 질문마다 어떤 계산을 얼마나 쓸지 고르는 compute-optimal policy

논문이 말하는 test-time compute의 두 손잡이

논문 §2는 추가 추론 계산을 통해 model의 output distribution(출력 분포)을 바꾸는 방법을 두 가지로 나눈다.

prompt q
  │
  ├─ proposer 축: 어떤 candidate 답을 만들 것인가?
  │     - 독립 sample을 여러 개 생성
  │     - 이전 답·비평을 context에 넣어 revision 생성
  │     - prompt / model distribution을 바꾼다
  │
  └─ verifier 축: 만든 candidate 중 무엇을 채택할 것인가?
        - 최종 답 하나의 score
        - 풀이 step마다의 score(PRM)
        - score를 이용한 best-of-N / beam / lookahead search

**proposer(제안기)**는 답안지를 만들어 내는 LLM이다. p(y|q)처럼 prompt q를 보고 답 y를 낼 확률 분포라고 생각하면 된다. **verifier(검증기)**는 “이 답 또는 이 풀이 단계가 맞을 가능성”을 점수화한다. 답을 만드는 능력과 잘 고르는 능력은 별개다. 좋은 verifier가 있어도 proposer가 정답이 될 후보를 단 한 번도 만들지 못하면 고를 정답이 없다. 반대로 후보 중 정답이 있어도 verifier가 틀린 답을 높게 준다면 selection이 망가진다.

논문의 formal definition(형식적 정의)을 한 기호씩 푼다

논문 §3.1은 다음을 정의한다.

[ \theta^_{q,y^(q)}(N)= \arg\max_{\theta} \mathbb{E}_{y\sim\operatorname{Target}(\theta,N,q)} \left[\mathbb{1}{y=y^*(q)}\right] \tag{1} ]

수식이 무서워 보이면 “예산 N 안에서, 이 문제에 정답이 나올 확률을 제일 크게 만드는 설정 θ를 고르자”라는 한 문장이다.

여기서 아주 큰 숨은 문제가 있다. 실서비스에서 y*(q)는 모른다. 정답을 알아야 식 (1)을 바로 계산할 수 있다면 문제를 이미 푼 셈이다. 그래서 논문은 θ*를 직접 구한 것이 아니라, base model 관점의 난이도를 대리 변수로 쓰는 근사 policy를 만들었다.

이 논문이 하지 않는 일

이 경계가 중요하다. 이 논문은 2024년 PaLM 2-S* 수학 실험으로 **“어떤 adaptive allocation이 가능하다”**를 보인 논문이다. “작은 model은 언제나 더 많이 생각하면 큰 model을 이긴다”는 제품 약속이 아니다.

선행 개념: sample, pass@1, reward model, PRM·ORM, search를 헷갈리지 말자

LLM은 답 하나를 결정적으로 꺼내는 DB query가 아니다

같은 prompt에도 temperature(temperature, 다음 token 확률 분포를 얼마나 퍼뜨릴지 조절하는 값)와 random seed가 다르면 다른 답이 나온다. 여러 답을 뽑는 이유는 model 분포 안에 정답 경로가 있을 수 있기 때문이다.

q = “어떤 수학 문제”

sample 1 → 풀이 A → 최종 답 12   (오답)
sample 2 → 풀이 B → 최종 답 14   (정답)
sample 3 → 풀이 C → 최종 답 12   (오답)

한 번만 생성하면 정답률은 pass@1의 감각에 가깝다. pass@1은 한 번 만든 답이 맞을 확률이다. pass@k는 k번의 기회 중 적어도 하나가 맞을 확률로 자주 쓰인다. 단, 후보 안에 정답이 존재하는 것과 system이 정답을 최종 선택하는 것은 다르다. verifier가 필요해지는 이유다.

Best-of-N은 “N개 중 score가 가장 큰 답”을 택한다

가장 단순한 test-time scaling은 independent sampling(독립 표본 생성)이다.

for i in 1..N:
    yᵢ = proposer.sample(q)
    sᵢ = verifier.score(yᵢ, q)
return yᵢ with largest sᵢ

N을 키우면 후보의 다양성이 늘 수 있다. 하지만 verifier를 N번 최적화하는 것과도 같다. verifier가 “그럴듯하지만 틀린” 문체·format·짧은 답을 좋아한다면 N이 커질수록 그 약점을 더 잘 찾아낸다. 논문 §5.3은 easy bin에서 beam search가 budget을 늘릴수록 PRM의 spurious feature(진짜 정답과 우연히 함께 나타난 가짜 신호)를 과최적화해 성능이 떨어지는 현상을 보고했다.

ORM과 PRM은 무엇을 채점하는가

예를 들어 2x=10 → x=5 → 따라서 답 7이라는 풀이에서 ORM은 최종 7만 보고 낮은 점수를 줄 수 있다. PRM은 첫 step은 높고 마지막 step은 낮게 줄 수 있다. 그러면 search는 “첫 step을 공유하는 candidate는 살리고, 마지막 계산을 다른 방향으로 확장”할 기회를 얻는다.

이 논문은 PRM을 각 step에서 0~1의 correctness estimate(정확할 가능성 추정값)를 내는 binary classifier로 fine-tuning했다. Appendix D에 따르면 soft label은 해당 step 뒤에서 Monte Carlo rollout(몬테카를로 rollout, 이후 답을 여러 번 계속 생성해 정답 비율로 가치 추정)을 하여 만들었다. 이 값은 수학적 진실 그 자체가 아니라 그 base policy가 그 prefix 뒤에서 정답으로 갈 가능성의 학습된 추정이다.

best-of-N weighted는 “한 candidate의 최고점”과 다르다

수학 문제에서 여러 풀이가 최종 답 14에 도달하고, 다른 풀이 하나가 12에 도달했다고 하자. 논문은 PRM의 step score를 각 풀이의 마지막 step score로 요약한 뒤, 같은 final answer를 내는 candidate들의 score를 더하는 best-of-N weighted를 썼다(§5.1).

[ \operatorname{Score}(a)= \sum_{i:\operatorname{final}(y_i)=a}v(y_i), \qquad a^*=\arg\max_a\operatorname{Score}(a) ]

a는 final answer, y_i는 i번째 전체 풀이, v(y_i)는 verifier score다. 같은 답을 여러 high-score 풀이가 지지하면 강해진다. 이것은 majority vote(가장 자주 나온 답)와도, 단일 최고 점수 candidate를 선택하는 보통 best-of-N과도 다르다.

beam search와 lookahead search는 넓이와 깊이를 어떻게 나누나

**beam search(빔 탐색)**는 풀이 전체를 끝까지 N개 생성한 뒤 고르는 대신, 중간 step마다 후보 prefix(아직 완성되지 않은 풀이 앞부분)를 score하고 일부만 계속 확장한다.

문제 q
  ├─ “식 세우기 A”  score 0.90  ─┐ 유지
  ├─ “식 세우기 B”  score 0.72  ─┤ 유지
  ├─ “식 세우기 C”  score 0.31  ─┘ 제거
  └─ “식 세우기 D”  score 0.18     제거

유지한 prefix에서 다음 step 후보를 다시 생성 → PRM 채점 → 반복

논문 §5.2의 구현 설명은 generation budget N, beam width M을 두고, 첫 step에서 N개를 만든 뒤 상위 N/M prefix를 남기고 각 prefix에서 M개씩 확장해 다시 N개 candidate prefix를 만들기를 반복한다. 최대 40회 확장 또는 풀이 종료까지 진행하고, 끝의 후보에 best-of-N weighted를 적용한다. 이때 M은 “얼마나 넓게 분기할지”와 “몇 prefix를 남길지”를 함께 바꾸는 hyperparameter다.

**lookahead search(앞보기 탐색)**는 현재 prefix를 평가할 때 k step 앞까지 temperature 0으로 rollout한 뒤, 그 끝 PRM score를 현재 선택에 되돌려 쓴다. k=0이면 beam search다. 더 멀리 미리 보면 value estimate가 좋아질 여지는 있지만 계산을 더 먹는다. 논문은 fair comparison을 위해 lookahead의 비용을 N×(k+1) samples로 정의했다. Figure 3에서는 같은 generation budget에서 lookahead가 대체로 다른 방법보다 낮았다. “더 복잡한 search가 항상 더 좋다”가 틀린 실제 사례다.

sequential revision은 같은 길을 고쳐 쓰고, parallel sample은 다른 길을 찾는다

parallel (넓이):
q → answer 1
q → answer 2
q → answer 3

sequential revision (깊이):
q → answer 1 → “answer 1을 보고 revision 2” → revision 3 → ...

revision은 첫 답이 거의 맞고 작은 계산·format·마지막 논리 오류만 수정하면 될 때 유리할 수 있다. 하지만 첫 접근 자체가 틀렸다면 앞 답을 context에 계속 넣는 것이 anchor(처음 답에 고정되는 현상)가 될 수 있다. 논문 §6은 revision model을 따로 fine-tuning했고, 기본 LLM에게 단지 “다시 생각해”라고 prompt하는 방법과 동일시하지 않았다.

이 논문이 관찰한 질적 pattern은 이렇다.

이는 §5–§6의 PaLM 2-S*·MATH 결과다. 어느 domain에도 그대로 옮겨 붙일 rule이 아니다.

밑바닥 원리와 알고리즘: 난이도로 θ를 근사해 예산을 routing한다

직접 알 수 없는 이상형과 실제로 쓴 근사형

식 (1)의 이상형은 문제마다 “진짜 정답률이 최대가 되는 θ”를 고른다. 배포 서버에는 정답지가 없으므로 직접 쓸 수 없다. 논문의 근사는 세 단계다.

1. 문제마다 base LLM이 얼마나 잘 푸는지로 difficulty(난이도)를 정한다.
2. 난이도 bin마다 validation 결과에서 가장 좋은 θ를 고른다.
3. 새 문제의 예상 난이도 bin → 그 bin의 θ와 N으로 실행한다.

이것은 request router가 tenant, priority, workload class로 DB query plan/queue를 다르게 고르는 것과 비슷하다. 단, LLM의 difficulty는 데이터베이스의 table size처럼 미리 정확히 주어지는 column이 아니다.

oracle difficulty: 연구에는 편하지만 서비스에는 정답을 몰래 본다

논문은 각 test question에 대해 base model의 pass@1을 2,048 sample로 추정한 뒤, 그 값으로 5개 quantile(동일 개수 구간) bin을 만들었다.

base model pass@1이 높다 → 이 model에게 쉬운 문제 → bin 1 쪽
base model pass@1이 낮다 → 이 model에게 어려운 문제 → bin 5 쪽

이 값은 benchmark의 ground-truth correctness function(정답 판정 함수)을 써야 하므로 oracle difficulty다. 운영 요청에서는 정답이 없으니 그대로 쓰면 안 된다. 논문도 §3.2에서 이를 분명히 한계로 적는다.

predicted difficulty: 정답 대신 PRM 점수 평균을 쓰지만, routing 자체도 비싸다

실사용에 더 가깝게 하려고 논문은 같은 2,048 sample의 PRM final-answer score 평균으로 5개 bin을 나눴다. 정답 label을 보지 않으므로 model-predicted difficulty다.

질문 q
  → 답을 2,048개 생성
  → PRM final score의 평균
  → 평균이 낮으면 “이 model에 어려움”으로 binning
  → 해당 bin policy 실행

여기서 “실사용 가능”이라는 말을 조심해야 한다. 2,048개의 답을 먼저 뽑는 router는 보통 서비스에서 매우 비싸다. 논문 Appendix C도 이 절차가 computationally expensive(계산적으로 매우 비싸다)이고, 그 비용을 분석에 accounting(비용 산입)하지 않았다고 쓴다. 본문 §3.2는 search를 이미 돌릴 때의 exploration cost와 공유할 수 있다고 설명하지만, 공짜라는 뜻은 아니다.

해석: 이 연구의 진짜 제품 교훈은 “2,048개를 뽑아 routing하라”가 아니다. difficulty predictor가 가치 있으려면 predictor 자체의 비용·오분류 비용·latency를 policy value와 함께 측정해야 한다는 것이다.

validation에서 bin별 policy를 고를 때 test leakage를 줄인 방법

한 데이터에서 bin을 만들고 같은 데이터로 최고 전략을 고르면, 잘 나온 설정을 우연히 고르는 selection bias(선택 편향)가 생길 수 있다. 논문은 각 difficulty bin에서 **two-fold cross validation(2-겹 교차 검증)**을 썼다.

fold A: “이 bin에서는 beam / best-of-N / 어떤 ratio가 제일 좋은가?” 선택
fold B: A가 고른 설정으로 성능 측정

fold B로 선택 → fold A로 측정도 수행
두 측정 평균을 보고

이것은 모든 과적합을 없애는 보증이 아니다. MATH라는 한 benchmark, PaLM 2-S*, 그들이 sweep한 후보 θ라는 경계는 남는다. 하지만 “평가한 같은 fold에서 최고 점수를 골라 그대로 보고”하는 것보다 낫다.

PRM search용 compute-optimal policy의 의사코드

아래는 논문 §3·§5를 backend 형태로 풀어 쓴 의사코드다. 원 저자 코드가 아니다.

def solve_with_search(question, generation_budget, difficulty_predictor, policy_table):
    difficulty_bin = difficulty_predictor(question)
    theta = policy_table[(difficulty_bin, generation_budget)]

    if theta.method == "best_of_n_weighted":
        candidates = [base_model.sample(question) for _ in range(theta.n)]
        return select_weighted_by_final_answer(candidates, prm)

    if theta.method == "beam":
        prefixes = initial_steps(base_model, question, theta.total_candidates)
        while not all_finished(prefixes) and not over_budget(prefixes):
            prefixes = keep_top_prefixes(prefixes, prm, theta.keep_count)
            prefixes = expand_each_prefix(base_model, prefixes, theta.branch_count)
        return select_weighted_by_final_answer(prefixes, prm)

    raise UnsupportedStrategy(theta)

policy_table은 configuration management(구성 관리) 대상이다. model version, prompt version, verifier version, budget class마다 검증된 table이어야 한다. production에서 prompt가 바뀌거나 verifier를 교체했는데 옛 table을 유지하면, validation에서 측정한 θ가 더는 최적이 아닐 수 있다.

revision용 compute-optimal policy는 N을 branch × chain length로 쪼갠다

총 generation budget을 B라고 하자. P개의 독립 chain을 병렬로 만들고, 각 chain에서 S번 순차 revision을 한다면 단순한 accounting은 대략 B≈P×S다. 실제 token 길이, 중도 종료, verifier cost까지 넣으면 더 복잡하다.

P=8, S=1  → 넓게 8개. pure parallel
P=1, S=8  → 한 답을 8번 고침. pure sequential
P=2, S=4  → 서로 다른 두 접근을 각각 네 번 고침. 혼합

논문 §6.2는 answer 선택을 위한 ORM verifier와 함께 이 sequential:parallel ratio를 바꾸었다. 쉬운 문제는 순차만으로 이득을 보는 경우가 있었고, 더 어려운 문제는 혼합 비율이 좋을 수 있었다. 그래서 B 하나만 고정해도 θ=(P,S,selector,...) 선택은 남는다.

논문의 revision model은 어떻게 학습했는가

이 부분을 생략하면 “LLM은 자기 답을 보면 저절로 고친다”는 오해가 남는다. 논문 §6.1과 Appendix H의 흐름은 다음이다.

MATH train question
  → base model로 독립 답 64개 sample (높은 temperature)
  → parse 가능한 답만 남김
  → correct answer 하나와 incorrect answer 0~4개를 한 trajectory로 조립
  → 마지막 incorrect answer는 character edit distance가 가까운 것을 우선 선택
  → [틀린 시도들 + 정답 시도]를 context/target으로 SFT
  → revision-capable model

틀린 답과 정답을 아무렇게나 붙이면 model은 이전 답을 읽고 수정하는 대신, 문맥을 무시하고 새로 답하는 shortcut을 배울 수 있다. 그래서 저자들은 final correct answer와 문자열상 더 가까운 incorrect answer를 우선 섞어 “수정할 만한” trajectory를 만들려 했다. token edit distance가 아니라 character edit distance를 쓴 heuristic(휴리스틱, 정확한 최적화 보증이 없는 실용 규칙)이며, 상관관계의 완벽한 척도는 아니라고 저자도 적었다.

inference에서는 학습 때 최대 4개의 이전 답만 context에 넣었지만, 더 긴 chain은 최근 4개 revision만 남겨 계속 생성할 수 있게 했다. 이것은 context window와 distribution shift(학습 때 본 상태와 실제 생성 중 상태가 달라짐)를 고려한 구현 선택이다.

내부 구조와 실제 실행 흐름: 논문 실험, 공개 artifact 경계, production system을 분리한다

논문이 실제로 평가한 pipeline

논문 §4의 공통 실험 조건은 다음이다.

MATH는 정답 판정이 가능한 수학 benchmark다. production의 open-ended 고객 문의, 문서 요약, RAG answer처럼 자동 ground truth가 없는 task와는 검증 난이도가 다르다. MATH 문제와 dataset 구성을 더 알고 싶다면 Hendrycks 외의 원 논문을 보되, 그 링크가 이 글의 설명을 대체하지는 않는다.

원 논문 source에서 확인한 “없음”의 범위

직접 확인: arXiv e-print source tarball의 파일 목록은 googledeepmind-test.tex, bibliography, figure image/PDF, DeepMind LaTeX class 등 문서 asset으로 구성됐다. .py, .ipynb, .sh, .cu, .cpp 실행 파일은 없었다. 본문 TeX에서 github, repository, code 링크도 찾지 못했다. 저자 개인 페이지의 해당 항목은 arXiv paper 링크만 제공한다.

이 확인으로 “지구상에 저자 코드가 절대 없다”는 결론을 낼 수는 없다. 다만 이 포스팅 작성 시점에 원 논문으로 독자가 내려받아 실행할 공식 PaLM 2-S·PRM·revision pipeline은 확인하지 못했다**는 뜻이다. PaLM 2-S도 public checkpoint가 아니므로 Figure 3·4·7·8·9의 수치를 그대로 재현했다고 주장하면 안 된다.

그래서 직접 실행 가능한 것은 무엇인가

원 저자 source가 없을 때는 paper fact와 내 예제를 분리해야 한다.

논문이 측정한 사실:
  PaLM 2-S* + MATH + 저자 PRM/revision model에서의 곡선·비교.

직접 실행한 검산:
  (a) bin마다 validation score의 argmax를 고르는 routing 규칙,
  (b) §7의 FLOPs-matching multiplier가 대수적으로 성립하는지.

직접 실행하지 못한 것:
  PaLM 2-S*, MATH full experiment, PRM/revision training,
  2,048-sample difficulty prediction 비용, benchmark accuracy 재현.

서비스에 옮기면 이 순서로 실행된다

다음은 논문의 idea를 operational system(운영 시스템)으로 바꾼 설계다. 해석·설계 제안이며 저자 공개 구현의 호출 경로가 아니다.

HTTP/API request
  → request validation / authentication / tenant policy
  → task classifier + cheap difficulty predictor
  → budget admission control (max tokens, max wall time, max money)
  → policy router (model/prompt/verifier/budget version이 붙은 θ 선택)
  → proposer executor
       ├─ parallel candidate generation
       ├─ sequential revisions
       └─ PRM-guided beam/search
  → verifier + answer aggregation
  → optional deterministic validator/tool result
  → final answer + provenance + telemetry persisted

DBA 관점에서 중요한 것은 final_answer만 저장하지 않는 것이다. 문제를 재현하려면 아래처럼 routing decision을 함께 남겨야 한다.

이 trace는 원문 답과 별도 보관 기간·암호화·권한을 설계해야 한다. candidate에는 사용자의 민감 정보가 여러 번 중복될 수 있다. “더 많이 sample”은 data retention(데이터 보관)과 exposure surface(노출 면적)도 키운다.

직접 검증과 재현: argmax routing과 FLOPs 교환식을 작은 코드로 끝까지 계산한다

실행 환경과 검증 범위

직접 실행 환경: macOS local shell, Python 3.9.6, 표준 라이브러리만 사용했다. GPU·PaLM API·MATH dataset·저자 PRM은 사용하지 않았다.

검증 대상: 아래 코드는 두 논문 규칙의 algebra(대수)와 decision logic(선택 로직)을 검산한다.

1. 한 difficulty bin에 여러 strategy의 held-out score가 있으면 argmax가 그 bin의 θ를 선택한다.
2. 논문 §7의 X=6ND_pretrain, Y=2ND_inference에서 나온 inference multiplier가 “작은 model의 training + 확장된 inference”와 “parameter를 M배 키운 model의 total FLOPs”를 같게 만든다.

중요: held_out 숫자는 아래 코드에서 내가 만든 교육용 숫자다. 논문 Figure의 정확도도, PaLM 결과도 아니다. 이 코드는 “논문이 주장한 benchmark를 재현”하지 않는다. routing rule과 식이 무엇을 하는지 실행으로 확인할 뿐이다.

"""Pedagogical verification for Snell et al. (2024), not a benchmark reproduction."""


def choose_best(scores):
    return max(scores.items(), key=lambda item: item[1])


def inference_multiplier(model_scale, inference_to_pretraining_token_ratio):
    # R = D_inference / D_pretrain.  X/Y = 3/R.
    return model_scale + 3 * (1 / inference_to_pretraining_token_ratio) * (model_scale - 1)


def main():
    # Made-up held-out accuracies: qualitative teaching data, not paper measurements.
    held_out = {
        "bin_1_easy": {"best_of_n": 0.91, "beam": 0.85, "lookahead": 0.78},
        "bin_2": {"best_of_n": 0.78, "beam": 0.75, "lookahead": 0.71},
        "bin_3": {"best_of_n": 0.49, "beam": 0.61, "lookahead": 0.55},
        "bin_4": {"best_of_n": 0.26, "beam": 0.37, "lookahead": 0.34},
        "bin_5_hardest": {"best_of_n": 0.04, "beam": 0.05, "lookahead": 0.04},
    }

    print("== pedagogical per-bin argmax ==")
    for bin_name, scores in held_out.items():
        strategy, score = choose_best(scores)
        print(f"{bin_name}: {strategy} ({score:.2f})")

    print("== FLOPs-matched inference multipliers for M=14 ==")
    model_scale = 14
    for ratio in (0.16, 0.79, 22.0):
        multiplier = inference_multiplier(model_scale, ratio)
        d_pretrain = 100.0  # algebra check only; N=1 is implicit
        d_inference = ratio * d_pretrain
        x = 6 * d_pretrain
        y = 2 * d_inference
        left = x + multiplier * y
        right = model_scale * (x + y)
        assert abs(left - right) < 1e-9
        print(
            f"R={ratio:g}: inference_multiplier={multiplier:.6f}; "
            f"small_train_plus_scaled_infer={left:.6f}; scaled_model_total={right:.6f}"
        )


if __name__ == "__main__":
    main()

실행 명령이다.

python3 -m py_compile verify_compute_optimal_routing.py
python3 verify_compute_optimal_routing.py

내가 실제 실행한 출력은 다음이다.

Python 3.9.6
== pedagogical per-bin argmax ==
bin_1_easy: best_of_n (0.91)
bin_2: best_of_n (0.78)
bin_3: beam (0.61)
bin_4: beam (0.37)
bin_5_hardest: beam (0.05)
== FLOPs-matched inference multipliers for M=14 ==
R=0.16: inference_multiplier=257.750000; small_train_plus_scaled_infer=8848.000000; scaled_model_total=8848.000000
R=0.79: inference_multiplier=63.367089; small_train_plus_scaled_infer=10612.000000; scaled_model_total=10612.000000
R=22: inference_multiplier=15.772727; small_train_plus_scaled_infer=70000.000000; scaled_model_total=70000.000000

실행한 script의 SHA-256은 998b4f6ca59a817b3d4dd557d1e2cabe3f4bdf82fc1dd87125b58a5c9be3d8f6다. 원 논문 PDF SHA-256은 ded7b20b51493258c5ce2a1a024cd33dd752de1fa3373d1207620da4cfe24545, e-print source SHA-256은 f179cbc6b43f09285096e8a088bdacb8b2f0af4f6e3bcaaf8c12721a0f5331f9다.

12살 숫자 예제: 왜 bin별 argmax가 필요한가

교육용 bin_3의 score가 다음이라고 하자.

best-of-N  = 0.49
beam       = 0.61
lookahead  = 0.55

max는 0.61을 찾아 beam을 반환한다. 반면 bin_1_easy에서는 0.91인 best_of_n을 고른다. 모든 문제에 beam 하나를 고정하면 bin 1에서는 0.06만큼을 버리고, 모든 문제에 best-of-N 하나를 고정하면 bin 3에서는 0.12만큼을 버린다. 이것이 논문의 난이도 조건부 policy의 최소 형태다.

실전에서는 score 하나가 흔들린다. 따라서 다음이 필요하다.

validation sample 수
confidence interval(신뢰구간)
seed별 분산
offline 평가와 online traffic 분포 차이
router 오분류 비용

0.61 > 0.60이라고 바로 새로운 policy를 deploy하면 안 된다. feature flag, holdout traffic, rollback 기준이 필요하다.

§7 FLOPs-matching 식을 한 줄도 건너뛰지 않고 유도한다

논문은 parameter 수를 N, pretraining token 수를 D_pretrain, 전체 inference token 수를 D_inference로 두고 다음 common approximation(흔히 쓰는 근사)을 쓴다.

[ X=6ND_{\text{pretrain}},\qquad Y=2ND_{\text{inference}} ]

X는 pretraining FLOPs, Y는 greedy decoding inference FLOPs다. 6과 2는 Transformer의 정확한 wall-clock 시간을 보장하는 상수가 아니라 FLOPs budget을 비교하기 위한 근사다. memory bandwidth, batch, KV cache, kernel, network, sampling overhead는 이 식 안에 없다.

parameter를 M배 키우고 data 양을 고정하면 total은 다음처럼 M배다.

[ M(X+Y) ]

작은 model의 pretraining은 원래 X만큼 이미 썼다고 하자. 동일 total FLOPs를 쓰려면 작은 model의 inference budget Y'는

[ \begin{aligned} X+Y' &= M(X+Y)\ Y' &= MY+(M-1)X\ \frac{Y'}{Y} &= M+(M-1)\frac{X}{Y}\ &=M+3\frac{D_{\text{pretrain}}}{D_{\text{inference}}}(M-1) \end{aligned} ]

이다. R=D_inference/D_pretrain이라고 두면

[ \boxed{\frac{Y'}{Y}=M+\frac{3(M-1)}{R}} ]

가 된다. 코드가 M=14에서 R=0.16이면 257.75×, R=22이면 15.77×를 출력한 이유다.

R이 작다: training token에 비해 추론 요청이 적다.
          작은 model에 요청당 큰 extra compute를 써도 전체 장부를 맞출 여유가 크다.

R이 크다: deployment에서 추론 token이 training token보다 훨씬 많다.
          매 요청에 extra compute를 붙이면 전체 비용이 빨리 불어난다.

논문 Figure 9는 R=0.16, 0.79, 22 세 경우와 약 14× parameter model을 비교했다. easy/intermediate bin 또는 낮은 inference load에서는 test-time compute가 이길 수 있었고, hard bin 또는 높은 inference load에서는 더 큰 pretraining이 낫기도 했다. 이 값들이 제품의 환율표는 아니다. 모델, task, M, token length, serving system이 바뀌면 다시 계산하고 측정해야 한다.

성능, 복잡도와 트레이드오프: 4×와 14×를 정확한 조건으로 읽는다

논문이 실제로 보고한 성능 pattern

다음은 과장 없이 Figure 3·4·7·8·9와 §5–§7을 읽어 요약한 것이다.

논문 abstract의 “more than 4×”는 같은 정확도에 도달하는 데 필요한 test-time compute efficiency의 비교다. 4배 빠른 latency, 4배 싼 GPU, 모든 prompt에서 4배 높은 accuracy라는 뜻이 아니다.

비용은 generation count 하나로 끝나지 않는다

논문은 공정 비교를 위해 generation budget을 정의했지만, production cost는 다음처럼 분해해야 한다.

[ C_{\text{request}} = C_{\text{route}}+ C_{\text{generate}}+ C_{\text{verify}}+ C_{\text{aggregate}}+ C_{\text{tool}}+ C_{\text{retry}} ]

N=64라도 candidate가 20 token인지 2,000 token인지, PRM이 한 번인지 각 prefix마다인지에 따라 cost와 tail latency가 전혀 다르다. 논문의 N은 비교를 위한 abstraction이고, 운영 budget은 token·FLOPs·wall time·dollar를 함께 가진다.

latency: parallel은 throughput과 tail latency를 맞바꾼다

parallel 64개:
  - GPU batch가 잘 차면 wall time을 줄일 수 있다.
  - 하지만 peak memory, queueing, rate limit, verifier batch가 병목일 수 있다.

sequential 64번:
  - 앞 결과가 다음 prompt라 dependency가 있다.
  - 한 chain의 wall time은 길어진다.
  - 중간에 “이미 충분히 좋다”라고 멈추는 early stop 여지가 있다.

beam/search:
  - prefix step마다 barrier(다음 확장 전 score 대기)가 생긴다.
  - high-quality verifier가 필요하다.

따라서 API의 SLA(Service Level Agreement, 서비스 수준 약속)가 p95 < 2초인 chat request에 256 sequential revision을 기본값으로 넣는 것은 논문을 따른 것이 아니다. latency class가 다른 batch/offline job에만 high budget을 허용하거나, baseline 답을 먼저 stream하고 background verification을 별도 흐름으로 두는 등 product decision이 필요하다.

verifier는 optimizer가 아니라 objective의 약한 대리자다

search가 하는 일은 대략 max verifier_score다. 사용자가 원하는 것은 max true_correctness다.

verifier score와 실제 correctness가 완전히 같으면 좋다.
실제로는 다르다.
budget을 키운 search는 그 작은 차이를 찾아 score만 높이는 답을 만든다.

논문 §5.3은 low-information repetitive step이나 지나치게 짧은 풀이가 search에서 나타난 예를 Appendix M에 실었다. 이를 reward hacking(보상 해킹) 또는 proxy exploitation(대리 지표 악용)이라고 부른다. 이는 “모델이 악의적이다”라는 뜻보다, objective가 불완전할 때 optimizer가 빈틈을 찾는 정상적인 최적화 문제다.

input distribution이 달라지면 routing table도 만료된다

정책 table은 다음 함수를 측정한 결과다.

[ \text{quality}=f(\text{base model},\text{prompt},\text{verifier},\text{task distribution},\theta,N) ]

여기서 하나라도 바뀌면 f가 바뀐다. 특히 revision model output에 base-model PRM을 그대로 적용하면 distribution shift가 생긴다. 논문 Appendix J는 이 이유로 revision output에 맞춘 별도 ORM을 학습했고, history를 verifier context에 넣는 ablation도 했다.

운영에서는 model release, system prompt, tool schema, answer parser, safety filter, traffic locale가 policy version과 동등하게 취급돼야 한다. “router는 그대로고 model만 업데이트”는 안전한 무변경이 아니다.

실패, 한계, 장애와 운영: 추가 추론은 fallback이 아니라 별도 distributed system이다

실패 모드와 먼저 볼 관찰값

production runbook: “더 생각하게 하자”를 deploy하기 전

1. Task contract를 닫는다.
   - 무엇이 정답인가? 자동 검사 가능한가? 사람이 판정해야 하는가?

2. Single-pass baseline을 만든다.
   - model/prompt/version, quality, p50/p95, token, cost를 고정한다.

3. 가장 싼 scaling을 하나만 추가한다.
   - 예: N=4 best-of-N + deterministic validator.

4. candidate 존재와 selection 품질을 분리 측정한다.
   - pass@k 비슷한 “정답 후보가 있었는가”
   - chosen@1 “선택기가 맞는 것을 골랐는가”

5. verifier가 있다면 calibration을 본다.
   - score bucket별 실제 정답률, budget별 degradation, adversarial/format case.

6. 난이도 router는 마지막에 붙인다.
   - predictor 비용까지 total cost에 넣고, unseen traffic에서 holdout 검증한다.

7. policy를 versioned config로 배포한다.
   - kill switch, per-tenant cap, timeout fallback, audit trace를 둔다.

이 순서가 중요한 이유는 router가 앞단에 오면 실패 원인이 늘어나기 때문이다. 처음부터 PRM+beam+revision+adaptive router를 한 번에 넣으면 “나빠진 것이 proposer 때문인지 verifier 때문인지 policy 때문인지” 분해할 수 없다.

보안과 데이터 경계

이 논문은 security paper가 아니다. 그래도 실제 agent/RAG system에 test-time compute를 붙이면 다음이 새로 생긴다.

candidate N개 × revision history × verifier prompt
  → 원래 요청의 민감 정보가 여러 내부 call로 복제될 수 있다.

tool-using proposer / verifier
  → prompt injection이 search branch를 늘리거나,
    내부 tool을 잘못 선택하도록 유도할 surface가 늘 수 있다.

따라서 tool 권한은 final answer가 아니라 각 candidate execution에도 최소 권한을 적용해야 한다. DB tool이라면 read-only role, allowlisted query/template, row/tenant filter, rate limit, audit log가 기본이다. “verifier가 마지막에 막겠지”는 authorization 설계가 아니다.

이 논문 스스로 말한 제한

논문 §8은 다음을 future work로 남겼다.

1. PRM tree search와 revision을 더 깊게 결합하지 않았다.
2. critique-and-revise 등 다른 test-time method를 모두 조사하지 않았다.
3. hardest problem에서는 이득이 작았다.
4. difficulty estimation 자체가 비싸다.
5. test-time에서 얻은 좋은 output을 base model에 distill해 반복 self-improvement하는 루프는 하지 않았다.

이 다섯 항목은 “논문 뒤에 후속 연구가 나왔으니 옛 논문은 무의미”라는 뜻이 아니다. 반대로 어떤 최신 reasoning system을 읽더라도 proposal, verification, allocation, cost accounting, feedback-to-training 중 무엇을 새로 해결했는지 확인하는 체크리스트가 된다.

대안, 비교와 선택 기준: 어떤 task에 무엇부터 붙일까

같은 층위의 방법을 비교한다

내 서비스에서 처음 고를 전략

정답 판정기가 있는 task라면 (SQL syntax + read-only execution, code unit test, 수식 evaluator, JSON schema) LLM verifier보다 deterministic check를 먼저 쓴다. candidate 4~8개를 만들고 실제 checker로 고르는 baseline이, PRM을 새로 훈련해 beam search 하는 것보다 훨씬 설명 가능하고 운영 가능할 때가 많다.

정답 판정기가 없는 open-ended task라면 quality label 수집·human rubric·pairwise evaluation을 먼저 만든다. PRM score가 좋다는 것만으로 real quality를 대신할 수 없다. verifier로 search를 키우기 전에 score와 human preference/ground truth의 관계부터 측정해야 한다.

기본 model이 domain 지식을 모른다면 test-time compute는 우선순위가 낮다. RAG(Retrieval-Augmented Generation, 검색 증강 생성), tool, fine-tuning, pretraining data가 먼저일 수 있다. 후보 256개가 모두 오래된 규정·없는 schema·틀린 수식을 반복한다면 selection은 정답을 창조하지 못한다.

12살에게 다시 설명하는 선택 규칙

답안들 중 맞는 것이 이미 섞여 있는가?
  아니오 → 책을 더 배우게 하거나, 자료·계산기를 준다. (training/RAG/tool)
  예 → 누가 맞는 답을 잘 고를 수 있는가?
       아니오 → 채점기를 먼저 만든다. (validator/evaluation)
       예 → 문제마다 필요한 만큼만 답안을 더 만들고 고친다. (adaptive test-time compute)

이 순서가 논문의 가장 실용적인 독해다. test-time compute는 missing knowledge의 대체물이 아니라 candidate generation과 selection이 이미 어느 정도 작동할 때 효율을 높이는 레버다.

흔한 오해와 최초 질문의 답

오해 1: “생각 token을 늘리면 LLM은 무조건 강해진다”

아니다. 논문 Figure 3은 일부 easy problem에서 beam search budget을 늘리자 성능이 떨어지는 pattern을 보였다. verifier의 약점을 더 잘 찾았기 때문이다. hardest bin도 큰 개선이 없었다. 더 긴 output, 더 많은 rollout, 더 깊은 tree는 계산을 늘릴 뿐이고 objective가 맞아야 quality가 오른다.

오해 2: “Best-of-N은 pass@N과 같은 말이다”

아니다. pass@N은 후보 중 적어도 하나가 정답인지에 관한 값이다. best-of-N은 verifier가 그 후보들 중 무엇을 선택하는지까지 포함한다. 후보 set에 정답이 있어도 verifier가 오답을 고르면 final accuracy는 낮다. 운영 metric도 candidate coverage와 selector accuracy를 분리해야 한다.

오해 3: “PRM은 풀이를 단계별로 보니 ORM보다 항상 낫다”

아니다. PRM도 학습된 proxy다. step segmentation, label 방식, base model output distribution이 달라지면 잘못된 score를 낼 수 있다. 논문은 자기 PRM/ORM 조건에서는 PRM이 더 좋았다고 보고했지만, revision model output에는 distribution shift 때문에 별도 ORM을 훈련했다. 이 자체가 일반 우위 보장이 아니라는 증거다.

오해 4: “논문이 4×를 보였으니 production 비용도 4분의 1이다”

아니다. 4×는 특정 baseline과 성능 지점의 test-time compute efficiency다. service에는 routing, verifier, queue, retries, token length, GPU utilization, p95 latency, observability 비용이 추가된다. predicted difficulty가 2,048 sample을 필요로 했다는 논문 한계도 total cost에 넣어야 한다.

오해 5: “작은 model + test-time compute가 14× 큰 model보다 항상 낫다”

아니다. 논문은 PaLM 2-S*, MATH, fixed-data parameter scaling, 세 R 값의 FLOPs-matched setting에서 비교했다. hard questions와 높은 inference load에서는 pretraining/더 큰 model이 더 나은 경우를 스스로 보였다. 작은 model이 정답 후보를 생성할 비자명한 성공률이 있어야 한다는 조건도 있다.

오해 6: “난이도 router는 질문을 읽고 공짜로 easy/hard를 안다”

아니다. 논문의 oracle difficulty는 정답을 사용한다. predicted difficulty도 많은 sample과 PRM score를 쓴다. 실서비스 router는 별도 model/heuristic이며 latency와 오류가 있다. router 자체를 검증·versioning·monitoring해야 한다.

그래서 이 논문을 읽고 내가 가져갈 한 가지

AI system을 볼 때 “이 model은 얼마나 큰가?”만 묻지 말고 다음 질문을 먼저 한다.

이 요청에서 model이 이미 정답 후보를 낼 수 있는가?
후보의 참 품질을 판별할 신호가 있는가?
추가 compute를 넓이·깊이·검증 중 어디에 쓸 것인가?
그 선택의 비용과 latency를 request 단위로 측정했는가?
어려운 문제에서 실패하면 더 sample할지, knowledge/model/tool을 강화할지 구분했는가?

이 다섯 질문에 답하지 못하면 “reasoning을 더 길게”는 학습 계획도, product architecture도 아니다. 반대로 답할 수 있다면, 작은 best-of-N baseline부터 시작해 verifier·revision·adaptive routing을 한 단계씩 검증하는 계획이 된다.

출처

1차 자료

1. Charlie Snell, Jaehoon Lee, Kelvin Xu, Aviral Kumar. Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters, arXiv:2408.03314v1, 2024-08-06. 이 글의 proposer/verifier 틀(§2), compute-optimal 정의와 난이도 binning(§3), PaLM 2-S*·MATH setup(§4), PRM search(§5), revision(§6), FLOPs-matched 교환식과 Figure 9(§7), 한계(§8)의 원전이다.
2. 같은 논문의 v1 PDF, e-print LaTeX source. source bundle 파일 구성·공식 실행 code 링크 부재의 확인 범위에 사용했다.
3. Dan Hendrycks 외. Measuring Mathematical Problem Solving With the MATH Dataset, arXiv:2103.03874. 논문이 사용한 MATH benchmark의 원전이다.
4. Hunter Lightman 외. Let's Verify Step by Step, arXiv:2305.20050. process supervision·PRM800k가 무엇인지의 원전이다. 이번 논문은 PRM800k를 그대로 사용해 성공했다고 주장하지 않았고, PaLM output distribution shift 때문에 Monte Carlo rollout label 접근을 사용했다.
5. Rohan Anil 외. PaLM 2 Technical Report, arXiv:2305.10403. 본 논문이 base model family로 적은 PaLM 2의 원전이다.

직접 검증 자료

• /tmp/test-time-compute-paper-research/verify_compute_optimal_routing.py: Python 3.9.6으로 실행한 교육용 argmax routing·FLOPs equality 검산 script. 이 글의 코드·출력·SHA-256을 본문에 기록했다.
• /tmp/test-time-compute-paper-research/paper.pdf, paper.txt, source.tar: 원 논문 PDF 추출과 LaTeX source 확인에 사용했다. 파일은 로컬 조사 artifact이며 기술로그 배포물에 포함하지 않았다.

이 글의 해석 경계

production runbook, telemetry schema, deterministic validator 우선순위, DB/tool 권한 분리는 원 논문 결과를 그대로 인용한 것이 아니라 논문의 proposer/verifier/allocation 구조를 backend·DBA 운영으로 옮긴 해석과 설계 제안이다. PaLM 2-S*·MATH benchmark 수치로 그 운영 설계의 성능을 보장하지 않는다.