💬 NLP

Copy-as-Decode: Grammar-Constrained Parallel Prefill for LLM Editing

이 논문은 입력의 대부분을 그대로 복사해야 하는 텍스트 및 코드 편집 작업에서, 생성을 구조화된 복사로 재해석하고 병렬 프리필 (parallel prefill) 을 활용하여 자동회귀 방식 대비 최대 303 배의 속도 향상을 달성하면서도 문법적 무결성을 보장하는 'Copy-as-Decode' 메커니즘을 제안합니다.

원저자: Ziyang Liu

게시일 2026-04-21

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Ziyang Liu

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

🏠 비유: 집을 고치는 두 가지 방법

1. 기존 방식: "다 부수고 다시 짓기" (Autoregressive Decoding)

지금까지 AI 가 글을 고칠 때 하는 일은 마치 집을 고치러 온 장인이, 고칠 부분만 고치는 게 아니라 집 전체를 한 번에 다 부수고 처음부터 다시 짓는 것과 비슷합니다.

상황: "거실 벽만 페인트칠해 줘"라고 요청했습니다.
기존 AI 의 행동: "네, 알겠습니다."라고 말하며 거실 벽뿐만 아니라 방, 주방, 화장실, 지붕까지 모든 벽을 다시 그려냅니다.
문제점: 이미 깨끗한 방과 주방까지 다시 그리는 데 시간이 너무 많이 걸립니다. AI 는 입력된 텍스트의 90% 가 넘는 부분을 그대로 가져가야 하는데도, 매번 처음부터 다시 계산하며 출력합니다.

2. 새로운 방식: "Copy-as-Decode (복사 -해석)"

이 논문이 제안하는 방법은 장인이 "이쪽 벽은 그대로 두고, 이 부분만 새로 칠하자"라고 지시하는 것입니다.

핵심 아이디어: AI 는 고칠 부분만 새로 쓰고, 나머지는 **입력된 원본에서 그대로 "복사 (Copy)"**해서 붙여넣습니다.
어떻게 가능할까? AI 가 출력할 때, "이 부분은 원본의 10 번째 줄부터 20 번째 줄까지 가져와"라고 **명령어 ()**를 내리면, AI 는 그 부분을 다시 계산하지 않고 한 번에 메모리 (KV Cache) 에 붙여넣습니다.
결과: 고칠 부분만 새로 그리기 때문에 시간이 획기적으로 단축됩니다.

🚀 이 기술의 3 가지 놀라운 점

1. 속도가 터지다 (Kernel Speedup)

비유: 100 장의 문서를 고칠 때, 기존 방식은 100 번을 일일이 복사해서 붙여야 하지만, 이 방식은 한 번에 100 장을 통째로 떼어와서 붙입니다.
실제 효과: 실험 결과, 8~512 개의 단어를 복사할 때 기존 방식보다 6.8 배에서 최대 303 배까지 빨라졌습니다. (예: 1 초 걸리던 게 0.003 초가 됨)

2. 얼마나 많이 복사할 수 있을까? (Copy Ceiling)

비유: "집을 고칠 때, 정말로 새로 칠해야 하는 벽은 얼마나 될까?"를 조사했습니다.
실제 효과: 연구진이 분석한 코드와 문서 수정 작업에서, 최종 결과물의 74%~98% 가 이미 원본에 그대로 있었습니다. 즉, AI 가 새로 만들어야 할 부분은 극히 일부라는 뜻입니다. 이 기술은 그 '이미 있는 부분'을 효율적으로 가져오는 방법을 제공합니다.

3. 실수 없이 정확하다 (Pipeline Losslessness)

비유: "복사해 온 벽이 원래 벽과 정확히 일치하는지 확인하는 검사관"이 있습니다.
실제 효과: 이 시스템은 AI 가 실수해서 잘못된 줄을 복사해 오지 않도록 **문법 (Grammar)**을 엄격하게 지키게 합니다. 실험 결과, 원본을 그대로 가져와서 붙이는 과정은 100% 정확했습니다. 만약 결과가 틀리다면, AI 가 '어디를 고쳐야 할지'를 잘못 골랐기 때문이지, '복사' 기술 자체의 문제는 아닙니다.

🧠 왜 이것이 중요한가요?

지금까지 AI 는 "무언가를 고치라"는 요청을 받으면, 고칠 부분만 고치는 게 아니라 전체를 다시 생성하는 비효율적인 방식을 썼습니다. 마치 편지를 고칠 때, 고칠 단어 하나를 위해 종이를 한 장 더 새로 써서 전체 편지를 다시 쓰는 것과 같습니다.

