{"id":"fc5446b0-cd1e-451a-9afb-52adaf1a213b","arxiv_id":"2411.12439","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Stable local consistency lets independently built locally consistent grammars be merged into one equivalent grammar, enabling LCG, a parallel compressor that handles 7.9 TB with 0.43 bits per symbol of working memory.","lead":"This paper introduces a parallel grammar-based compressor that handles terabyte-scale text, turning 7.9 TB of bacterial genomes into a representation 85 times smaller in about nine hours. The key idea, stable local consistency, lets separate chunks be parsed independently and then merged without re-synchronizing their parse trees.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central claim that MergeGrams reproduces BuildGram(Ta∪Tb) is unproven: the stated stability guarantee is weaker than Definition 1, and Theorem 3's proof omits equivalence.","rationale":"The reader's verdict of CONDITIONAL is appropriate: the experimental results are credible and the practical scale is novel, but the theoretical guarantee that parallel merging loses no compression is not rigorously proved. I partially agree with the reader's weakest assumption. The specific worry about context-dependent boundary phrases breaking MergeGrams may be too strong—the merge could still be correct if the invariant is proved inductively from terminal RHSs, without relying on the full stability definition. However, the paper does not provide such a proof, and the informal stability argument in §3.3.1 is indeed weaker than Definition 1. There is also a separate space-bound inconsistency in Theorem 2's proof (O(G logG) cannot be O(G log w) when w=Θ(log n) and G is large), which further signals that the theoretical sections are under-polished. Because the central merge-equivalence claim is load-bearing for the paper's main conceptual contribution, and it is asserted rather than demonstrated, the paper should remain CONDITIONAL pending either a rigorous proof or a targeted experimental verification of grammar equivalence on small instances.","tokens_in":21041,"tokens_out":18576,"duration_ms":178846,"concrete_test":"Run the released LCG implementation on small inputs in single-threaded mode: for each of many random pairs (Ta,Tb) with a shared pattern, compute M = MergeGrams(BuildGram(Ta), BuildGram(Tb)) and G = BuildGram(Ta∪Tb), and test whether M and G are isomorphic as grammars (same set of RHS strings over terminals, after canonical renaming of nonterminals at each level). A single mismatch is a counterexample to the equivalence claim; if all tests match, the practical claim passes but a proof is still required.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central theoretical assertion—that MergeGrams(Ga,Gb) is equivalent to BuildGram(Ta∪Tb,H)—is not established. Section 3.6 states the key invariant 'the right-hand sides of Ri_a and Ri_b are comparable' and asserts that Qa=Qb implies exp(Xa)=exp(Xb), but the proof of Theorem 3 only bounds time and space; it never shows that the merged rule set coincides with the sequential grammar. The only support for the invariant is the informal stability claim in §3.3.1, which is weaker than Definition 1: it requires the pattern occurrence to be 'surrounded by an identical context,' whereas Definition 1 promises identical core topologies for arbitrary contexts. If the invariant fails at any level—for example, when a common expansion is parsed into different phrase boundaries in Ta and Tb—the merge could match rules with equal RHS strings but unequal expansions, producing a grammar that generates strings outside Tab, or it could fail to merge duplicates that BuildGram would merge. A direct inductive proof that RHS equality at level i preserves expansions (from the base case of terminal RHSs) would fill the gap, but the paper does not provide it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes stable local consistency as a property of grammar-compression algorithms and uses it to design a parallel compressor, LCG. The main theoretical objects are BuildGram(T,H), which builds a locally consistent grammar in O(n) time w.h.p. using a shared set of hash functions, and MergeGrams(Ga,Gb), which merges two independently built grammars in O(Ga+Gb) time and O(Ga log ga + Gb log gb) space. The paper claims that the merged grammar is equivalent to the grammar BuildGram would produce on the union of the inputs. The experimental section reports that LCG compresses 7.9 TB of bacterial genomes in about nine hours with 16 threads and 0.43 bits/symbol of working memory, with compression ratios of 85x on ATB and up to 328x on COVID, and includes detailed comparisons with zstd, agc, RePair, and BigRePair.","tokens_in":21295,"tokens_out":16520,"duration_ms":167114,"significance":"If the equivalence theorem were established, this would be a significant contribution: it would provide the first grammar-compression method that scales to terabyte-sized collections with near-linear time and modest memory, and the stability concept would be of independent interest for parallel string processing. The experimental evidence is strong and transparent: Table 1 shows speed/memory/ratio for four competitors, Table 2 reports grammar-size statistics, Figure 4 gives time and memory breakdowns, and the implementation is released. The compression ratios are competitive, and the memory footprint is two to three orders of magnitude below that of RePair and BigRePair on the tested inputs. The main weakness is that the central theoretical equivalence is not proved; the current paper is therefore best read as a well-executed empirical demonstration plus an unproven theoretical framework.","major_comments":[{"comment":"The central claim that MergeGrams(Ga,Gb) is equivalent to BuildGram(Tab,H) is not proved. The proof of Theorem 3 only bounds the time and space of the merge operations; it never shows that the rule set of Gab coincides with, or is equivalent to, the rule set produced by BuildGram on the union, nor that the merged rules have the same expansions as the sequential ones. The 'comparable right-hand sides' invariant is stated in the first paragraph of Section 3.6 and is asserted to hold for i+1 after a merge round, but no inductive argument is given. In particular, the step from level i to i+1 requires showing that if a level-i RHS of Gb equals a level-i RHS of Ga after renumbering, then the corresponding nonterminals have identical terminal expansions; this is exactly the property that must be established, and the stability discussion in Section 3.3.1 only gives the weaker statement for occurrences 'surrounded by an identical context.' Without this proof, the merge could fail to identify rules that BuildGram(Tab,H) would identify, producing a larger grammar, or could merge rules with equal integer RHS but different expansions, producing a grammar that generates strings outside Tab. The proof must be supplied or the claim must be weakened.","section":"Section 3.6, Theorem 3"},{"comment":"Definition 1 promises that, for any pattern P appearing in two distinct texts, the independent executions ALG(Ta) and ALG(Tb) produce cores with identical topology. The only supporting argument is the sentence stating that if exp(T_i[ell]) appears in another collection T' different from T 'surrounded by an identical context,' then the breaks and core topology are identical. This condition is strictly weaker than the definition; it does not cover occurrences with different flanking contexts, which are exactly the cases that can arise in the merge scenario. Since the merge equivalence in Theorem 3 relies on this stability property, the paper needs either a rigorous proof that the hash-based LMS parsing is stable in the sense of Definition 1, or a formal statement of the weaker property that actually holds together with a proof that this weaker property suffices for the merge to be equivalent to BuildGram(Tab,H). As written, the property is asserted informally and is load-bearing for the paper's main theoretical claim.","section":"Section 3.3.1, Definition 1"},{"comment":"The experiments do not directly test the pair BuildGram/MergeGrams of Sections 3.3-3.6; they test PBuildGram, which uses a different variant of BuildGram with a read-only sink grammar and a merge tree (Section A.3). The correctness and equivalence of this parallel pipeline to BuildGram(Tab,H) is never stated as a theorem or proved. In particular, the modified BuildGram in Section A.2 assigns new metasymbols using s_a+s_b+1 and relies on the sink grammar's hash tables being read-only; the interaction between this variant and the MergeGrams equivalence is not analyzed. Since the experimental results are the paper's main evidence, the relationship between PBuildGram and the theoretical claims should be formalized.","section":"Sections A.2-A.3, PBuildGram"}],"minor_comments":[{"comment":"In the overview of MergeGrams, 'MergeGrams(Ga,Ga)' should read 'MergeGrams(Ga,Gb)'.","section":"Section 3.5"},{"comment":"Section 2.3 says the core of P has identical topology and labels, while Definition 1 says cores have identical topology and different nonterminal labels; please clarify whether the definition of core includes labels or only topology.","section":"Section 2.3 and Definition 1"},{"comment":"Theorem 2 states O(G log w) bits of working space, but the proof's last sentence claims O(G logG)+g logw+|H|w = O(G logw), which is not correct since O(G logG) dominates O(G logw) whenever logG is not O(log log n). The introduction and the proof both suggest the intended bound is O(G logG) bits; please correct the theorem statement and the algebra.","section":"Section 3.3, Theorem 2"},{"comment":"The proof of the O(n) time bound should make explicit that the sum of log|T_j| over the input strings is at most (n/nmax) log nmax, which is at most n for nmax at least 2; the current text jumps from a sum involving 2k log nmax to the conclusion O(n) without this inequality.","section":"Section 3.3, Theorem 2 proof"},{"comment":"Several citations to Nong et al. are inconsistent: Section 2.3 cites Nong et al. [29], Section 3.3 cites Nong et al. [22], and Section 3.3.1 cites Nong et al. [27]; references [22] and [29] do not correspond to the intended works by Nong, Zhang, and Chan. Please fix the citation numbers.","section":"References"},{"comment":"The experimental section does not report the threshold t or the fingerprint widths m_i used in the runs; please provide these parameters for reproducibility.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the missing proof of the merge equivalence and the discrepancy between the theoretical pipeline (BuildGram/MergeGrams) and the experimental pipeline (PBuildGram). If these can be fixed with a rigorous stability proof and a formal statement for PBuildGram, I would support acceptance. If not, the authors should clearly label the equivalence as a conjecture and present LCG as a heuristic; in that case the contribution would be weaker but still publishable in a more systems-oriented venue."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"LCG is the real deal on the practical side — genuinely the first grammar compressor demonstrated at terabyte scale — and the theory is under-proved but, as far as I can tell, correct.\n\nThe experiments carry the paper: 7.9 TB of bacterial genomes compressed in about nine hours with 16 threads and 0.43 bps of working memory, and it is the only grammar-based tool in the comparison that handled ATB and HUM at all. Table 2 and Figure 4 give a credible resource breakdown, and the paper is honest about losing on ratio to RePair and on memory to zstd. The genuinely new pieces are the stable-local-consistency framing and the merge-by-RHS algorithm; the code is public on GitHub. The enabling trick is real: fingerprinting full expansions means two independent runs agree on phrase boundaries without sharing nonterminal identifiers, which is what lets you merge grammars by matching right-hand sides.\n\nThe soft spots are where the reader puts them, with one correction. The stress test's failure scenario — equal RHS strings with unequal expansions, generating strings outside Tab — does not survive contact with the algorithm. The Section 3.6 invariant is bookkeeping: at level 1 the RHSs are terminals, so equal RHS means equal expansion, and the induction steps through the M remapping, which is defined by RHS matches. If a common expansion is parsed at different boundaries in Ta and Tb, the level-1 rules simply differ; higher levels then fail to match, and you get a larger grammar, not a wrong one. The paper omits the inductive step, which is annoying, but it is a page of work.\n\nThe genuine gap is stability itself. Definition 1 promises identical core topology for any pattern; the informal argument in Section 3.3.1 leans on 'identical context,' which is weaker than the definition. I believe the full claim is true w.h.p., because the fingerprint order is a total order on symbols that depends only on expansions, so the standard LMS local-consistency argument applies. But the paper never proves it, and the equivalence claim Gab = BuildGram(Tab,H) is asserted rather than demonstrated; Theorem 3's proof covers time and space only. Minor: Theorem 2 states O(G log w) for space, but the introduction says O(G log G) and the proof's own expansion is O(G log G) + g log w + |H|w. Also, all numbers are single runs, no error bars.\n\nWho this is for: the grammar-compression and string-algorithms community, and anyone compressing genome collections. It deserves a serious referee. Send it, and ask the author to write out the stability and merge-correctness proofs before acceptance.","headline":"A real terabyte-scale grammar compressor with an under-proved but likely correct theory; the merge invariant holds by induction, stability needs a written proof.","tokens_in":21785,"tokens_out":19350,"would_cite":true,"duration_ms":174164,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P30","68W10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Stable local consistency makes grammar compression parallel and scalable to terabytes.","keywords":["grammar compression","locally consistent parsing","stable local consistency","parallel compression","hash fingerprints","LMS parsing","grammar merging","terabyte-scale data"],"falsifier":"Take two strings that share a long pattern P but differ in flanks chosen to shift the LMS-type classification inside P; run BuildGram on each with the same H, then run MergeGrams. If the merged grammar is not equivalent to BuildGram over the concatenated collection — for instance if some rule expansion in the merged grammar is not a string of the collection — the stability property fails.","tokens_in":20793,"feed_emoji":"⚙️","tokens_out":5701,"duration_ms":57141,"temperature":0.7,"pith_summary":"The paper claims that grammar compression can be made parallel by a property it calls stable local consistency: if each independent chunk is parsed with the same set of hash functions, repeated substrings acquire cores with identical tree topology even though nonterminal names differ. It then shows a merge operation that matches rules by right-hand-side strings, producing a single grammar equivalent to one built over the whole collection. If these claims hold, the result is a grammar compressor that runs in linear expected time, uses working memory proportional to grammar size, and processed 7.9 TB of bacterial genomes in about nine hours on 16 threads, at 0.43 bits per symbol, with an 85x compression ratio. The paper positions this as making terabyte-scale grammar-based compression and downstream grammar-based string processing practical.","feed_headline":"Stable hashing makes grammar compression scale to terabytes","feed_subtitle":"Independent runs parse repeats identically, so chunk grammars merge losslessly and 7.9 TB compresses in ~9 hours.","key_machinery":"The load-bearing mechanism is stable local consistency, defined via the recursive polynomial fingerprints of Equation 2: each nontterminal's fingerprint is computed from the fingerprints of the symbols on its right-hand side, so two equal expansions get equal fingerprints regardless of the grammar in which they appear. BuildGram uses these fingerprints to classify positions as L/S/LMS types and induce breaks, generalising the suffix-sorting parsing of Nong et al. MergeGrams then matches rules level by level using the fingerprint-derived comparability of right-hand sides, discarding rules from one grammar whose expansion already occurs in the other.","core_discovery":"The central claim is that the stable property of BuildGram — that independent executions on different collections, given the same hash set H, produce cores with the same topology for every pattern — allows MergeGrams to combine grammars by matching right-hand sides rather than by synchronising nonterminal labels. The paper proves that MergeGrams(Ga,Gb) returns a locally consistent grammar for the union collection that is equivalent to BuildGram(Tab,H), runs in O(Ga+Gb) time with high probability, and uses O(Ga log ga + Gb log gb) bits of space. It also proves BuildGram runs in O(n) time with high probability and O(G log w) bits of working space. The experiments support the practical consequence: the implementation LCG compresses terabyte-scale collections with a speed between 232 and 506 MB/s, using 0.29–2.05 bits per symbol of memory, roughly an order of magnitude less memory than existing grammar compressors.","pith_inferences":["If stability holds without a common nonterminal label set, a collection could be parsed by different machines with different hash seeds and still be merged by comparing right-hand sides, as long as the seeds are shared; the paper only requires the same H, so this is an untested extension.","The merge cost is linear in grammar size rather than text size, which suggests that repeated merging (as in a streaming or distributed setting) adds only a small overhead; the paper's PBuildGram already does tree-shaped merges, so a more general distributed merge tree is a natural next step.","The empirical memory collapse from VByte keys suggests most of the reported working memory is phrase storage, not grammar structure; an inference is that an on-disk or more compact phrase store could bring working memory close to zstd levels while keeping grammar-based compression.","A testable consequence: if stability fails on low-entropy or highly repetitive boundaries (e.g., long runs of the same symbol where breaks are suppressed), the compression ratio would drop or the merged grammar would generate spurious strings; the paper avoids runs in the parsing, so the boundary handling is the spot to probe."],"forward_implications":["Grammar-based compression can be parallelised without loss: merging chunk grammars yields exactly the grammar the whole collection would have produced, so compression ratio does not degrade when many threads are used.","BuildGram's O(n) expected time and O(G log w) working space make it feasible to compress tens of terabytes on a single machine with modest memory.","The stability concept is not tied to the specific parsing: any locally consistent grammar that uses hashing to break text can be made stable in the same way.","Post-processing (run-length encoding of equal-symbol runs and removal of unique nonterminals) further shrinks the grammar, with Simp deleting more than 80% of nonterminals in the experiments.","The resulting grammar can be used as input to grammar-based string algorithms, potentially scaling MEM computation, BWT construction, and pattern matching to larger collections."],"supporting_citations":[{"why":"Supplies the LMS-based parsing that RandLMSPar adapts by substituting hash fingerprints for raw symbol comparisons.","marker":"[27]"},{"why":"Shows how locally consistent parsing can be turned into a grammar compressor via induced suffix sorting, the basis of BuildGram.","marker":"[29]"},{"why":"Provides the polynomial hash functions used to fingerprint grammar symbols and to make equal expansions hash equally.","marker":"[10]"},{"why":"Defines the core of a pattern, the object whose topology stability requires to be identical across independent runs.","marker":"[32]"},{"why":"Gives the classical definition of locally consistent parsing that the stable property extends.","marker":"[4]"},{"why":"Provides RePair, the standard grammar compressor used as the main compression-ratio baseline in the experiments.","marker":"[20]"},{"why":"Provides BigRePair, the competing scalable RePair variant whose resource usage and ratio are compared against LCG.","marker":"[12]"},{"why":"Proves that irreducible grammars reach kth-order empirical entropy, motivating the post-processing steps that shrink the grammar further.","marker":"[30]"}],"fun_headline_variants":["Stable grammar cores allow parallel merge: 7.9 TB in 9h","Parallel compression hits 85x on 7.9 TB via stable grammars","Stable grammar cores merge losslessly, compressing 7.9 TB in 9h","Stable local consistency enables parallel grammar merging at scale"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole parallel merge depends on the claim that two independent runs of the parser on different collections, using the same hash functions, will always give the same repeated substring the same internal phrase boundaries (the same core topology), no matter what surrounds it.","fun_headline_variants_meta":{"raw":{"variants":["Stable grammar cores allow parallel merge: 7.9 TB in 9h","Parallel compression hits 85x on 7.9 TB via stable grammars","Stable grammar cores merge losslessly, compressing 7.9 TB in 9h","Stable local consistency enables parallel grammar merging at scale"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000831,"raw_usage":{"total_tokens":3697,"prompt_tokens":1080,"completion_tokens":2617,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":696,"completion_tokens_details":{"reasoning_tokens":2532}},"tokens_in":696,"tokens_out":2617,"duration_ms":22295,"temperature":1.0,"reasoning_tokens":2532,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:32:33.602667+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take two strings that share a long pattern P but differ in flanks chosen to shift the LMS-type classification inside P; run BuildGram on each with the same H, then run MergeGrams. If the merged grammar is not equivalent to BuildGram over the concatenated collection — for instance if some rule expansion in the merged grammar is not a string of the collection — the stability property fails.","supporting_citations":[{"cited_title":"Practical linear-time O(1) -workspace suffix sorting for constant alphabets","cited_arxiv_id":null,"evidence_quote":"Supplies the LMS-based parsing that RandLMSPar adapts by substituting hash fingerprints for raw symbol comparisons."},{"cited_title":"Louza, Simon Gog, Mauricio Ayala-Rinc \\' o n, and Gonzalo Navarro","cited_arxiv_id":null,"evidence_quote":"Shows how locally consistent parsing can be turned into a grammar compressor via induced suffix sorting, the basis of BuildGram."},{"cited_title":"Polynomial hash functions are reliable","cited_arxiv_id":null,"evidence_quote":"Provides the polynomial hash functions used to fingerprint grammar symbols and to make equal expansions hash equally."},{"cited_title":"Symmetry breaking for suffix tree construction","cited_arxiv_id":null,"evidence_quote":"Defines the core of a pattern, the object whose topology stability requires to be identical across independent runs."},{"cited_title":"Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms","cited_arxiv_id":null,"evidence_quote":"Gives the classical definition of locally consistent parsing that the stable property extends."},{"cited_title":"Jesper Larsson and Alistair Moffat","cited_arxiv_id":null,"evidence_quote":"Provides RePair, the standard grammar compressor used as the main compression-ratio baseline in the experiments."},{"cited_title":"Rpair: Rescaling R e P air with rsync","cited_arxiv_id":null,"evidence_quote":"Provides BigRePair, the competing scalable RePair variant whose resource usage and ratio are compared against LCG."},{"cited_title":"RePair and all irreducible grammars are upper bounded by high-order empirical entropy","cited_arxiv_id":null,"evidence_quote":"Proves that irreducible grammars reach kth-order empirical entropy, motivating the post-processing steps that shrink the grammar further."}],"review_version":1}