비동기와 Hogwild! 추론 (Async and Hogwild! Inference)

추측 디코딩(Speculative Decoding, Phase 10 · 15)은 하나의 시퀀스(sequence) 안에서 토큰(token)을 병렬화합니다. 멀티 에이전트 프레임워크(multi-agent framework)는 시퀀스 전체를 가로질러 병렬화하지만, 투표(voting)나 하위 작업 분할(sub-task splitting) 같은 명시적 조정(explicit coordination)을 강제합니다. Hogwild! 추론(Rodionov et al., arXiv:2504.06261)은 또 다른 길을 갑니다. 같은 LLM의 N개 인스턴스(instance)를 공유 키-값 캐시(shared key-value cache)에 대해 병렬로 실행합니다. 각 워커(worker)는 다른 워커가 생성한 토큰을 즉시 보게 됩니다. QwQ나 DeepSeek-R1 같은 현대 추론 모델(reasoning model)은 미세조정(fine-tuning) 없이도 공유 캐시를 통해 스스로 조율할 수 있습니다. 이 접근은 아직 실험적이지만, 추측 디코딩과 직교(orthogonal)하는 새로운 추론 병렬성(inference parallelism) 축을 엽니다. 이 lesson에서는 Python 표준 라이브러리만으로 두 워커짜리 Hogwild! 시뮬레이터(simulator)를 구현하고, 모델이 이미 가진 추론 능력에서 공유 캐시 협업(shared-cache collaboration)이 어떻게 자연스럽게 떠오르는지 설명합니다.

유형: Build 언어: Python (표준 라이브러리) 선수 지식: Phase 10 · 12 (추론 최적화), Phase 10 · 15 (추측 디코딩) 예상 시간: 약 60분

학습 목표

• 세 가지 대표적인 병렬 LLM 토폴로지(parallel-LLM topology)인 투표, 하위 작업 분할, Hogwild!를 설명하고 각 방식이 어떤 문제를 겨냥하는지 짚어 봅니다.
• Hogwild!의 핵심 구성을 말로 풀어 봅니다. 여러 워커, 하나의 공유 KV 캐시, 그리고 자기 프롬프팅(self-prompting)을 통한 창발적 조정(emergent coordination)입니다.
• 워커 수 N, 작업 수준 병렬성(task-level parallelism) p, 조정 오버헤드(coordination overhead) c의 함수로 Hogwild!의 실시간 속도 향상(wall-time speedup)을 계산합니다.
• 토이 문제(toy problem)에서 두 워커짜리 Hogwild! 시뮬레이터를 구현하고, 창발적인 작업 분할이 어떻게 나타나는지 관찰합니다.

문제

현대 LLM은 어려운 문제를 긴 추론 체인(reasoning chain)으로 풉니다. 단계별 논리(step-by-step logic) 5000 토큰은 흔하고, 깊은 수학 문제에서는 수만 토큰까지 흘러갑니다. 70B 모델에서 디코딩 속도가 35 tokens/sec라면, 50k 토큰은 24분이 걸립니다. 인터랙티브하다고 부르기는 어렵습니다.

추측 디코딩(Phase 10 · 15)은 하나의 시퀀스 안에서 병렬화하여 3-5배 속도 향상을 제공합니다. 그 이후로는 자기회귀 디코딩(autoregressive decoding)의 순차 의존성(sequential dependency)이 단단한 천장(hard ceiling) 역할을 합니다. 새 토큰 하나는 이전 모든 토큰에 의존합니다.

그러면 자연스러운 질문이 떠오릅니다. 시퀀스 사이를 병렬화할 수는 없을까요? 같은 문제 위에 같은 모델의 사본을 여러 개 띄우고 서로 협력하게 만들어, 일을 나누어 풀게 할 수 있을까요?

기존 접근으로는 투표 앙상블(voting ensemble; N개 모델을 돌린 뒤 다수결로 답을 고름), 사고의 나무(tree-of-thought; 추론 경로를 분기시키고 다시 합침), 멀티 에이전트 프레임워크(각 에이전트에 하위 작업을 할당하고 코디네이터가 조율) 등이 있습니다. 각각 특정 작업 영역(task domain)에서 도움이 됩니다. 다만 모두 명시적인 조정 장치를 도입합니다. 투표 규칙(voting rule), 분기-가지치기 로직(branch-and-prune logic), 에이전트 간 메시징 프로토콜(agent-to-agent messaging protocol) 같은 것들입니다.

