PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2605.09630v1cs.CLcs.LG

TL;DR

Patch-based byte-level models trade efficiency for stale within-patch context as patches grow, motivating a way to decouple compute allocation from patch size. Scratchpad Patching inserts transient, selectively triggered states within patches to reduce this lag. Across experiments, it improves the quality-efficiency frontier and can approach byte-level quality with substantially lower cache and inference costs.

  • Problem

    Larger patches reduce compute and KV-cache usage but widen patch lag, making byte predictions rely increasingly on stale patch-level context and degrading modeling quality.

  • Method

    Scratchpad Patching inserts transient within-patch states that aggregate observed bytes and refresh context, using next-byte entropy to allocate updates selectively.

  • Results

    SP consistently improves the quality-efficiency frontier across patching schemes and, at 16 bytes per patch, matches or closely approaches the byte-level baseline with a 16× smaller patch KV cache and 3–4× less inference compute.

  • Takeaways & Limitations

    SP enables patch-based byte-level models to use larger patches while allocating compute within patches rather than fixing it solely through patch size or boundary placement.

  • Takeaways & Limitations

    The study focuses primarily on single-stage patching, does not directly reduce training-time FLOPs, and leaves richer scratchpad updates and hierarchical settings for future work.

Abstract

from arXiv · show

Tokenizer-free language models eliminate the tokenizer step of the language modeling pipeline by operating directly on bytes; patch-based variants further aggregate contiguous byte spans into patches for efficiency. However, the average patch size chosen at the model design stage governs a tight trade-off: larger patches reduce compute and KV-cache footprint, but degrade modeling quality. We trace this trade-off to patch lag: until a patch is fully observed, byte predictions within it must rely on a stale representation from the previous patch to preserve causality; this lag widens as patches grow larger. We introduce Scratchpad Patching (SP), which inserts transient scratchpads inside each patch to aggregate the bytes seen so far and refresh patch-level context for subsequent predictions. SP triggers scratchpads using next-byte prediction entropy, selectively allocating compute to information-dense regions and enabling post-hoc adjustment of inference-time compute. Across experiments on natural language and code, SP improves model quality at the same patch size; for example, even at $16$ bytes per patch, SP-augmented models match or closely approach the byte-level baseline on downstream evaluations while using a $16\times$ smaller KV cache over patches and $3$-$4\times$ less inference compute.

1 Introduction

Patch-based byte-level models improve efficiency by aggregating bytes, but larger patches worsen stale-context effects. Scratchpad Patching addresses this patch lag by adding transient within-patch representations, improving quality-efficiency trade-offs without increasing committed patch states.

  • Larger patches reduce computation and KV-cache usage but update patch-level context less often, creating a quality-efficiency trade-off.
  • Patch lag arises because only the final byte in a patch uses its completed representation, while earlier bytes rely on the previous patch context.
  • Scratchpad Patching inserts transient states at selected internal byte positions to aggregate observed bytes and refresh context for subsequent predictions.
  • SP improves the quality-versus-patch-size frontier across patchifier families, allowing larger patches and smaller KV caches without the usual quality penalty.
  • At 16 bytes per patch, SP models match or closely approach the byte-level baseline with a 16× smaller patch KV cache and 3–4× less inference compute.
  • Under comparable FLOPs budgets, SP narrows performance gaps among patchifier families, making simple fixed-size schemes competitive with complex boundary strategies.

2 Background

Byte-level models avoid tokenizer preprocessing but face long sequences, motivating patch-based architectures that aggregate bytes into shorter patch sequences. Their causal design creates patch lag because earlier bytes cannot use the current patch’s trunk representation.

  • Tokenization shortens sequences and defines prediction units, but its fixed external segmentation can make models sensitive to formatting and introduce brittleness.
  • Tokenizer-free byte-level modeling represents text directly as UTF-8 bytes and predicts each byte autoregressively without tokenization.
  • Patch-based byte-level models aggregate contiguous bytes into higher-level patches to reduce the number of sequence elements processed by the main trunk.
  • The common architecture contains an encoder, patchifier, main trunk, unpatchifier, and decoder that mediate between byte-level and patch-level representations.
  • Causality lets only the final byte of each patch condition on that patch’s trunk output; earlier bytes use the previous patch output, producing patch lag.
  • As average bytes per patch increase, patch lag widens and modeling quality becomes more sensitive to patch size.
  • In fixed-size patching, patch boundaries are regular, while adaptive scratchpad updates respond to elevated next-byte entropy and yield to patchification at coincident positions.

