{"id":"bdbb04d7-c202-4ba3-ada7-23e6f288f63d","arxiv_id":"2506.03976","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"Sequential tests for statistical sequence matching achieve an exact mismatch exponent when the match count is known, and provably dominate fixed-length tests in error decay.","lead":"This paper derives the exact exponential error rate (mismatch exponent) for sequential tests that decide which pairs of sequences in two databases come from the same unknown source distribution. It shows that stopping adaptively can beat fixed-length tests, and gives achievability bounds for the harder case where the number of matches is unknown.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's converse is overbroad as stated: a constant-output test (τ=N, φ≡H_l) satisfies the expected-stopping-time constraint but has infinite mismatch exponent under H_l, exceeding the claimed Es bound; the proof only works for tests that ensure positive mismatch exponents under all hypotheses.","rationale":"The reader's verdict is CONDITIONAL, and my concern does not overturn that overall assessment, but it points to a more central statement-level flaw than the one the reader flagged. The known-K exact exponent is the paper's headline result since it is the only part with a matching converse. The converse as stated is contradicted by a trivial constant-output test, and the proof explicitly assumes an unstated condition: that the test has positive mismatch exponents under all hypotheses (see the sentence before (141)). This is not an artifact of notation; the bound (151) genuinely requires the mismatch probabilities under the alternative distributions to vanish. The correct theorem likely holds for uniformly exponentially consistent sequential tests, and the method-of-types achievability and the data-processing converse are standard once that hypothesis is added. For that reason I recommend CONDITIONAL rather than REJECT: the exponent formula and the overall proof strategy appear sound, but Theorem 1's converse must be restated with the consistency assumption, and the same repair pattern should be applied to Theorem 3(ii), where the proof needs λ2<κ_l^K but the statement omits it. The constant-test counterexample is decisive against the literal wording of Theorem 1, so this is a load-bearing concern, not a stylistic quibble. The reader's identified weakest assumption (i.i.d. distinct distributions) is a modeling limitation, not an internal inconsistency; I do not make that the primary issue. My agreement is partial because the reader did not identify the Theorem 1 overstatement, though they did correctly identify the analogous omitted-condition problem in Theorem 3(ii).","tokens_in":28541,"tokens_out":10914,"duration_ms":124607,"concrete_test":"Give a one-page analytical check: set M1=M2=2, K=1, and l with M_1^K={(1,1)}. Let Φ_const be τ=N and φτ≡H_1^K. Verify that (7) is satisfied and β(Φ_const|P,Q)=0 under H_1^K, so the left side of (32) is +∞ whereas Es is finite for P_2≠Q_1. Then re-derive equations (141)-(152) under the explicit added assumption that β(Φ|P̃)→0 for every alternative hypothesis; if the re-derivation goes through, the theorem becomes correct after adding that hypothesis to the statement. This single test separates a harmless wording issue from a genuine gap in the central converse.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The converse part of Theorem 1 states an upper bound on the mismatch exponent for 'any sequential test satisfying the expected stopping time universality constraint.' This is false as written. Consider M1=M2=2, K=1, l=1 (matched pair (1,1)), with a nonempty alternative t=2. Define Φ_const by τ=N and φτ≡H_1. Then (7) holds with equality, but under H_1 the mismatch probability β(Φ_const|P,Q)=0, so the limsup in (32) is +∞, while Es(1,1,P,Q)=min_{t≠1} α D_{β/(α+β)}(Q_1||P_t) is finite whenever P_2≠Q_1. The proof itself reveals the missing hypothesis: immediately before (141) it says 'ensures positive mismatch exponent,' and the derivation of (150)-(151) requires β(Φ|P̃)→0 and β(Φ|P)→0. For a test that is poor under the alternative hypothesis, P̃(W) need not tend to 1, so the lower bound d(1-β(P̃),β(P)) ≥ -log β(P) is unjustified. Thus the exact known-K optimality theorem, the paper's central claim, is stated for a larger class than the proof handles. The likely repair is to restrict the converse to tests whose mismatch probabilities decay under every hypothesis (or to phrase optimality in terms of worst-case exponent); with that added assumption the data-processing argument is standard. This is a statement-level gap rather than evidence that the exponent formula itself is wrong, but it must be corrected before the 'exact exponent of optimal sequential tests' claim is accepted as stated. The unknown-K Theorem 3(ii) has the same flavor of a missing condition (the proof also requires λ2<κ_l^K, omitted from the statement), which is a further but secondary symptom.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies sequential tests for statistical sequence matching, where two databases of i.i.d. sequences are generated from unknown distinct distributions and a pair is matched if its distributions coincide. For the case where the number of matches K is known, the authors propose a non-parametric sequential test based on a minimal scoring function, prove that it satisfies an expected-stopping-time universality constraint, and claim an exact mismatch exponent Es(l,K,P,Q) = min_{t != l} sum_{(i,j) in M_t^K \\ M_l^K} alpha D_{beta/(alpha+beta)}(Q_j || P_i) for all optimal sequential tests satisfying that constraint. For the case of unknown K, they propose a sequential test with thresholds (lambda1, lambda2, lambda3), prove bounded expected stopping time under certain conditions, and lower-bound the false-alarm, mismatch, and false-reject exponents. They also compare with fixed-length tests from Zhou et al. and propose a one-step fixed-length variant, claiming benefits of sequentiality.","tokens_in":28895,"tokens_out":11273,"duration_ms":114846,"significance":"If the central claims are corrected, the paper makes a substantial contribution: it extends the fixed-length statistical sequence matching results of Unnikrishnan and Zhou et al. to the sequential setting and gives a parameter-free, method-of-types derivation of an exact mismatch exponent for optimal sequential tests when K is known. The unknown-K part provides a nontrivial achievable tradeoff among three error exponents and includes an honest statement that no converse is given. The paper also explicitly localizes a claimed error in [10, Eq. (64)] and provides numerical illustrations. However, the exact-optimality theorem is currently stated for a class of tests that is too broad, and the proof of the unknown-K expected stopping time omits a condition used in its own derivation; these issues are load-bearing and must be fixed before the central claims can be accepted as stated.","major_comments":[{"comment":"The converse in Theorem 1, Eq. (32), is stated for every sequential test satisfying the expected-stopping-time universality constraint (7), but this class includes the constant-output test tau = N, phi_tau = H_l. For that test, under H_l the mismatch probability is exactly zero, so the limsup in (32) is +infinity, while Es(l,K,P,Q) is finite whenever an alternative t has P_t != Q_1 (e.g., M1 = M2 = 2, K = 1, l = 1, t = 2). The proof does not handle this case: the condition 'ensures positive mismatch exponent' appears only in the sentence immediately before (141), not in the theorem statement. Moreover, inequality (150), d(1 - beta(P_tilde), beta(P)) >= -log beta(P), is not valid as a finite-N inequality; an asymptotic version can be recovered under exponential decay of both error probabilities by tracking the a log(1/b) correction term, but that argument is not supplied. The statement and proof should be aligned by adding a positive-mismatch-exponent condition under every hypothesis, or by phrasing the optimality claim in terms of worst-case exponent.","section":"Theorem 1 / Section V.B"},{"comment":"Theorem 3(ii) states that the expected stopping time is bounded when lambda2 > 0 and lambda3 < Lambda_l^K, but the proof's final bound (189) contains geometric-series denominators involving lambda2, F(lambda3, P, Q), lambda3, and G(lambda2, P, Q). By Lemma 1(iii), G(lambda2, P, Q) = 0 whenever lambda2 >= kappa_l^K (cf. (71)), so the h > K terms in (189) do not decay and the expected stopping time need not be bounded for lambda2 in that range, at least when K < M2. The proof actually concludes boundedness under 0 < lambda2 < kappa_l^K and lambda3 < Lambda_l^K; the theorem statement should include this additional upper bound on lambda2.","section":"Theorem 3(ii) / Section VI.B.1"},{"comment":"The achievability proof correctly derives in (132)-(135) that the limit of Delta(n) is Es(l,K,P,Q) = min_{t != l} sum_{(i,j) in M_t^K \\ M_l^K} alpha D_{beta/(alpha+beta)}(Q_j || P_i), but the concluding display (137) replaces this with min over individual pairs (i,j) not in M_l^K. Since the minimum over pairs is generally smaller than the minimum over sums, (137) proves only a weaker lower bound and does not match the theorem's claimed exponent. This appears to be a typographical slip, but as written the proof of the achievability part does not establish the stated exponent; the display should be corrected to the min over t of the sums.","section":"Section V.A, Eq. (137)"}],"minor_comments":[{"comment":"The test in (92) uses the events B^n_{h,t} defined in (53), which depend on lambda3, but Theorem 5 defines only positive parameters (lambda1, lambda2). The proof in (228) appears to replace the lambda3 terms from (182) and (185) with lambda2; please define lambda3 explicitly or state that lambda3 = lambda2 is intended.","section":"Theorem 5"},{"comment":"In Eqs. (93)-(95) the test is denoted Phi^uk_Zhou, but the theorem statement defines Phi^uk_FL; this inconsistency should be corrected.","section":"Theorem 5 displays"},{"comment":"The probability expression in (102) is written as a sum over the matched pairs only; after marginalizing over the unmatched sequences this is true, but the notation should be clarified to avoid the appearance that unmatched sequences are omitted from the joint distribution.","section":"Eq. (102)"},{"comment":"In Eq. (40) the liminf is written with /n, but the fixed-length test length is N; the variable should be N for consistency with the rest of the section.","section":"Theorem 2"},{"comment":"The comparison proves Ef(l,K,P,Q) <= Es(l,K,P,Q), which supports 'no worse' but not necessarily a strictly larger exponent; the wording 'larger mismatch exponent' should be qualified if equality can occur for some distributions.","section":"Section III.D"},{"comment":"The claim that [10, Eq. (64)] is incorrect is supported only by two numerical examples; if the paper intends to correct a prior published result, a derivation of the claimed non-equality would be more appropriate than numerical evidence alone.","section":"Section IV.B"}],"recommendation":"major_revision","confidential_remarks":"The paper is a serious contribution with a likely-correct exponent formula, and the issues identified are local rather than indications that the main formula is wrong. I recommend major revision rather than rejection: the converse of Theorem 1 needs a stated positivity-of-exponent condition, Theorem 3(ii) needs the lambda2 < kappa condition, Eq. (137) needs correction, and Theorem 5 needs its lambda3 parameter clarified. These are all fixable within the manuscript's scope. The paper would also benefit from a careful pass over notational inconsistencies in the appendices."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Sanjay,\n\nQuick read of arXiv:2506.03976. The known-K part is genuinely new and largely right, but Theorem 1 as stated is false. The converse claims to bound the exponent of any sequential test with bounded expected stopping time. That class includes the trivial test that always outputs H_l after N samples: E[τ]=N, mismatch probability zero, so the limsup exponent is +∞, exceeding the finite bound Es. The proof itself only works for tests with positive mismatch exponent under every hypothesis – the sentence before (141) says exactly that. So the theorem statement needs that added condition (or a worst-case-exponent phrasing). This is a statement-level gap, not a sign the exponent formula is wrong; the data-processing derivation is standard and the algebra in (132)-(135) checks out.\n\nWhat is new: the exact sequential mismatch exponent for known K, with a matching converse for the right class; the specialization to binary classification recovers Hsu-Li-Wang; the unknown-K achievability and the one-step fixed-length test are also new relative to Unnikrishnan and Zhou et al. The authors also give concrete numerical examples showing their Λ and κ do not simplify, which is useful.\n\nSoft spots: besides Theorem 1, Theorem 3(ii) states bounded expected stopping time under λ2>0 and λ3<Λ, but the proof (around Eq. (189)) also needs λ2<κ_l^K and strict positivity of the corresponding exponent; that condition is in the proof but not the statement. The claimed strict benefit of sequentiality over fixed-length tests is only proven as an inequality (Ef ≤ Es); 'strictly larger' is not established. The one-step fixed-length test comparison also uses ≥ where a strict claim is made. Minor typos (\"ur proposed\") throughout.\n\nBottom line: the core exponent computation is solid and likely to be the right benchmark, and anyone working on sequential detection or matching error exponents will find this useful. But the authors need to correct the statements before publication: add the positive-exponent assumption to Theorem 1, add the λ2 condition to Theorem 3(ii), and soften the strictness claims. I would not cite the theorem in its current form, but I'd be glad to see the revised version.\n\nFor peer review: send it out, but with a request for major revision and with a referee who checks statement-versus-proof mismatches.\n\nBest,\n[Your name]","headline":"Solid exponent computation for known K, but the stated optimality theorem is overbroad and the unknown-K theorem is missing a condition; worth refereeing after statement-level fixes.","tokens_in":29538,"tokens_out":4334,"would_cite":false,"duration_ms":41542,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A17","60F10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper derives exact mismatch exponents for sequential tests of statistical sequence matching and proves the proposed test achieves them when the number of matches is known.","keywords":["statistical sequence matching","sequential test","mismatch exponent","Rényi divergence","expected stopping time universality","false alarm exponent","false reject exponent","de-anonymization"],"falsifier":"Take a binary alphabet, set α = β = 1, M1 = M2 = 2, K = 1, with P1 = Q1 = Bern(0.2) as the true match and the alternative pair Q2 = Bern(0.8). Compute Es = D_{1/2}(Bern(0.8) || Bern(0.2)) and simulate the proposed sequential test with large N; if the empirical decay rate of the mismatch probability falls decisively below Es, the theorem's achievability claim is false.","tokens_in":28257,"feed_emoji":"📊","tokens_out":3355,"duration_ms":31840,"temperature":0.7,"pith_summary":"The paper studies the sequential version of statistical sequence matching, where two databases of i.i.d. sequences generated from unknown distributions must be matched. With a known number of matches K, it proves that every sequential test with bounded expected stopping time has mismatch exponent at most the quantity Es(l, K, P, Q) = min_{t != l} sum_{(i,j) in M_t^K \\ M_l^K} $\\alpha$ D_{$\\beta$/($\\alpha$+$\\beta$)}(Q_j || P_i), and it constructs a non-parametric minimal-scoring test that attains this exponent. This settles the sequential analogue of the fixed-length matching problem and shows that sequentiality strictly improves the exponent over fixed-length tests. For unknown K, the paper proposes a sequential test with bounded expected stopping time under certain parameter conditions and characterizes the tradeoff among the exponential rates of mismatch, false alarm, and false reject probabilities. It also gives a one-step fixed-length test that matches or improves the prior two-step fixed-length test.","feed_headline":"Exact error exponents found for sequential sequence matching","feed_subtitle":"A minimal-scoring test provably matches the best possible mismatch rate, beating fixed-length tests.","key_machinery":"The central object is the scoring function S_t^K($x^{{\\xi n}}$, $y^{{\\chi n}}$) = \\sum_{(i,j) \\in M_t^K} GJS(\\hat{T}_{x_i}, \\hat{T}_{y_j}, \\$\\alpha$, \\$\\beta$), where GJS(P, Q, \\$\\alpha$, \\$\\beta$) = \\$\\alpha$ D(P\\|R) + \\$\\beta$ D(Q\\|R) with R = (\\$\\alpha$ P + \\$\\beta$ Q)/(\\$\\alpha$ + \\$\\beta$) is a generalized Jensen-Shannon divergence that vanishes exactly when P = Q. The sequential test stops at the first n when some score is at most f(n), with f(n) decaying like (K+1)|\\mathcal{X}| \\log(n\\$\\alpha$+2)/n + K|\\mathcal{X}|\\log(n\\$\\beta$+2)/n, and then applies the minimal-scoring decision rule. The proof of the exact exponent uses type-class bounds on the probability that a competitive score is small, together with the variational form of the Renyi divergence, \\$\\alpha$ D_{\\$\\beta$/(\\$\\alpha$+\\$\\beta$)}(Q\\|P) = \\min_{V} [\\$\\alpha$ D(V\\|P) + \\$\\beta$ D(V\\|Q)]. The converse uses the data processing inequality for KL divergence and Doob's optional stopping theorem to upper bound any test's mismatch exponent.","core_discovery":"For the case of known number of matches, Theorem 1 establishes the exact large-deviation performance of sequential tests that satisfy expected stopping time universality: any such test has mismatch exponent at most Es(l, K, P, Q), and the sequential test that stops when a generalized Jensen-Shannon score falls below a slowly decaying threshold, then decides by the minimal score, achieves this exponent. The exponent is a min over alternative matchings of a sum of scaled Renyi divergences between the matched distributions that differ between the alternative and the true matching. For the unknown number of matches case, Theorem 3 bounds the achievable exponents of a sequential test in terms of three parameters (lambda1, lambda2, lambda3), showing a tradeoff between mismatch, false reject, and false alarm rates, and Theorem 5 provides a one-step fixed-length test that achieves the same false alarm and Bayesian exponents as the earlier two-step test, with a simpler procedure.","pith_inferences":["The exact exponent formula Es suggests a natural family of testable predictions: for fixed alpha and beta, the worst-case alternative matching is the one that maximizes the additive Renyi cost, a structure reminiscent of a shortest-path or cost-geometry problem.","One could extend the analysis to continuous alphabets by replacing the empirical type scoring with kernel-based divergence estimates, though the type-counting steps would need reworking.","The parameter tradeoff in the unknown-K setting (lambda1 versus lambda2, lambda3) could be optimized per distribution family, yielding a distribution-dependent operating point that the current theorem only bounds.","A converse for the unknown-K case, which the paper leaves open, might take the form of a matching lower bound on the product of exponents; if it holds, the three-error tradeoff would be tight."],"forward_implications":["Optimal sequential tests strictly improve the mismatch exponent over fixed-length tests, revealing the benefit of sequentiality in statistical sequence matching.","Specializing to statistical classification (M2 = K = 1) yields exact large deviations for sequential classification, recovering the binary classification result as a special case.","In the unknown-parameters setting, the proposed sequential test provides larger Bayesian exponent under each non-null hypothesis while achieving the same false alarm exponent as the two-step fixed-length test.","The exponent formula is monotone in both block-length ratios alpha and beta, approaching alpha D(Q_j || P_i) as beta tends to infinity, so the improvement from additional samples saturates.","The one-step fixed-length test eliminates the separate match-count estimation phase of prior fixed-length tests without hurting the achievable exponents."],"supporting_citations":[{"why":"Initiates the statistical sequence matching problem and gives the fixed-length asymptotically optimal test that this paper generalizes to the sequential setting.","marker":"[9]"},{"why":"Provides the fixed-length test and exponents for known and unknown number of matches that serve as the comparison baseline and the starting point for the sequential extension.","marker":"[10]"},{"why":"Supplies the expected stopping time universality framework and the variational form of Renyi divergence used in the converse and in the exponent computation.","marker":"[6]"},{"why":"Defines Renyi divergence, whose variational representation carries the exponent expression in the main theorem.","marker":"[14]"}],"fun_headline_variants":["Sequential matching tests beat fixed-length error exponents","Exact mismatch exponent for sequential tests","Sequential tests achieve larger mismatch exponent","Better error exponents via sequential sequence matching"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole analysis assumes that each sequence is generated i.i.d. from a distinct unknown distribution on a finite alphabet and that a pair is matched if and only if the underlying distributions are identical; if distributions can be close but not equal, or if sequences are not i.i.d., the stated exponents no longer apply.","fun_headline_variants_meta":{"raw":{"variants":["Sequential matching tests beat fixed-length error exponents","Exact mismatch exponent for sequential tests","Sequential tests achieve larger mismatch exponent","Better error exponents via sequential sequence matching"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000595,"raw_usage":{"total_tokens":2846,"prompt_tokens":1068,"completion_tokens":1778,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":684,"completion_tokens_details":{"reasoning_tokens":1725}},"tokens_in":684,"tokens_out":1778,"duration_ms":14290,"temperature":1.0,"reasoning_tokens":1725,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:50:27.993579+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a binary alphabet, set α = β = 1, M1 = M2 = 2, K = 1, with P1 = Q1 = Bern(0.2) as the true match and the alternative pair Q2 = Bern(0.8). Compute Es = D_{1/2}(Bern(0.8) || Bern(0.2)) and simulate the proposed sequential test with large N; if the empirical decay rate of the mismatch probability falls decisively below Es, the theorem's achievability claim is false.","supporting_citations":[{"cited_title":"Asymptotically optimal matching of multiple sequences to source distributions and training sequences,","cited_arxiv_id":null,"evidence_quote":"Initiates the statistical sequence matching problem and gives the fixed-length asymptotically optimal test that this paper generalizes to the sequential setting."},{"cited_title":"Large and small deviations for statistical sequence matching,","cited_arxiv_id":null,"evidence_quote":"Provides the fixed-length test and exponents for known and unknown number of matches that serve as the comparison baseline and the starting point for the sequential extension."},{"cited_title":"On universal sequential classification from sequentially observed empirical statistics,","cited_arxiv_id":null,"evidence_quote":"Supplies the expected stopping time universality framework and the variational form of Renyi divergence used in the converse and in the exponent computation."},{"cited_title":"Rényi divergence and Kullback-Leibler divergence,","cited_arxiv_id":null,"evidence_quote":"Defines Renyi divergence, whose variational representation carries the exponent expression in the main theorem."}],"review_version":1}