적응형 병렬 추론: 효율적인 추론 확장의 차세대 패러다임

적응형 병렬 추론: 효율적인 추론 확장의 차세대 패러다임

TL;DR

Adaptive Parallel Reasoning (APR)은 대형 언어 모델(LLM)이 추론 시점에 병렬 연산과 순차 연산 사이에 계산 자원을 동적으로 할당할 수 있게 하는 새로운 패러다임입니다. 모델이 언제 독립적인 추론 스레드를 생성하고 이를 어떻게 조정할지 스스로 결정하도록 함으로써, APR은 전체 지연 시간을 줄이고 긴 순차 추론 체인에서 발생하는 "context-rot"을 방지합니다.

순차 추론 확장의 문제점

순차 추론은 탐색량에 비례해 선형적으로 확장되며, 다음과 같은 세 가지 주요 병목 현상을 초래합니다:

  1. Context-Rot: 모델이 더 많은 중간 탐색 경로를 생성할수록 유용한 정보와 방해 요소를 구분하기 어려워져 성능이 저하됩니다.
  2. Latency: 추론 시간은 추론 길이에 비례해 증가하므로 복잡한 작업에서는 수십 분 혹은 수시간의 대기 시간이 발생할 수 있습니다.
  3. Compute Intensity: 출력 시퀀스 길이에 따라 확장되면 추론이 느려지고 신뢰성이 떨어집니다.

병렬 추론은 모델이 서로의 컨텍스트에 의존하지 않고 독립적인 스레드들을 동시에 탐색하도록 함으로써 이러한 문제들을 해결합니다.

고정 병렬성에서 적응형 제어로

이전의 병렬 추론 방법들은 주로 모델 외부에서 강제된 구조에 의존했습니다. APR은 이 제어권을 모델 자체로 이전합니다.

비적응형 접근법의 한계

  • Simple Fork-and-Join (Self-consistency, BoN): 경로를 독립적으로 샘플링하기 때문에 중복 계산이 많이 발생합니다.
  • Heuristic-based Structured Search (Tree/Graph/Skeleton of Thoughts, MCTS): 문제 분해 전략에 대한 사전 지식이 필요하지만, 모든 문제에 대해 이를 알 수는 없습니다.
  • Fixed-Stage Variants (ParaThinker, GroupThink, Hogwild! Inference): 문제에 따라 이점이 있든 없든 특정 병렬 구조를 강제합니다.

APR의 장점

적응형 병렬 추론은 문제 복잡도에 따라 모델이 병렬화 수준을 스스로 결정하도록 합니다. 이는 다음 세 가지 핵심 이점을 제공합니다:

  • 도메인 특화 휴리스틱 불필요: 모델이 강화 학습(RL)을 통해 일반적인 분해 전략을 학습하고, 동시 자기 검증과 같은 새로운 패턴을 스스로 발견합니다.
  • 중복 감소: 모델은 Best-of-N(BoN)과 달리 분기 전에 고유하고 겹치지 않는 하위 작업을 생성할 수 있습니다.
  • 동적 할당: 간단한 문제에 대해서는 병렬화를 선택하지 않아 불필요한 오버헤드를 피합니다.

적응형 병렬성을 위한 추론 시스템

적응형 병렬 분기는 일반적으로 포크‑조인 설계 방식을 따릅니다: 모델이 문제를 동시에 수행 가능한 하위 작업으로 포크하고, 최종 답변으로 조인합니다. 주요 기술적 과제는 KV 캐시 수준에서 결과를 집계하는 것입니다.

엔진 수정 방식 (Multiverse)

Multiverse, Parallel‑R1, NPR과 같은 방법은 추론 엔진을 수정하여 독립 스레드들의 KV 캐시 비연속 메모리 블록을 복사·붙여넣기합니다.

  • Trade‑offs: 두 번째 프리필(pre‑fill)을 피할 수 있지만, 잘못된 포인터나 캐시 퇴출 등 시스템 취약성이 증가하고, 위치 인코딩의 분포 이동(distributional shift)으로 인해 광범위한 학습 및 수정된 어텐션 마스크가 필요합니다.

엔진 비종속 방식 (ThreadWeaver)

ThreadWeaver는 오케스트레이션을 클라이언트 측으로 옮깁니다. 클라이언트가 독립 브랜치의 텍스트 출력을 연결하고, 엔진은 최종 결론을 위한 KV 캐시를 생성하기 위해 두 번째 프리필을 수행합니다.

  • Trade‑offs: 프리필 단계에서 약간의 계산 중복이 발생하지만, 디코딩보다 훨씬 저렴하기 때문에 효율성을 유지합니다. 엔진 수정이 필요 없으며 표준 인과(attention) 모델과도 호환됩니다.

학습 및 보상 설계

모델이 병렬 제어 흐름 토큰을 사용하도록 가르치려면 시연 데이터와 구체적인 인센티브 구조가 모두 필요합니다.

시연 및 SFT

Supervised Fine‑Tuning(SFT)은 병렬 제어 흐름의 구문을 가르치는 데 사용됩니다. SFT가 새로운 추론 능력을 유도하는지, 기존 능력을 특정 토큰 구문에 맞추는 것인지에 대한 논쟁이 지속되고 있습니다.

보상 메커니즘

단순히 결과 정확도만으로는 병렬화를 충분히 장려하기 어렵습니다. 연구자들은 다양한 보상 설계를 탐색했습니다:

  • Structure‑only Rewards: 스레드 수나 구조 사용을 보상하면 모델이 쓸모없는 스레드를 생성해 쉽게 "게임"할 수 있습니다.
  • Critical Path Rewards: 지연 시간을 최적화하기 위해, 보상은 가장 긴 인과 의존 토큰 시퀀스(critical path)에 초점을 맞춥니다. ThreadWeaver는 $1 - L_{\mathrm{critical}} / L_{\mathrm{total}}$ 형태의 보상을 사용하며, critical path가 전체 토큰 비율에서 작아질수록 보상이 증가합니다.
  • Correctness Gating: 비효율적이지만 틀린 경로에 보상이 주어지는 것을 방지하기 위해, 병렬화 보상은 최종 답변이 정확할 때만 부여됩니다: $R = \mathbf{1}(\text{Correctness}) + \mathbf{1}(\text{Correctness}) \times (\text{parallelization metric})$.

성능 및 남은 질문

APR의 평가 기준은 목표에 따라 다릅니다. Multiverse와 ThreadWeaver는 정확도와 지연 시간을 중시하고, NPR은 Genuine Parallelism Rate에 초점을 맞추며, Parallel‑R1은 APR을 중간 학습 단계의 탐색 스캐폴드로 활용해 RL 이후 성능을 끌어올립니다.

남은 과제

  • Inference vs. Training: 추론 시점의 병렬화가 일관되게 정확도를 향상시키는지, 아니면 주된 가치는 학습 단계의 탐색 스캐폴드인지 명확하지 않습니다.
  • Stability: 병렬화 보상이 완화되면 모델이 다시 순차 추론으로 회귀하는 경향이 있습니다.
  • Hardware Awareness: 향후 학습에서는 사용 가능한 연산 예산에 기반해 하드웨어 인식 병렬화 결정을 내릴 수 있습니다.
  • Depth of Parallelism: 현재 구조는 평면(flat) 형태이며, Recursive Language Models(RLMs)를 통한 깊이 1 이상의 재귀 병렬화 탐색이 다음 단계가 될 수 있습니다.

Sources