Remembered Dictionaries: Universal Compression of Unbounded-Alphabet Streams with Decoder-Only Memory

Many real data streams are made of symbols drawn from a vocabulary with no fixed size. Examples include words, URLs, IP addresses, product identifiers and sketch counter values. When such a stream is compressed, a large share of the bits does not go to describing how often symbols occur. It goes to spelling out what each new symbol is. Now suppose a decoder, such as a fusion center or a router, has already received an earlier stream from a related source, but the new sender has never seen that earlier stream. The decoder then already "knows the dictionary" for most frequent symbols, and the encoder does not know that it knows. We ask whether a blind encoder can still avoid re-spelling those symbols. We propose a concrete, low-complexity code that does this. The encoder sends short hashes of frequent symbols in place of their full descriptions, and the decoder resolves each hash against its remembered vocabulary. We will analyze how much this saves over the known limits for compressing an unknown source on an infinite alphabet.

The question sits where three bodies of work meet without overlapping. Theory for infinite alphabets shows that compressing an unknown source perfectly on a countably infinite alphabet is impossible unless the class of sources is restricted. The usual restriction is an envelope, a decaying bound $f(i)$ on the probability of the $i$-th most likely symbol. Even then, a small vanishing distortion buys real savings (Silva and Piantanida, 2017; Silva and Piantanida, 2020). Universal coding with side information, meaning extra data available at the decoder, shows that decoder-only memory gives no gain under strict losslessness but substantial gain once a vanishing error probability is allowed. That result was proved only for finite-dimensional parametric models over a 256-symbol alphabet (Beirami and Fekri, UC-DIS). Distributed source coding supplies the binning idea. Its Slepian–Wolf theorem says an encoder can send a bin index and let a decoder holding correlated data pick the right member. No paper in our material combines decoder-only memory with unbounded alphabets.

Core Claim

On unbounded alphabets with arbitrary symbol labels, the part of the code that decoder memory can remove is mostly the dictionary: the identities of distinct symbols, as opposed to their order and counts. Pattern coding already separates these two parts. It codes the pattern (the order in which new symbols first appear) separately from the dictionary (which actual symbol each pattern index stands for) (Acharya et al., tight pattern bounds).

We claim that a blind encoder can replace the dictionary with hashes for every symbol that appears at least $\tau$ times in its own block. Each hash is about $\log_2 |S_m| + \log_2(1/\epsilon)$ bits long, where $S_m$ is the set of distinct symbols in the decoder's memory of length $m$ and $\epsilon$ is the allowed collision probability. Symbols seen fewer than $\tau$ times are either spelled out or mapped to an escape symbol. The escape choice costs Hamming distortion only on positions holding rare symbols, so the distortion vanishes.

Two relaxations work together here: a vanishing per-letter distortion, as in Silva and Piantanida, and a vanishing decoding error, as in Beirami and Fekri. We expect the combination to cut the dictionary cost from roughly $L$ bits per new symbol to roughly $\log m$ bits, where $L$ is the label description length. This holds for every symbol that is frequent enough to sit in both the block and the memory. Under strict losslessness the gain should disappear, which is the infinite-alphabet analogue of Beirami and Fekri's Proposition 3.

The count threshold $\tau$ is chosen from the data, and it is the key ingredient. In the earlier two-stage codes the truncation point $k_n$ is a fixed alphabet size. Here the encoder decides what to hash using only its own counts, because a symbol that is frequent in the block is very likely also present in memory.

Research Program

The analysis uses Poissonization, which treats the blocklength as a Poisson variable so that symbol counts become independent. Acharya, Jafarpour, Orlitsky and Suresh showed this changes redundancy by at most about one bit, and it turns sequence-level quantities into sums over individual symbols. Let $p_i$ be the probability of symbol $i$, $n$ the block length and $m$ the memory length. Then the expected number of distinct symbols in the block that also appear in memory is

$$ D_{n,m} = \sum_i \left(1 - e^{-n p_i}\right)\left(1 - e^{-m p_i}\right), $$

and the expected number of block symbols absent from memory is $\sum_i (1-e^{-np_i})e^{-mp_i}$. Both formulas follow directly from independent Poisson counts.

For the power-law envelope $p_i \le c\, i^{-\alpha}$, standard occupancy arguments give a number of distinct symbols in the block of order $n^{1/\alpha}$. The theory component will turn these sums into the following results, for both the power-law envelope $c\,i^{-\alpha}$ and the exponential envelope $c\,e^{-\alpha i}$:

  • matching upper and lower bounds on the dictionary rate under decoder-only memory;
  • the same bounds when the encoder also has the memory, which is the two-sided benchmark;
  • the same bounds with no memory at all.

The goal is a distributed version of Silva and Piantanida's critical sequence $u^*_f(n)$. That sequence marks the growth rate of truncation size below which allowing distortion still lowers redundancy. It scales as $n^{1/(\alpha-1)}$ for power laws and as $\log n$ for exponential envelopes. We conjecture that memory shifts this threshold, and we will test the conjecture rather than assume it.

We will also prove the strict-losslessness barrier for this setting. The argument is that any symbol can be missing from $S_m$ with positive probability, and the encoder must succeed for every possible memory. So zero error forces the full spelling.

The construction stays deliberately simple:

  1. Pattern and counts. These are coded point-to-point with a universal code for patterns, or with the Censoring Code of Boucheron, Garivier and Gassiat. The Censoring Code splits symbols into frequent and rare groups and comes within a logarithmic factor of the lower bounds for power laws.
  2. Frequent dictionary entries. Each symbol with count at least $\tau$ is sent as a hash.
  3. Decoding. The decoder restricts its candidates to $S_m$, ranks matches by their memory count, and picks the top match.

