acceptodds
Under review as a conference paper at ICLR 2027

Can LLMZip Encode Without an LLM?

Abstract

Predictive compression methods such as LLMZip combine large language models (LLMs) with arithmetic coding to achieve strong text compression, but require costly LLM inference at both the encoder and decoder. We introduce text compression schemes that eliminate LLM inference at the encoder while retaining compression rates close to those of LLMZip. Our approach interleaves text into a matrix and compresses each column using syndrome source coding with error-correcting codes. Using the Slepian–Wolf (SW) theorem for general correlated sources, we establish that the scheme asymptotically matches LLMZip’s compression rate as the block length grows. For finite lengths, we develop a construction using low-density parity-check (LDPC) codes over , with a decoder that combines belief propagation with sequential LLM predictions across parallel text streams. On text8, using the byte-level BLT-7B model, our scheme achieves 1.2 and 1.73 bits per character (bpc) at block lengths of 4096 and 256 respectively compared to the 0.972 bpc of LLMZip. We further improve finite-length performance by introducing a weak language model at the encoder. Its predictions enable adaptive rate selection and optimized assignment of tokens to variable nodes in the LDPC Tanner graph, and the assignment requires no signaling. The two methods are complementary and together offer reductions of 0.09 and 0.264 bpc at block lengths of 4096 and 256 respectively, with feedback to account for rare predicted errors in rate to be truly lossless. Using a LoRA fine-tuned BLT-7B model for images as a pixel model at the decoder, we show that the scheme can also compress images losslessly. These results demonstrate that strong LLM-based compression can be achieved with substantially reduced encoder computation.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Large language models, Lossless compression, Slepian–Wolf coding, syndrome coding, LDPC codes, byte-level language models, image compression

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_CH4ROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes compression schemes for autoregressively modeled sources, primarily text, in a setting where an LLM-based probability model is available at the decoder but the encoder must use either no language model, or a weaker model. The encoding scheme uses syndrome source coding based around LDPC codes. The paper then considers encoder-side adaptations with adaptive rate and adaptive placement. Its main contribution is to show that having a LLM predictor at only the decoder is enough to recover much of the gain which LLM-based entropy coding achieves over classical codecs, and that the considered adaptations can overcome part of the remaining gap to symmetric arithmetic coding with LLM-informed probabilities (LLMZip). Theoretical validation is provided by way of a characterization of achievable rates for an idealized version of the algorithm using MAP decoding. Empirical results are reported for text compression on text8, public-domain books and CPython source code. An extension to Kodak images is given which shows that the idea can be applied to a modality other than text.

Critical strengths
  1. Reducing the high computational cost of methods like LLMZip is of practical interest, as requirement for an LLM to predict each character at both the encoder and decoder poses a barrier to their deployment. The current paper partially address this concern at the encoder side, while retaining much of the advantage in coding rate over classical codecs.
  2. The use of a weaker language model to inform rate and placement adaptation at the encoder is an interesting extension of the asymmetric-compute idea and provides an appreciable further reduction in the coding rate.
Critical weaknesses
  1. The proposed method only addresses the excessive computational requirements of LLMZip on the encoder side. The decoder still needs to run the expensive LLM, and the practical use for this asymmetric-compute setting is not particularly well-motivated in the paper. Some discussion of relevant real-world applications would be useful.
  2. The adaptive methods restore the requirement for a suitable predictor at the encoder. As shown in Table 2, the amount of computation at the encoder in this case is only 5 times less than the full LLMZip-arithmetic encoding, and orders of magnitude larger than the classical approaches, which makes the computational story less clear. I would be interested to know if an even cheaper predictor can still recover the gains seen in Table 2 from row (ii) to row (v) with less compute. Table 5 in the appendix presents several alternative predictors, but their computational cost isn't examined.
Questions for authors
  1. The method is claimed to be lossless, however syndrome source coding incurs a (vanishing) error probability (Theorem 6). The authors propose a feedback scheme to address this in Appendix F, while the headline results in Tables 1 and 2 instead report an "empirical lossless rate". It is however mentioned that the encoder cannot know RLLR_{\mathrm{LL}} a priori as it is computed across the whole corpus. How would a more realistic scenario, potentially requiring feedback, impact the achieved rate for the scheme (SW) without a language model at the encoder? How would the target/syndrome rate be chosen in this case? Moreover, Tables 3 and 5 allows a small error probability, while the baselines including LLMZip and the classical codecs always decode without error. Additional clarity about when feedback is used and which results reflect true lossless coding rates (i.e. enforcing Pe=0P_e = 0 via feedback) would be appreciated.
  2. The appeal to the Slepian-Wolf theorem appears somewhat loose, as Slepian-Wolf concerns the encoding of correlated sources, or more often, when encoding with side information at the decoder -- namely, given X2X_2 is available at the decoder, we can send X1X_1 at the rate of the conditional entropy H(X1∣X2)H(X_1 \mid X_2). While an LLM at the decoder provides a better predictive model there, I am unsure whether it should be referred to as a side information, as it is not a random source but instead an alternative, stronger probability model. In other words, it does not quite make sense to me to "condition" X1X_1 on X2X_2 in the preceding equation if X2X_2 is a (deterministic) pre-trained LLM instead of a correlated random variable, unless further explanation is given. Would the authors be able to clarify this, or else motivate their scheme through a framework other than Slepian-Wolf coding?
  3. One drawback of LLMZip is the requirement for bitwise-exact matching of the probabilities at the encoder and the decoder to achieve lossless transmission under arithmetic coding, which may be difficult to guarantee if different floating-point hardware, model quantizations, or other discrepancies occur between the encoder and decoder. It appears that the methods in the paper may improve on this limitation, especially the no-model version. Could the authors briefly discuss any potential implications, and considerations for deploying the method when the encoder and decoder might be operating on different machines using finite-precision arithmetic?
  4. The number of rows in the parity-check matrix (mi,nm_{i,n}) is not mentioned before it is introduced on line 144.
4 comments
AuthorsOpenReview ↗

Response (1/2)

We thank the reviewer for the positive assessment and the questions.

Q1: losslessness and rate choice.

  • We implemented the feedback protocol of Appendix F, including the rate-compatible codes, and now apply it to the model-free scheme (Common Response, Section 1):

    • the encoder starts at a public, fixed start rate, tuned once on a disjoint dev split;
    • it sends the syndrome plus kk GF(263) check symbols;
    • on each NACK it sends a few extra syndrome symbols (rate-compatible codes);
    • the raw fallback guarantees termination.
  • The output is wrong only if a wrong decode passes the checks, with probability at most 262−k262^{-k}, and kk can be raised at a known cost (Common Response, Section 1). With k=2k=2, 0 wrong decodes were accepted over about 608k codewords.

  • Impact on rate. The start rate is tuned on dev for a first-attempt frame error rate (FER) ≤10−3\le 10^{-3}, the same FER as Table 3, and then measured on the held-out test block. Here 99.8–99.9% of codewords decode at the first attempt. The realistic rate counts all check bits and feedback:

    nnPaper RLLR_{\mathrm{LL}}Realistic, FER ≤10−3\le 10^{-3} on dev (bytes 128+)Realistic, all bytes (incl. cold starts)
    2561.731.6341.638
    5121.501.4861.494
    20481.241.3241.349
    40961.201.2361.292
    • On the same bytes as the paper's empirical lossless rate RLLR_{\mathrm{LL}} (128 onward), the realistic rate is below RLLR_{\mathrm{LL}} at n≤512n \le 512. It is 0.04–0.08 bpc above it at n≥2048n \ge 2048.
    • That difference is the price of a realistic rate. RLLR_{\mathrm{LL}} is chosen after decoding the evaluation codewords themselves. The realistic rate is one public rate, tuned on held-out data, with checks and feedback counted.
    • Allowing more feedback lowers the realistic rate (Common Response, Section 3).
  • Which results are lossless. We will state explicitly that the protocol results above are lossless up to the check miss probability (at most 262−k262^{-k} per undetected error from the LDPC decoder), enforced by feedback and the checks. Tables 3 and 5, which allow FER 10−310^{-3} without feedback, will be labelled as feed-forward operating points that are not lossless.

