시간적 신뢰도로 병렬 추론 비용 줄이기

왜 중요한가

Parallel reasoning은 여러 추론 경로를 활용해 정확도와 견고성을 높이지만, 고정된 branch 수와 생성 길이는 수렴한 경로의 중복 계산을 초래합니다. ParaTempo는 여러 시점의 중간 답안 분포에서 branch별 수렴 정도를 계산하고, 그 신호 하나로 pruning·retirement·forking·조기 종료를 수행해 정확도 경쟁력을 유지하면서 평균 latency를 21.8–32.2%, 총 토큰 사용량을 18.1–30.3% 줄였습니다.

핵심 기여

시간에 따른 답안 수렴 신호

각 branch를 500개 생성 토큰마다 probe해 중간 답안 확률분포를 얻고, 최근 관측을 sliding window로 집계해 temporal confidence를 계산합니다. 이 신호는 단일 시점의 불안정한 변화보다 장기적인 답안 집중도를 반영합니다.

비동기 branch 생명주기 제어

Temporal confidence가 낮은 branch는 prune하고, dominant answer의 확률이 연속 probe 동안 높게 유지된 branch는 retire합니다. 확보한 계산 슬롯은 confidence가 높은 donor branch에서 prefix를 상속한 새 branch를 fork하는 데 사용합니다.

신뢰도 가중 전역 투표

Active와 retired branch의 dominant answer를 top-1 probability로 가중해 투표하고, 특정 답안의 누적 투표량이 조기 종료 기준을 넘으면 전체 생성을 끝냅니다. 이 과정은 branch별 독립 제어와 최종 ensemble 결합을 함께 수행합니다.

추론 비용과 정확도의 실험 검증

AIME 2026, HMMT November 2025, HMMT February 2026, GPQA Diamond에서 Qwen3.5-35B-A3B와 GPT-OSS-20B를 평가했습니다. ParaTempo는 Self-Consistency 대비 경쟁력 있는 정확도를 유지했고, Parallel-Probe 대비 정확도를 3.8–3.9 percentage points 높이면서 낮은 latency를 기록했습니다.

핵심 아이디어 이해하기

Parallel reasoning은 하나의 문제를 여러 branch로 나눠 각각 다른 추론 경로를 생성하고 마지막에 답안을 합칩니다. 그러나 모든 branch를 같은 길이까지 실행하면 이미 답안이 안정된 branch도 토큰을 계속 소비하고, 아직 불확실한 branch와 동일한 계산 예산을 받게 됩니다.

ParaTempo는 각 branch의 현재 reasoning prefix 뒤에 answer-forcing suffix를 붙여 잠정 답안 분포를 probe합니다. 한 번의 probe만 보면 중간 추론의 일시적인 흔들림에 영향을 받으므로, 최근 여러 probe의 분포를 평균내고 그 결과가 한 답안에 집중되는 정도를 temporal confidence로 계산합니다.

계산된 confidence가 낮으면 해당 branch를 prune해 자원을 회수하고, dominant answer의 확률이 여러 probe 동안 충분히 높으면 branch를 retire해 투표 증거만 보존합니다. 회수한 슬롯은 confidence가 높은 branch의 prefix와 독립 sampling seed를 이용한 새 branch에 배정하므로, 수렴한 경로의 중복 생성을 줄이면서 탐색 다양성을 유지합니다.

마지막으로 각 branch의 dominant answer를 top-1 probability로 가중해 투표합니다. 특정 답안에 대한 가중 투표가 전체 eligible branch 수에 비례한 조기 종료 기준에 도달하면 모든 branch를 기다리지 않고 추론을 끝내므로, 병렬 처리의 critical path와 총 생성 토큰을 함께 줄입니다.

방법론

입력 문제마다 K=16개의 독립 reasoning branch를 생성하고, 각 branch가 τ=500개의 토큰을 추가로 생성할 때마다 현재 prefix에서 중간 답안 분포를 얻습니다. 현재 prefix 뒤에 Final answer: 같은 answer-forcing suffix를 붙인 뒤 top-L=20 후보의 log probability를 answer bucket으로 변환하고, 후보 확률을 softmax 방식으로 정규화합니다.

최근 W개 probe 분포를 평균내어 집계분포 g를 만들고, 그 엔트로피의 지수 음수인 $C_{i,t}=\exp(-H(g_{i,t}))$ 를 temporal confidence로 사용합니다. 분포가 한 답안에 집중되면 엔트로피가 낮아져 confidence가 1에 가까워지고, 여러 후보로 퍼지면 confidence가 낮아집니다.

처음 N_warm=15개 probe 동안에는 branch를 개입 없이 실행해 현재 문제의 confidence 분포를 수집합니다. 그 분포의 1-q_prune 분위수로 θ_prune을 정하므로, 모든 문제와 모델에 같은 절대 threshold를 강제하지 않습니다.

