PaperlayerView exact revision on arXiv

Source-linked AI summary

zip2zip++: Towards Inference-Time Token Compression with Minimal Quality Loss

Saibo Geng, Andrea Gentilini, Xinxian Ma, Nathan Ranchin, Yunzhen Yao, Robert West

arXiv:2610.13605v1cs.CL

TL;DR

Fixed-vocabulary tokenization can over-segment some inputs, while prior LZW-based dynamic vocabularies reduce token use but can degrade perplexity and downstream performance. The paper introduces changes to hypertoken embeddings, RoPE positioning, and the LZW codec. Together, these changes substantially narrow the gap to uncompressed baselines.

  • Problem

    Fixed vocabularies can over-segment domain-specific or structured inputs, while prior LZW-based dynamic vocabularies reduce token use but have reported substantial perplexity increases and downstream degradation.

    Source: §1 · pp. 1–2

  • Method

    The paper modifies dynamic hypertoken embeddings and positioning and introduces codec and evaluation changes to address quality losses in LZW-based token compression.

    Source: §1 · p. 2

  • Results

    The four targeted modifications substantially narrow the gap to uncompressed baselines.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Compact tokenization can reduce inference cost and KV-cache memory while increasing effective context within a fixed token budget.

    Source: §1 · p. 1

Abstract

from arXiv · show

Dynamic vocabularies built on-the-fly via Lempel-Ziv-Welch (LZW) compression let a language model represent the same text in fewer tokens, but prior work shows that this efficiency comes at a cost to reasoning and perplexity. We show that this quality gap is not a fundamental price of compression but can be substantially closed through targeted improvements to the compression layer and LZW codec, without modifying the underlying pretrained language model. Our analysis reveals four key issues: (1) LZW's compression algorithm creates an implicit conflict between the input embedding and the output embedding, a tension that a single shared embedding cannot resolve; (2) naively applying RoPE to LZW-compressed sequences ignores that merged tokens can span multiple tokens; (3) merging certain tokens (notably digits) disproportionately hurts downstream accuracy; and (4) dynamic vocabularies introduce an inherent segmentation ambiguity that confounds standard evaluation. We address these through decoupled input/output dynamic embedding layer, size-aware RoPE positioning, and a modified LZW codec supporting selective merges and multi-view segmentations. Across four models, our recipe improves perplexity on every corpus we evaluated as well as mathematical reasoning accuracy, closing roughly half the quality gap between zip2zip and the uncompressed baseline at a similar compression ratio on general text. This represents a significant step toward lossless adaptive-vocabulary compression for language models.

1 INTRODUCTION

Fixed vocabularies can over-segment domain-specific text, while per-domain expansion requires intervention and may not generalize. The paper targets quality losses in dynamic LZW tokenization with changes to embeddings, positions, and the codec.

1 INTRODUCTION

  • Fixed vocabularies can over-segment domain-specific terminology, low-resource languages, and structured data, wasting inference steps and context capacity.Compact tokenization can reduce inference cost and KV-cache memory while increasing effective context within a fixed token budget.Source: §1 · p. 1
  • Domain-adaptive retraining and language-specific vocabulary expansion require per-domain intervention and do not generalize to new domains.Source: §1 · p. 2
  • Geng et al. (2025) use LZW to build hypertokens online and reduce token usage by up to 40%, but report substantial perplexity increases and sharp degradation on some tasks.Their approach uses lightweight LoRA finetuning to mitigate the effects of changing the vocabulary.Source: §1 · p. 2
  • The paper identifies four targeted changes—decoupled residual embeddings, identity initialization, size-aware RoPE, Fault-Tolerant LZW, and Multi-View Perplexity—that substantially narrow the gap to uncompressed baselines.The changes address embedding geometry, hypertoken positioning, fragile merges, and segmentation ambiguity.Source: §1 · p. 2

2 BACKGROUND: ZIP2ZIP

zip2zip augments a fixed base vocabulary with LZW hypertokens built online from recurring token sequences. A hyper-encoder supplies their embeddings and unembeddings, and continued pretraining adapts the model to compressed sequences.

2 BACKGROUND: ZIP2ZIP

  • LZW builds a dynamic hypertoken vocabulary online by merging recurring base-token subsequences, with the maximum merge size controlling compression granularity.New hypertokens become available for reuse as the input stream is processed.Source: §2 · p. 2
  • A hyper-encoder computes input embeddings from constituent base-token embeddings, while an output hyper-encoder supplies unembeddings so the model can score the combined vocabulary.The output hyper-encoder may be tied to the input hyper-encoder.Source: §2 · p. 2
  • Continued pretraining on compressed sequences adapts a pretrained model to the combined token space; LoRA training can update only the hyper-encoder and low-rank adapters using as few as 100M tokens.Source: §2 · pp. 2–3