Hogwild! 추론은 다른 결을 취합니다. N개의 워커가 단 하나의 KV 캐시를 공유합니다. 각 워커는 다른 워커가 생성한 토큰을 마치 자기 컨텍스트(context)의 일부인 것처럼 즉시 봅니다. 그리고 워커들은 추가 학습이나 미세조정 없이도 일을 나누는 방법을 스스로 찾아냅니다. 현대 추론 모델(QwQ, DeepSeek-R1, Claude 계열의 추론 모드)은 공유 캐시를 읽고 "워커 2가 이미 기본 사례(base case)를 처리했으니 나는 귀납 단계(inductive step)를 맡겠다" 같은 식으로 말할 수 있습니다.

속도 향상은 작업 부하(workload)에 따라 다르고, 2026년 4월 기준으로는 아직 실험적인 단계입니다. 그래도 이 아이디어는 추론 병렬성의 새로운 축을 열기 때문에 알아 둘 가치가 있습니다.

개념

기본 구성

같은 LLM을 실행하는 N개의 워커 프로세스(worker process)를 초기화합니다. 워커마다 따로 KV 캐시를 두는 대신, 하나의 공유 캐시를 유지합니다. 워커 i가 토큰 t_j를 생성하면, 그 토큰은 공유 캐시의 다음 위치에 기록됩니다. 워커 k가 다음 스텝(step)을 수행할 때는, N개 워커가 지금까지 만들어 낸 모든 내용을 포함한 현재 캐시 상태를 읽습니다.

스텝이 진행될 때 워커들은 토큰 쓰기(write)를 두고 경쟁합니다. 워커별 위치 인덱스(position index)는 따로 없습니다. 캐시는 점점 자라나는 하나의 시퀀스이고, 순서는 쓰기 도착 시각(write arrival time)으로 결정됩니다.

왜 조정이 자연스럽게 떠오르는가

워커들은 동일한 프롬프트(prompt)를 공유합니다. 보통 이런 식입니다. "You are one of N instances working together on this problem. Each instance reads the shared memory and can see what other instances have written. Avoid redundant work." 이 프롬프트와 공유 캐시만으로 충분합니다. 추론 모델은 캐시를 읽고 문제의 어느 부분이 이미 시도되었는지 파악한 뒤, 자주는 아니어도 종종 아직 탐색되지 않은 부분으로 방향을 틉니다.

Hogwild! 논문(Rodionov et al., 2025)은 다음과 같은 관찰을 보고합니다.

• 워커들이 계획(plan)을 세우고, 그 계획을 캐시를 통해 다른 워커들에게 전달합니다.
• 워커들이 다른 워커의 추론에서 오류를 발견하고 이를 지적합니다.
• 계획이 실패하면 워커들이 상황에 맞게 적응하며 대안을 제안합니다.
• 중복 여부(redundancy)를 확인하라는 지시를 받으면, 워커들이 중복을 감지하고 다른 방향으로 전환합니다.

이 가운데 어느 것도 미세조정이 필요하지 않습니다. 창발적인 행동은 모델이 이미 갖춘 추론 능력에서 나옵니다.

이름의 유래

논문 이름은 비동기 갱신 최적화기(asynchronous-update optimizer)인 Hogwild! SGD(Recht et al., 2011)에서 따왔습니다. 비유는 이렇습니다. Hogwild! SGD의 비동기 워커들이 모두 공유 파라미터 벡터(shared parameter vector)에 쓰는 것처럼, Hogwild! 추론의 워커들도 모두 공유 KV 캐시에 씁니다. 둘 다 동기화 보장(synchronization guarantee)보다는 경험적 수렴(empirical convergence)에 기댑니다.

RoPE가 이를 다루기 쉽게 만든다

회전 위치 임베딩(Rotary Position Embedding; RoPE, Su et al. 2021)은 Q와 K 벡터의 회전(rotation)으로 위치 정보(position information)를 인코딩합니다. 위치가 고정된 오프셋(baked-in offset)이 아니라 회전이기 때문에, 토큰의 위치가 바뀌어도 KV 캐시 항목을 다시 계산할 필요가 없습니다. 워커 i가 공유 캐시의 위치 p에 토큰을 쓰면, 그 위치를 읽는 다른 워커는 캐시된 항목을 그대로 사용할 수 있습니다. 다시 회전을 적용할 필요가 없습니다.

