{"id":"591b6f84-2373-4f12-99d1-90b9ee410196","arxiv_id":"2506.03294","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Building small BWTs and merging them into the whole BWT with prefix-free parsing cuts peak memory below direct PFP when the small datasets are mostly dissimilar.","lead":"The authors show that building and merging BWT indexes of small, distinct chunks of a huge dataset uses much less memory with prefix-free parsing than indexing the whole dataset directly. This could make pangenomic indexes feasible for terabyte-scale genome collections, though their method runs slower than alternatives and was tested on one dataset.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Merge correctness in §3/Fig. 2 assumes oldBWT per-phrase blocks are contiguous; BWT order is by following context, so sequential fread of occ(phrase) can mis-order characters even when each valid suffix is in one small dataset.","rationale":"The reader's weakest_assumption concerned dataset decomposition and the similarity condition. My concern is more fundamental: even under an ideal decomposition where every valid phrase suffix appears in exactly one small dataset, the merge step as described in §3/Fig. 2 may not reconstruct the correct BWT. The paper's proof counts occurrences but does not establish that the per-phrase blocks read from oldBWT are contiguous or correctly ordered. The BWT orders suffixes by their full following context; for a fixed valid suffix α appearing in multiple phrases, the small dataset's BWT interval for α can interleave characters from different phrases. A tiny parse (CACBCAC with trigger C) exhibits this: two phrases share the valid suffix C, and the Figure 2 procedure mis-copies characters, producing a shorter, wrong BWT. This is a concrete correctness gap in the central construction. I am not asserting the public implementation necessarily has this bug, because it may use a different internal representation than the pseudocode; but the paper as written does not provide the missing argument. The verdict should be UNVERDICTED pending the proposed test, because the claimed correctness of the memory-efficient merge is not established. If the test fails, the claim would need rejection; if it passes, the concern is resolved and the original conditional verdict could stand.","tokens_in":6211,"tokens_out":30484,"duration_ms":357291,"concrete_test":"Run the published pfp-merge on a single small input (or the synthetic text CACBCAC with w=1 and C as trigger) and compare the merged BWT to the BWT computed by bigbwt or by direct suffix sorting. If the outputs differ, Figure 2 is incorrect as written and the memory comparison in Table 1 does not demonstrate a correct merging algorithm.","verdict_should_be":"UNVERDICTED","load_bearing_attack":"Section 3's Figure 2 is the core of the claimed memory reduction: for each valid phrase suffix in the concatenated dictionary, it reads occ(phrase) characters from the corresponding small dataset's oldBWT and appends them to the output. The correctness proof only argues that the total number of characters for a suffix α is the sum of occ(β) over phrases β ending with α; it never proves that those occ(β) characters form a contiguous block in oldBWT. In a BWT/eBWT, the characters preceding the same α are ordered by the suffixes following α, i.e., by the context after the phrase, not by phrase identity. Two distinct phrases within the same small dataset can end in the same valid suffix α (the paper's 'exactly one small dataset' condition does not forbid this); then their occurrences are interleaved in oldBWT by next-phrase suffix order. Copying per-phrase blocks from a raw oldBWT therefore outputs the wrong characters/order. Example: text CACBCAC, w=1, trigger C gives phrases CAC and CBC with shared valid suffix C; applying Fig. 2 to the dataset's own BWT yields a 6-char string 'CABA$C' instead of the true 8-char BWT 'CABA$CCC'. The merge algorithm is thus not established even under the ideal similarity assumption.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a memory-reduction strategy for building the BWT of very large repetitive datasets with prefix-free parsing (PFP). The idea is to split the dataset into smaller, mutually dissimilar datasets, build a BWT for each small dataset with PFP, and then merge these BWTs into the BWT of the whole dataset. The merge is described in Section 3 through a code fragment (Figure 2) that copies, for each valid phrase suffix, a block of characters from the appropriate small dataset's BWT. The paper reports a single experiment on 9.39 GB of bacterial pangenomes, where pfp-merge peaks at 0.91 GB, far below plain PFP (bigbwt, 13.84 GB) and competitive with grlBWT (1.71 GB). The central correctness claim is that, under a heuristic condition that most w-mers appear in only one small dataset, each valid phrase suffix appears in exactly one small dataset, so copying the corresponding BWT characters yields the whole BWT.","tokens_in":6474,"tokens_out":9082,"duration_ms":113925,"significance":"If the merge procedure were correct, the paper would describe a practically attractive way to extend PFP's low-memory construction to datasets that are not repetitive enough for recursive PFP. The experimental result is striking: a 15x reduction in peak memory compared with plain PFP on a real 9.39 GB collection. The paper is also clearly written and makes its code and data available. These strengths are real, and the proposed direction of building small BWTs and merging them is worth pursuing. However, the correctness of the central algorithm is not established, and there is a concrete failure mode even under the paper's own 'not very similar' assumption. Because the contribution is the merge algorithm itself, this flaw is load-bearing.","major_comments":[{"comment":"The proof of correctness for the merge loop counts characters but never proves that the occ(SAD[i]) characters belonging to a given phrase are contiguous in oldBWT[DS(SAD[i])]. In a BWT/eBWT, the characters preceding the same valid phrase suffix α are ordered by the suffix following α; for occurrences at the end of a phrase, that suffix includes the following phrase, not the phrase identity. Two phrases ending with the same α can therefore interleave their occurrences in oldBWT, and the fread of occ(SAD[i]) characters copies the wrong context. A concrete failure occurs on text CACBCAC with w=1 and trigger string C: the phrases CAC and CBC share the valid suffix C, yet Figure 2, applied to the BWT of that single dataset, produces a string of length 6 instead of the true BWT of length 8. Thus the central claim of Section 3 is not established even under the ideal assumption that every valid phrase suffix appears in exactly one small dataset.","section":"§3, Figure 2"},{"comment":"The decomposition condition is informal: no algorithm or validation test is given for checking that most w-mers appear in only one small dataset, and the statement that w=20 is 'usually enough' is anecdotal. More importantly, the condition as stated is insufficient: the counterexample above satisfies the condition (the only valid suffix C appears in exactly one small dataset), yet the merge loop is still incorrect. A revised paper would need to either prove a formal condition under which the per-phrase blocks in oldBWT are contiguous, or replace the extraction step with a correct procedure that uses, for example, suffix-array intervals and rank/select operations.","section":"§3, 'not very similar' condition"},{"comment":"The experimental section reports peak memory and time on a single 9.39 GB collection, but does not report any verification that the BWT produced by pfp-merge is identical to the BWT of the whole dataset. Given the flaw in Figure 2, the experiment cannot currently be interpreted as evidence for correctness of the merging procedure. At minimum, the paper would need a differential test against bigbwt on the same input, and ideally on multiple datasets with varying degrees of similarity, together with a precise description of what the implementation actually does if it differs from Figure 2.","section":"§4, Table 1"}],"minor_comments":[{"comment":"The text refers to 'Masillo's CMT-BWT' in the experiments, while Section 1 calls it 'CMS-BWT'; the tool name should be reconciled.","section":"§4"},{"comment":"The table uses 'glrbwt' while the text and repository name use 'grlbwt' (or 'grlBWT'); the spelling should be unified.","section":"Table 1"},{"comment":"The abstract has formatting issues in the PDF text, including missing spaces such as 'Whenbuilding'; this should be corrected in the camera-ready version.","section":"Abstract"},{"comment":"The claim that storing dictionaries instead of SAD reduces space 'by about 4 or 8' depends on the suffix-array entry size and the dictionary encoding; the statement should be qualified more precisely.","section":"§3, streaming SAD"}],"recommendation":"reject","confidential_remarks":"The paper is well-written and addresses a timely problem, but the proposed merge algorithm appears to be incorrect as described. The counterexample is small and falls squarely within the paper's stated assumptions, so the issue is not a missing edge case but a fundamental gap in the correctness argument. I would encourage the authors to revisit the extraction step: if their implementation actually uses additional data structures to locate per-phrase intervals in oldBWT, that information should be disclosed and proved. With a corrected algorithm and a proper validation of the merged BWT, the idea could become a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nYou should know that the merge algorithm in §3, Figure 2, is not correct as written. The proof assumes that for a phrase β ending with a valid phrase suffix α, the occ(β) characters preceding α in the small dataset's BWT form a contiguous block. They don't. The BWT orders all characters preceding α by the suffix that follows α—which is the suffix starting after the phrase—and occurrences of β are interleaved with those of other phrases that also end with α. The counterexample in the stress-test note is sound: with text CACBCAC, w=1, trigger C, the code fragment produces a 6-character string instead of the true 8-character BWT. So the central claim—that you can merge small BWTs by copying per-phrase blocks—is not established.\n\nThat's a shame because the paper starts from a real pain point: PFP's memory blows up on AllTheBacteria and the 231-genome HPRC. The idea of decomposing the dataset into pieces that share few w-mers, building their BWTs, and merging them is natural and potentially useful. The engineering details are nice too: the 3-bit dictionary encoding, the streaming suffix-array merge, the min-heap note. The paper is clearly written, and the code is public.\n\nBut the flaws are load-bearing. The per-phrase block copy is wrong. The similarity condition is heuristic—'most w-mers appear in only one small dataset'—and w=20 is asserted without support. There is one experiment, no repeated runs, and no output validation; the reported memory numbers are interesting but not meaningful evidence for an algorithm that is described incorrectly. The method is also slower than grlBWT and bigbwt, so the only selling point is the low memory peak.\n\nWhat might work: if the merge step copies whole α-blocks from the appropriate small BWT (since each α appears in only one small dataset), then the order within the block is already correct. That would require a different code fragment and a different proof. The authors may have done something like that in the implementation; the paper should say.\n\nMy take: the idea is worth pursuing, but this version isn't ready. The authors need to fix the correctness argument (or the algorithm), add a real validation of the output, and specify what the similarity condition requires. I'd send it to review, because a serious referee could push them in the right direction, but I wouldn't accept it as is.\n\nBest regards.","headline":"The merge algorithm in §3 is incorrect as written: the BWT interleaves characters from different phrases that share a suffix, so per-phrase block copies don't produce the right order.","tokens_in":7039,"tokens_out":5770,"would_cite":false,"duration_ms":67407,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that building and merging BWTs of small, mutually dissimilar subdatasets lets prefix-free parsing index huge collections in a fraction of the memory, with a 9.39 GB bacterial collection handled in under a gigabyte.","keywords":["Burrows-Wheeler Transform","prefix-free parsing","BWT merging","low-memory algorithms","pangenomics","repetitive text indexing","extended BWT"],"falsifier":"Run pfp-merge on a dataset whose pieces share many w-length substrings, such as genomes of the same species split across pieces: if a substantial fraction of valid phrase suffixes appear in more than one small dictionary, the output BWT will be wrong or peak memory will approach plain PFP. A direct check is to count, for a proposed split with w=20, how many valid phrase suffixes occur in more than one small dataset; if that count is not near zero, the central claim fails for that split.","tokens_in":6023,"feed_emoji":"🧬","tokens_out":6907,"duration_ms":67120,"temperature":0.7,"pith_summary":"The paper proposes a memory-saving way to build the Burrows-Wheeler Transform (BWT) of a very large dataset that can be split into small, mutually dissimilar pieces, such as genomes grouped by species or by chromosome. Instead of parsing the entire dataset at once, the method builds the BWT of each small piece and then merges those BWTs into the BWT of the whole dataset. This avoids storing a single huge parse and dictionary, which is what makes plain PFP memory-hungry on terabyte-scale pangenomes. The authors demonstrate the approach on 9.39 GB of bacterial genomes, where their tool peaked at 0.91 GB, compared with 13.84 GB for standard PFP and 1.71 GB for the next-best tested tool.","feed_headline":"Merging small BWTs cuts PFP memory from 13.8 GB to 0.9 GB","feed_subtitle":"Build each piece's BWT separately, then merge by phrase-suffix order; a 9.39 GB bacterial collection is indexed in 0.91 GB peak.","key_machinery":"The load-bearing object is the valid phrase suffix: in a prefix-free parse, phrases start and end with trigger strings of length w, and any proper phrase suffix of length at least w is valid. PFP's correctness rests on the fact that no valid phrase suffix is a proper prefix of another, so the lexicographic order of valid phrase suffixes determines the BWT order of the characters that precede them. The merging algorithm scans these suffixes, looks up the phrase ending at each suffix, its total occurrence count, and the small dataset that owns it, then copies that many characters from the corresponding small BWT into the output. Supporting tables and streaming of the small dictionaries' suffix arrays keep the memory footprint down.","core_discovery":"The central discovery is that the piecewise BWTs can be merged by scanning valid phrase suffixes in lexicographic order, rather than by aligning the pieces. After removing trigger strings that appear in more than one small dataset, every valid phrase suffix appears in exactly one small dataset, so the characters preceding that suffix in the whole BWT are all in one small BWT and keep their relative order. A single pass over the suffix array of the concatenated dictionaries, copying blocks of characters equal to each phrase's occurrence count from the appropriate small BWT, therefore produces the BWT of the whole dataset. This bypasses the large parse and dictionary that plain PFP would need for the entire collection.","pith_inferences":["The reported 0.77 GB used by the merging phase itself suggests the memory advantage will grow with the number of groups: adding pieces adds tables, not another full-size parse.","The merge could be combined with other BWT construction algorithms for the small pieces, potentially inheriting their speed while keeping the lower memory of this approach.","The same unique-phrase-suffix idea could extend to other parse-based indexes, such as r-index-style structures or Wheeler graphs, making piecewise construction a general pattern for repetitive pangenomes.","A practical deployment would need an automatic way to find a valid decomposition and to verify that w=20 is sufficient; without that, the approach remains heuristic."],"forward_implications":["Collections of genomes grouped by species or chromosome can be indexed with PFP in memory close to the size of one group's dictionary rather than the whole collection's parse.","The memory during the final merge is dominated by the suffix array of the concatenated dictionaries, which can be streamed from disk, so datasets beyond the reach of plain PFP become tractable.","The algorithm can be parallelized by starting each small suffix array at an interior position, sharing the static dictionaries and tables across threads without proportionally increasing memory.","When queries only involve {A,C,G,T}, storing dictionaries in 3 bits per character keeps phrase-suffix comparisons fast, making the approach practical at scale."],"supporting_citations":[{"why":"Introduces prefix-free parsing and its correctness, the construction that the merging method extends.","marker":"[5]"},{"why":"Describes grlBWT, the strongest memory baseline in the experiment.","marker":"[7]"},{"why":"Shows recursive PFP, which the authors cite as failing on datasets not repetitive enough, motivating the merge approach.","marker":"[9]"},{"why":"Provides the AllTheBacteria resource, the source of the 30 genomes used in the experiment.","marker":"[16]"},{"why":"Reports BWT construction at terabase scale and is cited as the attempt that ran out of memory on AllTheBacteria, motivating the memory reduction.","marker":"[18]"},{"why":"Defines the extended BWT (eBWT), the notion that justifies keeping per-piece character order during the merge.","marker":"[21]"},{"why":"Describes the Lyndon-grammar BWT construction (lg) used as another baseline in the experiment.","marker":"[23]"}],"fun_headline_variants":["Merging small BWTs slashes PFP memory from 13.8 to 0.9 GB","Piecewise BWT merge: no giant parse, peak RAM under 1 GB","Index 9.4 GB of genomes with 0.91 GB by merging BWT pieces","Dissimilar pieces allow BWT merge, cutting PFP memory by 15x","Build small BWTs, merge by phrase order—PFP memory drops to <1 GB"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The dataset can be split into small pieces that are almost mutually dissimilar, so that nearly every w-length substring occurs in only one piece; otherwise the merge cannot assign each valid phrase suffix to exactly one small BWT and the memory benefit collapses.","fun_headline_variants_meta":{"raw":{"variants":["Merging small BWTs slashes PFP memory from 13.8 to 0.9 GB","Piecewise BWT merge: no giant parse, peak RAM under 1 GB","Index 9.4 GB of genomes with 0.91 GB by merging BWT pieces","Dissimilar pieces allow BWT merge, cutting PFP memory by 15x","Build small BWTs, merge by phrase order—PFP memory drops to <1 GB"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000513,"raw_usage":{"total_tokens":2412,"prompt_tokens":783,"completion_tokens":1629,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":399,"completion_tokens_details":{"reasoning_tokens":1512}},"tokens_in":399,"tokens_out":1629,"duration_ms":16652,"temperature":1.0,"reasoning_tokens":1512,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:07:33.961488+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run pfp-merge on a dataset whose pieces share many w-length substrings, such as genomes of the same species split across pieces: if a substantial fraction of valid phrase suffixes appear in more than one small dictionary, the output BWT will be wrong or peak memory will approach plain PFP. A direct check is to count, for a proposed split with w=20, how many valid phrase suffixes occur in more than one small dataset; if that count is not near zero, the central claim fails for that split.","supporting_citations":[{"cited_title":"Algorithms for Molecular Biology14, 1–15 (2019)","cited_arxiv_id":null,"evidence_quote":"Introduces prefix-free parsing and its correctness, the construction that the merging method extends."},{"cited_title":"Information and Computation294, 105088 (2023)","cited_arxiv_id":null,"evidence_quote":"Describes grlBWT, the strongest memory baseline in the experiment."},{"cited_title":"iScience27(10) (2024)","cited_arxiv_id":null,"evidence_quote":"Shows recursive PFP, which the authors cite as failing on datasets not repetitive enough, motivating the merge approach."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the AllTheBacteria resource, the source of the 30 genomes used in the experiment."},{"cited_title":"Bioinformatics40(12), btae717 (2024)","cited_arxiv_id":null,"evidence_quote":"Reports BWT construction at terabase scale and is cited as the attempt that ran out of memory on AllTheBacteria, motivating the memory reduction."},{"cited_title":"Theoretical Computer Science387(3), 298–312 (2007)","cited_arxiv_id":null,"evidence_quote":"Defines the extended BWT (eBWT), the notion that justifies keeping per-piece character order during the merge."},{"cited_title":"arXiv (2025)","cited_arxiv_id":null,"evidence_quote":"Describes the Lyndon-grammar BWT construction (lg) used as another baseline in the experiment."}],"review_version":1}