Field Log · Entry

Test-time Compute: Self-Consistency·Best-of-N·Search 설계 (2/10)

하나의 질문에서 여러 추론 후보를 병렬 생성하고 합의 또는 verifier로 선택하며 난이도와 SLO에 따라 계산 예산을 조절하는 구조

오늘의 결론

Test-time compute는 weight를 다시 학습하지 않고 한 요청에 더 많은 token·sample·search·verification을 배정해 답을 개선하려는 방법입니다. “오래 생각하면 항상 좋아진다”는 법칙은 아닙니다.

pass@k, self-consistency, Best-of-N은 서로 다른 질문에 답합니다. 정답이 후보 안에 하나라도 있는지, 다수 답이 무엇인지, verifier가 가장 좋은 후보를 고를 수 있는지를 구분해야 합니다.

후보 생성 능력과 선택 능력은 별도 병목입니다. oracle pass@k는 높지만 실제 Best-of-N이 낮다면 generator보다 verifier를 먼저 고쳐야 합니다.

독립 sample을 가정한 공식은 직관일 뿐입니다. 같은 prompt·model·잘못된 evidence에서 나온 경로는 오류가 강하게 상관되므로 compute를 늘려도 같은 오답만 반복할 수 있습니다.

Production에서는 query마다 고정 N을 쓰지 않습니다. 난이도·risk·초기 confidence·합의율·남은 SLO를 관측해 direct, sample, verify, search, abstain 사이에서 예산을 조절합니다.

앞 글에서는 Chain-of-Thought가 중간 token으로 계산 공간을 늘리지만 인과적 증명은 아니라는 경계를 세웠습니다. 이번에는 하나의 경로 대신 여러 후보를 만들고 선택할 때 계산 예산을 어떻게 써야 하는지 다룹니다.

test-time budget B
  = generation tokens
  + number of candidates
  + verifier calls
  + search expansions
  + tool and retrieval calls

objective
  = maximize verified task success
    under latency · cost · safety · capacity constraints

질문 난이도와 위험을 기준으로 direct, self-consistency, Best-of-N, verifier-guided search에 계산 예산을 배분하고 후보 다양성 선택 정확도 합의율 지연 비용으로 중단하는 구조

그림 1. Test-time scaling에는 후보를 더 만드는 축과 후보를 더 잘 선택하는 축이 있다. 둘 중 어느 병목인지 모르면 sample 수만 늘리고 품질은 그대로인 시스템을 만들기 쉽다.

Test-time Compute란 무엇인가

Training compute는 weight를 업데이트하는 데 사용합니다. Test-time 또는 inference-time compute는 고정된 model weight로 한 요청을 해결하는 동안 사용합니다.

training time:
  data → forward → loss → backward → update weights

test time:
  prompt → generate / sample / search / verify / use tools → answer

Test-time budget에는 단순 output token만이 아니라 다음이 포함됩니다.

긴 reasoning sequence
여러 독립 또는 조건부 sample
후보별 reward/verifier scoring
Tree·beam·Monte Carlo 형태의 search expansion
Retrieval, calculator, code execution 같은 environment interaction
Critique와 revision round
Final validation과 fallback

따라서 “reasoning token 1,000개”와 “100 token 후보 10개”는 token 수가 비슷해도 latency·parallelism·memory·선택 방식이 다릅니다.

품질을 두 함수로 나눈다

여러 후보를 쓰는 시스템은 최소 두 부분으로 나뉩니다.

candidate generator G:
  x → {y₁, y₂, ..., yₙ}

selector S:
  x, {yᵢ}, optional evidence → selected y*

품질은 generator가 좋은 답을 후보 집합에 포함시키는 능력과 selector가 그 답을 알아보는 능력의 곱에 가깝습니다.

P(system succeeds)
  = P(good candidate exists)
  × P(selector chooses good | good exists)

이는 정확한 독립 확률식이라기보다 진단용 분해입니다. 그래도 매우 유용합니다.