Q2: Slepian–Wolf framing. The reviewer is right that the LLM is not side information, and our wording in Secs. 1 and 6 ("a language model as decoder-only side information", "side-information model") is loose. As Sec. 2 defines, the side information is the previously decoded bytes Yp=X<pY_p = X_{<p}, a random variable correlated with the column XpX_p through the source. The decoder has YpY_p and the encoder does not use it, which is Slepian–Wolf coding with side information at the decoder only. The LLM is a fixed function of YpY_p that gives the decoder's model Q(Xp∣Yp)Q(X_p \mid Y_p), a (mismatched) decoding metric, and Theorem 1 gives the achievable rate as the column log loss under QQ. We will fix the wording in Secs. 1 and 6 and state this distinction explicitly in Sec. 2.

Q3: finite-precision robustness. Yes, unlike arithmetic coding, our scheme does not need bit-exact probabilities at both ends. The model-free encoder computes none, and order-6 placement is recomputed from the same counts at both ends; any mismatch only causes a failed decode, which the checks catch. Decoder-side numerical errors only affect BP, and the checks catch any wrong decode. In our closed-loop runs, online PMFs differed from precomputed ones by up to 0.12, yet decoding was byte-exact at the same rate.

Q4: notation. We will define mm before line 144.

AuthorsOpenReview ↗

Response (2/2)

W1: use case. The scheme fits settings where encoding happens on constrained devices and decoding in a datacenter. In these settings the encoder is the bottleneck: it runs on battery-powered or shared hardware, or must keep up with a high data rate, and it cannot host a large language model (7B). Our encoder computes one sparse GF(263) syndrome and two check symbols per codeword, with no model, no probabilities and no arithmetic coder. Decoding happens later, on accelerators that are already provisioned, and its cost is amortised (archives that are written often and read rarely) or offline (logs and telemetry analysed in batch). Examples are uploads and telemetry from edge devices using low-bandwidth uplinks, satellites that communicate with ground stations, write-many / read-rarely archives and log storage. The feedback channel in these settings is the ordinary ACK path/control channel in a wireless network.

W2: encoder compute of the adaptive variants. Yes. An order-6 counts model in place of the ctx16 BLT-7B keeps most of the gains at about 10310^3 operations per byte, the same order as xz and zstd and about 10810^8 times less than ctx16 (101110^{11}, Table 2). It drives placement directly and the rate predictor through a 6k-parameter MLP that runs once per codeword. Held-out test at FER ≤10−3\le 10^{-3} on dev, all bits counted (bpc):

nn25651220484096
SW (model-free encoder)1.6381.4941.3491.292
+ rate (order-6)1.6201.4411.3261.276
+ placement (order-6)1.5551.4001.3421.254
+ both (order-6)1.5331.3561.3341.255
  • Rate and placement with order-6 together save 0.105 and 0.138 bpc at n=256n=256 and 512512, and 0.015–0.037 at n≥2048n \ge 2048. That is 41–79% of the saving with ctx16 (Common Response, Section 3).
  • Higher orders do not help, because the held-out log loss of the order-kk model is lowest at k=6k=6.
  • The predictors of Table 5 all read the same ctx16 features, so each costs the same 101110^{11} operations per byte as ctx16, and the predictor head adds little to that.

Thank you for your detailed rebuttal and the new experiments. The new results clear up the nature of the claims around losslessness and the intended nature of the SW framing, although the error probability is still positive (although vanishingly small, so I agree that practically it can be considered as such). I also appreciate the new experiment with the 6th order Markov model as it shows a cheaper encoder-side model can retain some of the gains. I have therefore decided to retain my positive assessment of the paper.

AuthorsOpenReview ↗

Acknowledgement

Thank you for reading our response and the new experiments, and for keeping your positive assessment. We appreciate your time and your constructive feedback, which has improved the paper.

Reviewer_3pbeOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks whether LLM-based lossless compression (an LM plus arithmetic coding, "LLMZip") can be made light at the encoder by moving the language model entirely to the decoder. The byte sequence is cut into nn parallel streams arranged as rows of an array. After M=128M=128 initial-context bytes per stream, which are sent with a conventional compressor, each column of nn symbols is compressed to its syndrome under a parity-check matrix over GF(263). The decoder recovers columns in order: a byte-level LM (BLT-7B) predicts each stream's next byte from the already-decoded context, and nonbinary sum-product BP decodes each column. Theorem 1 gives a random-binning bound in terms of the decoder model's column log loss, with no stationarity assumption and allowing a mismatched model. Appendix B argues that the rate approaches LLMZip's as block length and stream length grow. On a 9M-byte subset of text8, the empirical lossless rate drops from 1.73 bpc (n=256n=256) to 1.20 bpc (n=4096n=4096), against 0.972 bpc for LLMZip. The paper then gives the encoder a "weak" predictor (BLT-7B with a 16-byte context) and uses it in two ways: (i) an interval-censored MLP predicts a rate for each codeword; (ii) high-entropy streams are assigned to well-separated Tanner-graph variable nodes, which needs no signaling. With one round of feedback, the two together lower the lossless rate by 0.083–0.264 bpc. The pipeline is repeated on Gutenberg, CPython source and Kodak images (using a LoRA-adapted BLT-7B). Appendices study the failure mechanism, five predictor families and placement controls.

Critical strengths

S1. A working LLM-grade compressor with no model at the encoder, plus a careful finite-length study. The encoder (Sec. 3) only computes a syndrome: about two GF(263) multiply-accumulates per symbol with dv=2d_v=2. Even so, every corpus codeword of the text8 slice decodes at 1.20 bpc per coded byte at n=4096n=4096 (Table 2), far below xz and gzip, with a 7B byte-level model used only at the decoder. The measurement is done with care. Corpus codewords certify losslessness, and resampled codewords give FER estimates. Fig. 2 shows waterfalls at five block lengths, and App. C shows the column log-loss variance scaling as 1/n1/n (nVar^≈2.8n\widehat{\mathrm{Var}}\approx 2.8–3.03.0). The supplement includes per-codeword outcome matrices. From them I could recompute the fixed-rate entries of Table 2 and the arithmetic of Tables 3–5. To my knowledge, this is the first concrete demonstration that the decoder-side-information paradigm carries over to LLM-based compression, and it is useful for the community to see.

