Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound

arXiv:2610.15631 · cs.IT, cs.DM, math.IT · Submitted 2026-10-11 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound".

Jane: Here's the gist of the paper. Codes in the Levenshtein metric that can correct multiple edits (including deletions, insertions, and substitutions) have attracted a lot of attention recently owing to their application in DNA-based storage and racetrack memories In this work, we present new techniques for designing explicit binary codes of length n that correct t edits with at most (2t+1) log n+Ot(log log n) bits of redundancy The main result is the existence of an explicit binary t-edit correcting code C ⊆ 0, 1n with redundancy (2t + 1) log n + 2tlog log n + Ot(1) bits, whose encoder and decoder run in polynomial time with respect to block-length n Pruning redundant reasoning tokens The paper introduces new techniques for designing explicit binary codes of length n that correct t edits with at most (2t+1) log n+Ot(log log n) bits of redundancy The authors first propose using a polynomial hash to construct a systematic code that corrects t edits with (4t + 2) log n + Ot(log log n) bits of redundancy Then, they propose the second technique called entropy recycling to use the indices of good hashes to carry information As a consequence, they obtain a partial-systematic code of length n that corrects t edits with at most (2t + 1) log n + Ot(log log n) bits of redundancy Finally, they provide deterministic polynomial-time encoding and decoding algorithms for their code How the training signal is built The construction rests on four ingredients: (i) Projected confusion set: If two codewords are within edit distance 2t, then their payloads are related in a simple way They call the set of such payloads the projected confusion set Γ(x), and show that it has size at most Dtn 2t for an explicit constant Dt and can be enumerated in polynomial time.

Tom: (ii) Polynomial hashes and good seeds: A good seed a yields a tag T = (a, Px(a)) that separates x from all of Γ(x) A single canonical good seed with b = (2t + 1) log n + Ot(1) already gives a systematic code with (4t + 2) log n + Ot(log log n) bits of redundancy.

Jane: (iii) Entropy-recycling fold: The key observation is that the encoder is free to choose which good seed to use The net cost of the tag drops from 2b to b + 1 bits.

Tom: (iv) Protecting the tag: A suffix-projection lemma shows that if two codewords are within edit distance 2t, then so are their suffixes.

Paper summary: Tom: So to wrap up, "Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound" presents a new technique using polynomial hashing and entropy recycling to design explicit binary codes that correct t edits with at most (2t plus one) log n plus Ot(log log n) bits of redundancy <ref:2610.15631#pg1,that correct t edits with at most (2t>.

Jane: The main thing they proved is the existence of an explicit binary t-edit correcting code with that specific level of redundancy, and the paper shows how to build it in polynomial time for encoding and decoding.

Lu: It’s significant because for t equals two, they show a redundancy of five log n plus some extra log log n bits, which beats previous results. For larger t, they improve upon the (4t minus one) log n plus o(log n) redundancy that was the best known for general t <ref:2610.15631#pg1>.

Meng: The paper tackles the problem of finding explicit codes that match existing theoretical bounds in a way that is constructive and runs in polynomial time, which is what we need for real-world deployment at scale.

Tom: The work really boils down to showing how you can use the structure of good polynomial hashes and then cleverly recycle their indices to reduce the information cost of the tag, moving us toward better bounds on error correction codes.

Jane: For someone listening who doesn't read math, it means they’re designing a system that corrects many kinds of small errors—deletions, insertions, substitutions—with a measured amount of extra data that is much tighter than what we could achieve before.

Conclusion: Tom: So we're wrapping up on Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound. Basically, this paper shows a new way to build codes that correct those mixed errors—deletions, insertions, substitutions—using much less extra data than we thought possible.

Jane: It seems like they've found a constructive method for explicit binary codes that matches the best known theoretical bounds for error correction right now. What do you think about matching those bounds?

Lu: They’re not just proving something exists; they’re building an actual encoder and decoder that runs in polynomial time, which is the real hurdle here. The authors show how to use polynomial hashes and then recycle the indices of good hashes to cut down on the required tag size.

Meng: But what does that practically mean for a system? If you're trying to store DNA or track things on a racetrack, less redundancy means smaller storage chips or faster processing speeds. Does it actually translate into something practical?

Tom: It translates into a tangible reduction in overhead. For t equals two, they’re getting five log n plus some extra log log n bits of redundancy, which is better than the six log n plus eight bound from previous work. That's a clear win on the number side.