좋은 후보 자체가 없다 → generation, prompt, retrieval, tool을 개선합니다.
좋은 후보가 있는데 선택하지 못한다 → verifier, aggregation, calibration을 개선합니다.
좋은 후보를 선택했지만 실행에서 실패한다 → harness와 environment contract를 개선합니다.

네 가지 대표 전략을 구분한다

1. 한 경로를 더 길게 생성한다

x → z₁ → z₂ → ... → zₘ → y

장점은 구현이 단순하고 KV cache를 한 sequence 안에서 이어 쓸 수 있다는 점입니다. 단점은 초반 오류에 고정되면 긴 token이 같은 방향을 정교하게 합리화할 수 있다는 점입니다.

s1 연구가 소개한 budget forcing처럼 generation을 더 생각하게 하거나 조기에 끝내도록 제어하는 방법도 있습니다. 하지만 특정 math benchmark와 model에서 얻은 관찰을 모든 domain의 단조 증가 법칙으로 바꾸면 안 됩니다.

2. Self-Consistency로 답을 집계한다

x → path 1 → answer A
x → path 2 → answer B
x → path 3 → answer A
x → path 4 → answer A

aggregate final answers → A

동일 prompt에서 temperature를 두고 reasoning path를 다양하게 sample한 뒤 final answer의 다수결 또는 확률 질량으로 선택합니다.

잘 맞는 조건:

답의 동치 관계를 안정적으로 정의할 수 있습니다.
서로 다른 유효 reasoning path가 존재합니다.
개별 오류가 완전히 같은 방향으로 묶이지 않습니다.
Majority answer가 task success와 관련 있습니다.

어려운 조건:

장문 요약처럼 답이 open-ended입니다.
후보가 서로 다른 세부 claim을 포함합니다.
모두 같은 잘못된 retrieved document를 봅니다.
Minority candidate만 올바른 예외 조건을 발견합니다.

3. Best-of-N으로 후보를 채점한다

generate N candidates
  → score each with verifier V(x, yᵢ)
  → choose argmaxᵢ V(x, yᵢ)

Final answer가 문자열 다수결로 묶이지 않아도 됩니다. 대신 verifier가 실제 품질 순서를 구분해야 합니다.

Verifier 예시:

정답을 아는 unit test
Compiler·schema validator
Calculator로 다시 계산한 결과
Claim-evidence entailment checker
Outcome reward model
Process reward model
LLM judge
Human review

Best-of-N의 ceiling은 generator와 verifier 중 약한 쪽이 결정합니다. Verifier가 verbosity나 특정 문체를 선호하면 N이 커질수록 그 허점을 가장 잘 이용한 후보를 고를 수도 있습니다.

4. Search로 중간 상태를 확장한다

root problem
  ├─ partial step a ── a1 ── answer
  │                  └─ a2
  ├─ partial step b ── b1
  └─ partial step c

expand → score partial state → prune → continue

Tree search, beam search, verifier-guided search는 완성된 답만 N개 만드는 대신 중간 state를 평가해 promising branch에 compute를 더 씁니다.

필요한 요소:

State 표현: 지금까지의 partial solution이나 environment state
Action 생성: 다음 reasoning step, retrieval, tool call
Value estimate: 이 state에서 성공할 가능성
Expansion policy: 어느 node를 몇 개 확장할지
Pruning: 어떤 branch를 버릴지
Terminal test: 답·증명·goal state가 완성됐는지

중간 score가 부정확하면 올바른 branch를 초기에 잘라낼 수 있습니다. Search overhead, serial latency, KV 관리도 커집니다.

전략 비교

전략	후보 다양성	선택 신호	병렬화	주요 실패
긴 단일 경로	낮음	최종 token 자체	낮음	초반 오류 고착·장황함
Self-consistency	중간~높음	답의 합의	높음	상관 오류·open-ended aggregation
Best-of-N	높음	외부 verifier	높음	verifier 오판·reward hacking
중간 상태 search	구조적	partial value/process score	혼합	pruning 오류·serial latency
Tool-assisted solve	환경 의존	실행 결과	혼합	tool 선택·권한·실패 처리