S2. Signaling-free adaptive placement, grounded in an analysis of how decoding fails. Section 4 shows that failures come from confidently mispredicted symbols landing on trapping sets, not from high mean log loss. For example, at n=4096n=4096 and R=1.35R=1.35 the two failing codewords had mean log loss 1.015 and 1.009, while 110 codewords that decoded had higher mean log loss. Sec. 5.2 and Eq. (12) turn this into a deterministic stream-to-variable-node map that both ends can compute. The controls in App. H are convincing:

  • At fixed rate, FER drops 34–48×, with paired McNemar counts of 869 repaired vs. 0 broken at n=4096n=4096, R=1.12R=1.12.
  • A fresh HH still gives a ninefold reduction.
  • A random permutation has no effect.
  • The intuitive "hardest symbols onto safest nodes" rule raises FER 10.9×.

Placement lowers the zero-failure lossless rate by 0.04–0.13 bpc at every block length (Table 2). That comparison is like-for-like.

Critical weaknesses

W1. The headline comparison with LLMZip and classical compressors is not like-for-like.

  • Initial contexts are excluded from the SW rate but included in the baselines. App. D and the decode driver in the supplement (misc/ratesweep_error_target.py, which cuts W=500W=500 windows from 1000-byte rows and codes columns 128–499 and 628–999) show what happens to bytes 500–627 of each row. They are the second stream's initial context, "transmitted with a conventional lossless compressor", and are not counted in any SW rate (Sec. 2: "we focus only on the rate over the coded tokens"). That is 128 of every 872 new bytes, or 14.7% of the source. The LLMZip reference (misc/llmzip_ac_baseline.py, offset 128 on the same rows) and the gzip baseline (misc/gzip_baseline.py) code all 872 bytes. Charging the excluded bytes only at xz's 2.135 bpc gives (744⋅1.20+128⋅2.135)/872≈1.34(744\cdot1.20+128\cdot2.135)/872\approx1.34 bpc at n=4096n=4096, and about 1.26 bpc for "both" (1.110).
  • The LLMZip reference is inflated. In results/ac_baseline/text8/, the arithmetic coder achieves 0.9717 bpc, while the model's log loss on the same 8.93M tokens is 0.9338. The 0.038 bpc (4%) gap comes from flushing about 30 bits of coder state at the end of every 872-byte row (llmzip/ac.py, flush). Standard termination, or one stream for the whole corpus, would make it negligible.
  • Error-detection bits are not charged. The per-column error-detection tags that Sec. 5.2 and App. F require are not counted.

Taken together, the abstract's "1.2 … compared to the 0.972 bpc of LLMZip" and the Table 1 comparison understate the gap. On identical coded bytes, the model-free scheme is about 28% above the 0.934 bpc an LLMZip coder can reach. End-to-end at the paper's operating point it is about 43% above, and Table 1's apparent advantage over paq8h largely disappears.

This overhead also grows with the block length. For a corpus of NcN_c bytes, the uncoded fraction is at least nM/NcnM/N_c: about 6% at n=4096n=4096 and about 23% at n=16384n=16384 for this 9 MB corpus. So part of the improvement with nn in Table 2 is paid for by bytes that are not counted.

This bears directly on the central claim that rates stay "close to those of LLMZip". It can be fixed: report end-to-end rates (all bits, all bytes) for each nn. Either code the initial columns with the SW scheme itself under a growing context, or charge a real compressor for them. Re-run LLMZip with standard termination, and state the minimum input size n(M+L)n(M+L).

W2. The gains from the encoder-side "weak predictor" are overstated, in compute and in rate.

(a) Compute. The encoder's predictor is BLT-7B itself with a 16-byte window (Sec. 5). Table 1 reports 101110^{11} vs. 5×10115\times10^{11} ops/char for this predictor vs. full LLMZip. That 5× ratio exists only because both are costed as exact-window recomputation with no KV-cache reuse. For a 7B transformer with a cached context, the per-byte cost is dominated by roughly 2×2\times(parameters) FLOPs, whatever the window length. So configurations (iii)–(v) do not show a light encoder. The statement that "a small or quantized model … could supply comparable inputs at a fraction of the compute" (Sec. 5) is not tested.

(b) Rate. Table 2 does not charge all columns the same way:

  • "Std SW" and "adaptive placement" are zero-failure oracle rates that must cover the single hardest corpus codeword.
  • "Adaptive rate" and "both" are charged max⁡(r^(x),Rˉ(x))\max(\hat r(x),\bar R(x)), with one round of feedback that tops each miss up to exactly Rˉ(x)\bar R(x) (App. F).

