DoDo-Code: an Efficient Levenshtein Distance Embedding-based Code for 4-ary IDS Channel
Authors: Alan J.X. Guo
Sihan Sun
Xiang Wei
Mengyi Wei
Xin Chen
Venue: NeurIPS 2025 poster ()
Keywords: combinatorial code
error correcting code
synchronization error correcting
Primary area: applications
TL;DR: An Levenshtein Distance Embedding-based Code for 4-ary IDS Channel

Abstract: With the emergence of new storage and communication methods, the insertion, deletion, and substitution (IDS) channel has attracted considerable attention. However, many topics on the IDS channel and the associated Levenshtein distance remain open, making the invention of a novel IDS-correcting code a hard task. Furthermore, current studies on single-IDS-correcting code misalign with the requirements of applications which necessitates the correcting of multiple errors. Compromise solutions have involved shortening codewords to reduce the chance of multiple errors. However, the code rates of existing codes are poor at short lengths, diminishing the overall storage density. In this study, a novel method is introduced for designing high-code-rate single-IDS-correcting codewords through deep Levenshtein distance embedding. A deep learning model is utilized to project the sequences into embedding vectors that preserve the Levenshtein distances between the original sequences. This embedding space serves as a proxy for the complex Levenshtein domain, within which algorithms for codeword search and segment correcting is developed. While the concept underpinning this approach is straightforward, it bypasses the mathematical challenges typically encountered in code design. The proposed method results in a code rate that outperforms existing combinatorial solutions, particularly for designing short-length codewords.

DoDo-Code: an Efficient Levenshtein Distance Embedding-based Code for 4-ary IDS Channel
Alan J.X. Guo Sihan Sun', Xiang Wei', Mengyi Wei', Xin Chen 1.2
Center for Applied Mathematics, KL-AAGDM, Tianjin University, Tianjin 300072, China State Key Laboratory of Synthetic Biology, Tianjin University, Tianjin 300072. China (jiaxiang. guo, gug. sihansun, weixiang, mengyi.wei. then__in]@ttjjie edu. cn
Abstract
With the emergence of new storage and communication methods, the insertion, deletion, and substitution (IDS) channel has attracted considerable attention. How- ever, many topics on the IDS channel and the associated Levenshtein distance remain open, making the invention of novel IDS IDS-correcting code hard task. Furthermore, current studies on single-IDS SieeIDDS-coreectin code misalign with the re- quirements of applications which necessitates the correcting of multiple errors. Compromise solutions have involved shortening codewords to reduce the chance of multiple errors. However, the code rates of existing codes poor at short lengths, diminishing the overall storage density. In this study, a novel method is introduced for designing high-code-rate single-IDS-correctin deep Levenshtein distance embedding. A deep learning model is utilized to project the sequences into embedding vectors that preserve the Levenshtein distances between the original sequences. This embedding space serves as a proxy for the complex Levenshtein domain, within which algorithms for codeword search and segment correcting is developed. While the concept underpinning this approach is straightforward, bypasses the mathematical challenges typically encountered code design. The proposed method results in a code rate that outperforms existing combinatorial solutions, particularly for designing short-length codewords.
codewords through
Introduction
With the emergence new storage and communication methods |22 [}, insertion, deletion, and substitution (IDS) channels over non-binary symbols have attracted significant attention. However, applying existing IDS-correcting codes to practical applications not straightforward and faces challenges such as low overall code rate and limited multiple error-correcting capabilities.
Most of the current IDS-correcting codes focus on correcting single error 6 of errors 12 13, with an emphasis on achieving asymptotic optimality in code rate. These codes
10 burst
typically varieties of the Parshamov-Tenengolt (VT) code 66
14 15 16]. Codebook generation
has recently gained attention in specific tasks, such as the
sentiitutioon---ellttittt
code [17.
However, in most applications, the ability to correct multiple IDS errors is erucial. This is because IDS errors may occur simultancously at different positions along the codeword, and the likelihood of insertion, deletion, and substitution can vary due channel properties, making them unequal in occurrence 18 [9].
To address the challenge of correcting multiple errors, a compromise approach is to employ segmented The sequence is
error-correcting code, as proposed previous studies 220 21 22
"Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

implicitly segmented into disjoint segments. each capable of correcting one single IDS error. This segmentation enables the sequence to rectify multiple errors some extent. However, the possibility remains that multiple errors may occur within the same segment. Researchers can employ an outer eroor-correciing code (ECC) to address such failures.
Unfortunately, the segmented crror-coreecting codes usually have low code rate, since these codes use the same code rate as their underlying current IDS-correcting codes have low code rate for small codeword lengths. For example, an order-optimal code of length over the 4-ary alphabet using log + Ollog log n) redundancy bits is introduced in 19]. The state-of sfate-of-the-ar art code rate till now is proposed in [10] with redundancy bits of log n + log log n + 7 + o(1, which reduces the redundancy by bits compared to the original code in [9]. Although such codes are efficient when n is large, the constant term in the number of redundancy bits limits their code rate when n small. Given this, there potential to enhance the code rate of segmented error-correcting codes, because the segments usually use shorter codewords
---rrrecccn code within each segment, and
23
This work focus on constructing a 4-ary code that uses fewer redundancy bits than the existing order- optimal code offered by the mathematicians 9 T0] the end of short-length codewords. Namely, following the bounded distance decoder (BDD) which is one of the basics of classical codes [25), the novel DoDo-Cou is proposed by leveraging the deep embedding of the Levenshtein distance. The embedding space is utilized as a proxy for the intricate Levenshtein domain, facilitating high code rate codebook design and fast IDS-corte IDS-correcting. The proposed DoDo-Code uses a comprehensive approach that includes the following key procedures: deep embedding of the Levenshtein domain, deep embedding- based greedy search of codewords, and deep embedding-basee segment correcting.
As result, the proposed DoDo-Code offers solution for IDS-correcting code when code length is short, excelling in the following aspects:
The proposed DoDo-Code achieves a code rate that surpasses the state-of-the-an and shows characteristics of "optimality" when code length n is small.
With edit operation corrupted codewords can be firmly corrected, the computational complexity is effectively reduced to Onn) of the decoder to correct IDS errors.
To the best of our knowledge, the proposed DoDo-Code is the first IDS-correcting code designed by deep learning methods and the first IDS IDS-correcting code that shows characteristics of "optimality" when the code length small.
Related works
30 31 have recently gained attention and achieved ofte-of-theeann performance in several settings, they offer little help in addressing the aforementioned issue. This is because they primarily target the additive white Gaussian noise (AWGN) channel and handle flip or erasure errors, rather than IDS errors. Moreover, being neural network-baseer these solutions typically fail generate the static, explicit codebooks for downstream applications.
While neural channel codes 226 27 28 29
3 Bounded Distance Decoder
The proposed code employs a quite fundamental approach called the BDD; let's revisit the basics of classical codes (55
Given a code C, which is a collection of codewords, its minimum distance is defined as follows:
d(C) = min(d((;; Cz)= : C, ej E C,i
Once code C' with a minimum distance of d is constructed, a BDD can be deployed with decoding radius
d-1 by correcting corrupted word è to the corresponding codeword such that
d(č, c) < r.
In the context of correcting IDS errors, the Levenshtein distance 7
plays pivotal role. It is defined as the minimum number of insertions, deletions, and substitutions required transform one sequence into another. According to the principles of BDD, to correct single IDS error, the decoding radius

---

in terms of Levenshtein distance is r | 1, meaning the minimum distance of the code must be least 3. Therefore, constructing a code ((n) for fixed code length n, whose elements have mutual Levenshtein distances greater than 3, is considered.
However, the construction of such a code faces three significant challenges. Firstly, the sizes of Levenshtein balls, representing the set of a sequence and its neighboring sequences within a Levenshtein distance of exhibit a lack of homogeneity [32 33). Researchers want select sequences with small Levenshtein balls as the codewords to enhance the code rate, but a clear depiction of Levenshtein balls is still absent [32 33]. An algorithm surpassing random codeword selecting has not yet been published to the best of our knowledge. Secondly, the computational complexity of the Levenshtein baseddce-based BDD is substantial. The complexity of computing the Levenshtein distance is at least O( Ve >> 0 [3 [3], unless the strong exponential time hypothesis false. Additionally, most existing neighbor searching algorithms, which are keys to the BDD process, are primarily designed for conventional distance [36] and inapplicable to the
Levenshtein distance.
4 DoDo-Code
4.1 Deep embedding of Levenshtein distance
Considering the complexity of calculating the Levenshtein distance, researchers have explored mapping sequences into embedding vectors, using conventional distance between these vectors to approximate the Levenshtein distance [37 38). Recently, deep learning techniques have been employed for Levenshtein distance embedding and achieved remarkable performance across various
works 33 40
42 43 44).
From a broader perspective, it is found that these embeddings not only accelerate the Levenshtein distance estimation, but also offer way analyze the properties and structures of the Levenshtein distance. The embedding aims to create a vector space where the squared Euclidean distance between vectors serves as a proxy for the Levenshtein distance between the original sequences. This allows us to leverage the geometric structure of the embedding space to reason about the complex combinatorial properties of the Levenshtein domain. For example, the vector space, the embedding vectors of sequences within Levenshtein ball should naturally exhibit a tight clustering. The embedding model from 4 is modified to focus more on the Levenshtein neighbor relations between the sequences in work.
Let s and t denote two sequences of length n on the alphabet {0, 1, 3,), and let d (s, t) represent the groundtruth Levenshtein distance between them. Our task is to identify an embedding function f(-), such that the mapped embedding vectors u = f()) and f(t) have conventional distance d = (u, v) approximates to the groundtruth Levenshtein distance d (s t). Let the embedding function f(::0) 0) be deep embedding model with learnable parameters é, which is implemented as a model with 10 ID-CNN (45) layers and one final batch normalization [46] in this
study. The training of f(: () can be expressed as an optimization of:
0 arg min Σ C(d, d)
(2)
arg min Σ (lddAAf(e)))))((ttt))))
where the function -(.-)) )) is a predefined loss function that measures the disparity between the predicted distance and the groundtruth distance. By optimizing (2), the parameters of the embedding model are learned and denoted ô. and the optimized deep embedding model f(: 0) is capable of mapping sequences to their corresponding embedding vectors. This model configuration is often referred to as a Siamese neural network [47]. A brief illustration of the utilized Siamese neural network is presented in Figure
The squared Euclidean distance between the embedding vectors is employed as the approximation of the groundtruth Levenshtein distance. It is defined as:
d = A(u, v) = Σ (u: vz)2
3

