CS Paper Radar

Easy to anticipate, hard to compute: boundary dependence finds the computed outputs that entropy patching misses

Nicolás Vera Zúñiga

cs.CL ·submitted 2026-10-08 12:03 UTC · v2
code/data

Abstract

Byte-level language models such as the Byte Latent Transformer (BLT) group bytes into patches and run their large global model once per patch. BLT starts a patch where a small model's next-byte entropy is high. We show that under tight patch budgets this rule has a blind spot: positions whose type the preceding text fixes but whose value must be computed, such as the number after "= " in a worked math solution. A nearly certain digit keeps the next byte's entropy near or below log2(10) = 3.32 bits, about BLT-1B's threshold for a 10% budget. In Meta's BLT-1B with patch starts on 10% of bytes, the entropy rule puts a patch start at 16% of the computed results in GSM8K solutions and gets 19.0% of them exactly right given the true preceding text; a boundary after each "=" at the same patch count gets 51.8%, and entropy combined with a label-free boundary-dependence signal gets 67.1% (default layout at 26% of bytes: 76.8%). The gap survives adapting BLT-1B to the budget with low-rank adapters (32.9% vs 72.7%, three runs per rule). In byte models trained from scratch at a 10% budget on a 1.9 GB math corpus, it is not detectable at 1M parameters, appears on final answers at 12M and on both targets at 50M, as training data grow too: at 50M boundary dependence gets 35.9% of computed results against 13.9% for entropy and 78.9% of final answers against 59.0% (3 seeds each), although final answers mostly copy the solution's last number and entropy starts a patch at every one. In BLT-1B the blind spot narrows at larger budgets (entropy covers about 90% of the values right after "= " at 20% of bytes) and in the same solutions rewritten as prose, where a patch start at each value still pays. Boundary dependence, the change in the model's own loss when a patch start is removed or added, measured per two-byte context on text in the same format, finds these positions without labels.

Comment
15 pages, 4 figures, 6 tables. v2: blind spot scoped to type-fixing cues and, in BLT-1B, to tight patch budgets (new Section 5); final answers shown to be mostly copies under teacher forcing; gap no longer said to grow with model size; seed-level intervals and a second training recipe. Code, logs and results: https://github.com/nicoveraz/segresearch (release v2.1.0, doi:10.5281/zenodo.24023934)

Closest papers

Nearest neighbours by meaning across the whole index.

When the next byte's type is fixed: why entropy patching skips computed values under tight budgets

cs.CL cs.LG ·2026-10-15 ·Nicolás Vera Zúñiga
code/data similarity 0.79
Abstract · v2 corrects v1's main claims (new title, abstract and framing; the paper's section "Changes in version 2" lists each change) and is the proj…

The Byte Latent Transformer (BLT) runs a large model once per patch and starts patches where a small model's next-byte entropy is high. Under tight budgets this rule skips computed values, such as the number after "= " in math. On BLT-1B at inference we trace the miss to the cue before a value: when the preceding bytes fix the next byte's type, the patcher's entropy is capped near log2 10 bits, close to a 10% budget's threshold. Entropy then starts a patch at 0% of values after a dollar sign and 19% after "= "; writing "is " instead of "= " raises the 19% to 66%. Version 1's two-byte lookup table, motivated by LZ novelty, acts as a learned detector of cues that tend to precede new values in its fitting text: on the solutions rewritten as prose it covers every value after a dollar sign and none after a plain space, and its margin over entropy falls from +42.1 to -8.9 points, partly because prose gives entropy more starts per value. In BLT-style models trained from scratch (1M-50M parameters, 128-byte context, 3 seeds per rule) and scored by teacher-forced exact match on answer spans, the table beats entropy at 50M by 36.8 points on computed results and 29.6 on final answers, which mostly copy the last computed result. A hand-written marker rule is not distinguishable from the table at 1M and 12M; its 50M control was not run. At 1M and 12M the table ran on a T4 GPU in fp16 and the baselines on an A40 in bf16; at 50M all ran on the A40. End to end, no 1M-50M model solves more than 2 of 100 GSM8K problems. A label-free probe of BLT-1B's patcher finds prose values, mostly after a dollar sign, but costs final answers. In six domains, no rule we tested beat entropy on exact match of whole words and numbers in more than one domain. The positive findings concern tight budgets on cue-formatted text. This version corrects version 1; the work is closed, with no venue intended.