The natural baseline is a single fixed rate given the same feedback. I computed this baseline from the supplementary per-codeword files (rstar_intervals_*_aligned.npz):

  • I chose one rate R0R_0 so that no more codewords need a resend than under the learned scheme, using the miss fractions in results/ood/reprice/*.json.
  • I charged each codeword max⁡(R0,Rˉ(x))\max(R_0,\bar R(x)), as App. F does.
  • Choosing R0R_0 in-sample favors the fixed rate slightly. A leave-one-set-out choice at FER ≤10−3\le10^{-3} gave the same rates to within one grid step.

The resulting "adaptive rate on top of placement" gains are:

Source, block lengthMy estimateReported
text8, n=256n=2561.500 → 1.466, ≈0.03 bpc0.13
Gutenberg, n=4096n=40961.160 vs. 1.155, ≈0.0050.07
Kodak, n=4096n=4096≈0 (2.980 vs. 2.983)0.06
Kodak, n=256n=256≈1.071.92
Python, n=256n=256fixed rate with placement and the same feedback (1.25) is better than "both" (1.350)0.10

At n=4096n=4096 on text8, the overall reduction of "both" relative to Std SW with the same feedback is about 0.05 bpc, not the 0.09 in the abstract. The authors' own remark in App. J about Python n=256n=256 (the saving "arises because a few hard codewords set the fixed rate") applies more widely. The link drawn in Sec. 6.3 between the adaptive-rate gain and Δmax⁡\Delta_{\max} is exactly what this accounting asymmetry predicts. Table 3, where every method meets FER ≤10−3\le10^{-3} without feedback, is the fair comparison, and there the adaptive-rate gains are modest: 0.026–0.085 bpc, or 17–29% of the genie gain.

This affects the abstract's "0.09 and 0.264 bpc" reductions, the "2 to 5% … 7 to 9% … 32%" claims (Secs. 1 and 6), and the third and fourth contributions. Under Table 2's accounting the resend fraction of the learned scheme is 0.5–1.5% at n=4096n=4096, which also sits uneasily with "rare predicted errors". It can be fixed by:

  • adding a validation-calibrated fixed-rate-plus-feedback baseline to Table 2;
  • reporting resend fractions;
  • evaluating placement and rate prediction with a genuinely cheap encoder model.
Questions for authors
  1. (W1) Please report end-to-end rates per block length. These should include the 128-byte initial contexts, either SW-coded with a growing context or charged to a named compressor, plus the error-detection bits. Please also re-run the LLMZip reference with standard arithmetic-coder termination (or a single stream). If the end-to-end rate at n=4096n=4096 stays within about 0.05 bpc of the per-coded-symbol rate, and the comparison is made on identical bytes, I would consider W1 resolved.

  2. (W2b) Please confirm or correct my matched-feedback computation. The baseline is a fixed rate calibrated on validation sets, with the same resend fraction as the learned scheme and the same max⁡(R0,Rˉ(x))\max(R_0,\bar R(x)) accounting. Please add it to Table 2. If the learned predictor keeps a gain of about 0.05 bpc or more at n≤512n\le512 on the text corpora against this baseline, and the abstract and Sec. 6 claims are rescoped to match, I would consider W2(b) resolved.

  3. (W2a) What is the encoder cost of configurations (iii)–(v) compared with a KV-cached LLMZip encoder? Placement only needs an entropy ranking, so could it be driven by a much cheaper model, such as an order-kk context model or a small byte-level LM? If placement keeps most of its Table 2 gain with an encoder model costing at most about 10810^{8} FLOPs/byte, I would regard (iv) as a genuine encoder-light improvement.

  4. Every fixed-rate entry in Table 2 uses a single code construction seed, and RLLR_{\rm LL} is a maximum over 372–29,760 codewords. Sec. 4 notes that the same codeword can pass under one draw of HH and fail under another. In the supplementary aligned files, one text8 codeword at n=2048n=2048 decodes at 1.24 but fails at 1.28, and one at n=512n=512 decodes at 1.22–1.48 but fails at 1.52. Please report RLLR_{\rm LL} for at least two more code seeds at n=256n=256 and n=4096n=4096, and clarify whether losslessness at RLLR_{\rm LL} holds "at and above" that rate as defined in Sec. 4.

  5. [Suggestion] Please position the work relative to prior use of syndrome coding to compress a single source:

    • Ancheta (1976), syndrome source coding;
    • Caire, Shamai & Verdú (2004), LDPC syndrome compression of sources with memory, decoded by BP with closed-loop doping;
    • distributed video coding (Puri & Ramchandran, 2002, PRISM; Girod et al., 2005), which established the light-encoder, heavy-decoder paradigm with decoder-side prediction and feedback-based rate control.

    It would also help to state what Theorem 1 adds beyond the standard random-binning/information-spectrum argument for a mismatched decoder.

4 comments
AuthorsOpenReview ↗

Response (1/3)

W1: like-for-like comparison. We implemented all four fixes the reviewer listed.

  1. End-to-end rates (including initial contexts) for each nn.
    • The new results use an updated layout with one contiguous 8.39 MB block of text8, cut into nn rows of N/nN/n contiguous bytes.
    • Each row's first 128 bytes are SW-coded with a growing context, with their own rate-compatible family, while the first 2–3 columns of each row are sent raw.
  2. Error-detection bits. k=2k=2 GF(263) check symbols per codeword, all incremental syndromes, and raw fallbacks are counted in the rate.
  3. LLMZip re-run with standard termination. One arithmetic coder over the block (one stream) gives 0.932 bpc, equal to the model log loss of 0.9323 on these bytes.
  4. Identical bytes. All compressors are run on the same 8,388,608 bytes.

Headline operating point: FER ≤10−3\le 10^{-3} on dev (Common Response, Section 3), model-free encoder, held-out test. 99.8–99.9% of codewords decode at the first attempt.

nnRow lengthBytes 128+ (bpc)End to end (bpc)DifferenceGap to LLMZip
25632 KB1.6341.638+0.004+76%
51216 KB1.4861.494+0.008+60%
20484 KB1.3241.349+0.025+45%
40962 KB1.2361.292+0.056+39%

n≥2048n \ge 2048 use row-extension codes; n≤512n \le 512 use merge/split.

  • The reviewer's 0.05 criterion for initial contexts. The end-to-end rate stays within 0.05 bpc of the rate on bytes 128 onward at n≤2048n \le 2048 (at most 0.025). At n=4096n=4096 it is 0.056, because the 8.4 MB test block gives rows of only 2 KB. At the FER ≤6×10−2\le 6 \times 10^{-2} operating point, it is 0.050 at n=4096n=4096.
  • Gap to LLMZip on identical bytes: The headline SW gap is now 39% at n=4096n=4096 (1.292 vs 0.932) near one-shot. The same protocol trades latency for rate and gives 1.199 bpc (+29%) at about 1.09 rounds, 1.133 (+22%) at about 2.3 rounds, and 1.126 (+21%) at the lowest dev bpc, at the code floor of 1.124 (+21%; Common Response, Section 3). With no model at the encoder, the gap to LLMZip on identical bytes thus falls from 39% to 21% as latency is relaxed (the gap of the code floor itself). The original paper's accounting gave 24%, and the reviewer estimated 43% after correction. We will replace the abstract's comparison with these explicit gaps and trade-offs.

W2(a): encoder compute.

  • The headline SW scheme runs no encoder model. The start rates are public and feedback does the adaptation.

  • An order-6 counts model replaces BLT-7B (ctx16) at the encoder for both placement and rate, as the reviewer suggests. It is a Markov model (Witten–Bell) over orders 0–6 (a table lookup on the previous 6 bytes, no neural network). The decoder recomputes the same placement ranking from verified bytes, so placement needs no signalling. The rate MLP uses the same statistics per codeword, and its start level is signalled and counted (W2(b)).

  • Results at FER ≤10−3\le 10^{-3} on dev (held-out test, all bits counted, 0 wrong accepted):

    nnModel-free encoder+ rate (order-6)+ placement (order-6)Both (order-6)
    2561.6381.6201.5551.533
    5121.4941.4411.4001.356
    20481.3491.3261.3421.334
    40961.2921.2761.2541.255

    Placement keeps most of its gain with this model (0.083 and 0.094 bpc at n=256n=256 and 512512, 0.038 at n=4096n=4096). In the genie floor, the order-6 ranking recovers 54–76% of the gain of ranking by the decoder's own BLT-7B entropies.

  • Why order 6. Held-out log loss is lowest at k=6k=6 (1.73 bpc, against 1.75 at k=8k=8 and 1.87 at k=10k=10), and neither the placement ranking nor the rate predictor improves beyond it.

  • Against ctx16. ctx16 predicts the per-codeword rate better (Spearman 0.56–0.67, against 0.46–0.59 for order-6), which shows in its larger rate gains, both on SW and on top of placement (W2(b); Common Response, Section 3).

AuthorsOpenReview ↗

Response (2/3)

W2(b): matched fixed-rate + feedback baseline.

  • Our current SW protocol is "fixed start rate + feedback". The start rate is a public constant chosen on a disjoint dev split as the lowest dev bpc with FER ≤10−3\le 10^{-3}. Two adjacent levels are time-shared in a public pattern so the budget is met exactly. Every learned column is tuned to the same budget, so all columns are compared at matched first-attempt FER with the same feedback and accounting.

  • The learned rate predictor. The rate MLP gives a logistic estimate (μ,σ)(\mu, \sigma) of each codeword's critical rate. The start rate is its α\alpha-quantile μ+σ logit α\mu + \sigma\,\mathrm{logit}\,\alpha, with logit α=ln⁡α1−α\mathrm{logit}\,\alpha = \ln\frac{\alpha}{1-\alpha}, shifted by δ\delta and floored at FF, i.e. max⁡(F, μ+σ logit α+δ)\max\big(F,\ \mu + \sigma\,\mathrm{logit}\,\alpha + \delta\big), rounded up to the start ladder. The public constants FF, α\alpha, δ\delta are chosen on dev from per-level decode tables that give the exact dev outcome of any rule. The floor FF stops codewords that look easy from starting too low. Without it, the predictor lost to the baseline at n=256n=256 (1.649 against 1.638 bpc). The start level is sent with a Huffman code fitted on dev (2–3.7 bits per codeword against log⁡2G=4.7\log_2 G = 4.7) and counted.

  • Gains of the rate predictor against the matched baseline (bpc, held-out test):

    nn25651220484096
    ctx16 (paper's predictor): rate vs. matched fixed rate0.0330.0630.0410.036
    ctx16: rate + placement vs. placement alone0.0360.0690.0440.016
    order-6 (cheap): rate vs. matched fixed rate0.0190.0530.0230.016
    order-6: rate + placement vs. placement alone0.0230.0440.008-0.001

    With the paper's ctx16 predictor, adaptive rate meets the reviewer's 0.05 bpc bar at n=512n=512 (0.063 alone and 0.069 on top of placement) and gains 0.016–0.044 bpc at the other block lengths. With the much cheaper order-6 model it still gains at every nn (0.016–0.053 bpc alone) and meets the bar at n=512n=512. Since all columns use the same feedback, these gains come from adaptivity.

  • Resend fractions (% of codewords with more than one attempt):

    nnBaseline+ rate (order-6)+ placement (order-6)Both (order-6)
    2560.170.110.090.10
    5120.130.140.160.16
    20480.150.170.120.12
    40960.240.390.340.34

    Resends are rare at this point (0.09–0.39%), so "rare predicted errors" is accurate.

  • Table 2 accounting. For completeness, on Table 2's original accounting and its other corpora, a fixed rate given the same top-up and no more resends confirms the same matched gains computed by the reviewer, i.e., the rate prediction on top of placement gains 0.07 bpc on text8 at n=256n=256 (0.13 reported), 0.15 on Gutenberg and 1.05 on Kodak at n=256n=256, about zero at n=4096n=4096 on Gutenberg, Kodak and Python, and a loss on Python at n=256n=256.

  • Rescoping.

    • The text8 end-to-end table at FER ≤10−3\le 10^{-3} (W1) will become the primary headline, and its numbers will replace those in the abstract.
    • For completeness, Table 2 will be retained and will report the matched fixed-rate + feedback baseline, and all the gains will be stated against it.
    • The model-free SW encoder with feedback will become the main contribution. Rate prediction and placement will be presented as gains on top of it from an encoder model (order-6 or ctx16), largest at short block lengths.
    • The "0.09 and 0.264 bpc" reductions and the percentage claims in Secs. 1 and 6 will be removed.
AuthorsOpenReview ↗

Response (3/3)

Code seeds. We reran the end-to-end protocol with two more code seeds (three in total) at the balanced operating point (about 2.3 mean rounds), with everything else fixed:

nnseed 11 (reported)seed 12seed 13
5121.19211.19231.1930
40961.13271.13301.1333

The rate varies by at most 0.001 bpc, with 0 wrong accepted in every run. Losslessness does not depend on the seed, because a codeword that fails at one rate is repaired by the next increment.

Related work. We will position the work against:

  • Ancheta (1976), syndrome source coding; Ancheta (1976) introduces the idea of a universal syndrome source coding scheme. It gives a theoretical construction and practical constructions for simple sources. However, there is no natural way to design practical codes and decoders that will provide good compression for complicated sources such as language.
  • Caire, Shamai & Verdú (2004), LDPC syndrome compression with BP and closed-loop doping; This paper uses LDPC codes and belief propagation decoding to implement a syndrome source coding scheme. For compressing sources with memory, it uses the Burrows Wheeler transform (BWT). The authors claim that the performance of BWT is similar to that of gzip, which we have shown is very far away from our results. In particular, the decoder does not use a language model. This is a significant difference from our proposed approach.
  • Distributed video coding (PRISM; Girod et al. 2005), including its feedback-channel rate control, which is close to our incremental protocol. PRISM by Puri et al. and the "Distributed Video Coding" tutorial by Girod et al. consider video coding in a setup where the encoder complexity is very small and the decoder complexity is high, similar to the current setup. Indeed, they propose the use of Slepian–Wolf or Wyner–Ziv encoding, which also is similar to our setup. The key difference between their paper and ours is that in their papers, the inter-frame correlation across consecutive images provides the side information that is exploited at the decoder. In our setting, the decoder has no such naturally available, already decoded side information. Our interleaved scheme is novel and it is required to decode bytes in an order that makes it feasible to be exploited as side information.

What Theorem 1 adds. Theorem 1 ties the achievable rate of each column to the log loss of the decoder's model on that column. It requires no stationarity or ergodicity assumption, allows the model to be mismatched, and uses a linear encoder that needs only a scalar rate. This log loss is the quantity we measure and tune the start rates against. The theorem does follow from the standard random-binning argument of the information-spectrum approach (Miyake & Kanaya, 1995), as Sec. 3 states and we do not claim it as a novel proof. However, there is a small difference in the proof. The decoder of Miyake & Kanaya outputs the source sequence if it is the only source sequence that is typical with the side information. Instead, in our proof, the decoder outputs the sequence with the highest probability that also satisfies the syndrome checks, i.e., the maximum likelihood sequence. We separately consider the event that the source is not typical and the case when the source is typical but it is not the maximum likelihood codeword. The difference is indeed minor.

AuthorsOpenReview ↗

Discussion Reminder

Thank you again for your careful review. As the discussion period is closing soon, we wanted to check whether our response addresses your concerns. In brief:

  • Like-for-like comparison (W1). We implemented all four fixes you listed: end-to-end rates including the initial contexts, counted error-detection bits, LLMZip re-run as one stream with standard termination (0.932 bpc), and identical bytes for every compressor.
  • Latency–rate trade-off (Common Response, Section 3). The same protocol, with no model at the encoder, trades feedback rounds for rate: at n=4096n = 4096 the gap to LLMZip falls from 39% near one-shot to 29% at about 1.09 rounds and 21% at the lowest rate, which is the gap of the code floor itself. An encoder model substitutes for rounds: at about 1.05 rounds it closes 30–48% of the gap to the operating point that needs about 2.3 rounds.
  • Cheap encoder model and fair baseline (W2). An order-6 model (∼103\sim 10^3 ops/byte) keeps 41–79% of the ctx16 gains, and all gains are now stated against a matched fixed-rate plus feedback baseline.
  • Rescoping and related work. The main contribution is the model-free SW encoder with feedback and its latency–rate trade-off; rate prediction and placement are gains on top of it from an encoder model. Our response also positions the work against Ancheta (1976), Caire, Shamai and Verdú (2004), and PRISM / Girod et al. (2005).

If any point remains unclear, we would be glad to clarify it before the discussion closes. If the response resolves your concerns, we would appreciate it if you would consider updating your score.

Reviewer_dusCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether LLM-based lossless compression can avoid expensive language model inference at the encoder. The authors propose a Slepian–Wolf coding approach that divides a source sequence into interleaved streams and uses LDPC syndrome coding at the encoder. At the decoder, an LLM provides token probability estimates, which are combined with belief propagation to reconstruct the original data. The paper further introduces adaptive rate allocation and adaptive placement to improve finite-block-length performance. Experiments on text corpora and image data demonstrate the feasibility of the approach.

Critical strengths
  1. The paper addresses an interesting and practically relevant problem. Moving expensive language model inference from the encoder to the decoder offers a different perspective on the computational asymmetry of learned lossless compression. Although syndrome-based compression and LDPC decoding are established techniques, their application to single-source LLM-based compression is a meaningful direction.
  2. The paper provides both theoretical analysis and empirical evidence. The achievable-rate analysis supports the proposed coding principle, while the experiments across different block lengths demonstrate the trade-off between compression rate and decoding reliability. The adaptive rate and placement strategies are also evaluated through component comparisons, and the additional experiments on adaptive placement provide useful evidence of its effectiveness.
Critical weaknesses
  1. The evaluation does not sufficiently establish the performance of a complete lossless compression system. The proposed decoder can produce an incorrect reconstruction even when the recovered codeword satisfies the syndrome constraints. Although the paper discusses error detection and feedback-based repair, the practical verification mechanism is not sufficiently specified. In particular, the implementation and bitrate overhead of the per-column error-detection tags remain unclear. Furthermore, Table 2 assumes rate-compatible syndrome transmission for the adaptive schemes, whereas Appendix F acknowledges that the implemented LDPC matrices are constructed independently at different rates. The authors provide an estimate of the additional retransmission cost, but this does not fully establish the performance of an implemented end-to-end repair protocol. More importantly, the reported compression rates mainly cover the syndrome-coded tokens rather than the complete source. Initial contexts and other protocol overhead are not consistently included. This makes it difficult to assess the actual file-level compression performance and the fairness of the comparison with conventional lossless compressors. An end-to-end evaluation reporting the total transmitted bits, including initialization and reliability overhead, would substantially strengthen the paper.

  2. The initialization dependencies introduced by overlapping streams are not sufficiently explained. Appendix D states that the initial context of a stream can be reused from the tail of the preceding chunk. However, Section 3 describes a decoder that processes all streams within a set column by column. If the reused context depends on coded symbols in another stream of the same set, those symbols may not yet be available when decoding begins. The paper should clarify how these dependencies are resolved in the actual decoding schedule and whether additional initialization information must be transmitted. This is particularly important for establishing that the reported closed-loop decoding procedure can reconstruct the complete source without relying on unavailable original context.

  3. The error-resilience story is unclear to me. Decoding is sequential and each column's context comes from previously recovered symbols, so one bad column should propagate and corrupt everything after it. The only fallback I see is detection plus a feedback/retransmission round from the encoder. Wouldn't that require frequent interactive rounds, and doesn't that undermine latency for any real-time setting? More broadly, I found the overall system description hard to follow, and Fig. 1 carries very little information. Following from above: if columns can fail and need repair, in what sense is it still "lossless"? The error-free operating points feel conditional rather than a real guarantee.

  4. The experimental comparison is too narrow. LLMZip is treated as the reference point, although several more recent lossless text compressors already improve on it. The method should be positioned against the current set of strong compressors.

  5. Dataset and decoder-model details are under-specified. Lots of effort goes into derivations but too little into high-level info, which indeed hurts readability.

  6. My another concern is the use case. In practice you encode once on a server and decode many times on end devices; decoding is the bottleneck and those devices are compute-constrained, so we normally cut decoding cost. This paper does the opposite: it removes encoder compute but places a 7B LLM at the decoder. I struggle to see a realistic setting where this trade-off makes sense, and the paper doesn't offer one.

Questions for authors
  1. How does the decoder verify the correctness of each recovered codeword before updating the LLM contexts? What error-detection mechanism is used, and how are its bitrate overhead and possible undetected errors accounted for?

  2. How are overlapping stream contexts initialized when the preceding chunk has not yet been fully decoded? Does the reported closed-loop implementation follow exactly the same initialization and scheduling procedure as a deployable decoder?

  3. Could the authors report the actual end-to-end compression rate, including initial contexts, rate signaling, error-detection information, and retransmissions? A measured encoding/decoding time comparison would also help clarify the practical computational advantage.

  4. Could the authors give more comprehensive experimental comparison to include more recent works?

3 comments
AuthorsOpenReview ↗

Response (1/2)

We thank the reviewer for the detailed feedback. W1–W3 and Q1–Q3 are addressed by the new lossless protocol (SW + NACK feedback) and the end-to-end evaluation (Common Response, Sections 1–3) detailed below.

W1 / Q1 / Q3: complete lossless system and end-to-end rate.

  • Error detection at the decoder. Each codeword carries kk GF(263) check symbols, drawn freshly per codeword, and their rate (klog⁡2263/nk \log_2 263/n bpc) is counted. The decoder updates its LLM context only after a codeword passes both the syndrome and the checks.
  • Undetected error propagation. The LDPC decoder typically has a small probability of undetected error. kk checks multiply the probability of undetected error by at most 262−k262^{-k}. Thus, the probability of undetected error can be made small enough for practical purposes even with small kk. With k=2k=2, we measured 0 wrong accepted (92 caught by checks and correctly decoded with incremental syndromes) over about 608k codewords. More check symbols lower this at an exactly predictable cost: k=6k=6 gives 262−6≈3×10−15262^{-6} \approx 3 \times 10^{-15} for +0.008 bpc at n=4096n=4096, verified on the full test block (Common Response, Section 1).
  • Repair. Repair now uses implemented rate-compatible codes (incremental syndromes), not independent codes.
  • Reported rate. All bits are counted, including the SW-coded initial contexts, checks, raw fallbacks, feedback and start-level signalling.

End-to-end lossless bpc at the headline operating point: settings tuned on a disjoint dev split for a first-attempt frame error rate (FER) ≤10−3\le 10^{-3}, then measured on the held-out test block. The brackets give the % of codewords that needed feedback. SW uses a model-free encoder. The last column adds placement and a start-rate predictor driven by a cheap order-6 counts model (a table lookup per byte, plus a 6k-parameter MLP per codeword for the rate). LLMZip, measured as one stream on the same bytes, gives 0.932 bpc at every nn.

nnSWSW + rate + placement (order-6)
2561.638 (0.17%)1.533 (0.10%)
5121.494 (0.13%)1.356 (0.16%)
20481.349 (0.15%)1.334 (0.12%)
40961.292 (0.24%)1.255 (0.34%)

See Common Response (Section 3) for the full table with each component, and operating points that trade more feedback for a lower rate.

  • Q3: rate signalling. With the rate predictor, the encoder sends its start level with a fixed Huffman code fitted on dev (2–3.7 bits per codeword, included in the rate). SW needs no rate signalling, since its start rates are public.
  • Q3: timing. The SW encoder runs no model. It computes one sparse syndrome and two check symbols per codeword in 4–5.5 ms per MB on one CPU core. The order-6 variants add a cheap table lookup per byte and, for the rate, a small 6k-parameter MLP forward pass per codeword. LLMZip's encoder instead runs BLT-7B on every byte (about 5×10115\times10^{11} FLOPs per byte). Both decoders run the same BLT pass. Ours adds BP so its cost per column rises modestly from 1.5 to 2.4 s at n=512n=512 and from 6.0 to 6.4 s at n=2048n=2048 on one H200.

W2 / Q2: initialization dependencies. In the paper's layout at n≥2048n \ge 2048, a stream's initial context could lie in columns that are decoded later. The current tables use an updated layout that cuts the test block into nn independent rows so every context the decoder uses is already decoded. We implemented the deployable closed-loop decoder (BLT on decoded bytes with the same schedule) and verified that it recovers the source byte-exactly end to end at n=512n=512 and n=2048n=2048.

AuthorsOpenReview ↗

Response (2/2)

W3: error resilience, interactivity and latency.

  • A column is used as context only after it passes the checks, so errors cannot propagate. This keeps closed-loop decoding lossless end to end.
  • The headline is near one-shot. On the held-out test block (for settings tuned for FER ≤10−3\le 10^{-3} on dev), 99.7–99.9% of codewords decode from the first syndrome (without any NACK) with 1.001–1.005 overall mean decode attempts per codeword (Common Response, Section 3).
  • Feedback signalling cost is negligible as the decoder sends a message only on a NACK (the gap since the previous NACK using Elias-gamma coding). At the headline operating point, this costs at most 0.00012 bpc on the reverse link.
  • Rounds can be traded for rate. At n=2048n=2048, our SW scheme achieves 1.349 bpc near one-shot (1.00 rounds, headline), 1.230 at 1.09 rounds, 1.136 at 2.4 rounds, and 1.120 at 6.3 rounds, close to the code floor of 1.116 (Common Response, Section 3).
  • Latency model. Columns of a stack are decoded in order, because column pp is the context of column p+1p+1. The encoder streams start syndromes without waiting, so a codeword accepted at its first attempt costs no round trip. Each NACK adds one round trip (RTT) and one more BP attempt. Per column, latency ≈TLLM+rˉ TBP+(rˉ−1) RTT\approx T_{\text{LLM}} + \bar r\, T_{\text{BP}} + (\bar r - 1)\,\text{RTT}, with rˉ\bar r the mean attempts per codeword. At the headline point rˉ≈1.001\bar r \approx 1.001–1.0051.005: with a 50 ms RTT, NACKs add at most 0.3 ms per column on average, against 1.5–6.0 s of BLT inference per column in our unoptimised decoder. Throughput is unaffected when several stacks are decoded in parallel: the GPU works on other stacks while one waits for its increment.
  • The output equals the input unless a wrong decode passes the checks (probability ≤262−k\le 262^{-k} per wrong decode), and termination is guaranteed by the raw fallback. With k=6k=6 (an error probability of at most 3×10−153 \times 10^{-15} per codeword), this is "lossless" for all practical applications.

W4 / Q4: comparison with newer compressors. Our goal is LLM-quality compression with an encoder that runs no model. For a fixed model no encoder can go below the model's log loss and LLMZip already reaches it (0.932 bpc with BLT-7B on our test bytes). LLMZip with the same model is therefore the like-for-like reference and the gap to it is exactly the cost of removing the model from the encoder. It is possible to improve the performance of LLMZip with a stronger predictor model. A stronger decoder model would lower our rate in the same way (Theorem 1) with no change to the encoder. Against compressors with a similar encoder cost we are about 1.6$\times$ better than xz and zstd (1.292 vs 2.03 bpc at n=4096n=4096). We are happy to add any compressor the reviewer suggests but such a comparison does not change the contribution of the paper.

W5: dataset and model details, readability. We will expand the dataset and model description and rewrite the system section and Fig. 1 around the protocol (encoder →\to syndrome + checks →\to decoder with LLM →\to ACK/NACK).

W6: use case. The scheme fits settings where encoding happens on constrained devices and decoding in a datacenter. In these settings the encoder is the bottleneck: it runs on battery-powered or shared hardware, or must keep up with a high data rate, and it cannot host a large language model (7B). Our encoder computes one sparse GF(263) syndrome and two check symbols per codeword, with no model, no probabilities and no arithmetic coder. Decoding happens later, on accelerators that are already provisioned, and its cost is amortised (archives that are written often and read rarely) or offline (logs and telemetry analysed in batch). Examples are uploads and telemetry from edge devices using low-bandwidth uplinks, satellites that communicate with ground stations, write-many / read-rarely archives and log storage. The feedback channel in these settings is the ordinary ACK path/control channel in a wireless network.

AuthorsOpenReview ↗

Discussion Reminder

Thank you again for your detailed review. As the discussion period is closing soon, we wanted to check whether our response addresses your concerns. In brief:

  • Complete lossless system (W1, Q1). Each codeword now carries kk GF(263) check symbols; a wrong decode is accepted with probability at most 262−k262^{-k}, and detected errors are repaired with incremental syndromes over NACK feedback. Over about 608k codewords, no wrong decode was accepted (92 were caught and repaired); k=6k=6 costs only +0.008 bpc.
  • End-to-end rate (Q3, W2). Every transmitted bit is counted (initial contexts, checks, fallbacks, feedback, rate signalling): 1.638 to 1.292 bpc at n=256n = 256 to 40964096, with fewer than 0.25% of codewords needing feedback, against 0.932 bpc for LLMZip on the same bytes.
  • Latency (W3) and use cases (W6). We give the latency model and the rate at each latency operating point, and describe the settings where a model-free encoder matters.

If any point remains unclear, we would be glad to clarify it before the discussion closes. If the response resolves your concerns, we would appreciate it if you would consider updating your score.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Common Response (1/2)

We thank the reviewers for their thorough review. Two shared concerns were whether the scheme is lossless (dusC, 3pbe, CH4R) and whether the rates are end to end (dusC, 3pbe). We address both of them by a new implementation and evaluation.

1. A lossless protocol

We have implemented a full protocol with feedback.

  • Checks. Per codeword, the encoder now sends the syndrome and kk check symbols c=Rxc = Rx over GF(263), with RR drawn freshly per codeword from a public seed. The decoder accepts the BP decoder output only if it satisfies the syndrome and the checks. A wrong decode passes with probability at most 262−k262^{-k}, for any input. These check bits (klog⁡2263/nk\log_2 263/n bpc) are counted in all the reported rates below.
  • NACKs. The decoder sends a message only when a codeword fails its checks. It codes the gap to the previous NACK with Elias-gamma, spending about 2log⁡2(gap)+12\log_2(\text{gap})+1 bits per NACK. Because NACKs are rare, this cost is negligible, at most 0.00012 bpc on the reverse link (Section 3).
  • Choosing kk. Since LDPC coding and check generation are decoupled, kk check symbols cost exactly klog⁡2263/nk \log_2 263/n bpc. For this reason, all the rates can be readily adjusted for any kk, and hence any target reliability. We implement and verify this on the full test block at n=4096n=4096 where k=6k=6 gave identical decodes and +0.008 bpc, for a miss probability of 262−6≈3×10−15262^{-6} \approx 3 \times 10^{-15} per wrong decode.
  • Repair. On each NACK, the encoder sends a few extra syndrome symbols of a rate-compatible GF(263) LDPC family (incremental syndromes). If the top rate fails, the column is sent raw, which guarantees termination.
  • Measured. With k=2k=2, over about 608,000 codewords, 0 wrong decodes were accepted and 92 were caught by the checks.

2. Evaluation setup

  • One contiguous block of 8,388,608 text8 bytes is cut into nn independent rows, and column pp of the rows is one codeword. Every byte is coded and counted. The first few columns of each row are sent raw, and the rest of each row's first 128 bytes are SW-coded with a context that grows up to 128 bytes.
  • The reported rate includes all bits used for syndromes, increments, checks, raw fallbacks, feedback and start-level signalling (for adaptive rate schemes).
  • Each setting is tuned on a disjoint dev split for a first-attempt frame error rate (FER) ≤10−3\le 10^{-3}, and the results are measured on the held-out test block.
  • LLMZip with the same BLT-7B is measured as one arithmetic coder over the block with rate 0.932 bpc. xz -9e gives 2.031, zstd -19 2.037 and gzip -9 2.641.
AuthorsOpenReview ↗

Common Response (2/2)

3. End-to-end results

Encoder models. As suggested by reviewer 3pbe, we use a 6th-order Markov predictor (order-6) instead of the context-16 LLM (ctx16) for placement and the start-rate predictor at the encoder. The encoder then runs no large model since order-6 is a table lookup per byte, and the rate predictor only adds a 6k-parameter MLP per codeword. We report both side by side for comparison.

Headline (held-out test, bpc, with % of codewords resent in brackets). 0 wrong decodes accepted in every column. Rate is the learned start-rate predictor, placement assigns hard streams to well-spread variable nodes, and order-6 is a byte counts model with no neural network.

Methodn=256n=256n=512n=512n=2048n=2048n=4096n=4096
SW (model-free encoder)1.638 (0.17%)1.494 (0.13%)1.349 (0.15%)1.292 (0.24%)
+ rate (order-6)1.620 (0.11%)1.441 (0.14%)1.326 (0.17%)1.276 (0.39%)
+ placement (order-6)1.555 (0.09%)1.400 (0.16%)1.342 (0.12%)1.254 (0.34%)
Both (order-6)1.533 (0.10%)1.356 (0.16%)1.334 (0.12%)1.255 (0.34%)
+ rate (ctx16)1.605 (0.13%)1.431 (0.11%)1.308 (0.12%)1.256 (0.49%)
+ placement (ctx16)1.536 (0.21%)1.388 (0.10%)1.356 (0.22%)1.245 (0.59%)
Both (ctx16)1.500 (0.18%)1.319 (0.37%)1.312 (0.17%)1.228 (0.59%)
  • 99.4–99.9% of codewords decode from the first syndrome (1.001–1.011 attempts per codeword). The decoder sends a message only on a NACK, which costs at most 0.00012 bpc on the reverse link.
  • Even the cheap order-6 model lowers the bpc at every nn, by up to 0.138 bpc with rate and placement.
  • A better encoder model helps more. With ctx16 (BLT-7B on a 16-byte context), rate and placement together save 0.036–0.175 bpc, against 0.015–0.138 with order-6.
  • The SW model-free encoder is 1.6$\times$ better than xz and zstd.

Trading latency for rate. The same protocol tuned for more feedback rounds starts codewords lower and approaches the floor of the code. Model-free encoder, held-out test, bpc (mean rounds in brackets):

Operating point (dev target)n=256n=256n=512n=512n=2048n=2048n=4096n=4096
Near one-shot (FER ≤10−3\le 10^{-3}, headline)1.638 (1.00)1.494 (1.00)1.349 (1.00)1.292 (1.00)
Low latency (FER ≤6×10−2\le 6 \times 10^{-2})1.453 (1.06)1.328 (1.07)1.230 (1.09)1.199 (1.09)
Balanced (mean rounds ≤2.5\le 2.5)1.275 (1.94)1.192 (2.36)1.136 (2.39)1.133 (2.33)
Max compression (lowest dev bpc)1.242 (3.47)1.172 (4.81)1.120 (6.25)1.126 (5.67)
Code floor (genie start, every bit counted)1.2151.1711.1161.124
  • At n=4096n=4096 the gap to LLMZip shrinks from 39% to 29%, 22% and 21%, which is the gap of the code floor itself (+21%): with enough feedback, the protocol reaches the floor of the code. The application chooses the operating point.
  • An encoder model substitutes for rounds. Additionally, in the low latency operating point (FER ≤6×10−2\le 6 \times 10^{-2}), rate and placement with ctx16 give 1.367, 1.264, 1.202 and 1.172 bpc at 1.03–1.07 rounds. This closes 30–48% of the gap to the balanced operating point requiring about 2.3 rounds.

4. Changes to the paper

  • Losslessness will be defined as above, lossless up to a check miss probability of 262−k262^{-k} that can be made arbitrarily small, and will replace "certified / empirical lossless rate".
  • The end-to-end table above will become the primary headline, and its numbers will replace those in the abstract.
  • For completeness, Table 2 will be retained and will report the matched fixed-rate + feedback baseline, and all the gains will be stated against it (3pbe W2b).
  • Results with the cheap order-6 encoder model will be added next to ctx16 (3pbe W2a, CH4R W2), showing how the gains of adaptive placement and rate scale with model capability.
  • The use cases, related work, Slepian–Wolf framing and presentation will be revised in the paper as described in the per-reviewer responses.
AuthorsOpenReview ↗

Revision uploaded

We have uploaded the revised paper. Changes are marked in blue.

Changes promised in the Common Response, Section 4.

  • Losslessness is now defined as lossless up to a check miss probability of 262−k262^{-k}, which can be made arbitrarily small (Secs. 2 and 3). This replaces "certified / empirical lossless rate".
  • The end-to-end protocol is now the headline (Table 2, Sec. 4), and its numbers are in the abstract and in Table 1. Table 3 gives the trade-off between latency and rate, down to the code floor.
  • The model-free encoder with feedback is now the main contribution. Rate prediction and placement are presented as gains on top of it, with the order-6 model next to ctx16 (Tables 4 and 5, Sec. 6.3). The "0.09 and 0.264 bpc" claims were removed.
  • The zero-failure fixed-rate table (Table 7, App. E) now reports the matched fixed-rate + feedback baseline, and the gains are stated against it.
  • The use cases and the related work (Ancheta; Caire, Shamai & Verdú; PRISM; Girod et al.) are in Sec. 1. The data and model details are in Sec. 4 and App. H.

Other changes from the individual responses.

  • dusC: the system section now describes the protocol (error detection and feedback, Sec. 3), and Fig. 1's caption and steps follow it.
  • 3pbe: the gains of the encoder-side decisions are measured end to end against the model-free row (Table 4), and the code seeds are reported in App. H.
  • CH4R: mm is defined at its first use (Sec. 3), the side-information wording in Secs. 1 and 7 is fixed, and the fixed-rate results without feedback are collected in App. E.

Cross-references to the revised paper. Our earlier responses use the numbering of the submission. Their tables and sections now appear as follows:

SubmissionRevision
Table 2 (zero-failure fixed rate)Table 7, App. E
Table 3 (feed-forward rates)Table 6, App. E
Table 5 (predictor families)Table 9, App. I
Sec. 6 (other corpora)App. K
App. F (feedback)App. G

Secs. 1, 2, 3 and 7 and Table 1 keep their numbers.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.