---

Although the squared Euclidean distance is not a true distance metric, its effectiveness has been validated in [43] Moreover, since it is simply the square of the Euclidean distance, it remains compatible with most neighbor searching algorithms in Euclidean space.
The negative log-likelihood loss with the Pois- son distribution (PNLL) [4). which is formu- lated as:
f(:01:
Embedding Nerwork
[(d, d) = PNLL(d::) å dlnd, (5)
has been proposed provide a global approxi- mation of the Levenshtein distance. In this work, the code's construction dependent on local structures within the Levenshtein distance do- main, namely sequences distance of or 2. Consequently, from the perspective of the greedy search algorithm, there is no functional difference between using the complete Leven- shtein distance and a truncated version. How- ever, this distinction is raised for training the embedding model, relaxing the optimization ob- jective truncated Levenshtein distance easier learning task for the model than approximating the global Levenshtein distance metric precisely. In view of this, the loss function is revised to emphasize the approximations between sequence pairs within the Levenshtein balls of radius 2. Specifically, the model is trained to provide a precise prediction for Levenshtein distance and to ensure that the predicted distance is greater than 2 when the groundtruth distance is greater or equal to 2. The revised loss function is defined as follows:
Shared Weight
Alu ej
f(;0)=
Einhedding
Network
Figure 1: Siamese neural network. Given two sequences s, t. mapped to respective embedding vectors u, The approximated distance is caleu- lated as a conventional distance between u and a.
L(d, d) = C(d, d)
if d = 1;
(6)
if 2 2, [ C(2,
where 1 aez is the indicator function that evaluates 1 when d < 2.
For the sake of brevity, f(-) will be used to represent the learned embedding function f(:;0) in the subsequent discussion.
4.2 Deep embedding- greedy search of codewords
As previously mentioned, single-IDS- -oooreeDt codes with large code lengths n are ineffective, as the longer the codeword, the higher the likelihood of multiple errors occurring within the same segment. Moreover, existing combinatorial codes have already achieved order optimal code rates, which are nearly optimal when is large.
In view of this, the code rates are focused. By concentrating on smaller code lengths, the random search for codebook becomes feasible.
codes with small code lengths n and aim to achieve higher
random search- based approach of constructing the code C(n) is repeating the following procedure: randomly selecting sequence from candidate set (initially consists of all possible sequences A(n) (0, 1, 2, ")), and then filtering out the neighboring sequences of the chosen one from this set.
To outperform the random codeword selecting algorithm in terms of code rate, a selecting criterion for choosing codewords from the candidate set is crucial in the greedy search procedure. Finding a method to select more codewords equivalent to enhancing the overall code rate. In a greedy search approach, codewords with fewer neighbors should be selected in advance. However, it remains an open problem to accurately depict the neighbor density of each sequence, as only the minimum, maximum, and average sizes of Levenshtein balls with radius 1 have been studied in existing works 32 33
Fortunately, the deep embedding of Levenshtein distance establishes a connection between the structural characteristics of Levenshtein distances and the distribution properties of the embedding vectors. This deep embedding allows for rough estimation of the neighboring sequences associated

---

with given sequence through the Euclidean ball centered at the embedding vector f(s). By employing final batch normalization, the embedding model outputs vectors that follow a multivariate normal distribution N(O, Σ) with a mean vector 0 and covariance matrix E. This probability density function (PDF) of the embedding vectors can then leveraged evaluate the density of neighbors around the codewords. Namely, low-density vectors correspond to sequences that have fewer Levenshtein neighbors. By selecting these sequences first, the greedy search makes the efficient choice at each step, leaving maximal room for future codewords and thus maximizing the final codebook size.
Let m denote the dimension of the random vector, the PDF of [N0, Σ) is formulated as
1 (-
p(a) (2x) + - exp
The covariance matrix Σ is easy to estimate with all of the embedding vectors f(A(n)). Having the estimated covariance matrix Σ in hand, the PDF of ((0, Σ) for each embedding vector can be calculated using 7 To achieve the goal of selecting codewords with fewer neighbors, an effective selecting criterion can be expressed in the embedding space as the sequence whose embedding vector has the lowest PDF value should be chosen as the codeword in each iteration. A step further, by making some simplifications to 7 an embedding vector and its corresponding sequence should be selected u > - zu is the maximum over the candidate set.
Algorithm 1 Deep embedding based greedy search of codewords
Input: Codeword length nı the 4-ary alphabet Σ4; pre-trained embedding model f()).
Output: A codebook C(nn) where the minimum distance between any two codewords is at least 3. 1: Create the candidate set A + A(n) containing all 4"h sequences of length n.
2: Initialize empty codebook C' t 0.
3: Compute the embedding vectors: = {f(+))s E A(n)).
4: Estimate the covariance matrix Σ of the embedding vectors U.
5: while A do
6: Select from A that f(s) have the lowest PDF value: arg max f f())"
7: Add s to the codebook: C' + (U(s))
8: Remove neighboring sequences: A),(s, where B(s, (s' (l,)
2}.
9: end while
10: return (mn)=C.
The entire procedure for the greedy selecting of codewords is illustrated in Algorithm [ Firstly, the statistical distribution NO. Σ) is estimated on the embedding vectors (A(n)). Subsequently, the sequence from the candidate set whose embedding vector possesses the lowest PDF value is chosen as a codeword. Finally, the candidate set is updated by filtering out the Levenshtein ball, and this selecting iteration is repeated until the candidate set becomes empty.
Once the codebook is generated, users encode information by choosing codewords according to indices from a predefined order.
4.3 Deep embedding- based segment correcting
Refer a corrupted codeword segment. In the Levenshtein domain, only brute-force methods are applicable for segment correcting to the best of our knowledge. This segment correcting method in BDD involves calculating the Levenshtein distance between the segment and all the codewords, and then selecting the codeword with the minimal distance as the correction. However, this brute-force approach incurs significant computational complexity, scaling up Onn² ('n))) It is worth noting that the cardinality of the code [C(n) grows fast with an increasing n in the experiments. While this method can undoubtedly be optimized through techniques like early stopping when calculating Levenshtein distances, its complexity remains at least O(((()))).
In this work, the deep embedding vectors and their distances are leveraged correct errors without using the Levenshtein domain. The segment correcting procedure is outlined in Figure 2 To be precise, K-dimension tree (K-d tree) [48] is constructed from the embedding vectors f(((n))
5

---

corresponding to the codewords C(n). Subsequently, the embedding vector é = f(é) of a corrupted segment è is utilized query its nearest neighbors v f(c) within this K-d tree, thereby confirming the nearest codeword e to this segment. Significantly, the construction of the K-d tree incurs one-time complexity cost, while the average complexity of querying operations from the K-d tree is Ollog (n)) 49). representing a considerable improvement over the previously mentioned brute-force search method.
(())
It is important to recognize that this neighbor- searching procedure is conducted within the em- bedding space, and is based on approximation rather than the exact Levenshtein distance. As a result, the query results from the K-d tree may not always accurately represent the true mini- mum Levenshtein distances. To mitigate this, multiple nearest neighbors can be queried, and the Levenshtein distances between the segment and the queried neighboring codewords can double-checked to improve the reliability of the results.
K-d free
segmen
embedd.
Quadyt neighhors
K-d K-d
CONFECE
crubed. VOC.
(C))))
Figure 2: Flowchart for the deep embedding- based segment correcting. A K-d tree is constructed us- ing the embedding vectors f f(C(n)) of all the code- words. The embedding vector of a segment is used to query the K-d tree for its neighboring sequences.
Experiments and Results
5.1 Codewords in the embedding space
To demonstrate the effectiveness of the proposed deep embedding- greedy search of codewords and the reasonability of using an estimated distribution to evaluate the density of the sequences, the embedding vectors for all the candidate sequences and the selected codewords are visualized and presented in Figure
(a) deep embedding based search
(b) random search
(c) VT code
The relationships between the codewords and their neighboring sequences in the embedding space under three different scenarios: (a) results from the proposed deep embedding- codeword search; (b) results from a random codeword search; (c) results using codewords from the VT code. In each subplot, the diamond markers represent the codewords, and the solid lines connect the codewords to their distance 1 neighbors. In (a) and (b), the color indicates the order in which the codewords were selected, with darker colors signifying codeword selected earlier. In (c), the red triangle markers identify sequences that are neither codewords nor within distance of 2 to any codeword.
Figure 3:
To enhance the readability, Figure is generated from experiments with simplified setting: the codeword length is set to N = 10, the code is reduced from 4-ary alphabet to a binary alphabet, and the embedding dimension is reduced to To visualize the embedding vectors effectively, the t-SNE [50] is employed to project the high-dimensional embedding vectors into R The Figure [a Figure 36 and Figure 3c are plotted by the codewords/vecton. obtained from the proposed deep embedding- based codeword search, random codeword search, and the VT code, respectively. In each subfigure, the diamond markers denote the codewords/vectors, and the solid lines connect these to their distance-1 neighbors.
In Figure [equree3aante and Figure the color scheme indicates the order in which the codewords were selected, with darker colors representing codewords selected earlier in the search procedure. A comparison of these two subfigures, which represent the projections of the embedding vectors, shows that the deep embedding- based search tends to select codewords closer to the periphery of the estimated distribution

---

of embedding vectors, while the random search selects codewords without any specific pattern. This observation aligns with that the embedding vectors follow multivariate normal distribution, and the vectors that deviate from the mean should be selected earlier in Figure 3a due to their lower PDF in the estimated distribution.
In Figure 3c] the combinatorially constructed codewords from the VT code are plotted over the em- bedding vectors. The red triangle markers identify the isolated sequences that are neither codewords nor within a distance of 2 from any codeword, which isolated sequences would be eliminated during the greedy codeword search the first two subfigures. The presence of these isolated sequences suggests that the Levenshtein balls with a radius 2, centered on the VT codewords, cannot make complete coverage on the Levenshtein domain. This indicates that a modification of the VT code, which considers these isolated sequences, could achieve larger code rate. Additionally, it is also observed in Figure 3c that the VT codewords have a biased distribution in the embedding space used in this experiment, with the codewords tending to be located in the North- while the isolated sequences are more likely found in the South-Eass of the plane.
5.2 Code rate and optimality
To illustrate the utilization of the deep embedding- based greedy search yields an augmented count of codewords, thereby promoting the overall code rate. Comparisons are made between the proposed code and the state-of-the-art combinatorial codes.
Given that the codebook, once generated, is relatively independent of the deep learning model, the code with the maximum cardinality from among 10 runs of the computational experiments is selected. The corresponding code rates are calculated using the formula
log, [C(n)
(n)
(8)
m2
5.2.1 DoDo-Code outperforms the combinatorial codes.
The resulting code rates are visualized against the code length in Figure For comparison, the code rates of the combinatorial code introduced in [9] which is order-optimal with redundancy of logn n- + (log log nı) bits, as well as the ofatc-of-the-art code rates from [10] which is also order- optimal using log n + log log n + 7 + o(1) redundancy bits, are presented. Additionally, the code rates corresponding to the imaginary redundancies of log n + log log n + 1, log n + log log n + log 3, and log + log log + in Figure 4 are also drawn. It's worth noting that for small code lengths no existing 4-ary code achieves these levels of redundancies.
Focusing solely on the proposed code, Figure 4 clearly shows a trend of increasing code rates with longer codeword lengths n. Notably, for n 11, the code rate reaches 68.9%. Compared to existing Mfte-offthheat works 19. [00. the DoDo-Code achieves a significantly higher code rate. This improvement is attributed to the fact that, although these established combinatorial codes are order optimal, the constant terms in their redundancies dominate when n is small, thereby reducing the code rates.
0.8
0.6
0.5
0.4
0.3
+1522
0.2
lopnii log
0.1
logn Orloglagn) mi (oai etal)
logn tagioge uoth Etaters (5011)
Dobbo Cale
0.0
11
Length n of the code C(n)
5.2.2 DoDo-Code may represent the minimal redundancy achievable.
Figure 4: The code rate of code searched by deep embedding-based greedy search strategy, re- ported as the best in 10 runs. Comparison meth- ods are the state-of-the-ar approaches of Cai and Garbys. The code rates corresponding to order- optimal redundancies of log n + log log + log n log log + log 3, and log n log log n 2 are also plotted. These levels of redundancies are not achieved by any codes before this work.
Furthermore, when compared to the imag- inary redundancies of log n + log log + flog 2, log 3, log 4} the code rate curve of DoDo-Code lies between log n + log log + and log + log log n + 2 and overlaps the curve of log n + log log n + log exactly. may be claimed that the proposed DoDo-Code is ap-
7

---

proximately optimal using log n + log log + log 3 redundancy bits. However, this assertion lacks theoretical proof in this study.
It's worth noting that log + log log n + log 3 can be reformulated as log 3n + log log n. which is code. It is known that correcting one-bit flip nearly the best code rate for single-IDS- in N bits requires at least log N redundancy bits for information to identify the error position. In the context of 4-ary code, correcting a substitution in bases requires information on both the error position and the substituted letter, which could be any of the other three letters. As result, minimum of log 3n redundancy bits required. Given this, the redundancy log 3n + log log is very close to its lower bound and possibly represents the minimal redundancy achievable. Mathematicians might explore this topic further by leveraging combinatorial or probabilistic methods.
5.3 Ablation study on embedding space searching and revised PNLL loss
To illustrate the effectiveness of searching for codewords in the embedding space, the comparison is made between the proposed embedding space search and the random codeword selecting, which is also introduced for the first time to the best our knowledge. The cardinalities of the codebooks were compared, both in terms of average and maximum results across 10 runs, with the findings presented Table T The results clearly indicate that using the PDF of the distribution of embedding vectors the selecting criterion in the greedy search yields larger codebooks. Furthermore, it is observed that the increase in codeword count becomes more pronounced as the codeword length n greedy search identifies 16.8%
increases. For instance, when 11, the deep embedding-bail more codewords compared to the random codeword selecting approach.
For an ablation study using the revised PNLL loss in Equation (6) as the optimization target for the Levenshtein distance embedding network, experiments were also conducted engaging the original PNLL loss from Equation (5). with the results presented in the row labeled DEGS * in Table The results suggest that employing the revised PNLL loss slightly increased the number searched codewords.
Table I: The cardinality of constructed codebook. The results are reported the mean value and maximum value over 10 runs of the experiments. The method "Rand" stands for random codeword selecting method, the method "DEGS" (resp. "DEGS#") stands for the proposed deep embedding- based greedy search with the revised PNLL loss (resp. original PNLL loss), and the "A" stands for the differences.
Method
7
8
9
10
11
Rand
251.5 5.1
813.2 + 3.7
2694.0 = 15.2
9091.7 + 18.8
31071.9 + 40.5
DEGS*
264.5 3.3
873.3 + 8.5
2963.5 18.4
10199.4 + 57.6
35720.4 + 297.7
avg.
DEGS
267.5 + 4.7
884.8 + 15.3
3001.6 8.5
10325 .4 + 48.6
35973.1 + 157.8
+6..4%
+8.8%
+11.4%
+13.6%
+15.8%
Rand
259
820
2717
9124
31142
DEGS
270
887
2983
10283
36191
DEGS
275
900
3011
10414
36368
A
+6.2%
+9.8%
+10.8%
+14.1%
+16.8%
5.4 Success rate and experimental time complexity of segment correcting
The proposed deep embedding- based segment correcting is proposed as an alternative to the neigh- boring search procedure of BDD. Experiments were conducted to demonstrate that the proposed method is both reliable and efficient.
It is worth noting that the searched codewords maintain minimum mutual Levenshtein distance of 3, ensuring that single error in a codeword can confidently corrected by the BDD. However, the deep embedding of the Levenshtein distance introduces approximation error, which can affect reliability of the nearest neighbors identified through the tree search in the embedding space. compromise solution is to increase the number A: of searched neighbors, and then perform a double confirmation using the Levenshtein distances these neighbors. Experiments with different values of & were conduceted, and the number of failed corrections out of 10 attempts is presented in Table

---

As indicated in 2 the ratio of failed corrections ranges from 0.3% to 0.9% along with different code length, when only one embedding vector (k 1) queried. When the search expanded to k 2 neighbors, the number of failed corrections decreases significantly. Further increasing the searched neighbors to k = 4, the number of failed corrections is out of correcting 10 modified codewords.
Table 2: Number of failed segment correctings in 10 tries by using tree search. The segments are obtained by randomly edit modification the codewords. & is the number of neighbors queried in the tree search.
7
8
10
11
k 142
k
328,
398,439
465,080
740,468
828,885
4,411
2,330
7,060
10,869
k 0
0
754
0
121
& 4
0
0
0
0
&
0
0
0 0
The proposed deep embedding-basee segment correcting utilizes K-d tree search in Euclidean space, which theoretically offers a lower average complexity of O(log ((n))). To demonstrate the efficiency of this method, experiments varying the number le of searched neighbors were performed, compared with the brute-force search method, which corrects segments by identifying the codeword with the minimal Levenshtein distance. As shown in Figure 5 the proposed method in Euclidean space significantly reduces time complexity by orders of magnitude compared to the brute-force approach. Moreover, the extra burden of raising k from 1 to 5 minimal, as indicated in Figure 5
5.5 Complexity
When the complexity of copying a codeword is disregarded, the encoder of the DoDo-Code operates with negligible complexity, since the codebook is pre- generatee, and encoding simply consists of selecting a codeword by its index.
Time used to correct 10 segments
10a
Tree search (K- 1)
Tree search (k- 5)
1976
Brute force search
10a
5738000
The embedding model, which is implemented by a CNN architecture, maps the sequences to their embedding vectors with a complexity of O(n). Without considering the one-time cost of building the K-d tree by the embedding vectors of the codebook, the segment correcting process incurs time complexity of most (nn) when querying k = 1 neighboring sequence. The set An)) containing all sequences of length over the 4-ary alphabet has a cardinality 4", and the code C(n) is subset of A(n). The theo- retical expected query time for the K-d tree is Oloo (C(n)), which simplifies to (n), con- sidering [(n) < 4th When querying k > 1 neighbors, the double-check Levenshtein dis- tance increases the time complexity to On²)).
10²
52 99
46
10a
10a
n=
n=
n= 10
n= 11
Length n of the code C(n)
Figure 5: The time used to correct 10 segments. The segments are obtained by randomly one edit modification on the codewords. k is the number of neighbors the tree search. The brute-force search calculates the Levenshtein distances until the finding of 1-distance codeword. The y-axis is in log scale.
The memory complexity store the K-d tree is O(m C(n))), where m is the dimension of the embedding vectors and [C'n)) is the cardinality the codebook. Since the tree can be generated on- fle-fly from the codebook each time the decoder is initialized, and the codebook is deterministically generated using a given embedding model and random seed, the only persistent storage needed is for the embedding model itself.
5.6 Dataset, source code, and model setting
All the sequences used for training and testing are generated randomly. The groundtruth Levenshtein distance is obtained by Python module called Levenshtein. Therefore, the experiments run inde-

---

pendently of any specific dataset and generate the data on their own. The source code is available in com aawaaaauuuuaaaa ennku/DoDo- DoDo Code Unless otherwise specified, the embedding model utilizes an architecture of stacking 10 ID-CNNs, with the embedding vector dimension set to 64.
https://ga thub. /ttt://.tttuuu....
6 Conclusion and Limitations
To address the code rate issue from the segmented error-correcting codes, the DoDo-Code, which boasts an "optimal" code rate at the short code lengths for 4-ary IDS correcting code, was proposed. By leveraging the deep embedding space as a proxy for the complex Levenshtein domain, the mathematically unexplored field is bypassed in the code design. The fundamental concept of BDD forms the backbone of the proposed code. In the embedding space, an efficient codeword searching algorithm was introduced maximize the codebook. Later, the decoding or correcting algorithm was integrated into the Euclidean embedding space by a K-d tree, reducing the computational complexity, Experiments illustrated the proposed DoDo-Codk outperforms the state-of-the- combinatorial codes in code rate when the code length is small.
Limitations. The DoDo-Code did not provide explicit mathematical rules for description, necessitat- ing a deeper understanding of combinatorial underlying principles. The codeword searching relies on greedy search strategy, which can lead to significant complexity when attempting to construct the codebook for large code lengths. We hope that future research by mathematicians will uncover the underlying principles governing codewords and lead to the invention of mathematically defined codes.
Acknowledgement
This work was supported by the National Key Research and Development Program of China under Grant 2020YFA0712100 and 2025YFC3409900, the National Natural Science Foundation of China, and the Emerging Frontiers Cultivation Program of Tianjin University Interdisciplinary Center.
References
[1] George M Church, Yuan Gao, and Sriram Kosuri. Next-generation digital information storage DNA. Science, 1376610)::22881168 2012.
[2] Nick Goldman, Paul Bertone, Siyuan Chen, Christophe Dessimoz, Emily M. LeProust, Botond Sipos, and Ewan Birney. Towards practical, high-capacity, low-maintenance information storage synthesized DNA. Nature, 494(74355:77-800 2013.
[3] Robert N. Grass, Reinhard Heckel, Michela Puddu, Daniela Paunescu, and Wendelin J. Stark. Robust chemical preservation of digital information on DNA in silica with error-correciing codes. Angewandte Chemie International Edition, 2455)22552 2015.
[4] Lee Organick, Siena Dumas Ang, Yuan-Jyue Chen, Randolph Lopez, Sergey Yekhanin, Kon- stantin Makarychev, Miklos Z Racz, Govinda Kamath, Parikshit Gopalan, Bichlien Nguyen, al. Random access in large-scale DNA data storage. Nature biotechnology. 36(3):242-248, 2018.
[5] Alex El-Shaikh, Marius Welzel, Dominik Heider, and Bernhard Seeger. High-scale random access on DNA storage systems. NAR Genomics and Bioinformatics, 4(1):lqab1266 01 2022.
[6] Rom R Varshamov and GM Tenenholtz. A code for correcting single asymmetric emror Automatica l'elleekhanika, 26(2):288-29) 1965.
[7] Vladimir Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet physics. Doklady, 10:707-710, 1965.
[8] Neil JA Sloane. On single-deletion-ccoreeiie codes. Codes and designs, 10:273-291, 2000.
[9] Kui Cai, Yeow Meng Chee, Ryan Gabrys, Han Mao Kiah, and Tuan Thanh Nguyen. Correcting a single indel/edit for DNA-based data storage: Linear-time encoders and order-optimality. IEEE Transactions on Information Theory, 67(6):3438-344 34518, 2021.
10

---

[10] Ryan Gabrys, Venkatesan Guruswami, João Ribeiro, and Ke Wu. Beyond single-deletinn correcting codes: Substittiions and transpositions. IEEE Transactions on Information Theory, 69(1):169-186, 2023.
[11] Clayton Schoeny, Antonia Wachter-Zeh, Ryan Gabrys, and Eitan Yaakobi. Codes correcting burst of deletions or insertions. IEEE Transactions on Information Theory, 63(4):1971-11855 2017.
[12] Thi-Huong Khuat and Sunghwan Kim. A quaternary code correcting a burst of at most two deletion insertion errors in dna storage. Entropy, 23(12):1592, 2021.
[13] Shuche Wang, Yuanyuan Tang, Jin Sima, Ryan Gabrys, and Farzad Farnoud. Non-binary codes for correcting burst of at most deletions. IEEE Transactions on Information Theory, 2023,
[14] Lorenzo Calabi and W Hartnett. A family of codes for the correction of substitution and synchronization errors. IEEE Transactions on Information Theory, 15(1):102-1M) 1969.
[15] Eicchi Tanaka and Tamotsu Kasai. Synchronization and substitution error-correcting codes for the Levenshtein metric. IEEE Transactions on Information Theory, 22(2):156-162 1976.
[16] Kedar Tatwawadi and Shubham Chandak. Tutorial algebraic deletion correction codes. arXiv preprint 1XX.:1990.00787 2019.
[17] Yi Lu, Yun Ma, Chenghao Li, Xin Zhang, and Guangxiang Si. Unrestricted error-type code- book generation for error correction code DNA storage inspired by NLP. arXiv preprint arXiv:2401.15915 2024.
[18] Meinolf Blawat, Klaus Gaedke, Ingo Hütter, Xiao-Ming Chen, Brian Turezyk, Samuel Inverso, Benjamin W. Pruitt, and George M. Church. Forward error correction for DNA data storage. Procedia Computer Science, 80: 1011 1022, 2016.
[19] Lorenz Welter, Roman Sokolovskii, Thomas Heinis, Antonia Wachter-Zeh, Eirik Rosnes, et al. An end-to-end coding scheme for DNA-based data storage with nanopore-sequenced reads. arXiv preprint arXiv:2406. 12955, 2024.
[20] Zhenming Liu and Michael Mitzenmacher. Codes for deletion and insertion channels with segmented errors. IEEE Transactions on Information Theory, (6(11:224-24) 232, 2009.
[21] Mahed Abroshan, Ramji Venkataramanan, and Albert Guillén Fàbregas, Coding for segmented edit channels. IEEE Transactions on Information Theory, 64(4):3086-3098, 2017.
[22] Kui Cai, Han Mao Kiah, Mchul Motani, and Tuan Thanh Nguyen. Coding for segmented edits with local weight constraints. In 202/ IEEE International Symposium Information Theory (ISTT), pages 1694-1699. IEEE, 2021.
[23] Zihui Yan, Cong Liang, and Huaming Wu. A segmented-edit error-correcting code with re- synchronization function for DNA-based storage systems. IEEE Transactions on Emerging Topics in Computing, pages 1-13, 2022.
[24] Issam Maarouf, Andreas Lenz, Lorenz Welter, Antonia Wachter-Zeh. Eirik Rosnes, and Alexan- dre Graell Amat. Concatenated codes for multiple reads of dna sequence. IEEE Transactions on Information Theory, 69(2):910 2022.
[25] Tom Richardson and Ruediger Urbanke. Modern coding theory. Cambridge university press, 2008.
[26] Mohammad Vahid Jamali, Hamid Saber, Homayoon Hatami, and Jung Hyun Bae. Productae: Toward training larger channel codes based on neural product codes. In ICC 2022-IEEE International Conference on Communications, pages 3898-3903. IEFE, 2022.
[27] Yoni Choukroun and Lior Wolf. Error correction code transformer. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances Neural Information Processing Systems, volume 35, pages 38695-38705. Curran Associates, Inc., 2022.

---

[28] Karl Chahine, Yihan Jiang, Joonyoung Cho, and Hyeji Kim. Deepict: Learning codes for interference channels. IEEE Transactions on Wireless Communications, 23(4):2740-23) -75444 2023.
[29] Hamid Saber and Jung Hyun Bae. Generalized concatenated polar auto-encoder: A deep learning based polar coding scheme. GLOBECOM 2024-2024 IEEE Global Communications Conference, pages 1942-1947, IEEE, 2024.
[30] Yoni Choukroun and Lior Wolf. Learning linear block error correction codes. In International Conference on Machine Learning, pages 8801-8814 14. PMLR, 2024.
[31] Seong-Joon Park, Hee- Youl Kwak, Sang-Hyo Kim, Yongjune Kim, and Jong-Seon No. CrossMPT: Cross-attention message-passing transformer for error correcting codes. In The Thirteenth International Conference on Learning Representations. 2025.
[32] Daniella Bar-Lev, Tuvi Etzion, and Eitan Yaakobi. On the size of balls and anticodes of small diameter under the fixed-length levenshtein metric. IEEE Transactions on Information Theory, 69(4):2324-234) 23440, 2023.
[33] Geyang Wang and Qi Wang. On the size distribution of levenshtein balls with radius arXiv preprint arXiv:2204.022000 2022.
[34] William Masek and Michael S. Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20(1):18-31, 1980.
[35] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 15, page 51-58, 2015.
[36] Pádraig Cunningham and Sarah Jane Delany. K-nearest neighbour classifiers a tutorial. ACM Comput. Surv. 54(6), jul 2021.
[37] Rafail Ostrovsky and Yuval Rabani. Low distortion embeddings for edit distance. J. ACM, 54(5):23-es, October 2007.
[38] Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký. Streaming algorithms for embedding and computing edit distance in the low distance regime. In Proceedings of the Forty-Eighth Anmual ACM Symposium on Theory of Computing, STOC '16, page 712-725, 2016.
[39] Satoshi Koide, Keisuke Kawano, and Takuro Kutsuna. Neural edit operations for biological sequences. In Advances in Neural Information Processing Systems, volume 31, 2018.
[40] Xiyuan Zhang, Yang Yuan, and Piotr Indyk. Neural embeddings for nearest neighbor search under edit distance, 2020.
[41] Xinyan Dai, Xiao Yan, Kaiwen Zhou, Yuxuan Wang, Han Yang, and James Cheng. Convo- lutional embedding for edit distance. In Proceedings of the 43rd International ACM SIGIR conference research and development in Information Retrieval, SIGIR, pages 599-608, 2020.
[42] Gabriele Corso, Zhitao Ying, Michal Pándy, Petar Veličković, Jure Leskovec, and Pietro Liò. Neural distance embeddings for biological sequences. In Advances in Neural Information Processing Systems, volume 34, pages 11559118551, 2021.
[43] Alan JX Guo, Cong Liang, and Qing-Hu Hou. Deep squared Euclidean approximation to the Levenshtein distance for DNA storage. International Conference on Machine Learning, pages 8095-8100 PMLR, 2022.
[44] Xiang Wei, Alan JX Guo, Sihan Sun, Mengyi Wei, and Wei Yu. Levenshtein distance embedding with Poisson regression for DNA storage. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 3779--1880 2024.
[45] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems 25, pages 1097-1105. 2012.
12

