💬 NLP

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

This paper introduces "Copy-as-Decode," a grammar-constrained decoding mechanism that accelerates LLM text and code editing by replacing autoregressive regeneration of unchanged tokens with a single parallel-prefill operation, achieving up to 303x speedup while maintaining syntactic validity and offering significant theoretical wall-clock time reductions.

Original authors: Ziyang Liu

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ziyang Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a professional editor working on a massive, 100-page manuscript. A client sends you a note saying, "Change the third paragraph, but keep everything else exactly the same."

The Old Way (Standard AI):
The current AI models act like a very polite but slightly inefficient scribe. Even though 95% of the document is perfect and doesn't need changing, the AI re-reads the entire 100 pages from scratch, word by word, and re-types the whole thing to give you the new version. It's like rewriting a whole book just to fix a single typo. It takes a long time and wastes a lot of energy.

The New Way (Copy-as-Decode):
This paper introduces a clever new trick called Copy-as-Decode. Instead of re-writing the whole book, the AI is taught to act like a smart project manager who uses a "Cut and Paste" command.

Here is how it works, broken down into simple analogies:

1. The "Two-Tool" Grammar (The Instruction Manual)

Instead of letting the AI write freely, we give it a strict, simple instruction manual with only two tools:

Tool A (Copy): "Take lines 10 through 50 from the original document and paste them here."
Tool B (Generate): "Write something new here."

The AI isn't allowed to just "write" the whole thing. It has to explicitly say, "I'm going to copy these parts" and "I'm going to write these parts." It's like forcing a chef to say, "I will use the pre-chopped onions from the bowl (Copy)" and "I will chop these new carrots myself (Generate)."

2. The "Magic Clipboard" (Parallel Prefill)

This is the secret sauce that makes it fast.

Normal AI: To copy 100 words, the AI has to "think" about the first word, then the second, then the third... one by one. It's like walking down a hallway and picking up 100 books one by one.
Copy-as-Decode: Because the AI knows exactly which words it needs to copy (they are already in the original document), it doesn't need to "think" about them. It uses a Magic Clipboard. It grabs the whole chunk of 100 words in a single, instant motion and slaps them onto the new page.

In computer terms, this is called a Parallel Prefill. Instead of taking 100 steps to copy 100 words, it takes 1 giant leap.

3. The "Guardian" (The FSM)

You might worry: "What if the AI gets confused and tries to copy a line that doesn't exist?"
The paper uses a tiny, super-fast "Guardian" (a Finite State Machine) that watches the AI's every move.

If the AI tries to type a random letter when it should be typing a line number, the Guardian stops it immediately.
This ensures the AI never makes a syntax error. It's like a spell-checker that doesn't just correct your spelling but physically prevents you from typing a wrong word in the first place.

Why Does This Matter? (The Results)

The researchers tested this on code and text editing tasks and found some amazing things:

Speed: For chunks of text between 8 and 512 words, this method is 7 to 300 times faster than the old way. It's the difference between walking to the store and teleporting.
Accuracy: They found that in real-world editing tasks (like fixing bugs in code), 74% to 98% of the final text is just "copy-paste" from the original. The AI only needs to actually "think" and "write" a tiny fraction of the time.
Reliability: Because the AI is forced to use the "Copy" tool for the parts it knows, it never accidentally changes a line it was supposed to keep. It's mathematically guaranteed to be correct for the parts it copies.

The Catch (The "Span Selection" Problem)

The system is incredibly fast, but it relies on the AI being good at one specific thing: Pointing.
The AI has to correctly identify exactly which lines to copy.

If the AI says, "Copy lines 10–20," but it should have been "11–21," the whole thing breaks.
The paper shows that if the AI is off by just one line, the success rate drops from 100% to about 15%.
The Good News: The researchers showed that even a small, untrained AI can learn to do this pointing task reasonably well (getting about 12–17% right immediately), and with more training, it should get much better.

Summary

Copy-as-Decode is like upgrading a car from a manual transmission where you have to shift gears for every single mile, to a car with a "Turbo Boost" that instantly jumps over the miles you don't need to drive.

It tells the AI: "Don't re-invent the wheel. If the text is already there, just point to it and grab it instantly. Only use your brain for the parts that actually need changing." This makes editing text and code significantly faster, cheaper, and more reliable.

1. Problem Statement

Large Language Models (LLMs) currently edit text and code by autoregressively regenerating the entire output sequence, even when the majority of the output tokens are identical to the input. This "full regeneration" approach incurs two major inefficiencies:

Latency: Wall-clock time scales with the total output length rather than the size of the actual edit.
Redundancy: The model wastes compute cycles re-generating content it has already attended to in the prompt, and risks "drifting" on tokens that should have remained static.