3 Scratchpad Patching

Scratchpad Patching refines patch representations at selected within-patch positions, reducing patch lag while retaining only committed patch states for inference. Its specialized training layout supports parallel processing, and transient scratchpads add no KV-cache overhead at inference.

  • Patchification with Scratchpads: SP progressively refines each patch representation by aggregating increasingly long byte prefixes and passing them through the trunk.Scratchpads are transient states, while each patch also has a committed representation.
  • Patchification with Scratchpads: Each non-final byte can condition on a current scratchpad rather than the previous patch representation, reducing lag to the gap since the latest scratchpad.Patchification takes precedence when a scratchpad trigger coincides with a patch boundary.
  • Selective Scratchpad Updating: Scratchpad updates are selected by next-byte prediction entropy, concentrating computation at positions with elevated uncertainty.The trigger is pn := 1[Hn>τSP], with fixed patch boundaries retained unless a boundary coincides with a trigger.
  • Parallel Training with Specialized Attention Masking: During training, scratchpads and committed representations are concatenated so byte losses can be computed in parallel under a specialized causal attention mask.Elements in a patch attend to themselves and earlier committed patch representations, while scratchpads are not attended to by other elements.
  • Parallel Training with Specialized Attention Masking: The training layout includes Tℓ scratchpads followed by committed representation zℓ for each patch, with Tℓ=0 recovering the standard patch-based layout.The specialized mask preserves the intended causal structure despite parallel training.
  • Efficient Inference with Scratchpad Overriding: At inference, scratchpads are computed transiently and overridden immediately, so only finalized patch representations remain in the KV cache.SP therefore adds no KV-cache overhead despite using additional transient states.

4 Experiments

The experiments evaluate SP across patchifier families on validation BPB, natural-language understanding, and code generation, emphasizing quality-efficiency trade-offs. SP improves performance especially for larger patches while reducing persistent sequence length and inference cost.

  • Experimental Setup: The evaluation measures BPB, MBPP and HumanEval pass@1, NLU accuracy, persistent sequence reduction, and FLOPs/byte reduction relative to the byte-level baseline.Models share an encoder-trunk-decoder backbone and differ primarily in patchification mechanism.
  • Main Results: SP shifts the quality-efficiency frontier toward lower validation BPB at fixed sequence reduction and larger patches at fixed BPB.The gains are strongest for aggressive patch sizes such as p = 8 and p = 16.
  • Main Results: SP models can achieve lower BPB than the byte-level baseline while retaining shorter trunk sequences and FLOPs savings.Some variants also reach lower BPB and shorter trunk sequences than the tokenizer baseline, with moderately higher training FLOPs.
  • Natural Language Understanding: Fixed-size patching with p=16 improves average NLU accuracy from 48.0 to 54.2 with SP, matching the byte-level baseline at 54.1.SP also narrows performance differences among patchifier families on the eight NLU benchmarks.
  • Code Generation: SP improves code-generation pass@1 across patchifier families while largely preserving KV-cache reductions and recovering quality at p=8 and p=16.At larger patch sizes, FLOPs reductions are comparable to or larger than the tokenizer baseline.

5 Analyses

The analyses test whether SP's gains persist under matched compute, across languages, and when inference-time patch size or scratchpad frequency changes. They find targeted compute allocation, multilingual improvements, and post-hoc compute-quality control without retraining.

  • FLOPs-matched Performance Comparison: Under equal training FLOPs, SP matches or improves BPB for most patchifier families, indicating gains from targeted compute allocation rather than a larger budget.H-Net is the main exception, with degraded validation BPB under strict FLOPs matching.
  • Multilingual Performance: Adding SP improves the ranking of patch-based byte-level models across the 200-language FLORES-200 validation set.The pure byte-level model remains strongest and most consistent, while the tokenizer-based model performs poorly on average.
  • Inference-time Flexibility: SP supports post-hoc inference-time adjustment along two axes: realized patch size and scratchpad update frequency.These adjustments require no retraining.
  • Patch Size Variation: SP-trained models degrade gracefully when realized inference-time patch size differs from training, unlike non-SP models, which suffer substantial performance drops.The patch-size variation uses entropy-based patching with default threshold τP = 2.5.
  • Scratchpad Frequency Variation: Reducing scratchpad density trades compute for modest quality loss, while increasing it recovers performance across validation BPB on code and MBPP pass@1.This exposes a smooth compute-quality curve through a single inference-time control without retraining.