---

[46] Sergey loffe and Christian Szegedy. Batch Normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pages 448 456. PMIR, 2015.
[47] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using a" siamese" time delay neural network. Advances in Neural Information Processing Systems, 6, 1993.
[48] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Com- munications of the ACM, 18(9):509-517 1975.
[49] Jerome H Friedman, Jon Louis Bently, and Raphael Ari Finkel. An algorithm for finding best matches in logarithmic expected time, ACM Transactions on Mathematical Saftware (TOMS), 3(3):209-22) 226, 1977.
[50] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of machine learning research, 9(11), 2008.
13

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificcton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The contributions and scope of this work are clearly outlined in both the abstract and the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
14

---

Justification:
The conclusion section explicitly discusses the limitations of this work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sellispecifiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texi system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [NA]
Justification:
The paper does not present thcoretical results that are to the community.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: This manuscript includes all the necessary information for reproducing the results, and the source code available in the anonymized repository at hhttps // //anonymous. 4open wcweece/r/Deeee.......oe..e. 51BD
Guidelines:
15

---

The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to hosted model (e.g., in the of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The source code is available in the anonymized repository at https //anonymous 4open. science/ DDooo/Doooooo---55 and will be open-sourced upon publication of this work.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/Ct////oeeeeeeaeeaaaeee ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
16

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
The experimental details are included, and the source code is provided.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The results are reported in format of mean + std.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The time consumption is presented in Figure
Guidelines:
The answer NA means that the paper does not include experiments.
17

---

The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttp:://eeurip: httpp///w/p...ccccceeeeeeeeeeeee
Answer: [Yes]
Justification:
This research follows the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
We do not anticipate any negative societal impacts arising from this work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
If the authors
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
18

---

Since the datasets are randomly generated, the risk of misuse of the model is minimal.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The model architecture is correctly referenced and trained from scratch.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, pwtptts..ppssiiiiepae. thcode wwt.coo///aaaa com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The source code is available in the anonymized repository at https:// anonymous 4open wwwescceeeeeeeeeeeeeeeeeeeeeeeee Code- -1BB with a fine document.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
19

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our L.LM policy hatoge//nearris.cc/oooffeeeeeeee for what should or should not be described.
20


Reviews:
[{"review_id": "9DFC2WjsBp", "reviewer": "Reviewer_hcVn", "summary": "This paper introduces DoDo-Code, a deep learning–based method for constructing error-correcting codes over a 4-ary alphabet that are resilient to single insertion, deletion, or substitution errors. The core idea is to embed codewords into a continuous space where distances approximate the Levenshtein metric. This learned embedding enables efficient codeword construction through greedy search, and fast decoding using K-d trees. The motivation stems from the high computational complexity of directly computing Levenshtein distances in the discrete code space. By operating in a continuous proxy space learned by a neural encoder, the authors exploit the structured neighborhood geometry to select codewords more systematically, avoiding random or exhaustive search. For decoding, candidate codewords are first retrieved based on proximity in the embedding space, and then the exact Levenshtein distance is computed over this smaller subset to identify the closest match.", "questions": "No specific questions", "limitations": "None", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Application is niche but novel. Successfully addresses the practical problem that existing combinatorial codes have poor rates at short lengths. Specifically, exploiting the multivariate embedding to replace random search over the codeword space with a more structured tree-based greedy search for error correction is very interesting.\n\n2. Performance seems to be very good for short code lengths (N=10). While a code length of 10 is considered too small for general codes, within IDS codes it appears to be an acceptable choice for a small set of applications. Within this space, the practical performance (inference time for a given number of corrections) is impressive. \n\nWeaknesses \n\n1. Overly strong claims such as “...embedding vectors carry the properties of their original sequences from the Levenshtein distance domain...” are made without sufficient justification. Many such statements assume a high level of familiarity with the topic, making it difficult to fully appreciate the actual contributions.\n\n2. The overall research theme seems more suited to an information theory or wireless communication venue than NeurIPS. The contributions from a deep learning perspective are few to none, with most innovations stemming from the clever application of deep learning to solve error correction problems. For instance, there is a large body of work on \"neural channel codes,\" which similarly transform discrete codewords into continuous embeddings to improve error correction. Refer to [1], [2], [3].\n\nAgain, without detracting from the contributions of the paper, in my opinion, the work may be better appreciated by the coding theory community than the NeurIPS community, as the majority of the contributions lie in cleverly identifying the lack of structure needed for faster decoding of IDS codes in discrete space and bridging this gap by transforming the codes into continuous space using standard deep learning techniques.\n\n1. ProductAE: Toward Training Larger Channel Codes based on Neural Product Codes, ICC 2022\n\n2. DeepIC+: Learning Codes for Interference Channels, TWS 2023\n\n3. Generalized Concatenated Polar Auto-Encoder: A Deep Learning Based Polar Coding Scheme, GLOBECOM 2024", "was_revised": true, "final_justification": "Although the scope of work is of limited interest to NeurIPS community, it does tackle an interesting problem within the coding theory space and the community would find the work of value.", "rebuttal": "We thank Reviewer for the thoughtful and constructive review. We are encouraged that the reviewer found our approach to be novel, the application interesting, and the performance impressive for short code lengths.\n\nThe reviewer’s main concerns appear to be\n+ the paper's fit for the NeurIPS venue;\n+ its relation to “neural channel codes”;\n+ the clarity of certain claims. \n\nWe address each of these points below and are confident that these clarifications will demonstrate our paper's suitability for NeurIPS.\n\n-----\n## On the Contribution to Deep Learning and Fit for NeurIPS ##\nWhile we agree our work will be of interest to the coding theory community, we believe its core contributions also include a novel machine learning methodology for solving a difficult combinatorial search problem. \n\n+ **A Novel ML-based Search Methodology**. The central contribution is not merely the application of a deep model, but the introduction of a new, learning-based heuristic for combinatorial search. The key insight is to learn an embedding space and use the probability density function (PDF) of the embedding vectors as a heuristic to guide a greedy search. This allows us to select candidate sequences from the periphery of the distribution, which we show leads to larger codebooks than random search. We believe this principle—using the learned density of an embedding space to guide a search—is a generalizable ML concept applicable to other combinatorial problems where \"solution density\" is a relevant but intractable property.\n+ **Distinction from Standard ML Applications**. The custom loss function (Equation 6), is not a standard application of existing techniques. It is specifically tailored to the problem's unique requirement of ensuring a Levenshtein distance of at most 3. This demonstrates another way our approach is tailored to solve this specific scientific challenge.\n\n+ **NeurIPS 2025 is an interdisciplinary conference**. We'd also like to highlight that the NeurIPS 2025 **Call For Papers**, explicitly welcomes submissions in areas of \"**Applications**\" and \"**Machine learning for sciences**\" and emphasizes that “The Thirty-Ninth Annual Conference on Neural Information Processing Systems (NeurIPS 2025) is **an interdisciplinary conference**…”. We believe our work, which introduces a new, learning-based heuristic for combinatorial search, fits squarely within this scope. While the application is in coding, the technique itself is a machine learning contribution, and we believe a top-tier, interdisciplinary venue like NeurIPS is the place to share this work with the broader community.\n\n-----\n## On the Relation to “Neural Channel Codes”\nWe thank the reviewer for pointing us to the literature on \"neural channel codes.\" We have reviewed the suggested papers and agree they are important related work. However, they address a fundamentally different problem, and we will clarify this in our revision.\n\n+ The neural channel codes (e.g., ProductAE, DeepIC+, GCC POLAR-AE) use autoencoders to learn an end-to-end communication system. The neural network itself is the encoder/decoder pair, trained to minimize the bit-error rate, effectively replacing classic codes.\n+ DoDo-Code is a code construction algorithm. Our deep learning model is an offline tool used to search for a static, explicit codebook C(n) that satisfies a specific combinatorial property (d(C) ≥ 3). The final code is a simple lookup table, and the neural network is discarded after the search. Our method contributes to the design of codes, whereas neural channel codes contribute to their direct implementation as neural networks.\n+ Another fundamental difference is the error channel our codes are designed for. Existing neural codes (e.g., ProductAE, DeepIC+, GCC POLAR-AE, ECCT) primarily target the Additive White Gaussian Noise (AWGN) channel and flip\\substitution errors, a standard model for traditional communication systems. However, the AWGN model is not suitable for next-generation storage media, such as DNA-based storage or other biological sequence-based storage, where errors manifest as insertions, deletions, and substitutions. DoDo-Code is specifically built to handle these IDS errors, making the work distinct from and complementary to prior art in neural coding.\n\nWe will add a paragraph to our related work section to discuss this important distinction, which will better contextualize our contribution.\n\n-----\n## On Clarifying Claims and Improving Readability \nWe appreciate the reviewer’s feedback on clarity. We agree that the statement “...embedding vectors carry the properties of their original sequences...” can be made more precise.\n\nTo improve readability for a broader audience, we will revise this and similar sentences. For instance, we will change the above to:\n\n\"The embedding aims to create a vector space where the squared Euclidean distance between vectors serves as a proxy for the Levenshtein distance between the original sequences. This allows us to leverage the geometric structure of the embedding space to reason about the complex combinatorial properties of the Levenshtein domain.\"\n\nWe will perform a thorough pass of the manuscript to ensure our claims are precise and the work is accessible. \n\n-----\nWe believe these revisions, combined with our clarifications on the contribution, will show that DoDo-Code is a novel paper well-suited for NeurIPS. **We hope the reviewer will consider our response favorably.**"}, {"review_id": "CbkAahwaRI", "reviewer": "Reviewer_oBLi", "summary": "This paper introduces DoDo-Code, a novel method introduced for designing high-code-rate single-IDS-correcting codewords through using deep Levenshtein distance embedding. The method leverages a Siamese neural network to map sequences (codewords) into an embedding space that preserves Levenshtein distances, then uses this space as a proxy for complex distance computations in both codeword search and error correction. The approach targets short-length codewords where existing combinatorial methods have poor code rates.\nThe authors make three key contributions: (1) a deep embedding method that approximates Levenshtein distances using squared Euclidean distance in embedding space, (2) a greedy codeword search algorithm that selects sequences (codewords) with lowest probability density function values to maximize code rate, and (3) a fast error correction method using K-d tree search in embedding space. Experiments on 4-ary codes demonstrate superior code rates compared to state-of-the-art combinatorial methods for short codewords.", "questions": "1. The paper lacks clarity about the exact filtering criterion in the greedy search algorithm. In Section 3.2, you describe \"filtering out the neighboring sequences\" without specifying the distance threshold. However, examination of the code reveals that all sequences with Levenshtein distance ≤2 from each selected codeword are removed, not just distance-1 neighbors as the term \"neighboring sequences\" typically implies. This critical detail should be explicitly stated in the paper for algorithmic clarity.\n2. A pseudocode of the embedding-based greedy search algorithm may be included in the paper for better understanding.\n3. Table 1 demonstrates that the revised loss function yields larger codebooks compared to the original loss when used with embedding-based greedy search. However, the paper lacks a clear explanation connecting the loss function design to this improved performance. Could the authors explain how the revised loss function's approach affects the embedding space structure and subsequent PDF-based codeword selection, ultimately leading to the larger codebooks observed\n4. Could the authors provide more intuition behind the use of low probability density regions in the embedding space for codeword selection? A brief explanation how low-density embeddings correspond to fewer Levenshtein neighbors would make the strategy easier to understand.", "limitations": "Yes, the authors do address the limitations.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper presents a creative approach using deep learning by mapping sequences to embedding vectors and leveraging this embedding space as a proxy for the complex Levenshtein domain. A novel codeword searching algorithm was introduced in the embedding space to maximize the codebook, thereby achieving high-code-rate. Additionally, a decoding algorithm was integrated into the Euclidean embedding space using a K-d tree rather than operating in the Levenshtein domain, thereby reducing computational complexity.\n\nWeaknesses: Some sections (e.g. 3.2) of the paper rely on concepts that are explained somewhat briefly. Providing more illustrative explanations or examples could improve clarity and make the overall approach easier to follow.", "was_revised": true, "final_justification": "This paper is well written and deserves to be presented at NeurIPS.", "rebuttal": "We sincerely thank the reviewer for their thoughtful feedback and for recognizing the novelty and significance of our work. The reviewer’s comments are insightful and have helped us identify key areas where the manuscript's clarity can be improved. We are confident that by incorporating the suggested changes, the paper will be much stronger and more accessible.\n\nWe will address each of the reviewer's points below.\n\n-----\n## On the Filtering Criterion in the Greedy Search\n\nThe reviewer points out that the paper lacks precision in describing the filtering step of the greedy search algorithm and that this detail is critical for reproducibility. We apologize for this oversight.\n\nTo construct a code that can correct a single IDS error using a Bounded Distance Decoder (BDD), the minimum Levenshtein distance between any two codewords must be at least 3 ($d_{min} \\geq 3$). This ensures that the decoding balls of radius $r = \\lfloor((3-1)/2)\\rfloor = 1$ are disjoint. To enforce this $d_{min} \\geq 3$ property, the greedy algorithm selects a codeword and then filters out all sequences from the candidate set that have a Levenshtein distance of 1 or 2 from the selected codeword.\n\nIn the revised manuscript, we will explicitly state this in Section 3.2. We will change the phrase \"filtering out the neighboring sequences\" to \"filtering out the Levenshtein ball of radius 2 (i.e., all sequences $s’$ such that $\\Delta_{L}(s_{codeword}, s') \\leq 2$)\" to remove any ambiguity.\n\n-----\n## Request for Pseudocode for Section 3.2\nThe reviewer suggests that pseudocode would improve the understanding of the greedy search algorithm. We completely agree with this. \n\nWe will add a formal pseudocode block for the \"Deep Embedding-Based Greedy Search\" algorithm in the revised paper as follows. \n\n> #### **Algorithm: Deep Embedding-Based Greedy Search**\n>\n> **Input:**\n> * Codeword length $n$.\n> * The 4-ary alphabet $\\Sigma_4$.\n> * A pre-trained normalized deep embedding model $f(·)$.\n>\n> **Output:**\n> * A codebook $C(n)$ where the minimum Levenshtein distance between any two codewords is at least $3$.\n>\n> **Procedure:**\n>\n> 1.  **Initialization**:\n>      * Create the candidate set $A=A(n)$ containing all $4^n$ possible sequences of length $n$.\n>      * Initialize an empty codebook $C=\\Phi$.\n>\n> 2.  **Embedding and Distribution Fitting**:\n>      * Compute the embedding vectors for the candidate set: $U =\\lbrace f(s) | s \\in A(n) \\rbrace$.  \n>      * Estimate the covariance matrix $\\hat{\\Sigma}$ of the embedding vectors $U$ to model their distribution.\n>\n> 3.  **Iterative Greedy Selection**:\n>      * **While** the candidate set $A$ is not empty:\n>           * Select the sequence $s$ from $A$ whose embedding $f(s)$ corresponds to the lowest PDF value. This is achieved by finding the $s$ that maximizes the term $f(s)^{T} \\hat{\\Sigma}^{-1} f(s)$.\n>           * Add the selected codeword $s$ to the codebook: $C = C \\cup \\lbrace s \\rbrace$.\n>           * Identify the Levenshtein ball of radius 2 around $s$, which is the set $B(s, 2) = \\lbrace s' \\in A | \\Delta_{L}(s, s') \\leq 2 \\rbrace$.\n>           * Remove all sequences in $B(s, 2)$ from the candidate set $A$ to ensure the minimum distance requirement is met: $A = A \\backslash B(s, 2)$.\n> \n> 4.  **Return**:\n>      * Return the final codebook $C(n)=C$.\n\n-----\n## Explaining the Superiority of the Revised Loss Function\n\nThe reviewer asks for a clearer explanation of why the revised loss function (Eq. 6) leads to larger codebooks compared to the original PNLL loss (Eq. 5), as shown in Table 1. This is an excellent question that gets to the heart of our model design. \n\nAs clarified previously, the code's construction is dependent on local structures within the Levenshtein distance domain, namely sequences at a distance of 1 or 2. Consequently, from the perspective of the greedy search algorithm, there is no functional difference between using the complete Levenshtein distance and a truncated version. \n\nHowever, this distinction is raised for training the embedding model, $f(·)$. Relaxing the optimization objective to revised PNLL loss (Eq. 6) is an easier learning task for the model than approximating the global Levenshtein distance metric precisely. This allows the model to focus its capacity on the crucial local structure, providing a more accurate approximation for distances of 1 and 2. \n\nTo be precise, the original PNLL loss (Eq. 5) aims for a good global approximation. It tries to be accurate across all Levenshtein distances, treating an error in estimating $d=10$ similarly to an error in estimating $d=1$. Our revised PNLL loss (Eq. 6) is specifically tailored for the BDD task. It focuses on creating a very clear margin in the embedding space around the critical decision boundary for single-error correction. It heavily penalizes two specific failures: (1) misidentifying a $d=1$ neighbor and (2) failing to push $d≥2$ sequences far enough away (i.e., predicting $\\hat{d} < 2$ when $d≥2$).\n\nThe revised loss function compels the model to learn a more structured representation by focusing on the decision margin. This enhances the accuracy of the subsequent PDF-based density estimation, which in turn enables the algorithm to pack more codewords into the final codebook $C(n)$. While our method using the original PNLL loss (Eq. 5) already produces a code rate approaching the theoretical optimum, the revised PNLL loss (Eq. 6) improves this rate further. As demonstrated in Table 1, this additional improvement is consistent, though marginal.\n\nWe will add this detailed explanation to the end of Section 3.2 in the revised manuscript to connect the loss function's design directly to the empirical results in Table 1.\n\n-----\n## Intuition for Low-Density Codeword Selection\n\nThe reviewer asks for more intuition on why selecting codewords from low-density regions of the embedding space is an effective strategy. \n\nIt is important to first note a key difference from conventional error-correcting codes. In codes based on the Hamming distance, for instance, the Hamming balls are the same size for every sequence. In that context, the choice of codeword does not need to account for ball size. However, for IDS error correction, Levenshtein balls are not uniform; their size depends on the corresponding center sequences. \n\nIn greedy codebook construction, the strategy is to always select the codeword that removes the minimum number of other candidates. For our application, this translates to choosing sequences that have the smallest Levenshtein balls of radius 2, as this maximizes the candidate pool for future iterations. \n\nUnfortunately, characterizing the size of Levenshtein balls is a known hard problem in combinatorics, and no efficient algorithm exists to do this for every sequence.\n\nOur method uses the embedding space as a proxy to estimate this property. The Siamese network learns to map sequences with a small Levenshtein distance to vectors with a small Euclidean distance. It is therefore reasonable to assume that a sequence with many Levenshtein neighbors (a \"dense\" point in the Levenshtein domain) will be mapped to a vector that is surrounded by many other vectors (a dense region in the embedding space).\n\nThe PDF of the fitted multivariate normal distribution is our formal measure of this density. Our core intuition is that these low-density vectors correspond to sequences that have fewer Levenshtein neighbors. By selecting these sequences first, the greedy search makes the efficient choice at each step, leaving maximal room for future codewords and thus maximizing the final codebook size. Figure 4a visually supports this, showing our method preferentially picks codewords from the distribution's periphery. \n\nWe will integrate this step-by-step intuition into Section 3.2 to make the motivation behind our greedy search strategy clearer.\n\n------\n**We believe these revisions will fully address the reviewer's concerns regarding clarity. We are grateful for the opportunity to improve our manuscript and are confident that the revised version will meet the high standards of NeurIPS.**"}, {"review_id": "sPEYYYMLS5", "reviewer": "Reviewer_Rv7D", "summary": "This paper deals with coding for DNA storage. This problem is very popular in the research community as DNA based storage has a huge capacity. Sequencing operation is error prone and the errors which we can observe are not usual substitution errors but insertions and deletions. So, in order to deal with such errors new coding methods are required. Actually, such errors were already considered in the literature by Varshamov, Tenengoltz, Levenstein and others, these errors are a particular case of so-called asymmetric errors. But the problem is solved only for insertion or deletion of 1 symbol. The authors address the problem and propose new codes and embedding-based decoders that can deal with insertions, deletions and substitutions (IDS).", "questions": "- What is the memory complexity of K-d tree?\n- Please mention the numbers of codewords in the constructed codes.\n- What about long IDS correcting codes? Can the proposed approach be useful for this task?", "limitations": "The codes are short and contain small amount of codewords.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well-written, clear and proposes rather interesting approach.\n\nThe main weaknesses are as follows. The usual coding task is to construct exponential number of codewords, e.g. $2^{100}$. Here the number of codewords is small (such that we can perform brute force search).\n\nThe rate comparison is not clear for me. The VT codes are optimal codes that are guaranteed to correct one error. You perform comparison in different conditions (probabilistic ones). This should be mentioned explicitly.", "was_revised": true, "final_justification": "I would like to thank the authors for clarification. I will keep my rating at 4.", "rebuttal": "We would like to extend our sincerest gratitude to the reviewer for their time and insightful feedback on our manuscript. We are encouraged by the positive assessment that our paper is \"well-written, clear and proposes rather interesting approach.\" We appreciate the opportunity to address the weaknesses and questions raised. \n\nBelow, we address each of the reviewer's points in detail.\n\n-----\n## On the Focus on Short-Length Codes and Codebook Size\n\nWe thank the reviewer for their comment regarding the codebook size. This work deliberately targets a different, yet critical, area: designing high-rate, single-error-correcting codes for short lengths.\n\nThis focus is motivated by two key observations from the existing literature and practical applications:\n\n**Suboptimality of Existing Codes at Short Lengths:** State-of-the-art combinatorial codes, while order-optimal for large n, exhibit poor code rates at short lengths. This is because the constant terms in their redundancy calculations become dominant when code length $n$ is small. \n\n**Practicality for Multiple Error Correction:** A common and practical strategy for correcting multiple IDS errors is to employ segmented error-correcting codes. In this paradigm, a long sequence is divided into shorter, disjoint segments, each designed to correct a single error. The overall efficiency and storage density of such a system are critically dependent on the code rate of the short codes used within each segment. \n\nGiven these observations, high-rate, single-error-correcting codes for short lengths are critical for practical applications, **yet this area remains underdeveloped**. The proposed DoDo-Code directly addresses this gap by achieving a significantly higher code rate in the short-length regime. By improving the rate of these foundational short codes, this work provides a direct path to enhancing the performance of practical, multi-error-correcting systems.\n\nRegarding the specific number of codewords, we would like to direct the reviewer to Table 1 on Page 8 of the manuscript, which provides the precise cardinalities of the codebooks. For example, for a code length of $n=11$, our Deep Embedding-based Greedy Search (DEGS) finds a codebook with a maximum of $36,368$ codewords, a 16.8% improvement over the random search baseline. We will ensure this key result is referenced more clearly in the main text.\n\n-----\n## On the Rate Comparison and Deterministic Error-Correction Guarantee\nWe appreciate the reviewer raising this crucial point about the comparison conditions. We apologize if this was not sufficiently clear and welcome the chance to clarify a key aspect of our work: the DoDo-Code provides the same deterministic, worst-case guarantee for single-error correction as the combinatorial codes to which it is compared.\n\nThe \"probabilistic\" nature of our approach lies in the search heuristic for finding a good codebook, not in the properties of the final code itself. The codebook construction method, as outlined in Section 2, ensures that the minimum Levenshtein distance d between any two codewords is at least 3. According to the principles of BDD, a minimum distance of d=3 is the requirement to unambiguously and deterministically correct any single IDS error. The comparison with VT codes is therefore conducted under the same conditions of a guaranteed single-error correction capability. It is worth noting that the VT code is optimal for correcting a single insertion or deletion over a binary alphabet. However, for the 4-ary alphabet with ID**S** errors, existing codes based on the VT construction are only order-optimal; no optimal code is known. \n\nThe decoder, while leveraging the efficient K-d tree search in the embedding space, is also designed for high reliability. The tree search acts as a fast method to find the most likely candidate corrections. As we acknowledge that this search is based on an approximation, we employ a double-check mechanism by querying a small number of neighbors and verifying with the exact Levenshtein distance. As shown in Table 2, with $k\\geq 4$, our decoder achieved a 100% success rate over $10^8$ trials, confirming its practical reliability for single-error correction. \n\nAlthough the proposed fast decoder (K-d tree search) makes a trade-off to achieve lower time complexity, the error-correction capability of the code itself remains deterministic. The code and BDD guarantee that a brute-force search over the codeword set will reliably find the correct sequence for any single IDS error. \n\n-----\n## Responses to Specific Questions\nWe thank the reviewer for the following specific questions:\n\n+ What is the memory complexity of the K-d tree?\n\nThe memory complexity to store the K-d tree is $O(m * |C(n)|)$, where $m$ is the dimension of the embedding vectors and $|C(n)|$ is the cardinality of the codebook. In our experiments, we used an embedding dimension of $m=64$, and the codebook sizes $|C(n)|$ are detailed in Table 1.\n\n+ What about long IDS correcting codes? Can the proposed approach be useful for this task?\n\nThis is a very relevant question. As we discuss in the Section 5, our current greedy search algorithm is computationally intensive and not directly suited for constructing codebooks for very long code lengths. For the long-code regime, existing combinatorial approaches are already order-optimal. Therefore, the primary contribution of our paper is for the short-length regime where our method demonstrates a significant rate improvement over the state-of-the-art. We believe, however, that the learned embedding space itself could be a valuable tool for future mathematical analysis to uncover principles that might lead to the invention of new, scalable codes.\n\n-----\n**Summary of Planned Revisions**\n\nBased on the reviewer’s valuable feedback, we will revise the manuscript to improve its clarity:\n+ In the Introduction, we will add a sentence to more explicitly frame our work's focus on high-rate short codes and their direct relevance to practical segmented error-correction schemes.\n+ In Section 4.2, we will add a clarification to state that the rate comparison is performed between codes offering the same deterministic single-error correction guarantee.\n+ In Section 4.5, we will add the memory complexity of the K-d tree.\n\n-----\nOnce again, we thank you for your thorough review and constructive suggestions. We are confident that these clarifications will strengthen our paper and better highlight its contributions."}, {"review_id": "XDAfBUbYub", "reviewer": "Reviewer_1PZb", "summary": "The paper introduces a novel algorithm for designing high-code-rate single-IDS-correcting codewords through a deep Levenshtein distance embedding. The method is composed from a CNN based Siamese neural network that embeds symbol sequences in a Euclidian sub-space. The embedding is trained to preserve the Levenshtein distance between the original sequences.\n\nThe learned embeddings offer a solution for IDS channels decoding in two main aspects:\n\n1. The proposed DoDo-Code achieves a code rate that surpasses the state-of-the-art and shows characteristics of “optimality” when code length n is small.\n\n2. With one edit operation corrupted codewords can be firmly corrected, the computational complexity is effectively reduced to O(n) of the decoder to correct IDS errors.", "questions": "1. At what code length n does the DoDo-Code become computationally impractical? Have you conducted experiments for larger values of n, and does the performance advantage over existing methods persist at those scales?", "limitations": "The overhead in terms of space is not addressed.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well written and easy to understand.\n2. The proposed DoDo-Code achieves a state-of-the-art code rate compared to existing methods in the literature.\n2. The learned Levenshtein distance embedding enables a K-d tree–based segment correction procedure. This procedure has a time complexity between O(n) and O(n^2), depending on the number of queries, offering a performance advantage over existing methods.\n3. The reported experiments validate the code rate and correction time complexity claims for small code length (n). \n  \nWeaknesses:\n\n1. From a ML and deep learning perspective, the work presents no methodological advancements.\n2. The empirical evaluation of the correction capabilities and time complexity of the DoDo-Code are very limited, and is applied only on segments obtained by randomly one edit modification on the codewords. No evaluations on real world data sequences/segments were provided.\n3. Space complexity is not addressed, as the proposed method require storing the K-d tree and trained NNs together with the DoDo-Code code book.\n4. The use of the DoDo-Code for larger values of n is not discussed.\n5. The claim for \"minimal redundancy achievable\" is not formally proved.", "was_revised": true, "final_justification": "The paper proposes an original and interesting method for code-book design and decoding on single IDS channels. While the approach entails non-trivial space overhead that could limit its immediate practicality, the underlying ideas are innovative and, in my view, warrant publication.", "rebuttal": "We sincerely thank the reviewer for their thorough assessment and encouraging feedback. We are encouraged the reviewer  recognized that DoDo-Code achieves state-of-the-art performance with a novel, efficient decoding procedure.\n\nWe will address the weaknesses and questions in the follow.\n\n-----\n## On Methodological Advancement in Machine Learning\n\nWhile we agree that the underlying network architecture is a well-established deep learning model, this work still presents a novel and methodologically application of deep learning to solve a challenging problem in coding theory. The proposed work demonstrates a new, learning-based heuristic for combinatorial search. \n\n+ **A deep embedding-based greedy search**: We are the first to propose a data-driven greedy search that uses the probability density function (PDF) of embedding vectors to select optimal codewords. This approach provides a principled way to maximize codebook size by selecting sequences with fewer neighbors first. As shown in our ablation study, this search method finds up to 16.8% more codewords than a random search, demonstrating its effectiveness.\n\n+ **A revised loss function distinct from standard application**: The loss function is tailored to the specific requirements of the BDD. The revised PNLL loss function (Equation 6) specifically focuses on creating a precise mapping for Levenshtein distances of 1 and 2, which is critical for single-error correction, rather than a general-purpose approximation.\n\n+ We'd also like to highlight that the NeurIPS 2025 **Call For Papers**, explicitly welcomes submissions in areas of \"**Applications**\" and \"**Machine learning for sciences**\" and emphasizes that “The NeurIPS 2025 is **an interdisciplinary conference**”. We believe our work, which introduces a new, learning-based heuristic for combinatorial search, fits squarely within this scope.\n\n-----\n## On the Scope of Empirical Evaluation\n\nWe acknowledge that the experiments were conducted on segments generated by random single-edit modifications. This was a deliberate choice to establish the fundamental performance of DoDo-Code and enable a fair comparison with existing state-of-the-art combinatorial codes and theoretical bounds. These theoretical methods are themselves designed to correct a single error, irrespective of the channel's specific error characteristics. This serves as the standard way to validate the code's fundamental capabilities.\n\nRegarding the correction of single IDS errors with specific real-world patterns, we believe that the experiments partly provide substantial coverage. The experiments detailed in Table 2 tested the code against $10^8$ random single-edit modifications, a scale sufficient to encompass a vast range of potential error cases.\n\nWe acknowledge that correcting multiple errors from real-world data involves more complex error patterns. The DoDo-Code proposed in this work focuses on correcting a single error and, therefore, cannot be directly applied to multiple errors. However, it is well-suited to function as a “in-segment” code for schemes like segmented or marker codes [1-4], which are designed to handle multiple errors by correcting one error per segment. In this context, the performance on real-world multiple-error patterns is more related to the design of the segment code architecture, rather than “in-segment” code. \n\n+ [1] ZM Liu and M Mitzenmacher. Codes for deletion and insertion channels with segmented errors. IEEE Transactions on Information Theory\n+ [2] M Abroshan, R Venkataramanan, and AG Fàbregas. Coding for segmented edit channels. IEEE Transactions on Information Theory\n+ [3] K Cai, HM Kiah, M Motani, and TT Nguyen. Coding for segmented edits with local weight constraints. ISIT\n+ [4] ZH Yan, C Liang, and HM Wu. A segmented-edit error-correcting code with resynchronization function for DNA-based storage systems. IEEE Transactions on Emerging Topics in Computing\n\nWe will consider the application of this work to the correction of multiple errors using real-world data as a future investigation topic.\n\n-----\n## On Space Complexity\nWe thank the reviewer for pointing out the omission of a detailed space complexity analysis. The storage requirements of our method are manageable and consist of two main components:\n\n**The Trained Neural Network**: The embedding model is a 10-layer 1D-CNN with a fixed number of parameters. For a codeword length of $n=10$, the total number of parameters in the network is **2.7m**, making it a computationally lightweight model compared to contemporary deep learning architectures.\n\n**The K-d Tree**: The K-d tree is constructed from the embedding vectors of the final codebook, $C(n)$. Its space complexity is $O(m|C(n)|)$, where $m$ is the embedding dimension (64 in our work) and $|C(n)|$ is the number of codewords. Since codebook generation is a one-time, offline process, and our work focuses on small $n$, this storage overhead is practical and fixed before any decoding occurs. Furthermore, it is worth noting that this storage is not mandatory; the K-d tree can be generated on-the-fly from the codebook each time the decoder is initialized, thus minimizing persistent storage requirements.\n\nFor the online decoding process, the user only needs the lightweight embedding model and the pre-built K-d tree, not the entire training or search apparatus.\n\n-----\n## On Scalability for Larger Codeword Length $n$\nAs noted in the paper's limitations section, the greedy search for codebook generation becomes computationally intensive for large $n$ due to the need to process all $4^n$ possible sequences.\n\nThis is a deliberate trade-off. Our work is specifically motivated by the poor performance of existing order-optimal codes at short lengths. DoDo-Code is designed to fill this well-known gap in the literature. \n\nFor larger values of $n$, the constant terms in the redundancy of combinatorial codes become negligible, and the existing combinatorial approaches are good enough for code rate. Therefore, DoDo-Code is not intended to be a universal solution, but rather a superior and \"optimal\" one for the specific, practical, and challenging domain of short-length codes.\n\n-----\n## On the \"Minimal Redundancy\" Claim\n\nWe want to clarify that the claim of achieving \"minimal redundancy\" is presented as a strong empirical observation rather than a formal, theoretical proof, as stated in the paper. This distinction was made explicitly in the paper, where we state the \"assertion lacks theoretical proof\" in Line 294. To reflect this, we used cautious phrasing, as seen in Line 284: “Section 4.2.2 DoDo-Code **may** represent the minimal redundancy achievable”.\n\nEven though, the evidence for this claim is compelling. As shown in Figure 5, the code rate of DoDo-Code almost perfectly aligns with the curve corresponding to a redundancy of $\\log n+\\log\\log n+\\log 3$ bits. This value can be reformulated as $\\log 3n+\\log\\log n$, which is close to the theoretical lower bound of $\\log 3n$ bits required to correct a single substitution error in a 4-ary alphabet. (The lower bound of $\\log 3n$ is analyzed in Line 299.) \n\nIt is obvious that there still be a remaining gap between the empirical redundancy of $\\log 3n+\\log\\log n$ and the theoretical lower bound of $\\log 3n$. Honestly, determining whether this $\\log\\log n$ term can be eliminated for 4-ary code is a significant theoretical open question beyond the scope of this work. However, there is evidence to suggest this term may be necessary. For instance, most of the combinatorial codes pursue an order-optimal redundancy of the form $\\log n + O(\\log\\log n)$. The presence of a $\\log\\log n$ term in other solutions suggests it may be a characteristic feature. (Note that $\\log 3n= \\log 3 + \\log n$ and $\\log 3$ goes into $O(\\log\\log n)$)\n\n-----\n**Response to Questions**\n\n+ At what code length n does the DoDo-Code become computationally impractical?\n\nThe primary bottleneck is the codebook generation, which roughly scales with $O(4^n)$. Although this is a one-time, offline cost, the exponential scaling makes the greedy search computationally impractical for large values of $n$. Our experiments were conducted up to $n=11$ on a single CPU core, and we estimate that for $n$ significantly larger than $15$, the required resources would become prohibitive. \n\n+ Does the performance advantage over existing methods persist at those scales?\n\nThe trend of the performance in Figure 5 suggests that the advantage of the proposed work declines when $n$ grows. Actually, we do not expect the large margin performance advantage to persist for large $n$. \n\nAs discussed above, the performance of existing combinatorial codes improve as $n$ increases, because the constant terms in their redundancy formulas become negligible. The order-optimal property of these codes makes them nearly optimal for large $n$. Therefore, for applications requiring large $n$, established combinatorial codes are good enough. \n\nConversely, for applications that require small $n$, like segmented codes for multiple IDS error correction, DoDo-Code's advantage is clear. It provides superior performance at short lengths, a domain where other methods are poor in code rate. \n\n-----\nWe hope these clarifications have adequately addressed the reviewer's concerns and have further highlighted the novelty of our work. We are confident that DoDo-Code offers a valuable contribution to the field and respectfully ask the reviewer to consider it for acceptance."}]

Author rebuttal:

Meta-review: I wanted to thank authors and reviewers in engaging in a productive rebuttal discussion. All reviewers agreed that the paper presents acceptably novel and rigorous results, which also correlates with my own reading. I recommend acceptance.
Decision: Accept (poster)