Warmup 이후 confidence가 θ_prune보다 낮은 branch는 prune하고, 최근 X=9개 probe에서 dominant answer의 확률이 매번 θ_retire=0.90 이상인 branch는 retire합니다. Pruned branch가 슬롯을 반환하면 temporal confidence가 가장 높은 eligible donor의 prefix를 독립 sampling seed로 복제해 새 branch를 fork합니다.

최종 투표에서는 branch별 dominant answer와 top-1 probability c를 사용해 $V_t(a)=\sum_i c_{i,t}\mathbf{1}\{\hat{y}_{i,t}=a\}$ 를 계산합니다. 어떤 답안의 투표량이 $\gamma_{ES}|\mathcal{B}_t|$ 이상이 되면 조기 종료하고, 그렇지 않으면 active branch가 사라지거나 예산이 소진될 때 가장 큰 투표량의 답안을 반환합니다.

주요 결과

Qwen3.5-35B-A3B에서 ParaTempo는 네 benchmark 평균 정확도 71.1%를 기록해 Self-Consistency의 72.2%와 1.1 percentage points 차이를 보였습니다. 동시에 평균 latency를 21.8%, 총 생성 토큰을 30.3% 줄여 고정 예산 병렬 추론의 정확도 이점을 더 적은 계산으로 유지했습니다.

Parallel-Probe와 비교하면 Qwen3.5-35B-A3B에서 정확도를 3.9 points 높이고 latency를 10.6% 줄였으며, GPT-OSS-20B에서는 정확도를 3.8 points 높이면서 sequential cost가 비슷했습니다. 네 benchmark의 개별 결과에서도 ParaTempo는 Qwen3.5-35B-A3B 기준 AIME26 83.3%·198.4초·161.9k tokens, HMMT25 73.3%·205.7초·166.6k tokens, HMMT26 42.4%·208.0초·168.9k tokens, GPQA 85.4%·161.1초·130.4k tokens를 기록했습니다.

사전 분석에서 token entropy와 perplexity의 volatility는 각각 0.54와 0.56이었고, 미래 안정성에 대한 AUC는 0.58과 0.57에 그쳤습니다. Instantaneous answer confidence는 volatility 0.26, AUC 0.71이었으며, temporal confidence는 여러 probe를 집계해 단일 시점 신호보다 더 안정적이고 미래 dominant answer 유지 여부를 더 잘 예측했습니다.

HMMT25 ablation에서는 pruning을 제거하면 latency가 205.7초에서 233.0초로 증가했고, retirement를 제거하면 정확도가 73.3%에서 66.7%로 6.6 points 하락했습니다. Forking을 끄면 latency와 토큰 수는 줄지만 정확도가 70.0%로 3.3 points 낮아져, 회수한 자원을 새 탐색에 재투입하는 과정이 solution diversity 유지에 필요함을 확인했습니다.

기술 상세

중간 답안 probe는 현재 reasoning prefix에 answer-forcing suffix를 붙이고, top-L=20 후보 토큰의 log probability를 answer bucket으로 매핑한 뒤 정규화합니다. 후보 v의 log probability를 ℓ(v)라고 할 때 $p(v)=\exp(\ell(v))/\sum_u\exp(\ell(u))$ 를 계산하며, 각 입력값은 후보별 log probability이고 출력은 후보 답안 확률분포입니다. 예를 들어 한 probe의 두 후보 log probability가 같으면 정규화 후 두 후보가 각각 0.5가 되고, 한 후보의 log probability가 더 높으면 해당 후보의 확률 mass가 커집니다.

Temporal aggregation은 sliding window 안의 probe 분포를 평균내는 연산입니다. W=7이면 현재 probe를 포함한 최근 최대 7개 분포에서 각 answer bucket의 확률을 평균내며, 특정 probe에만 나타난 후보는 해당 시점에 0 probability를 갖습니다. 이후 $C=\exp(-H(g))$ 를 계산하므로 단일 후보에 확률 1이 모이면 H=0, C=1이 되고, 확률이 여러 후보에 균등하게 분산될수록 C가 낮아집니다.

Pruning threshold는 warmup 동안 수집한 confidence 집합의 1-q_prune 분위수로 정합니다. 기본 q_prune=0.50이므로 warmup confidence 분포의 중앙 분위수를 기준으로 낮은 confidence branch를 제거하며, post-fork probe history가 충분히 쌓이기 전에는 이 조건을 적용하지 않습니다. Retirement는 최근 X=9개 probe에서 top-1 probability가 θ_retire=0.90 이상인지 확인하고, 조건을 만족한 branch의 dominant answer와 confidence weight를 보존한 채 decoding만 중단합니다.

Forking은 eligible donor 중 temporal confidence가 가장 높은 branch를 선택해 prefix를 상속하고 독립 sampling seed로 계속 생성합니다. 따라서 입력은 donor의 부분 추론과 반환된 계산 슬롯이고, 처리는 prefix 복제와 새 sampling이며, 출력은 기존 답안 가설을 활용하는 별도 탐색 branch입니다. 전역 종료는 답안 a의 weighted vote mass가 $\gamma_{ES}|\mathcal{B}_t|$ 이상인지 검사하며, 기본 γ_ES=0.50은 eligible branch 수에 비례한 누적 증거 기준을 뜻합니다.