3 HYPERTOKEN ENCODER ARCHITECTURE

LZW’s prefix-closed dictionary creates a conflict between output embeddings that score competing prefix-related tokens and input embeddings that serve next-token prediction. The paper hypothesizes that one shared encoder cannot satisfy both geometries.

3 HYPERTOKEN ENCODER ARCHITECTURE

  • LZW registers each hypertoken only after its own prefix, making the dynamic vocabulary a trie and the combined vocabulary a non-uniquely decipherable code.Multiple segmentations can map to the same base-token string.Source: §3.1 · p. 3
  • At a decoding position, prefix-related hypertokens compete against the same hidden state, favoring prefix-aligned output embeddings.Source: §3.1 · p. 3
  • The input encoder instead serves next-token prediction with a balanced geometry, leading the authors to hypothesize that one shared encoder cannot serve both objectives well.Source: §3.1 · p. 3

A. Prefix Aligned Codes B. Suffix Aligned Codes

The section addresses conflicting input and output embedding geometries, hypertoken scale mismatch, and position assignment for compressed spans. It also considers hierarchical composition to support larger evaluation-time merges.

A. Prefix Aligned Codes B. Suffix Aligned Codes

  • LZW’s prefix-closed dictionary favors prefix-aligned output embeddings, while the input encoder is balanced; the authors untie the encoders to serve these different geometries.The output encoder is prefix-aligned in substitution probes, whereas input substitution effects are similar at both ends.Source: A. Prefix Aligned Codes B. Suffix… · pp. 3–4

3.2 RESIDUAL HYPER-ENCODER WITH IDENTITY INITIALIZATION

  • Zero-initializing a residual hyper-encoder makes each hypertoken start at its first constituent’s embedding, removing the early loss shock and improving final loss and accuracy.The change yields step-10 loss 3.97 and gradient norm approximately 50, versus the prior step-10 loss of 70–100.Source: §3.2 · pp. 4–5

3.3 SIZE-AWARE ROPE

  • Size-aware RoPE assigns a hypertoken a position from its base-token span, preserving the positions of remaining base tokens; a learned gate can interpolate toward default compressed indexing.The considered fixed choices are the span’s start, mean, or end position.Source: §3.3 · p. 5
  • Adding end indexing to the digit-protected, untied model raises GSM8K by 2.7 points at unchanged perplexity; the learned rule matches its perplexity but not its reasoning.The authors therefore retain parameter-free end indexing.Source: §3.3 · p. 5

3.4 HIERARCHICAL HYPER ENCODER

  • A flat hyper-encoder’s positional structure is tied to its training-time maximum merge size, whereas a hierarchical encoder reuses one pairwise composer as evaluation-time spans grow.Larger merge sizes add recursion steps without new parameters or length-specific embeddings.Source: §3.4 · p. 6

4 A FAULT-TOLERANT LZW CODEC

The section modifies LZW to tolerate imperfect neural compression and protect selected tokens from merging. It also evaluates compressed predictions across equivalent segmentations, rather than only the greedy parse.

4 A FAULT-TOLERANT LZW CODEC

  • A compressed string can have multiple valid segmentations that decode identically, while greedy LZW selects only one canonical parse.Neural generation may produce a valid alternative, so canonical-only evaluation underestimates performance.Source: §4 · p. 6
  • A guarded merge loop recovers from missed merges by absorbing known dictionary combinations and inserting entries only for genuinely novel combinations.On valid compressed input it recovers the standard LZW dictionary; on imperfect input it emits base tokens rather than cascading garbage.Source: §4 · p. 6
  • The codec bypasses merging for protected special tokens and tokens such as digits, whose merging can hurt language-model performance.Protected tokens are emitted directly as base tokens.Source: §4 · p. 7

4.1 MULTI-VIEW PERPLEXITY

  • Multi-view likelihood aggregates probability across valid segmentations of the expanded target instead of penalizing a non-canonical but equivalent parse.For base tokens, the valid-segmentation set contains only the original token.Source: §4.1 · p. 7
  • A merge cap bounds the number of valid segmentations, allowing exact multi-view evaluation in one additional forward pass at 1.6× standard perplexity cost.The evaluation uses sequence packing and a tree-structured attention mask.Source: §4.1 · p. 7

5 EXPERIMENTS

