Deletion traces: sample lower bounds and uniform reconstruction

Source and verification

This article explains family 122 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Deletion channels and reconstruction

Fix an unknown binary string $x\in \{0,1{\}}^n$. A deletion trace retains each position independently with probability $p=1-q$ and concatenates the surviving bits in order. The observer receives the whole trace, including its length, but not the original positions of its bits. Different traces are independent.

For example, the trace 01 of 001 may retain the first zero or the second zero. Those distinct retention patterns produce the same observation. The channel hides locations as well as deleting symbols.

Worst-case reconstruction requires success for each fixed input string. This differs from reconstructing a random string on average. The length and channel probability are known throughout this family.

Let $T_{q,s}(n)$ be the smallest fixed number of traces allowing recovery of every binary string of length $n$ with probability at least $s$. The estimator may be randomized and computationally unbounded. Thus a lower bound on $T_{q,s}$ is an information limitation, not merely a runtime limitation.

🏷️ The three manuscript contributions

Quantitative lower bound

Fix $s\in (0,1]$ and $0<c<1/(4\log 2)$. Along every sequence with $n\to \infty$ and $q^3\log n\to \infty$,

$$T_{q,s}(n)\ge n^{c\log (q^3\log n)}$$

eventually. In particular, every fixed $q\in (0,1)$ requires $n^{\Omega (\log \log n)}$ samples. (OpenAI, 2026)

The channel can vary between instances, but is held fixed throughout the construction and sampling experiment for each instance. The lower bound is for deterministic input words and complete traces, not for a restricted collection of trace statistics.

The two upper-bound papers use the parameter

$$\begin{array}{c}X=1+\frac{\log n}{1+\log (1/q)}(q>0),\\ X=1(q=0),\\ \begin{array}{rl}B(n,p)& =p^{-1}(\log n)X^2\\ & \cdot (1+\log X{)}^6.\end{array}\end{array}$$

Sample bound and uniform decoder

The latest-anchor manuscript gives reconstruction with $\exp (O(B(n,p)))$ traces and success at least $2/3$, including general exactly observed symbols, without asserting efficient decoding. (OpenAI, 2026a)

The uniform-decoder manuscript gives one randomized multitape Turing machine for binary strings and known rational $p=a/b\in (0,1]$. For absolute constants $C,c$, it uses at most

$$M=\lceil \exp (CB(n,p))\rceil$$

traces, succeeds with probability at least $2/3$, and halts within $(n+L+M{)}^c$ bit operations on every internal random sequence and every well-formed stream of traces of length at most $n$. Here $L$ is the binary length of the reduced numerator and denominator. (OpenAI, 2026c)

The runtime includes reading traces and their delimiters, parameter calculations, finite precision, and output. External generation of independent traces is the only oracle operation. For fixed $p$, both resources are quasipolynomial, since

$$\begin{array}{c}B(n,p)=O_p((\log n{)}^3{\ell }_n^6),\\ {\ell }_n=1+\log \log n.\end{array}$$

The lower and upper exponents do not match. For fixed deletion rate, their logarithms have orders at least $(\log n)(\log \log n)$ and at most a cubic logarithm with an iterated-logarithmic factor, respectively. Optimal complexity remains open within these statements.

🏷️ Low deletion and the full-length baseline

If $q\le n^{-\epsilon }$ for fixed $\epsilon >0$, then $X\le 1+1/\epsilon$ and $p^{-1}$ is bounded for large $n$. Hence $B=O_{\epsilon }(\log n)$: the sample bound is polynomial, and the binary decoder has polynomial bit complexity in $n+L$.

This does not contradict the lower bound, since then $q^3\log n\to 0$. At $p=1$, a single trace reveals the input exactly.

More generally, one entire undeleted copy appears with probability $p^n$. After $m$ traces, the probability of seeing none is

$$(1-p^n{)}^m\le e^{-m{p}^n}.$$

Thus roughly $p^{-n}\log 3$ traces always suffice by this elementary method. It is exponential at fixed $p<1$, which explains why the quasipolynomial upper bound needs more subtle statistics. In very low deletion regimes, the full-length method can itself become efficient.

🏷️ Generating functions expose the hidden positions

Index bits from zero, and let $Z_j$ be the $j$th bit of a trace, with absent positions contributing zero. Conditional on retaining input position $i$, its trace rank is the number of retained earlier positions, a binomial random variable. Therefore

$$\mathbb{E}\sum _j{Z}_j{w}^j=p\sum _{i=0}^{n-1}{x}_i(q+pw{)}^i.$$

The channel acts by the substitution $z=q+pw$. When $|w|\le 1$, its image is the disk $|z-q|\le p$. A detectable difference between source generating functions is useful only if it can be moved into this observable region without losing too much magnitude.

Single-coordinate means need not capture everything available in a complete trace. The upper-bound constructions use products at several trace ranks and exponential weights on the gaps between them. Their multivariate generating identities generalize this elementary substitution.

