{"id":"7d1d3f07-c3c7-4bdf-ad9d-1bafa7781093","arxiv_id":"2411.16667","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"OPMOS parallelizes the NAMOA* multi-objective shortest-path search by popping batches of labels while preserving priority order, reporting a geometric mean 34x speedup on 72 Arm cores.","lead":"OPMOS is a parallel algorithm for finding exact trade-off routes in graphs with many objectives at once. On a 72-core Arm CPU it reports a geometric mean 34x speedup over a standard sequential method for five real ship-routing problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exactness of OPMOS rests on an unproved relaxed-ordering invariant; solution-count matching on five routes is insufficient evidence, and a full-set or ground-truth comparison is needed.","rationale":"The reader's weakest_assumption identifies the same load-bearing concern: OPMOS's exactness relies on a label-setting invariant that is neither proved nor convincingly validated. The paper's Section 5.1 explicitly relaxes NAMOA*'s global ordering by popping NUM_POP labels per iteration and processing them asynchronously, so workers can act on stale frontiers. My analysis of the algorithm suggests that premature closing may be safe for exactness because dominance is transitive: any pruned label that was dominated by the premature label will also be dominated by the later label that dominates the premature label. However, this is exactly the kind of argument the paper should provide, and it does not. The empirical check in Section 7.4 only matches solution counts, which is a weak test for set equality; a missing Pareto-optimal cost vector and an extra dominated one would still leave the count unchanged in principle. Since the paper's strongest claim is the combination of exactness and speedup, and the speedup figure would be misleading if the solver were approximate, this concern must be resolved before the result can be treated as a benchmark. The proposed test — comparing full Pareto sets across parameter sweeps, including brute-force ground truth on small graphs — would settle whether the concern lands. I do not see a demonstrated internal inconsistency in the algorithm, only an unproven and insufficiently tested invariant, so the reader's CONDITIONAL verdict is appropriate; no verdict change is needed.","tokens_in":28,"tokens_out":10518,"duration_ms":172291,"concrete_test":"Run OPMOS and sequential NAMOA* on the five TMPLAR routes and on small random graphs (tens of nodes, 3-5 objectives) with brute-force-enumerable ground-truth Pareto fronts; compare full sets of cost vectors (not just sizes) across NUM_POP in {1, 8, 64, 256, max} and NUM_THDS in {2, 16, 64, 128}. If any OPMOS run omits a cost vector present in the brute-force front or in sequential NAMOA*, the exactness claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that OPMOS preserves NAMOA*'s exact Pareto-optimal set while achieving 34x speedup (Section 7.4, Table 3). This claim requires that the batched, asynchronous execution in Algorithm 2 never loses a label that would appear in the exact front. The paper does not prove this. In Section 5.1, OPMOS relaxes NAMOA*'s global label ordering: the main thread pops NUM_POP labels at once, and worker threads process them against PZR/PQ/e without seeing updates generated by other workers in the same batch (Algorithm 2, lines 32-40 vs. 21-22). A label can therefore be closed, or used to prune other labels, before a dominating label produced in the same batch is applied. The only empirical support offered is Section 7.4's statement that the 'total number of solutions' match between sequential and OPMOS runs — a count, not a comparison of the actual Pareto sets. Counts can agree while the sets differ (e.g., one missing solution offset by spurious duplicates would not be detected by size alone). Because the headline speedup is only meaningful if the solver is exact, this unproved invariant is the load-bearing weak point. It may be salvageable — dominance transitivity suggests premature closing could merely add redundant work rather than drop solutions — but that argument is not made, and no formal verification, artifact, or set-level comparison is provided.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents OPMOS, a parallel multi-objective shortest-path algorithm that parallelizes NAMOA* by extracting multiple labels per iteration from a shared priority queue (NUM_POP), processing them asynchronously on worker threads, and using a label-complexity-aware load-balancing scheme. The authors report a geometric mean 34x speedup over their sequential NAMOA* baseline on a 72-core Arm CPU across five TMPLAR maritime ship-routing graphs, and claim that OPMOS preserves the exact Pareto-optimal solution set.","tokens_in":23481,"tokens_out":7075,"duration_ms":68674,"significance":"If the exactness claim is substantiated, the paper makes a valuable contribution: it is the first single-instance parallel MOS algorithm that handles an arbitrary number of objectives, and the reported speedups (17x-57x per route) are substantial. The paper deserves credit for internally consistent evaluation: Table 3 yields the stated geometric mean 34x, and the ablation studies (FIFO vs. PQ, synchronous vs. asynchronous updates, alternative load balancers) provide useful evidence for the design choices. The principal weakness is that the central correctness claim, exact Pareto-front preservation, is asserted without a formal proof and is validated only by matching solution counts on five routes, which is a weaker check than set equality.","major_comments":[{"comment":"There is no proof that the relaxed label ordering preserves the exact Pareto front. Sequential NAMOA* (Algorithm 1, line 6) pops one label per iteration in global lexicographic order; OPMOS pops NUM_POP labels at once, and worker threads process labels from the previous iteration without seeing updates generated by other workers in the current batch (lines 21-22 versus 32-40). This can cause a label to be expanded, and to prune labels from PZR/PQ, before a dominating label produced by a concurrent worker is applied to the shared data structures. The exactness claim in Section 7.4 therefore lacks direct formal support. The authors should either provide a correctness invariant (e.g., showing, via dominance transitivity, that any label pruned as a result of premature expansion is also pruned by the eventual dominator, and that no Pareto-optimal label is lost), or exhibit a counterexample. The current manuscript does neither.","section":"Section 5.1, Algorithm 2 (lines 9-16 and 32-40)"},{"comment":"The empirical evidence for exactness is the statement that 'the total number of solutions obtained from the sequential MOS match perfectly with OPMOS for all experiments'. Matching solution counts is insufficient to establish that the Pareto-optimal sets are identical: counts can agree while the sets differ, for example if one true label is missing and one spurious duplicate is counted. To support the exactness claim, the authors should compare the actual sets of Pareto-optimal labels (cost vectors or reconstructed solution paths) between sequential NAMOA* and OPMOS for all configurations reported in Table 3 and Figures 5-10, and ideally also against an independent sequential implementation.","section":"Section 7.4"}],"minor_comments":[{"comment":"The text says 'routes 2 and 4 only complete 4 and 6 objectives in this time limit', but Table 2 shows Route 2 completing 4 objectives and Route 5 completing 6. This is presumably a typo: it should say 'routes 2 and 5'.","section":"Section 6.1, Table 2"},{"comment":"The formal definition of dominance is garbled by non-standard symbols: 'W(X)[a]↘W(Z)[a]' and 'W(X)[a] < W(Z)[a]' should be expressed with conventional notation (componentwise less-or-equal and at least one strict inequality). Similarly, the symbols '↗' and '↔' are hard to parse; please use standard relation symbols.","section":"Section 3, dominance definition"},{"comment":"The nomenclature for the bag data structures (wbag_TUM, wbag_MNVW, cbag_TUM, cbag_MNVW) is difficult to follow, especially the logical swapping described in the text. Clarify the roles of the current-iteration and next-iteration bags, and use consistent names across the prose and the pseudo-code.","section":"Section 5.1 and Algorithm 2"},{"comment":"The per-label comparison density scatter plots are informative but visually dense; the color and point-size encoding is hard to read at publication size. Consider using logarithmic axes or faceting by objective count to improve readability.","section":"Figure 3"},{"comment":"The text reports 'execution time of 3 milliseconds' for two objectives, but Figure 2 uses normalized values. Providing the absolute runtimes for both low and high objective counts would make the characterization more concrete.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The exactness issue is the main barrier to acceptance. If the authors provide a rigorous correctness proof, or at least a thorough set-level empirical validation, the paper could be acceptable after revision. A secondary concern is the absence of an independent baseline beyond the authors' own sequential implementation; this is mitigated by the lack of a widely available practical parallel MOS baseline for more than two objectives, but the authors should state this limitation explicitly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"OPMOS is a real systems contribution. It gives the first single-instance parallel MOS algorithm I know of that handles an arbitrary number of objectives, with a sensible design: batch label extraction from a global priority queue, asynchronous updates, and a label-aware load balancer. The experimental work is careful. The ablations against FIFO, synchronous updates, and alternative schedulers are exactly what you want to see, and the measured 34x geometric-mean speedup over their sequential NAMOA* on 72 cores is plausible given the numbers and the runtime breakdowns. The ship-routing graphs from TMPLAR, with up to 12 objectives, are more realistic than the synthetic benchmarks in most of this literature.\n\nThe load-bearing problem is exactness. Sequential NAMOA* gets its exact Pareto set from a global lexicographic order on label processing. OPMOS deliberately relaxes that order: the main thread pops NUM_POP labels at once, workers process them without seeing same-iteration updates, and updates are applied asynchronously. The paper nowhere proves that this relaxed execution never closes or prunes a label that would appear in the exact set. The only evidence is a sentence in Section 7.4 saying the total number of solutions matches sequential MOS. That is not enough. Counts can agree while the fronts differ, and a number does not tell you whether the missing solution is Pareto-optimal. The stress-test note is right that this is the weak point.\n\nI also want flags: the benchmark graphs and code are not released, the sequential baseline is their own implementation, and the timings appear to be single-run. Those are common in systems papers, but they make independent verification harder. None of this kills the paper. The relaxed-order invariant is plausibly true — premature closing might merely add redundant work rather than drop solutions, as the note says — but the argument needs to be made. A formal proof would be ideal; a set-level comparison on all routes and objective counts, ideally with artifacts, is the minimum.\n\nWho is this for? People working on multi-objective search, parallel graph algorithms, and maritime decision support. It deserves a serious referee. I would send it to review, but insist that the exactness claim be backed by either a proof or a full Pareto-set comparison, and strongly encourage releasing the code and data.","headline":"OPMOS is a genuinely new parallel take on multi-objective shortest paths with impressive measured speedups, but its exactness claim rests on an unproved relaxed-ordering invariant and only count-level empirical support.","tokens_in":23986,"tokens_out":2505,"would_cite":false,"duration_ms":23963,"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":"OPMOS computes the exact Pareto-optimal route set 34x faster in parallel.","keywords":["multi-objective shortest path","Pareto-optimal","parallel algorithm","NAMOA*","priority queue","load balancing","ship routing","exact search"],"falsifier":"Run OPMOS and the sequential NAMOA* on small graphs whose exact Pareto front can be enumerated exhaustively, across several lexicographic orderings and batch sizes larger than one; if any cost vector in the sequential front is missing from OPMOS's output, or the two fronts have equal size but different vectors, the exactness claim is false.","tokens_in":23003,"feed_emoji":"🚢","tokens_out":8424,"duration_ms":73918,"temperature":0.7,"pith_summary":"The paper proposes OPMOS, a parallel version of the multi-objective A* search algorithm NAMOA*, and claims that it produces the same exact Pareto-optimal route set as the sequential algorithm while running far faster. The problem is multi-objective shortest-path search, where each edge carries a vector of costs and the answer is the set of mutually non-dominated routes. OPMOS keeps a single lexicographically ordered priority queue, extracts several labels per iteration, distributes them across worker threads, and applies updates asynchronously to hide queue latency. On a 72-core Arm CPU, using real-world maritime ship-routing graphs with up to twelve objectives, the paper reports a geometric mean 34x speedup over sequential NAMOA* while matching the sequential solution counts exactly. If the correctness claim holds, exact many-objective route planning becomes practical on ordinary multicore CPUs rather than only on special-purpose hardware.","feed_headline":"OPMOS computes the exact Pareto-optimal route set 34x faster in parallel","feed_subtitle":"Batching priority-queue labels across 64 worker threads keeps the full trade-off front while cutting runtime.","key_machinery":"The central mechanism is batched ordered extraction from one lexicographic priority queue, paired with asynchronous update application. A label is a partial path from the start node to some node, carrying a cost vector; NAMOA* orders these labels by lexicographic lower-bound estimates of total goal cost. OPMOS extracts NUM_POP labels per iteration, passes them to worker threads, and lets the main thread apply queue inserts and deletions concurrently, with deletions marked in per-node label sets and resolved lazily at extraction time. A second mechanism is a label-aware load balancer: goal-node labels are handled separately from regular labels, their pruning searches are spread across nodes, and regular labels' neighbor expansions are divided into chunks sized by estimated cost per thread.","core_discovery":"In the paper's own terms, the central result is that ordered parallelism is compatible with exact multi-objective search: OPMOS pops NUM_POP labels at a time from OPEN, a priority queue ordered lexicographically by estimated cost vector, lets worker threads process those labels' expansions and dominance and pruning checks without seeing the current iteration's updates, and has the main thread apply all updates asynchronously. The claimed consequence is that the exact Pareto-optimal solution set is preserved for an arbitrary number of objectives, because in many-objective search most high-priority labels are close to the global Pareto front and batching them costs little work efficiency. The measured consequence is a geometric mean 34x speedup over sequential NAMOA* using 64 worker threads and 256 labels per iteration.","pith_inferences":["The paper's exactness evidence is empirical: total solution counts match on five routes, but the full Pareto-optimal sets are not compared. A formal invariant proof, or a counterexample on a small graph, would settle whether batch extraction and lazy pruning can ever discard a needed label.","The speedup is strongest at high objective counts; at two objectives work inefficiency nearly cancels parallelism. Adapting NUM_POP and worker count to objective count and label complexity is a natural next step.","The same batched-extraction scheme could be ported to vector hardware such as GPUs, where thousands of labels could be popped at once, but the asynchronous update path and load balancer would need redesign for massively parallel execution."],"forward_implications":["OPMOS gives decision-makers the full Pareto-optimal route front, not an approximation, for problems with an arbitrary number of objectives.","Runs that took tens of minutes on one core shrink to tens of seconds or a few minutes, expanding the practical size and objective count of exact MOS instances.","Relaxing global label order while staying close to the Pareto-optimal front is a viable parallelization strategy for MOS, so exact multi-objective search need not be strictly sequential.","The asynchronous model moves the bottleneck from priority-queue latency to load balance, and the proposed scheduler is what keeps imbalance from dominating.","The techniques can be dropped into existing ordered graph-processing pipelines, extending their reach beyond ship routing."],"supporting_citations":[{"why":"Supplies the sequential NAMOA* label-setting algorithm and consistent-heuristic framework that OPMOS parallelizes.","marker":"[15]"},{"why":"Provides the theoretical parallel label-setting model for two objectives that motivates close-to-priority extraction.","marker":"[26]"},{"why":"Survey that identifies parallel MOS as an open problem and frames ordering and lexicographic choice as key challenges.","marker":"[25]"},{"why":"Supplies the real-world multi-objective ship-routing graph generator and the routes used in evaluation.","marker":"[30]"},{"why":"Documents the 72-core Arm CPU platform on which all speedups are measured.","marker":"[19]"},{"why":"Weather reanalysis dataset from which the wave and weather objective values in the graphs are derived.","marker":"[10]"},{"why":"Represents the approximation approach that OPMOS deliberately avoids in order to keep exact solutions.","marker":"[37]"},{"why":"Establishes NP-hardness of the exact Pareto front, motivating acceleration work.","marker":"[27]"}],"fun_headline_variants":["OPMOS: exact Pareto-optimal paths, 34x faster via parallel batching","Parallel batching gives exact MOS search a 34x speedup on 64 threads","OPMOS achieves 34x speedup for exact multi-objective shortest paths","Exact multi-objective routing, 34x faster with ordered parallel batching","34x faster: OPMOS keeps exact Pareto frontier with parallel label batching"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that removing several partial routes from the priority queue at once, and processing them before the batch's newly discovered routes are added back, still produces every route needed for the exact Pareto-optimal answer; the paper supports this only by matching route counts on five test cases, with no formal proof.","fun_headline_variants_meta":{"raw":{"variants":["OPMOS: exact Pareto-optimal paths, 34x faster via parallel batching","Parallel batching gives exact MOS search a 34x speedup on 64 threads","OPMOS achieves 34x speedup for exact multi-objective shortest paths","Exact multi-objective routing, 34x faster with ordered parallel batching","34x faster: OPMOS keeps exact Pareto frontier with parallel label batching"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000272,"raw_usage":{"total_tokens":1622,"prompt_tokens":926,"completion_tokens":696,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":542,"completion_tokens_details":{"reasoning_tokens":589}},"tokens_in":542,"tokens_out":696,"duration_ms":6339,"temperature":1.0,"reasoning_tokens":589,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:50:23.025598+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run OPMOS and the sequential NAMOA* on small graphs whose exact Pareto front can be enumerated exhaustively, across several lexicographic orderings and batch sizes larger than one; if any cost vector in the sequential front is missing from OPMOS's output, or the two fronts have equal size but different vectors, the exactness claim is false.","supporting_citations":[{"cited_title":"Luis Pérez De La Cruz","cited_arxiv_id":null,"evidence_quote":"Supplies the sequential NAMOA* label-setting algorithm and consistent-heuristic framework that OPMOS parallelizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the theoretical parallel label-setting model for two objectives that motivates close-to-priority extraction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Survey that identifies parallel MOS as an open problem and frames ordering and lexicographic choice as key challenges."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Documents the 72-core Arm CPU platform on which all speedups are measured."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Represents the approximation approach that OPMOS deliberately avoids in order to keep exact solutions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of the exact Pareto front, motivating acceleration work."}],"review_version":1}