한 제품에서 이들을 조합할 수도 있습니다. 예를 들어 retrieval plan을 4개 sample하고, 각 plan을 실행한 뒤 citation verifier로 Best-of-N을 선택할 수 있습니다.

pass@k는 “선택하지 않은 Oracle” 지표다

Code generation에서 k개 sample 중 하나라도 unit test를 통과하면 pass@k 성공으로 셉니다.

개별 sample 성공 확률이 p이고 완전히 독립이라고 단순화하면:

P(at least one success in k)
  = 1 − (1 − p)^k

예를 들어 p = 0.2, k = 5라면 독립 가정 아래 약 0.672입니다. 그러나 실제 sample은 같은 model·prompt·training bias를 공유해 독립이 아닙니다. 이 숫자는 직관이지 production 예측식이 아닙니다.

더 중요한 문제는 oracle입니다.

pass@k asks:
  "Was any candidate correct?"

production asks:
  "Can the system identify and return the correct one?"

Unit test처럼 자동 판별기가 있다면 pass@k 후보를 실제로 고를 수 있습니다. 판별기가 없으면 높은 pass@k가 사용자에게 바로 전달되지 않습니다.

success@1과 함께 본다

success@1: 실제 반환 정책이 고른 한 답의 성공률
oracle success@k: 후보 집합 안에 성공이 하나라도 있는 비율
selection efficiency: oracle opportunity 중 selector가 살린 비율

selection efficiency
  = actual selected successes / oracle-solvable cases

분모가 0인 경우를 별도 처리하고 confidence interval을 보고합니다.

Majority Vote가 개선되는 조건

Binary 정답에서 개별 sample이 독립이고 정확도 p > 0.5라면 홀수 N의 majority가 이론적으로 좋아집니다. 하지만 LLM reasoning에서는 다음 가정이 자주 깨집니다.

Sample별 정확도가 동일하지 않습니다.
답이 binary가 아닙니다.
오류가 독립이 아닙니다.
Answer parser가 일부 후보를 잘못 normalize합니다.
Majority class가 안전한 답이라는 보장이 없습니다.

특히 rare exception을 찾는 문제에서는 다수의 상식적 오답이 소수의 근거 기반 정답을 압도할 수 있습니다. 합의율은 confidence feature일 수 있지만 correctness certificate가 아닙니다.

후보 다양성을 측정한다

N=16이어도 모두 같은 답과 같은 reasoning이면 실질 후보 수는 1에 가깝습니다.

측정 예시:

Unique normalized answer 수
Pairwise semantic distance
Reasoning step 또는 plan의 edit distance
사용한 evidence set의 Jaccard distance
Tool sequence diversity
Correct/incorrect outcome의 intra-class correlation

Temperature만 올려 표현을 다양하게 만드는 것이 reasoning diversity는 아닙니다. 서로 다른 decomposition, evidence, tool route가 생겼는지 봅니다.

Verifier Score를 과신하지 않는다

Best-of-N은 argmax를 취하므로 verifier의 작은 편향도 N이 커질수록 증폭될 수 있습니다.

y* = argmax V(x, yᵢ)

if V rewards verbosity accidentally:
  larger N → higher chance of an extremely verbose candidate
           → selector chooses it

Verifier의 세 가지 오류

False positive: 틀린 후보에 높은 점수
False negative: 올바른 비표준 풀이에 낮은 점수
Misranking: 둘 다 맞거나 틀린 후보의 상대 utility를 잘못 정렬

Accuracy 하나보다 pairwise ranking, calibration, critical false-positive rate를 봅니다.

Generator와 Verifier의 독립성 문제

같은 model을 generator와 judge로 쓰면 같은 편향과 지식 오류를 공유할 수 있습니다. 다른 model이면 자동으로 독립적인 것도 아닙니다. 같은 web corpus와 benchmark leakage를 공유할 수 있습니다.

가능하면 task-specific executable signal을 먼저 사용합니다.

