Research map / Large language models / Reasoning and chain of thought

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

NeurIPS 2026 · Large language models › Reasoning and chain of thought · approach: Efficient LLM serving · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes Scratchpad Patching, which inserts transient entropy-triggered scratchpads inside byte patches to refresh patch-level context, improving quality-efficiency trade-offs of patch-based byte-level LMs without growing the persistent KV cache.

Problem

Patch-based tokenizer-free models face a trade-off where larger patches reduce compute and KV cache but degrade modeling quality because bytes within a patch rely on stale ("lagged") patch representations.

Approach

Insert transient scratchpad states at selected internal byte positions (triggered by next-byte entropy) that aggregate the bytes seen so far in the patch and pass through the trunk, so later bytes condition on a fresh current-patch state; scratchpads are excluded from the persistent KV cache at inference.

Key results

• Fixed (p=16) improves from 48.0 to 54.2 average NLU accuracy with SP, matching the byte-level baseline (54.1) at 16 bytes per patch.
• At p=16, SP raises MBPP pass@1 from 18.2 to 27.5 while keeping a 16x KV-cache reduction and ~3.7x inference FLOPs/byte reduction.
• After SP, different patchifier families cluster in performance-FLOPs space, and simple fixed-size patching becomes competitive with more complex boundary strategies.

Surprising findings

• Dense every-byte scratchpad updates yield slightly worse BPB than selective entropy thresholds on natural language.
• SP can degrade validation BPB for H-Net under strict FLOPs matching, attributed to redundant scratchpads adjacent to learned boundaries.

Limitations

• SP does not directly reduce training-time FLOPs compared to standard patch-based baselines.
• Evaluated only on single-stage patching; multi-stage hierarchical settings (H-Net, AU-Nets) left for future work.
• Scratchpads simply recompute intermediate representations; richer recurrent-style update rules are unexplored, and at most one scratchpad per byte position.

Experimental setup

Datasets: DCLM Stack v2 OpenWebMath FLORES-200

Benchmarks: MBPP HumanEval ARC-Easy ARC-Challenge BoolQ HellaSwag OpenBookQA PIQA WinoGrande MMLU FLORES-200

Metrics: bits-per-byte pass@1 accuracy sequence reduction factor FLOPs/byte reduction KV cache reduction

Baselines: Byte-level Transformer Tokenizer-based Transformer Fixed-size patching SpaceByte Entropy-based patching H-Net

Builds on: MegaByte SpaceByte Byte Latent Transformer H-Net Mixture-of-Depths

Closest papers by meaning

• Beyond Next Token Prediction: Patch-Level Training for Large Language Models (ICLR 2025 · similarity 0.88)
• PatchKV: Weight Space Compensation of KV Cache (NeurIPS 2026 · similarity 0.87)
• Language Models Can Predict Their Own Behavior (NeurIPS 2025 · similarity 0.86)
• MrT5: Dynamic Token Merging for Efficient Byte-level Language Models (ICLR 2025 · similarity 0.86)
• Co-PatcheR: Collaborative Software Patching with Component-specific Small Reasoning Models (NeurIPS 2025 · similarity 0.86)
• Exact Byte-Level Probabilities from Tokenized Language Models for FIM-Tasks and Model Ensembles (ICLR 2025 · similarity 0.86)