{"id":"4648b282-8d85-433e-ab83-ef34fcff7567","arxiv_id":"2608.01387","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A suffixient-set based index finds maximal exact matches in O(rho_P log m) time plus constant per suffix-tree edge, using O(rho_T + chi) space, when both text and pattern are run-length compressed.","lead":"This paper gives a compressed index that finds maximal exact matches between a highly repetitive text and a run-length-compressed pattern in time proportional to the number of runs in the pattern. The result is aimed at fast haplotype and pangenome queries, a routine bottleneck in bioinformatics.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3 proof is deferred; central O(rho_P log m) query bound rests on unverified z-fast trie construction.","rationale":"The reader's weakest assumption pinpoints Lemma 3, and the manuscript explicitly leaves its proof to the full version. My reading confirms that this lemma is the linchpin of the claimed query time: the Section 3 algorithm queries it at each run-boundary mismatch, and the O(rho_P log m) bound follows only if each such query costs O(log m). The paper also defers parts of Theorem 4's details, but the main unverified step is Lemma 3. There are no obvious internal contradictions; the approach is plausible given prior z-fast trie work, but as written the central theorem is not independently checkable. Therefore the existing CONDITIONAL verdict remains appropriate, and I do not recommend changing it.","tokens_in":98,"tokens_out":2809,"duration_ms":34705,"concrete_test":"Obtain or independently prove Lemma 3: construct the modified z-fast trie over the set of reversed prefixes of T ending at each position in a smallest suffixient set, using the RL hashes from Lemma 2. Prove that for any prefix of P, the longest common suffix with a stored reversed prefix can be found in O(log m) time after O(rho_P) preprocessing, with O(chi) space. If the proof requires omega(log m) time or omega(chi) space, or needs Omega(m) preprocessing, Theorem 4's complexity must be revised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 4) depends on Lemma 3, which states that a modified z-fast trie over reversed prefixes of T ending at suffixient positions can, after O(rho_P) preprocessing of P, return the longest common suffix of any prefix of P with one of those reversed prefixes in O(log m) time and O(chi) space. The proof of Lemma 3 is explicitly deferred to the full version (Section 2: 'whose proof we leave to the full version'). The algorithm in Section 3 uses this subroutine to handle mismatches at run boundaries in P; without it, the O(rho_P log m) bound and even correctness of the left-to-right pass are not established. The right-to-left pass also has details deferred ('with some attention to details... full version'). Since no proof or implementation is provided, the paper does not currently substantiate its main theorem. This is not an internal inconsistency but an unverified dependency.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an index for finding maximal exact matches (MEMs) when both text T and pattern P are given in run-length compressed form. The main result (Theorem 4) claims O(rho_T + chi) space and O(rho_P log m) query time, plus a constant per suffix-tree edge descended, where rho_T and rho_P are the numbers of runs and chi is the size of a smallest suffixient set. The approach modifies Depuydt et al.'s suffixient-set index by introducing 'RL hashes' for run-length compressed strings and by using a modified z-fast trie over reversed prefixes at suffixient positions to answer longest-common-suffix queries. A further adaptation (Theorem 5) is claimed for set-maximal exact matches (SMEMs) in sparse haplotype panels, with space proportional to the number of 1s in the panel. The paper is clearly written and the motivation is sound, but several load-bearing proofs are deferred to a non-existent full version.","tokens_in":7139,"tokens_out":2762,"duration_ms":28135,"significance":"If the main theorem is correct, it is a meaningful contribution: it removes the O(m log sigma / log n) preprocessing cost of Depuydt et al.'s MEM index when the pattern is run-length compressed, which is relevant for pangenomic and haplotype applications where query patterns are sparse or highly repetitive. The SMEM adaptation targets an important bioinformatics problem. However, the significance is currently conditional: the central query-time bound rests on Lemma 3, whose proof is explicitly deferred, and on a right-to-left pass whose details are also deferred. The paper does not contain an implementation or experimental validation, which is not required for a theory paper, but it also does not contain complete proofs of its main claims.","major_comments":[{"comment":"Lemma 3 is the key subroutine that supplies the longest-common-suffix query used at run boundaries of P. Its proof is explicitly left to the full version ('whose proof we leave to the full version of this paper because z-fast tries are somewhat complicated'). Since Theorem 4 and the correctness of the left-to-right pass in Section 3 both depend on this lemma, the main query bound O(rho_P log m) is not substantiated by the submitted manuscript. The authors should provide a complete proof or a precise pointer to a verifiable published version; a statement of the lemma alone is not sufficient for the central claim.","section":"Section 2, Lemma 3"},{"comment":"The right-to-left pass is needed to turn the left-to-right matching-statistics information into the actual MEMs. The text says: 'With some attention to details that we will cover more thoroughly in the full version of this paper, this gives us the following theorem.' The details of this pass are load-bearing: they determine both correctness and the claimed O(rho_P log m) time (or O(rho_P) plus per-edge cost). As written, the proof of Theorem 4 is incomplete at this step.","section":"Section 3, right-to-left pass"},{"comment":"Theorem 5 is presented as the main application, but the entire adjustment of the Section 3 machinery to per-column tries and pointers is deferred: 'Adjusting the details of Section 3 appropriately gives us the following theorem. We defer the details of that adjustment to the full version of this paper.' The claimed space bound 'proportional to the number of 1s in M' and the query time bound therefore lack proof. This is especially problematic because the sparse-haplotype setting changes the data structures (per-column centroid decompositions, pointers for 1s) and the query semantics (SMEMs rather than MEMs), so the reduction is not automatic.","section":"Section 4, Theorem 5"}],"minor_comments":[{"comment":"The proof of Lemma 2 also leaves the detailed constant-time hash combination to the full version ('which we will describe in detail in the full version of this paper'). The sketch is plausible, but since the result is used by Lemma 3, including the explicit formulas for combining the three RL-hash pieces would improve self-containedness.","section":"Section 2, Lemma 2"},{"comment":"The sentence defining suffixient sets has a typo: 'it in some sense it is sufficient' should be 'it is in some sense sufficient'.","section":"Section 1"},{"comment":"The term 'edge we would fully or partially descend in the suffix tree for T' is used in Theorem 4 but not formally defined. In particular, it is unclear whether partially descended edges are counted per character or per suffix-tree edge, and whether this count is bounded independently of m.","section":"Section 3"},{"comment":"Reference [13] is cited as 'Personal communication, 2026.' This is not verifiable by the reader; if the jump index is described in an unpublished manuscript or technical report, that should be cited instead, or the relevant properties should be stated explicitly.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper's main theorem is stated as a fait accompli, but the two decisive algorithmic pieces — Lemma 3 and the right-to-left pass — are explicitly deferred to a full version. The SMEM theorem is also deferred entirely. This is a high-risk submission style for a journal. The overlap with coauthors' prior work (Depuydt et al. and Groot Koerkamp's jump index) is not itself a problem, as the claimed contribution is an extension, not a restatement. The editor should require that the full proofs be included in the revision before sending the paper to a second round of technical review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper before you read it: it has a genuinely useful idea for MEM-finding when both text and pattern are run-length compressed, but the main theorem is not actually proven in the text. The proof of Lemma 3, which is the load-bearing subroutine for the O(rho_P log m) query bound, is explicitly deferred to a nonexistent full version, and so are the right-to-left pass of Theorem 4 and the adjustment behind Theorem 5. What is new and good: the RL hash of Lemma 2 is a real contribution — preprocessing the run-length encoding of P in O(rho_P) time and then hashing any substring spanning run boundaries in constant time is plausible and useful on its own. The observation that mismatches can only occur at run boundaries in P or T is used well: the pointers from the start of runs in T to a previous position maximize the longest common suffix, and the z-fast trie over reversed prefixes at suffixient positions is a clean way to handle the P-side mismatches. The paper is also honest about what it is not proving; it explicitly flags the deferred parts rather than hiding them. That said, the soft spots are not minor. Lemma 3 is not a detail — without a proof that the modified z-fast trie supports O(log m) longest-common-suffix queries for prefixes of P in O(chi) space, the central O(rho_P log m) bound is unsupported. The right-to-left pass, which is what actually extracts the MEMs from the matching statistics, is only a sketch. And there is no implementation, so even the practical claims about SMEM finding are untested. This does not look like an internal contradiction; the architecture is coherent and the pieces could fit. But as a submitted paper it is an extended abstract, not a complete result. Who gets value from it: researchers working on suffixient sets, run-length compressed indexes, and pangenomic haplotype matching. The RL hash and the pointer scheme might be reused even if the main theorem changes. I would not cite the main bound in my own work until Lemma 3 has a real proof. For peer review: I would send it to referees because the idea is promising and the problem is relevant, but the verdict should be conditional — accept only if the full proofs are supplied and the missing details are checked. The paper deserves a serious referee, not because it is finished, but because the core idea may well be salvageable and the community would benefit from either a verified theorem or an explicit counterexample.","headline":"Nice idea for run-length compressed MEM-finding, but the main theorem currently rests on a deferred proof of the central subroutine.","tokens_in":7528,"tokens_out":2577,"would_cite":false,"duration_ms":27484,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W32","68P05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Run-length compressed patterns can be matched against compressed texts in time proportional to their number of runs rather than their length.","keywords":["maximal exact matches","MEM","run-length encoding","suffixient set","z-fast trie","Karp-Rabin hashing","set-maximal exact matches","haplotype indexing"],"falsifier":"Build the Lemma 3 data structure for a text with a known suffixient set and query it with all prefixes of a run-compressed pattern, counting trie nodes and hash operations per query. Any prefix that requires more than $O(\\log m)$ such operations, or any data structure exceeding $O(\\chi)$ space after $O(\\rho_P)$ preprocessing, would falsify the theorem. A concrete stress test is a de Bruijn-like highly repetitive text with small $\\chi$ and patterns with many short runs.","tokens_in":6797,"feed_emoji":"🧬","tokens_out":8164,"duration_ms":72031,"temperature":0.7,"pith_summary":"This paper claims that maximal exact matches (MEMs) of a run-length encoded pattern against a run-length encoded text can be found without processing the pattern character by character. The proposed index stores a text $T$ with $\\rho_T$ runs in $O(\\rho_T + \\chi)$ space, where $\\chi$ is the size of the smallest suffixient set of $T$, and answers a query pattern $P$ with $\\rho_P$ runs in $O(\\rho_P \\log m)$ time plus constant time for each edge of $T$'s suffix tree that the search would descend. If the claim holds, MEM search on repetitive texts such as pangenomes and haplotype panels can depend on the number of runs, which is often much smaller than the length of the pattern. The same machinery adapts to set-maximal exact matches (SMEMs) between a query haplotype and a sparse haplotype panel, using space proportional to the number of 1s in the panel.","feed_headline":"MEM search scales with a pattern's runs, not its length","feed_subtitle":"Run-compressed text indexing answers maximal exact matches in run-count time and extends to haplotype SMEMs.","key_machinery":"The argument rests on three components. RL hashing is a Karp-Rabin variant defined on the run-length encoding of a string, letting any substring delimited by two run-internal offsets be hashed in constant time after $O(\\rho_P)$ preprocessing. A suffixient set is a small set of text positions covering all suffix-tree branching edges; a modified z-fast trie stores the reversed prefixes of $T$ ending at those positions and answers longest-common-suffix queries in $O(\\log m)$ time. Run-boundary pointers in $T$ resolve mismatches at the start of runs in constant time by jumping to an earlier position whose prefix shares the longest common suffix.","core_discovery":"The central claim is Theorem 4: store $T$ in $O(\\rho_T+\\chi)$ space and, given $P$ with $\\rho_P$ runs, find all MEMs in $O(\\rho_P\\log m)$ time plus constant time for every suffix-tree edge fully or partially descended. The proof route replaces Karp-Rabin hashing by a run-length hash: after $O(\\rho_P)$ preprocessing, any substring of $P$ between two positions inside runs can be hashed in constant time. Mismatches at run starts in $T$ are handled by pointers from each run start to an earlier position with the longest common suffix, and mismatches at run starts in $P$ are handled by a modified z-fast trie over reversed prefixes of $T$ ending at suffixient positions, answering longest-common-suf","pith_inferences":["If the deferred proofs of Lemma 3 and the right-to-left pass hold as stated, the same run-boundary idea could be applied to variation graphs: long runs of 0/1 edges in a haplotype walk might be crossed in constant time using succinct representations of permutations and functions, rather than edge by edge.","The two-pass matching-statistics structure suggests the technique generalizes beyond MEMs to other statistics usually computed via suffix-tree walks, such as matching statistics or longest-common-prefix arrays for run-compressed inputs.","For bi-allelic panels with rare variants, the SMEM index should be tested against PBWT implementations on real genotype data; if query time indeed only charges columns with 1s, sparse queries will be nearly independent of panel width."],"forward_implications":["MEM queries on repetitive texts no longer require $O(m)$ or $O(m\\log\\sigma/\\log n)$ preprocessing per pattern; the cost is $O(\\rho_P\\log m)$ plus one constant-time step per suffix-tree edge visited.","The space bound $O(\\rho_T+\\chi)$ can be much smaller than $n$; since $\\chi\\le 2r$ and $\\chi\\le 2\\bar r$, it stays comparable to RLBWT-based indexes.","SMEM queries against sparse haplotype panels run in time proportional to the number of panel edges descended plus $\\sum_{Q[j]=1}(1+\\log \\sum_k M[k][j])$, with space proportional to the number of 1s in the panel.","The RL hash is a reusable primitive: it gives constant-time equality hashing for substrings of run-length compressed patterns without a near-linear preprocessing pass."],"supporting_citations":[{"why":"Introduces suffixient sets and the baseline MEM index that this paper modifies for run-compressed patterns.","marker":"[10]"},{"why":"Supplies z-fast tries, the data structure behind the modified longest-common-suffix query in Lemma 3.","marker":"[2]"},{"why":"Provides Karp-Rabin hashing, which the paper reworks into run-length hashing.","marker":"[14]"},{"why":"Introduces the PBWT and the SMEM problem framing for haplotype panels that Theorem 5 addresses.","marker":"[11]"},{"why":"Supplies the centroid decomposition of tries used to make per-column suffixient queries logarithmic in the number of leaves.","marker":"[3]"},{"why":"Gives the bound $\\chi \\le 2r$ that justifies comparing $O(\\rho_T+\\chi)$ space with run-length BWT indexes.","marker":"[17]"}],"fun_headline_variants":["MEM search speeds up with pattern runs, not size","Run-compressed indexing: MEMs in O(ρ_P log m) time","Focus on runs, not letters: faster MEM queries","Compact index + run-aware hashing = fast MEMs"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"Lemma 3 asserts that a modified z-fast trie over reversed prefixes of $T$ ending at suffixient positions can answer the longest-common-suffix query for any prefix of $P$ in $O(\\log m)$ time after $O(\\rho_P)$ preprocessing while using $O(\\chi)$ space, and the paper defers the proof to the full version; if that subroutine fails, the $O(\\rho_P\\log m)$ query time does not follow.","fun_headline_variants_meta":{"raw":{"variants":["MEM search speeds up with pattern runs, not size","Run-compressed indexing: MEMs in O(ρ_P log m) time","Focus on runs, not letters: faster MEM queries","Compact index + run-aware hashing = fast MEMs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000514,"raw_usage":{"total_tokens":2304,"prompt_tokens":687,"completion_tokens":1617,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":431,"completion_tokens_details":{"reasoning_tokens":1547}},"tokens_in":431,"tokens_out":1617,"duration_ms":11177,"temperature":1.0,"reasoning_tokens":1547,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T00:13:22.157508+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build the Lemma 3 data structure for a text with a known suffixient set and query it with all prefixes of a run-compressed pattern, counting trie nodes and hash operations per query. Any prefix that requires more than $O(\\log m)$ such operations, or any data structure exceeding $O(\\chi)$ space after $O(\\rho_P)$ preprocessing, would falsify the theorem. A concrete stress test is a de Bruijn-like highly repetitive text with small $\\chi$ and patterns with many short runs.","supporting_citations":[{"cited_title":"Fast prefix search in little space, with applications","cited_arxiv_id":null,"evidence_quote":"Supplies z-fast tries, the data structure behind the modified longest-common-suffix query in Lemma 3."},{"cited_title":"Efficient randomized pattern-matching algorithms","cited_arxiv_id":null,"evidence_quote":"Provides Karp-Rabin hashing, which the paper reworks into run-length hashing."},{"cited_title":"Efficient haplotype matching and storage using the positional Burrows– Wheeler transform (PBWT).Bioinformatics, 30(9), 2014","cited_arxiv_id":null,"evidence_quote":"Introduces the PBWT and the SMEM problem framing for haplotype panels that Theorem 5 addresses."},{"cited_title":"Cache-oblivious string B-trees","cited_arxiv_id":null,"evidence_quote":"Supplies the centroid decomposition of tries used to make per-column suffixient queries logarithmic in the number of leaves."},{"cited_title":"Smallest suffixient sets as a repetitiveness measure","cited_arxiv_id":null,"evidence_quote":"Gives the bound $\\chi \\le 2r$ that justifies comparing $O(\\rho_T+\\chi)$ space with run-length BWT indexes."}],"review_version":1}