stronger evidence order, when available:
  environment success / unit test / exact rule
  → authoritative tool result
  → claim-evidence verification
  → calibrated learned verifier
  → generic LLM preference

다음 글에서는 outcome verifier와 process verifier를 더 깊게 분해합니다.

Compute Budget을 식으로 쓴다

요청 q의 총비용을 대략 다음처럼 분해할 수 있습니다.

C(q)
  = C_router
  + N × C_generation
  + N × C_verification
  + C_search_overhead
  + C_tools

Wall-clock latency는 모두 더한 값이 아닙니다. 후보를 병렬 실행하면 generation wall time은 최대 branch에 가까울 수 있지만 GPU capacity와 돈은 N개만큼 사용합니다.

parallel candidate latency
  ≈ queue + max(branch latency) + aggregate

resource consumption
  ≈ sum(branch compute and tokens)

Traffic 전체에서는 병렬 fan-out이 queue를 키워 다른 사용자의 latency까지 악화할 수 있습니다. 한 요청의 p50만 보고 global goodput을 놓치지 않습니다.

Budget의 다섯 단위

Token: input, reasoning, final answer
Candidate: sample 수, active branch 수
Interaction: retrieval·tool·environment step
Time: deadline, TTFT, episode p95
Money/capacity: request 비용, GPU-second, concurrency slot

모든 단위에 hard cap과 soft target을 둡니다.

Adaptive Budgeting

모든 query에 N=32를 쓰는 대신 작은 비용으로 시작하고 필요할 때 확장합니다.

stage 0: classify risk and estimated difficulty
stage 1: direct answer + cheap checks
stage 2: if uncertain, sample 3 paths
stage 3: if disagreement, verify or retrieve again
stage 4: if high-risk and unresolved, search or escalate

Router feature 예시:

Query length와 constraint 수
숫자·날짜·code·multi-hop signal
Retrieval score와 evidence conflict
First-pass entropy 또는 verbal uncertainty
Candidate agreement
Verifier margin
Tool error와 repeated state
Risk class와 side-effect 여부
남은 latency·cost budget

Router 자체도 틀릴 수 있으므로 “쉬움”으로 분류한 critical slice의 false negative를 따로 측정합니다.

Compute-optimal은 고정된 숫자가 아니다

ICLR 2025의 test-time compute 연구는 problem difficulty와 base model, test-time strategy에 따라 최적 budget이 달라지고 adaptive allocation이 중요함을 보였습니다. 특정 수학 dataset에서 얻은 배율을 RAG, coding, customer support에 그대로 옮기지 않습니다.

Product의 최적점은 다음에 따라 바뀝니다.

Model snapshot
Prompt와 tool protocol
Task distribution
Verifier 품질
Hardware와 serving scheduler
Latency·cost 가격
Risk tolerance

따라서 offline sweep과 production traffic replay로 frontier를 다시 측정합니다.

언제 멈출지 정의한다

Compute scaling에서 stopping rule은 algorithm의 일부입니다.

충분한 합의

top answer vote share ≥ threshold
and effective sample diversity ≥ minimum

동일 답 반복만으로 threshold를 넘지 않도록 diversity 조건을 함께 둡니다.

Verifier Margin

score(best) − score(second) ≥ margin
and score(best) ≥ absolute threshold

Margin만 크고 모든 후보 점수가 낮을 수 있으므로 absolute threshold도 필요합니다.

Verified Terminal State

Unit test 통과
Schema와 semantic constraint 통과
Citation coverage와 entailment 통과
Environment goal state 확인
Policy engine 승인

Diminishing Return

최근 batch에서 새 answer, evidence, score 개선이 거의 없으면 멈춥니다.

Δquality_estimate / Δcompute < minimum_gain

Quality estimate가 noisy하므로 한 번의 작은 변화에 과민 반응하지 않습니다.

Hard Deadline

if remaining_time < estimated_finalize_time:
  stop expansion
  return verified partial / abstain / escalate

Deadline 직전까지 branch를 늘리다 final validation과 streaming 시간을 잃지 않도록 finalize reserve를 남깁니다.