이 논문은 **"이미 있는 것은 다시 쓰지 말고, 지시대로 가져와서 붙여라"**는 방식을 도입했습니다.

단점: AI 가 "어디를 고칠지" (어떤 줄을 복사할지) 를 정확히 찾아내는 훈련이 필요합니다. (현재는 아직 완벽하지 않아 100% 를 달성하지는 못했지만, 가능성을 증명했습니다.)
장점: 훈련이 잘만 된다면, AI 가 문서를 수정할 때 속도가 수십 배 빨라지고, 전산 비용은 획기적으로 줄어듭니다.

💡 결론

이 기술은 **"AI 가 글을 고칠 때, 이미 있는 내용은 다시 계산하지 않고 '복사 - 붙여넣기'로 처리하여 속도를 비약적으로 높이는 새로운 방법"**입니다. 마치 장인이 집을 고칠 때, 고칠 부분만 집중하고 나머지는 그대로 두는 지혜를 AI 에게 심어준 것과 같습니다.

1. 문제 정의 (Problem)

대형 언어 모델 (LLM) 이 텍스트나 코드를 편집할 때, 기존 방식은 입력의 대부분이 그대로 유지되더라도 전체 출력을 autoregressive(자기회귀적) 방식으로 처음부터 다시 생성합니다.

비효율성: 입력 문서의 74~98% 가 그대로 복사되어야 하는 경우에도, 모델은 매 토큰마다 순차적인 포워드 패스 (forward pass) 를 수행합니다.
지연 시간: 출력 길이에 비례하여 지연 시간이 증가하며, 실제로는 이미 모델이 프롬프트에서 주석 (attention) 을 기울인 내용을 다시 계산하는 낭비가 발생합니다.
기존 대안의 한계:
- Speculative Decoding (추측적 디코딩): 소규모 드래프트 모델을 사용하지만, 확률적 검증 과정을 거치기 때문에 복사 (copy) 영역에서 100% 수용 보장이 어렵습니다.
- Search-and-Replace / Diff: 구조적 컨텍스트를 다시 생성해야 하거나, 앵커 (anchor) 모호성으로 인해 오류가 발생할 수 있습니다.

2. 방법론: Copy-as-Decode (Methodology)

저자는 편집 생성을 구조화된 두 가지 원시 연산 (two-primitive grammar) 을 통한 디코딩으로 재정의했습니다.

A. 문법 및 프로그래밍 구조

모델은 자유로운 텍스트 생성 대신, 다음 두 가지 원시 연산으로 구성된 프로그램을 생성하도록 강제됩니다.

<copy lines="i-j"/>: 입력 문서의 $i$ 번부터 $j$ 번 줄까지를 그대로 복사합니다.
<gen> ... </gen>: 새로운 내용을 생성합니다.

이 문법은 **토큰 수준의 유한 상태 기계 (FSM)**에 의해 강제됩니다. FSM 은 모델의 로지츠 (logits) 를 현재 문법 상태에 부합하는 토큰으로만 제한하여, 문법적으로 유효한 프로그램이 100% 생성되도록 보장합니다.

B. 병렬 프리필 (Parallel Prefill) 을 통한 KV 캐시 스플라이싱

이 메커니즘의 핵심은 <copy> 연산 시 autoregressive 디코딩을 생략하는 것입니다.

작동 원리: 모델이 <copy lines="i-j"/>를 선택하면, 해당 줄에 해당하는 토큰들은 이미 입력에 존재하므로 "알려진" 상태입니다.
KV 캐시 업데이트: 모델은 이 $N$ 개의 토큰을 단일 병렬 프리필 (parallel-prefill) 포워드 패스로 처리하여 KV 캐시에 직접 주입 (splice) 합니다.
효과: $N$ 개의 토큰을 생성하는 데 $N$ 번의 autoregressive 디코딩 단계가 필요한 대신, 1 번의 병렬 포워드 패스로 처리됩니다. 이는 Speculative Decoding 의 검증 단계와 동일한 커널을 사용하지만, 확률적 검증 대신 문법적 강제 수용 (acceptance = 1) 을 적용합니다.

C. 결정론적 Resolver

생성된 프로그램을 해석하여 최종 편집된 문서를 출력하는 Resolver는 결정론적 (deterministic) 으로 작동하며, 모델의 생성 오류 없이 입력을 기반으로 정확한 출력을 보장합니다.

