{"id":"60c7de4b-3aa8-434d-acdd-02c8c5abe71a","arxiv_id":"2411.17091","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"LESS losslessly stores provenance graphs by learning graph structures with XGBoost and compressing attributes into a minimum spanning tree of edit operations, reporting gains over LEONARD on disk, storage time, query speed, and memory.","lead":"This paper presents LESS, a storage system that compresses large security provenance graphs losslessly by splitting them into graph structure and attributes, using an XGBoost model for the structure and a minimum spanning tree of edit operations for the attributes. If the measured improvements hold, LESS would make long-term storage of audit logs for attack investigation substantially cheaper in disk, memory, and time.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Calibration-table sizes in Tables VI/II are inconsistent with reported per-character XGBoost accuracy; the structure-compression ratio and losslessness claim are therefore unsupported.","rationale":"I read LESS as a lossless learned provenance-graph store whose headline claim is Pareto dominance over LEONARD: 6.29x storage time, 5.24x disk usage, 18.3x query speed, and 11.5% memory. That claim must hold for every component, but the structure-side argument is the load-bearing one: vectorize the adjacency lists, train XGBoost to predict the 13-symbol stream, use a calibration table to correct all mispredictions, and then rely on model plus calibration table being far smaller than the raw structure. The paper's own Tables VI and VII make this condition numerically implausible. A per-character accuracy of 0.71 with a 296KB calibration table implies a vector length of about half a million symbols, whereas the S1 graph (2.08M nodes, 2.16M edges, 18MB structure) should produce a vector orders of magnitude longer after decimal expansion of the delta/RLE tuples. The reader identified exactly this inconsistency as the weakest assumption, and I agree it is the most load-bearing. I therefore keep the reader's CONDITIONAL verdict: the concern is serious and addressable but does not by itself require rejection. What would change the verdict is either a released implementation that reproduces the reported calibration sizes, or a precise definition of 'Acc' showing why the calibration table can be so small. The missing code link and the undefined accuracy metric are part of the same reproducibility gap. I am not raising a separate concern about the query warm-up exclusion, although it is also worth reporting; the calibration-size inconsistency is more fundamental because it threatens the lossless compression ratio itself.","tokens_in":22921,"tokens_out":6794,"duration_ms":63955,"concrete_test":"Run the Section II-B vectorization on S1 (and D1) using the published DARPA OpTC/TC files: count the total number of 0–12 symbols L in the flattened vectors. Compute E = round((1-Acc)*L) and encode E corrections with the paper's δ/v calibration scheme; compare the resulting byte size to the 296KB (S1) and 347KB (D1) entries in Tables VI and II. If the encoded table is more than, say, 2x the reported size, either the accuracy metric is misdefined or the calibration size is underreported, and the structure-compression ratio is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section II-B describes a 13-symbol vectorization and a calibration table that stores (δ,v) for every mispredicted symbol, with δ in 1 or 3 bytes and v in 1 byte. Table VII reports Acc 0.7109–0.7662 on S1–S5, while Table VI reports calibration tables of only 296KB–1.32MB. At Acc=0.7109, a per-symbol error rate of 0.289 means 296KB (at about 2 bytes per correction) supports roughly 148K corrections, i.e., a vector of about 510K symbols. The S1 structure vector, obtained by decimal-expanding the delta/RLE 2-tuple lists for 2.16M edges and 2.08M nodes (18MB structure size), must contain on the order of 10^7 symbols. The two numbers are off by more than an order of magnitude. If 'Acc' is instead per row, edge, or node, the paper never defines it, and the calibration entries per incorrect row would only be larger. Because the central compression claim is model plus calibration table versus raw structure, this inconsistency directly undermines the reported 5.24x disk reduction and the losslessness guarantee. No code or metric definition is provided to resolve the discrepancy.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"LESS is a provenance-graph storage system that splits the input graph into structure and attributes. The graph structure is delta- and run-length encoded into a 13-symbol vector, modeled with XGBoost, and stored as a trained model plus a calibration table that corrects mispredictions; graph attributes are stored as an approximate minimum attribute tree built from a window-based similarity matrix and edit operations. The paper reports experiments on DARPA TC, DARPA OpTC, and a self-collected Linux Audit dataset, claiming 6.29x less storage time, 5.24x less disk usage, 18.3x faster queries, and 11.5% of LEONARD's memory, along with ablations of model choice, window size, and dataset scale.","tokens_in":23193,"tokens_out":11756,"duration_ms":123836,"significance":"If the reported numbers are correct, LESS is a practical improvement for long-term provenance storage: separating structure from attributes is a clean design, the XGBoost-plus-calibration scheme is lightweight and CPU-friendly, the attribute tree exploits a useful locality heuristic, and the evaluation spans multiple datasets with per-component breakdowns. The per-phase time breakdowns and the ablation studies are valuable. However, the central efficiency claim is not currently verifiable because the model accuracy reported in Table VII is undefined and numerically inconsistent with the calibration-table sizes in Table VI; no code or artifact is linked despite a reference to an 'open-source link.' The contribution is significant if these numbers can be reproduced and the inconsistency resolved.","major_comments":[{"comment":"The accuracy metric behind Table VII is never defined, and the reported values are hard to reconcile with the calibration-table sizes. With Acc around 0.71-0.72 for S1-S3, the per-symbol error rate is about 0.29; at roughly two bytes per correction (one byte for v plus one byte for delta, since delta > 127 is extremely unlikely at this accuracy), a 296KB calibration table accounts for only about 150K corrected symbols. S1 alone has 2.16M edges and an 18MB structure, so its decimal-expanded, delimiter-augmented vector should contain millions of symbols, implying on the order of a million corrections and several megabytes of calibration data. If 'Acc' is instead per row, per node, or per edge, the paper must say so, because in that case the accuracy value cannot be used to bound the calibration table as the text does. Since the structure-compression gain is precisely 'model plus calibration table versus raw structure,' this inconsistency directly affects the reported disk-reduction and losslessness/efficiency claims. Please state the exact accuracy definition, give the resulting vector lengths for S1-S5, and show how the calibration-table byte counts follow from them.","section":"Section II-B (Calibration); Tables VI and VII"},{"comment":"The headline '18.3x faster query speed' is computed after a separate 'Warm up' phase that reconstructs the entire graph structure, and this warm-up takes 68-96 seconds on D1-D5. For point queries used in forensic investigation, this warm-up is part of the user-visible latency and is not amortized unless many queries are issued against the same reconstructed structure. The comparison with LEONARD and SEAL should either report end-to-end latency including warm-up for the evaluated 100-node query workload, or explicitly justify why excluding warm-up is the appropriate comparison for the intended use case.","section":"Section III-B (Query Speed); Table II"},{"comment":"The prediction procedure is not specified precisely enough to verify the lossless reconstruction claim. The text says the graph-structure vectors are inputs and 'predicted subsequent characters' are outputs, and that a fixed sequence is used as a starting point to obtain a predicted vector of equal length, but it does not describe the feature window, the autoregressive decoding loop, the choice of the fixed starting sequence, or the stopping criterion for 'accuracy stabilizes.' Without these details, a reader cannot reproduce the model, the calibration table, or the query-time reconstruction; please provide a precise algorithm or pseudocode for both training-time and inference-time prediction.","section":"Section II-B (Model Training and Inference)"}],"minor_comments":[{"comment":"The paper says LESS is faster in storage time and query speed than 'current approaches,' but Section III-B reports that SEAL has lower storage time and higher query speed than LESS. The summary should scope the headline comparison to LEONARD or explicitly state the trade-off with SEAL.","section":"Abstract and Section III-B"},{"comment":"The text mentions an 'open-source link,' but no code repository URL appears in the paper. Please include the artifact link, or state that the artifact will be released with the camera-ready version.","section":"Section III-A"},{"comment":"Algorithm 2 computes a minimum spanning tree over a similarity matrix that contains +infinity for out-of-window pairs and then applies a max-distance cutoff; if the resulting graph is disconnected, the output is a forest rather than a single tree. The pseudocode should specify how the chosen MST algorithm handles disconnected components.","section":"Section II-C (Algorithm 2)"},{"comment":"The sentence that the bag-of-words plus Manhattan distance 'is the number of different characters between the statistical attribute strings' is imprecise: the Manhattan distance between character-count vectors is the sum of absolute count differences, which is only an approximation of edit distance and not a count of differing character types.","section":"Section II-C (Similarity Matrix Computing)"},{"comment":"The x-axis labels in the locality histograms are densely packed and unreadable at print size; a cumulative distribution plot or binned histogram would convey the locality argument more clearly.","section":"Figure 3"},{"comment":"The text says tuning 'max depth' and 'n estimators' gives 'almost consistent accuracy' across S1-S5, but accuracy jumps from 0.7153 (S3) to 0.7683 (S4) when max depth changes from 1 to 3. Please clarify whether this jump is expected and how the hyperparameters are selected.","section":"Section III-C-5, Table VII"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the main technical blocker is the undefined accuracy metric and its apparent inconsistency with the calibration-table sizes. I would ask the authors to provide a precise definition of Acc, a worked example for one dataset (e.g., S1) showing vector length, number of corrections, and resulting calibration bytes, and ideally an artifact/code release. The paper's claims against SEAL should also be scoped more carefully. If the calibration numbers are corrected and the artifact confirms them, the paper could be a solid systems contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, here's my read on LESS (arXiv:2411.17091). The core idea is clean: split a provenance graph into structure and attributes, store the structure with a trained XGBoost model plus a calibration table for errors, and store attributes as a minimum spanning tree over attribute strings with edit operations as edge labels. That's a sensible engineering combination of LEONARD's learned-model storage and SEAL's structure/attribute split, and the losslessness argument is basically sound because the calibration table corrects every misprediction and the attribute tree records exact edit operations. The paper also gives a direct comparison against LEONARD and SEAL on DARPA TC and OpTC, which is useful.\n\nThe problem is that the numbers don't add up. Table VII reports per-symbol accuracy of 0.71 to 0.77 on S1-S5, but Table VI shows calibration tables of only 296KB to 1.32MB for those same datasets. At 71% per-symbol accuracy, around 29% of symbols are wrong. The vector for S1 has to be on the order of ten million symbols (18MB of structure, expanded with delimiters), so the calibration table should be several megabytes, not a few hundred KB. The paper never defines what 'Acc' means. If it is per row or per node, the calibration entries per incorrect row would be larger, not smaller. This is load-bearing because the structure-compression claim is model-plus-calibration-table versus raw structure. The reported 5.24x disk reduction and the lossless guarantee rest on this.\n\nThere are other soft spots: no code is released despite a mention of an open-source link, the XGBoost training procedure is underspecified (no learning rate, subsampling, stopping criterion beyond 'accuracy stabilizes'), and the query-speed metric excludes the warm-up time needed to rebuild the whole graph structure, which makes the comparison against LEONARD's per-query iterative prediction an apples-to-oranges game.\n\nAll of that said, the core framework is plausible and the attribute-tree part is a reasonable contribution. The paper is not circular: the model is trained on the data it stores, and the calibration makes it lossless. The accuracy/sizes inconsistency is likely fixable with a clear metric definition and a re-reported table, and the authors should release code. I'd send it to review, expecting major revision. If the numbers survive scrutiny, it's a useful systems paper for the provenance-storage community.","headline":"LESS has a sensible learned-storage design, but the reported accuracy and calibration-table sizes don't reconcile, which undercuts the headline compression numbers.","tokens_in":23709,"tokens_out":4928,"would_cite":false,"duration_ms":43759,"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":"LESS stores provenance graphs losslessly by learning the structure with XGBoost and arranging attributes as an edit-operation tree—6.29x faster storage, 5.24x less disk, 18.3x faster queries than the leading learned baseline.","keywords":["provenance graph storage","lossless compression","learned storage models","XGBoost","minimum spanning tree","audit log storage","attack investigation","calibration table"],"falsifier":"Using the vectorization and calibration procedures described in the paper, recompute the calibration-table size from the XGBoost model's actual mispredictions on one of the evaluation graphs. If, at the reported accuracy of about 0.71-0.77, the resulting table is much larger than the reported hundreds of kilobytes, then the accuracy metric is not per character and the lossless-compression claim needs re-derivation.","tokens_in":22738,"feed_emoji":"🗄️","tokens_out":12475,"duration_ms":108737,"temperature":0.7,"pith_summary":"LESS is a storage system for provenance graphs—the dependency graphs analysts use to trace how an attack unfolded. The paper's central claim is that a provenance graph can be stored losslessly by splitting it into structure (nodes and edges) and attributes (process names, timestamps, paths) and giving each half its own compression scheme: an XGBoost model learns the vectorized adjacency structure while a small calibration table fixes the model's mistakes, and a minimum attribute tree stores each attribute string as edit operations relative to a parent string so common text is recorded once. On the public benchmark datasets the authors report that LESS uses 5.24x less disk than the previous learned-storage system, stores 6.29x faster, answers queries 18.3x faster, and runs in 11.5% of the memory. The motivation is practical: defenders must keep audit logs for long periods, and any lossless scheme that makes archives smaller and queries quicker lowers the cost and latency of forensic investigation. The paper argues the split itself is the key insight, because the two halves have different redundancy profiles.","feed_headline":"Learned model plus attribute tree shrinks attack-log storage 5.24x","feed_subtitle":"Lossless scheme claims 6.29x faster writes and 18.3x faster queries on provenance graphs.","key_machinery":"Two mechanisms carry the compression. The first is a model-plus-calibration-table: XGBoost, a gradient-boosted decision tree whose size is controlled by max depth and number of trees, predicts the next symbol of a vectorized adjacency list, and a calibration table records every misprediction as an (offset, correct value) pair with a compact byte encoding; this pair converts a lossy predictor into an exact store. The second is the minimum attribute tree, a minimum spanning tree over attribute strings built from a similarity matrix of bag-of-words Manhattan distances, where each tree edge stores insertion, deletion, and substitution operations relative to its parent and overly distant strings are stored verbatim instead of as edits. Combined, these turn a provenance graph into three files whose total size the paper reports as roughly 2-3% of the uncompressed graph on the evaluation datasets.","core_discovery":"The authors set out to show that learned compression can be made lossless and fast for provenance graphs, and that the way to do it is to stop treating a graph as one object. They claim the structure and the attributes have different statistical profiles and therefore need different stores: the structure is delta- and run-length-encoded into a short alphabet, learned by an XGBoost classifier, and corrected by a calibration table of (offset, value) pairs; the attributes are turned into bag-of-words vectors, compared by Manhattan distance inside a sliding window, and organized into a minimum spanning tree whose edges record only the edit operations needed to transform a parent string into a child string. The final artifacts—a small model, a calibration table, and the attribute trees—are sufficient to rebuild the original graph exactly, so nothing is discarded. The experimental claim is that this combination beats the leading learned-storage baseline by 5.24x on disk, 6.29x on storage time, and 18.3x on query speed while using a fraction of the memory.","pith_inferences":["The same structure/attribute split should transfer to other repetitive semi-structured event graphs—network flows, telemetry streams, container runtime logs—where the skeleton is small and attributes repeat; that is a testable extension the paper does not attempt.","Since the bag-of-words and Manhattan-distance proxy discards character order, strings with the same characters in different orders will look artificially similar and generate more edit operations; a bounded n-gram encoding could raise compression at modest extra cost.","Allowing a child attribute to derive from any already-stored node, or sharing subtrees across many children, could cut redundancy further than a strict tree, at the price of more complex query path-finding."],"forward_implications":["If the numbers hold, long-term cyber defense could keep years of audit logs at a few percent of their raw size while still running backtrace and forward-trace queries on demand.","Because a query rebuilds the structure once in a warm-up phase and then follows parent pointers in the attribute tree, latency no longer scales with repeated model inference, the bottleneck of iterative learned approaches.","The split design makes each half independently replaceable: the paper explicitly notes that other machine-learning models can be substituted for XGBoost without changing the rest of the pipeline.","Losslessness means restored graphs can feed any downstream analysis—anomaly detection, graph reduction, attack investigation—exactly as the original would, and reduced or labeled graphs can be stored in the same format.","For very large graphs, the paper shows that slicing the input keeps storage and memory feasible; the cost is that slice boundaries must be tracked outside the system."],"supporting_citations":[{"why":"Provides the learned provenance-graph storage baseline that LESS is compared against; supplies its method and the comparative experimental setup.","marker":"[15]"},{"why":"Provides the query-friendly lossless compression baseline used for the storage-time and query-speed comparisons.","marker":"[18]"},{"why":"Defines the XGBoost gradient boosting model that learns the vectorized graph structure in LESS.","marker":"[12]"},{"why":"Defines edit distance, the similarity concept that motivates the bag-of-words/Manhattan-distance proxy for attribute strings.","marker":"[45]"},{"why":"Supplies the bag-of-words encoding used to turn attribute strings into vectors for similarity computation.","marker":"[57]"},{"why":"The main public dataset on which the headline disk, storage-time, memory, and query-speed numbers are measured.","marker":"[13]"}],"fun_headline_variants":["Lossless learned compression cuts provenance logs 5.24x","Split graph structure and attributes for 5.24x smaller logs","18.3x faster query and 6.29x faster write with learned store","Uses 11.5% the memory of prior art while compressing logs 5.24x","Provenance log store cuts disk 5.24x, write 6.29x, query 18.3x"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole scheme assumes that the two halves are compressible: the XGBoost model's prediction errors are few enough that the calibration table stays far smaller than the raw structure, and neighboring attribute strings are similar enough that edit-operation trees beat storing strings verbatim.","fun_headline_variants_meta":{"raw":{"variants":["Lossless learned compression cuts provenance logs 5.24x","Split graph structure and attributes for 5.24x smaller logs","18.3x faster query and 6.29x faster write with learned store","Uses 11.5% the memory of prior art while compressing logs 5.24x","Provenance log store cuts disk 5.24x, write 6.29x, query 18.3x"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000862,"raw_usage":{"total_tokens":3752,"prompt_tokens":970,"completion_tokens":2782,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":586,"completion_tokens_details":{"reasoning_tokens":2667}},"tokens_in":586,"tokens_out":2782,"duration_ms":17093,"temperature":1.0,"reasoning_tokens":2667,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:33:44.224421+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Using the vectorization and calibration procedures described in the paper, recompute the calibration-table size from the XGBoost model's actual mispredictions on one of the evaluation graphs. If, at the reported accuracy of about 0.71-0.77, the resulting table is much larger than the reported hundreds of kilobytes, then the accuracy metric is not per character and the lossless-compression claim needs re-derivation.","supporting_citations":[{"cited_title":"The case for learned prove- nance graph storage systems,","cited_arxiv_id":null,"evidence_quote":"Provides the learned provenance-graph storage baseline that LESS is compared against; supplies its method and the comparative experimental setup."},{"cited_title":"{SEAL}: Storage- efficient causality analysis on enterprise logs with query-friendly com- pression,","cited_arxiv_id":null,"evidence_quote":"Provides the query-friendly lossless compression baseline used for the storage-time and query-speed comparisons."},{"cited_title":"Learning string-edit distance,","cited_arxiv_id":null,"evidence_quote":"Defines edit distance, the similarity concept that motivates the bag-of-words/Manhattan-distance proxy for attribute strings."},{"cited_title":"Understanding bag-of-words model: a statistical framework,","cited_arxiv_id":null,"evidence_quote":"Supplies the bag-of-words encoding used to turn attribute strings into vectors for similarity computation."},{"cited_title":"Transparent computing,","cited_arxiv_id":null,"evidence_quote":"The main public dataset on which the headline disk, storage-time, memory, and query-speed numbers are measured."}],"review_version":1}