Test-time scaling (TTS)

Test-time scaling (TTS)

Contents

1. 개요
2. 사용 이유
3. TTS 방법론
   1. Breadth (가로 확장) – 다중 샘플 & 표결
      1. Self-Consistency
      2. Best-of-N + Reranking
   2. Depth (세로 확장) – 더 깊게 생각하기
      1. Longer Inference / Chain-of-Thought Scaling
      2. Deliberate Decoding / Deliberation Networks
      3. Reflection / Self-Consistency in Depth
      4. Budget Forcing / Test-time Scaling (Depth Control)
   3. Search(탐색 구조화) – 트리/그래프 탐색
   4. Adaptive Budget – 난이도에 따라 다르게
4. Examples

1. 개요

(핵심 아이디어) 높은 성능을 위해, “더 오래 + 더 넓게” 생각하자!

• a) 더 “많은” 샘플 (token) 생성
• b) 더 “깊은” 탐색

TTS 설명

• (1) 정의: “ inference (test) 시점에 추가 연산 “ 통해 성능을 끌어올리는 방법론
• (2) 기존 vs. TTS
  • (기존) Train의 compute를 강조
  • (TTS) “Inference“의 compute를 강조

2. 사용 이유

난이도가 높은 inference에서 “한 번”의 forward: 불안정한 결과

\(\rightarrow\) “여러 경로”를 탐색/평가하면 더 좋아질 수 있음을 확인함!

e.g., OpenAI o1 계열

• Inference 시 생각 (연산) 시간을 더 들여 정확도를 올리는 접근

3. TTS 방법

(1) Breadth (가로 확장) – 다중 샘플 & 표결

a) Self-Consistency

• 간단하지만 강력한 방법론!

• Procedure
  • Step 1) 같은 문제를 temperature sampling으로 N번 풀기
  • Step 2) 다수결/스코어로 최종 답 채택
• Reference:
  • Self-Consistency Improves Chain of Thought Reasoning in Language Models (https://arxiv.org/pdf/2203.11171)

b) Best-of-N + Reranking

• Self-Consistency 자체가 일종의 Best-of-N 아이디어를 포함
• 차이점? 더 일반적으로 후보군 생성 → “검증/채점기로 reranking”
• Procedure
• Step 1) 후보 N개 생성

• Step 2) “외부 채점기” (Rule/Scorer/LLM-judge)로 최고 후보 선택

• Reference
  • STaR: Bootstrapping Reasoning With Reasoning (https://arxiv.org/pdf/2203.14465)
    • 여러 reasoning 후보를 생성 + 정답/검증 기준에 맞는 경로를 재선택하여 학습 데이터에 반영
  • Self-Refine: Iterative Refinement with Self-Feedback (https://arxiv.org/pdf/2303.17651)
    • 후보 답안을 생성한 뒤 모델 스스로 피드백을 주고, 그에 따라 수정/재랭킹하는 구조
  • Competition-Level Code Generation with AlphaCode (https://arxiv.org/pdf/2203.07814)
    • 수십만 code 후보 생성 후, test case 채점기로 성능 좋은 후보만 채택

(2) Depth (세로 확장) – 더 깊게 생각하기

더 긴 inference token

• e.g., reasoning.effort을 높이거나, 단계별 사고를 장려!

resp = client.responses.create(
    model="o1",
    input=[{"role": "user", "content": "어떤 수학 문제"}],
    reasoning={"effort": "high"},   # ← 깊게 생각
    max_output_tokens=800,
)

a) Longer Inference / Chain-of-Thought Scaling

• Procedure
  • Step 1) 모델이 답을 내기 전, “더 많은 reasoning tokens”을 생성하도록 유도
  • Step 2) “긴” 사고 과정 \(\rightarrow\) 정답률을 향상 유도!
• Reference
  • Chain-of-Thought Prompting Elicits Reasoning in Large Language Models (https://arxiv.org/pdf/2201.11903)
    • LLM이 단계별 추론(CoT)을 거치면 복잡한 수학/논리 문제에서 성능이 급상승
  • Scaling Instruction-Finetuned Language Models (a.k.a. FLAN-PaLM, https://arxiv.org/pdf/2210.11416)
    • 모델 크기뿐 아니라 추론 token 길이를 늘릴 때 성능이 함께 스케일링됨을 보고

b) Deliberate Decoding / Deliberation Networks

• Procedure

  • Step 1) 모델이 초안(draft) 답변을 생성
  • Step 2) 2-pass 구조로 초안을 검토·수정 (한 경로를 더 정교화)