학습된 위치(learned-position)나 절대 위치(absolute-position)를 쓰는 모델이라면, 동시에 일어나는 쓰기마다 캐시 무효화(cache invalidation)가 필요해집니다. RoPE 덕분에 캐시는 안정적으로 유지됩니다.

실시간 속도 계산

T_serial을 워커 하나가 혼자 문제를 푸는 데 걸리는 시간이라고 합시다. p는 작업 수준에서 병렬화 가능한 비율(parallelizable fraction)이고, c는 스텝당 조정 오버헤드입니다. 즉, 늘어난 캐시를 읽고 무엇을 쓸지 결정하는 비용입니다.

단일 워커 시간은 T_serial입니다.

조정 비용이 무료라고 가정하면, N 워커 Hogwild! 시간은 다음과 같습니다.

T_serial * ((1 - p) + p / N)

전형적인 암달의 법칙(Amdahl's Law) 형태입니다. 조정 오버헤드를 포함하면 다음과 같습니다.

T_serial * ((1 - p) + p / N) + c * steps_per_worker

워커가 생산적으로 일하려면, c가 스텝당 디코드 시간(per-step decode time)에 비해 작아야 합니다. 5천 토큰 이상을 만들어 내는 추론 모델에서는 워커당 수백 토큰의 조정 오버헤드가 들어가도 충분히 이득을 볼 수 있습니다. 반대로 짧은 채팅 작업(chat task)에서는 조정 비용이 지배적이라 Hogwild!가 직렬 실행보다 오히려 느려집니다.

구체적인 예시

10k 토큰 분량의 사고의 사슬(chain-of-thought)을 요구하는 추론 문제를 생각해 봅시다. 문제의 p = 0.7이 병렬화 가능한 부분(서로 다른 증명 전략, 사례 분석 등)이고, 워커당 조정 오버헤드가 c = 200 토큰이라고 합시다. N = 4 워커일 때는 다음과 같습니다.

• 직렬 시간: 10000 디코드 스텝.
• Hogwild! 시간: 10000 * (0.3 + 0.7 / 4) + 200 * 4 = 10000 * 0.475 + 800 = 5550 디코드 스텝.
• 속도 향상: 10000 / 5550 = 1.8x.

이 정도는 그리 크지 않습니다. 그러나 50k 토큰처럼 더 긴 추론 문제에서는 조정 오버헤드가 상각(amortize)되면서 속도 향상이 2.5-3배까지 올라갑니다. Hogwild!는 멀티스레드 코드를 자연스럽게 작성할 수 있는 언어에서의 스레드 수준 병렬성(thread-level parallelism)에 해당하는 추론 방식이라고 볼 수 있습니다.

Hogwild!를 꺼내 들 때

• 수천 토큰 분량의 긴 추론 문제이고, 작업을 독립적인 하위 목표(sub-goal)로 나누어 병렬화할 수 있을 때.
• 단계별 사고를 하도록 학습된 추론 모델일 때. 비추론 모델(non-reasoning model)은 스스로를 조율(self-coordinate)하지 못합니다.
• 공유 캐시와 N개 워커 프로세스의 활성화 메모리(activation memory)를 담을 수 있는 충분한 VRAM이 있는 단일 노드 배포(single-node deployment)일 때. 캐시는 공유하지만, 각 워커는 자기만의 활성화 메모리를 가집니다.

사용하지 않을 때

• 짧은 인터랙티브 채팅. 조정 오버헤드가 지배적입니다.
• 병렬화되지 않는 작업(단일 선형 증명, 단일 컴파일 등). 이런 경우는 N=1이 최대입니다.
• 비추론 모델. 조정이 자연스럽게 떠오르지 않습니다.
• 다중 노드 배포(multi-node deployment). 공유 캐시는 매우 빠른 워커 간 동기화(cross-worker synchronization)를 필요로 합니다. 노드 내부(intra-node)는 괜찮지만, 노드 간(cross-node)은 지연(latency) 면에서 재앙입니다.

실험적 단계라는 점

2026년 4월 기준 Hogwild!는 오픈 소스 PyTorch 구현이 있는 연구용 방법(research method)입니다. 프로덕션 도입은 아직 일어나지 않았습니다. 막고 있는 요인은 크게 세 가지입니다.

1. 동시 실행되는 프로세스 사이의 공유 KV 캐시 관리(shared KV cache management)는 결코 가벼운 엔지니어링이 아닙니다.
2. 창발적 조정은 작업에 따라 결과가 달라지고, 벤치마크(benchmark)가 아직 만들어지는 중입니다.
3. 속도 향상은 추측 디코딩이 이미 제공하는 수치에 비하면 그리 크지 않습니다. 둘을 결합할 수는 있지만, 결합 자체가 또 하나의 엔지니어링 레이어가 됩니다.

알아 둘 가치는 있고, 실험해 볼 가치도 있습니다. 다만 아직 제품을 걸 단계는 아닙니다.

직접 만들기

code/main.py는 토이 Hogwild! 시뮬레이터를 구현합니다.

• 두 개의 워커 프로세스. 각각은 결정적인(deterministic) "LLM"으로, 알려진 확률에 따라 작업 토큰(work-token), 관찰 토큰(observe-token), 조정 토큰(coordinate-token) 중 하나를 만듭니다.
• 두 워커가 함께 읽고 쓰는 공유 캐시. 여기서는 단순한 토큰 리스트입니다.
• 단순한 조정 로직. 다른 워커가 어떤 카테고리(category)에 충분한 작업 토큰을 이미 만들었다고 판단되면, 다른 카테고리로 옮겨 갑니다.

시뮬레이터는 고정된 스텝 예산(step budget) 동안 실행되며 다음 정보를 보고합니다.

• 생성된 총 작업 토큰 수.
• 총 실시간 시간(워커 스텝 수).
• 단일 워커 대비 실효 속도 향상(effective speedup).
• 어떤 워커가 어떤 토큰을 썼는지 보여 주는 추적(trace).

Step 1: 공유 캐시

두 워커가 끝에 덧붙이는(append) 리스트입니다. 실제 구현에서는 Python threading.Lock 같은 단순 잠금(simple locking)이 필요하지만, 여기서는 카운터(counter)로 흉내만 냅니다.

Step 2: 워커 루프

각 워커는 매 스텝마다 다음 일을 합니다.

• 현재 공유 캐시를 읽습니다.
• 이미 들어 있는 내용을 바탕으로 어떤 카테고리의 토큰을 쓸지 결정합니다.
• 토큰 하나를 씁니다.

Step 3: 조정 휴리스틱

캐시 안에 카테고리 X의 토큰이 이미 K개 있고 워커가 의도한 카테고리도 X라면, 워커는 카테고리 Y로 바꿉니다. 이는 추론 모델이 "이건 이미 누가 다뤘으니 다른 일을 하자"라고 행동하는 것을 흉내 내는 토이 대용물(toy stand-in)입니다.

Step 4: 측정된 속도 향상

같은 총 스텝 예산으로 N=1 워커 구성과 N=2 워커 구성을 각각 실행하고, 만들어진 작업 토큰 수를 셉니다. 조정 기반 작업 분할 덕분에 N=2 쪽이 대략 1.5-1.8배 더 많은 작업 토큰을 만들어 내야 합니다.

Step 5: 조정을 흔들어 보기

조정 휴리스틱의 민감도(sensitivity)를 낮춥니다. 다시 실행합니다. 좋은 조정이 없으면 N=2가 같은 토큰을 중복해서 만들고, 속도 향상이 1배 아래로 떨어지는 것을 관찰합니다. 이는 논문의 관찰과도 맞닿아 있습니다. 즉, 이 트릭은 워커들이 스스로 조율할 만한 추론 역량을 갖추었을 때만 동작합니다.

사용해보기

2026년 4월 기준으로 프로덕션 환경에서 Hogwild! 통합은 아직 연구용 수준(research-grade)입니다. Yandex/HSE/IST의 참조 구현(reference implementation)은 PyTorch 기반이며, DeepSeek-R1과 QwQ 모델 위의 단일 노드 멀티 프로세스 구성을 겨냥합니다.

실용적인 도입 경로는 다음과 같습니다.

1. 추론 작업 부하를 프로파일링(profile)합니다. 토큰 가운데 탐색적인 부분(여러 전략, 사례 분석, 검색 등)과 선형적인 부분의 비율을 측정합니다.
2. 탐색적 부분이 지배적이면 두 워커짜리 Hogwild! 실험을 돌립니다. 그리고 실시간 시간 개선치(wall-time improvement)를 측정합니다.
3. 개선치가 1.3배 미만이면 조정 비용이 지배하는 영역(coordination-dominated regime)입니다. 단일 워커로 되돌립니다.
4. 개선치가 1.5배 이상이면 N=4로 늘려 다시 측정합니다. 수확 체감(diminishing returns)은 보통 N=4-8 근처에서 나타납니다.

추측 디코딩과 함께 쓸 수도 있습니다. 각 Hogwild! 워커가 독립적으로 추측 디코딩을 활용할 수 있습니다. 두 속도 향상은 대략 곱셈 형태로 결합되어, 3배의 추측 디코딩과 1.8배의 Hogwild!가 합쳐지면 단순한 단일 워커 디코딩 대비 약 5.4배의 실효 속도 향상이 나옵니다.

산출물 만들기

이 lesson은 outputs/skill-parallel-inference-router.md를 만듭니다. 추론 작업 부하 프로파일(토큰 예산, 작업 병렬성 프로파일, 모델 계열, 배포 대상)이 주어지면, 투표, 사고의 나무, 멀티 에이전트, Hogwild!, 추측 디코딩 전략 가운데 어디로 라우팅(route)할지를 결정합니다.

연습문제

1. 기본 설정으로 code/main.py를 실행합니다. 같은 실시간 시간 안에서 N=2 Hogwild! 구성이 N=1 베이스라인(baseline)보다 더 많은 작업 토큰을 만들어 내는지 확인합니다. (난이도: 쉬움)

2. 조정 휴리스틱의 강도를 낮춥니다. coordination_weight=0.1로 설정하고 다시 실행해, 속도 향상이 무너지는 모습을 보입니다. 워커들이 서로 조율하지 못하면 중복 작업을 하게 된다는 점을 함께 설명합니다. (난이도: 중간)

3. p=0.8, c=500, N=4 워커인 50k 토큰 추론 작업에 대한 예상 Hogwild! 속도 향상을 계산합니다. p=0.3, c=200, N=4인 1k 토큰 채팅 작업에 대해서도 같은 계산을 합니다. 왜 한쪽은 이득이고 다른 한쪽은 손해인지 설명합니다. (난이도: 중간)

4. Hogwild! 논문의 Section 4(preliminary evaluation)를 읽습니다. 저자들이 보고한 두 가지 실패 모드(failure mode)를 찾아냅니다. 더 잘 짜인 조정 프롬프트가 각 실패 모드를 어떻게 완화할 수 있을지 설명합니다. (난이도: 어려움)

5. 토이 시뮬레이터에서 Hogwild!와 추측 디코딩을 결합합니다. 각 워커가 내부적으로 2-token 추측 디코딩을 사용하도록 만들고, 곱셈 형태의 속도 향상을 보고합니다. 두 워커가 같은 공유 캐시 접두(prefix)를 확장하려고 할 때 어떤 기록 관리(bookkeeping) 문제가 생기나요? (난이도: 어려움)

핵심 용어

더 읽을거리

• Rodionov et al. — Hogwild! Inference: Parallel LLM Generation via Concurrent Attention (arXiv:2504.06261) — Hogwild! 논문입니다. QwQ와 DeepSeek-R1에 대한 예비 평가(preliminary evaluation)를 담고 있습니다.
• Recht, Re, Wright, Niu — Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent (arXiv:1106.5730, NeurIPS 2011) — 이름의 기원이 된 원조 Hogwild! 논문입니다.
• Su et al. — RoFormer: Enhanced Transformer with Rotary Position Embedding (arXiv:2104.09864) — 공유 캐시 기반 추론을 다루기 쉽게 만들어 주는 RoPE를 소개합니다.
• Yao et al. — Tree of Thoughts: Deliberate Problem Solving with Large Language Models (arXiv:2305.10601) — Hogwild!와 직교하는 사고의 나무 추론 전략입니다.
• Leviathan et al. — Fast Inference from Transformers via Speculative Decoding (arXiv:2211.17192) — Hogwild!와 결합할 수 있는 시퀀스 내부 병렬화(within-sequence parallelism), 즉 추측 디코딩입니다.
• Hogwild! reference PyTorch implementation — 논문 실험의 단일 진실 공급원(single source of truth)이 되는 참조 PyTorch 구현입니다.