15.3 Search-time Compute

앞 절은 reasoning을 명시적인 search graph로 다뤘습니다. Test-time compute는 더 넓은 시스템 문제입니다. Prompt와 latency 또는 비용 budget이 주어졌을 때 어떤 inference 절차를 실행할지, 얼마나 계산할지, 언제 멈출지를 결정해야 합니다.

Token이 늘었다고 reasoning이 늘었다고 볼 수는 없습니다. 모델은 유용한 대안을 탐색할 수도 있지만, 같은 말을 반복하거나 오류를 합리화하거나 설명만 길게 쓸 수도 있습니다. 따라서 분석 단위는 reasoning-token 수가 아니라 model–sampler–verifier–budget system 이어야 합니다.

1. Inference Compute를 쓰는 세 가지 방식

Parallel sampling

$N$ 개 candidate를 생성하고 verifier, reward model, test 또는 majority vote로 하나를 고릅니다. 독립인 candidate가 acceptable할 확률을 $p$ 라고 하면, 적어도 하나가 acceptable할 확률은

P(\text{coverage})=1-(1-p)^N

입니다. 이는 전달 품질의 상한일 뿐입니다. Verifier가 좋은 candidate를 놓칠 수 있고 sample은 서로 상관되어 있으며 $p$ 는 prompt마다 크게 다릅니다. pass@ $N$ 은 coverage, best@ $N$ 은 selector가 전달한 결과를 측정합니다. 둘을 섞으면 selection error가 가려집니다.

Sequential search

Beam search, tree search, process-reward-guided search는 부분 해답을 평가하고 약한 branch를 중단합니다. Best-of- $N$ 보다 completion token을 덜 쓸 수 있지만, 부정확한 process verifier가 유일하게 회복 가능한 경로를 잘라낼 수 있습니다. Search policy, branch width, expansion depth, stopping rule도 평가 대상의 일부입니다.

Learned long-form deliberation

Reasoning-oriented model은 하나의 trajectory 안에서 분해, 검산, 수정을 수행하도록 학습됩니다. 외부 tree controller를 줄일 수 있지만, 보이거나 숨겨진 trace가 충실한 실행 로그라는 뜻은 아닙니다. 모델이 wait 라고 쓴 것과 실제로 다른 내부 search state에서 회복한 것은 다른 주장입니다.

2. Scaling 근거를 정확히 읽기

Snell et al.은 평가한 설정에서 compute-optimal allocation이 best-of- $N$ baseline보다 4배 넘게 효율적일 수 있음을 보였습니다 [1]. Test-time compute를 쓴 작은 모델이 14배 큰 모델을 능가한 사례도 보고했습니다. 중요한 조건은 작은 모델이 이미 non-trivial success를 보이는 난이도 구간이었다는 점입니다. 작은 모델이 token만 길게 내면 언제나 큰 모델을 대체한다는 법칙이 아닙니다.

수익 곡선은 보통 세 구간으로 나뉩니다.

이미 풀 수 있음: 추가 sample은 맞는 작업을 주로 중복합니다.
탐색 가능: 필요한 primitive가 있고 sampling 또는 verification이 올바른 조합을 드러낼 수 있습니다.
Capability 제한: generator가 가능한 경로를 거의 만들지 못하거나 verifier가 이를 구별하지 못합니다. Budget을 늘려도 포화할 수 있습니다.

추가 inference가 불필요한 수정이나 stopping 실패를 일으켜 일부 task의 정확도를 낮추는 overthinking 도 보고됩니다 [3]. “Compute가 많을수록 항상 좋다”는 외삽은 안전하지 않습니다.

Test-time budget allocation: 모형 시뮬레이션

Benchmark 결과가 아닌 설명용 모형입니다. 아래 곡선은 가정을 명시적으로 보여줍니다.

상대 compute budget: 24

Verifier 신뢰도: 82%

문제 난이도:

유용한 candidate가 하나 이상 존재: 59.8%

유용한 candidate를 실제로 선택: 49.0%

Compute cost index: 24/100

해석: Coverage가 포화하기 전까지 candidate 추가가 유효하며, 이후에는 verifier 오류가 병목이 됩니다.

3. Compute-Optimal Routing

$a$ 를 model, sample 수, temperature, 최대 token, search policy, verifier, stopping rule을 묶은 action이라고 하겠습니다.