• Reference

  • Deliberation Networks: Sequence Generation Beyond One-Pass Decoding (https://papers.nips.cc/paper_files/paper/2017/file/c6036a69be21cb660499b75718a3ef24-Paper.pdf)

    • NMT에서 제안된 2-pass 디코딩, 이후 LLM reasoning에도 적용

      In this work, we introduce the deliberation process into the encoder-decoder framework and propose deliberation networks for sequence generation. A deliberation network has two levels of decoders, where the f irst-pass decoder generates a raw sequence and the second-pass decoder polishes and refines the raw sentence with deliberation. Since the second-pass deliberation decoder has global information about what the sequence to be generated might be, it has the potential to generate a better sequence by looking into future words in the raw sentence.
      

  • Think Twice: Deliberation Improves Large Language Models (https://arxiv.org/pdf/2311.10227)

    • LLM이 “다시 생각하기” 루프를 거치면 정밀한 추론 성능이 향상

c) Reflection / Self-Consistency in Depth

• Procedure

  • Step 1) 모델이 답안을 낸 뒤, 본인 스스로 자기 피드백(Reflection)을 생성
  • Step 2) 피드백을 반영해 다시 수정·보강 (깊이를 늘려 정답 안정화)

• Reference

  • Reflexion: Language Agents with Verbal Reinforcement Learning (https://arxiv.org/pdf/2303.11366)

    • Agent가 답을 낸 뒤, 자기 피드백을 통해 점진적으로 답변 품질을 개선

    We propose Reflexion, a novel framework to reinforce language agents not by updating weights, but instead through linguistic feedback. Concretely, Reflexion agents verbally reflect on task feedback signals, then maintain their own reflective text in an episodic memory buffer to induce better decision-making in subsequent trials. 
    

  • Self-Refine: Iterative Refinement with Self-Feedback (https://arxiv.org/pdf/2303.17651)

    • 후보 답안을 생성한 뒤, 모델 스스로 피드백을 주고, 그에 따라 수정/재랭킹하는 구조
    • (Breadth에도 해당되지만) 반복적 자기수정은 한 경로를 점점 깊게 발전시키는 형태도 가능

d) Budget Forcing / Test-time Scaling (Depth Control)

• Procedure
  • Step 1) 추론 시 token 예산(budget)을 강제로 크게 부여
  • Step 2) 모델이 더 길게 생각하도록 유도 → 성능 우상향 곡선 확보
• Reference
  • s1: Simple test-time scaling (https://arxiv.org/pdf/2501.19393)
    • 단순 SFT(1K 데이터) + budget forcing만으로도 o1류 모델처럼 더 깊게 생각할수록 성능이 오르는 곡선 재현

(3) Search(탐색 구조화) – 트리/그래프 탐색

• Tree-of-Thought:
  • 중간 생각을 분기해 여러 inference 나무를 탐색
  • 합의/재귀적 수정으로 품질을 높임.
• Forest-of-Thought:
  • 희소 활성화·동적 자기수정·합의 유도를 통해 효율/정확도 개선을 보고.

(4) Adaptive Budget – 난이도에 따라 다르게

동적 스케일링

• “쉬운” 문제는 샘플/token을 “적게”
• “어려운” 문제는 샘플/token을 “많게”

4. Examples

예시 A: Self-Consistency (다수결)

• 상황: 수학 단답형.

• 방법: 같은 프롬프트를 temperature>0로 \(N\)회 생성

  → 정답 후보들 중 최빈값 채택.

def self_consistent_solve(llm, prompt, n=10, temp=0.7):
    answers = []
    for _ in range(n):
        ans = llm(prompt, temperature=temp)
        answers.append(extract_final_answer(ans))
    return majority_vote(answers)

예시 B: Best-of-N + 재랭킹(검증기 결합)

• 상황: 코드 문제.
• 방법: 후보 코드 N개 생성 → test 케이스 실행/정적 분석/LLM-judge 점수로 1위 선택.

cands = [gen_code(prompt) for _ in range(N)]
scores = [unit_test_score(code) for code in cands]  # 또는 LLM-judge 점수
best = cands[np.argmax(scores)]

예시 C: Forest-of-Thought (탐색 + 합의)

• 상황: 단계적 “논증”이 필요한 “복잡한 문제”
• 방법: 여러 inference 나무를 병렬로 확장 → 중간에 합의/자기수정 → 최종 정리
• 포인트: 탐색을 구조화해 단일 체인 한계를 보완(성능↑, 다만 구현 복잡/비용↑)