{"id":"a021720a-3bf4-4373-9714-af47fadfd4ce","arxiv_id":"2501.06570","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Poly-LSM hybridizes vertex-based and edge-based LSM storage for graphs and adaptively selects update methods, and the resulting Aster graph database outperforms baselines on large graphs.","lead":"Aster wraps a new graph storage engine, Poly-LSM, that keeps both edge-by-edge and neighbor-list views of a graph inside an LSM-tree and adaptively picks the cheaper update method per edge. On large graphs the paper reports throughput up to 17x higher than the best baseline that finished loading.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central claim rests on Lemma 3.1, whose skewed-workload proof is deferred to an unpublished technical report, while the implemented threshold uses P_u = 1/n and ignores per-vertex lookup frequency; the paper's robustness under skewed workloads is therefore not established.","rationale":"The reader's weakest_assumption correctly identifies the uniform-workload assumption in Section 3.3 and the unproven Lemma 3.1 as the load-bearing risk. My stress-test agrees: the threshold in Eq. 8 uses only degree, so per-vertex lookup skew is invisible to the adaptive mechanism; the only stated rescue is Lemma 3.1, whose proof is not in the paper. The paper deserves credit for a concrete cost model, a degree sketch with a stated approximation guarantee (Lemma 3.2), and an extensive experimental comparison, including a billion-edge Twitter dataset. However, none of the experiments appears to apply a skewed lookup distribution, so the regime addressed by Lemma 3.1 is untested. This is a correctness risk, not an internal inconsistency: the cost model is explicitly stated to assume uniformity, and the paper flags the general case as deferred. A CONDITIONAL verdict remains appropriate because the concern is substantial but addressable: either the technical report must supply a rigorous proof that accounts for per-vertex lookup frequencies, or the evaluation must include skewed-workload experiments. If the proposed test shows Poly-LSM is dominated by a static policy in a skewed workload, the verdict should move toward REJECT for the current version; if the proof or experiment validates robustness, ACCEPT would be supported. Since neither outcome is yet known, I do not change the reader's CONDITIONAL verdict.","tokens_in":28880,"tokens_out":6483,"duration_ms":66524,"concrete_test":"Run Aster on a synthetic scale-free graph (e.g., n = 10^5, m = 10^6, T = 10, L = 4) under a 50/50 lookup/update workload in which 30% of lookups target a single high-degree vertex u* (degree approximately 100) and the remaining lookups are uniform over all vertices. Compare Poly-LSM's throughput against Delta-Poly, Pivot-Poly, and a hand-tuned policy that always pivot-updates u* and delta-updates all other vertices. If Poly-LSM is not within a small constant of the best policy, and especially if it is no better than the worse of Delta-Poly and Pivot-Poly, then the P_u = 1/n assumption in Eq. 3 is not harmless and Lemma 3.1 is not validated by the implementation. Independently, retrieve technical report [1] and verify whether its Lemma 3.1 proof uses per-vertex lookup probabilities rather than the global P_u = 1/n used in the threshold derivation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that Poly-LSM simultaneously achieves edge-based update efficiency and vertex-based lookup efficiency depends on the adaptive threshold d_t in Eq. 8. This threshold is derived under the explicit uniform-workload assumption P_u = 1/n in Eq. 3, so it depends only on vertex degree and global workload ratios, not on how often a particular vertex u is queried. Real graph workloads are typically skewed: a small number of hub vertices receive a disproportionate share of lookups. For such a hot vertex u with degree d_u > d_t but lookup frequency f_u >> 1/n, the prospective-read term in Eq. 1 should be N_L * f_u rather than N_L / n; the delta update is then far more expensive than the pivot update, yet Poly-LSM systematically selects delta. The reverse error occurs for cold vertices that should be delta-updated but are forced to pivot because their degree is below d_t. The paper acknowledges this regime only via Lemma 3.1, which asserts O(log m)-competitiveness under skewed workloads, but the proof is deferred to the unpublished technical report [1], and Section 6 contains no experiment with a skewed lookup distribution. Section 6 also claims Poly-LSM is 'theoretically global optimal', a statement the paper only argues for uniform workloads. If Lemma 3.1 fails, the adaptive mechanism can be dominated by a simple static policy on skewed workloads, and Design 1's simultaneous-efficiency claim is unsupported in exactly the regime where graph workloads are hardest to handle.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Poly-LSM, an LSM-tree-based graph storage engine that stores graph data as polymorphic key-value entries, allowing both edge-based (delta) and vertex-based (pivot) updates. A cost model over LSM I/O is used to derive an adaptive degree threshold (Eq. 8) that selects delta versus pivot updates per vertex, and a compact Morris-counter degree sketch supports this decision in memory. The paper also describes partitioned Elias-Fano encoding for adjacency lists, and builds a full Gremlin-capable graph database, Aster, on top of RocksDB. The evaluation compares Aster with Neo4j, ArangoDB, OrientDB, SQLG, JanusGraph, and NebulaGraph across moderate, large, and billion-scale datasets, reporting up to 17x throughput improvement over the best baseline on the Twitter graph, plus an I/O cost model validation in Figure 8(C).","tokens_in":29202,"tokens_out":6484,"duration_ms":56434,"significance":"If the central claims hold, the paper makes a useful contribution: a single disk-resident graph storage engine that avoids the usual read/write trade-off of linked-list, relational, and single-layout LSM graph stores. The adaptive threshold is derived from input constants (I, B, T, L, theta_L, theta_U, d) rather than fitted to the experimental results, and Figure 8(C) provides an out-of-sample check of predicted versus actual I/O. The implementation of a complete Gremlin-capable database and the billion-scale Twitter evaluation are additional strengths. However, the manuscript's robustness claim for skewed workloads is not established in the paper itself, and the abstract's blanket performance claim is contradicted by the paper's own moderate-scale results.","major_comments":[{"comment":"The adaptive threshold in Eq. (8) is derived under the explicit uniform-workload assumption P_u = 1/n stated in Eq. (3). The only statement covering skewed workloads, Lemma 3.1, is asserted with the proof deferred to the unpublished technical report [1]. This is load-bearing for Design 1's claim of simultaneous update and lookup efficiency. Under a skewed lookup distribution, the prospective-read term in Eq. (1) should depend on the per-vertex lookup frequency f_u rather than the global average 1/n; a hot vertex with degree above d_t would then be systematically delta-updated even when its high lookup frequency makes a pivot update cheaper, and a cold vertex below d_t would be pivot-updated even when delta is cheaper. The paper should either include the proof of Lemma 3.1 or provide an experiment with a skewed lookup distribution (for example, Zipf over vertex IDs) comparing Poly-LSM against Delta-Poly, Pivot-Poly, and Vertex-LSM. In addition, the statement in §6.2 that Poly-LSM is \"theoretically global optimal\" is stronger than what Section 3.3 establishes, since exact optimality is only argued under the uniform-workload assumption.","section":"§3.3, Lemma 3.1 and Eq. (8)"},{"comment":"The abstract claims that Aster \"outperforms all baseline graph databases,\" and Section 6.2 states that \"Aster outperforms all other databases on moderate and large-scale graphs.\" These statements are contradicted by the paper's own results: on DBLP with heavy lookups, Aster is reported to be slower than Neo4j, and Figure 7(D) states that Aster \"slightly trails Neo4j on moderate-scale datasets\" for the GetNeighbors operation. The claim should be qualified to large-scale and massive-scale datasets or to the specific workloads where it holds, and should not be stated as a blanket superiority claim.","section":"Abstract and §6.2 (Figure 6, Figure 7)"}],"minor_comments":[{"comment":"The text says \"most entries in Pivot-Poly exist in the form of edge-based adjacency lists,\" but Pivot-Poly performs pivot updates, which create vertex-based adjacency-list entries; this appears to be a typo and should read \"vertex-based adjacency lists\" or \"pivot entries.\"","section":"§6.1"},{"comment":"The sentence \"Poly-LSM's adaptive mechanism uses u's degree... based on the threshold outlined in Equation 6\" refers to the wrong equation; the adaptive threshold is defined in Eq. (8), not Eq. (6).","section":"§3.3, The Degree Sketch"},{"comment":"The description that RocksDB's 1-leveling keeps \"each buffer flush as a separate run in the first level and does not merge with existing data\" is a simplification; in RocksDB's Leveled compaction, level 0 runs are eventually merged into level 1. The cost model extension may still be valid, but the wording should be more precise.","section":"§3.3, 1-leveling extension"},{"comment":"The partitioned Elias-Fano encoding has tunable parameters (segment count and prefix length), but the paper does not state how these are chosen in the experiments or whether performance is sensitive to them; a brief note or sensitivity result would improve reproducibility.","section":"§3.4"}],"recommendation":"major_revision","confidential_remarks":"The main technical concern is the deferred proof of Lemma 3.1: the paper's robustness under skewed workloads is a central selling point, and the current manuscript neither reproduces the proof nor tests a skewed-lookup workload. I would urge the editor to require either the proof to be included in the paper or a direct skewed-workload experiment before acceptance. The abstract overclaim regarding beating all baselines should also be corrected, as it conflicts with the paper's own DBLP heavy-lookup result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nThe headline: this is a solid systems paper with a real engineering contribution, but the abstract oversells it and the main theoretical robustness claim is parked in an unpublished tech report. Worth a serious referee, but needs revision before acceptance.\n\nWhat's new: the hybrid LSM layout that lets a graph vertex have one pivot entry plus several delta entries, with per-vertex adaptive choice between delta and pivot updates based on a degree threshold derived from a cost model. The building blocks—RocksDB Merge Operator, Morris Counter, Elias-Fano—are all standard, but the combination and the threshold analysis are genuinely new. I checked the cost model and it's simple but not circular: the inputs are physical constants (I, B, T, L) and workload ratios, no fitted parameters, and Figure 8(C) shows predicted vs actual I/O tracking well, which is a real out-of-sample check.\n\nThe empirical work is comprehensive: multiple baselines, datasets from moderate to billion-scale Twitter, plus property queries and Graphalytics. On the tested workloads the advantage is real, especially on large graphs.\n\nWhere it gets soft. First, the abstract says 'outperforms all baseline graph databases'; the paper's own Figure 6 shows Neo4j beating Aster on DBLP under heavy lookups, and the text admits it. That's an overclaim that should be fixed. Second, the adaptive threshold derivation assumes uniform lookup distribution (P_u = 1/n). Real graph workloads are skewed, and the paper's only answer to that is Lemma 3.1, which asserts O(log m)-competitiveness but whose proof is deferred to an unpublished technical report. There's no experiment with skewed lookup distribution, so the robustness claim hangs on a lemma the reader cannot check. This is the weakest point. It's not a fatal flaw—the system likely still behaves reasonably—but as written the central claim 'simultaneous update and lookup efficiency' is only established under uniform workloads, and 'theoretically global optimal' in Section 6 is only argued for uniform. Third, the baselines are dated (Neo4j 3.2, OrientDB 2.2, etc.) and there are no error bars. Minor, but worth noting.\n\nWho this is for: anyone working on LSM-based graph storage or disk-resident graph databases. It deserves peer review, and with the overclaim fixed and either the lemma proof included or a skewed-workload experiment added, it would be acceptable.\n\nRecommendation: send it for review, but insist on those revisions.","headline":"Hybrid LSM graph storage design that is genuinely new and mostly well-validated, but the abstract overclaims and the skewed-workload robustness proof is deferred to a tech report.","tokens_in":29725,"tokens_out":3907,"would_cite":true,"duration_ms":33682,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A graph storage engine can get fast updates and fast lookups at once by storing each vertex as a pivot entry plus small delta entries and choosing per update based on degree.","keywords":["LSM-tree","graph database","disk-resident storage","adaptive updates","degree sketch","Elias-Fano encoding","hybrid storage layout","Gremlin"],"falsifier":"Run the same update/lookup workload on a power-law graph whose hub vertices receive most of the lookup traffic, compare measured I/O cost against the throughput predicted by the paper's uniform-workload cost model, and check whether the $O(\\log m)$-competitiveness bound holds; if the actual cost of the threshold-chosen updates exceeds that of always-delta or always-pivot by more than the model allows, the uniformity assumption is violated.","tokens_in":28679,"feed_emoji":"⚡","tokens_out":8013,"duration_ms":72935,"temperature":0.7,"pith_summary":"Disk-resident graph databases have historically forced a choice: store each edge as its own entry and updates are cheap but neighbor lookups are slow, or store each vertex's adjacency list as one entry and lookups are fast but updates require read-modify-write. This paper tries to remove that choice. It proposes Poly-LSM, an LSM-tree-based storage engine in which each vertex has one pivot entry holding the bulk of its adjacency list plus small delta entries holding recent edge changes, and a per-operation adaptive rule decides which kind of update to issue based on the vertex's degree and the workload's lookup/update ratio. On top of Poly-LSM the authors build Aster, a Gremlin-compatible graph database, and report that it outperforms all tested mainstream graph databases, with up to a 17x throughput improvement over the best baseline on the billion-edge Twitter graph. The interest is that, if the claims hold, a single disk-resident engine can serve mixed read/write workloads on very large evolving graphs without the usual read-write trade-off.","feed_headline":"Hybrid LSM graph store tops rivals by 17x on Twitter","feed_subtitle":"A per-vertex adaptive storage layout lets Aster keep edge writes cheap and neighbor reads fast at billion-edge scale.","key_machinery":"The load-bearing mechanism is the hybrid pivot-delta entry layout inside a standard LSM-tree. Each vertex has exactly one pivot entry—a sorted adjacency list—plus zero or more delta entries, each holding a recent edge insertion or deletion; compaction folds deltas into the pivot as it pushes data down the levels. The adaptive decision is made by a cost model that compares the expected I/O cost of a delta update (write cost now plus extra reads later) with that of a pivot update (read-modify-write of the whole adjacency list now), yielding a degree threshold $d_t$: vertices with degree at or above $d_t$ use delta updates, lower-degree vertices use pivot updates. An 8-bit Morris-counter-based degree sketch estimates each vertex's degree in memory with bounded variance, and partitioned Elias-Fano encoding compresses the sorted neighbor lists to reduce space and I/O.","core_discovery":"The paper's central claim is that Poly-LSM achieves update efficiency comparable to edge-based LSM-trees and lookup efficiency akin to vertex-based LSM-trees simultaneously. The device that makes this possible is a polymorphic key-value layout: each vertex is stored as one pivot entry (a sorted adjacency list) together with any number of delta entries (single-edge updates), and the LSM-tree's own compaction gradually merges delta entries into the pivot entry as data moves to deeper levels. Edge insertions and deletions can therefore start life as cheap delta writes, while lookups still terminate at the consolidated pivot entry, so read cost is bounded by the number of LSM levels rather than by vertex degree. The paper further claims that the delta-versus-pivot decision can be made optimally per operation by thresholding on a vertex-degree estimate supplied by an 8-bit sketch, and that the resulting system, Aster, outperforms all baseline graph databases in its experiments, including a 17x throughput gain over the best-performing baseline on the billion-edge Twitter dataset.","pith_inferences":["The same pivot/delta idea could generalize beyond graphs: any LSM-backed key-value store holding large composite values could decide per key whether to write a small delta or rewrite the whole value, using a per-key size or hotness estimate instead of degree.","A testable extension is to relax the uniform-lookup assumption in the cost model—for example, replacing $P_u = 1/n$ with a Zipfian frequency model—and see whether the threshold and the 17x result survive skewed hub-centric workloads.","The 8-bit degree sketch has roughly 10% relative error, so vertices whose degree sits near $d_t$ may be assigned the 'wrong' update method; the paper argues the cost difference is small there, but measuring the cumulative effect on frequently updated hub vertices would settle that.","Because delta entries are timestamped in the MVCC design, the layout may extend naturally to temporal or versioned graphs, where each delta is a time-stamped edge and compaction must be careful not to collapse distinct versions."],"forward_implications":["A single disk-resident graph database can serve mixed update/lookup workloads without forcing users to pick a write-optimized or read-optimized storage layout.","Because delta entries are merged into pivot entries during normal LSM compaction, the hybrid layout needs no new storage primitive beyond the Merge Operator APIs already present in standard LSM engines.","Neighbor lookup cost is bounded by the number of LSM levels rather than the degree of the queried vertex, which is what lets performance degrade slowly as graphs grow to billion-edge scale.","The threshold rule is tunable: lookup-heavy or low-average-degree workloads push $d_t$ up (more pivot updates), update-heavy or high-average-degree workloads push it down (more delta updates).","Compressing adjacency lists with partitioned Elias-Fano encoding reduces the bytes read and written per entry, amplifying the benefit of the pivot layout for dense vertices."],"supporting_citations":[{"why":"The LSM engine whose Merge Operator, compaction, and bloom-filter machinery Poly-LSM extends.","marker":"[32]"},{"why":"The Merge Operator API that supplies the delta-entry semantics for accumulating edge values with the same key.","marker":"[30]"},{"why":"The LSM cost-modeling work that supplies the leveling and write-amplification terms used in the adaptive threshold analysis.","marker":"[24]"},{"why":"The approximate counting scheme that underlies the 8-bit per-vertex degree sketch.","marker":"[67]"},{"why":"The compression scheme for sorted integer lists used to encode neighbor sets and cut space and I/O.","marker":"[69]"},{"why":"The microbenchmark that supplies several datasets and the workload design for the experimental comparison.","marker":"[57]"},{"why":"The billion-edge Twitter graph on which the reported 17x throughput improvement is measured.","marker":"[49]"},{"why":"The graph traversal framework used to implement the Gremlin query interface of Aster.","marker":"[12]"}],"fun_headline_variants":["LSM with hybrid vertex storage: 17x faster on Twitter graph","Graph updates meet LSM: Aster's polymorphic layout wins 17x","Adaptive LSM for graphs: cheap writes, fast reads at scale","Aster's key trick: vertex-level delta merging in LSM","Per-vertex pivots give Aster 17x on billion-edge Twitter"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The adaptive threshold is computed from a cost model that assumes every vertex is queried about equally often; real graph workloads are typically skewed toward a few hub vertices, and the paper defers the proof that performance stays near-optimal under such skew to an external technical report.","fun_headline_variants_meta":{"raw":{"variants":["LSM with hybrid vertex storage: 17x faster on Twitter graph","Graph updates meet LSM: Aster's polymorphic layout wins 17x","Adaptive LSM for graphs: cheap writes, fast reads at scale","Aster's key trick: vertex-level delta merging in LSM","Per-vertex pivots give Aster 17x on billion-edge Twitter"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000206,"raw_usage":{"total_tokens":1397,"prompt_tokens":945,"completion_tokens":452,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":356}},"tokens_in":561,"tokens_out":452,"duration_ms":5209,"temperature":1.0,"reasoning_tokens":356,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:58:03.333183+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same update/lookup workload on a power-law graph whose hub vertices receive most of the lookup traffic, compare measured I/O cost against the throughput predicted by the paper's uniform-workload cost model, and check whether the $O(\\log m)$-competitiveness bound holds; if the actual cost of the threshold-chosen updates exceeds that of always-delta or always-pivot by more than the model allows, the uniformity assumption is violated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Merge Operator API that supplies the delta-entry semantics for accumulating edge values with the same key."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The approximate counting scheme that underlies the 8-bit per-vertex degree sketch."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The compression scheme for sorted integer lists used to encode neighbor sets and cut space and I/O."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The microbenchmark that supplies several datasets and the workload design for the experimental comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The billion-edge Twitter graph on which the reported 17x throughput improvement is measured."}],"review_version":1}