Jane: So, for someone who doesn't read math, it means they’ve found a trick to use hashing to create a much tighter structure for error correction than before. It’s about making sure every bit of extra data actually does useful work in correcting those specific types of errors.

Lu: The clever part is the entropy recycling fold, which lets the encoder choose which good seed to use, dropping the tag cost significantly. They're pushing that leading term down from two log(Dtn squared t plus one) to just one log(Dtn squared t plus one).

Meng: I need to know how much faster this encoding and decoding actually runs when you scale it up. If it’s polynomial time, that’s good, but if the constant factors are huge, it’s still too slow for high-throughput applications. What's the actual runtime like?

Tom: The paper details algorithms where Step two of decoding takes time proportional to n to the power t plus one log n. So we're looking at something like n to the power t plus one log n operations, which is manageable for moderate values of t.

Jane: It’s about moving from theoretical existence proofs to actual, efficient systems that can handle real-world noise in things like DNA storage or memory. It shows a pathway toward codes that are both theoretically tight and practically fast enough to deploy.

Lu: Their future work involves combining this fold with other ideas, like syndrome compression, to potentially push that redundancy even lower down toward the existential bound for deletion-correcting codes.

Meng: If they can get it down to something closer to what we know about deletion codes, that would be a huge step in making these systems viable at scale. (Sound of gentle traffic noise increasing slightly)

VinUniversity · National University of Singapore

cs.IT, cs.DM, math.IT

Submitted: 2026-10-11

Updated: 2026-11-03

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: Codes in the Levenshtein metric that can correct multiple edits (including deletions, insertions, and substitutions) have attracted a lot of attention recently owing to their application in DNA-based…

Key concepts

Projected confusion set
This set contains the payloads of codewords that are close to each other in terms of edit distance. The paper shows this set has a manageable size, allowing the construction process to be polynomial time and explicit.
Polynomial hashes and good seeds
A good seed is a value that, when used with a polynomial hash function, creates a tag that effectively separates one codeword from all other codewords close to it. A single canonical good seed already yields a systematic code with (4t + 2) log n + Ot(log log n) bits of redundancy.
Entropy-recycling fold
This is the key technique where the encoder can choose which good seed to use. This choice reduces the net cost of transmitting the tag from 2b to just b+1 bits, significantly lowering the overall redundancy of the resulting code.
Tag protection
A suffix-projection lemma proves that if two codewords are close in edit distance, their suffixes must also be close. This property is used to ensure that appending a protected tag does not increase the required redundancy too much.

Terminology

Summary

Codes in the Levenshtein metric that can correct multiple edits (including deletions, insertions, and substitutions) have attracted a lot of attention recently owing to their application in DNA-based storage and racetrack memories This work presents new techniques for designing explicit binary codes of length n that correct t edits with at most (2t+1) log n+Ot(log log n) bits of redundancy

Pruning redundant reasoning tokens

The paper introduces a technique called entropy recycling to design explicit binary codes that correct multiple edits with a redundancy of (2t + 1) log n + Ot(log log n) bits. They first propose using a polynomial hash to construct a systematic code with (4t + 2) log n + Ot(log log n) bits of redundancy. p. 0

Where the paper says it

In this work, we present new techniques for designing explicit binary codes of length n that correct t edits with at most (2t+1) log n+Ot(log log n) bits of redundancy. We first propose to use a polynomial hash to construct a systematic code that corrects t edits with (4t + 2) log n + Ot(log log n) bits of redundancy.

Then, they use the indices of good hashes to carry information via entropy recycling, resulting in a partial-systematic code with at most (2t + 1) log n + Ot(log log n) bits of redundancy. p. 0
Where the paper says it

So, we propose the second technique, called entropy recycling, to use the indices of good hashes to carry information. As a consequence, we obtain a partial-systematic code of length n that corrects t edits with at most (2t + 1) log n + Ot(log log n) bits of redundancy.

Finally, they provide deterministic polynomial-time encoding and decoding algorithms for their code. p. 0
Where the paper says it

As a consequence, we obtain a partial-systematic code of length n that corrects t edits with at most (2t + 1) log n + Ot(log log n) bits of redundancy. Finally, we provide deterministic polynomial-time encoding and decoding algorithms for our code.

How the training signal is built

The construction relies on four ingredients:

(i) Projected confusion set:

If two codewords are within edit distance 2t, then their payloads are related in a simple way: the second payload is within edit distance 2t of a word obtained from the first by removing or appending at most 2t symbols at its end.

(ii) Polynomial hashes and good seeds:

