{"id":"547b8c91-0b43-41d1-9dd0-ff47f3bca2a0","arxiv_id":"2608.04905","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":7,"one_line_summary":"A dual-graph, reinforcement-and-imitation learning framework for MAPF that scales to 100,000 agents, with results close to search-based solvers on random maps.","lead":"PRIMAL3 is a learning-based system for multi-agent pathfinding that uses two communication graphs and a search-based teacher during training, and it claims to coordinate up to 100,000 simulated agents without the teacher at run time. It reports success rates near those of classical planners on random maps, but its largest-scale results rest on single test instances and on hyperparameters tuned to the benchmark.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The city-scale claim rests on an unverified per-timestep cost: Algorithms 1 and 2 require dense pairwise path-overlap computation and row-wise arg-max selection, and the paper reports no runtime, memory, or complexity data at 50k/100k agents.","rationale":"We agree with the reader: the weakest assumption is the per-timestep cost of A* reference paths and dense overlap construction. The moderate-scale evidence is internally consistent: the 32x32 comparisons, the 64-agent ablations, and the decay-factor landscape support a conditional acceptance in the evaluated regime. The city-scale claim, however, is precisely where the evidence stops: no runtime, single 50k/100k instances, no comparison against search-based solvers at those scales, and no explanation of how the dense matrices in Algorithms 1-2 are avoided. A secondary internal inconsistency is that Eq. 8 assigns 0.5 to non-opposite different-direction overlaps, but Algorithm 1 line 15 adds I[r_i(k)=r_j(l)], which is always 0 in that else branch; the stated conflict coefficient is therefore not implemented as written. This does not change the main verdict because the conflict graph still receives opposite-direction and stationary conflicts, but it should be corrected. The decay factors (gamma_conf=0.9, gamma_foll=0.5) are also selected after observing the evaluation benchmark, so the headline numbers are mildly optimistic. None of these points move the verdict: the paper is a useful contribution in the evaluated regime, but the city-scale scaling claim needs the missing feasibility evidence before it can be accepted as demonstrated.","tokens_in":24035,"tokens_out":8334,"duration_ms":113950,"concrete_test":"Require the authors to release the evaluation code and report, on the identical workstation, per-decision-step wall-clock time, peak memory, and Algorithm 1 overlap-event counts for N=1000,2000,...,10,000, plus the measured time for the 50,000 and 100,000 agent runs. The decisive check: fit per-step time versus N. If it grows roughly quadratically (time about 4x when N doubles) because of the dense overlap/argmax, or if no pruning mechanism is identified that avoids materializing O(n^2) overlap scores, then the city-scale claim is unsupported. Independently, re-derive the complexity of Algorithms 1-2 as written (O(n^2 L^2) naive, or O(E_overlap + n^2) if dense rows are materialized) and identify the mechanism that makes N=100,000 tractable on the reported hardware.","verdict_should_be":"UNCHANGED","load_bearing_attack":"PRIMAL3's central claim is that a learned decentralized policy coordinates 100,000 agents at city scale. For this to hold, Algorithms 1 and 2 must be executable at that scale at every decision step: each agent needs a fresh A* reference path (Section IV-A.1), the interaction matrices A_conf/A_foll must be populated by enumerating pairwise path overlaps (Algorithm 1), and each agent's top conflict/following neighbor must be extracted (Algorithm 2). The paper reports success rates and failure-load statistics but no wall-clock time, no memory use, and no asymptotic cost for any of these steps. Algorithm 1 as written iterates over all ordered agent pairs and all overlapping positions; Algorithm 2 then performs an arg max over a dense row for every agent. The text's sparsity argument ('each symmetrized graph contains at most N edges, average degree at most 2') only bounds the final communication graphs, not the dense computation needed to select those edges. At N=100,000 on roughly 500k-cell maps with paths of length ~700, even a spatial-hash implementation must process billions of overlap events per decision step unless an unstated sparsification or pruning scheme is used. The 50k/100k runs are also single unspecified instances, so a single favorable configuration could drive the result. This is the load-bearing weak point of the city-scale claim: not the per-agent policy, which plausibly transfers, but the per-timestep reference-path and pairwise-overlap computation required before the learned policy acts.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes PRIMAL3, a decentralized learning-based MAPF framework with three main components: a topology-aware dual-graph communication module that separates following and conflict interactions derived from A* reference-path overlaps, a LaCAM3-guided confidence-boosting training scheme that uses policy entropy to trigger selective expert interventions, and a priority-aware PIBT action-refinement shield that preserves the policy's fallback preferences. The evaluation compares against search-based solvers (LaCAM, LaCAM3, LNS2) and learning-based baselines (SYLPH, MAPF-GPT, HMAGAT) on 32x32 random and maze maps, reports success rates of 95-99% for up to 10,000 agents, describes success on single 50,000 and 100,000 agent instances, provides component ablations, and includes two real-robot demonstrations.","tokens_in":24441,"tokens_out":8925,"duration_ms":107340,"significance":"If the results hold, PRIMAL3 would be a meaningful step for learned MAPF: it shows that a decentralized policy with topology-aware communication can substantially narrow the gap to centralized search solvers at moderate scale and pushes the scale envelope of learned policies. The paper has clear strengths: the following/conflict graph separation is well motivated; the entropy-triggered selective use of LaCAM3 is a sensible way to spend expert queries; the priority-aware PIBT shield preserves action preferences; and the effective-failure-load analysis in Section V-C is a thoughtful way to compare policies under the all-agents-success criterion. The real-robot experiments, although small, support deployability. However, the current manuscript does not yet provide enough evidence for the headline city-scale and near-search-parity claims, and one part of the central graph-construction pseudocode is inconsistent with the equations.","major_comments":[{"comment":"Algorithm 1 is inconsistent with Eq. (7) and Eq. (8) in the non-opposite, both-nonzero, different-direction case. The else branch on line 15 adds I[r_i(k) = r_j(l)] * gamma_conf^k, but the branch is reached only when r_i(k) != r_j(l), so the indicator is always 0. Eq. (8) assigns rho_conf = 0.5 to this case, and the text and Fig. 2 say that different-direction overlaps should enter the conflict graph. As written, the pseudocode would discard exactly the soft different-direction conflict signal. Please correct the pseudocode and state which behavior was actually implemented.","section":"IV-A.2, Algorithm 1"},{"comment":"The city-scale claims in Section V-C rest on an unverified per-timestep cost. Algorithm 1 enumerates all ordered agent pairs and all overlapping positions between their reference paths, and Algorithm 2 performs a row-wise argmax over the dense matrices A_conf and A_foll. The sparsity argument in Section V-C ('each symmetrized graph contains at most N edges, average degree at most 2') bounds only the final communication graphs, not the dense computation needed to select those edges. At 50,000 or 100,000 agents, the reference-path computation and the pairwise overlap enumeration must be executed at every decision step, yet the paper reports no wall-clock time, no memory usage, and no asymptotic complexity for any scale. Without this information, or an explicit pruned implementation, the feasibility of the headline scaling result is not established.","section":"IV-A.2 and V-C"},{"comment":"The 50,000- and 100,000-agent results are based on two single instances, with no map side lengths, no instance specification, no repeated runs, and no information on how close the runs were to the horizon limit. A single favorable configuration is not sufficient evidence for the abstract's 'up to city-level 100,000 agents' claim. Please report multiple instances per scale, the exact map sizes, and the number of used timesteps.","section":"V-C, last paragraph"},{"comment":"The decay-factor sweep selects gamma_conf = 0.9 and gamma_foll = 0.5 on the same 32x32 maze 64-agent benchmark that is then used for the component ablation and for the headline 93.5% success rate. The full-model number is therefore the maximum of a tuning sweep on the evaluation set, and the ablated variants in Fig. 7 are compared at parameters chosen to favor the full model. This is a fitting-on-the-test-set concern. Please move the decay-factor selection to a validation set, or show that the ablation conclusions are unchanged over a range of decay settings.","section":"V-D2 / Fig. 8"},{"comment":"The claim that PRIMAL3 is 'almost on par' with LNS2 and LaCAM3 on random maps is not statistically supported. Fig. 5 reports no confidence intervals or significance tests for the 200 instances, and the comparison mixes time budgets: search-based solvers are allowed 30 seconds of planning time while PRIMAL3's wall-clock inference time is not reported. Please provide binomial confidence intervals for the success rates, report per-instance wall-clock time for all methods, and state the random-map generation protocol so that the comparison is interpretable.","section":"V-B and Fig. 5"}],"minor_comments":[{"comment":"The conclusion says 'scalability to instances with up to 10,000 agents,' but the abstract and Section V-C claim 50,000 and 100,000 agents; please make these statements consistent.","section":"VII"},{"comment":"The ablation is labeled 'w/o LaCAM* guidance' while the text mostly says LaCAM3; please standardize the terminology.","section":"Fig. 7"},{"comment":"The learned priority term s_prio_theta,i in Eq. (36) is never defined as a network output or given a training objective; please clarify where this quantity comes from.","section":"IV-C, Eq. (36)"},{"comment":"Equations (27) and (33) use epsilon_num inside the logarithm; since the action distribution is a softmax output it is already strictly positive, so this additive constant should either be removed or applied to the probability before the log.","section":"IV-B, Eqs. (27) and (33)"},{"comment":"The exact map side lengths for the 50,000 and 100,000 agent instances are missing; please include them with the other instance details.","section":"V-C"},{"comment":"A code release or a more detailed reproducibility appendix would strengthen the empirical claims; the current manuscript does not state whether code is available.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The main risk to acceptance is the gap between the abstract's city-scale claim and the evidence in Section V-C. If the authors can supply runtime and memory numbers and repeat the 50k/100k runs, the paper could be a strong contribution. I would also ask the editor to ensure the decay-factor tuning issue is addressed, since the headline ablation number is partly a fitted value. The related-work coverage is appropriate and the experimental breadth is impressive."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on PRIMAL3. The paper is a genuine step forward for learning-based MAPF: the dual following/conflict graph is a sensible way to split coordination into compatible and competing interactions, and the entropy-triggered LaCAM3 intervention is a clever trick to focus expert guidance where the policy is actually unsure. The moderate-scale results are credible and the ablations support each component. If I worked on learned MAPF, I'd want to build on this.\n\nThe soft spots are real, though. The headline 50k/100k-agent claim rests on two single instances with no runtime or memory numbers. Algorithms 1 and 2 require pairwise path overlaps and row-wise arg-maxes; at 100k agents that's an O(n^2) blow-up per decision step unless there's an unstated sparsification. The paper's sparsity argument only bounds the final communication graphs, not the dense computation needed to build them. That's the load-bearing weak point, and it's acknowledged only indirectly. Also, the decay-factor sweep was done on the evaluation benchmark, so the 93.5% ablation success rate is partly a fitted number. The main comparisons lack error bars and significance tests, and no code or hyperparameters are released.\n\nThat said, the central method holds up in the regime where it is carefully evaluated. The paper is honest about its limitations, including the hand-crafted features and LaCAM3 training overhead. The scaling narrative is ahead of the evidence, but not absurd: a policy with bounded communication could plausibly transfer to large teams if the reference-path and overlap computation were made efficient.\n\nWho should read it: anyone working on learned MAPF or on scaling reactive policies. The paper deserves a serious referee; an editor should send it out, because the architecture and the empirical gap over HMAGAT are worth careful checking. My own verdict would be conditional acceptance, with the authors required to either provide runtime/complexity data for the large-scale pipeline or soften the 50k/100k claims.","headline":"Solid incremental architecture with credible mid-scale results; the city-scale claim needs a runtime audit before it's taken at face value.","tokens_in":24923,"tokens_out":3138,"would_cite":false,"duration_ms":33699,"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":"PRIMAL3 claims a learned decentralized policy that coordinates up to 100,000 agents, reaching 95–99% success at 1,000–10,000 agents and nearly matching search-based solvers on random maps.","keywords":["multi-agent pathfinding","reinforcement learning","imitation learning","decentralized policy","graph communication","PIBT action refinement","LaCAM3 expert guidance","scalable MAPF"],"falsifier":"Run PRIMAL3's graph-construction steps (Algorithms 1 and 2) on a 100,000-agent instance and measure wall-clock time and memory per timestep; if they exceed the execution horizon of 2048 steps or available memory, the scaling claim fails.","tokens_in":23774,"feed_emoji":"🤖","tokens_out":4023,"duration_ms":42539,"temperature":0.7,"pith_summary":"PRIMAL3 aims to show that a learned, decentralized multi-agent pathfinding policy can scale to city-level problems that were previously the preserve of centralized search-based planners. The paper's central claim is that a policy trained with reinforcement learning plus selectively injected expert guidance reaches success rates of 95–99% on instances with 1,000 to 10,000 agents, completes single instances with 50,000 and 100,000 agents, and on random maps performs almost on par with state-of-the-art search-based solvers such as LNS2 and LaCAM3. The key is to make coordination graph-structured: one graph for agents moving in the same direction and one for agents competing for the same space, together with topology features that expose bottlenecks and dead ends. If the claim holds, learned reactive policies become a practical alternative to centralized replanning for large-scale fleets.","feed_headline":"A learned policy routes 100,000 agents","feed_subtitle":"PRIMAL3 keeps 95-99% success on thousands of agents and nearly matches search-based solvers.","key_machinery":"The load-bearing object is a pair of interaction graphs built from A* reference paths. A directed conflict graph weights opposing, stationary, and differently-oriented path overlaps with a discount factor $\\gamma_{\\mathrm{conf}}=0.9$, while a following graph weights same-direction overlaps with $\\gamma_{\\mathrm{foll}}=0.5$; each agent keeps at most one conflict neighbor and one following neighbor, updated only when the previous overlap vanishes. These graphs feed two separate communication branches: multihop gated aggregation for following relations, and masked attention with ego-difference encoding for conflict relations. Training uncertainty is measured by action entropy against a threshold of about 0.464, which gates when LaCAM3 intervenes. Execution uses a priority-aware PIBT shield, where PIBT is priority inheritance with backtracking, an online method that resolves vertex and edge conflicts by propagating priority; here its priority is a weighted combination of persistent age, a learned scalar, and normalized goal distance.","core_discovery":"PRIMAL3 claims that decentralized learning-based MAPF can be scaled far beyond previous limits by making both communication and action refinement sensitive to the type of interaction and the map's topology. The policy distinguishes path-compatible interactions, handled by multihop message passing on a following graph, from path-competing interactions, handled by masked attention on a conflict graph. During training, agents whose action distributions have high entropy are identified as uncertain, and for those agents the LaCAM3 planner supplies label-smoothed expert actions; in the late episode, unresolved agents follow a cached LaCAM3 plan. During execution, a priority-aware PIBT module uses persistent waiting times, learned priorities, and goal distances to keep actions collision-free while retaining the policy's fallback preferences. The result is a policy that does not need LaCAM3 at inference yet, on random 32x32 maps, reaches success rates from 1.00 down to 0.92 for 50 to 300 agents and, at ultra-large scale, maintains 95.0–99.0% success from 1,000 to 10,000 agents, with two single-instance demonstrations at 50,000 and 100,000 agents.","pith_inferences":["Editorial inference: The entropy-thresholded injection of an expensive search-based expert suggests a general training recipe: use a classical planner as a selective oracle only where the policy is uncertain, which could transfer to other multi-agent coordination tasks beyond MAPF.","Editorial inference: The paper does not report per-timestep runtime or the cost of computing pairwise path-overlap matrices; verifying that Algorithms 1 and 2 scale to 100,000 agents within the 2048-step horizon is the natural next test before deployment claims are accepted.","Editorial inference: Since the following and conflict graphs are built from reference paths, the approach could extend to lifelong MAPF by recomputing reference paths on goal changes, with the persistent age variable already providing the temporal memory that lifelong settings need."],"forward_implications":["A decentralized learned policy can solve one-shot MAPF instances with 100,000 agents, a scale previously unreported for learning-based methods, without invoking LaCAM3 at inference.","On random maps, learning-based MAPF can reach success rates close to centralized search-based solvers (LNS2 and LaCAM3), narrowing the long-standing gap between reactive policies and search.","Each agent communicates with at most one partner per interaction type, keeping average communication degree at most 2 regardless of team size, which is what makes the graph updates scale-independent.","The effective per-agent failure hazard of PRIMAL3 at 1,000–10,000 agents is about 16 times lower than HMAGAT's, meaning the success-rate gap widens predictably with team size rather than from a sudden policy collapse."],"supporting_citations":[{"why":"Defines the original PRIMAL hybrid RL-IL framework that PRIMAL3 extends.","marker":"[16]"},{"why":"Supplies the reference-path-overlap idea and communication-partner selection that the dual-graph construction builds on.","marker":"[24]"},{"why":"The LaCAM3 planner used as the training-time expert for entropy-triggered interventions and imitation targets.","marker":"[15]"},{"why":"HMAGAT is the strongest learning-based baseline and the hypergraph-communication approach that PRIMAL3 is compared against at ultra-large scale.","marker":"[20]"},{"why":"Establishes the PIBT-based action shielding for learned MAPF policies that the priority-aware refinement modifies.","marker":"[25]"},{"why":"Defines PIBT, the priority-inheritance-with-backtracking method underlying the execution-time action refinement.","marker":"[38]"},{"why":"LaCAM is a search-based baseline and the configuration-based search family from which LaCAM3 is engineered.","marker":"[14]"},{"why":"MAPF-LNS2 is the large-neighborhood-search baseline that PRIMAL3 matches or approaches on random maps.","marker":"[13]"}],"fun_headline_variants":["Scaling MAPF to 100k agents with learned coordination","PRIMAL3 clears 100,000-agent MAPF without search","RL-based MAPF for 100,000 agents, no search needed","City-scale pathfinding: PRIMAL3 routes 100k agents","Ultra-large MAPF: 100k agents via RL and imitation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The city-scale claim assumes that computing an A* path for every agent and the pairwise path-overlap matrices at each step stays fast enough at 100,000 agents, but the paper reports no runtime or memory scaling, so the practical feasibility is unverified.","fun_headline_variants_meta":{"raw":{"variants":["Scaling MAPF to 100k agents with learned coordination","PRIMAL3 clears 100,000-agent MAPF without search","RL-based MAPF for 100,000 agents, no search needed","City-scale pathfinding: PRIMAL3 routes 100k agents","Ultra-large MAPF: 100k agents via RL and imitation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000305,"raw_usage":{"total_tokens":1810,"prompt_tokens":1067,"completion_tokens":743,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":683,"completion_tokens_details":{"reasoning_tokens":651}},"tokens_in":683,"tokens_out":743,"duration_ms":8098,"temperature":1.0,"reasoning_tokens":651,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T13:50:50.379577+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run PRIMAL3's graph-construction steps (Algorithms 1 and 2) on a 100,000-agent instance and measure wall-clock time and memory per timestep; if they exceed the execution horizon of 2048 steps or available memory, the scaling claim fails.","supporting_citations":[{"cited_title":"Primal: Pathfinding via reinforcement and imitation multi- agent learning,","cited_arxiv_id":null,"evidence_quote":"Defines the original PRIMAL hybrid RL-IL framework that PRIMAL3 extends."},{"cited_title":"Social behavior as a key to learning-based multi-agent pathfinding dilemmas,","cited_arxiv_id":null,"evidence_quote":"Supplies the reference-path-overlap idea and communication-partner selection that the dual-graph construction builds on."},{"cited_title":"Improving learnt local mapf policies with heuristic search,","cited_arxiv_id":null,"evidence_quote":"Establishes the PIBT-based action shielding for learned MAPF policies that the priority-aware refinement modifies."},{"cited_title":"Lacam: Search-based algorithm for quick multi-agent pathfinding,","cited_arxiv_id":null,"evidence_quote":"LaCAM is a search-based baseline and the configuration-based search family from which LaCAM3 is engineered."},{"cited_title":"Mapf-lns2: Fast repairing for multi-agent path finding via large neighborhood search,","cited_arxiv_id":null,"evidence_quote":"MAPF-LNS2 is the large-neighborhood-search baseline that PRIMAL3 matches or approaches on random maps."}],"review_version":1}