기술 요약: Parason – LLM 추론에서의 서브태스크 및 트라이얼 병렬성 규명

1. 문제 정의

Chain-of-Thought (CoT) 프롬프팅과 OpenAI o1, DeepSeek-R1 같은 시스템을 포함한 최근의 대규모 언어 모델(LLM) 추론 기술의 발전은, 테스트 타임 연산량(test-time compute)을 늘리는 것이 복잡한 수학적 및 논리적 과업의 성능을 크게 향end시킨다는 것을 입증했습니다. 그러나 표준적인 자기회귀 디코딩(autoregressive decoding)은 이러한 긴 추론 궤적을 순차적으로 실행합니다. 이는 어려운 문제에서 추론 궤적이 수십만 또는 수백만 토큰까지 늘어날 수 있음을 의미하며, 이로 인해 "더 오래 생각하기(think longer)" 전략은 인터랙티브 에이전트나 지연 시간(latency)에 민감한 애플리케이션에서 실용성이 떨어지는 심각한 병목 현상을 초래합니다.

병렬 추론은 자연스러운 해결책을 제시하지만, 기존 시스템은 주로 고수준의 과업을 독립적인 조각으로 분해하는 **서브태스크 병렬성(Subtask Parallelism)**에 집중해 왔습니다(예: 합계의 서로 다른 부분을 계산). 이러한 접근 방식은 보편적인 형태의 병렬성인 **트라이얼 병렬성(Trial Parallelism)**을 간과합니다. 트라이얼 병렬성에서 모델은 어떤 경로가 작동할지 알 수 없는 상황에서 여러 개의 가설적이고 경쟁적인 가설을 병렬로 탐색하여 이를 검증합니다. 이는 어려운 추론 과정에서 흔히 나타나는 행동입니다. 기존 방법들은 모든 병렬 브랜치를 독립적인 전체 궤적으로 취급하거나, 필수적인 서브태스크와 가설 검증을 위한 트라이얼(trial)을 구분하지 못하여 불필요한 연산을 발생시키거나 지연 시간을 제어하지 못하는 문제가 있습니다.

2. 방법론: Parason 프레임워크

저자들은 서브태스크 및 트라이얼 병렬성을 모두 드러내고 활용하는 훈련 및 추론 공동 설계(co-design) 프레임워크인 Parason을 소개합니다. 이 방법론은 세 가지 핵심 구성 요소로 이루어집니다.

A. 병렬 추론의 의미론적 분류 (Semantic Taxonomy)

본 논문은 실행 의미론에 따라 두 가지 상호 보완적인 병렬 형태를 구분합니다.

• 서브태스크 병렬성 (AND-branch): 문제는 독립적인 하위 목표($g_1, \dots, g_k$)로 분해됩니다. 모든 브랜치가 필요하며, 최종 답안을 형성하기 위해 그 결과들이 반드시 결합되어야 합니다. 이는 기존의 적응형 병렬 시스템에서 지배적인 형태입니다.
• 트라이얼 병렬성 (OR-branch): 모델이 솔루션 경로에 대해 불확실성을 겪는 상황입니다. 모델은 서로 경쟁하는 시도들($a_1, \dots, a_k$)을 실행하여 다양한 가설을 테스트합니다. 서브태스크와 달리 모든 브랜치가 필요한 것은 아니며, 시스템은 유용한 결과를 유지하기 위해 탐색된 궤적들을 추론 이력에 통합합니다. 이는 강력한 추론 모델이 보이는 "시도하고, 막다른 길을 감지하고, 수정하는" 행동을 모방합니다.

DeepSeek-R1 및 DeepSeek-V4 모델의 Humanity's Last Exam (HLE) 데이터셋에 대한 추론 궤적의 경험적 분석 결과, 트라이얼 병렬성이 병렬화 가능한 추론 단계의 대다수(65.5%~73.8%)를 차지하며, 어려운 문제에서는 서브태스크 병렬성을 크게 상회한다는 것이 밝혀졌습니다.

B. 구조화된 병렬 궤적 형식 (CFG)

이러한 모드들을 실행 가능하게 만들기 위해, Parason은 순차적 추론 궤적을 구조화된 병렬 궤적으로 변환하는 문맥 자유 문법(Context-Free Grammar, CFG)을 정의합니다.

• 태그(Tags): 이 형식은 특정 태그를 사용합니다: 영역을 표시하는 <Parallel>, 영역의 목적을 설명하는 <Outlines>, 브랜치 유형을 표시하는 <Subtask> 및 <Trial>, 그리고 브랜치의 결과를 저장하는 <Thread>.
• 실행: 이 구조를 통해 추론 엔진은 궤적을 파싱하고, 각 브랜치(서브태스크 또는 트라이얼)에 대해 독립적인 워커를 할당한 뒤, 모델 아키텍처를 수정하지 않고도 결과를 메인 궤적으로 반환할 수 있습니다. 이 시스템은 SGLang과 통합되며, 유효한 태그 중첩을 강제하기 위해 XGrammar를 사용합니다.

C. 병렬성 인지 강화 학습 (PA-GRPO)

저자들은 정확도, 지연 시간, 그리고 병렬성 활용도를 최적화하는 다중 목적 강화 학습 알고리즘인 PA-GRPO를 제안합니다. 궤적 $i$에 대한 보상 함수($R_i$)는 다음과 같이 정의됩니다.
$$R_i = -1 + 2 \times \mathbb{1}(\text{correct}_i) \times \left( 1 - \alpha f\left(\frac{T_i - \mu_T}{\sigma_T}\right) + \beta_{\text{subtask}} f\left(\frac{R^{\text{subtask}}_i - \mu_s}{\sigma_s}\right) + \beta_{\text{trial}} f\left(\frac{R^{\text{trial}}_i - \mu_r}{\sigma_r}\right) + \min(\rho \cdot \eta(s), \rho_{\text{clip}}) \right)$$