a^*(x)=\arg\max_{a\in\mathcal A} \left[ \mathbb E\!\left[U(y,x)\mid x,a\right] -\lambda\,\mathbb E\!\left[C(a,x)\right] \right].

여기에 latency, safety, availability 제약을 둡니다. $U$ 는 task utility, $C$ 는 총 compute 또는 금전 비용, $\lambda$ 는 제품의 비용 가중치입니다. SLO가 있는 서비스라면 p95 latency budget 아래에서 기대 utility를 최대화하는 제약식이 운영하기 쉽습니다.

Production router는 보정되지 않은 “난이도” label 하나에 의존해서는 안 됩니다.

저비용 model의 calibrated success probability
작은 pilot sample 사이의 disagreement
Verifier margin 또는 entropy
Tool 필요 여부, prompt 길이, 예상 output 길이
고객 tier, deadline, 오류 비용

Routing은 off-policy evaluation이나 randomized shadow experiment로 검증합니다. 어려운 prompt만 비싼 policy로 보내면 raw success rate만으로 그 policy가 나빠 보이는 selection bias가 생깁니다.

4. Accounting: Token이 비용의 전부는 아니다

$N$ 개 candidate의 대략적인 원장은

C_{\text{total}} = C_{\text{shared prefill}}+ \sum_{i=1}^{N}C_{\text{decode},i}+ C_{\text{verification}}+ C_{\text{orchestration}}

입니다. Prefix sharing은 prefill과 KV memory를 줄일 수 있습니다. Parallel sampling은 wall-clock latency를 줄여도 총 FLOPs를 줄이지 않습니다. 다른 tokenizer나 model을 쓰는 verifier는 자체 formatted input과 attention mask가 필요합니다. Tool call에는 외부 latency와 비용이 추가됩니다. Early stopping은 output-length 분포와 selection pool을 모두 바꿉니다.

다음 실행 가능한 reference는 application contract를 분리합니다.

Interface 수준 예시입니다. Generator와 verifier는 serving stack에서 제공합니다. Generator token ID를 관계없는 verifier에 바로 넘길 수 있다고 가정하지 않습니다. Production code에는 tokenizer-native chat template, batching, retry, deterministic request ID, cancellation, safety check, calibrated score가 필요합니다.

from dataclasses import dataclass
from typing import Callable, Sequence


@dataclass(frozen=True)
class Candidate:
    text: str
    output_tokens: int
    finish_reason: str


@dataclass(frozen=True)
class Selection:
    answer: str
    score: float
    samples: int
    generated_tokens: int


def budgeted_best_of_n(
    prompt: str,
    generate: Callable[[str, int, int], Sequence[Candidate]],
    verify: Callable[[str, str], float],
    *,
    samples: int,
    max_new_tokens: int,
    token_budget: int,
) -> Selection:
    if samples < 1 or max_new_tokens < 1 or token_budget < 1:
        raise ValueError("budget은 양수여야 합니다")

    candidates = list(generate(prompt, samples, max_new_tokens))
    used = sum(item.output_tokens for item in candidates)
    if used > token_budget:
        raise RuntimeError(f"선언한 budget 초과: {used}>{token_budget}")
    if not candidates:
        raise RuntimeError("generator가 candidate를 반환하지 않았습니다")

    scored = [(verify(prompt, item.text), item) for item in candidates]
    score, winner = max(scored, key=lambda pair: pair[0])
    return Selection(winner.text, score, len(candidates), used)

이 경계는 budget 초과와 빈 candidate set을 관찰 가능하게 만듭니다. Selection threshold도 필요합니다. 모든 score가 낮다면 최댓값을 반환하기보다 abstention이나 상위 route가 안전할 수 있습니다.

5. Deliberation을 학습시키기

DeepSeek-R1 report는 두 recipe를 구분합니다 [2].

DeepSeek-R1-Zero 는 초기 supervised reasoning 단계 없이 base model에 reinforcement learning을 적용합니다. Report는 긴 reasoning과 self-reflection의 출현뿐 아니라 가독성과 language mixing 문제도 설명합니다.
DeepSeek-R1 은 cold-start data, reasoning-oriented RL, rejection sampling과 supervised fine-tuning, alignment-oriented RL을 포함하는 multi-stage pipeline입니다. “Pure RL”이라고 부르면 부정확합니다.

Group Relative Policy Optimization (GRPO)은 여러 response의 group-relative baseline을 추정해 별도로 학습한 critic model을 피합니다. Actor–critic PPO 대비 한 종류의 memory 비용을 없애지만 rollout 생성, policy/optimizer state, KL control에 사용하는 reference policy, verification 비용은 남습니다.