6 Related Work

Related work spans alternatives to tokenization, byte-level language modeling, patch-based byte architectures, and adaptive computation. SP differs by allocating content-adaptive compute independently of patch size and boundary rules.

  • Language Modeling Beyond Tokenization: Alternative text representations include morphology-driven byte encodings, compressors, concept-level semantic units, and pixel-rendered representations.These approaches address limitations associated with tokenized text through different representation choices.
  • Byte-level and Patch-based Modeling: Byte-level models such as ByT5, MrT5, and MambaByte avoid external tokenization, while patch-based architectures shorten long byte sequences through pooled representations.Patch-based designs are discussed as a response to the computational cost of long byte sequences.
  • Patch-based Architectures: Patch-based byte models differ mainly in how they determine patch boundaries, including fixed-size, delimiter-based, entropy-based, and learned-router methods.The surveyed architectures process shorter patch-level or latent sequences in a main trunk.
  • Adaptive Compute Allocation: SP enables fine-grained, content-adaptive compute allocation independently of patch size and boundary rule.The resulting trade-off covers persistent sequence length, compute, and task performance.
  • Adaptive Compute Allocation: SP connects to adaptive-computation research while applying that principle to patch-based byte modeling.Its central design decouples compute allocation from patch size or persistent sequence length.

7 Conclusion

Scratchpad Patching improves patch-based tokenizer-free byte-level models by inserting transient states within patches, decoupling compute allocation from effective patch size and addressing patch lag. The work shifts the quality-efficiency frontier, while leaving multi-stage patching, richer update rules, and explicit training-compute savings for future study.

  • Conclusion: Scratchpad Patching inserts transient scratchpad states within patches to decouple compute allocation from effective patch size and address patch lag.Patch lag is the structural gap between next-byte predictions and the most recent available patch representation.
  • Conclusion: SP consistently shifts the quality-efficiency frontier across a wide range of patching schemes.The method enables models to allocate compute more flexibly instead of inheriting that decision from a tokenizer or patchifier.
  • Limitations: The study primarily evaluates single-stage patching and leaves systematic investigation of hierarchical multi-stage architectures to future work.SP is described as compatible in principle with hierarchical architectures, but those settings are not systematically studied.
  • Limitations: SP does not directly reduce training-time FLOPs compared with standard patch-based baselines.Designing scratchpad formulations with more explicit compute savings remains future work.

A Model Architecture Details

The experiments compare byte-level, tokenizer-based, and patch-based byte-level Transformers under roughly matched parameter counts. Patch-based models share a five-component byte-to-patch architecture, while the implementation retains full self-attention and varies mainly in patchifier design.

  • Model Families: The study compares byte-level, tokenizer-based, and patch-based byte-level Transformers with roughly equal total parameter counts.The byte-level baseline operates directly on UTF-8 bytes, while the tokenizer baseline uses subword tokens.
  • Byte-level Transformer: The byte-level baseline predicts the next byte autoregressively without patching or tokenization using a vocabulary of 320 symbols.The vocabulary contains 256 UTF-8 byte values and 64 reserved sentinel tokens.
  • Patch-based Models: Patch-based architectures use an encoder, patchifier, main trunk, unpatchifier, and decoder.The encoder and decoder operate at byte-level resolution, while the main trunk processes the patch-level sequence.
  • Attention: Full self-attention is used in the encoder, main trunk, and decoder, while more efficient layer designs are left for future work.Replacing full attention with sliding-window attention produced a slight validation BPB regression that was not statistically significant.
  • Patchifier Variants: All patch-based baselines share the same backbone and differ primarily in patchifier implementation, except H-Net, which also modifies the unpatchifier.Compared patchifiers include fixed-size patching, SpaceByte, entropy-based patching, and H-Net.

B Implementation Details

