{"id":"a20b840a-f0a3-4b95-84ba-f37038ac99ed","arxiv_id":"2608.10455","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Low-complexity fixed-length and sequential tests for statistical sequence matching are proven exponentially consistent, with explicit error exponents for discrete and continuous sequences.","lead":"This paper designs matching tests between two databases of sequences that run in polynomial time instead of exponential time, by scoring every pair and picking the most similar pairs. The tests are shown to be exponentially consistent, meaning errors shrink exponentially with sequence length, for both known and unknown numbers of true matches.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Continuous-sequence results in Theorems 1-4 inherit all key concentration and stopping-time bounds from unpublished self-cited preprint [8]; until those bounds are independently verified or stated in full, the central exponential-consistency claim for continuous data is conditional.","rationale":"The reader's weakest-assumption analysis correctly identifies the reliance of the continuous-sequence results on the unpublished, self-cited preprint [8]. My read of the proof structure confirms that the dependency is not incidental: the fixed-length continuous proof (Theorem 1) uses [8] for the key two-sided MMD bound, and the sequential continuous proofs (Theorems 2-4) reuse [8] for both the concentration of matched-pair scores, the lower-tail bound for unmatched-pair scores, and the resulting stopping-time bounds. If any of these imported inequalities is invalid or has a different constant, the stated exponents and the bounded-expected-stopping-time conditions would need to be recomputed; the central claim of exponential consistency for continuous sequences would at least lose its current proof. This is exactly the kind of external dependence that justifies a conditional verdict rather than acceptance. I did not find a more load-bearing internal inconsistency. The discrete sequential-test discussion contains a secondary algebraic slip: setting λ = log K/(N-1)+g(N-1) makes K exp(-(N-1)(λ-g(N-1))) = 1, which does not by itself satisfy the sufficient condition K exp(-(N-1)(λ-g))/(1-exp(-(λ-g))) ≤ 1; a slightly larger λ of order (log K + log N)/(N-1) would be needed. This is repairable and does not change the asymptotic exponent, so it is not the primary reason for the conditional verdict. The absence of a converse is acknowledged by the authors and does not threaten the stated achievability claim. Therefore I agree with the reader that the paper should be accepted only conditionally, pending independent verification of the [8] concentration bounds or a self-contained derivation.","tokens_in":37311,"tokens_out":15264,"duration_ms":149218,"concrete_test":"Obtain the full version of [8] and have an independent researcher re-derive from McDiarmid's inequality (or from Hoeffding-type U-statistic bounds) the specific estimates used here: for X^n ~ P, Y^m ~ Q with n = ceil(αN), m = ceil(βN), |κ| ≤ Θ, verify P{MMD²_hat(X^n,Y^m) ≥ t} ≤ exp(-N min{α,β} t²/(64Θ²)) and the two-sided comparison bound P{MMD²_hat(X_i,Y_j) ≥ MMD²_hat(X_ȳ,Y_j̄)} ≤ exp(-N min{α,β} (MMD²(P_ȳ,Q_j̄))²/(128Θ²)). Then recompute Theorems 1-4 continuous exponents with the verified constant and check that all stopping-time geometric-series conditions still hold. If [8] is unavailable, the continuous claims should be explicitly marked as dependent on an unverified preprint.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's discrete-sequence proofs are essentially self-contained, but every continuous-sequence claim is carried by bounds imported from [8], an unpublished preprint submitted by the same author. In the proof of Theorem 1, equation (69) is asserted 'similarly to [8, Eq. (108), (121) and (124)]' and gives the single-pair mismatch bound for the MMD scoring function. In the proof of Theorem 2, the expected stopping-time bound for continuous data uses [8, Eq. (144)-(146)] and the mismatch bound uses [8, Eq. (158)-(159)]. The same two groups of inequalities are reused in the proofs of Theorems 3 and 4 for all continuous false-alarm, mismatch, and false-reject exponents, and in the stopping-time geometric-series conditions (e.g., Theorem 2 requires K exp(-(N-1)E(λ))/(1-exp(-E(λ))) ≤ 1). Thus, if [8]'s concentration inequalities are wrong, have different constants, or require extra conditions not stated here, the continuous parts of the central claim lack proof. The paper flags [8] as submitted, but it does not reproduce or independently derive the inequalities, leaving the reader unable to check the constants (e.g., 128Θ²) or the conditions on λ. This is load-bearing because the main theorem states unconditional exponential consistency for continuous sequences, while the proof's foundation is outside the paper and not verifiable from the submitted text.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies statistical sequence matching between two databases of i.i.d. sequences generated from unknown, distinct distributions. It proposes fixed-length and sequential tests based on pairwise scoring functions: the GJS divergence for discrete sequences and the MMD estimator for continuous sequences. The tests avoid exhaustive search over all K-match configurations, reducing complexity to polynomial in the number of sequences. For a known number of matches K, Algorithm 1 outputs the K pairs with smallest scores; Algorithm 2 adds a threshold-based stopping rule. For an unknown number of matches, Algorithm 3 thresholds all pairwise scores, and Algorithm 4 uses two thresholds, λ1 and λ2, to decide when to stop and which pairs to declare matched. The main results are Theorems 1–4, which assert exponential consistency and lower bounds on the mismatch, false-alarm, and false-reject exponents, together with bounded expected stopping time under stated conditions. Simulations illustrate the claimed computational advantage and the qualitative benefit of sequentiality.","tokens_in":37662,"tokens_out":6493,"duration_ms":64632,"significance":"If the results hold, this is a useful step toward practical statistical sequence matching: it replaces exhaustive search over an exponentially large collection of matchings with polynomial-time thresholding and sorting, while retaining exponentially decaying error probabilities. The discrete-sequence analysis is largely self-contained and uses standard method-of-types arguments, which is a strength. The paper also gives explicit exponent expressions and a fair number of numerical illustrations. The continuous-sequence results, however, are built on concentration and stopping-time inequalities imported from an unpublished, self-cited preprint; until those inequalities are independently stated and verified, the central continuous-consistency claims remain conditional. The paper honestly lists the absence of converse results as a limitation, but the title and abstract present the consistency statements without that qualification.","major_comments":[{"comment":"The continuous-sequence half of Theorem 1 rests on the single-pair bound PA{MMD2(X_i^{ξN}, Y_j^{χN}) ≥ MMD2(X_{\\bar i}^{ξN}, Y_{\\bar j}^{χN})} ≤ exp(-N min{α,β}(MMD2(P_{\\bar i}, Q_{\\bar j}))^2 / (128Θ^2)), which is asserted 'similarly to [8, Eq. (108), (121) and (124)]'. Since [8] is an unpublished preprint by the same author and the constants and conditions are not reproduced here, the claimed unconditional exponential consistency for continuous sequences cannot be checked from this manuscript. Please reproduce the McDiarmid-type derivation or state the imported result in full, including the exact role of the bounded kernel constant Θ and any additional conditions on the threshold λ.","section":"§V-A, Eq. (69)"},{"comment":"The expected-stopping-time and error-probability bounds for continuous sequences all import [8, Eq. (144)-(146)] and [8, Eq. (158)-(159)]. These inequalities are used to obtain the geometric-series conditions in Theorems 2 and 4, and they also feed into the continuous parts of Theorems 3 and 4. If those bounds are incorrect, have different constants, or require extra conditions not stated here, the positive-exponent claims for continuous sequences collapse. Because the dependence is load-bearing and the source is self-cited and only 'submitted', the authors should either provide self-contained proofs in an appendix or explicitly reformulate Theorems 1–4 as conditional on the inequalities in [8].","section":"§V-B and §VI-B, Eqs. (102), (105), (131)-(137), (194)-(208)"}],"minor_comments":[{"comment":"In Theorem 3, the false-reject exponent is written with η in Eq. (51) and in the proof at Eq. (130); according to Eqs. (7) and (9), η denotes false-alarm probability while ζ denotes false-reject probability. Please correct the notation consistently.","section":"§III-B, Theorem 3"},{"comment":"The geometric-series display appears to be missing a minus sign in the numerator exponent: it should read exp(-(N-1) E_s,c_A(λ,·)) / (1 - exp(-E_s,c_A(λ,·))), rather than the printed form in which exp(-(N-1)) is multiplied by the exponent.","section":"§V-B, Eq. (108)"},{"comment":"In the system model, the distinctness condition for the second database is printed as 'Q_j ≠ Q_j' for i ≠ j; it should read Q_i ≠ Q_j.","section":"§II-A"},{"comment":"In the comparison with [8, Theorem 1], the argument of Λ_K_A is written as (f^{M1}, g^{M2}) rather than (P^{M1}, Q^{M2}); the notation is inconsistent with the surrounding definitions.","section":"§III-B, Eq. (31)"},{"comment":"The caption refers to 'binary observed sequences' while the described simulation uses the alphabet {1,2,3} of size three. Please correct the caption or the simulation description.","section":"§III-B, Fig. 1(a)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's continuous-sequence results rely on a self-cited, unpublished preprint [8] for all key concentration bounds. This is both a verifiability concern and a citation-practice concern; the editor may wish to ask the authors to clarify the status of [8] or to provide the required bounds in an appendix. The discrete part of the paper is substantially self-contained and appears sound, so the appropriate route is a major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does something real: it replaces the exhaustive search over match sets in statistical sequence matching with a polynomial sort on pairwise scores, and it proves exponential consistency for that heuristic. That is a genuine step forward for the subfield. The discrete-sequence analysis, using the method of types with the GJS divergence, is self-contained and careful; the explicit exponents are credible, and the argument for positivity is sound. The sequential extensions and the unknown-K variants are natural, but working through the stopping-time bounds is real work. The paper is also honest that converses are open, and the simulations back up the claimed complexity saving.\n\nThe catch is the continuous-sequence side. Theorems 1 through 4 import the key MMD concentration and stopping-time bounds from [8], a preprint by the same author that is only marked \"submitted\" in the bibliography. The text cites it as if it were established, and the paper does not reproduce the inequalities or state their conditions. That is load-bearing: if [8]'s constants (e.g. the 128Θ^2) or its conditions on λ are wrong, the continuous claims have no proof in front of the reader. I would not call this a minor gap. The discrete half stands on its own; the continuous half is conditional.\n\nThere are also minor typos (η vs ζ for false reject in Theorem 3, a missing exponent in Eq. (108), a few notational slips). None of these affect the discrete argument, but they should be cleaned up.\n\nMy recommendation: this deserves a serious referee, not a desk reject. The main request should be to make the continuous section self-contained—state the MMD inequalities, prove them in an appendix, or explicitly condition the theorems on [8] until that preprint is public. With that fixed, it is a solid contribution to the sequence-matching literature; in the current form, the continuous claims are conditional on an unreliable footnote.","headline":"Discrete results are solid and the complexity story is real; the continuous claims ride on an unpublished self-cited preprint, so treat the headline as conditional until that is fixed.","tokens_in":38144,"tokens_out":3584,"would_cite":false,"duration_ms":34909,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A13","94A17","62F03","60F10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that low-complexity ranking tests match sequences with exponentially decaying errors, for discrete and continuous data and for known or unknown numbers of matches.","keywords":["statistical sequence matching","error exponent","large deviations","Jensen-Shannon divergence","maximum mean discrepancy","sequential test","low-complexity test","mismatch probability"],"falsifier":"For two Gaussians with known population MMD gap $\\Delta^2$, simulate the $K=1$ fixed-length test with $\\alpha=\\beta=1$ and the Gaussian kernel $\\sigma^2=1/2$; check that the empirical mismatch probability decays at least as fast as $\\exp(-N\\Delta^2/128)$. A slower decay violates the claimed exponent bound.","tokens_in":37107,"feed_emoji":"🔗","tokens_out":8569,"duration_ms":69561,"temperature":0.7,"pith_summary":"Statistical sequence matching asks which sequences in two databases were drawn from the same unknown distribution, a task that arises in database de-anonymization. This paper proposes tests that replace exhaustive search over all possible match sets with a simple rule: compute a pairwise score for every cross-database pair and take the K smallest scores (when K is known) or threshold the scores (when K is unknown). The paper proves these tests are exponentially consistent—their error probabilities decay exponentially in the sequence length with strictly positive exponents—for both discrete and continuous sequences. The discrete analysis uses the generalized Jensen–Shannon divergence and the method of types; the continuous analysis uses maximum mean discrepancy and McDiarmid's inequality. If correct, this makes sequence matching practical for database sizes where exhaustive search is impossible.","feed_headline":"Rank scores, not match sets: errors still drop exponentially","feed_subtitle":"New tests compare every pair of sequences once; error probabilities still decay exponentially with sequence length.","key_machinery":"The engine is a pairwise scoring function with an asymptotic zero-versus-positive separation: for discrete sequences it is the generalized Jensen–Shannon divergence $\\mathrm{GJS}(P,Q,\\alpha,\\beta)=\\alpha D(P\\|R)+\\beta D(Q\\|R)$ with $R=(\\alpha P+\\beta Q)/(\\alpha+\\beta)$, evaluated on empirical distributions and scaled by $1/N$; for continuous sequences it is the unbiased maximum mean discrepancy estimator with a bounded characteristic kernel, scaled the same way. The decision rule is deliberately simple—Algorithm 1 takes the K smallest scores, Algorithm 3 thresholds at $\\lambda$, and the sequential versions add stopping rules that wait until K scores fall below $\\lambda$ (known K) or until every pair is classified above $\\lambda_2$ or below $\\lambda_1$ (unknown K). The proofs then reduce to bounding the probability that an unmatched pair beats a matched pair on the scoring function, using the method of types for GJS and McDiarmid's inequality plus MMD concentration bounds for the continuous case.","core_discovery":"The central claim is that a fixed-length test that ranks all M1M2 pairwise scoring-function values and outputs the K smallest as the matched pairs is exponentially consistent whenever each database consists of distinct generating distributions. Theorem 1 lower-bounds the mismatch exponent by a strictly positive quantity for every allowed distribution tuple, for discrete sequences via the GJS scoring function and for continuous sequences via MMD. The paper further claims that a sequential version that stops once K scores fall below a threshold achieves a strictly larger mismatch exponent than the fixed-length version, and that both designs extend to the case of unknown K, where one threshold (or two thresholds in the sequential design) simultaneously estimates the number of matches and identifies them, with exponential control of mismatch, false reject, and false alarm probabilities. The price of not knowing K is quantified: for continuous sequences the best Bayesian exponent with unknown K is half the known-K mismatch exponent.","pith_inferences":["Editorial inference: the same 'score all pairs, then threshold' template should transfer to other combinatorial assignment problems, such as record linkage or graph alignment, where exhaustive enumeration of matchings is the main obstacle.","Editorial inference: the exponents are governed by the smallest separation between any unmatched pair and any matched pair, suggesting that a converse matching this min-gap quantity would show the ranking tests are optimal within the class of pairwise-score tests.","Editorial inference: because Theorems 2–4 for continuous sequences inherit their concentration inequalities from an unpublished source, a numerical audit of those MMD tail bounds—or an independent proof—would be the natural next step before relying on the continuous results."],"forward_implications":["With K known, the fixed-length test needs only $M_1M_2$ score computations and a sort, yet its mismatch probability decays exponentially in $N$ with a strictly positive exponent for every distinct-distribution tuple.","With K unknown, a single threshold $\\lambda$ yields simultaneously exponentially small false alarm, false reject, and mismatch probabilities whenever $\\lambda$ is smaller than the minimum pairwise score gap between unmatched distributions.","Sequential versions stop as soon as K scores fall below $\\lambda$ and are shown to have strictly larger mismatch exponents than the fixed-length versions under the same expected stopping time bound.","For continuous sequences, not knowing K halves the best Bayesian exponent relative to known K (in the MMD case), quantifying the cost of ignorance.","The exhaustive search baseline needs about $6.45\\times 10^{29}$ checks for $M_1=100$, $M_2=50$, $K=10$, while the new test uses about $2.5\\times 10^7$ operations."],"supporting_citations":[{"why":"Defines statistical sequence matching and provides the original fixed-length test whose exhaustive-search complexity this paper avoids.","marker":"[1]"},{"why":"Establishes the exhaustive-search benchmark for discrete sequences with known and unknown K, including the error-exponent framework adopted here.","marker":"[2]"},{"why":"Provides the sequential exhaustive-search test and stopping-time constraint that the proposed sequential tests are compared with.","marker":"[3]"},{"why":"Introduces the maximum mean discrepancy metric used as the continuous scoring function and its kernel two-sample interpretation.","marker":"[7]"},{"why":"Supplies the MMD concentration inequalities used in the continuous-sequence proofs and the continuous exhaustive-search benchmark.","marker":"[8]"},{"why":"Gives the variational form of the GJS divergence and the expected stopping time universality constraint used in the sequential design.","marker":"[14]"},{"why":"Proves that the MMD estimator in (19) is unbiased for the population MMD, the basis of the continuous scoring function.","marker":"[22]"},{"why":"The method of types underlies the discrete-sequence exponent calculations.","marker":"[24]"},{"why":"McDiarmid's inequality is the concentration tool that produces the MMD tail bounds for the continuous proofs.","marker":"[25]"}],"fun_headline_variants":["One-pass scoring: exponential error decay in sequence matching","Sequential tests tighten exponential error bounds in matching","Exponential consistency with linear complexity for sequence matching","Rank all pairs once: errors decay exponentially in matching","Score-based matching: exponential error control without search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The continuous-sequence proofs inherit their core tail bounds from an unpublished preprint by the same author; if those MMD concentration inequalities are wrong, the exponential-consistency claims for continuous sequences lose their foundation.","fun_headline_variants_meta":{"raw":{"variants":["One-pass scoring: exponential error decay in sequence matching","Sequential tests tighten exponential error bounds in matching","Exponential consistency with linear complexity for sequence matching","Rank all pairs once: errors decay exponentially in matching","Score-based matching: exponential error control without search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000231,"raw_usage":{"total_tokens":1484,"prompt_tokens":943,"completion_tokens":541,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":559,"completion_tokens_details":{"reasoning_tokens":468}},"tokens_in":559,"tokens_out":541,"duration_ms":4894,"temperature":1.0,"reasoning_tokens":468,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:20:58.149080+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For two Gaussians with known population MMD gap $\\Delta^2$, simulate the $K=1$ fixed-length test with $\\alpha=\\beta=1$ and the Gaussian kernel $\\sigma^2=1/2$; check that the empirical mismatch probability decays at least as fast as $\\exp(-N\\Delta^2/128)$. A slower decay violates the claimed exponent bound.","supporting_citations":[{"cited_title":"Asymptotically optimal matching of m ultiple sequences to source distributions and training seq uences,","cited_arxiv_id":null,"evidence_quote":"Defines statistical sequence matching and provides the original fixed-length test whose exhaustive-search complexity this paper avoids."},{"cited_title":"Large and sm all deviations for statistical sequence matching,","cited_arxiv_id":null,"evidence_quote":"Establishes the exhaustive-search benchmark for discrete sequences with known and unknown K, including the error-exponent framework adopted here."},{"cited_title":"Large Deviations for Sequential Tests of Statistical Sequence Matching","cited_arxiv_id":"2506.03976","evidence_quote":"Provides the sequential exhaustive-search test and stopping-time constraint that the proposed sequential tests are compared with."},{"cited_title":"A kernel two-sample test,","cited_arxiv_id":null,"evidence_quote":"Introduces the maximum mean discrepancy metric used as the continuous scoring function and its kernel two-sample interpretation."},{"cited_title":"Exponentially consistent tests for statistical sequence matching of continuous sequences,","cited_arxiv_id":null,"evidence_quote":"Supplies the MMD concentration inequalities used in the continuous-sequence proofs and the continuous exhaustive-search benchmark."},{"cited_title":"On universal sequenti al classification from sequentially observed empirical sta tistics,","cited_arxiv_id":null,"evidence_quote":"Gives the variational form of the GJS divergence and the expected stopping time universality constraint used in the sequential design."},{"cited_title":"A kernel two-sample test,","cited_arxiv_id":null,"evidence_quote":"Proves that the MMD estimator in (19) is unbiased for the population MMD, the basis of the continuous scoring function."},{"cited_title":"The method of types [information theory],","cited_arxiv_id":null,"evidence_quote":"The method of types underlies the discrete-sequence exponent calculations."}],"review_version":1}