They split the message into b-bit blocks, view them as coefficients of a polynomial Px(Z) over F2 b, and hash x by evaluating Px at a seed a in F2 b. A good seed yields a tag T = (a, Px(a)) that separates x from all of Γ(x). p. 4

Where the paper says it

Each competitor x ′ ∈ Γ(x) collides with x under fewer than n seeds, so fewer than Dtn 2t+1 seeds are bad for x. A good seed a yields a tag T = (a, Px(a)) that separates x from all of Γ(x).

(iii) Entropy-recycling fold:

The key observation is that the encoder is free to choose which good seed to use, and doubling the field size ensures every payload has at least K = 2b−1 good seeds, allowing b − 1 additional message bits to select the seed as the v-th good seed in a canonical order.

(iv) Protecting the tag:

The 2b-bit tag is mapped to a word of length 2b + Ot(log b) of a code with minimum edit distance at least 2t+1, and a suffix-projection lemma shows that if two codewords are within edit distance 2t, then so are their suffixes.

Where the gains come from

The redundancy is calculated as (2b + Ot(log b)) - (b − 1) = (2t + 1) log n + Ot(log log n). The entropy-recycling fold removes the cost of transmitting the seed, which is a significant saving over syndrome compression or coloring-based constructions. p. 9

Where the paper says it

The hash value ha(x) must take about |Γ(x)| · n ≈ n 2t+1 values to leave room for a separating seed, and the seed a itself is needed because the decoder does not know which seed the encoder used. Up to the extra factor n, which counts the collisions of a single competitor, this is the familiar “twice the GV bound” cost of syndrome compression [41] and of coloring-based constructions [27]: a coloring of a graph of maximum degree ∆ costs about 2 log ∆ bits.

The construction improves the leading coefficient of the best previously known explicit t-edit correcting codes from about 4t − 1 to 2t + 1, saving roughly (2t − 2) log n bits. p. 3
Where the paper says it

• Near-optimality for general t. Our construction improves the leading coefficient of the best previously known explicit t-edit correcting codes from about 4t − 1 to 2t + 1, saving roughly (2t − 2) log n bits.

The paper presents two main constructions: Construction III.3, a systematic code based on a single good hash with redundancy (4t + 2) log n + Ot(log log n) bits, and Construction IV. p. 1

Where the paper says it

For general t, Cheng, Jin, Li, and Wu [10] and Haeupler [19] obtained order-optimal (or nearly order-optimal) redundancy via deterministic document exchange, albeit with large constants. Sima and Bruck [38] constructed t-deletion correcting codes with 8tlog n + o(log n) bits of redundancy by generalizing the VT construction to sequences with sparse, regularly spaced synchronization patterns.

p. 5
Where the paper says it

Section III presents the systematic code based on a single good hash. Section IV introduces good and bad hashes and presents the code with (2t + 1) log n + Ot(log log n) bits of redundancy based on many good hashes.

4, which uses entropy recycling to achieve the better bound of (2t + 1) log n + Ot(log log n) bits. p. 0
Where the paper says it

So, we propose the second technique, called entropy recycling, to use the indices of good hashes to carry information. As a consequence, we obtain a partial-systematic code of length n that corrects t edits with at most (2t + 1) log n + Ot(log log n) bits of redundancy.

Construction IV.4 is not fully systematic because the b − 1 bits of ν are encoded in the choice of the seed, but it is partial-systematic as the first m = n − Ot(log n) symbols are message symbols. p. 3
Where the paper says it