The implementation forms patch representations by locally aggregating byte states, then uses several patchification strategies and entropy-triggered scratchpad updates. Ablations retain patchifier cross-attention and mean pooling because they provide the reported improvements.

  • Patchifier: The patchifier partitions bytes into contiguous segments and forms each patch representation by local cross-attention over byte hidden states.Each patch query attends only to byte positions within its corresponding patch, and the resulting representations are projected to trunk dimensionality.
  • Unpatchifier: Trunk outputs are broadcast back to byte positions by the unpatchifier and fused with encoder residuals before decoding.This connects patch-level processing back to byte-level predictions.
  • Ablations: Cross-attention at the patchifier improves BPB, whereas adding it at the unpatchifier provides no measurable benefit.The experiments therefore retain cross-attention only at the patchifier.
  • Ablations: Mean pooling yields consistent but small improvements over using the final byte state as the patch query.Mean pooling is adopted as the default strategy.
  • Patchification Strategies: Fixed-size, delimiter-based, entropy-based, and H-Net patchifiers provide the principal implementation variants.Fixed-size widths are 2, 4, 8, or 16 bytes, while SpaceByte averages roughly 6.3 bytes per patch on the training corpus.
  • Scratchpad Configuration: Scratchpad updates occur when encoder next-byte prediction entropy H_n exceeds the threshold τ_SP.The default thresholds are τ_SP = 1.5 for fixed-size and SpaceByte, 1.0 for entropy-based patching, and 2.5 for H-Net.
  • Entropy Prediction: The entropy predictor uses two additional Transformer layers and an auxiliary language-modeling head trained jointly with the main head.For entropy-based patching, the existing auxiliary head is reused with separate thresholds for patch boundaries and scratchpad updates.
  • Design Choices: Stopping gradients from the auxiliary predictor and using two Transformer layers outperform the tested alternatives.Adding more layers or capacity does not yield further improvements.

C.2 Training Hyperparameters

Training comparisons fix the number of raw bytes seen while allowing total training FLOPs to vary with sequence shortening and scratchpad refinement. Models use common optimization settings and approximately 2B parameters over 50,000 steps.

  • Comparison Regime: The experiments fix the number of raw bytes seen across models to create a data-bounded comparison.Total training FLOPs still vary because patching shortens the main-trunk sequence and SP adds refinement steps.
  • Training Setup: All models have roughly 2B parameters and train for 50,000 steps with a batch size of 8M bytes.This corresponds to approximately 400B bytes of training data.
  • Context and Optimization: Byte-level and patch-based models use an 8,192-byte context, while the tokenizer-based model uses 2,216 tokens corresponding to roughly 8,192 bytes.The sequence batch size is 1,024 across the reported setups.

D Evaluation Details

The evaluation covers validation BPB, code generation, and multiple-choice natural language understanding. Across these downstream settings, SP variants achieve higher performance at a given sequence reduction factor.

  • Evaluation Tasks: Models are evaluated on validation Bits-Per-Byte, code generation, and multiple-choice natural language understanding tasks.Validation BPB uses held-out code, natural language, and math splits; code generation uses MBPP and HumanEval; natural language understanding spans eight benchmarks.
  • Code Generation: Code generation is measured with pass@1 on MBPP and HumanEval using five samples per problem.The evaluation uses 3-shot prompting for MBPP, zero-shot prompting for HumanEval, and fixed temperature-0.2 nucleus sampling with p = 0.95.
  • Downstream Results: SP variants consistently achieve higher downstream task performance at a given sequence reduction factor across code generation and natural language understanding.The comparison includes pass@1 on MBPP and HumanEval and average accuracy over eight natural language benchmarks.

E.2 Ablations of Scratchpad Patching Strategies

The ablations show that entropy-based scratchpad triggering provides the best compute-quality trade-off, while scratchpads improve over the non-SP baseline across triggering strategies. Dense updates offer limited additional benefit and can be less effective for natural language, while interactions vary across patchifier families.

  • Triggering Strategies: Entropy-based triggering achieves the best compute-quality trade-off across code, math, and natural language.The ablation uses fixed-size patching with p = 8 and varies entropy thresholds, fixed strides, and whitespace-based updates.
  • Triggering Strategies: All tested triggering strategies improve consistently over the non-SP baseline, including simple whitespace-based heuristics.The non-SP baseline corresponds to the least frequent update setting in the fixed-size patching ablation.
  • Domain Differences: On code and math, τSP = 1.0 nearly matches dense τSP = 0 updates despite requiring roughly 3× fewer training FLOPs.The text reports marginal BPB differences between selective and every-position updates in these domains.
  • Domain Differences: On natural language, dense updates yield slightly worse BPB than selective thresholds such as τSP = 1.0 or 1.5.The paper hypothesizes that reprocessing highly predictable prose positions can dilute training signal and favor local patterns over long-range dependencies.
  • Patchifier Interactions: H-Net scratchpad updates often couple closely to patch boundaries, causing redundant computation on adjacent bytes and sometimes smaller gains or inefficiencies.For SpaceByte, patchification takes precedence when triggers coincide; entropy-based patching uses distinct thresholds to separate allocations.
Loading 2605.09630v1…