NgramRL은 RL 롤아웃 재사용으로 구조화 생성 후학습을 가속한다

무엇인가

이 논문은 RL 후학습, 특히 GRPO에서 롤아웃 생성이 전체 스텝 시간의 70%를 넘길 수 있는 병목을 다룬다. 투기적 디코딩은 자연스러운 해법이지만, 기존 드래프트 모델은 정책과 함께 GPU 메모리를 차지하고 정책이 변하면 초안이 낡아 수용률이 떨어진다. 모델 없는 방식도 현재 생성 한 번이나 고정 데이터 저장소에만 의존해 RL 롤아웃처럼 정책이 조금씩 변하는 환경에서는 수용률이 낮다. 저자들은 GRPO가 같은 프롬프트를 여러 스텝과 에폭에 걸쳐 반복 방문하고 정책이 점진적으로만 바뀐다는 점에 주목한다. 같은 프롬프트의 이전 롤아웃이 추가 파라미터나 학습 없이도 정책을 따라가는 초안 소스가 된다는 것이다. 실제로 같은 Spider 프롬프트의 연속 에폭 롤아웃은 7~23토큰 길이의 부분 문자열을 공유했고, 이전 롤아웃 하나만으로도 이후 롤아웃의 48~96%를 커버했다.

어떻게 동작하나

NgramRL의 핵심은 프롬프트별 n-gram 캐시다. 각 프롬프트마다 최근 W스텝의 롤아웃에서 n_min부터 n_max 차수의 n-gram을 뽑아, n-1개 토큰 문맥을 관측된 다음 토큰과 빈도에 매핑하는 조회 테이블을 만든다. 롤아웃 중에는 현재 문맥과 가장 길게 일치하는 n-gram을 찾아 저장된 다음 토큰을 초안으로 제안하고, 타깃 모델이 한 번의 포워드로 검증한다. 수용 확률은 p_acc=min(1, πθ(x|c)/q(x|c))로 계산하고, 거부 시에는 정규화된 양의 잔차에서 다시 샘플링한다. 이 표준 투기적 샘플링 보정 덕분에 최종 커밋 토큰은 드래프터 q와 무관하게 정확히 타깃 정책 πθ 분포를 따르며, 롤아웃 분포와 학습 결과를 바꾸지 않는다. 캐시는 호스트 메모리에 있고 GPU 상주 드래프터 상태를 두지 않는다.

무엇과 다른가

문제는 CPU 캐시 조회가 GPU 포워드와 직렬화된다는 점이다. 저자 측정에서 매 디코드 반복마다 호스트-디바이스 왕복 때문에 GPU가 약 29% 유휴 상태가 되었고, 조회 자체보다 동기화와 스케줄링이 병목이었다. 이를 숨기기 위해 적응형 팬아웃 프리페처를 둔다. 이 프리페처는 다음 스텝의 검증 결과를 수용 길이 j와 타깃이 내는 보너스 토큰 b의 쌍 (j,b)로 예측한다. 현재 스텝의 포워드 중에 각 수용 길이 분기마다 캐시에서 상위 f_j개의 보너스 후보를 뽑아 k토큰 초안 테이블을 만들고, 이를 GPU로 미리 전송한다. 검증 후 실제 (j*,b*)가 나오면 GPU가 O(1) 키 조회로 초안을 찾는다. 적중하면 호스트 시간 없이 진행하고, 빗나가면 해당 요청만 순차 조회로 폴백하므로 배치 전체가 멈추지 않는다. 후보 예산 N=Σf_j는 최근 W스텝의 수용 길이 히스토그램과 분기별 커버리지 프로파일을 이용해 기대 커버리지를 최대화하도록 탐욕적으로 배분한다. 완전 수용 분기의 보너스는 이미 캐시된 궤적의 다음 토큰이라 약 90% 확률로 최상위 후보이므로 f_j=1로도 충분하다. 이론적 속도 향상은 speedup(c)=(T_gpu+T_cpu)/(T_gpu+(1-c)T_cpu)로, 커버리지 c가 1에 가까워지면 1+T_cpu/T_gpu에 접근한다.

어떻게 쓰나

실험은 2대의 NVIDIA A100 80GB에서 verl의 GRPO와 vLLM 롤아웃 엔진으로 수행했다. 스텝당 64개 프롬프트에 대해 5개 완성을 샘플링하고 15에폭 동안 학습했으며, 모델은 Qwen3-8B와 DeepSeek-LLM-7B, 데이터셋은 GSM8K, Spider 1.0, CodeContests를 사용했다. 베이스라인은 prompt-lookup decoding, REST, SuffixDecoding이고 모두 k=16의 동일한 드래프트 예산을 맞췄다. 지표는 타깃 포워드당 커밋 토큰 수인 TPS로, 1 더하기 평균 수용 초안 길이다. 전체 실행 평균과 마지막 30% 구간 평균을 보고했고, 런타임 측정은 Qwen3-8B bf16, 배치 64, k=16을 RTX PRO 6000 96GB와 32코어 AMD Ryzen Threadripper 9970X 호스트에서 Nsight Systems로 분해했다.