🏷️ Latest anchors and compact frequency masks

For two candidate strings, let $d$ be their first differing position. Group a tuple probe by its latest selected position $d+m$. Every term with $m<0$ queries only their common prefix and cancels. The discrepancy is consequently a polynomial in the anchor variable, rather than a Laurent expression with uncontrolled negative powers.

A period-avoiding contiguous pattern gives an initial discrepancy. The induction multiplies up to four weighted probes whose frequencies nearly cancel. Sorting their selected positions, including equality ties, merges them into one larger tuple. Its order grows by at most a factor four.

Choose the latest endpoint of the merged tuple as a common anchor. Differences from earlier endpoints are nonnegative gaps. Old masks cover inherited loose gaps, and a new mask covers the gaps introduced by the merger. This coverage provides decay for summing over otherwise unconstrained positions.

The masks have two controls: exponential decay in those gaps, and a representation by a complex measure supported on a bounded frequency region. A radial compactification replaces the initial mask with one having the desired frequency support, with a quantitatively small error. Keeping the masks in this form until the final stage prevents repeated expansion from exhausting the frequency and coefficient budgets.

At the stopping scale, the source expands the masks, selects a frequency witness, and moves all gap parameters together through one complex strip into the channel disks. Bounded trace tests then distinguish each pair. A union bound over all rival strings gives sample-efficient identification, but enumerating the rivals is not an efficient decoder. The general-symbol extension first observes the alphabet and uses binary projections to distinguish pairs; it retains this sample-only character. (OpenAI, 2026a)

🏷️ From pair separation to an efficient decoder

The uniform algorithm instead tests prefixes through a convex relaxation of the remaining bits’ moments. A moment functional assigns values to low-degree polynomials and requires nonnegative values on squares. Its moment matrix is positive semidefinite. Actual probability laws satisfy these conditions, but a feasible truncated array need not come from an actual law.

The required separation theorem is therefore stronger than pairwise distinguishability: no feasible moment array fixing a first wrong bit may imitate all selected trace statistics. Positivity supplies inner products, allowing a chain argument to propagate discrepancies through products. A spanning-tree assignment controls the new gaps when tuples interleave, and contour deformation reduces attenuation and frequency.

For a correct prefix, the true completion gives feasible moments but may lie on the boundary of the PSD cone. Mix it with a small amount $\theta$ of independent uniform signs on the remaining coordinates. The latter moment matrix is the identity, so

$$M_{\mathrm{mix}}=(1-\theta )M_{\mathrm{true}}+\theta I⪰\theta I.$$

Each bounded trace expectation changes by at most $\theta$. Thus statistical tolerance permits a strictly positive matrix margin. The source’s rational feasibility procedure is guaranteed to find a solution when this slack exists; it need not decide arbitrary exact semidefinite feasibility.

One simultaneous event controls every estimated rank statistic and hence all adaptively chosen prefixes. Exact rational PSD checks produce a separating vector when needed; projected updates and dyadic rounding make progress toward a slack point. A fixed iteration cap guarantees termination even on inaccurate or adversarial well-formed trace streams. The analytic witnesses proving separation need not be found by the algorithm. (OpenAI, 2026c)

🏷️ Indistinguishability and the lower-bound construction

For one-trace laws $P,Q$, total variation is $\mathrm{TV}(P,Q)=\frac{1}{2}{\sum }_w|P(w)-Q(w)|$. Two equally likely candidates can be distinguished with success at most $(1+\mathrm{TV}(P,Q))/2$. Since

$$\mathrm{TV}(P^{\otimes m},Q^{\otimes m})\le m\mathrm{TV}(P,Q),$$

tiny one-trace variation forces many samples for success greater than $1/2$. The manuscript proves that, at each fixed $q$, the minimum variation between distinct length-$n$ words decays faster than every inverse power of $n$.

Its construction creates hidden location uncertainty at successive scales. Exact common mass between side-output laws leaves a fair orientation bit unrevealed even after those outputs are reported. Many independent pairs create a broad binomial displacement of a central segment. Concatenating genuine traces of the fixed word’s pieces gives the correct complete-trace law; later auxiliary observations introduce explicitly tracked projection and conditioning errors.

Complementary signed patterns supply cancellation. The elementary Thue–Morse polynomial

$$\prod _{j=0}^{r-1}(1-z^{2^j})$$

has a zero of order $r$ at $z=1$. Convolving such signs with a broad displacement distribution suppresses differences. In the recursive expansion, even terms cancel. An odd term either has a single active descendant, where smoothing applies, or forces a binary subtree with at least $2^b$ old score factors at depth $b$. Shared and individual displacements must be controlled jointly to retain the extra decay.

Errors from failed layouts, conditioning, and projection back to real traces are included before taking many samples. The extension to every fixed positive success probability uses several independently selected gadgets and posterior factorization; the two-candidate inequality above alone does not prove it when $s\le 1/2$. Padding transfers the construction to every sufficiently large exact length. (OpenAI, 2026b)

