🤖 machine learning

Scratchpad Patching: Decoupling Compute from Patch Size in Byte-Level Language Models

This paper introduces Scratchpad Patching (SP), a technique that decouples compute from patch size in byte-level language models by dynamically inserting transient scratchpads to mitigate patch lag, thereby enabling larger patches for reduced KV-cache and compute costs without sacrificing modeling quality.

Original authors: Lin Zheng, Vasilisa Bashlovkina, Timothy Dozat, Dan Garrette, Laura Rimell, Joshua Maynez

Published 2026-05-12

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Lin Zheng, Vasilisa Bashlovkina, Timothy Dozat, Dan Garrette, Laura Rimell, Joshua Maynez

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 trying to read a very long book, but you have a strict rule: you can only look at the text in big chunks, like grabbing a handful of pages at a time. This is how modern "patch-based" AI models work. Instead of reading word-by-word (tokens), they read byte-by-byte (the raw computer code for letters) in groups called patches.

The problem with this "grab a handful" approach is a phenomenon the authors call Patch Lag.

The Problem: The "Stale" Handful

Imagine you are reading a paragraph. You grab a chunk of text (a patch) to process.

The Last Page: When you get to the very last page of that chunk, you have the full picture of what you just read. You can make a perfect guess about what comes next.
The First Page: But when you are on the first page of that same chunk, you haven't actually seen the rest of the chunk yet! You are forced to guess based on the previous chunk you read.

If your chunks are huge (say, 16 bytes long), the first 15 bytes are guessing based on "stale" information from the past. The bigger the chunk, the longer this "lag" lasts, and the worse the AI gets at predicting the next letter.

Usually, you have to choose:

Small Chunks: Great accuracy, but the AI has to do a lot of work (slow and expensive).
Big Chunks: Fast and cheap, but the AI makes more mistakes because it's guessing too far ahead.

The Solution: The "Scratchpad"

The authors introduce a clever trick called Scratchpad Patching (SP).

Think of it like this: You are still grabbing those big handfuls of pages (patches) to keep things efficient. But, inside your hand, you have a transient scratchpad.

As you look at the first few pages of the chunk, you quickly jot down notes on your scratchpad.

The Magic: These notes are temporary. You use them to update your understanding immediately so you can make better guesses for the next few pages.
The Catch: Once you finish the chunk and move to the next one, you throw the scratchpad away. You don't keep it in your long-term memory (the "KV cache").

This allows the AI to have the speed of big chunks (because it only saves the final result of the chunk) but the intelligence of small chunks (because it refreshed its knowledge mid-chunk).

How Does It Know When to Use the Scratchpad?

The AI doesn't use the scratchpad for every single letter; that would be too slow. Instead, it uses a "traffic light" system based on Entropy (a fancy word for "surprise" or "uncertainty").

Low Surprise: If the text is boring and predictable (like "the cat sat on the..."), the AI skips the scratchpad. It knows what's coming.
High Surprise: If the text gets complex or unpredictable (like a sudden code variable name or a weird symbol), the AI triggers the scratchpad. It says, "Wait, this is important! Let me pause and re-evaluate everything I've seen so far in this chunk before I guess the next letter."

The Results: The Best of Both Worlds

The paper shows that this method works like a magic switch:

Quality without the Cost: Even when using very large chunks (16 bytes), the AI with Scratchpads performs almost as well as if it were reading byte-by-byte.
Memory Savings: Because the scratchpad is thrown away immediately, the AI doesn't need to store extra memory. It keeps the "KV cache" (the AI's short-term memory) 16 times smaller than a standard byte-by-byte model.
Flexible Speed: You can turn the "scratchpad switch" up or down after the model is trained. If you need it to be super fast, you turn off the scratchpads. If you need it to be smarter, you turn them on. You don't need to retrain the model to do this.

Summary Analogy

Imagine you are a chef cooking a massive stew.

Old Way (Standard Patching): You taste the stew only once every 10 minutes. If you add a spicy ingredient at minute 1, you don't taste it again until minute 10. By then, the flavor might be off.
New Way (Scratchpad Patching): You still only take a full "official" taste every 10 minutes to log the recipe. But, in between, you dip a spoon in whenever the smell changes drastically (high entropy) to adjust your seasoning immediately. You throw the spoon away after tasting, so you don't have to wash a million spoons (memory), but your stew tastes perfect.

The paper proves that by adding these temporary "taste tests" (scratchpads), you can cook a huge pot of stew (process long text) quickly, cheaply, and with perfect flavor.

Technical Summary: Scratchpad Patching (SP)

Problem Statement

Modern language models typically rely on tokenization to segment text into subword units, a process that introduces brittleness, sensitivity to prompt formatting, and difficulties in scaling. Tokenizer-free approaches operating directly on bytes offer a solution but suffer from prohibitive computational costs due to long sequence lengths. To mitigate this, patch-based byte-level models aggregate contiguous bytes into larger "patches," processing them as single units to reduce sequence length and KV-cache footprint.