실험은 vLLM, 단일 NVIDIA A100 80GB GPU, 최대 trajectory 길이 16,384 tokens, temperature 0.6, nucleus sampling p=0.95, K=16에서 수행했고 모든 결과는 네 번의 독립 실행 평균입니다. ParaTempo의 기본값은 τ=500, L=20, W=7, X=9, N_warm=15이며, 이 설정이 branch-level 비동기 제어와 confidence-weighted voting을 구성합니다.

한계점

논문은 ParaTempo의 평가를 AIME 2026, HMMT November 2025, HMMT February 2026, GPQA Diamond의 네 benchmark와 Qwen3.5-35B-A3B 및 GPT-OSS-20B에 한정해 보고합니다. 따라서 다른 reasoning model, 더 큰 branch 수, 여러 GPU 구성, 비수학적 일반 작업에서 동일한 효율과 정확도가 유지되는지는 본문 결과만으로 확인되지 않습니다.

실무 활용

ParaTempo는 별도 training 없이 기존 reasoning model의 test-time parallel sampling 과정에 branch별 probe와 상태 제어를 추가하는 방식입니다. 논문은 vLLM과 단일 NVIDIA A100 80GB GPU에서 이를 구현했으며, 공개된 code와 dataset 저장소를 통해 실험 구성을 확인할 수 있습니다.

수학 문제에서 여러 reasoning branch를 병렬 생성하면서 일찍 수렴한 branch의 추가 토큰 생성을 중단하는 추론 시스템
과학적 multi-step reasoning에서 불확실한 branch를 prune하고 높은 confidence branch에서 새 탐색 branch를 fork하는 실행기
Self-Consistency의 고정 예산을 줄이면서 accuracy 경쟁력을 유지해야 하는 test-time scaling 파이프라인
branch별 생성 길이가 크게 달라 동기화 대기와 critical-path latency가 커지는 병렬 추론 환경

코드 공개 여부: 공개

코드 저장소 보기

키워드

병렬 추론(Parallel Reasoning)시간적 신뢰도(Temporal Confidence)비동기 branch 제어(Asynchronous Branch Control)답안 공간 수렴(Answer-Space Convergence)신뢰도 가중 투표(Confidence-Weighted Vote)

용어 해설

병렬 추론(Parallel Reasoning): — 하나의 문제에 대해 여러 개의 독립적인 추론 경로를 동시에 생성한 뒤 결과를 결합하는 방식입니다. 경로 수를 늘리면 정답의 견고성이 높아질 수 있지만, 모든 경로에 동일한 생성 예산을 배정하면 일찍 수렴한 경로도 불필요한 토큰을 계속 생성하게 됩니다.
시간적 신뢰도(Temporal Confidence): — 한 추론 경로가 시간에 따라 특정 답안에 얼마나 일관되게 집중하는지를 측정하는 branch-local 신호입니다. 여러 시점의 중간 답안 분포를 sliding window로 평균낸 뒤 그 엔트로피의 지수 음수를 계산해, 경쟁하는 답안 수가 적을수록 높은 값을 얻습니다.
엔트로피(Entropy): — 확률분포가 여러 후보에 얼마나 퍼져 있는지를 나타내는 불확실성 지표입니다. 답안 분포의 각 확률에 로그를 취해 가중합한 뒤 음수를 붙이면 값이 계산되며, 한 후보에 집중될수록 작아지고 여러 후보로 분산될수록 커집니다.
Self-Consistency: — 동일한 문제에서 여러 추론 경로를 생성하고 최종 답안의 다수결로 결과를 정하는 병렬 추론 방법입니다. 각 경로에 고정된 생성 예산을 사용하므로 답안 품질을 높일 수 있지만, 경로별 수렴 시점과 유용성이 달라도 계산량을 동일하게 소비합니다.
비동기 실행(Asynchronous Execution): — 서로 다른 추론 경로가 같은 생성 깊이에 도달하기를 기다리지 않고 각 경로의 상태에 따라 독립적으로 다음 작업을 결정하는 실행 방식입니다. ParaTempo는 이를 통해 수렴한 경로를 먼저 종료하고, 불확실한 경로에 계산 자원을 재배분합니다.

시간적 신뢰도로 병렬 추론 비용 줄이기

왜 중요한가

핵심 기여

핵심 아이디어 이해하기

방법론

주요 결과

기술 상세

한계점

실무 활용

키워드

용어 해설

관련 토론

댓글

관련 기사

토큰 예산 인지형 LLM 추론

왜 중요한가

핵심 기여

핵심 아이디어 이해하기

방법론

주요 결과

기술 상세

한계점

실무 활용

키워드

관련 토론

댓글

관련 기사

토큰 예산 인지형 LLM 추론