Moreover, all but Ot(log n) message bits appear unaltered as the first n − Ot(log n) symbols of each codeword. We also give a simpler, fully systematic t-edit correcting code with (4t + 2) log n + Ot(log log n) bits of redundancy, encoding time Ot(n 2t+2 log2 n), and decoding time Ot(n t+1 log n) (Theorem III.

The complexity analysis shows that for Construction IV.4, the encoder and decoder run in time O˜t(n 2t+2 log2 n) bit operations, dominated by a single call to BADSET. p. 3

Where the paper says it

Let t ≥ 1 be fixed. For every sufficiently large n, there exists an explicit binary t-edit correcting code C ⊆ {0, 1} n with redundancy (2t + 1) log n + 2tlog log n + Ot(1), whose encoder and decoder run in polynomial time with respect to block-length n.

With fast arithmetic, the cost of these algorithms drops to O˜t(n 2t+1) time. p. 4
Where the paper says it

Doubling the field size ensures that every payload has at least K = 2b−1 good seeds, so we let b − 1 additional message bits select the seed as the v-th good seed in a canonical order. The seed thus carries information rather than pure redundancy, and the net cost of the tag drops from 2b to b + 1 bits.

The decoder for Construction IV. p. 3
Where the paper says it

Let t ≥ 1 be fixed. For every sufficiently large n, there exists an explicit binary t-edit correcting code C ⊆ {0, 1} n with redundancy (2t + 1) log n + 2tlog log n + Ot(1), whose encoder and decoder run in polynomial time with respect to block-length n.

4 can be run in Ot(n 2t+2 log2 n) bit operations. p. 3
Where the paper says it

Let t ≥ 1 be fixed. For every sufficiently large n, there exists an explicit binary t-edit correcting code C ⊆ {0, 1} n with redundancy (2t + 1) log n + 2tlog log n + Ot(1), whose encoder and decoder run in polynomial time with respect to block-length n.

The paper concludes that the construction appends to the payload a protected tag (a, Px(a)) consisting of a seed and a polynomial hash value. A single canonical seed gives a systematic code with (4t + 2) log n + Ot(log log n) bits of redundancy (Construction III. p. 4

Where the paper says it

Using a single canonical good seed with b = (2t + 1) log n + Ot(1) already gives a systematic code with (4t + 2) log n + Ot(log log n) bits of redundancy. (iii) Entropy-recycling fold.

p. 4
Where the paper says it

Using a single canonical good seed with b = (2t + 1) log n + Ot(1) already gives a systematic code with (4t + 2) log n + Ot(log log n) bits of redundancy. (iii) Entropy-recycling fold.

p. 4
Where the paper says it

Using a single canonical good seed with b = (2t + 1) log n + Ot(1) already gives a systematic code with (4t + 2) log n + Ot(log log n) bits of redundancy. (iii) Entropy-recycling fold.

3). Doubling the field size guarantees that every payload has more than q/2 good seeds, and letting b − 1 message bits choose the seed removes almost all of the cost of the seed (Construction IV. p. 4
Where the paper says it

The key observation is that the encoder is free to choose which good seed to use. Doubling the field size ensures that every payload has at least K = 2b−1 good seeds, so we let b − 1 additional message bits select the seed as the v-th good seed in a canonical order.

p. 4
Where the paper says it

The key observation is that the encoder is free to choose which good seed to use. Doubling the field size ensures that every payload has at least K = 2b−1 good seeds, so we let b − 1 additional message bits select the seed as the v-th good seed in a canonical order.

p. 4
Where the paper says it

The key observation is that the encoder is free to choose which good seed to use. Doubling the field size ensures that every payload has at least K = 2b−1 good seeds, so we let b − 1 additional message bits select the seed as the v-th good seed in a canonical order.

4).

The analysis shows that for Construction IV.4, the redundancy accounting is rB = b + 1 + ρt(2b) ≤ (2t + 1) log n + 2tlog log n + Ot(1). p. 9

Where the paper says it

The redundancy is n − m = N = 2b + ρt(2b). Since b ≤ (2t + 1) log n + log Dt + 1 and ρt(2b) = 2tlog b + Ot(1) = 2tlog log n + Ot(1), we obtain the stated bound.

The leading term of the redundancy is governed by log Γ(x) · (maximum number of collisions per competitor) ≈ log n 2t · n, and the fold removes the factor of two in front of it. p. 9
Where the paper says it

Up to the extra factor n, which counts the collisions of a single competitor, this is the familiar “twice the GV bound” cost of syndrome compression [41] and of coloring-based constructions [27]: a coloring of a graph of maximum degree ∆ costs about 2 log ∆ bits. The point of the next section is that the seed need not be pure redundancy.

The entropy-recycling fold is a general principle that applies whenever a code is built from a seeded family of hashes or colorings in which every message has many good seeds, and it removes the cost of transmitting the seed. p. 4
Where the paper says it

Using a single canonical good seed with b = (2t + 1) log n + Ot(1) already gives a systematic code with (4t + 2) log n + Ot(log log n) bits of redundancy. (iii) Entropy-recycling fold.

The paper presents explicit binary codes correcting t edits with (2t + 1) log n + Ot(log log n) bits of redundancy and polynomial-time encoding and decoding. The construction appends to the payload a protected tag (a, Px(a)) consisting of a seed and a polynomial hash value. p. 8

Where the paper says it

WARM-UP: A SYSTEMATIC CODE FROM A SINGLE HASH We first show how the polynomial hash of Section II yields a systematic t-edit correcting code with (4t + 2) log n + Ot(log log n) bits of redundancy. The idea is to append to the payload x a protected tag consisting of one evaluation point a and the hash value ha(x), where a is chosen so that ha distinguishes x from every payload in its projected confusion set.

p. 8
Where the paper says it

WARM-UP: A SYSTEMATIC CODE FROM A SINGLE HASH We first show how the polynomial hash of Section II yields a systematic t-edit correcting code with (4t + 2) log n + Ot(log log n) bits of redundancy. The idea is to append to the payload x a protected tag consisting of one evaluation point a and the hash value ha(x), where a is chosen so that ha distinguishes x from every payload in its projected confusion set.

A single canonical seed gives a systematic code with (4t + 2) log n + Ot(log log n) bits of redundancy (Construction III.3). Doubling the field size guarantees that every payload has more than q/2 good seeds, and letting b − 1 message bits choose the seed removes almost all of the cost of the seed (Construction IV.4). We conclude with a discussion of extensions and future work. p. 5
Where the paper says it

Section V describes the encoding and decoding algorithms and analyzes their complexity. Section VI concludes the paper with a discussion of extensions and future work.

p. 5
Where the paper says it

Section V describes the encoding and decoding algorithms and analyzes their complexity. Section VI concludes the paper with a discussion of extensions and future work.

The paper presents explicit binary codes correcting t edits with (2t + 1) log n + Ot(log log n) bits of redundancy and polynomial-time encoding and decoding. The construction appends to the payload a protected tag (a, Px(a)) consisting of a seed and a polynomial hash value. A single canonical seed gives a systematic code with (4t + 2) log n + Ot(log log n) bits of redundancy (Construction III.3). Doubling the field size guarantees that every payload has more than q/2 good seeds, and letting b − 1 message bits choose the seed removes almost all of the cost of the seed (Construction IV.4). We conclude with a discussion of extensions and future work.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Binary DNA Storage Correction: The AI system can correct multiple errors (edits, deletions, insertions, substitutions) in DNA-based storage systems with at most (2t + 1) log n + Ot(log log n) bits of redundancy for a given length n.

  2. Efficient Data Retrieval from Noisy Sequences: The system can decode messages from sequences corrupted by up to t edits by using deterministic polynomial-time encoding and decoding algorithms, allowing it to reliably recover the original message even when synchronization is lost due to insertions or deletions.

  3. Optimized Search in High-Density Memories: By employing entropy recycling, the AI system can utilize a partial-systematic code where the seed carries information rather than pure redundancy, effectively reducing the tag overhead from two times the GV bound to (2t + 1) log n + Ot(log log n).

  4. Near-Optimal Error Correction for General Edits: The construction provides an explicit binary t-edit correcting code with a leading coefficient of (2t + 1), improving upon previous best known explicit codes which were around (4t - 1).

  5. Scalable and Efficient Encoding/Decoding: The AI system can encode and decode messages in polynomial time relative to n, specifically achieving an encoder complexity of Ot(n 2t+2 log2 n) and a decoder complexity of Ot(n t+1 log n).

Abstract

Correcting synchronization errors is one of the oldest problems in coding theory. In the mid-1960s, Levenshtein, and independently Ullman, showed that a single deletion can be corrected with n+O(1) bits of redundancy, which is asymptotically optimal. For any fixed t, a Gilbert--Varshamov (GV) type argument shows that codes correcting t deletions exist with redundancy 2t n+O t(1). Achieving this classical GV-type bound explicitly has proved remarkably difficult. Explicit codes with redundancy O t(n) were first obtained by Brakensiek, Guruswami, and Zbarsky in 2016, half a century after Levenshtein, and Guruswami and Håstad matched the GV-type bound for two deletions only in 2021. For every fixed t at least 3, the best explicit constructions still require roughly twice the GV-type redundancy: (4t-1) n+o(n) for t deletions and 4t n+O t(n) for t edits (insertions, deletions, and substitutions). We close this factor-of-two gap for every fixed t, even in the Damerau--Levenshtein model, which also allows adjacent transpositions. We construct explicit binary codes with deterministic polynomial-time encoding and decoding that correct any combination of at most t such errors using 2t n+2t n+O t(n) bits of redundancy. A single construction thus achieves the leading term of the classical GV-type bound simultaneously for deletions, edits, and Damerau--Levenshtein errors, extending the Guruswami--Håstad result from two deletions to every fixed t and to substantially richer error models.

Sources

Related papers