Existing solutions like search-and-replace formats or speculative decoding offer partial improvements but suffer from anchor ambiguity, probabilistic rejection, or the need for separate draft models.

2. Methodology: Copy-as-Decode

The authors propose Copy-as-Decode, a decoding-layer mechanism that treats editing as a structured program execution rather than free-form generation. The method consists of three core components:

A. Two-Primitive Grammar

The model is constrained to emit a program using a specific grammar with two operations:

<copy lines="i-j"/>: References a contiguous range of lines ( $i$ to $j$ ) from the input document.
<gen> ... </gen>: Emits new, generated content.
This grammar is enforced by a Token-Level Finite State Machine (FSM) that restricts the model's logits to valid tokens at every step, guaranteeing a 100% parse rate.

B. Parallel-Prefill Splicing (The Core Innovation)

When the model commits to a <copy> operation:

The tokens for the specified line range are already known (they are literal input tokens).
Instead of generating these tokens autoregressively (one by one), the system performs a single parallel-prefill forward pass.
This pass directly splices the input tokens into the Key-Value (KV) cache.
Result: $N$ autoregressive steps are replaced by 1 parallel forward pass, with an acceptance probability of 1 (deterministic), unlike speculative decoding which relies on probabilistic verification.

C. Deterministic Resolver

A pure, deterministic resolver consumes the generated program and the immutable input document to reconstruct the final output. It expands <copy> spans verbatim and inserts <gen> content, ensuring the output is a faithful composition of the input and new text.

3. Key Contributions

The paper establishes the mechanism's viability through three measurable properties, independent of end-to-end model training:

Kernel Speedup (Systems Property):
- Measured on Qwen2.5-1.5B and 7B models (A100 GPU).
- Copying $N$ tokens via parallel prefill is 6.8× to 303× faster than autoregressive generation for span lengths $N \in [8, 512]$ .
- Speedup scales linearly with span length in the overhead-dominated regime and saturates in the compute-bound regime.
Copy Ceiling (Data Property):
- Analyzed on ProbeEdit (text) and HumanEvalPack-Fix (Python/JS code).
- 74% to 98% of gold-standard output tokens can be represented as contiguous line-level copy spans under an "oracle" alignment.
- Combining this coverage with the measured kernel speedup yields a theoretical closed-form wall-clock upper bound ( $bnd_{exact}$ ):
  - 29.0× speedup for ProbeEdit.
  - 3.4× for Python fixes.
  - 4.2× for JavaScript fixes.
  - 13.0× pooled average.
Pipeline Losslessness (Correctness Property):
- Oracle programs (derived via difflib.SequenceMatcher) round-trip through the resolver with 100% byte-exact accuracy on all 482 test cases.
- This proves that any downstream failure in a real system is due to span selection errors (the model picking the wrong lines), not a flaw in the mechanism itself.
- Sensitivity Note: A perturbation study shows that a single-line index error ( $\epsilon=1$ ) causes Exact Match (EM) to drop from 100% to 15.48%, highlighting the need for high-precision span selection.

4. Experimental Results & Analysis

Format Efficiency: Compared to standard formats (Search/Replace, Unified Diff), Copy-as-Decode achieves perfect round-trip fidelity while reducing token budget by avoiding anchor text and hunk headers.
Selector Learnability (SFT Pilot):
- A small-scale supervised fine-tuning (SFT) pilot on Qwen2.5-Coder-1.5B (131–385 examples) improved held-out Exact Match from 0% to 12–17%.
- This confirms the task is learnable, though the current pilot is below production thresholds.
- Failure Mode: The dominant error is "both endpoints off" (incorrect start/end lines), suggesting future training should focus on span-end precision.
Comparison to Speculative Decoding: Unlike speculative decoding which uses a small draft model and probabilistic acceptance, Copy-as-Decode uses the input document as the "draft" with unconditional acceptance, eliminating draft-model training and rejection overhead.

5. Significance and Future Work

Theoretical Bound: The paper provides a rigorous, data-driven upper bound on the efficiency gains possible for LLM editing, showing that significant speedups (up to 29×) are theoretically achievable without changing the base model architecture.
Decoupling: It decouples the "copy" operation from the "generate" operation, allowing the system to leverage hardware parallelism for the former while using standard generation for the latter.
Future Directions:
- Token-Level Extension: Moving from line-level to token-level copying (<copy tokens="a-b"/>) could increase coverage to 91–99%.
- Integration: Integrating the splice primitive into production serving stacks (vLLM, SGLang) with paged attention.
- Training: Scaling the span-selector training to larger models (7B+) and larger datasets to close the gap between the oracle ceiling and real-world performance.

In summary, Copy-as-Decode redefines text editing as a structured decoding problem, leveraging parallel prefill to bypass the latency of autoregressive regeneration for unchanged content, offering a pathway to significantly faster and more efficient LLM-based editing systems.