However, the authors identify a fundamental trade-off in standard patch-based architectures: patch lag. In these models, the main trunk (the primary compute engine) updates its representation only at patch boundaries. Consequently, for any byte within a patch that is not the final one, the model must rely on a "stale" representation from the previous patch to preserve causality. As patch sizes increase to improve efficiency, this lag widens, forcing more predictions to rely on outdated context, which significantly degrades modeling quality. This creates a tight coupling where larger patches yield better efficiency but worse quality.

Methodology: Scratchpad Patching (SP)

The paper introduces Scratchpad Patching (SP), a mechanism designed to decouple compute allocation from patch size, thereby addressing patch lag without increasing the persistent KV-cache footprint.

Core Mechanism

Instead of committing a single representation only at the end of a patch, SP inserts transient scratchpad states at selected internal byte positions within a patch.

Transient States: When a scratchpad is triggered, the model aggregates all bytes seen so far within the current patch, passes this aggregation through the main trunk, and generates a fresh representation.
Causality Preservation: This fresh representation is immediately available for subsequent byte predictions within the same patch, replacing the stale representation from the previous patch.
KV-Cache Efficiency: Crucially, these scratchpad states are not persisted in the KV cache. They are computed on-the-fly during inference and immediately discarded. Only the final "committed" patch representation is stored. This allows the model to perform multiple refinement steps within a patch without increasing the inference-time memory footprint or the effective sequence length seen by the trunk.

Triggering Strategy

To avoid the computational cost of updating at every byte (which would negate the benefits of patching), SP employs a selective triggering mechanism:

Entropy-Based Triggering: A scratchpad update is fired at byte position $n$ if the next-byte prediction entropy of the encoder exceeds a predefined threshold ( $\tau_{SP}$ ).
Content Adaptivity: This strategy selectively allocates compute to "information-dense" regions where the model is uncertain, while skipping predictable regions.
Post-Hoc Adjustment: Because the trigger is based on a threshold applied to the encoder's output, the frequency of scratchpad updates can be adjusted at inference time without retraining, allowing for flexible trade-offs between compute and quality.

Architecture

SP is agnostic to the underlying patchifier (the method used to define patch boundaries). It integrates into the standard five-component patch-based architecture (Encoder, Patchifier, Main Trunk, Unpatchifier, Decoder) by modifying the flow of information within the patch. During training, scratchpad states are unrolled and concatenated into the trunk input with a specialized causal attention mask that prevents scratchpads from attending to future states or other scratchpads, ensuring they only aggregate past bytes within the current patch.

Key Contributions

Decoupling Compute from Patch Size: SP introduces a general mechanism that allows models to use larger patches (for efficiency) without suffering the quality degradation typically associated with increased patch lag.
Addressing Patch Lag: The authors characterize patch lag as a structural failure mode of patch-based models and demonstrate that SP effectively reduces this lag by refreshing context within the patch.
Efficient Inference: SP achieves these improvements while maintaining the same committed patch sequence length and KV-cache footprint as standard patch-based models.
Flexible Compute Control: The method enables post-hoc adjustment of inference-time compute via entropy thresholds, offering a "single-knob" control for efficiency-accuracy trade-offs.

Experimental Results

The authors evaluated SP across four patchifier families (Fixed-size, SpaceByte, Entropy-based, and H-Net) on natural language, code, and mathematics datasets.

Quality-Efficiency Frontier: SP consistently shifts the Pareto frontier of quality (measured by Bits-Per-Byte, BPB) versus efficiency (sequence reduction).
High Patch Sizes: At aggressive patch sizes (e.g., 16 bytes per patch), SP-augmented models match or closely approach the performance of byte-level baselines. For instance, a Fixed-size (p=16) model with SP achieved an average NLU accuracy of 54.2, nearly matching the byte-level baseline (54.1), while using a 16× smaller KV cache and 3–4× less inference compute.
Code Generation: SP significantly improved pass@1 rates on MBPP and HumanEval benchmarks, particularly for large patch sizes where vanilla models struggled.
Compute Allocation: Under FLOPs-matched comparisons, SP models generally matched or outperformed non-SP baselines, suggesting the gains come from better-targeted compute allocation rather than simply adding more compute.
Multilingual Robustness: SP improved the performance of patch-based models across 200 languages (FLORES-200), narrowing the gap to pure byte-level models.

Significance and Claims

The paper claims that Scratchpad Patching represents a practical step toward more flexible end-to-end language models. By allowing models to decide where to allocate compute based on information density rather than inheriting rigid segmentation from a tokenizer or patchifier, SP offers a superior trade-off between persistent sequence length, computational cost, and task performance.

The authors emphasize that SP is a generic technique applicable to many existing patch-based architectures. They note that with SP in place, the performance gap between different patchification strategies (e.g., fixed-size vs. learned boundaries) narrows, suggesting that compute allocation may be a more critical bottleneck than the specific method of defining patch boundaries.

The work is modest in its limitations: it focuses on single-stage patching and does not directly reduce training-time FLOPs compared to standard baselines (though it improves inference efficiency). The authors suggest that future work could explore hierarchical architectures and richer update rules.