{"id":"93e66090-41f5-4cbf-9cc2-55557e58e584","arxiv_id":"2607.26821","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":5,"one_line_summary":"Synthetic uniform edge weights systematically misrepresent parallel SSSP performance on real graphs, shifting optimal Δ and sometimes inverting algorithm rankings.","lead":"Parallel shortest-path algorithms are usually timed on graphs with fake uniform edge weights, but real graphs have very different weight patterns. That mismatch can flip which algorithm looks fastest and change the settings people tune, so current benchmarks can mislead.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"Representativeness of the 17-graph/6-synthetic sample, plus independent weight reassignment that erases topology–weight dependence, is the load-bearing limit on generalizing hierarchy inversion to benchmarking standards.","rationale":"The reader correctly isolated external validity of the graph/synthetic sample as the weakest link supporting the strongest claim; the additional dependence-structure confound is a concrete refinement of the same point rather than a new flaw. Empirical measurements inside the paper are careful and the sensitivity/Δ-tuning results are reproducible from the reported figures, so no downgrade to REJECT is warranted. The existing CONDITIONAL (pending artifacts and variance) already covers the practical caveats; the representativeness issue is precisely why the verdict should stay CONDITIONAL rather than move to ACCEPT. No internal inconsistency or calculation error was found that would overturn the on-sample claims.","tokens_in":22559,"tokens_out":616,"duration_ms":43260,"concrete_test":"Recompute algorithm rankings (Kendall τ of the 7 codes) on the existing graphs after replacing natural weights by a topology-aware null model that preserves the empirical weight–degree or weight–distance correlation (e.g., rewire weights inside degree bins or geographic distance bins). If τ(NAT, synthetic) rises above 0.7 and the number of strict inversions drops by more than half, the hierarchy-inversion claim is driven mainly by destroyed dependence rather than by the marginal distribution that benchmarks actually control.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (synthetic uniforms alter optimal Δ/ρ and can invert the tuned performance hierarchy vs natural weights) is internally well-supported by the per-distribution optimal sweeps (Figs. 2, 5, 6) and frontier-size diagnostics (Fig. 4) on the chosen instances. Its force as an indictment of community practice (Graph500, GAP, etc.) rests on two untested extrapolations: (1) that the 17 graphs (8 OSM roads + 9 skewed-degree from HipMCL/SuiteSparse/Benson) plus the six literature recipes in Table 2 adequately sample “real-world SSSP workloads,” and (2) that differences arise from the marginal weight distribution alone. In reality every synthetic trial independently redraws w(e) and therefore destroys any natural topology–weight correlation (road lengths vs geometry, similarity scores vs clusters, packet counts vs hubs). Section 7 explicitly flags the interplay [20] yet the experiments never isolate it; consequently the observed rank changes and sensitivity factors (Fig. 3) confound distribution shape with dependence structure. If either the sample or the independence assumption is unrepresentative, the leap from “on these graphs” to “benchmarking standards are biased” does not hold.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper argues that parallel SSSP benchmarking practice, which predominantly assigns synthetic uniform (or simple normal) edge weights to unweighted graphs, is disconnected from real-world weight distributions and thereby biases algorithm rankings and parameter choices. It statistically characterizes edge weights on 17 naturally weighted graphs (road networks from OSM plus skewed-degree graphs from HipMCL, SuiteSparse, and Benson repositories) via Clauset-style MLE/KS/likelihood-ratio fitting of body and tail, contrasts them with six literature synthetic recipes, and evaluates seven state-of-the-art parallel SSSP codes (GAP, GBBS, Wasp, Δ*-stepping, ρ-stepping, MultiQueue Dijkstra, parallel Bellman-Ford). The central empirical claims are that natural weights are typically log-normal in the body with heavy (often log-normal rather than pure power-law) tails, that synthetic uniforms alter optimal Δ/ρ and can invert tuned performance hierarchies relative to natural weights, and that synchronous Δ-based algorithms are more sensitive than asynchronous ones.","tokens_in":22952,"tokens_out":1350,"duration_ms":38906,"significance":"If the results hold under broader sampling, the work is significant for the parallel graph algorithms and HPC benchmarking communities: it supplies concrete evidence that a long-standing convenience assumption (uniform weights) is not neutral, supplies a reusable statistical characterization pipeline and public OSM road datasets, and yields actionable guidance (tune Δ/ρ on the target weight distribution; prefer asynchronous or carefully dynamic methods for robustness). Strengths include the breadth of the algorithm suite, full per-distribution retuning sweeps, frontier-size diagnostics that explain work and step-count effects, and explicit acknowledgment of large-n p-value collapse. The paper does not claim a new algorithm; its value is diagnostic and methodological.","major_comments":[{"comment":"§3.2 and §5–6: All synthetic trials independently redraw w(e) from a marginal distribution, destroying any natural topology–weight dependence (road length vs. geometry, similarity vs. clusters, packet counts vs. hubs). Section 7 explicitly cites the interplay literature [20] yet the experiments never isolate marginal shape from dependence structure. Consequently the reported rank inversions, sensitivity factors (Fig. 3), and Δ shifts (Fig. 6) confound the two. This is load-bearing for the claim that existing standards are biased; either an experiment that preserves empirical (topology, weight) pairs while reshaping the marginal, or a clearly scoped limitation that the results speak only to independent reassignment, is required before the indictment of Graph500/GAP-style practice can be stated at the present strength.","section":"§3.2, §5–7"},{"comment":"§1, §3.1 and §7: The leap from “on these 17 graphs + 6 literature recipes” to “current benchmarking methods unintentionally bias” and “challenge existing benchmarking standards” rests on an untested representativeness assumption. The sample is dominated by OSM roads and a handful of biological/co-authorship/traffic matrices; domain-specific semantics (bounded [0,1] similarities, integer co-authorship counts, extreme hubs in mawi) and implementation artifacts enter every comparison. A short, explicit external-validity paragraph stating which workload classes are and are not covered, and tempering the Graph500 indictment accordingly, is needed for the central claim to travel.","section":"§1, §3.1, §7"},{"comment":"§6.1 and Fig. 5: Aggregated Δ mis-tuning penalties are computed only over the intersection of Δ values that finished under a 10-minute cap across all implementations. Heavily mis-tuned points are therefore censored precisely where penalties would be largest, and the intersection size (average 22 points) is not reported per cell. This weakens the comparative robustness claims (e.g., “GBBS most robust”). Either complete the sweeps with a higher cap / early-stop reporting, or replace the geometric-mean penalty with a survival-style or winsorized statistic that makes the censoring explicit.","section":"§6.1, Fig. 5"}],"minor_comments":[{"comment":"Table 2 and §3.2: The half-normal absolute-value truncation of the two normal synthetics is a reasonable reading of prior work, but should be stated once in the table caption so readers do not have to reconstruct it from the text.","section":"Table 2"},{"comment":"Fig. 2 and Fig. 6: Marker conventions (square = integer, circle/hollow = float) are useful but easy to miss; a single legend entry repeated in both captions would help.","section":"Fig. 2, Fig. 6"},{"comment":"§2.3: MultiQueue is evaluated at fixed c=2, s=64 and labeled “parameter-free.” A one-sentence caveat that stickiness remains a latent parameter (as the authors themselves note) would avoid over-claiming.","section":"§2.3"},{"comment":"Observation 2 / Table 3: For the two road graphs where the pure power-law tail is not rejected, the %tail is ~0.009%. Emphasizing that the non-rejection is driven by extreme sparsity of the tail would prevent over-reading the PL column.","section":"Table 3"},{"comment":"Minor typographical: “assignes” → “assigns” (§3.2); “impor-” line break artifacts in the PDF; ensure all arXiv/DOI links resolve in the camera-ready.","section":null}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a solid empirical systems paper whose central measurements look reproducible and carefully executed. The main risk is over-generalization from an independent-weight design and a convenience sample; once the authors scope the claims and address the censoring in the Δ sweeps, it should be a useful contribution. Fit for a parallel/distributed or graph-algorithms venue is good; novelty is diagnostic rather than algorithmic, which some theory-heavy venues may undervalue."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing worth knowing is that they actually measured it. On 17 large naturally weighted graphs they fit body/tail models (log-normal body is the consistent story; tails are mixed PL/LN), then ran seven current parallel SSSP codes under six literature synthetics and showed that optimal Δ/ρ can jump orders of magnitude and that the tuned ranking can flip relative to the natural-weight baseline. That is new content, not a restatement of “Δ depends on weights.”\n\nWhat they do well: the Clauset-style pipeline at scale, the full retuning sweeps, the frontier-size traces that separate work from BSP step count, and the clear split between synchronous codes (sensitive) and the more asynchronous ones (MQ, Wasp). Figures 2–6 and Table 3 back the claims without circular math. Sensitivity factor and mis-tuning penalty are just summaries of observed numbers. Citations look normal for the subfield; they release the OSM conversions.\n\nSoft spots, in proportion. The leap from “on these graphs” to “benchmarking standards are biased” is the softest part. The 17-graph set is heavy on OSM roads plus a handful of HipMCL/SuiteSparse/Benson matrices; domain weight semantics differ a lot. More importantly, every synthetic trial redraws weights independently, so it erases any natural topology–weight correlation. They cite the interplay paper and note it in the discussion, yet the experiments never isolate shape from dependence. That confounds the sensitivity numbers if you want to indict Graph500 in general. Minor practical limits: some Δ sweeps hit the ten-minute wall, GBBS had correctness issues for Δ<1 on roads, and the public artifact story is incomplete. None of that sinks the core measurements.\n\nThis is for people who build or evaluate parallel graph kernels and anyone who still defaults to U[0,1) or U[1,255]. Worth a reading-group slot if your group cares about benchmarking honesty. I would cite the characterization and the hierarchy-inversion results. Send it to referees; it deserves the time even if they push on external validity and ask for a dependence-preserving generator experiment.","headline":"Solid empirical systems paper: natural vs synthetic weights really do retune and reorder SOTA parallel SSSP; the indictment of Graph500-style practice is directionally right but rests on sample and independence assumptions the authors partly flag themselves.","tokens_in":23536,"tokens_out":552,"would_cite":true,"duration_ms":17323,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Synthetic uniform edge weights change which parallel SSSP algorithms win and how they must be tuned, relative to natural weights on real graphs.","keywords":["parallel SSSP","edge-weight distribution","Δ-stepping","benchmarking bias","log-normal weights","parameter tuning","asynchronous shortest paths"],"falsifier":"Re-run the same seven implementations on a substantially larger or differently sampled set of naturally weighted graphs (or on production workloads whose weights follow neither the paper's log-normal bodies nor the six synthetics) and check whether optimal Δ/ρ values and algorithm rankings still diverge systematically from the uniform-weight baselines.","tokens_in":23422,"feed_emoji":"⚖️","tokens_out":852,"duration_ms":16692,"temperature":0.7,"pith_summary":"Most parallel single-source shortest-path algorithms are benchmarked on graphs whose edge weights are drawn from simple synthetic recipes, usually uniform. Real networks instead carry heavy-tailed or log-normal weights whose body and tail look nothing like those recipes. Because bucket width, step count, and redundant work all depend on the weight distribution, the synthetic choice is not a neutral label: it changes optimal parameters and can reverse which implementation is fastest. The paper fits the empirical weight distributions of seventeen large road, traffic, social, semantic and biological graphs, contrasts them with six literature synthetics, and times seven state-of-the-art parallel SSSP codes under every combination. The result is that current practice systematically misrepresents real-world ranking and tuning, so benchmarks and algorithm design must treat weight distribution as a first-order variable.","feed_headline":"Uniform weights flip which shortest-path codes win","feed_subtitle":"On real graphs the same algorithms rank and tune differently than under the synthetic weights used in benchmarks","key_machinery":"Side-by-side statistical characterization (Clauset-style MLE, KS, likelihood-ratio tests of body and tail) of seventeen natural weight distributions versus six literature synthetics, followed by exhaustive Δ/ρ sweeps and timed runs of seven parallel SSSP implementations, which together quantify sensitivity, mis-tuning penalty, and ranking inversion.","core_discovery":"Evaluating parallel SSSP with the synthetic uniform weights common in the literature alters optimal parameter configurations and can invert the observed performance hierarchy relative to the same algorithms run on naturally weighted real-world graphs; edge-weight distribution is a first-order driver of both computational work and the structure of synchronous steps.","pith_inferences":["The same weight-sensitivity critique likely extends to other weight-dependent graph kernels (betweenness, hop-constrained paths, weighted matching) that are still routinely evaluated under uniform synthetics.","Once weight generators become statistically faithful, automated or online Δ/ρ adaptation may become more valuable than further hand-tuned static defaults.","Topology–weight coupling (hubs that force regression to Bellman–Ford behaviour) suggests that synthetic generators must also preserve joint structure, not only marginal weight histograms."],"forward_implications":["Default or portable Δ and ρ values tuned on uniform weights are unreliable on real graphs and must be re-tuned to the target weight distribution.","Asynchronous or relaxed-priority designs show lower sensitivity to weight variation than strictly synchronous Δ-stepping variants and are therefore preferable when weight distributions are unknown or highly skewed.","Future public benchmarks should replace or augment uniform weights with generators whose body and tail match the log-normal-plus-heavy-tail pattern observed on real data.","Algorithm designers should treat weight distribution as a first-class input when claiming practical superiority, not merely topology or core count."],"fun_headline_variants":["Synthetic weights invert SSSP algorithm rankings","Uniform edge weights mislead parallel SSSP benchmarks","Real graph weights reorder shortest-path code winners","Edge-weight distribution flips SSSP params and hierarchy","Natural weights change which parallel SSSP codes win"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The seventeen chosen natural graphs and six literature synthetic recipes are representative enough of real workloads and community practice that the observed bias and hierarchy inversions indict existing benchmarking standards in general.","fun_headline_variants_meta":{"raw":{"variants":["Synthetic weights invert SSSP algorithm rankings","Uniform edge weights mislead parallel SSSP benchmarks","Real graph weights reorder shortest-path code winners","Edge-weight distribution flips SSSP params and hierarchy","Natural weights change which parallel SSSP codes win"]},"model":"grok-4.5","effort":"low","cost_usd":0.004616,"raw_usage":{"total_tokens":1273,"prompt_tokens":701,"num_sources_used":0,"completion_tokens":53,"cost_in_usd_ticks":46164000,"prompt_tokens_details":{"text_tokens":701,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":519,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":701,"tokens_out":53,"duration_ms":9486,"temperature":1.0,"reasoning_tokens":519,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T20:03:45.195418+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Re-run the same seven implementations on a substantially larger or differently sampled set of naturally weighted graphs (or on production workloads whose weights follow neither the paper's log-normal bodies nor the six synthetics) and check whether optimal Δ/ρ values and algorithm rankings still diverge systematically from the uniform-weight baselines.","supporting_citations":[],"review_version":1}