검증 가능한 reward는 수학과 code에서 만들기 쉽지만 함정이 있습니다. Unit test가 불완전할 수 있고 answer extractor가 잘못된 reasoning을 통과시킬 수 있으며, group의 모든 sample이 같은 reward를 받으면 normalization이 불안정해질 수 있습니다. Open-ended task에서는 judge-model bias와 rubric ambiguity가 목표에 포함됩니다.

Reasoning 길이는 관찰 가능한 비용 이지 search depth의 신뢰할 수 있는 proxy가 아닙니다. 답변 품질과 generated token, 총 FLOPs 또는 accelerator time, verifier 비용, latency, failure mode를 함께 보고해야 합니다.

6. Evaluation과 Release Gate

Budget을 조정하기 전에 evaluation matrix를 정의합니다.

Model capability frontier 아래와 위를 포함한 난이도·domain slice
Model size와 inference policy 사이 fixed-compute 비교
pass@ $N$ , best@ $N$ , verifier regret, calibration, abstention 품질
총 generated/verifier token, accelerator-seconds, p50/p95 latency, peak KV memory
Malformed trace, non-termination, reasoning 반복, answer flip, reward hacking, safety regression

Stopping과 rollback 기준을 미리 정합니다. Verified terminal answer에서 멈추고, 반복되는 semantic state를 제한하며, calibrated confidence가 낮으면 큰 model로 전환합니다. 비싼 route가 paired quality gain을 내지 못하거나 선언한 구간에서 latency/비용 한도를 넘으면 rollback합니다.

재구성 가능한 request ID, model/verifier version, sampling parameter, seed, routing feature, candidate hash, score, finish reason을 남겨야 합니다. 이 원장이 없으면 이상한 답변을 재현할 수 없고 router를 audit할 수도 없습니다.

7. 핵심 정리

Test-time compute는 긴 chain-of-thought의 다른 이름이 아니라 budget allocation discipline입니다. Generator가 유용한 대안을 만들 수 있고, verifier가 순위를 매길 수 있으며, marginal utility가 marginal cost보다 큰 요청에 router가 계산을 써야 효과가 있습니다. 다음 절에서는 자주 실제 병목이 되는 verifier를 다룹니다.

Quizzes

Quiz 1: pass@

N

이 best-of-

N

전달 품질의 상한인 이유는 무엇인가요?

Pass@ $N$ 은 acceptable candidate의 존재만 묻습니다. System은 이를 실제로 골라야 하며, sample 상관과 verifier 오류 때문에 best@ $N$ 이 훨씬 낮을 수 있습니다.

Quiz 2: Parallel sampling이 latency를 낮추면서 compute를 낮추지 못할 수 있는 이유는 무엇인가요?

Candidate를 동시에 실행하면 경과 시간은 줄지만 총 decode FLOPs, token, KV capacity, verifier work는 candidate 수에 따라 증가하기 때문입니다.

Quiz 3: 14배 작은 model 결과가 입증하지 않는 것은 무엇인가요?

보편적인 model 대체 법칙을 입증하지 않습니다. 작은 model이 non-trivial success를 보인 특정 task와 난이도 구간에 조건부인 결과입니다.

Quiz 4: Reasoning-token 수만 최적화하면 안 되는 이유는 무엇인가요?

긴 trace에는 유용한 search뿐 아니라 반복, 합리화, 잘못된 answer flip이 포함될 수 있습니다. 품질, verifier regret, 비용, latency, stopping을 함께 측정해야 합니다.

Quiz 5: 어려운 prompt만 비싼 policy에 보냈을 때 raw accuracy 비교가 편향되는 이유는 무엇인가요?

서로 다른 prompt 분포를 보기 때문입니다. Randomized/matched evaluation, off-policy estimator 또는 난이도별 paired comparison이 필요합니다.

References

Snell, C., Lee, J., Xu, K., & Kumar, A. (2024). Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters. arXiv:2408.03314.
DeepSeek-AI. (2025). DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning. arXiv:2501.12948.
Ghosal, S. S., et al. (2025). Does Thinking More always Help? Mirage of Test-Time Scaling in Reasoning Models. arXiv:2506.04210.
Brown, N., et al. (2024). Large Language Monkeys: Scaling Inference Compute with Repeated Sampling. arXiv:2407.21787.