{"id":"e87a4dcb-f9ae-4878-9f49-385521189c2a","arxiv_id":"1908.04933","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new algorithm computes Re-Pair, a grammar-based compression method, in O(n^2) time using roughly text-sized working space, but the core frequency-counting proof appears to overcount repeated-character bigrams.","lead":"This paper gives an algorithm that computes the Re-Pair grammar compressor in O(n^2) time while using only the space of the input text plus a small overhead, with variants for parallel and external-memory settings. The generalist might care because grammar compression is used to store repetitive data, and cutting the memory needed to build the grammar changes what can be compressed on ordinary machines.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.2 overcounts repeated-character bigrams, so the frequency table F can select the wrong most frequent bigram; Theorem 2.3 relies on it every round.","rationale":"Reader's weakest assumption matches mine. The central claim Theorem 2.3 is exactly: with max((n/c)lg n, n*lg(sigma_m))+O(lg n) bits, compute Re-Pair in O(n^2) time. The algorithm's only way to know which bigram to replace is the frequency table F, rebuilt by Lemma 2.2 at the start of each of O(lg n) rounds. If Lemma 2.2 can return a bigram that is not the most frequent under non-overlapping counting, the algorithm's replacement sequence is not Re-Pair's, so Theorem 2.3 is not established as written. The counterexample is simple and does not rely on exotic alphabets or machine details. The paper's own Sec. 3.1 (Case b=c) contains the correct run-based non-overlap counting for the bit-parallel variant, which indicates the issue is fixable rather than fatal to the overall program; but Lemma 2.2, the sequential workhorse, is not patched. Since the parallel and external-memory theorems inherit Lemma 2.2 or its direct variants, the error propagates to those claimed bounds as well. I therefore concur with REJECT: the manuscript as written does not support its central claim. No additional load-bearing concern was found beyond this one; the identified fix is localized but essential.","tokens_in":18615,"tokens_out":6265,"duration_ms":65209,"concrete_test":"Simulate Lemma 2.2 exactly as written (scan all positions, binary search in F', increment) on T = aaaaabcbcbcb with d=1, and report the top bigram and frequency. If the lemma's stated guarantee were correct, it would return bc (non-overlapping frequency 3). The scan as described returns aa with count 4. Alternatively, patch the scan to count only non-overlapping occurrences of equal-character bigrams (e.g., after each match advance one extra position within runs) and rerun; if the patched Lemma 2.2 restores bc as the top bigram, this confirms that the unpatched scan is the source of the failure.","verdict_should_be":"REJECT","load_bearing_attack":"Lemma 2.2 (Sec. 2.1) is the workhorse: each round of Theorem 2.3 computes F by calling it, and the final O(n^2) time bound sums over O(lg n) such calls. The proof computes 'the frequencies of all these bigrams in T ... by scanning the text from left to right' and incrementing a counter on every matching position. That counts overlapping occurrences. But the paper's own definition (Sec. 1.2) is non-overlapping frequency. For any run of L identical characters b, the scan records L-1 occurrences of bb, while the relevant frequency is floor(L/2). This is not merely a cosmetic mismatch: it can change which bigram is reported as most frequent. Example: T = aaaaabcbcbcb. The scan reports aa with frequency 4 and bc with frequency 3, so Lemma 2.2 with d=1 returns aa as the most frequent bigram; under non-overlapping counting, aa has frequency 2 and bc has frequency 3, so the true most frequent bigram is bc. Since Theorem 2.3 replaces the bigram returned by F, the algorithm can make a different replacement sequence than Re-Pair from the very first turn. The paper itself shows it knows the correct treatment: Sec. 3.1, Case b=c, handles runs by splitting into runs ending at even/odd positions and excluding overlaps. That fix can be ported to Lemma 2.2, but as written the lemma's proof does not implement it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an algorithm that computes the Re-Pair grammar compression for a text of length n over an integer alphabet in O(n^2) time using max((n/c) lg n, n⌈lg σ_m⌉)+O(lg n) bits of working space including the text space, working in the restore model. The central tool is a trade-off lemma (Lemma 2.2) that computes the d most frequent bigrams in O(max(n,d) n lg d / d) time and 2d⌈lg(σ^2 n/2)⌉+O(lg n) bits, which is invoked O(lg n) times in the main sequential algorithm. The paper also gives a bit-parallel variant (Theorem 3.1), a parallel variant (Theorem 5.3), an external-memory variant (Theorem 6.1), an adaptation to MR-Re-Pair (Section 4), and a C++ implementation (Section 2.5).","tokens_in":18885,"tokens_out":22560,"duration_ms":211753,"significance":"If the main theorem is correct, this is the first non-trivial in-place Re-Pair algorithm for large integer alphabets, and the same framework extends to parallel and external-memory settings, which would be a meaningful contribution. The paper also includes an implementation and practical heuristics, and the bit-parallel section (Section 3.1) correctly handles the delicate case of repeated-character bigrams by using runs and parity of ending positions. However, the central Lemma 2.2, on which Theorems 2.3, 3.1, 5.3, and 6.1 all rely, counts overlapping occurrences rather than the non-overlapping frequencies required by the paper's own definition of Re-Pair, so the main correctness claim is not established as written.","major_comments":[{"comment":"The proof of Lemma 2.2 computes frequencies by scanning the text from left to right and incrementing a counter for every position whose bigram appears in F'. For a run of L identical characters, this counts L−1 occurrences of the repeated bigram, whereas the paper defines the frequency of a bigram as its number of non-overlapping occurrences (Section 1.2), which is floor(L/2). This is not a cosmetic discrepancy: for T = aaaaabcbcbcb, the scan reports aa with count 4 and bc with count 3, so with d = 1 it selects aa as the most frequent bigram, while the non-overlapping frequencies are aa = 2 and bc = 3, making bc the correct choice. Since Theorem 2.3 invokes Lemma 2.2 O(lg n) times and every replacement decision in the main loop is based on the resulting table F, the algorithm can diverge from the Re-Pair replacement rule from the first turn. The paper itself describes the correct treatment in Section 3.1 (Case b = c), counting runs via even/odd ending positions; that technique can be ported to Lemma 2.2 by skipping to the end of each run and adding floor(L/2), while preserving the O(n lg d) per-scan time. As written, however, the proof of Lemma 2.2 does not implement this, so the central theorem is not established. I consider this a load-bearing correctness issue that must be resolved in a revision.","section":"Section 2.3, capacity of F"},{"comment":"The proof of Theorem 2.3 does not rigorously establish that the freed text space at the beginning of each round is large enough to store the frequency table F together with the working space of Lemma 2.2. The text says 'suppose that we have enough space available for storing the frequencies of α f_k bigrams' and then gives a growth calculation using constants α and β, but it never proves by induction that the space actually freed by previous replacements reaches this size. Since the claimed space bound (max((n/c) lg n, n⌈lg σ_m⌉) + O(lg n) bits including the text) is a central contribution, the authors should supply an explicit invariant that relates the number of freed characters, the bit width ⌈lg σ_{i+1}⌉, and the capacity α f_k, and verify it for large alphabets (σ = Ω(n)), where Lemma 2.2's frequency table has entries of size Θ(lg n) bits. Without such an invariant, the in-place space claim is not fully supported.","section":"Section 2.3, capacity of F"}],"minor_comments":[{"comment":"The extended substring S_j has length d+2 and can contain up to d+1 distinct bigrams, while the frequency table F' has only d entries; the proof's statement that 'there are at most d different bigrams in S_j' is false in general. Increase F' to d+1 entries or note that constants absorb the extra slot.","section":"Section 2.1, proof of Lemma 2.2"},{"comment":"The time bound O(max(n,d) n lg d / d) is undefined for d = 1 because lg 1 = 0. Either state the result for d ≥ 2 and handle d = 1 separately with an O(n^2) bound, or adjust the formula.","section":"Section 2.1, Lemma 2.2"},{"comment":"The summation notation with O(lg n) as the upper limit is informal; replacing it with an explicit bound such as sum_{k=0}^{C lg n} for a constant C would make the time analysis more precise.","section":"Section 2.3, Eq. (1)"},{"comment":"The handling of runs that cross chunk borders is described only in prose; a formal statement of how the run lengths are accumulated and how the even/odd parity is applied across chunk boundaries would improve reproducibility.","section":"Section 3.1, Case b = c"},{"comment":"The implementation fixes the bit width of the text space to 16 bits and assumes a byte alphabet, so the reported experiments do not exercise the bit-width enlargement step that is central to the in-place space claim of Theorem 2.3. This simplification should be stated more prominently.","section":"Section 2.5, implementation"},{"comment":"The notation O(n^2) ∩ O(n^2 lg log_τ n lg lg lg n / log_τ n) is unconventional; since the second term is never larger than the first, describing the bound as O(n^2) with the refinement given in Theorem 3.1 would be clearer.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is an attractive and significant claim, and the flaw in Lemma 2.2 appears local and repairable, so I recommend major revision rather than rejection. If the authors can provide a correct proof of Lemma 2.2 that counts non-overlapping frequencies while preserving the claimed time and space bounds, and if they can make the space-invariant argument in Section 2.3 rigorous, the paper may become acceptable. The novelty relative to [13] and [27] is adequately motivated, and the derivation appears self-contained."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth your time if you care about grammar compression or in-place string algorithms. The paper gives the first non-trivial in-place Re-Pair algorithm for large integer alphabets, plus parallel and external-memory variants, and it ships C++ code with benchmarks. The core design—maintain a growing frequency table F in the space freed by replacing bigrams, recompute it only when it empties, and use a trade-off lemma to find the d most frequent bigrams—is genuinely new. The bit-parallel section is also competent: it handles runs of identical characters correctly by splitting runs at even/odd boundaries, which suggests the authors knew the right way to count non-overlapping frequencies.\n\nThe problem is Lemma 2.2. The paper defines frequency as non-overlapping occurrences, but the proof counts every occurrence in a left-to-right scan. For a run of L identical characters, that counts L-1 occurrences of the pair, not floor(L/2). The stress-test counterexample is correct: T = aaaaabcbcbcb has overlapping 'aa' count 4 but non-overlapping count 2, while 'bc' has 3 non-overlapping occurrences. Lemma 2.2 with d=1 returns 'aa'; the true Re-Pair winner is 'bc'. Since Theorem 2.3 calls Lemma 2.2 every round to build F, the algorithm can deviate from Re-Pair from the first turn. That is load-bearing, not cosmetic.\n\nThe good news is it is clearly fixable: port the run-handling from Sec 3.1 into Lemma 2.2's scan. But as written, the main theorem's correctness proof does not go through.\n\nOther soft spots are minor: the space analysis with α and β is sloppy (the capacity derivation 'f_k = Θ(n) after O(lg n) steps' skates over details), and the implementation hard-codes 16-bit symbols, so the benchmarks do not validate the full space claims.\n\nWho should read this: anyone working on grammar compression or space-efficient string algorithms. It is a serious paper with a serious bug. My recommendation: send it to a good referee but ask them to verify Lemma 2.2 and require a corrected proof. The ideas deserve to be in the literature, but not with the current gap.","headline":"Valuable small-space Re-Pair algorithm with a real, fixable bug in the main frequency-counting lemma; deserves serious review.","tokens_in":19419,"tokens_out":5263,"would_cite":false,"duration_ms":47629,"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":"Re-Pair grammar compression is computable in quadratic time in text-sized working space, including the text itself.","keywords":["Re-Pair","grammar compression","in-place algorithm","small-space computation","frequency table","bigram","restore model","external memory"],"falsifier":"Run the algorithm on a unary text $a^{2k}$ with the trade-off parameter $d=1$: Lemma 2.2's left-to-right scan reports $2k-1$ occurrences of the bigram $aa$, whereas Re-Pair's definition of frequency demands $k$ non-overlapping occurrences. Comparing the frequency stored in $F$ against a direct run-aware count on this input settles whether the subroutine is correct.","tokens_in":18403,"feed_emoji":"📦","tokens_out":15585,"duration_ms":132266,"temperature":0.7,"pith_summary":"Re-Pair is a grammar-compression scheme that repeatedly replaces the most frequent non-overlapping bigram by a fresh non-terminal. This paper tries to establish that the whole Re-Pair grammar can be computed in $O(n^2)$ time using $\\max((n/c)\\lg n, n\\lceil\\lg \\sigma_m\\rceil)+O(\\lg n)$ bits of working space, with the text itself counting as part of that space; for a large integer alphabet with $\\sigma = \\Omega(n)$, that is the first non-trivial in-place Re-Pair algorithm. The demonstration works in the restore model, so the original input can be overwritten and later recovered in the time of the computation with $O(\\lg n)$ extra bits. The same round-based skeleton yields a bit-parallel variant running in $O(n^2 \\lg \\log_\\tau n \\lg \\lg \\lg n / \\log_\\tau n)$ time when $\\tau = o(n)$, plus parallel and external-memory versions. A sympathetic reader would care because Re-Pair's main practical obstacle is not its compression ratio but the large frequency tables its textbook computation maintains, and this paper attacks exactly that obstacle.","feed_headline":"Re-Pair compression now fits in text-sized memory","feed_subtitle":"A frequency table grown in the space freed by replaced bigrams cuts Re-Pair's working memory to roughly text size.","key_machinery":"The load-bearing object is a growing frequency table $F$, physically stored in the text space freed by replacing bigrams with single non-terminals, together with a threshold $t$ fixed at each round as $F$'s lowest stored frequency. Lemma 2.2 is the trade-off subroutine: to find the $d$ most frequent bigrams it splits the text into overlapping blocks of length $d$, builds a candidate table per block, counts candidates by scanning the text with binary search, and merges partial tables, costing $O(\\max(n,d)\\, n \\lg d / d)$ time in $2d\\lceil\\lg(\\sigma^2 n/2)\\rceil$ bits. $F$'s rounds grow its capacity $f_k$ by a constant factor $\\gamma > 1$, so only $O(\\lg n)$ recomputations are needed, and each turn's update rule—decrement frequencies adjacent to replaced occurrences, add bigrams that newly contain the non-terminal, drop entries below $t$—keeps $F$ synchronized with the text.","core_discovery":"The paper's central claim is that Re-Pair can be driven by a frequency table $F$ that is stored in the space freed up by the very replacements it guides. At the start of round $k$ the table holds $f_k$ bigrams and a threshold $t$, the table's lowest frequency; as long as $F$ is non-empty after a turn, it still contains a most frequent bigram, so the next turn can simply take the highest-frequency entry. Only when $F$ empties is it rebuilt, with capacity multiplied by a factor $\\gamma > 1$; because $\\gamma$ is bounded away from 1, only $O(\\lg n)$ rebuilds occur, and each rebuild uses a trade-off subroutine (Lemma 2.2) that partitions the text into overlapping blocks and counts the $d$ most frequent bigrams in $O(\\max(n,d)\\, n \\lg d / d)$ time with $2d\\lceil\\lg(\\sigma^2 n/2)\\rceil$ bits. The result is Theorem 2.3's $O(n^2)$ time and text-sized working space, with variants for bit-parallel counting, parallelism, external memory, and MR-Re-Pair.","pith_inferences":["The round-growth pattern is a general recipe: any compressor whose bottleneck is a candidate or frequency table could grow that table inside the space its own output frees up, using a threshold to avoid frequent rebuilds.","The broadword bigram-counting primitive of Section 3 is reusable on its own for other small-space string algorithms that need bigram frequencies under tight memory.","A natural extension is to make the Lemma 2.2 scan run-aware for repeated bigrams, counting $\\lfloor L/2 \\rfloor$ inside a run of $L$ equal characters instead of $L-1$ occurrences; such a count would match Re-Pair's non-overlapping definition directly and should preserve the time bound.","The practical bottleneck is the early rounds with tiny $f_k$; combining the paper's heuristics (majority vote when one bigram dominates, temporary full table for small alphabets) into an adaptive start could make the $O(n^2)$ worst case rare on real corpora."],"forward_implications":["Re-Pair becomes computable in text-sized working memory plus $O(\\lg n)$ bits, so large-scale grammar compression no longer requires frequency tables that dwarf the input.","The restore model guarantees the original text can be recovered in the time of the whole computation with only $O(\\lg n)$ extra bits, so overwriting the input is safe.","For integer alphabets with $\\sigma = \\Omega(n)$, this is the first non-trivial in-place Re-Pair algorithm; earlier space-efficient Re-Pair algorithms assumed a constant alphabet.","The same frequency-table skeleton gives a parallel CRCW variant running in $O(n^2/p)$ time with $O(p\\lg n)$ extra bits and an external-memory variant whose I/O cost is bounded by scans and sorting instead of a large heap.","When the terminal-plus-nonterminal alphabet $\\tau$ satisfies $\\tau = o(n)$, bit-parallel broadword search lowers the time to $O(n^2 \\lg \\log_\\tau n \\lg \\lg \\lg n / \\log_\\tau n)$ in the same space."],"supporting_citations":[{"why":"Defines Re-Pair and gives the original expected-linear-time algorithm whose large frequency tables are the space bottleneck this paper targets.","marker":"[21]"},{"why":"Gives the prior space-efficient Re-Pair algorithm for constant alphabets, the baseline this paper generalizes to large integer alphabets.","marker":"[5]"},{"why":"Extends the space-efficient approach to include the text within the working space, but only for constant alphabets; a prior bound this paper's theorem matches without that assumption.","marker":"[4]"},{"why":"Introduces the restore model in which an algorithm may overwrite and later restore the input, the model assumed by Theorem 2.3.","marker":"[7]"},{"why":"Provides the in-place heapsort used inside Lemma 2.2 for sorting candidate bigram tables.","marker":"[32]"}],"fun_headline_variants":["Re-Pair's working memory shrinks to text size","Text-sized space for Re-Pair grammar compression","Re-Pair reuses freed space for its frequency table","Small-space Re-Pair: O(n) bits suffice","Self-reclaiming frequency table shrinks Re-Pair memory"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Lemma 2.2's proof assumes that a single left-to-right scan that finds each scanned bigram in a candidate table and increments its counter yields the non-overlapping frequency Re-Pair needs; on a run of $L$ equal characters that scan records $L-1$ occurrences of the repeated bigram, while only $\\lfloor L/2 \\rfloor$ non-overlapping copies exist. Since every round's table is seeded by this subroutine, the main theorem inherits that assumption.","fun_headline_variants_meta":{"raw":{"variants":["Re-Pair's working memory shrinks to text size","Text-sized space for Re-Pair grammar compression","Re-Pair reuses freed space for its frequency table","Small-space Re-Pair: O(n) bits suffice","Self-reclaiming frequency table shrinks Re-Pair memory"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000295,"raw_usage":{"total_tokens":1720,"prompt_tokens":955,"completion_tokens":765,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":685}},"tokens_in":571,"tokens_out":765,"duration_ms":7275,"temperature":1.0,"reasoning_tokens":685,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:30:16.102568+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the algorithm on a unary text $a^{2k}$ with the trade-off parameter $d=1$: Lemma 2.2's left-to-right scan reports $2k-1$ occurrences of the bigram $aa$, whereas Re-Pair's definition of frequency demands $k$ non-overlapping occurrences. Comparing the frequency stored in $F$ against a direct run-aware count on this input settles whether the subroutine is correct.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines Re-Pair and gives the original expected-linear-time algorithm whose large frequency tables are the space bottleneck this paper targets."},{"cited_title":"Bille, I","cited_arxiv_id":null,"evidence_quote":"Gives the prior space-efficient Re-Pair algorithm for constant alphabets, the baseline this paper generalizes to large integer alphabets."},{"cited_title":"Practical and Effective Re-Pair Compression","cited_arxiv_id":"1704.08558","evidence_quote":"Extends the space-efficient approach to include the text within the working space, but only for constant alphabets; a prior bound this paper's theorem matches without that assumption."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the restore model in which an algorithm may overwrite and later restore the input, the model assumed by Theorem 2.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the in-place heapsort used inside Lemma 2.2 for sorting candidate bigram tables."}],"review_version":1}