- 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
- 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.
- 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
- 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.
- 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
- 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 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 via feedback) would be appreciated.
- 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 is available at the decoder, we can send at the rate of the conditional entropy . 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" on in the preceding equation if 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?
- 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?
- The number of rows in the parity-check matrix () is not mentioned before it is introduced on line 144.
4 comments
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 operations per byte, the same order as xz and zstd and about times less than ctx16 (, 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 on dev, all bits counted (bpc):
| 256 | 512 | 2048 | 4096 | |
|---|---|---|---|---|
| SW (model-free encoder) | 1.638 | 1.494 | 1.349 | 1.292 |
| + rate (order-6) | 1.620 | 1.441 | 1.326 | 1.276 |
| + placement (order-6) | 1.555 | 1.400 | 1.342 | 1.254 |
| + both (order-6) | 1.533 | 1.356 | 1.334 | 1.255 |
- Rate and placement with order-6 together save 0.105 and 0.138 bpc at and , and 0.015–0.037 at . 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- model is lowest at .
- The predictors of Table 5 all read the same ctx16 features, so each costs the same 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.
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.
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 output is wrong only if a wrong decode passes the checks, with probability at most 262−k, and k can be raised at a known cost (Common Response, Section 1). With k=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, 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:
Which results are lossless. We will state explicitly that the protocol results above are lossless up to the check miss probability (at most 262−k per undetected error from the LDPC decoder), enforced by feedback and the checks. Tables 3 and 5, which allow FER 10−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<p, a random variable correlated with the column Xp through the source. The decoder has Yp 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 Yp that gives the decoder's model Q(Xp∣Yp), a (mismatched) decoding metric, and Theorem 1 gives the achievable rate as the column log loss under Q. 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 m before line 144.