Across four instruction-tuned models, the experiments compare zip2zip++ with zip2zip and an uncompressed control on perplexity, accuracy, generation, and long-context tasks. The recipe improves perplexity across corpora and shows especially strong mathematical-reasoning gains, while ablations and length-generalization tests probe its components and scope.

Evaluation I: Perplexity and Few-Shot Accuracy

  • zip2zip++ lowers perplexity on all four corpora at both model scales under strict and multi-view scoring, and matches or beats zip2zip on most accuracy tasks.The recipe closes roughly a third of the strict gap to Uncompressed, with multi-view scoring accounting for a further sixth to a third as an evaluation correction.Source: Table 2 · p. 8, Table 1 · p. 8, §5 · p. 8

Evaluation II: Downstream Tasks

  • GSM8K rises from 0.36 to 0.68 at 3.8B and from 0.51 to 0.69 at 14B; MATH-500 rises from 0.15 to 0.24 and from 0.22 to 0.30.Code generation and instruction-following results do not improve consistently; at 14B zip2zip++ trails zip2zip on both tasks.Source: Table 3 · p. 8, §5 · p. 8

Evaluation III: Long-Context Understanding

  • At 3.8B, RULER accuracy rises from 46.6 to 70.7 at 4K and from 15.2 to 52.8 at 32K, while remaining below Uncompressed.All recipes used 2,048-token finetuning sequences and inference-time LongRoPE adaptation, limiting the long-context interpretation.Source: Table 3 · p. 8, §5 · p. 9

Evaluation IV: Ablation Study

  • Protecting digits moves GSM8K from 0.36 to 0.61; three architectural changes add seven points, while 200B extra compressed-pretraining tokens improve WikiText perplexity to 1.63 as GSM8K falls from 0.68 to 0.64.The ablation also reports +1.6 points of mean multiple-choice accuracy and −0.025 WikiText byte-perplexity from untying hyper-encoders.Source: Table 4 · p. 9, §5 · p. 9

Evaluation V: Hypertoken Length Generalization

  • An M3 model evaluated with merge size 4 tracks a native M4 model closely, with a WikiText byte-perplexity gap under 0.1%.The model forms and uses unseen length-4 merges; performance stays within a few percent on repeated-window text designed to make them frequent, with the largest jump at the training boundary and a later plateau.Source: Figure 6 · p. 9, §5 · pp. 9–10

6 CONCLUSION

The proposed architectural and algorithmic alternatives strongly outperform original zip2zip on perplexity across corpora and model scales, while roughly halving the distance to an uncompressed model. The quality gap remains open, but the result is a step toward quality-neutral adaptive tokenization.

6 CONCLUSION

  • The recipe strongly outperforms zip2zip on perplexity at both model scales and roughly halves the distance to an uncompressed model, though it does not close the gap.Source: §6 · p. 10

AI USE STATEMENT

The paper reports AI assistance in programming, writing, brainstorming, and literature review, while stating that tools did not run experiments or produce reported numbers. It also summarizes its ethics scope and identifies materials for reproduction.

AI USE STATEMENT

  • AI tools assisted with programming, paper writing and mock reviewing, brainstorming, scientific discussion, and literature review, but not experiments or reported numbers.The authors state that they reviewed the assisted work and take responsibility for the paper.Source: AI USE STATEMENT · p. 10

ETHICS STATEMENT

  • The work uses standard public datasets and benchmarks, adds no new data collection or human subjects, and notes that lower inference cost applies to beneficial and harmful uses alike.Source: ETHICS STATEMENT · p. 10

REPRODUCIBILITY STATEMENT

  • Reproduction details, per-component results, seed spread, and unsuccessful branches are reported in Sections C and D, and code and checkpoints are publicly available.Source: REPRODUCIBILITY STATEMENT · p. 10

A RELATED WORK

Prior work shortens text through fixed-vocabulary changes, lossy input compression, or dynamic segmentation, each with distinct constraints. The paper situates zip2zip’s quality issues in embedding, positional, digit-merging, and evaluation challenges.

Adapting a fixed vocabulary

  • Fixed-vocabulary adaptation produces a vocabulary fixed after training, requiring per-domain intervention and missing repetition specific to an input.Approaches add domain tokens or alter vocabulary-learning algorithms, including relaxing BPE’s word-boundary constraint (Gee et al., 2023; Liu et al., 2025).Source: A RELATED WORK · p. 15

Compressing the input

  • Prompt-compression methods are lossy and affect only input, whereas LZW codes remain aligned with original token boundaries and can adapt an existing model without retraining.Lester et al. (2024) train on arithmetic-coded text and find the resulting codes hard to model.Source: A RELATED WORK · p. 15