전제와 한계

웜 캐시 구간에서 NgramRL은 타깃 포워드당 3.60~7.77토큰을 커밋했고, SuffixDecoding보다 최대 1.99배, prompt-lookup decoding보다 7.0배 더 많았다. 첫 에폭의 콜드 구간을 포함한 전체 평균에서도 모든 과제에서 앞섰다. 이점은 출력 규칙성이 강한 과제에서 컸다. Spider와 DeepSeek의 GSM8K 유도 과정에서 가장 컸고, CodeContests에서는 과제 간 보일러플레이트 때문에 전역 캐시가 유리해 가장 작았다. 수용 길이는 두꺼운 꼬리를 보였다. Spider에서는 14.1%의 스텝에서 12개 이상이 수용됐고 최대 10.1%의 스텝에서 16개 전부가 수용됐다. 긴 수용 스텝 비율은 DeepSeek GSM8K 13.0%, Qwen GSM8K 6.4%, CodeContests 3.7%였다. 수용률은 프롬프트가 재등장하기 전까지 0이었다가 이력이 쌓이며 상승했고, Spider에서는 중반 이후 SQL 출력이 다양해지며 하락했다. 소거 실험에서 n_max=6과 k=16이 속도 곡선의 무릎이었고, 프롬프트별 키를 전역 버킷으로 바꾸면 수용률이 2.41로 떨어져 SuffixDecoding의 2.43에 가까워졌다. 프롬프트별 키는 같은 구간에서 3.05였고, SuffixDecoding 캐시를 4배인 4만 응답으로 늘려도 2.65에 그쳤다. 히스토리 윈도 4는 전체 수용률의 79~91%를 잡았고, 16을 넘기면 GSM8K에서 오히려 조금 낮아졌다.

프리페처의 커버리지는 Spider에서 N=8에 0.95, N=16에 0.97까지 포화됐다. GSM8K와 CodeContests는 N=32에서 각각 0.65와 0.49에 이르렀고 그 이후에는 로그 수준의 이득만 있었다. Spider N=16에서 Qwen3-8B는 커버리지 0.966으로 1.40배 중첩 상한 대비 1.38배 속도를 냈고, DeepSeek-7B는 커버리지 0.995로 측정된 1.21배 상한을 그대로 달성했다. 엔트로피가 높은 과제에서는 같은 메커니즘이 GSM8K 1.10배, CodeContests 1.14배 상한에 대해 1.05~1.06배를 냈다. 빗나간 요청은 순차 조회로 폴백하므로 최악의 경우도 기존 동기식 베이스라인과 같다. 논문은 프리페처가 후보 예산 16에서 Qwen3-8B 결과의 96.6%를 커버하고 동기식 NgramRL 대비 측정 롤아웃 처리량을 1.38배 높여 1.40배 중첩 상한에 근접한다고 정리한다.

개발자 관점에서 이 방식은 verl의 vLLM 롤아웃 워커에 붙는 드롭인 최적화로, 보상 모델·옵티마이저·정책 아키텍처를 바꾸지 않는다. 같은 프롬프트가 반복되는 RL 스타일 학습, 특히 text-to-SQL이나 코드, 도구 호출처럼 출력이 구조적인 과제에서 효과가 크다. 다만 캐시 윈도, n_max, k, 후보 예산 N을 실제 워크로드의 반복성과 CPU/GPU 시간 비율에 맞춰 조정해야 한다. 저자들이 밝힌 전제와 한계도 분명하다. 프리페치 체인은 드래프트 요청당 약 N회 조회를 수행하므로 T_gpu 안에 들어와야 하고, N이 약 64를 넘으면 숨기려는 호스트 시간 T_cpu에 근접해 예산의 최적점이 작다. 속도 향상과 최적점은 T_cpu/T_gpu 비율에 좌우되어, 큰 모델이나 큰 배치에서는 GPU 시간이 커져 숨길 수 있는 비율이 줄고 CPU가 상대적으로 무거운 환경에서 더 유리하다. 커버리지의 잔여 미스는 데이터 부족이 아니라 엔트로피 한계라서 롤아웃 이력을 더 쌓아도 잘 오르지 않는다. 오래된 롤아웃은 정책 변화로 낡기 때문에 작은 윈도가 메모리와 정렬 모두에 유리하고, CodeContests 초반처럼 전역 보일러플레이트가 강한 과제에서는 프롬프트별 키링의 이점이 작다. 그럼에도 타깃 검증이 정확히 분포를 보존하므로 학습 정확도와 수렴 자체를 바꾸지 않는 가속이라는 점이 이 논문의 핵심 주장이다.