This decoder is a table lookup. It avoids two costs that hold back related schemes: the growing tree search that Distributed Arithmetic Coding needs (Grangetto, Magli and Olmo), and the long blocklengths that LDPC syndrome codes require. The hash length depends on $|S_m|$, and the encoder can bound $|S_m|$ from $m$ and the envelope. This mirrors Beirami and Fekri's assumption that the encoder knows the memory length but not the memory's contents.

An extension follows the correlated-parameter setting of Beirami and Fekri's network compression paper. There the memory source and the new source share most of their vocabulary but have different frequencies. Our analysis then depends only on the overlap of their supports, not on parameter correlation.

Baselines

The naive reference point is the point-to-point almost-lossless two-stage code of Silva and Piantanida, which ignores the decoder's memory. It truncates the alphabet to $k_n$ symbols, sends tail symbols as an escape, and codes the rest losslessly. Our version spells labels in full and tunes $k_n$ by grid search to the best rate at a matched distortion. Every proposed configuration must beat this baseline on rate at equal or lower per-letter Hamming distortion. Otherwise memory is not helping.

The strongest existing competitor for exploiting decoder memory is a "truncate, then finite-alphabet distributed code" pipeline. It first applies the same truncation. It then compresses the resulting finite-alphabet sequence with a universal Slepian–Wolf binning code that uses the decoder's memory as side information, in the spirit of Beirami and Fekri's decoder-only memory regime. We implement that regime as random binning with a decoder that picks the most probable sequence in the bin under a predictor trained on memory counts. For short blocks we use Distributed Arithmetic Coding, extended from binary to the truncated alphabet. Both pipelines get the same data, the same memory, the same grid over truncation size and bin rate, and the same error target. Our code beats this baseline if it reaches a lower total rate at equal block error and distortion, especially as $L$ grows. The file contains no numerical result for either method on unbounded-alphabet data. Grangetto et al. report experiments only on binary sources at blocklengths 50 to 1000, and Beirami and Fekri's results are analytical bounds. So: no reported result found on Lacuna for distributed coding on countably infinite alphabets, and we will reimplement both baselines.

The upper benchmark is two-sided memory: the encoder also sees the memory and can send exact indices into $S_m$. This bounds how much of the available gain the blind encoder recovers.

Two ablations isolate the key ingredients:

  • Fixed threshold. Replace the count threshold $\tau$ with a fixed hash set made of the top $k_n$ symbols by block count. This tests whether choosing what to hash from the data matters.
  • No hashing. Remove hashing so that only the memory-trained probability model is used. This isolates the dictionary saving from the probability-learning saving.

Why not just…?

Why not just truncate the alphabet and run a standard finite-alphabet Slepian–Wolf code? This is the real threat. If symbol labels are short, for example integers whose description costs about $\log i$ bits, then truncation plus binning may capture most of the gain, and our dictionary mechanism adds little. The proposal predicts the opposite only when label length $L$ is much larger than $\log m$. The experiments vary $L$ explicitly, from integer labels to string labels of 64 bits and more, to find the crossover. If no crossover appears, we will report that the dictionary is not where the gain lies.

Why not just give the encoder a shared static dictionary, as practical compressors do? That is the two-sided memory setting. It requires the encoder to receive the memory, which costs a communication round or a synchronized copy that the distributed setting rules out. We keep it as the upper benchmark and report the fraction of its gain that the blind encoder recovers.

Why not just learn the correlation with a neural distributed coder? Neural Distributed Source Coding trains a conditional vector-quantized autoencoder whose decoder uses side information. Its discrete latent vocabulary is fixed at training time, so it cannot represent symbols it never saw. That is exactly the regime we target, and the method also comes with no redundancy bounds. We do not run it as a main baseline. A brief test with fixed token sets would show the failure on held-out vocabulary, but this is secondary to the argument.

Why not let the encoder estimate which symbols the decoder has? Without feedback, the encoder's only evidence is its own counts, and that is precisely what the threshold $\tau$ uses. Any better estimate would need to know the memory's contents, which collapses into the two-sided case.

Proposed Experiments

The synthetic experiments draw i.i.d. sources from power-law envelopes with $\alpha \in \{1.2, 1.5, 2, 3\}$ and from exponential envelopes with several decay rates. Symbols get random string labels of controlled length $L$. Block lengths run from 50 to $10^5$, which brackets the short-block regime of Grangetto et al. Memory lengths satisfy $m/n \in \{0.1, 1, 10, 100\}$. In the correlated-support variant, the memory source and the block source share a controlled fraction of their supports.

As a real-data check outside the file's benchmarks, we will compress streams of skewed counters like those handled by CounterSnake (Liu et al.), with a previous window serving as memory. We will also compress tokenized text streams in which one document serves as memory for the next.

The metrics are:

  • total rate in bits per symbol, and redundancy above $nH(P)$;
  • per-letter Hamming distortion;
  • block decoding error;
  • decoder time.

Four checks decide the outcome:

  1. Strict-losslessness barrier. Under strict losslessness the decoder-only gain should vanish empirically. Setting $\epsilon \to 0$ with no escapes should force rates back to the naive baseline.
  2. Sources of savings. Measured savings should track the Poissonized prediction $D_{n,m}(L - \log_2|S_m| - \log_2(1/\epsilon))$ as $m/n$ and $L$ vary. A systematic mismatch would show that the analysis misses where the savings come from.
  3. Shifted critical sequence. The truncation size or threshold at which almost-lossless gains disappear should move when memory is present. This is the distributed counterpart of the critical sequence $u^*_f(n)$, and observing it, or failing to, is the main scientific outcome.
  4. Crossover against the strongest baseline. The crossover in $L$ against the truncate-then-bin baseline determines whether the dictionary mechanism is a real contribution or a reformulation.