3. 주요 기여 (Key Contributions)

이 논문은 엔드 - 투 - 엔드 모델 학습 없이도 검증 가능한 세 가지 측정 가능한 속성을 제시합니다.

커널 가속도 (Kernel Speedup):
- Qwen2.5 (1.5B, 7B) 모델에서 8~~512 토큰 길이의 복사 구간을 병렬 프리필로 처리할 때, autoregressive 방식 대비 **6.8 배~~303 배**의 속도 향상을 입증했습니다.
- 구간 길이가 길어질수록 (N=512) 속도 향상 폭이 극대화됩니다.
복사 상한선 (Copy Ceiling):
- 실제 편집 데이터셋 (ProbeEdit, HumanEvalPack-Fix) 에서 **골드 (Gold) 토큰의 74~98%**가 줄 단위 복사 원시 연산으로 구현 가능함을 확인했습니다.
- 이를 커널 속도 향상 곡선과 결합하여 **이론적 벽시계 시간 상한 (Wall-clock Bound, $bnd_{exact}$ $bn d_{e x a c t}$ )**을 도출했습니다.
  - ProbeEdit: 29.0 배
  - Python Fix: 3.4 배
  - JS Fix: 4.2 배
  - 전체 평균: 13.0 배
파이프라인 무손실성 (Pipeline Losslessness):
- 오라클 (Oracle) 프로그램 (정확한 편집 지시) 을 Resolver 에 통과시켰을 때, 482 개의 모든 사례에서 **바이트 단위 (byte-exact) 정확도 100%**를 달성했습니다.
- 이는 시스템의 실패가 복사 구간 선택 (span selection) 모델의 문제인지, 메커니즘 자체의 결함인지 명확히 구분할 수 있는 전제 조건을 제공합니다.

4. 실험 결과 (Results)

성능 향상: A100 GPU 환경에서 Qwen2.5 모델을 사용하여 측정된 결과, 복사 구간이 길어질수록 지연 시간이 선형적으로 감소하고 처리량이 급증했습니다.
정확도 민감도 분석: 오라클의 줄 번호에 $\pm 1$ 의 노이즈 (오프 - 바이 - 원) 가 발생하면, 정확도 (EM) 가 100% 에서 **15.48%**로 급격히 하락했습니다. 이는 향후 학습된 선택기 (selector) 가 매우 정밀한 구간 선택 능력을 가져야 함을 시사합니다.
학습 가능성 (Learnability) 파일럿: Qwen2.5-Coder-1.5B 모델을 131~~385 개의 오라클 프로그램으로 미세 조정 (SFT) 한 결과, 학습 전 0% 였던 정확도가 **12~~17%**로 상승했습니다. 이는 메커니즘이 학습 가능함을 증명하지만, 아직 배포 수준은 아닙니다.
기타 형식 비교: 기존 Search/Replace 나 Unified Diff 형식보다 토큰 효율성이 높고, 앵커 모호성 없이 100% 정확도 (Round-trip EM) 를 달성했습니다.

5. 의의 및 결론 (Significance)

새로운 패러다임: LLM 편집을 "생성"이 아닌 "구조화된 디코딩 + KV 캐시 스플라이싱"으로 재정의하여, 불필요한 계산 비용을 제거했습니다.
시스템 최적화: 모델 학습 없이도 시스템 레이어에서 극적인 속도 향상을 달성할 수 있음을 보여주었습니다.
확장성: 현재는 줄 (line) 단위 복사지만, 토큰 단위 확장 () 을 통해 복사 커버리지를 99% 까지 높일 수 있는 가능성을 제시했습니다.
미래 작업: 현재는 단일 파일 편집에 국한되었으나, vLLM/SGLang 과 같은 배치 서비스 환경에 스플라이싱 커널을 통합하고, 더 큰 모델 (7B 이상) 로 선택기를 학습하는 것이 향후 과제로 제시되었습니다.

요약하자면, 이 논문은 LLM 이 입력의 대부분을 그대로 복사해야 하는 편집 작업에서, autoregressive 생성의 비효율성을 극복하기 위해 문법 제약을 통해 복사 구간을 식별하고, 이를 병렬 프리필을 통해 KV 캐시에 직접 주입하는 혁신적인 메커니즘을 제안했습니다. 이는 모델 학습 없이도 최대 30 배 이상의 속도 향상을 가능하게 하는 강력한 시스템적 솔루션입니다.