Cycle과 Duplicate State

Agent가 같은 query, tool argument, error를 반복하면 compute가 progress로 바뀌지 않습니다. Canonical state hash와 repetition limit으로 중단합니다.

RAG Agent에 적용하기

Query-level Candidate보다 Plan-level Candidate

답 text만 여러 개 만들기보다 retrieval plan을 다양화할 수 있습니다.

plan A: exact entity → policy section → exception
plan B: product taxonomy → regional policy → date rule
plan C: keyword + dense hybrid → rerank → claim verify

각 plan을 실행한 결과의 evidence coverage와 contradiction을 채점합니다. 같은 evidence로 문장만 바꾸는 N개보다 실질 다양성이 큽니다.

Retrieval Failure와 Reasoning Failure를 분리한다

oracle evidence supplied + model fails
  → reasoning/generation bottleneck

oracle evidence supplied + model succeeds
but live retrieval fails
  → retrieval bottleneck

Evidence가 없는데 reasoning sample만 늘리는 것은 비용을 hallucination에 쓰는 셈입니다.

Read Tool과 Write Tool의 Budget이 다르다

Read-only search는 병렬 후보를 비교적 안전하게 실행할 수 있습니다. 결제·메일·삭제 같은 write action은 후보마다 실제 실행하면 안 됩니다.

candidate phase:
  propose write plans in dry-run sandbox

selection phase:
  verify one plan + authorize

commit phase:
  execute once with idempotency key

Test-time search가 side effect를 N배 만들지 않도록 plan과 commit을 분리합니다.

Episode Consistency

Multi-turn agent가 매 turn 다른 model·branch로 바뀌면 state와 assumption이 흔들릴 수 있습니다. Episode 내 candidate identity, tool snapshot, memory version을 trace에 남기고 필요한 경우 routing을 sticky하게 합니다.

Serving과 Cancellation까지 설계한다

병렬 sampling은 application code의 Promise.all 한 줄로 끝나지 않습니다.

요청별 fan-out 상한
Tenant별 concurrency quota
Branch별 token budget
Early winner가 나왔을 때 나머지 generation cancel
Cancel signal이 provider/GPU scheduler까지 전달되는지
이미 사용한 token 비용의 accounting
Timeout 후 늦게 도착한 tool result 폐기
KV cache와 prefix cache 격리·재사용
Overload에서 N을 줄이는 graceful degradation

Tail Latency

병렬 후보 모두를 기다리면 가장 느린 branch가 aggregation을 막습니다.

wait-all latency ≈ max(T₁, ..., Tₙ)

N이 커질수록 straggler를 만날 확률도 커집니다. Quorum aggregation, per-branch timeout, minimum candidate count를 정의합니다.

Global Capacity

한 요청에 compute를 8배 쓰면 동일 GPU에서 처리할 수 있는 동시 사용자 수가 줄어듭니다. Offline single-request latency뿐 아니라 target arrival trace에서 TTFT·ITL·goodput을 측정합니다.

평가 Matrix

다음 sweep은 generator와 selector를 분리해 보여 줍니다.

N ∈ {1, 2, 4, 8, 16}
strategy ∈ {majority, verifier, search}
budget ∈ {short, medium, long}
slice ∈ {lookup, arithmetic, multi-hop, code, unanswerable, high-risk}

기록할 지표:

범주	지표
생성	oracle success@N, unique answers, evidence diversity
선택	selected success@1, selection efficiency, verifier false positive
신뢰성	abstention, critical error, agreement, score calibration
비용	input/output token, verifier/tool cost, GPU-second
지연	p50/p95/p99 episode latency, timeout, straggler rate
운영	cancel success, queue depth, goodput, capacity per replica

Frontier를 그린다

X축을 성공 episode당 비용, Y축을 task success로 두고 Pareto frontier를 봅니다. Latency와 critical error는 별도 hard gate로 둡니다.

dominated configuration:
  another config is cheaper and at least as accurate

Pareto candidate:
  no other config improves one objective without worsening another