0.41

Where Activation Sparsity and KV-Cache Sparsity Cross in LLM Decoding

cs.LG cs.CLcs.PF ·2026-09-27 ·Jungseob Lee, Seungyoon Lee, Seongtae Hong, Sugyeong Eo, Heuiseok Lim
code/datahighly cited similarity 0.60
Abstract · 22 pages, 6 figures, 17 tables

At each step, decoding one sequence with a large language model rereads the projection weights, whose traffic is fixed, and the key-value (KV) cache, whose traffic grows with context. Activation sparsity trims the first term and KV-cache sparsity the second, yet their reported speedups are hard to compare because each depends on context length and on the dense attention kernel it is measured against. We derive a byte crossover, the context length at which the two savings are equal, together with ideal speedup bounds for each branch and for their composition, from model dimensions and keep ratios alone. We then time both branches and their composition from 2K to 128K tokens on two GPUs after a dense prefill of real text, with dense and sparse modes reading the cache through the same split-K attention kernel. The projection branch leads at short context and the KV branch at long context, with speedups that follow their byte bounds up to fixed kernel costs. Adding these costs, measured in separate sweeps, lets the byte account predict the measured crossings of three keep-ratio pairs, a second model, and a second GPU to within 4.1K tokens. Timing the dense baseline with masked instead of split-K attention inflates the apparent speedup of the same KV policy about fivefold. An attention-scored KV selection answers the same passkey and multi-key placements as dense decoding up to 127K tokens, whereas a KV window misses most of them. Under matched perplexity budgets, activation sparsity composed with this selection decodes 14 to 26% faster than the best single branch on both GPUs. Code is available at https://github.com/js-lee-AI/ByteCross.

0.57

Breaking the Token Ceiling: Distilling Smaller, Stronger Byte Models

cs.CL cs.AIcs.LG ·2026-09-11 ·Kalyani Marathe, Artidoro Pagnoni, Tomasz Limisiewicz, Margaret Li, Mike Lewis +2 more
similarity 0.57
Abstract

Small models are made more capable through distillation from a larger one that shares their tokenization scheme. However, do distilled byte and token models behave similarly in terms of scaling trends as compute and data increases? To enable this comparison, we introduce two variants to efficiently convert token logits to Byte Logits: 1) approximate: Marginalize-It, and 2) exact: End-Of-Token. We then present the first large scale study of overtraining decoder-only dense transformer models varying two dimensions simultaneously: the tokenization scheme (Tokens, Bytes, Bytes w/ eot) and the training objective (Distillation vs. Cross-Entropy), sweeping layer-parameter-matched models with roughly 1 billion parameters up to 1 trillion bytes of data. Across eight benchmarks spanning three categories: Multiple Choice QA, Language Generation, and Machine Translation, we find that Token-1B models outperform byte models (End-Of-Token-1B and Bytes-1B) in the low-FLOP regime but eventually plateau; byte models start worse yet surpass Token-1B models with more compute, reaching a higher downstream task performance ceiling. Extrapolating the average top-1 error vs. validation BPB scaling laws predicts that, asymptotically, distilled End-Of-Token-1B outperforms distilled Token-1B by up to 4%. They are also far more data efficient, matching the performance of distilled Token-1B using only one-sixth of the training data. Moreover, by operating over a small vocabulary of 256 bytes instead of on the order of 100K tokens, they circumvent the need for top-k truncation during logit dumping, while also reducing logit storage costs to roughly one-fifth. Finally, our downstream performance scaling laws predict that our distilled End-Of-Token-1B models asymptotically surpass the Llama 3.2-1B, Gemma-3-1B-pt, and Gemma 2B models on averaged downstream tasks by up to 6.5%, 8.1%, and 2.1%, respectively.