🏷️ Key steps and proof outlines

One event controls every adaptive prefix decision

The uniform decoder estimates all rank statistics of order at most $D$ before testing prefixes. Let $N$ be their number and let $\zeta$ be the tolerance. Every statistic is a zero-one observable, so its empirical mean from $T$ traces has variance at most $1/(4T)$. Chebyshev at tolerance $\zeta /8$ and a union bound give

$$\mathrm{Pr}[\text{some statistic errs by more than }\zeta /8]\le \frac{16N}{T{\zeta }^2}.$$

Taking the source’s $T=512(1+N){\zeta }^{-2}$ makes this at most $1/32$. On this one event, every later prefix test sees accurate statistics even though the prefix was chosen using earlier tests. There is no new independent concentration claim for each adaptively selected prefix. (OpenAI, 2026c)

Positivity slack makes feasibility algorithmic

A correct prefix has the moment matrix of its actual remaining bits, which may be singular. Mix it with weight $\zeta /8$ of independent uniform signs on the remaining positions. Distinct square-free sign monomials are orthogonal under this product law, so its moment matrix is the identity. The mixture has matrix lower bound $(\zeta /8)I$. Every bounded channel statistic changes by at most $\zeta /8$, leaving room within the statistical tolerance.

For a wrong prefix with its first error at the last position, feasibility would reproduce all true statistics within $9\zeta /8$. The separation theorem excludes this once $\zeta$ is smaller than its witness gap. Thus on the good event a correct prefix has strict slack, while the competing wrong prefix is infeasible.

The rational solver exploits this promise. If an affine constraint is violated, its coefficient vector supplies a separating direction. If the moment matrix is not positive semidefinite, exact rational elimination supplies a vector $v$ with negative quadratic form. Writing $v^{\mathsf{T}}M(m)v=c+h\cdot m$ gives a direction $a=h/(G{v}^{\mathsf{T}}v)$, where $G$ is matrix dimension. The bound $\Vert h{\Vert }_1\le G\Vert v{\Vert }_2^2$ ensures $\Vert a{\Vert }_2\le 1$, while the slack point $m^{\ast }$ satisfies $⟨m^{\ast }-m,a⟩\ge \zeta /(8G)$.

A short move in that direction decreases squared distance to $m^{\ast }$. Projection to the coordinate cube cannot increase the distance; sufficiently fine dyadic rounding consumes only part of the decrease. Since the cube has bounded diameter, a fixed iteration cap guarantees a feasible output in the slack case and termination in every case. This proves exactly the feasibility interface the decoder needs, without an oracle for arbitrary exact SDP feasibility.

Latest anchors preserve polynomial structure

In the sample-only upper bound, group a tuple statistic by its latest selected source position relative to the first differing bit. Terms anchored before the discrepancy cancel because the candidate prefixes agree. All remaining anchor offsets are nonnegative. When probes multiply, their ordered tuples may interleave or share positions; choosing their common latest endpoint expresses every new displacement as a nonnegative gap. The masks then pay for sums over those gaps, and their compact frequency representation limits the cost of the eventual contour shift into channel disks. (OpenAI, 2026a)

Lower bounds preserve the complete observation law

For two one-trace laws with total variation $\eta$, a maximal coupling makes the traces equal with probability $1-\eta$. Couple $m$ independent copies coordinatewise; a union bound gives product variation at most $m\eta$. Thus pairwise success bounded away from one half requires order $1/\eta$ traces.

The lower-bound construction makes $\eta$ small by smoothing signed patterns with broad hidden displacements. The product ${\prod }_{j<r}(1-z^{2^j})$ has a factor $1-z$ from every term, hence a zero of order $r$ at one. This high-order cancellation suppresses low-frequency differences after convolution. The multiscale proof must preserve that suppression for the whole trace law, including side outputs; exact common mass hides orientation bits even after those outputs are revealed. Multiple gadgets and posterior factorization are then needed for arbitrarily small fixed success targets, beyond what the two-candidate coupling alone proves. (OpenAI, 2026b)

See Also

• Binary information contraction studies a channel with known coordinate locations; deletions introduce the additional difficulty of alignment.
• Edit-distance approximation compares two supplied strings, whereas reconstruction must infer an unknown string from random subsequences.

🏷️ Manuscripts and verification scope

• Uniform quasipolynomial-time trace reconstruction — pinned manuscript and companion source.
• A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction — pinned manuscript and companion source.
• Quantitative lower bounds for trace reconstruction — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope page selects the quantitative lower bounds and one-trace indistinguishability. Despite its broader heading, its comparator list does not select either quasipolynomial upper-bound manuscript. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A latest-anchor induction with spectrally compact masks for worst-case trace reconstruction.

🐻  OpenAI 2026b. Quantitative lower bounds for trace reconstruction.

🐻  OpenAI 2026c. Uniform quasipolynomial-time trace reconstruction.