{"id":"ae78b06b-8b41-4909-b094-8c450f0802ef","arxiv_id":"2607.11271","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"OptFSST lifts FSST's average compression factor by 7.3% and FSST12's by 17.0% across 92 string columns using DP encoding, triple counting, and pruning; it also proves the symbol-table selection problem is NP-hard when the alphabet is part of the input.","lead":"This paper modifies FSST, a string compressor used in database systems, replacing its greedy encoding with a dynamic-programming step plus two symbol-table heuristics. On 92 real string columns it reports average compression-factor gains of 7.3% (FSST) and 17.0% (FSST12), at a 2–4x extra cost in compression time.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Headline averages rest on an under-specified benchmark-filtering rule (§5.1); without the exact exclusion criterion the 7.3%/17.0% claims are not reproducible.","rationale":"The reader's weakest assumption identifies the benchmark-population filtering as the key risk. I independently confirm this is the most load-bearing concern. The paper's main contribution is empirical: it claims specific average compression-factor improvements over FSST and FSST12. If the population on which these averages are computed is not reproducibly defined, the claim cannot be verified or compared against future work. The filtering rule as stated in §5.1 is a discretionary exclusion that could materially alter the averages. The paper would be accepted conditionally on clarifications: publish the exact rule (including the dictionary encoder and its threshold) and the list of 92 columns, or release the benchmark script. The other issues (unreported baseline hyperparameters, lack of repeated-run statistics, unspecified count3 storage, the 'nine bits' inconsistency) are real but less central: the baseline hyperparameters are at least the defaults of the standard FSST release, and the internal inconsistencies do not directly threaten the headline numbers if the benchmark set is fixed. The NP-hardness proof appears mathematically sound and is honestly caveated to apply only when the alphabet is part of the input. Therefore, I agree with the reader's CONDITIONAL verdict; no change is needed, but the stated conditions are essential.","tokens_in":17676,"tokens_out":11743,"duration_ms":93689,"concrete_test":"Obtain the exact filtering rule and column list. Run the evaluation on all columns with ≥1000 strings from the five datasets, without dictionary-encoding exclusion. Recompute mean and median improvements under several plausible operationalizations of 'better' (e.g., dictionary compression factor > FSST's, >1.1× FSST's). If the 7.3%/17.0% averages shift by more than 1 percentage point across definitions, the headline claim is not robust to the filtering choice.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim is the average compression-factor improvement of 7.3% over FSST and 17.0% over FSST12. These numbers are computed over 92 columns selected by a rule that is not precisely defined: §5.1 states 'Columns that are compressed better using dictionary encoding are filtered out' and 'at least 1000 strings per column'. The dictionary-encoding exclusion is discretionary: no operational definition is given for what 'compressed better' means (compression factor? which dictionary encoder? what threshold?), and the exact list of columns is not published. If the rule is applied differently, the set of 92 columns changes, and the averages could shift materially. For example, excluding columns where FSST already performs well, or including columns where FSST catastrophically fails, would directly change the numerator and denominator of the improvement ratio. The paper's own outlier disclosures (OptFSST12 min 0.39, two-byte-string max 47.7%) show sensitivity to specific columns. Because the headline averages are the paper's main contribution, this under-specification is load-bearing: without the exact rule, an independent party cannot reproduce the benchmark population, and the claim's external validity is uncertain. This concern is distinct from the baseline-parameter issue, which is secondary because the baseline is the standard FSST release with default parameters; the filtering rule, by contrast, determines the very sample on which the averages are computed.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents OptFSST and OptFSST12, modifications of the FSST and FSST12 string compressors. OptFSST replaces FSST's greedy longest-match encoder with a dynamic program that finds the minimum-cost segmentation of each string for a fixed symbol table, using cost 1 for a symbol and cost 2 for an escaped byte (Section 3.1). It also adds a third frequency counter for triples of emitted symbols during table construction and a pruning rule that corrects stale gains of overlapping candidates (Sections 3.2 and 3.3). The paper proves that the underlying symbol-table selection problem STS_l is NP-hard for every fixed l>=2 when the alphabet is part of the input (Section 4, Appendix A). The evaluation on 92 real-world string columns reports average compression-factor improvements of 7.3% over FSST and 17.0% over FSST12, with a 3-4x compression-time slowdown, preserved decompression speed for OptFSST, and 1.2x better decompression speed for OptFSST12.","tokens_in":17932,"tokens_out":11263,"duration_ms":96590,"significance":"The DP-based encoding is a principled and clean improvement over greedy encoding for a fixed symbol table, and the NP-hardness proof in Appendix A is a solid justification for the heuristic table construction; I verified the reduction's main accounting and found no flaw. The evaluation is unusually honest for this area: it ablates each component separately, discloses tested-and-abandoned variants, and explains the OptFSST12 0.39x outlier. If the empirical claims survive a well-specified benchmark population, this is a useful incremental contribution for systems that use FSST-style random-access string compression. The main risk is not algorithmic but methodological: the headline averages depend on a benchmark-selection rule that is not operationalized in the manuscript.","major_comments":[{"comment":"The headline averages (7.3% and 17.0% in Section 5.2) are computed over a set of 92 columns whose selection is not reproducible. Section 5.1 states only that columns 'compressed better using dictionary encoding are filtered out' and that columns with fewer than 1000 strings are dropped. This leaves the central exclusion rule undefined: which dictionary encoder, compared by compression factor or size, with what threshold, and applied to what units? The per-dataset counts (23+22+31+13+3=92) exactly sum to the final total, making it unclear whether any columns were excluded and from which corpora. I request the exact selection rule, the number of excluded columns per source, the full column list in the artifact, and a sensitivity analysis around the dictionary-encoding filter. Without this, the average improvements and the 82/92 and 87/92 column counts are not independently verifiable.","section":"Section 5.1"},{"comment":"The compression-factor metric is not defined, and the role of the symbol-table size is ambiguous. The DP recurrence in Section 3.1 minimizes only the encoded payload (1 byte per symbol, 2 per escaped byte). However, the Section 5.4 discussion of the OptFSST12 min 0.39x result says the 4096-entry symbol table's 'serialization alone exceeds twice the input size and dominates the reported compression factor', implying the reported compression factor includes the serialized symbol table. If so, the DP objective is not the reported objective, and a heuristic table construction can outweigh the DP gain on small columns. Please state the exact formula for compression factor, specify whether symbol-table bytes are included for all codecs, and report table sizes for baseline and OptFSST variants. This is needed to interpret the headline improvements and the outlier.","section":"Sections 3.1 and 5.2"},{"comment":"The pruning component is retained even though its aggregate effect is reported as neutral ('no noticeable effect' on the mean) and the ablation shows it can hurt in a minority of columns. This is a defensible design choice given the majority-of-columns benefit, but the paper should quantify the distribution rather than only report the mean and best cases: e.g., how often does pruning degrade the compression factor and by how much? Since pruning is one of the three named contributions, a fuller characterization would strengthen the claim that it is a useful correction rather than a heuristic kept on the basis of the majority count.","section":"Section 5.2"}],"minor_comments":[{"comment":"The citation 'GPU-aware FSST adaptation [5?]' contains an unresolved question mark and should be corrected to a proper reference.","section":"Section 2"},{"comment":"The tie-breaking rule 'prefer longer symbols on equal DP cost' is presented as improving compression factors. Because all ties have the same output cost for the final encoding, the effect must come from the training loop's frequency counts; this should be stated explicitly so readers do not infer that the tie-break improves the DP optimum.","section":"Section 3.1"},{"comment":"The paper does not state which FSST/FSST12 version or parameter settings (sample size, number of generations, candidate budget) are used for the baseline. Please add the exact version and default parameters, or state that the released defaults are used.","section":"Section 5.1"},{"comment":"Table 1 reports end-to-end slowdowns, but the text in Section 5.3 gives only average compression speeds. It would be useful to report the median as well, since the violin plots show skewed distributions.","section":"Section 5.3"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about benchmark filtering is the decisive issue; it is load-bearing and fixable. The NP-hard proof and the DP formulation appear sound, and the paper's transparency about the 0.39x outlier is a strength. If the authors supply an exact benchmark-selection procedure, the full column list, and a clear compression-factor definition, I would be willing to accept."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The DP-encoding idea itself is not new — the original FSST paper mentions it as a footnote — but this paper does the work: it implements a trie-based DP encoder that is actually fast enough to use, integrates it into the generation-based table construction, adds a triple-frequency counter and conflict-aware pruning, and ports everything to FSST12. That combination, with the FSST12 numbers, is not in the prior literature. The NP-hardness result for STS_l (alphabet part of the input) is a nice addition; I checked the reduction in Appendix A and it works: the copy strings force C into D, the edge gadgets cost 2 or 3, and the |U| <= K mapping is sound. It also honestly notes in Appendix B that fixed alphabet size makes the problem polynomial.\n\nThe evaluation is better than most. The ablation separates each component. They say pruning is neutral in aggregate, they disclose the 0.39x OptFSST12 outlier and explain it, and they report the 47.7% max comes from a column of 2-byte strings. They describe and abandon an adaptive threshold. The kept heuristics are not reported as fitted to the benchmark suite. That kind of transparency earns trust.\n\nThe soft spot is load-bearing. The headline averages are computed over 92 columns selected by a rule stated as 'Columns that are compressed better using dictionary encoding are filtered out' (§5.1). There is no operational definition — which dictionary encoder, what threshold, compression factor or ratio, on the same data? — and the column list is not given. Since the outliers show sensitivity to individual columns, this filtering rule can materially shift the 7.3%/17.0% numbers. This is fixable: report the exact rule and the full column list, or at least the excluded columns.\n\nMinor issues: no repeated-run statistics, artifact has no commit hash, and the 'nine bits' comment in §3.2 is inconsistent with the 12-bit codes of FSST12. These are minor.\n\nThis paper deserves a real referee. The engineering is sound, the claims are honest, and the missing details are all addressable without new experiments.","headline":"The core result — DP-based encoding plus count3 and pruning gives 7.3%/17% average compression-factor gains on FSST/FSST12 — is plausible and honestly evaluated; the main blemish is the under-specified benchmark-filtering rule, which needs pinning down before those averages are reproducible.","tokens_in":18532,"tokens_out":3420,"would_cite":true,"duration_ms":28114,"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 shows that FSST's greedy encoding and symbol selection are suboptimal, and that replacing them with a dynamic-programming encoder plus improved table construction raises average compression factors by 7.3% over FSST and 17.0% ove","keywords":["FSST","string compression","dynamic programming","symbol table","random access","columnar storage","NP-hardness","compression factor"],"falsifier":"Run OptFSST and FSST on a large unfiltered set of string columns, including dictionary-friendly columns, with identical training settings for both, and compute the mean compression-factor improvement; if the mean falls below a few percent or many columns regress, the claimed 7.3%/17.0% averages are an artifact of the benchmark filter. A second check: hold the symbol table fixed and compare DP encoding to greedy longest-match encoding on every string; if DP never improves on greedy, the central recurrence is not carrying the gain.","tokens_in":17471,"feed_emoji":"🗜️","tokens_out":4875,"duration_ms":42342,"temperature":0.7,"pith_summary":"FSST compresses database strings by replacing frequent byte sequences with one-byte codes in a static symbol table, but its greedy longest-match encoding and greedy symbol selection leave compression on the table. This paper introduces OptFSST, which computes the optimal encoding for a given symbol table using a dynamic-programming recurrence, and improves symbol-table construction with a triple-frequency counter and a pruning step. It also proves that finding an optimal symbol table is NP-hard when the alphabet is part of the input, justifying heuristic table construction. On 92 real-world string columns, OptFSST improves average compression factors by 7.3% over FSST and 17.0% over FSST12 while preserving fine-grained random access, and OptFSST12 decompresses 1.2x faster on average. The cost is a 2-4x slowdown in compression and table-construction time, which the paper argues is worthwhile because compression is paid once while decompression is on the query path.","feed_headline":"Optimal encoding lifts FSST compression by up to 47.7%","feed_subtitle":"Dynamic programming plus smarter symbol selection cuts string size 7.3% on average with no decompression change.","key_machinery":"The central mechanism is the DP recurrence with a trie-backed lookup: from each input position the encoder either escapes one byte (cost 2) or emits a table symbol matching the prefix (cost 1), choosing the minimum suffix cost. Because candidate symbols are stored in a trie, the DP enumerates only actually matching symbols up to the maximum symbol length, and the dp_choice array turns the cost table into an encoding. Supporting mechanisms are the third frequency counter count3, which packs three 9-bit codes into a 32-bit hash key to discover triples of consecutive emitted symbols, and pruning, which subtracts a selected concatenated symbol's count from its component symbols and pairs before","core_discovery":"For a fixed symbol table T, the minimum compressed size of a string s satisfies the recurrence dp[i] = min(2 + dp[i+1], 1 + min_{s[i:j] in T} dp[j]), and OptFSST computes it with a trie walk, storing dp_choice to emit the optimal segmentation. This replaces FSST's greedy longest-match encoder. For table construction, OptFSST adds count3 triple counting to expose longer recurring symbols earlier and prunes overlapping candidates' counts so redundant symbols do not waste limited table entries. The paper proves that STS_l, selecting a dictionary of length-at-most-l symbols minimizing total encoded cost, is NP-hard for every fixed l >= 2 when the alphabet is part of the input, motivating these h","pith_inferences":["Combining OptFSST with prefix-extraction layout schemes could compound the two sources of redundancy (cross-string prefixes and intra-string symbols); the paper notes the schemes are complementary but does not measure the combination.","The DP encoder is branch-heavy and parallelizable per string; the paper's hint about DPX-style instructions suggests a GPU implementation could substantially cut the reported compression-time cost, but this is untested.","The fixed-alphabet polynomial result in Appendix B points to a pragmatic test: on low-cardinality alphabets, a near-optimal table search may be feasible and could outperform the heuristics on those columns.","The benchmark filters out dictionary-encodable columns, so the 7.3%/17.0% averages describe the gain on columns where FSST is the right tool; on an unfiltered fleet of string columns the headline averages would likely be lower."],"forward_implications":["Systems that already store FSST-compressed columns can adopt OptFSST without changing the decompression format or the random-access property, because the compressed representation is unchanged.","Gains in compression factor translate directly into smaller memory footprints and lower memory-bandwidth pressure per scan, which matters when analytical workloads are cache- and bandwidth-bound.","OptFSST12's 1.2x decompression-speed gain means queries reading compressed string columns can get faster, not just smaller.","The NP-hardness result for STS_l implies no polynomial-time optimal table construction exists for variable alphabet size, so the heuristic components are necessary rather than incidental.","The per-column variation (89% of columns improve for OptFSST, 95% for OptFSST12) indicates the method helps most columns while a minority stay near parity or regress, so users should expect workload-dependent gains."],"fun_headline_variants":["FSST gets optimal encoding: up to 47.7% smaller strings","DP beats greedy for FSST encoding: 47.7% gain","NP-hard symbol selection? OptFSST prunes for 91.5% gain","OptFSST: Triple counting and pruning lift FSST compression","Optimal FSST encoding: 7.3% average, 47.7% max improvement"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The headline averages depend on a filtering rule that removes columns where dictionary encoding beats FSST, and the exact rule is not disclosed; if that selection were different, the improvement numbers could change materially.","fun_headline_variants_meta":{"raw":{"variants":["FSST gets optimal encoding: up to 47.7% smaller strings","DP beats greedy for FSST encoding: 47.7% gain","NP-hard symbol selection? OptFSST prunes for 91.5% gain","OptFSST: Triple counting and pruning lift FSST compression","Optimal FSST encoding: 7.3% average, 47.7% max improvement"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000935,"raw_usage":{"total_tokens":3880,"prompt_tokens":827,"completion_tokens":3053,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":2949}},"tokens_in":571,"tokens_out":3053,"duration_ms":18970,"temperature":1.0,"reasoning_tokens":2949,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T06:57:45.947281+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run OptFSST and FSST on a large unfiltered set of string columns, including dictionary-friendly columns, with identical training settings for both, and compute the mean compression-factor improvement; if the mean falls below a few percent or many columns regress, the claimed 7.3%/17.0% averages are an artifact of the benchmark filter. A second check: hold the symbol table fixed and compare DP encoding to greedy longest-match encoding on every string; if DP never improves on greedy, the central recurrence is not carrying the gain.","supporting_citations":[],"review_version":2}