0.45

The Right Byte First: How UTF-16 Helps Multilingual Boundary Prediction

cs.CL cs.LG ·2026-10-15 ·Hyunsik Kim
similarity 0.57
Abstract · 32 pages, 5 figures, 29 tables

Many hierarchical byte-level language models group bytes into patches using a learned boundary predictor whose view of the next codepoint depends on encoding and lookahead. In UTF-8, codepoints of many scripts take three bytes: 8 of 24 bits mark length and continuation, and the first byte carries only 4 high codepoint bits. After the same left context, a mark extending a grapheme cluster and a letter starting the next can thus share their first byte. Universal Byte-Level Encoding (UBE) keeps one- and two-byte UTF-8 encodings but writes these codepoints as two UTF-16 bytes, low byte first, so its first symbol carries 8 low codepoint bits that can distinguish such continuations. We train small causal predictors on matched FineWeb-2 text and evaluate on FLORES-200 under UTF-8, UBE, and UBE's same-length big-endian variant. At one-symbol lookahead, balanced grapheme-boundary error at codepoint boundaries across 17 languages in 13 Brahmic scripts is 8.76% with UTF-8, 8.62% with the big-endian variant, and 0.06% with UBE. When the target instead retains a parent tokenizer's subword cuts at grapheme boundaries, UBE lowers the mean error relative to UTF-8 at the same lookahead by 72.91% in Korean, 35.29% in Chinese, and 67.32-99.55% in eight more scripts. In the seven of them whose main Unicode block fits on one 256-codepoint page, the big-endian variant stays within 3.0% of UTF-8, so the gain follows byte order, not length. In Korean and Chinese, UBE's mean error falls below UTF-8's final mean error after only 25% and 37.5% of training. Which byte comes first thus affects how much lookahead a byte-level boundary predictor needs.

0.17

Spend Bytes on Breadth: Precision-Count Trade-offs for Decode-Time KV Compression in Long Chain-of-Thought Reasoning

cs.CL ·2026-10-05 ·Runguo Li
similarity 0.57
Abstract · 17 pages, 4 figures, 13 tables

Reasoning models write most of their KV cache while decoding long chains of thought (CoT), so the cache has to be compressed online under a fixed memory budget. Decode-time methods mostly decide which tokens to evict. We ask how a fixed byte budget should be split between the number of cached tokens and their precision. BreadthKV spends the bytes on more tokens at low precision, combining quantization with eviction, and picks the bit-width for each model and budget with a 60-problem end-to-end calibration, since offline attention error does not predict it reliably. On three reasoning models and four math and science benchmarks, it scores above eviction alone in 17 of 18 settings and produces shorter outputs. Much of what eviction loses comes from derailed runs, which keep reasoning until the length cap without reaching an answer. On Qwen3-8B at our tightest budget, eviction sends 91% of AIME samples to the cap and BreadthKV 40%. Under the same protocol, BreadthKV is statistically indistinguishable from a joint rate-distortion allocator (RDKV) that uses 27% more KV memory-time, and it outperforms our re-implementation of ThinKV.

0.20

MINE: Entropy-coded Memory-efficient Inference for Large Language Models

cs.LG cs.DCcs.PF ·2026-11-06 ·Emil Schätzle, Markus Püschel
code/data similarity 0.56
Abstract · Submitted to the 15th International Conference on Learning Representations (ICLR), 2027. Artifact: https://doi.org/10.5281/zenodo.23885927