Dynamic and byte-level architectures

  • Dynamic and byte-level architectures learn segmentation jointly with the model and lack a lossless codec to a canonical token stream; zip2zip instead adds LZW hypertokens to BPE and adapts a pretrained model with LoRA.Dynamic Vocab (Liu et al., 2024b) also grows vocabulary during generation, but differs in entry creation and training.Source: A RELATED WORK · p. 15

The interfaces a compressed stream disturbs

  • The three architectural findings concern incompatible input/output embedding geometries, variable-span position handling, and digit merging as the largest source of degradation.Exempting digits from merging recovers most of the digit-related degradation.Source: A RELATED WORK · p. 15

Tokenization ambiguity and marginal likelihood

  • 29–36% of zip2zip++’s strict perplexity deficit against its uncompressed control is a scoring artefact rather than a modelling failure.Multi-view perplexity marginalizes over valid segmentations, whose number grows exponentially with span length in the prefix-closed LZW dictionary.Source: A RELATED WORK · pp. 15–16

Other routes to fewer forward passes

  • Speculative decoding reduces latency by spending extra compute while leaving vocabulary and output distribution unchanged; adaptive tokenization shortens sequences but must preserve quality across a changed vocabulary.Adaptive tokenization also reduces KV-cache and context consumption.Source: A RELATED WORK · p. 16

B EMBEDDINGS PROBES

The embedding probes find that output hypertoken representations favor shared prefixes, while input representations track broader constituent overlap. Raw BPE tables show no comparable asymmetry, locating the learned patterns in the hyper-encoders.

Substitution Details

  • Raw BPE embedding tables remain within rK 0.71–1.33 at every K, unlike the output hyper-encoder’s 4.8–6.6 asymmetry.The control applies the identical substitution probe directly to pretrained Win and Wout, with no hyper-encoder.Source: B EMBEDDINGS PROBES · p. 16, Figure 7 · p. 16

Sequence probe

  • The sequence probe compares pairwise cosine similarities among every contiguous sub-span of length at least two in “It is a dog.”It tests whether similarity follows the nested prefix chain or the number of shared constituents.Source: B EMBEDDINGS PROBES · p. 16
  • The output embeddings form a prefix-chain block at cosine similarity ≥0.88, while input similarity tracks constituent overlap: ABCD is closer to BCD (0.71) than AB (0.48).The output pairs spanning the two blocks have cosine similarities of 0.21–0.44.Source: B EMBEDDINGS PROBES · p. 16

C EXPERIMENTAL SETUP

The evaluation uses an update-matched uncompressed control and task-specific benchmarks, then tests how codec, scoring, and training choices affect quality and compression. The reported gains are qualified by extraction, transfer, seed-variance, and comparability constraints.

C EXPERIMENTAL SETUP

  • The control is update-matched, not base-token- or trainable-parameter-matched: it sees about 262M base tokens versus about 375M for compressed recipes, which also train two hyper-encoders.All runs share a training and evaluation stack; compression is reported as C = Nbase/Ncompressed ≥ 1.Source: C EXPERIMENTAL SETUP · pp. 16–17, Table 5 · p. 18

C.1 BENCHMARKS AND EVALUATION DETAILS

  • Benchmarks include two-shot multiple-choice and generation tasks, RULER at 4K–32K contexts, and perplexity on WikiText plus fixed 1,000-document subsets of larger corpora.RULER uses inference-time LongRoPE adaptation without long-context finetuning; the larger-corpus subsets are fixed for reproducible comparisons.Source: §C.1 · p. 18, §C.3 · p. 19

C.2 ANSWER EXTRACTION FOR GSM8K AND MATH-500

  • Flexible extraction separates arithmetic correctness from template adherence, but GSM8K uses “####” when emitted and otherwise the generation’s last number.Strict matching can penalize correct answers that omit templates; continued generations can also fool a plain last-number heuristic, so instruction-following effects remain relevant.Source: §C.2 · pp. 18–19, Table 6 · p. 19

D.2 PROTECTED TOKENS

  • 25.4 points of GSM8K recovery over the unprotected baseline come from protecting digits during training; protecting operators and LATEX control tokens adds only 0.5 points.Digit protection localizes the compression cost to math-heavy generation; WikiText compression is 1.17× with zip2zip++ versus 1.21× for the unprotected recipe.Source: §D.2 · p. 20, Table 9 · p. 21