평균 frontier뿐 아니라 high-risk·Korean·long-context slice의 frontier를 따로 확인합니다.

흔한 실패와 처방

1. pass@k를 실제 제품 정확도로 보고한다

정답 후보가 존재해도 고를 방법이 없을 수 있습니다.

처방: Oracle success@k와 selected success@1을 함께 보고합니다.

2. Sample을 독립 시행으로 계산한다

같은 model과 context의 오류는 상관됩니다.

처방: 실제 curve와 answer/evidence diversity, 반복 오류 cluster를 측정합니다.

3. N만 늘리고 Verifier는 고정한다

Verifier exploit을 잘하는 후보를 찾을 확률도 커집니다.

처방: N별 false-positive와 selection efficiency를 다시 calibration합니다.

4. Open-ended 답에 문자열 다수결을 쓴다

같은 뜻을 다른 문장으로 쓰거나 부분 claim이 다릅니다.

처방: Claim decomposition, semantic clustering, evidence-aware verifier를 사용합니다.

5. 모든 Query에 최대 Budget을 쓴다

쉬운 요청의 지연과 전체 queue가 악화됩니다.

처방: Cheap-first adaptive policy와 overload degradation을 둡니다.

6. Search Branch에서 Write Tool을 실행한다

후보 탐색이 실제 부작용을 중복 생성합니다.

처방: Dry-run plan search와 authorized single commit을 분리합니다.

7. Winner가 나와도 Branch를 계속 돌린다

응답에는 쓰지 않을 token과 tool 비용이 남습니다.

처방: Cancellation propagation과 accounting을 integration test합니다.

8. Quality만 보고 Tail Latency를 숨긴다

긴 branch 하나가 p99와 timeout을 지배합니다.

처방: Candidate count별 latency distribution과 straggler rate를 봅니다.

Production 체크리스트

스스로 확인하기

Test-time compute와 training compute의 경계는 무엇인가?
Oracle pass@k와 production success@1이 다른 이유는 무엇인가?
Self-consistency와 Best-of-N의 selector는 어떻게 다른가?
후보 오류가 서로 상관되면 1-(1-p)^k 직관이 왜 낙관적인가?
Generator ceiling과 verifier bottleneck을 어떤 두 지표로 구분할 수 있는가?
Verifier의 작은 편향이 N 증가와 함께 커질 수 있는 이유는 무엇인가?
Search가 완성 답 N개 생성과 다른 점은 무엇인가?
Adaptive budget router가 사용할 수 있는 신호는 무엇인가?
Finalize reserve가 필요한 이유는 무엇인가?
RAG에서 같은 evidence를 본 문장 후보 N개가 다양하지 않은 이유는 무엇인가?
Write tool을 search branch마다 실행하면 어떤 문제가 생기는가?
한 요청의 병렬 latency가 줄어도 system goodput이 나빠질 수 있는 이유는 무엇인가?

작은 실습

정답을 자동 채점할 수 있는 50개 문제와 claim-evidence로 채점할 50개 RAG 질문을 준비합니다.

N={1,2,4,8}로 후보를 sample합니다.
Oracle success@N, majority, verifier Best-of-N을 각각 계산합니다.
선택하지 못한 oracle opportunity를 모아 verifier 오류를 분류합니다.
Normalized answer 수와 evidence set 다양성을 기록합니다.
Candidate count별 token·비용·p95 latency를 측정합니다.
합의율과 verifier margin으로 adaptive stop policy를 만듭니다.
고정 N과 adaptive policy의 cost per success를 locked test에서 비교합니다.

이 실습이 끝나면 “sample을 더 뽑으면 좋아진다”가 아니라 어떤 query에서 어떤 후보·검증·중단 전략이 가장 싼 성공을 만드는지 설명할 수 있어야 합니다.

다음 글은 Verifier와 Process Supervision: ORM·PRM·Value Model입니다. 후보를 고르는 score가 무엇을 배워야 하며 왜 reward hacking이 생기는지 살펴봅니다.