We present MINE (Memory-efficient INference Engine), a lossless entropy coding approach that accelerates single-stream inference of Large Language Models (LLMs), where existing lossless compression methods yield speedups only for specific data types such as BF16 and under additional assumptions. Single-stream decoding is strongly memory-bound, since every weight must be streamed from memory once per generated token and requests cannot be batched in local or low-latency deployments. At the core of MINE is dtANS-LLM, a GPU entropy coding scheme adapted from the prior dtANS to the needs of LLM inference. It exploits the non-uniform distribution of weights, which persists even after quantization, and exposes hyper-parameters that trade compression ratio against decoding cost. We auto-tune these parameters for each tensor and GPU to obtain the Pareto front between model size and decoding latency. MINE integrates into vLLM as a plugin and selects the best kernel configuration for a given memory budget. On Llama 3.1 8B Instruct with a 2.1-bit EntQuant checkpoint, MINE achieves speedups of 2.52x and 1.48x over the fastest baseline on an RTX 4060 Ti and an RTX 5090, at effective bitrates of 2.24 and 3.43 bits per weight. MINE is available as open source.

0.28

DCKV: Learned Transform Coding of the Prompt KV Cache in Hybrid Language Models

cs.LG cs.AI ·2026-10-27 ·Egor Maximov, Aleksei Merkelov, Vasiliy Alekseev, Ivan Krivorotov, Valentin Beliaev +3 more
similarity 0.56
Abstract · 21 pages, 7 figures, 14 tables

Hybrid language models keep a key-value (KV) cache only in their few full-attention layers, but this cache is still the part of a prompt's state that grows with the prompt and that must be stored or moved to reuse it. We present DCKV, a differentiable codec for the KV cache and the first KV-cache codec that is trained end to end. Its transform, its quantizer and its entropy models, which are conditioned on the prompt tokens and on already decoded neighbouring positions, are optimized together against the frozen language model, both for the code length that the entropy models assign and for the change of the model's output. On Qwen3.5-2B, DCKV stores a compressed token in more than 55 times fewer bytes than bf16 at a loss of at most 1.8 points on three long-context benchmarks, and in more than 100 times fewer bytes at a loss of at most 3.6 points.

0.23

Breaking the 1.58-bit Barrier for Ternary LLMs

cs.AI cs.LG ·2026-09-14 ·Evangelos Georganas, Alexander Heinecke, Pradeep Dubey
similarity 0.55
Abstract

Ternary Large Language Models (LLM) store every weight as one of three symbols $\{-1,0,+1\}$, so the cost of a ternary model is conventionally referenced to the information-theoretic $\log_2 3 \approx 1.585$ bits per weight. The prevailing deployment format packs five ternary weights into one byte (five-trit packing), and due to the power-of-two group sizes used in practice this rounds up to $1.625$ bits per weight. This effective storage bit-width treats the three symbols $\{-1,0,+1\}$ as equiprobable. We measure the actual symbol distribution of 29 ternary LLM models and find that zeros account for up to $51.5\%$ of all weights. Motivated by this finding, we introduce BITCOS, a simple distribution-adaptive layout comprised of a dense presence bitmap plus a compacted sign vector, and costs $2 - z$ bits per weight element given a zero density $z$ in the model's weights. BITCOS stores weights more compactly than the five-trit packing in 26 of the 29 tested models, and reaches $1.485$ bits per weight on the sparsest of them. BITCOS is amenable to efficient unpacking on modern processors and GPUs, and we present optimized unpacking sequences for AVX-512, AVX2 and Intel Xe2 GPUs. Measured against production state-of-the-art ternary matrix-vector multiplication kernels, at the zero densities real-world ternary models exhibit, the realized gain with our proposed layout is up to $1.28\times$. Finally, we illustrate end-to-end LLM inference results on 5 different platforms (client and server CPUs, integrated and discrete Xe2 GPUs) where decode throughput improves by up to $1.18\times$ on CPUs and $1.27\times$ on GPUs.

0.52