D.3 PER-COMPONENT GAINS AND SIGNIFICANCE

  • 32.2 points above unmodified zip2zip and 6.9 points below update-matched Uncompressed, zip2zip++’s GSM8K improvement and residual gap are both statistically significant.On Llama-3.2-1B and 3B, it beats zip2zip by 4.7 and 12.0 points, respectively, while remaining 9.3 and 11.6 points below Uncompressed.Source: §D.3 · p. 21

D.4 MULTI-VIEW SCORING

  • 29–36% of the canonical perplexity penalty is removed by exact marginalization over segmentations, compared with an apparent 74–97% under the first-token bound.The bound is not used as evidence because it overstates how much segmentation ambiguity accounts for the perplexity deficit.Source: §D.4 · p. 21

D.5 MERGE-SIZE TRANSFER

  • Under exact multi-view scoring, the size-3 encoder’s 3→4 transfer penalty is only 12% and 5% smaller than the strict penalty.Natural text rarely uses the larger merge-size cap: raising it from 3 to 4 changes compression by 0.018% on default evaluation and 0.22% on WikiText.Source: §D.5 · p. 22, Table 11 · p. 22, Figure 10 · p. 22

D.6 DATA SCALE; D.7 SEED VARIANCE AND COMPARABILITY

  • Raw-text pretraining improves language modeling but degrades instruction-tuned reasoning; longer SFT partly restores reasoning while sacrificing most of the perplexity advantage.The long-SFT comparison lacks a matched control. Separately, single-seed GSM8K differences below roughly two points should not be read as effects; compressed-versus-uncompressed comparisons also share a window-filter confound, and decoding speed was not benchmarked.Source: §D.6 · p. 22, Table 12 · p. 23, §D.7 · p. 23

D.8 NEGATIVE RESULTS

The negative-results section shows that improved training-side proxies can coexist with worse downstream performance, while Fault-Tolerant LZW handles imperfect compression and tree attention scores multiple segmentations efficiently. The tree-attention score remains conditioned on the canonical prefix, and the positional variants show no benefit at the reported 8k-step budget.

D.8 NEGATIVE RESULTS

  • On HumanEval and IFEval, zip2zip++ was statistically indistinguishable from zip2zip, leaving compression-associated losses of 25–26 code-generation points and 6–9 instruction-following points unrecovered.The reported paired McNemar p-values are 0.16 and 1 on Phi-3.5-mini, and 0.32 and 0.16 on Phi-3-medium.Source: §D.8 · p. 23
  • Online masking improved teacher-forced next-token accuracy 49.41→50.15%, hypertoken accuracy .420→.504, and generation compression 1.2536→1.3107×, yet worsened six of seven downstream tasks.Table 13 reports single runs; seed spread is discussed in Section D.7.Source: §D.8 · pp. 23–24, Table 13 · p. 24
  • At 8k steps, neither two-axis nor gated RoPE helped; the authors note both variants were still improving when the learning-rate budget ran out.This result does not establish that compressed coordinates are intrinsically harmful.Source: §D.8 · p. 24

E FAULT-TOLERANT LZW: DETAILS

  • Standard LZW can desynchronize when a neural compressor under-merges: unconditional insertion may duplicate an existing entry, whereas FT-LZW inserts only at a novel combination.Its guarded loop preserves the emitted base-token sequence on imperfectly compressed input; Figure 11 traces the skip, resume, and early-exit cases.Source: E FAULT-TOLERANT LZW: DETAILS · pp. 24–25, Figure 11 · p. 25
  • FT-LZW also emits designated disabled tokens verbatim and resets the buffer, resolves unknown codes under two stated cases, and caps codebook growth.The cap bounds codebook memory over a long context.Source: E FAULT-TOLERANT LZW: DETAILS · p. 25

F TREE ATTENTION FOR MULTI-VIEW SCORING

  • Tree attention isolates each segmentation branch to the canonical context and its own ancestors, packing views for one-pass scoring; Figure 12 depicts the attention mask.Canonical nodes cannot see branches, and sibling or cross-target branches remain isolated.Source: F TREE ATTENTION FOR MULTI-VIEW SCORING · p. 25, Figure 12 · p. 26
  • On WikiText, tree attention is 26.0× faster than independent-prefix scoring and costs 1.6× standard perplexity evaluation.All views are scored in one forward pass.Source: F TREE ATTENTION FOR MULTI-VIEW SCORING · p. 26
  • Tree-attention views condition on the canonical prefix only, so the resulting score is not the marginal over segmentations of the whole text.The remaining deficit is therefore a canonical-context measurement, not a bound on the compressed interface’s modeling cost.Source: F TREE ATTENTION FOR MULTI-VIEW SCORING · p. 26

Related papers

Loading 2610.13605v1…