• 정확도 (Correctness): 주요 신호이며, 오답에는 음수의 기본 보상이 주어집 hold.
• 지연 시간 페널티 (Latency Penalty): 임계 경로(critical-path) 토큰 수($T_i$)에 페널티를 부여하여 실제 실행 시간(wall-clock time)을 단축하도록 유도합니다.
• 병렬성 인센티브 (Parallelism Incentives): $\beta_{\text{subtask}}$와 $\beta_{\text{trial}}$은 모델이 각각의 병렬 모드를 활용하도록 독려합니다. 저자들은 이들이 서로 다른 목표를 가진다고 언급합니다. 즉, 트라이얼 병렬성은 총 토큰 수를 희생하여 탐색 폭을 넓힘으로써 정확도를 높이는 반면, 서브태스크 병렬성은 가장 긴 경로를 압축하여 지연 시간을 줄입니다.
• 가속 보상 (Acceleration Reward): 전체 생성 길이 대비 임계 경로의 단축을 선호하는 클리핑된 항입니다.

3. 주요 기여

1. 병렬 추론의 분류 체계: 본 논문은 현재의 병렬 추론 시스템에서 누락된 구성 요소인 트라이얼 병렬성을 식별하였으며, 이것이 어려운 추론 과업(HLE 및 OpenMath 데이터셋에서 50% 이상)에서 병렬화 가능한 연산의 대다수를 차지함을 입설명했습니다.
2. Parason 프레임워크: 순차적 궤적을 도구 호출(tool call)을 통해 표준 추론 엔진에서 실행 가능한 문법 제약 병렬 궤적으로 변환하는 시스템으로, 런타임의 깊은 수정 없이도 작동합니다.
3. PA-GRPO 알고리즘: 정답 정확도, 임계 경로의 토큰 경로에 따른 지연 시간, 그리고 서브태스크 및 트라이얼 병렬성의 균형 잡힌 활용을 공동으로 최적화하는 강화 학습 목적 함수입니다.
4. 경험적 검증: 실험 결과, Parason은 수학적 벤치마크(AIME24, AIME25, Math500, AMC)에서 경쟁력 있는 정확도를 유지하면서 평균 약 1.7배의 가속을 달 achieves 했습니다. 지연 시간 제한 설정(예: 2048 토큰)에서 Parason은 표준 지도 미세 조정(SFT) 베이스라인보다 월등한 성능을 보입니다.

4. 결과

• 정확도: Parason은 AIME25(70.6%) 및 AMC(97.5%)에서 8B 모델을 사용하여 나열된 병렬 시스템 중 최고 수준의 성능을 달성했으며, 일부 지표에서는 더 큰 32B 모델 베이스라인을 능가했습니다.
• 지연 시간 및 가속:
  • 시스템은 평균 토큰 레벨 가속 비율 1.7배를 달성했습니다.
  • 지연 시간 제한 시나리오(2048 토큰 예산)에서, 가장 우수한 서브태스크 인지 모델은 AIME24에서 34.7%의 정확도에 도달하여, SFT 전용 베이스라인의 16.8%를 크게 앞질렀습니다.
  • 문제가 어려워질수록 병렬화 가능한 작업이 많아집니다. 생성되는 총 토큰 수는 난이도에 따라 증가하지만, 가장 긴 토кен 경로는 훨씬 느리게 성장하여 난이도 전반에 걸쳐 1.70–1.74배의 안정적인 가속 비율을 유지합니다.
• 어블레이션 (Ablation): 연구에 따르면 트라이얼 보상($\beta_{\text{trial}}$)은 정확도 향상에 가장 효과적이며, 서브태스크 보상($\beta_{\text{subtask}}$)은 지연 시간 감소에 더 효과적입니다.

5. 의의 및 주장

본 논문은 Parason이 추론을 단순히 순차적인 프로세스나 단순한 과업 분해로 보는 관점에서 벗어난 변화를 나타낸다고 주장합니다. 트라이얼 병렬성을 명시적으로 인식하고 활용함으로써, Parason은 현재의 병렬 추론 시스템에 있는 "빠진 조각"을 해결합니다.

저자들은 본 연구의 성과를 다음과 같이 정리합니다:

• 이론과 실제 사이의 간극 해소: 이론적인 속도 향상을 보고하거나 복잡한 엔진 수정이 필요한 이전 연구들과 달리, Parason은 CFG와 도구 호출 실행을 사용하여 SGLang과 같은 현대적 추론 엔진에서 직접 실행 가능합니다.
• 지연 시간-정확도 파레토 최적선(Pareto frontier) 개선: 어려운 추론이 반드시 더 긴 직렬 대기 시간을 요구하는 것은 아니며, 많은 연산을 임계 경로 밖으로 옮길 수 있음을 입증했습니다.
• 어려운 추론의 본질 강조: 어려운 추론은 단순히 분해(Subtask)의 문제가 아니라, 불확실한 경로를 탐색하고 정교화(Trial)하는 과정임을 보여주며, 이는 기존 시스템들이 거의 무시했던 행동입니다.

결론적으로, 저자들은 현재의 평가가 수학적 추론과 8B 규모의 모델에 집중되어 있다는 한계를 언급하며, 향-후 더 넓은 도메인과 모델 크기에 걸쳐 이러한 패턴을 검증하기 위한 후속 연구가 필요하다고 밝혔습니다.