Pairwise is Not Enough: Hypergraph Neural Networks for Multi-Agent Pathfinding
Authors: Rishabh Jain
Keisuke Okumura
Michael Amir
Pietro Lio
Amanda Prorok
Venue: ICLR 2026 Poster (2026)
Keywords: hypergraph
group interaction modeling
imitation learning
MAPF
Primary area: applications to robotics, autonomy, planning

Abstract: Multi-Agent Path Finding (MAPF) is a representative multi-agent coordination problem, where multiple agents are required to navigate to their respective goals without collisions. Solving MAPF optimally is known to be NP-hard, leading to the adoption of learning-based approaches to alleviate the online computational burden. Prevailing approaches, such as Graph Neural Networks (GNNs), are typically constrained to *pairwise* message passing between agents. However, this limitation leads to suboptimal behaviours and critical issues, such as attention dilution, particularly in dense environments where group (i.e. beyond just two agents) coordination is most critical. Despite the importance of such higher-order interactions, existing approaches have not been able to fully explore them. To address this representational bottleneck, we introduce HMAGAT (Hypergraph Multi-Agent Attention Network), a novel architecture that leverages attentional mechanisms over directed hypergraphs to explicitly capture group dynamics. Empirically, HMAGAT establishes a new state-of-the-art among learning-based MAPF solvers: e.g., despite having just 1M parameters and being trained on 100$\times$ less data, it outperforms the current SoTA 85M parameter model. Through detailed analysis of HMAGAT's attention values, we demonstrate how hypergraph representations mitigate the attention dilution inherent in GNNs and capture complex interactions where pairwise methods fail. Our results illustrate that appropriate inductive biases are often more critical than the training data size or sheer parameter count for multi-agent problems.

Published as a conference paper at ICLR 2026
PAIRWISE IS NOT ENOUGH: HYPERGRAPH NEURAL NETWORKS FOR MULTI-AGENT PATHFINDING
Rishabh Jain', Keisuke Okumura! 1.2 Michael Amir', Pietro Liö', Amanda Prorok University Cambridge, UK 2 National Institute of Advanced Industrial Science and Technology (AIST), Japan {rj412 ko393, ma 151, p121 9, asp45) esst. cam. ac .uk
ABSTRACT
Multi-Agent Path Finding (MAPF) is representative multi-agent coordination problem, where multiple agents are required to navigate to their respective goals without collisions. Solving MAPF optimally is known to be NP-hard, leading the adoption of learning-based approaches to alleviate the online computational burden. Prevailing approaches, such as Graph Neural Networks (GNNs), typ- ically constrained to pairwise message passing between agents. However, this limitation leads to suboptimal behaviours and critical issues, such as attention dilution, particularly in dense environments where group (i.e. beyond just two agents) coordination is most critical. Despite the importance of such higher-order interactions, existing approaches have not been able to fully explore them. To ad- dress this representational bottleneck, we introduce HMAGAT (Hypergraph Multi- Agent Attention Network), a novel architecture that leverages attentional mechan- isms over directed hypergraphs to explicitly capture group dynamics. Empirically. HMAGAT establishes a new mate-of-the-art among learning-based MAPF solvers: e.g., despite having just 1M parameters and being trained on 100x less data, it outperforms the current SoTA 85M parameter model. Through detailed analysis EMAGAT'S attention values, we demonstrate how hypergraph representations mitigate the attention dilution inherent in GNNs and capture complex interactions where pairwise methods fail. Our results illustrate that appropriate inductive bi- are often more critical than the training data size or sheer parameter count for multi-agent problems.
INTRODUCTION
Multi-agent coordination is fundamental topic in multi-agent systems, where multiple agents work together to achieve a common goal. Applications include warehouse automation (Wurman et al.) 2008), autonomous driving (Shalev-Shwartz al. (016), traffic management (Adler & Blue 2002) and manufacturing process control (Leng et al. (002).. These settings involve complex interactions and dependencies among agents. In the literature, such interactions are typically modelled
pairwise manner, using graph neural networks (GNNs) or transformers (Bernárdez et al., [2023 Liu
al. 2024 Li et al. 2024b). However, pairwise interactions are insufficient to fully capture highly- coupled multi-agent dynamics, where interactions may involve multiple agents simultaneously.
This insufficiency has led to the exploration of higher-order representational structures, such as hypergraphs, which can naturally model group interactions. Recent works have shown that hyper- graphs can effectively model small-scale multi-agent problems (Zhu al. 2024| /Zhao et al. (025) and simple group interactions, like social groups in trajectory prediction tasks (Lin al. 2024 Xu
cct al. 2022). However, the question remains, "Can hypergraphs scale beyond simple group settings to capture the dynamics of complex, highly-coupled multi-agent tasks?"
In this work, we provide a positive answer to this question by focusing on one such problem of multi-agent pathfinding (MAPF), where the goal is to compute collision-fre free paths that efficiently guide a team of agents to their respective destinations. Optimally solving MAPF is known to be NP-hard (Surynek 2010), in sparse grids (Geft & Halperin 2022). which highlights the strong

---

Published as a conference paper at ICLR 2026
(a)
6
(Rt)
(te)
(0)
cost( A)
(Ost(A)
cost 6
cast(B)
cost
(C)
D)
(D)
SoC
SoC
25
cost(
coot
(ost(B)
cust CC) 6
cost (D) 6
(b)
(c)
HMAGAT (1M)
MAPP-OPT (5SM)
MAPF-CPP (Ph)
MAGAT (0.79M)
MAPF-3PT-006 (2M)
20
Grerel sa Quality
Hagi Quality
-SCTTM
2024
xSSIL
RVAH
HIMAGAT (this work)
XG2RL
AUAM
HMAPE
PURNT
BAILGUN Interection Size
(2, N}
Ohenal Scattaitt
Hagh Staldhbutt
ego
parrwise
group
full joint-state
Figure 1: (a) MAPF requires group interactions. (i) The SoC-optimal (sum-of-costs) group interaction-based solution. (iiiv) Pairwise interactions with agent A, showing the optimal paths when agent pairs are isolated. (ii) Combination of the pairwise solutions. This solution is sub- optimal compared the group interaction-based solution. (b) Group interaction modelling has been previously unexplored. Positioning of MAPF solvers with respect to their interaction mod- elling. (c) HMAGAT achieves state-of-the-art performance. Radar plot comparing learnt MAPF solvers, showing average solution quality and scalability (both the higher, the better) across different small maps- and agent densities, and focused view on the highest agent density (High AD) scen- arios. Details of the metrics are in Appendix B
entanglement among agents. This makes MAPF a suitable testbed for studying highly-coupled multi-agent problems, especially obstacle-dense maps with large numbers of agents.
As with the other multi-agent problems, previous works on MAPF have focused on pairwise
interaction-modellingg popularly using GNNs (Li al. 2020 2021 Veerapaneni et al. 2025)
transformers (Wang et al., 22023] Andreychuk et al. 2025a). However, MAPF inherently group problem, i.c., optimality and completeness can, generally, only be achieved when modelling the full joint state space of all agents (not just two), as shown in Figure Ta We argue that the use of hypergraphs provides strong inductive biases for capturing group interactions, thereby enabling the development of more capable MAPF approaches.
To address this gap, (i) we propose HMAGAT, a novel imitation learning framework for MAPF, leveraging a hypergraph attention network to better model the higher-order group interactions. (ii) We propose hypergraph generation strategies that dynamically construct directed hypergraphs and (ii)) empirically demonstrate the prowess of approach over existing solvers, as shown in Fig, Ic beating the previous state-of-the-arr learning model while using only 112% parameters and -1% of the training data. (iv) Through experiments, perform deeper analysis why pairwise attention fails while modelling group interactions, and how hypergraphs overcome these issues.
II Large maps included in the radar plot, as MAPF-GPT fails to scale them, resulting in skewed results.
2

---

Published as a conference paper at ICLR 2026
2 PRELIMINARIES
2.1 HYPERGRAPIS AND MULTI-AGENT LEARNING
Hypergraphs are higher-order generalisation of graphs, where edges, called hyperedges, can con- nect any number of nodes. Formally, directed hypergraph is defined as H. (V,E), E), where V is the set of nodes and is the set of directed hyperedges. Each hyperedge (T(e), H (e)), where Te) S V is the tail and (e)) C V is the head of the hyperedge. A set of hyperedges incident to node i E V is denoted as [ = {e E & i T(e) H(e)).
an ordered pair
The hypergraph counterpart of graph neural networks (GNNs) is referred to as hypergraph neural networks (HGNNs). HGNNs have been increasingly adopted in multi-agent learning tasks due to their ability to capture higher-order interactions. E.g., HGNNS for formation control and robotic warehouses (Zhao et al.) 2025), multi-agent continuous trajectory prediction (Lin et al. 2024 Xu
et al. 2022) and social robot navigation (Li et al. 2024a Wang et al. (024). While these studies
focus on problems with often modest team sizes ( 10 agents), where tightly coupled coordination
among agents is less critical, work explores the potential of HGNNs in more challenging
coupled setting containing large number of agents, namely, MAPF
2.2 MULTI-AGENT PATHFINDING (MAPF)
We consider a widely used MAPF formulation (Stern et al. 2019), defined by a team of agents four-connecter grid graph G (V, E), and distinct start 8; V and goal ...,, n). E V for each agent i E A. At each timestep. each agent either stays in place or moves to an adjacent vertex. Vertex and edge collisions are prohibited: agents cannot occupy the same vertex simultancously or swap their occupied vertices. Then, for each agent i E A, we aim to assign a collision-free path म. (o" Sj: ..... v"" g:). The solution quality is assessed by sum-of- costs (SoC), which sums the travel time of each agent until it stops at the target location. Herein, configuration Q E Va refers to the locations for all agents. The dist function returns the shortest path length between two vertices on G, while neigh(u) represents adjacent vertices for E V.
A (1,
MAPF an appealing benchmark to assess the capabilities of multi-agent learning techniques, tailored to industrial setups such as warehouse automation (Agaskar et al. 2025). Several direc- tions exist on how to leverage MI. for MAPF (Alkazzi Okumura (002)), with major thrust being the governance of agent-wise neural policies that interpret their surrounding information and output actions, ideally leading to coordination beyond mere greedy behaviour. Such policies are typic- ally constructed either via reinforcement learning (RL) (Sartoretti et al. (219)) imitation learning (IL) (Li et al. 2021). This work focuses on IL. setups, motivated by recent findings that (i) col- lecting demonstration data is inexpensive with modern MAPF solvers (Okumura 2024), and (ii) IL consistently outperforms RL (Andreychuk et al. 2025a
Veerapaneni et al.) 2025
2.3
MAGAT: GNN-BASED POLICY FOR MAPF
Among existing policies for MAPF to date, MAGAT ( et al. 2021) a representative approach that employs GNNs capture pairwise agent interactions. Formally, governs policy (1 9) that outputs an action distribution over candidate target vertices for agent i, given its observation o, and the communication graph G, which is constructed based spatial proximity within radius Roomm E N The model consists of (i) a CNN encoder that converts o into the node feature x,, (ii) GNN layer that aggregates messages from other agents following G, and (iii) an MLP decoder.
Our proposed HMAGAT builds upon MAGAT. In addition to replacing the GNN with HGNN lay- ers, HMAGAT also incorporates techniques introduced in follow-up works on MAGAT. These include stacking GNN layers (three) to enhance representational power (Veerapaneni et al. 2025) and in- corporating position-based edge features embedded into G. Our implementation of MAGAT also includes these improvements.
Local Observation. Throughout the rest of the paper, we fix the observation tensor o; for agent i at configuration Q to be centred around its current position Qli). with shape x (2. + 1) x (2Rths + 1), where Robs E Ny0 determines the FOV size. The four channels consist of (i) an obstacle map, (ii) agent map, (ii)) a projection of the goal direction, and (iv) normalised cost-
3

---

Published as a conference paper at ICLR 2026
expert
hypergraphs
HMAGAT
quality imp
expert
Eacodar (CNN)
(6) expert-dnta collection
(b) hypergraph generation
model training
(d) post training
Figure 2: Overview of HMAGAT. (a) We collect demonstrations using an expert solver over 21K instances. (b) For each timestep, we extract directed hypergraph representation (head agent shown with bold outline here). (c) These are used to train our WGNNN-based model. (d) Post-training, we train the model using expert trajectories over intermediate instances, improve solution quality, A temperature sampler is also trained to make the model more confident.
lo-go map. For each location v E within FOV, the normalised cost-to-go value is computed as (dist(e, 9:) dist( dist(Q (2 while setting it to for obstacles. This construction is braseingbbased based MAPF studies (Alkazzi & Okumura 2024).
commonly used in learning-
3 HMAGAT
While GNNs have shown promise in modelling multi-agent systems, they inherently focus on pair- wise interactions between agents. This pairwise focus can limit their ability to capture the com- plex coupled-dynamies in multi-agent systems with interactions involving multiple agents simultan- eously. We identify two key limitations of GNNs, specifically MAGAT, in this context.
Attention in dense scenarios. In multi-agent systems, agent interactions tend to be uneven, where for given agent, some interactions might be more important than others. Thus, methods like MAGAT use an attentional mechanism to better model the interactions between agents. The attention scores are computed
pairwise manner and normalised over the neighbourhood (via softmax). This, however, can be problematic in out-of out-of-distribution dense scenarios. In such scenarios, each agent will have a dense neighbourhood, with only few agents being truly relevant. However, since the attention scores are first computed pairwise and then normalised over the neighbourhood, the pres- ence many irrelevant agents will dilute the attention scores of the relevant agents. Appendix E. includes informal proof that GNNs suffer from this phenomenon.
Group Interactions. The interactions in GNNs are inherently pairwise, while multi-agent prob- lems, like MAPF, tend to be fundamentally a group planning problem. Models like MAGAT can assuage this some extent by using multiple GNN layers, where deeper layers can theoretically learn to capture group interactions. However, without an explicit bias for these group interactions, the model would likely struggle learn such interactions. We provide further details on these lim- itations in Appendix F
Motivated by these observations, we propose HMAGAT, an attentional hypergraph neural network (HGNN)- based imitation learning model for MAPE, We first describe the architecture of HMAGAT, and then explore different hypergraph generation strategies.
3.1 ARCHITECCURE
To model the group interaction of multiple agents influencing single agent's decision, we design directed hypergraphs, with a singleton head and a multi-node tail. We replace the GNN layers in MAGAT with our HGNN layers, resulting in pipeline consisting of (i) CNN encoder, followed by (ii) HGNN layers, and (ili) an ML.P decoder.
Communication Hypergraph. We detail several strategies to generate a hypergraph H. in Sec- tion 3.2 We include hyperedge features Wje for each H and E T(e). This is set be
4

---

Published as a conference paper at ICLR 2026
diree-dimensions vector, consisting of the relative positional co-ordinates and the Manhattan dis- tance between the agent and the hyperedge centre, which is taken to be the position of the head agent or, in the general case, the centroid of the head agents.
Hypergraph Attention Network. We design our HGNN in a message-passing manner, with mes- sages going from the tail nodes to the hyperedges the head nodes. Concretely, let x denote the node feature of agent layer I. The layer update proceeds with:
(1+1) x;
E
( h )("))
aie
(E(()NCH())
0/
11)
softmax
h() LeakyReLU (x4)
(000
(9)
Σ
act
(1)
(W! x) + W!ll wze)
(hyperedge representation)
(3)
JET(c)
9 softmax LeakyReLU
Σ
x /HHHll
(o!) x e w,:w
(4)
(E((()
Here, Wye )(wje) is the hyperedge feature processed via MLP o azej and aie are the normal- ised attention weights, w
(
(Rt,n.e.k] and (1) (n.e.k) the learnable weights, and or is non non-linearitty The above design reflects the necessity of modelling variable hypergraph and hyperedge sizes. In- stead of architectures with fixed and uniquely identifiable relation types (Busbridge et al. 2019), HMAGAT is derivative from attentional HGNNs (Bai al.) 2021 Chen al. (020), which can accommodate dynamic and flexible hypergraph structures.
This HGNN architecture capable of mitigating attention dilution. We provide an informal proof in Appendix E.2
3.2
HYPERGRAPH GENERATION
Unlike GNNs, which naturally in- troduce pairwise interactions over a communication graph, defining hy- pergraphs for MAPF that capture group interactions is not trivial. We focus on directed hypergraphs with singleton heads and multi-node tails.
Algorithm COLOUURINGABEDDDHYYRRRRR
input: colours C, colouring R, agents A, positions Q
I: 0
2: for E A,CE do
3:
<- {u E A [[u]] - @|o]| || & Ieumm A (Q(u).c) e R)
4: ifT o then E EU ((T U (v). (w)))
5: return (A,E)
directed hypergraph
An intuitive approach to assign a polour-potenntillly multiple colours-to each vertex v E V. based on geometric adjacency, under the belief that agents in the same local region are more likely to interact collectively. We then form groups according to agent locations and their colours; that is, agents sharing the same colour form the tail of a hyperedge. Concretely, let C. be the set of colours, and let R V 2/ denote the colouring function. Given C and Rt Alg. [ggTatesss directed hypergraph subject to the constraint of a communication radius Reomm We next discuss strategies to build the colouring R.
Lloyd Hypergraphs. A principled approach to workspace partitioning is to employ Voro- noi diagram, which divides the space into re- gions based on distances to set of & ini- tial seed locations. By applying Lloyd's al- gorithm (Lloyd 1982] Zaman et al. 22024,, one can obtain a balanced Voronoi partition with ap- proximately equal-sized regions, regardless of the choice of initial seeds. In principle, each region can be assigned distinct colour. How- ever, a strict partitioning is not ideal for our setting, since agents may interact across these artificial boundaries. This motivates to introduce "soft" borders by allowing multiple colours per vertex.
(b)
Figure 3: Going from (a) strict partitioning
to (b) overlapping groups.
5

---

Published as a conference paper at ICLR 2026
Concretely, after the Lloyd's algorithm, discard half of the least populous colours and reassign the corresponding regions to the colours of their neighbouring regions. An illustration this process is shown in Figure with the pseudocode provided in Appendix A
k-means Hypergraphs. Since Lloyd's algorithm requires O V1 time for updating centroids, it becomes impractical for large graphs. In a faster method, we first diffuse colours from k randomly sampled vertices, where each vertex is associated with k-dimensional vector and each dimension corresponds to one colour. Over a fixed number of iterations T, each vertex updates its vector to the mean of its neighbours' vectors. We then apply k-means clustering (MacQueen) 1967) these vectors, followed by the "soft boundary operation" described above. This procedure reduces the complexity to (K))V)) See Appendix [ for the detailed procedure.
Shortest Distance-based Hypergraphs. We also explore non-colouring-bass hypergraphs. Given an agent i, we say that two agents and k should be in the tail of hyperedge with head i if agent can encounter one agent while visiting the other. We formalise this using the shortest path distances between the agents. We include further details of this strategy in Appendix
3.3 TRAINING PIPELINE
Model Training. We use the POGEMA toolkit (Skrynnik et al. 2025 also employed in the de- velopment of MAPF-GP? (Andreychuk et al. 2025a). Following CAAPF-GPT's training protocol, generate total of 21K instances, of which, 20% feature randomly placed obstacles, while the remaining 80% are maze-like environments. Map sizes range from 17x17 to 21x21, with 16, 24, or 32 agents. For reference, MAPF-GPT uses 3.75M instances for training. In line with MAPF-GPT, we generate expert trajectories using lacam3 (Okumura) 2024). state-of-the-arr anytime MAPF solver. We adopt staged timeout strategy with time limits of [1, 5, 15, 60]s, where a longer timeout is used only if the shorter ones fail. As the training set does not include challenging situations, most instances were solved within 1 s. HMAGAT, with Reomm = 7 and Robs 5, is trained on the collected expert trajectories using cross-entrops loss. We train for 200 epochs. requiring about 100 hours on an NVIDIA L40S GPU, using the Adam W optimiser (Loshchilov & Hutter 2019
Online Expert. To mitigate the distributional shift common in imitation learning, we further apply on-demand dataset aggregation (Ross et al., 201T), collecting new trajectories where the model fails, following MAGAT (Li et al. 2021). To improve the quality of trajectories, after achieving 80% success rate, we check if the length of the model's solution exceeds doar the expert trajectory length, with 6bsr 1.2. If so, we follow Andreychuk et al. (2025b) and extract instances at every h-th step, where h 16. We then solve these instances using lacam3 with timeouts of [1, 10)s, adding trajectories that are 6 shorter than the model's 's trajectory. To keep the training time manageable, limit the total number of quality improvement expert-calls to 30 per online expert phase.
Post-Training We follow MAPF-GPT-DOE (Andreychuk et al. 2025b) and apply post-training phase to further improve the solution quality. This follows the same training procedure as before, but with the quality improvement online expert being called for all 500 instances and with the train- ing consisting of 1 3 ratio of the quality improvement instances and the pre-collected instances, respectively. We run the online expert after every epoch, due the high accuracy the model. We run this post-training for 20 epochs, requiring about 30 hours an NVIDIA L40S GPU.
Temperature Sampling, Previous works have shown that GNNs can achieve high accuracy, but tend to be miscalibrated, having low confidence in their predictions (Hsu et al. 2022 Wang et al.] 2021). This is particularly problematic in MAPF, where we sample the next action based on the model's 'ss output distribution. Similar problems are likely to exist for HGNNs as well. To tackle this, softmax temperature between 0.5 and 1.0. We train an RL module to dynamically adjust T for each agent based on its local observability and action log-odds. This module is trained for 50 epochs, taking about hours NVIDIA L40S GPU, We include further details in Appendix A

---

Published as a conference paper at ICLR 2026
4 EVALUATION
Baselines. We compare HMAGAT with the following three state-of-the-art learning-based MAPF solvers: (i) MAGAT (Li et al. 2021), D an attentional GNN-based model. (ii) MAPF-GPT (Andreychuk)
et al. 2025a), the most capable IL policy to date, using a GPT-like architecture. The authors provided three model sizes: 2M, 6M, and 85M. (iii) MAPF-GP
(Andreychuk al.] 2025b). fine- tuned version of MAPF-GPT T (2M) model, which the authors claim matches the 85M model. We use PIBT-based collision shielding (Okumura et al., 2022) for all these methods, as recommended by
Veerapaneni et al. (025). We also run our evaluation on SSIL (Veerapaneni et al. (023). another GNN-based II. model, and SCRIMP [Wang et al. 2023) and DCC (Ma et al. 2021), ). two RL models.
However, due to the vast difference in performance, we limit their results to Appendix C
Metrics. We present the success rates, the average relative sum-of-costs (Rel. SoC) with respect to lacam3 with 30s budget and the average runtime per-map. The success rate measures the percentage of instances in which all the agents reach their respective goals. For calculating SoC for failed instances, we follow POGEMA's (Skrynnik et al., 2025) and, in turn, MAPF-GPT's (An- dreychuk et al. 2025a) strategy of assigning the episode length to be the costs for agents that fail to reach their goals. For iterative solvers, this is a valid strategy get a lower bound on the SoC if the episode length was not limited. lacam3 is the only search-based solver evaluated, and it succeeds all the evaluated scenarios, leading to no issues.
Evaluation Maps.
The commonly used MAPF-benchmarking maps can be divided into seven main categories (Stern et al.) 20199; (i) Maze, (ii) Marehouse, (iil) Room, (iv) Game, (v) city, (vi) Random and (vii) Open.
In our evaluation below, we use (i) Sparse Maze and (ii) Empty Room with 256 step limit and 60s s time limit, (iii) Dense Maze, (iv) Dense Room and (v) Dense Warehouse with 512 step limit and 60 s time limit, and (vi) ost003d with 1024 step limit and 90 time limit. Since Random and Open maps are just simpler versions of Maze maps, omit their results. City maps are large and sparse, with simple obstacle structures, so we limit their evaluation to Appendix
4.1
RESULTS
Sparse
Mazo
Empty Room
Denie Haze
Dense Roon
Marchouse
0s:C033
Success Rate
1.80
6.00
6.0
4.56
21
23x21
21
23x22
1bx22
11
Runtime
12
95
150 182
30
125
100
Ragents
MAPF-GPT-DDG
MAPF-OPT (BM)
MAGAT
HMAGAT (k-maans)
MAPF-OPT (85M)
MAPF-GPT (2M)
HMAGAT (Lloyd)
HMAGAT (Shortest Dist)
Figure 4: Evaluation of the learning- MAPF policies, averaged over 128 instances. Transparent
regions represent 95% confidence intervals. SoC is reported relative to 1 lacam3 (w/ 30 time limit).
Figure 4 shows the results on the different maps. We see that all HMAGAT strategies consist- ently obtain higher quality solutions than MAGAI, well as larger models, like MAPF-GPT (2M), MAPP-GPP (6M) and MAPF-GPT-DEE
(2M). HMAGAT remains competitive with the largest MAPF-GPT (85M) model, while being significantly faster. k-means and Lloyd's HMAGAT have con- sistently high solution quality, with the k-means strategy being faster, especially on the larger maps, expected. For the rest of the analysis, we focus on k-means hypergraphs.
HMAGAT outperforms MAPF-GPT (85M) in the Maze maps in terms of solution quality, but MAPF-GPT (85M) outperforms HMAGAT in the Room and Warehouse maps, except for the
7

---

Published as a conference paper at ICLR 2026
Table 1:
Comparison of HGNN and GNN, corresponding to HMAGAT w/o embellishments and
MAGAT, on different maps with the maximum agent density, Rel. SoC is relative to lacam3.
Dense
Dense Warehouse
Dense Room
Metric
Method
ost:003d
Paris
Maze
GNN
72.7%
2.3%
66.4%
100.0%
100.0%
Success Rate
HGNN
75.8%
39.8%
75.0%
100.0%
100.0%
Rel. SoC (95% CI)
GNN
2.07 + 0.09
2.12 0.10
2.63 + 0.07
1.06 = 0.00
1.03 + 0.00
HGNN
1.79 + 0.09
1.78 1 0.08
2.35 1 0.06
1.05 = 0.00
1.02 4: 0.00
highest agent density case for Dense Warehouse map. fact, HMAGAT achieves 75+%
success rate even in this challenging scenario, while the other methods achieve <11% success rates. MAPF-GPT (85M) is fails to scale to ost003d, while HMAGAT obtains solutions close to 1acam3's 3's quality.
Ablation Study, Figure shows the results of our ablation study over the highest agent density scenarios on each of the small maps, where we start from MAGAT and incre- mentally add components HMAGAT. For ease, we fix the hy- pergraph generation strategy be k- means colouring-basee based. The addition of each module improves both the success rate and the solution quality, except for the RL-based temperature sampling, which trades off the cess rate for improved solution qual- ity. This shows the importance of each component for the success of HMAGAT.
Ablation over highest agent density runs
1.0
Failure Rate
Rol. Sum of Costs
0.0
2.00
of Costs
Faluua Rate
1.78
reach
0.4
0.2
1.25
MAGAT
+Hypargraphs
+0E
+oot:: Train Quality Imp.
+Tomp. Samp. (HMAGAT)
Quality Imp.
Figure 5: Ablation study. We start from MAGAT and in- crementally add components reach HMAGAT. We plot the failure rate and Rel. SoC (both the lower the better), over the highest agent density scenarios of the small maps.
4.2 HGNN vs GNN DEEPER ANALYSIS
% of attention scores
20%
Attention Warehouse
GNN
In this section, we further analyse the difference due to the use of HGNNs over GNNs. To isolate the effects and perform direct comparison, we focus on stripped-down version of HMAGAT, consisting solely of the replacement of the GNN layers with HGNNs. To emphasise the dif- ference from HMAGAT, we refer to this stripped-down ver- sion as simply the HGNN model and MAGAT as the GNN model, for this analysis.
15%
HGNN
10%
5%
0%
10
10
10
1
10a
Attention
(log scale)
Attention in Dense Maze
% of attention scores
Table I shows the comparison between the two models over different maps. We see that the HGNN model con-
20%
GNN HGNN
15%
sistently outperforms the GNN model across all maps, es- pecially in the denser maps. This aligns with our hy- pothesis that HGNNs are better able to capture complex group interactions. The HGNN model also has a higher success rate the dense scenarios. This gap particularly pronounced on the Dense Warehouse map, where the HGNN model has a success rate of 39.8% compared the GNN model's 2.3%.
10%
5%
0%
10
10
10-2
10
10
Attention score bins (log scale)
Figure 6: Attention score distribution in the first layer of the models with 128 agent instances.
Attentional Analysis. To better understand the difference in performance of the two models, we analyse the attention scores in the first layer of both the models. Figure 6 shows the distribution of these attention scores over a sample instance Dense Marehouse and Dense Maze maps. The GNN model has a high concentration of attention scores in the midhee range, which leads to a dilution of attention, resulting in very few agents receiving high attention. On the other hand, the HGNN model has fewer agents in this range, allowing it to maintain more agents in the highest
8

---

Published as a conference paper at ICLR 2026
attention score bin. This supports our hypothesis that GNNs struggle in high density scenarios due to the dilution of attention scores, which our HGNN model is able to overcome. We provide further analysis of attention dilution in Appendix H
4.3 HAND-CRAFTED SCENARIOS
We now analyse the two models hand-crafted scenarios and showcase the limitations of GNNs due to (i) attention dilution in dense scenarios and (ii) the inability to effectively capture group interactions, which HGNNs are able overcome since they do not rely on pairwise interactions.
Table 2: CV of attention scores (in the first layer) for agent 0 as we vary the number of agents from 4 to (inclusive both) in the map described in Fig- ure (left).
Method
Grp.
Grp. 1
Grp. 2
Grp. 3
GNN
29.4%
20.0%
14.9%
39.2%
HGNN
6.0%
4.3%
7.4%
14.7%
Ratio
4.94
4.66
2.01
2.66
Hand-crafted scenarios. The filled circles represent the agent locations, while the empty ones represent their targets. Scenario (left): We form 4 groups of agents, shown by different colours here. Scenario 2 (right): We show the next greedy actions for the agents.
Figure 7:
Table 3: Percentage Shapley values for the agents with respect to agent in Figure (right).
Agts. 3 vs. 4
Method Agt.
Agt. 2 Agt.
Agt.
GNN HGNN
15.0%
60.3%
13.1%
11.6%
+13% +802%
19.0%
59.6%
19.3%
2.1%
Scenario Since, GNNs, the attention scores are computed in a pairwise manner, high density of agents in unimportant regions will lead to a dilution of attention. To illustrate this, we consider the scenario shown in Figure 7 (Ieft). We can create a sequence of scenarios by starting with agents (agents 0-3 in groups 0-3, respectively) and sequentially adding agents 4-7 to group 3. We focus on the first layer attention scores wrt. agent O. By design, agent primarily needs to attend to agent 2 and, potentially, agent 1, as their respective greedy paths have intersections with agent 0's. On the other hand, the agents in group 3 are not expected to interfere with agent O's path, and thus, increasing the number of agents in group 3 should not affect the attention distribution for agent 0.
Table shows the coefficient of variation (CV) of the attention scores. The GNN model exhibits a high variation in the attention scores leading to a dilution of the attention scores in the important regions. In contrast, the HGNN model exhibits much lower variation, remaining relatively unaffected by the number of agents in group 3, as desired. We include more details on the attention scores in Appendix D
increase the number of agents in less important regions,
Scenario In this scenario, we aim illustrate the ability of HGNNs capture group interac- tions as opposed to GNNs. Towards this end, we design the scenario shown in Figure 7 (right), analysing how agents 1-4 influence agent To quantify the influence, we make use Shapley values (Shapley) 1951 Lundberg & Lee 2017), taking the mean of the absolute Shapley values for each plausible action-class log-odds prediction.
By design, we expect the following influence ranking: Agent 2 > Agent 3 R Agent 1 >> Agent 4. This is because agent 2's next greedy action conflicts with agent O's. Agent 3's greedy path will want agent I to occupy this conflicting cell, leading to group interaction effect and thus, similar high influence on agent O's actions. Since agent 2 is already moving away from agent 4, agent is expected to have low influence. From purely pairwise perspective, agents 3 and 4 have mirrored start and goal locations wrt. agent O, and thus, should have similar influence on agent 0's actions. However, due to group interactions, expect agent to have higher influence than agent 4.

---

Published as a conference paper at ICLR 2026
Table shows the percentage Shapley values for the GNN and HGNN models. As expected, see that both models assign the highest influence to agent For the GNN model, agents 1, and have similar influence, with agent having only 13% more influence than agent 4. This highlights the inability of the GNN model to capture group interactions effectively. On the other hand, in the HGNN model, agent 3 has a significantly higher influence (802% more) than agent 4, showcasing the ability of HGNNs to capture group interactions and distinguish between the agents.
5 CONCLUSION
In this work, we explored MAPF representative multi-agent problem with complex interactions. We proposed HMAGAT, an MAPF solver based on hypergraph neural networks (HGNNs), as solu- tion to model higher order interactions. We empirically demonstrated that our approach outperforms current state-of-the-art methods, which only consider pairwise interactions. HMAGAT achieves su- perior performance to MAPF-GPT (85M), 85x larger model, trained on 100x more data. We perform further analyses to show that, indeed, the HGNNs help to capture group interactions bet- ter than GNNs via explicit group modelling. Our results show how higher order representational learning models can lead to improved model performance, while lowering the sample complexity and model size, strongly motivating future research to explore hypergraph- based methods for chal- lenging multi-agent problems with highly coupled interactions. As our model achieves SoTA per- formance with significantly smaller parameter count than previous works, our results demonstrate that better inductive biases, such as hypergraph-based interaction modelling, are complementary strategy to training larger models when tackling difficult multi-agent problems.
REPRODUCIBILITY STATEMENT
Section 3 details our proposed HMAGAT model and training procedure. In order to make our work easily reproducible, we provide further details about the model architecture and training in Ap- pendix A including relevant hyperparameters. We provide our codebase as supplementary material, which includes instructions to reproduce our results as well as checkpoints for our trained models. The codebase also includes scripts to generate the instances used to train and evaluate models.
ACKNOWLEDGMENTS
This research was funded in part by Trinity College Cambridge, European Research Council (ERC) Project 949940 (gAla), JST ACT-X (JPMiAX22AI), and JST PRESTO (JPMJPR2513).
REFERENCES
Jeffrey L Adler and Victor J Blue. A cooperative multi-agent transportation management and route guidance system. Transportation Research Part C: Emerging Technologies, 10(5):433 454, 2002. ISSN htt.a//cw......c..oo.....oooeeoa
doi:
00055999688000000000000000000333 URL https:
www. www.ssciiicccccccc rect.
Ameya Agaskar, Sriram Siva, William Pickering, Kyle O' O'Brien, Charles Kekeh, Ang Li, Bri- anna Gallo Sarker, Alicia Chua, Mayur Nemade, Charun Thattai, et al. Deepfleet: Multi-agent foundation models for mobile robots. arXiv preprint arXiv:2508.08577 2025.
Jean-Mare Alkazzi and Keisuke Okumura. A comprehensive review on leveraging machine learning for multi-agent path finding. IEEE Access, 2024.
Anton Andreychuk, Konstantin Yakovlev, Aleksandr Panov, and Alexey Skrynnik. Mapf-gpt: Imita- tion learning for multi-agent pathfinding at scale. In Proceedings of AAAI Conference on Artificial Intelligence (AAAI), 2025a.
Anton Andreychuk. Konstantin Yakovlev, Aleksandr Panov, and Alexey Skrynnik. Advancing leamn able multi-agent pathfinding solvers with active fine-tuning. arXiv preprint arXiv:2506.23793 2025b.
10

---

Published as a conference paper at ICLR 2026
Song Bai, Feihu Zhang, and Philip H.S. Torr. Hypergraph convolution and hypergraph attention. Pattern Recognition, 110:107637, 2021. ISSN 0031-3203. doi: https://oo..og//001111....uuu
2020.107637. URL https: wwwp//wwwww.omm/m.mm/////ww http://www..aaaaeeoc.ocoooo/oota
Guillermo Bernárdez, José Sudárez-Varela Albert López, Xiang Shi, Shihan Xiao, Xiangle Cheng, Pere Barlet-Ros, and Albert Sabellos-Aparicio Magnneto: A graph neural network- -based multi- agent system for traffic engineering. IEEE Transactions on Cognitive Communications and Net- working. 9(2): 506, 2023. doi: 10.1099TCCC.220333355111
Dan Busbridge, Dane Sherburn, Pietro Cavallo, and Nils Hammerla, Relational graph attention networks. arXiv preprint 1904:09994. 2019.
Chaofan Chen, Zelei Cheng, Zuotian Li, and Manyi Wang. Hypergraph attention networks. In 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Commu- nications (TrustCom), pp. 1560-1565. IEEE, 2020.
Tzvika Geft and Dan Halperin. Refined hardness of distance-optimal multi-agent path finding. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, AAMAS 22, pp. 481-488, Richland, SC, 2022. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 978 1450322136.
Hans Hao-Hsun Hsu, Yuesong Shen, Christian Tomani, and Daniel Cremers. What makes graph neural networks miscalibrated? 2022.
Jiewu Leng. Weinan Sha, Zisheng Lin, Jianbo Jing, Qiang Liu, and Xin Chen. Blockchained smart contract pyramid-driven multi-agent autonomous process control for resilient individualised man- ufacturing towards industry 5.0. International Journal of Production Research, 61(13)3430-- 4321, 2023. doi: 00.1000000207543..222222002 00207543 200.232222......222222222222222.
URL https: /ctp:///c...oooooo http:////....o.1111000010000
Jiachen Li, Chuanbo Hua, Hengbo Ma, Jinkyoo Park, Victoria Dax, and Mykel Kochende- rfer. Multi-agent dynamic relational reasoning for social robot navigation. arXiv preprint arXiv:2401. 12275, 2024a.
Qingbiao Li, Fernando Gama, Alejandro Ribeiro, and Amanda Prorok. Graph neural networks for decentralized multi-robot path planning. In 2020 JEEE/RSJ international conference intelli- gent robots and systems (IROS), pp. 11785-11792. IEEE, 2020.
Qingbiao Li, Weizhe Lin, Zhe Liu, and Amanda Prorok. for lcage multi-robot path planning. IEEE Robotics and Automation Letters (RA-L), 2021.
Message-awar graph attention networks
Xinyi Li, Sai Wang, Siqi Zeng, Yu Wu, and Yi Yang. A survey Ilm-based multi-agent systems: workflow, infrastructure, and challenges. Vicinagearth, 1(1);9, 2024b.
Weilong Lin, Xinhua Zeng, Chengxin Pang, Jing Teng, and Jing Liu. Dyhgdat: Dynamic hyper- graph dual attention network for multi-agent trajectory prediction. In 2024 IEEE International Conference on Robotics and Automation (ICRA), pp. 16662-16668. IEEE, 2024.
Ziheng Liu, Jiayi Zhang, Enyu Shi, Zhilong Liu, Dusit Niyato, Bo Ai, and Xuemin Shen. Graph neural network meets multi-agent reinforcement learning: Fundamentals, applications, and future directions. IEEE Wireless Communications, 31 (6)399 2024.
S. Lloyd. Least squares quantization in pem. IEEE Transactions on Information Theory, 28(2): 129-137, 1982. doi: 10. 10.1109/TT.1992.0 1056489.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In Proceedings of the International Conference Learning and Representation (ICLR), 2019.
Scott M Lundberg and Su-In Lec. A unified approach interpreting model predictions. Advances in neural information processing systems, 30, 2017.
Ziyuan Ma, Yudong Luo, and Jia Pan. Learning selective communication for multi-agent path finding. IEEE Robotics and Automation Letters (RA-I.), 2021.
11

---

Published as a conference paper at ICLR 2026
J. B. MacQueen. Some methods for classification and analysis of multivariate observations. In L. M. Le Cam and J. Neyman (eds.), Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability, volume pp. 281-297. University of California Press, 1967.
Keisuke Okumura. Engineering lacam": Towards real-time, large- scale, and near-optimal multi- agent pathfinding. In Proceedingy of International Joint Conference Autonomous Agents & Multiagem Systems (AAMAS). 2024.
Keisuke Okumura, Manao Machida, Xavier Défago, and Yasumasa Tamura. Priority inheritance with backtracking for iterative multi-agent path finding. Artificial Intelligence (AIJ), 2022.
Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. reduction of imitation learning and struc- tured prediction to no-regret online learning. In Proceedings of the International Conference Artificial Intelligence and Statistics (AISTATS), 2011.
Guillaume Sartoretti, Justin Kerr, Yunfei Shi, Glenn Wagner, TK Satish Kumar, Sven Koenig, and Howie Choset. Primal: Pathfinding via reinforcement and imitation multi-agent learning. IEEE Robotics and Automation Letters (RA-L), 2019.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Shai Shalev-Shwartz, Shaked Shammah, and Amnon Shashua. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03225. 2016.
Lloyd S. Shapley. Notes on the N-Person Game - 11: The Value of an N-Person Game. RAND Corporation, Santa Monica, CA, 1951. doi: 10.7249/RM0670.
Alexey Skrynnik, Anton Andreychuk, Anatolii Borzilov, Alexander Chernyavskiy, Konstantin Yakovlev, and Aleksandr Panov. Pogema: A benchmark platform for cooperative multi-agent pathfinding. In Proceedings of the International Conference on Learning and Representation (ICLR), 2025.
Roni Stern, Nathan Sturtevant, Ariel Felner, Sven Koenig, Hang Ma. Thayne Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, TK Kumar, et al. Multi-agent pathfinding: Definitions, variants, and benchmarks. Proceedings of Annual Symposium on Combinatorial Search (SoCS), 2019.
Nathan R. Sturtevant. Benchmarks for grid-based pathfinding. IEEE Transactions on Computational Intelligence and Al in Games, 4(2):144-148, 2012. doi: 10.1 1.111//CCIAIG..2222299966
Pavel Surynek. An optimization variant of multi-robot path planning is intractable. In Proceedings of the AAAI conference on artificial intelligence, volume 24, pp. 1261-1263, 2010.
Yimin Tang, Xiao Xiong, Jingyi Xi, Jiaoyang Li, Erdem Biyık, and Sven Koenig. Railgun: A unified convolutional policy for multi-agent path finding across different environments and tasks. arXiv preprint ar arXiv:2503.0299 2025.
Rishi Veerapaneni, Qian Wang. Kevin Ren, Arthur Jakobsson, Jiaoyang Li, and Maxim Likhachev. Improving learnt local mapf policies with heuristic search. In Proceedings of International Con- ference on Automated Planning and Scheduling (ICAPS), 2024.
Rishi Veerapaneni, Arthur Jakobsson, Kevin Ren, Samuel Kim, Jiaoyang Li, and Maxim Likhachev. Work smarter not harder: Simple imitation learning with cs-pibt outperforms large scale imitation learning for mapf. In Proceedings of IEEE International Conference Robotics and Automation (ICRA), 2025.
Binyu Wang, Zhe Liu, Qingbiao Li, and Amanda Prorok. Mobile robot path planning in dynamic environments through globally guided reinforcement learning. IEEE Robotics and Automation Letters, 5(4):6932-69) 6939, 2020. doi: 10.1 1..0 30266668.
Weizheng Wang. Aniket Bera, and Byung- Min. Hyper-samarl: Hlyergraaph-bssee based ordinated task allocation and socially-aware navigation for multi-robot systems. arXiv preprint arXiv:2409. 11511, 2024.
12

---

Published as a conference paper at ICLR 2026
Xiao Wang, Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neural networks via confidence calibration. 2021.
Yutong Wang, Bairan Xiang, Shinan Huang, and Guillaume Sartoretti. Scrimp: Scalable communic- ation for reinforcement-and imitation-learning www---linnnnnaeeeeee basedd multi-agent pathfinding. In 2023 IEEE/RS/ International Conference on Intelligent Robots and Systems (IROS), pp. 9301-9308. IEEE, 2023.
Peter R. Wurman, Raffaello D' Andrea, and Mick Mountz. Coordinating hundreds of cooper- ative, autonomous vehicles in warchouses. Al Magazine, 29(1):9, Mar. 2008. doi: 10.
1609/aima. v29:1 URL httpss:/ojss. aaai wwg. http//ziaaaai///////mammama htt///nnxxxx// php/
Chenxin Xu, Maosen Li, Zhenyang Ni, Ya Zhang, and Siheng Chen. Groupnet: Multiscale hyper- graph neural networks for trajectory prediction with relational reasoning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
2022.
Tareq Zaman, Nicolas Nytko, Ali Taghibakhshi, Scott Maclaac Luke Olson, and Matthew West. Generalizing lloyd's algorithm for graph clustering. SIAM Journal on Scientific Computing, 46 A2):421 2024. 23M15568001
doi: 10.1137/23M1556600 URL srctps://dos ooriloorgg1111111
Delin Zhao, Yanbo Shan, Chang Liu, Shenghang Lin, Yingxin Shou, and Bin Xu. Sdhn: Skewness- driven hypergraph networks for enhanced localized multi-robot coordination. arXiv preprint arXiv:2504. 0564445504.06844 2025.
Tianyu Zhu, Xinli Shi, Xiangping Xu, Jie Gui, and Jinde Cao. Hypercomm: Hypergraph-base based communication in multi-agent reinforcement learning. Neural networks: the official journal of the International Neural Network Society, 178: 106432, 2024.
A FURTHER DETAILS FOR HMAGAT
A.1 TEMPERATURE SAMPLING MODULE
We consider lightweight temperature sampling module predict the softmax temperature To train this module, we consider an actor-critic setup. For each agent, the actor takes the log-odds predicted by the model, the number of agents in its FOV, the number of obstacles in its FOV, and the distance and relative positional vector to its goal as input, passing them through a 2-layer MLP with ReLU activations, outputting scalar activation and scaling the output. The critic takes the same input, passing them through 2-layer MLP with ReLU and outputs a scalar value for the instance by averaging the outputs for all agents. We consider simple reward functionn where we give reward of +1 to each agent if all agents reach their goals, else a reward of -1, in order to encourage higher success rates, while also encouraging shorter paths.
[0.5, 1.0] for each agent, by applying a sigmoid
We train this module using the PPO algorithm (Schulman et al. 2017), with a clip ratio of 0.2, a discount factor of 0.99, and GAE À of We use learning rate of 3 10-4 and batch size of 64. We train this module for 50 epochs, requiring about hours on an NVIDIA L40S GPU. These trained 85 instances, each with 32 agents, 20 + 80% combination of Random and Ma maps, with 15 separate instances for validation.
A.2 HYPERGRAPII GENERATION
Colouring-based Hypergraphs. Algorithm B] shows the pseudocode for generating a colouring for given grid using Lloyd's 's algorithm, with overlapping regions. Algorithm 4shows the pseudo- code for generating a colouring using k-means clustering, with overlapping regions.
Lloyds versus k-means. Lloyd's algorithm for graphs employs Floyd- Warshall's algorithm to up- date centroids, which has a time complexity O(E.sc |sg] 3), where s, is the size of cluster e. The cluster sizes can be imbalanced, leading to a worst-case time complexity of ((V(3). In contrast, k-means clustering has time complexity of OEE [se]) for the updates, because it only
13

---

Published as a conference paper at ICLR 2026
Algorithm 2 STIOTTESTDESTNNGBBSDDDYEEEEEEEE
input: grid G = (V, E), agents A, agent positions Q params: communication radius Am dynamic slack variable
I:
P. set of hyperedges
for E A
3: H + {F}
b> head of hyperedge communicating agents initialize candidate edges
4:
Ac +- {u E A
[10[u] 0 s Rm \ {n)
5:
Ec +-0
for E Ac
7:
for w Ac {u] do Q + dist Q(a)) s max @lv)), dist (Qv)), 2(=()) + then Be Ec U (u, w), (w,u)}
8:
if dist((2
9:
10:
C GETCLIQUESAAC Ec)
for T
12: 8 + (
13:
return 3
Algorithm 3 GRIDCOLOURING
input: grid G (V, (V,E) E)
params: number of initial colours K, number of final colours k number of iterations
I: R', C" 4- --L.LLSOOOGGRAAA
W,
Rigid colouring from Loydd's b We use k = k
2: C < k-most populous colours in R'
3: R < ((v,c) E R'' C C}
D Discard least populous colourings Intiill uncoloured vertices While are uncoloured vertices
4: U + VV E (.(vc))
while E V... V13....ee. E. C do
Rola f R
7: for E U do
8: R R+ RU [(u, e
Be neigh(u) (v, Raw
Take neighbours' colours Less rigid colouring
return C
requires computing the mean the features of the vertices the cluster, where d is the feature dimension. Since, our case, (the number of clusters) and Enec [Sc] [V] this complexity becomes O(k x [V]..
With a moderate graph size, this cost is not prohibitive with respect to the model inference. E.g., on the Dense Warehouse map with 128 agents, HMAGAT takes average 19s solve, out of which 0.04s are spent on the colouring of the map. 0.005s 8% of inference time) are spent on constructing the hypergraphs from the colouring each time step. In practice, this can be highly optimized using C++.
Shortest Distance-based Hypergraphs. Algorithm shows the pseudocode for generating shortest distance- based hypergraphs. In order to get faster clique computations, we simply sample cliques by randomly selecting an agent from the communicating agents, and then greedily adding agents to the clique by checking if the new agent is connected to all the existing agents in the clique. We repeat this process until we have each communicating agent at least one clique, each time selecting of the non-selected agents the starting agent. We repeat the process if have less than total cliques, in order to ensure that we have a reasonable number of sampled cliques in highly connected distance graphs. To lower the computation time, only generate new hypergraphs every timesteps.
B RADAR PLOT DETAILS
Figure Ic shows the performance of various learning-based MAPF solvers on the small maps, i.e. on Sparse Maze, Empty Room, Sparse Warehouse, Dense Maze, Dense Room and Dense Warehouse. More details on the maps can be found in Appendix C Tigure[[shows more detailed results on these maps. We define the metrics used in the radar plot follows:
SoChea /ooC
Sol. Quality = 0
(5)
no solution found
14

---

Published as a conference paper at ICLR 2026
Algorithm 4 KMEANSCOLOURING
input grid G = (V,E)
params: number of initial colours k' number of final colours k number of iterations
1: xlv]
Initial colour vectors
2: X + Randomly assign k' vertices to unique colours (i.c. set X(e, c) := 1)
1> Random seeding Diffuse colours
3: for E [1, n] do
4: X.odd < X
for E V
6:
X + mmenighttt) Xui[u]
7:
X'el + [|)]
Mean of neighbours' colours Rigid colouring from k-means b We use k = K /
8: C²,C" + K-EAAN(S,,,,, k n))
9: C <- k-most populous colours in R'
10: R ((v,c) E |Ce
Discard least populous colourings Initial uncoloured vertices > While there are uncoloured vertices
U E C.(r.c) E R)
12: while 3v VI (v, do
13: Raa < R
14: for U do
15: R RU {(u, c) V C Ee neigh(u) (v,c) E Rou
Take neighbours' colours Less rigid colouring
16:
return R,C
Table 4: Map details.
Map
Size (H W)
Obstacle Density
Step Limit
Time Limit
Sparse Maze
21 x 21
8 24%
256
60
Empty Room
23 23
-00
256
60
Sparse Marehouse
22
-32%
256
60s
Dense Maze
21 x 21
30 40%
512
60s
Dense Room
23 x 23
34 42%
512
60s
Dense Warehouse
16 23
-43%
512
60s
cst003d
194 194
-65%
1024
90s
1ak303d
194 x 194
-61
1024
90s
Paris
256 x 256
-2%
1024
90s
Berlin
256 x 256
-27%
1024
90s
(tagens) #agents
Min, dugents nuntimeMMin. Augents)
Scalability
if timed out
C FURTHER EVALUATION RESULTS
C.I MORE EVALUATION MAPS
We provide further evaluation results on more maps with more methods here. Table shows the details for each map. ost003d and lak303d Game maps. while Paris and Berlin linnnn City maps, all taken from the MovingAl pathfinding repository (Sturtevant 2012).
C.2 COMPARISON OF HMAGAT VARIANTS
Small maps. Figure g shows the results on the small maps. On the sparse maps, all HMAGAT variants perform nearly identically in terms of SoC. They also have similar success rates, except for k-means-baas based EMAGAT on Sparse Warehouse, where has slightly worse success rate. k-means-based and Lloyds-based HMAGAT have similar runtimes, while the shortest-distance based HMAGAT is slightly slower, with the gap being more pronounced the more agents there are. This expected because unlike the rolouring-based methods that compute the colouring irrespective of the agent configurations, the shortest-distance based method's 's time complexity increases with the number of agents.
On the Dense Maze and Dense Room maps, all HMAGAT variants again have similar SoC and success rates. However, Dense Wa Warehouse, the shortest-distance based HMAGAT has worse
15

---

Published as a conference paper at ICLR 2026
Spazoo Hazo
Expty Room
Sparse We Harwhouse
Macr
Den
Dense Warchouse
Success Rute
Runtine (5)
Rel. SoC
Pagents
#agents
#agents
#agents
Ragonts
Rugonts
SSIL
MAPF-OPT-DDG
HMAGAT (Lioyd)
HMAGAT (k-means)
MAPF-GPT (85M)
(Shortest Dist.)
DCD
MAPF-GPT (6M)
MAPF-GPT
Figure 8: Evaluation of the learning-based MAPF policies on small maps, averaged over 128 instances. Transparent regions represent 95% confidence intervals. SoC is reported relative to lacam3 (w/ s0 time limit).
SoC, and both the shortest-distance based and Lloyds-based HMAGAT have slightly worse success rates. In these scenarios, the shortest-distance based HMAGAT is again the slowest, with the gap being much more pronounced. This is expected because unlike the colouring- only need to compute the colouring once. the shortest-distance based method needs to compute the shortest distances every 5 timesteps, which means that for the more complex maps, where the agents take longer reach their goals, the overhead of computing the shortest distances is more pronounced.
methods that
1akJ03d
Beriin
Success Rate
Rontine (4)
Rel. SoC
12
1.2
#agents
#agoots
#agcnts
#agents
MAPF.GPT-DDG
HMAGAT (Liyyd)
HMAGAT (e-means)
- SCRIMP
MAPF-GPT (85M)
MAGAT
HMAGAT (Shortast Dist.)
MAPF-GPT (6M)
MAPF-GPT (2M)
Figure 9: Evaluation of the learning-based MAPF policies the large maps, averaged over 128 instances. Transparent regions represent 95% confidence intervals. SoC reported relative to 1acam3 (w/ 30 time limit).
16

---

Published as a conference paper at ICLR 2026
Large maps. Figure Sigure9ssowee shows the results the large maps. On the Game maps, again all HMAGAT variants perform nearly identically in terms of SoC and all have perfect success rates. k-means- based HMAGAT is the fastest, with the shortest-distance based HMAGAT being slightly slower, with the gap increasing with the number of agents. Lloyds-based HMAGAT is the slowest, although the gap does not increase with the number of agents. This is expected because the colouring is computed only once and is independent of the number of agents. Lloyds is slower than k-means as noted in Appendix A and this becomes apparent here, where [V] is large.
On the City maps, k-means-based and shortest-distance based HMAGAT perform nearly identically in terms of SoC and have perfect success rates. Lloyds-base based HMAGAT, on the other hand, times out in these scenarios. This is because [V] here is even larger than the Game maps. We see that the shortest-distance based HMAGAT is faster than k-means-based HMAGAT here, although the gap decreases with the number of agents. This is expected because the total time complexity of hyper- graph generation in shortest-distance based method depends on the number of time steps and the number of agents, while for the k-means-based method, it depends with a large and sparse map, [V] is large leading to a higher time complexity for the k-means-based method, but not for the shortest-distance based method, which is independent of [V] (assuming the number of time steps as an independent variable). However, as the number of agents increases, the time complexity of the shortest-distance based method increases, leading decrease in the gap.
[V]. Since we are dealing
We see that k-means- based HMAGAT obtains a good balance between performance and speed across all maps, and so, for the rest of the analysis, we focus on this variant.
C.3 COMPARISON OF HMAGAT WITH OTHER METHODS
Small maps. Figure 8 shows the results on the small maps. HMAGAT consistently outperforms MAGAT, WAPF-GPT-DEE
MAPF-GPT (6M), MAPF-GPT (2M), SSIL, SCRIMP and DCC in terms of SoC and success rates across all maps and agent counts. The only exception being MAPF-G2T-DDO and MAPF-GPP GPT on Dense Room, where they have higher success rates, but still have worse SoC.
On the sparse maps, HMAGAT and MAPF-GPT (85M) achieve similar SoC, with HMAGAT having slightly worse performance on the highest agent count scenario for Empty Room and Sparse We Warehouse, but better performance on Sparse Maze. On the Dense Maze map, HMAGAT consistently outperforms MAPF-GPT (85M), with the gap increasing fair amount for the highest agent count scenario. For the Dense Room and Dense Warehouse maps, MAPF-GPT (85M) has slightly better SoC, except for the highest agent count scenario on Dense Warehouse, where HMAGAT has better SoC. In this scenario, EMAGAT has significantly higher success rate, achieving 89.1% success rate compared to 4% for MAPP-GPT T (85M).
Notably, HMAGAT is significantly faster than MPP (85M) across all maps and agent counts, and has lower slope in the runtime vs. number of agents plots.
Large maps. Figure 9 shows the results on the large maps. HMAGAT consistently outperforms MAGAT, MAPF-GPT (85M), MAPF-GPT-DDS MAPF-CPT (6M), MAPF-GPT (2MM), SCRIMP and DCC. HMAGAT and MAGAT the only two methods that able easily scale to these maps and have perfect success rates across all maps and agent counts. SSTL achieves a similar SoC to HMAGAT for the lower agent count scenarios, but seems unable scale to various higher agent count scenarios.
HMAGAT consistently achieves Rel. SoC close to 1.0, i.e. it produces solutions close to lacam3's quality.
MAPE-GPT (85M) and MAPF-GPT-DDG. Andreychuk et al. 2025b) claim that MAPF-GPT-DDG matches the performance of MAPF-GPT (85M), and, at times, even outperforms it. However, in our experiments, we see that MAPF-G2 --DDD consistently underperforms MAPF-G?T (85M), except for the large maps, where MAPF- GPT (85M) fails to scale. We believe that this discrepancy is due to the fact that AAndreychuk et al. (2025b) evaluate these models without PIBT-based collision shielding (Okumura et al. [022] Veerapaneni et al., 2024). MAPF-G2T-DDG likely produces solutions with lower collisions, due to the finetuning. leading to better performance than MAPF-GPT (85M) when not using any advanced collision shielding. To
17

---

Published as a conference paper at ICLR 2026
verify this, evaluated MAPF-GPI-DDG and MAPF-GPT (85M) without PIBT-based collision shielding on Sparse Maze, Empty Room and Sparse Warehouse maps with 128 agents each. Table shows the results. We see that MAPF-GPT (85M) struggles even these sparse maps and MAPF-GPT-DDG consistently outperforms it, verifying our hypothesis.
However, seen in Figure when using PIBT-based collision shielding, MAPF-GPT (85M) sistently outperforms MAPF -PP--DD.
Table 5: Comparison of MAPF GPT (85M) and DAPF-GPT-DDU without PIBT-based collision
shielding. Averaged over 128 instances, each with 128 agents.
Sparse Maze
Empty Room
Sparse Warehouse
Metric
Method
TPT (85M)
6.3%
2.3%
39.1%
Success Rate
MAPF - -PPF-GGTTDDDDD
76.6%
96.9%
99.2%
Rel. SoC (95% CI)
MAPF (85M)
6.93 + 0.24
5.81
+ 0.14
5.61
0.23
MAPF-GPT-DDG
3.81 + 0.20
3.02 + 0.14
3.05 + 0.11
C.4 HGNN vs GNN ON MAXIMUM AGENT DENSITY
Table 6 shows the performance HGNN and GNN on different maps with the maximum agent density with additional maps compared to Table | GNN in terms of solution quality.
We see that HGNN consistently outperforms
D FURTHER DETAILS ON HAND CRAFTED SCENARIOS
Scenario To calculate o the attention a node i pays to an agent j in the I-th layer of HMAGAT, we simply use the following sum:
E
KETGGAAEEOONNETTO
We present the attention scores for the GNN and HGNN models in the first layer Tables and g We also present the attention scores averaged across all layers in Tables and [00 with the coefficient of variation in Table 11 We see that the HGNN model consistently has lower coefficient of variation across all groups, indicating that it more robust to the increase in the number of agents in low-importance regions.
We have seen that the HGNN model able to handle the increase in the number of agents less important regions. However, we also need to ensure that when the number of agents in the important regions increases, we do not see significant decrease in the attention scores for this region. Towards this end, we construct scenario shown in Figure 10
In contrast to the scenario described in Figure 7 (left), we now have agent O's greedy path overlap- ping with paths of agents in group 3, i.e the group for which we vary the number of agents. Thus, agent 0 is expected to primarily attend to agents in group 3. Table [2] shows the HGNN attention scores for this scenario. We that the attention scores for group 3 stay high as we vary the number of agents, indicating that the HGNN model is able to maintain high attention scores for the important region.
Scenario While calculating the Shapley values, we average the scores between the ones com- puted on the original map shown in Figure 7 (right) and map formed by horizontally flipping in order to reduce the effect of any asymmetries learnt by the models.
E INFORMAL PROOF OF ATTENTION DILUTION
We provide an informal analysis, demonstrating that GNNs face attention dilution, which HGNNs capable of mitigating. We first start with demonstrating that GNNs suffer from attention dilution.
18

---

Published as a conference paper at ICLR 2026
Table 6: Comparison of HGNN and GNN, corresponding to HMAGAT woo embellishments and MAGAT, on different maps with the maximum agent density. Results are over 128 instances per map. Rel. SoC the sum-of-costs relative lacam3. for which show the 95% confidence intervals.
Sparse Mazc 93.8%
Sparse Warchouse
Sparse
Metric
Method
ost.003d
1ak303d
Room
Success
GNN
96.9%
100.0%
100.0%
100.0%
Rate
HGNN
93.0%
100.0%
100.0%
100.0%
100.0%
GNN
1.99 + 0.04
2.16 + 0.04
1.86 + 0.02
1.06 0.00
1.05 + 0.00
Rel. SoC
HGNN
1.91 0.04
1.95 + 0.02
1.69 + 0.02
1.05 + 0.00
1.04 + 0.00
Dense
Dense Marehouse
Dense
Metric
Method
Paris
Borlin
Maze
Room
Success
GNN
72.7%
2.3%
66.4%
100.0%
100.0%
Rate
HGNN
75.8%
39.8%
75.0%
100.0%
100.0%
GNN
2.07 0.09
2.12 + 0.10
2.63
0.07
1.03
0.00
1.02 0.00
Rel. SoC
HGNN
1.79 - 0.09
1.78 + 0.08
2.35 = 0.06
1.02 - 0.00
1.02 0.00
Table 7: GNN Attention scores in the first layer for agent over the different groups in Figure (left).
Agents
Group
Group
Group
Group 3
Agents
0.394750
0.257375
0.192023
0.155852
Agents
0.286059
0.234413
0.186970
0.292558
Agents
0.251 166
0,202690
0.161970
0.384175
Agents
0.215447
0.172166
0.146812
0.465576
Agents
0,194606
0.159428
0.135639
0.510326
Table 8: HGNN Attention scores in the first layer for agent over the different groups in Figure (left).
Agents
Group
Group
Group 2
Group 3
Agents
0.024621
0.104523
0.493603
0.377252
Agents
0.027046
0.110814
0.583928
0.278213
Agents
0,024019
0.113196
0,603738
0.259047
Agents
0.023478
0.102690
0,571674
0.302157
Agents
0.023619
0.104273
0.564101
0.308007
Table 9: GNN Attention scores averaged across layers for agent over the different groups in Figure (left).
Agents
Group
Group
Group 2
Group 3
Agents
0.170300
0.381573
0.190819
0.257309
Agents
0.130953
0.349720
0.188699
0.330629
Agents
0.117691
0.329456
0.171886
0.380967
Agents
0.109234
0.278605
0.164050
0.448111
Agents
0.099965
0.249049
0.156532
0.494454
19

---

Published as a conference paper at ICLR 2026
Table 10: HGNN Attention scores averaged across layers for agent over the different groups in Figure (left).
Agents
Group
Group
Group 2
Group 3
Agents
0.103088
0.274550
0.305216
0.317146
Agents
0.119637
0.247633
0.350739
0.281991
Agents
0.118572
0,239537
0.334259
0.307632
Agents
0.120345
0.219097
0.329250
0.331308
Agents
0.117992
0.221249
0.319412
0.341347
Table 11: Coefficient of variation of the average-attention scores (across layers) when varying the number agents in group 3 in Figure (left).
Method
Group
Group 1
Group
Group 3
GNN
21.85%
16.87%
8.63%
24.54%
HGNN
6.24%
9.39%
5.17%
7.26%
GNN / HGNN
3.5012
1.7957
1.6686
3.3794
E.1 GNNS SUFFER FROM ATTENTION DILUTION
Consider graph g (V,E) and node E V with neighbourhood Mi, where can partition N₁ into two subsets:
Anoise; nodes in a similar locality that do not aid in predicting i's label.
Nies: the remaining nodes in the neighbourhood.
Let ai denote the pre-softmax attention score for node j Nr with respect node and let the normalised attention scores be given by Oii ExeN, exp(a.))
expla.s)
To demonstrate attention dilution, we construct a new graph -V', E') by adding more noisy nodes to graph G. Specifically, we define the neighbourhood of node in the new graph as No Nr U A', where nodes in A' are in similar locality Aroise, The other nodes retain their original features. Let x/, and w represent the node embeddings and edge vectors in the new graph, with d' and oky denoting the pre-softmax and normalised attention scores, respectively.
Since, x² = Xx and W/y = wiy for all j E Mi. we have a' = ai for all j E No.
Figure 10: Hand-crafted scenario to illustrate the effect of increasing number of agents in important regions on the attention scores. Filled circles represent the agent locations, while the empty ones represent their targets. Agents are grouped via colours, with groups 0 to 2 consisting of their cor- responding agents only, while group 3 consists of agents 3 to 7. We start with the agents numbered from 0 to and add more agents to group in order of their numbering.
20

---

Published as a conference paper at ICLR 2026
Table 12: HGNN Attention scores the first layer over groups.
Agents
Group
Group
Group 2
Group 3
Agents
0.000949
0.001 296
0.001605
0.996150
5 Agents
0.002126
0.000187
0.000252
0.997436
Agents
0.002358
0.000235
0.000335
0.997073
Agents
0,002095
0,002070
0.002800
0.993035
Agents
0.005777
0.003658
0,005720
0.984845
Thus, for all nodes j E &Mess, we have:
exp(aly) a = ΣKEN; exp(a'u) ΣKEN, exp(asx) + ENEN exp(a'a)
exp(asj)
<
Osj
This shows that the attention scores for nodes in Mi have decreased due to the addition of noisy nodes in A', demonstrating attention dilution.
E.2 HGNNS CAN MITIGATE ATTENTION DILUTION
Now, we demonstrate that HGNNs can mitigate attention dilution:
Consider a hypergraph H = (V, corresponding to the same instance represented by the graph G. Again, let node V have a node neighbourhood that can be partitioned into two subsets Niuoiee and Notest, with nodes A being in a similar locality. Assume an appropriate hypergraph structure such that nodes in Auuoiee belong the tail of single hyperedge e, EH. while nodes in A belong to the tails of other hyperedges. Eee C. Eg, with i being in the head of all these hyperedges. Let Oej be the attention score for node j with respect to hyperedge e, and let aje and Oge be the pre-softmax and normalized attention scores for hyperedge e with respect to node respectively. Here we have:
exp(aij)
Oite
ke JUE... exp(aix)
Also, let the hyperedge embedding for an hyperedge be h
Now, we construct the new hypergraph H' (V", E corresponding the same instance repres- ented by the graph g'. Here we have V = VUA' A', with nodes in A' having similar locality to nodes in Mumisee Since they share a locality. we can assume that nodes in Nuuose A' belong to the tail of the same hyperedge e', E Ejg, while nodes in Arest belong to the tails of other hyperedges, Erea. with being in the head of all the hyperedges, similar to the original hypergraph.
For all nodes j E Afestt we have:
de = aej
This is because the hyperedges Ees have the same tail nodes as the original hypergraph, leading to the same attention scores. This means the hyperedge embeddings for hy hyperegges in E remain unchanged, i.c. h. = he for all e E Egert This also means that the pre-softmax attention scores for hyperedges in Erest remain unchanged, i.c. d/ aie for all Erest
With regards to hyperedge e'= The original hyperedge e, consisted of nodes not helpful with i's label prediction. Since the hyperedge embeddings computed node embeddings, simply adding more nodes to the tail of the hyperedge does not increase the magnitude or relevance of the hyperedge embedding. Since the new nodes, A', are also helpful for predicting node i's label, they will not increase the hyperedge's attention score. Thus, we can assume that the pre-softmax attention score for hyperedge e', remains unchanged, i.e. alee aie.
weighted combination of the
Thus, for all nodes j E Nrestt we have:
exp(a'))
exp(aij)
ag Σ Ekete Er exp(a(x)
Oij
Σ ke few PUm exp(a:t)
21

---

Published as a conference paper at ICLR 2026
This shows that the attention scores for nodes in M remain unchanged despite the addition of noisy nodes A', demonstrating that HGNNs can mitigate attention dilution. Thus, unlike GNNs, introducing additional noisy nodes does not dilute the attention assigned to informative nodes.
F FURTHER DETAILS ON PAIRWISE INTERACTION MODELLING FOR MAPF
MAPF solvers take as input information about each agent, and use this information to compute paths for all agents. For MAGAT/GNNS, each agent's information represented using relevant node em- beddings, while for MAPF-GP /frr-GG/rannsormeers. this information is represented using relevant token embeddings. An action for agent i predicted based on the information of agent and the informa- tion of other agents. When only pairwise interactions are considered, we say the action for agent oN is predicted as follows:
((x;, JEN.
where x; is the information of agent i, ø is function that models the interaction between agent i and agent j and + is an aggregation function for the interactions.
In the context of Figure I(c), show the pairwise interactions, d, in parts (iii-v,, with respect to agent A. + can be taken to be any aggregation function; in this case, it could just be the intersection operation among the pairwise paths. This results in the predicted path for the agents as shown in part (ii). However, we see that this predicted path not optimal, and the purely pairwise interactions fail to capture the group interaction that leads to the optimal solution shown in part (i).
In the context of MAGAT and -PPT, o(x;, Xý) is the messages in the message passing frame- work and the value vector in the attention layer, respectively, while ① is the attention-based weighted-mean aggregation in both cases. Although these mechanisms are only using pairwise interactions, they can still perform well on MAPF tasks, by learning to approximate group interac- tions. They can do so by: (i) using high-dimensional embeddings that can simply encode all the information about other agents, followed by complex enough function to decode this information, or (ii) stacking multiple layers of pairwise interactions, which can allow for indirect capture of group interactions. Both MAGAT and KAPF-GPT use combination of these two strategies. However, both of these strategies have their limitations.
The first strategy relies on the model's s ability to encode and decode all relevant information about other agents within high-dimensional embeddings. This may work well for small-scale problems, but as the number agents increases, the amount of information that needs to be encoded grows significantly, making it increasingly difficult for the model to effectively capture all necessary inter- actions. The second strategy, stacking multiple layers of pairwise interactions, can help indirectly capture group interactions, but given fixed number of layers, there is limit the complexity of group interactions that can be effectively modelled. As the number of agents increases, the depth required to capture all relevant group interactions may exceed practical limits.
In contrast, hypergraph- based approaches can directly model the group interactions among agents, allowing for a more natural and efficient representation of the MAPF problem. Also, purely from an alignment perspective, hypergraph-basee approaches align better with the underlying structure of interactions in optimal MAPF solutions.
G FAILURE MODE ANALYSIS OF HMAGAT
In Figure we that HMAGAT (k-means) is a lower success rate Dense Room with 128 agents compared to MAPF-GPT-DDG, Below, we analyse the failure modes of HMAGAT in these scenarios.
First, we note that even in scenarios where HMAGAT fails in the Dense Room maps, it achieves an average of 97.3% partial success rate (percentage of agents that reach their goals at the end of task). Of the 2.7% agents that failed to reach their goals at the final timestep, 90% reached their goal sometime during the programme execution, but later had move.
Table [3 shows the breakdown of the failure modes for these 2.7% of the agents that fail to reach their goals. Here, we say agent deadlocked if, for the last actions, it stayed the same
22

---

Published as a conference paper at ICLR 2026
Table 13: Failure mode analysis of HMAGAT (k-means) on Dense Room with 128 agents.
Failure Mode
Percentage
Deadlock
3.4%
Livelock
46.4%
Hit max timestep limit
50.2%
location. An agent was said be livelocked, if it only oscillated between locations at least times before hitting the max timestep limit. Rest of the agents were assumed to have failed due to simply hitting the max timestep limit.
We performed further analysis on the livelocked agents, and found that all livelocks involved oscil- lation between only two locations. Given this, should be possible improve the success rate of HMAGAT, using some straightforward deadlock/livelod" detection mechanism, escaping the dead- lock/livelock by increasing the sampling temperature or following a greedy path whenever dead- lock/livelock is detected.
H FURTHER ATTENTION DILUTION EXPERIMENTS
In Figure 0 we have seen how GNNs suffer from attention dilution, and HGNNs can mitigate them on single instances of Dense Za and Dense Warehouse maps.
In order further verify this, we perform experiments across multiple instances of highest agent density scenarios across different maps. As relative measure of the attention dilution, we calculate the average normalised entropy of the attention scores, averaged across all execution steps and 128 instances, using the formula below:
Oij log oij logl/V
H -=
Σ JEN,
I
TEV
where V is the set of nodes of the graph and M₁ is the neighbourhood set of node i.
Table 14: Average normalised entropy of attention scores for GNN and HGNN models on highest agent density scenarios across different maps. Results are averaged over 128 instances, and their 95% confidence intervals are reported.
Spar rse Maze
Empty
Dense
Dense
Dense Warehouse
Method
Room
Ma ze
Room
GNN
0.659 + 0.000
0.662 + 0.000
0.715 + 0.001
0.733 + 0.001
0.651 + 0.000
HGNN
0.514 + 0.000
0.502 + 0.000
0.565 + 0.001
0.592 + 0.001
0.523 + 0.000
Table shows the average normalised entropy of attention scores for GNN and HGNN models. We see that the HGNN model consistently has significantly lower average normalised entropy of attention scores across all maps, indicating that GNNs suffer from attention dilution, while HGNNs mitigate them.
I HYPERPARAMETER SENSITIVITY
We trained our HMAGAT (k-means) model with = 10% the number of vertices the MAPF grid, [V]. and with communication radius Reomm 7. In the following tables, present the performance of our HMAGAT model with varying values of l and Reomm during test time.
Table 15 and Table 16 show the performance of HMAGAT (k-meaans) with varying values of k and Reomm respectively. We see that the performance of HMAGAT (k-means) is relatively stable across different values of and Reomm, The success rates vary slightly, but this variation might also be due
23

---

Published as a conference paper at ICLR 2026
Hyperparameter sensitivity analysis of HMAGAT (k-means), with varying values of on the highest agent density instances. Results are averaged over 128 instances. 95% confidence intervals are reported for Rel. SoC.
Table 15:
Metric
k
Sparse Maze
Empty Room
Dense Maze
Dense Room
Dense Warehouse
5%
90.6%
100.0%
62.5%
60.2%
82.0%
Success Rate
10%
93.0%
100.0%
73.4%
60.9%
89.1% %
20%
91.4%
100.0%
68.8%
61.7%
93.0%
5%
1.45 + 0.03
1.36 0.01
1.31 + 0.07
1.64
0.05
1.04 + 0.05
Rel. SoC
10%
1.47 + 0.04
1.34 0.01
1.27 + 0.06
1.63 + 0.05
1.02 = 0.05
20%
1.45 + 0.03
1.34
0.01
1.26
0.06
1.62 0.05
1.02 = 0.05
Table 16: Hyperparameter sensitivity analysis HMAGAT (k-means), with varying values of R.oom on the highest agent density instances. Results are averaged over 128 instances. 95% confidence intervals are reported for Rel. SoC.
Metric
pcomm
Sparse Maze
Empty Room
Dense Maze
Dense Room
Dense Warehouse
93.8%
100.0%
73.4%
60.2%
89.1%
Success Rate
93.0%
100.0%
73.4%
60.9%
89.1%
93.0%
100.0%
73.4%
66.4%
90.6%
1.46 0.03
1.35 + 0.02
1.28 + 0.06
1.63 + 0.04
1.01 0.05
Rel. SoC
1.47 + 0.04
1.34 0.01
0.06 1.27 0.06
1.63 + 0.05
1.02 + 0.05
1.46 0.03
=.00
1.25
1.62 + 0.05
1.03 0.05
to randomness introduced by the sampling based nature of the models. The relative SoC values main robust across different hyperparameter settings, indicating that the solution quality of HMAGAT (k-means) not significantly affected by these hyperparameters.
cansling-based
24


Reviews:
[{"review_id": "aWyOY6b6kb", "reviewer": "Reviewer_5P7E", "summary": "The paper aims to address the limitation of GNN-based approached for MAPF that relies on message passing between pairs of agents. However, in dense environments, it requires higher-order group interaction where a large number of irrelevant neighbors reduce the focus on critical agents. The paper proposes HMAGAT, which is an imitation learning framework that uses HGNN to model group dynamics. The architecture is a CNN-> HGNN -> MLP. The hyper graph generation strategies include k-mean, Lloyd’s alogirhtm and shortest-distance based heuristics. Empirically, HMAGAT outperforms state-of-the-art with smaller network sizes and less training data.", "questions": "When you compute the Rel. Soc, how do you deal with the instances that are unsolved, especially when a. different solvers solve a different set of instances?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. It is a novel application of hypergraphs to scale on large MAPF instances. \n2. The integration of multiple hyper graph generation methods is a new contribution.\n3. The analysis of HGNN vs GNN provides a good insight into why HGNN is better than GNN.", "weaknesses": "1. The main weakness is the lack of non-ML baselines, such as simple methods like priority planning and more advanced solvers like Large Neighborhood Search or LACAM mentioned in the paper. Those are very efficient and effective solvers that can scale to instances as large as those evaluated in the paper.\n2. It isn’t clear how the Rel. SoC metric is computed. See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "edLnREQ8ml", "reviewer": "Reviewer_VXsq", "summary": "This paper proposes HMAGAT, a hypergraph-based imitation learning framework for Multi-Agent Path Finding (MAPF). It argues that pairwise interaction modeling, as commonly done via GNNs or transformers, is insufficient for capturing the inherently group-based dependencies among agents. By introducing directed hypergraph attention layers, HMAGAT captures higher-order interactions, leading to improved solution quality and scalability. The model achieves strong empirical results, outperforming prior SOTA while using little data and parameters.", "questions": "1.\tHow are the hyperedges dynamically generated during training and inference? Are they based purely on spatial proximity, or do they incorporate learned attention or communication priors?\n\n2.\tCan the authors formalize or provide intuition for how HMAGAT captures higher-order dependencies that are provably beyond the capacity of pairwise GNNs or transformers?\n\n3.\tWhat is the asymptotic complexity of HMAGAT’s message passing with respect to the number of agents and hyperedges? Is there a practical limit where hypergraph construction becomes prohibitive?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.\tThe paper convincingly argues that MAPF requires modeling joint dependencies beyond pairwise interactions. The use of hypergraphs is theoretically justified as a natural representation of group interactions, which is both elegant and underexplored in this context.\n\n2.\tHMAGAT extends the MAGAT architecture by replacing GNN layers with hypergraph attention modules and introducing dynamic hypergraph generation strategies. The directionality and adaptive nature of these hyperedges introduce inductive biases that align well with MAPF’s structure.\n\n3.\tThe experimental section is robust, spanning multiple map types (small, sparse, dense, and large). HMAGAT demonstrates substantial gains in Sum of Costs (SoC) and success rates, especially in high agent-count and dense environments. The runtime analysis shows HMAGAT is faster and more scalable than MAPF-GPT while maintaining solution quality.", "weaknesses": "1.\tWhile the motivation is clear, the paper lacks a formal analysis of why and under what conditions hypergraph attention improves over pairwise attention. A discussion of expressivity (e.g., via Weisfeiler-Lehman hierarchy or permutation invariance properties) could strengthen the theoretical foundation.\n\n2.\tAlthough HMAGAT scales better than MAPF-GPT, it is not evident how hypergraph construction costs scale with agent counts beyond the tested benchmarks. The paper would benefit from a complexity analysis or ablation of hypergraph size versus performance.\n\n3.\tAll evaluations are performed on Pogema-like benchmarks. It remains unclear how HMAGAT performs on out-of-distribution environments (e.g., dynamic obstacles, non-grid worlds). Including cross-domain tests or transfer experiments would strengthen the empirical story.\n\n4.\tThe ablation study focuses on performance comparisons but could better disentangle the contributions of hypergraph generation, attention mechanisms, and training data reduction. It’s difficult to isolate which aspect contributes most to the gains.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PeNEEQJpn3", "reviewer": "Reviewer_KnuG", "summary": "The paper introduces HMAGAT, a hypergraph-based extension of the MAGAT framework for multi-agent pathfinding. The core idea is to capture higher-order agent interactions beyond pairwise relationships by representing agent dependencies through hyperedges. The method integrates several enhancements, including observation encoding improvements, post-training quality optimization, and temperature-based sampling during inference. The authors evaluate HMAGAT across multiple benchmark MAPF environments, comparing it to state-of-the-art learning-based methods.", "questions": "Q1: How does adding PIBT shielding affect the model’s runtime performance?\n\nQ2: The runtime spikes observed seem unusual for the MAPF-GPT family (especially on _ost003d_). Did the authors investigate this behavior, and how exactly was runtime measured or computed?\n\nQ3: Were the authors willing to provide the raw testing data or the code  to run a full evaluation (script to run all testing instances) of the proposed approach?\n\nQ4: How much GPU time is required to reproduce the testing results?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is generally well-written and clearly structured. The graphical illustrations are clear and informativel.\n- The experimental evaluation includes a solid and well-chosen set of test maps.\n- HMAGAT demonstrates strong empirical performance across a diverse set of benchmarks, showing both scalability and robustness.", "weaknesses": "W1: The motivational example in Figure 1(c) is unclear, and I do not fully understand what prevents models such as MAPF-GPT from learning an optimal policy when expert data for this case are provided. It would be helpful if the authors clarified what exactly is meant by pairwise interactions in MAPF and why these interactions would limit a learnable model from reproducing the expert’s optimal SoC solution. A formal definition or additional explanation would make the example more convincing.\n\nW2: Based on the ablation results in Figure 5, the final performance appears to stem from multiple components, including Hypergraphs, OE Quality Improvement, Post-Train Quality Improvement, and Temperature Sampling. As a result, the initial motivation regarding pairwise interactions seems less supported, and the impact of the hypergraph component does not appear dominant. This also suggests that the paper’s focus on hypergraphs for highly-coupled multi-agent problems is somewhat overshadowed by the combination of techniques used to outperform current learnable MAPF approaches. \n\nW3: The proposed approach builds on several prior methods and involves a multi-stage, complex pipeline, including the MAGAT base, the addition of Hypergraphs and a mechanism to prepare observations, offline training on expert data, subsequent online fine-tuning, and a separate RL-trained model for temperature sampling. While this combination achieves strong performance, it raises concerns about the overall simplicity and generality of the approach. Relying on heavily staged, task-specific designs may limit scalability and the ability to leverage general computation, suggesting that more unified or end-to-end approaches could be more broadly effective.\n\nW4:  I’m not entirely convinced that collision shielding should be applied to all approaches (as recommended by Veerapaneni et al., 2025). This suggestion is not theoretically motivated, and based on decision-making theory, it effectively changes the policy. We can consider two policies: $\\pi$, the default one, and $sh(\\pi)$, the policy with shielding. When performing imitation learning from an expert, applying shielding introduces a distributional shift. \n\nFor MAPF-GPT-85M, this works well because the model is trained on expert data where no collisions occur, so shielding helps, even with the shift between PIBT and LaCAM. However, for MAPF-GPT-DDG-2M, this is not the case, since the model was fine-tuned and the model performance was influenced by its own behavior.\n\nFormally, since the policy determines the trajectory of states, applying shielding changes the state distribution: $s_{t+1} \\sim P(\\cdot \\mid s_t, a_t), \\quad a_t \\sim \\pi(a_t \\mid s_t)$ versus $s'_{t+1} \\sim P(\\cdot \\mid s'_t, a'_t), \\quad a'_t \\sim sh(\\pi)(a'_t \\mid s'_t),$\n\nwhich implies that $p(s_t) \\neq p(s'_t)$ and consequently $p(o_t) \\neq p(o'_t)$, where $o_t$ denotes agent' observation at time $t$. Thus, shielding induces a distinct observation distribution, on which the model was not trained.\n\nThe proper approach, in my view, is to fine-tune MAPF-GPT-DDG in an environment that includes shielding to eliminate this inconsistency.\n\nW5: Following up on the previous weakness, I believe it is not entirely fair to apply modifications to existing approaches without conducting a proper ablation study. It is not clear how shielding influences the algorithms to which it was applied. While the authors provide some ablation results in Table 5 of the appendix, a more thorough analysis would involve testing all approaches both with and without shielding, and reporting the complete set of metrics (including success rate, SoC, and runtime).\n\nW6: It seems to be an overstatement in the experimental results that HMAGAT consistently outperforms larger models, except for MAPF-GPT-85M. For example, MAPF-GPT-DDG (2M) shows better performance in instances with a large number of agents for the Sparse Maze and Dense Room scenarios, and comparable performance in the Empty Room and Dense Maze environments. Moreover, despite achieving better or similar success rates, MAPF-GPT-DDG exhibits lower performance in terms of SoC, which appears counterintuitive. It would be helpful if the authors investigated this further and provided an explanation of how these plots were generated. \n\nDespite the major concerns raised, I remain open to discussion and willing to adjust my score depending on how the identified weaknesses are addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DXscMG4SaH", "reviewer": "Reviewer_YpAe", "summary": "This paper proposes HMAGAT, a hypergraph neural network-based approach for Multi-Agent Path Finding (MAPF). The authors argue that existing GNN-based methods are fundamentally limited by pairwise message passing, which leads to attention dilution in dense scenarios and fails to capture group interactions. HMAGAT leverages directed hypergraphs with attention mechanisms to explicitly model higher-order agent interactions. The method achieves impressive empirical results, matching or outperforming MAPF-GPT (85M parameters) while using only 1M parameters and training on 100× less data. The paper includes comprehensive experiments across 10 map types, detailed ablation studies, and insightful analyses using attention distributions and Shapley values.", "questions": "1. The 100× training data difference between HMAGAT (21K) and MAPF-GPT (3.75M) is my biggest concern. Can you train MAPF-GPT on your 21K instances and report results? This would isolate whether your gains come from architectural improvements or simply from the baseline being undertrained.\n\n2. Can you provide some theoretical analysis—even informal—about what makes hypergraphs better suited for MAPF?\n\n3. What are the typical failure modes when HMAGAT doesn't succeed? Understanding when hypergraphs fail would help clarify their scope of applicability.\n\n4. Can you demonstrate that attention dilution happens systematically in real benchmark runs, not just the two hand-crafted scenarios? Maybe show attention statistics across many Dense Warehouse episodes?\n\n5. How much wall-clock time does training take for HMAGAT compared to MAGAT? What's the computational overhead of hypergraph construction?\n\n6. What guidance would you give practitioners for choosing between Lloyd, k-means, and shortest-distance strategies? When does each work best?\n\n7. How sensitive is performance to hyperparameters like k (number of colors), R^comm, and R^obs?\n\nThe core idea here is interesting and the paper is generally well-written. The motivation for using hypergraphs in dense coordination scenarios resonates with me, and the empirical results look promising. That said, the training data confound and lack of theoretical grounding  are issues that need addressing. I'm also curious about the failure analysis  and whether attention dilution is a systematic phenomenon  or mainly visible in constructed examples. If the rebuttal can provide satisfactory answers to these concerns, particularly the first two, I'd be happy to reconsider my score.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The core motivation is strong and well-articulated. The observation that pairwise interactions are insufficient for highly-coupled multi-agent coordination problems is intuitive and important. Bringing hypergraph representations to MAPF is a natural and valuable direction—recent work has shown promise for hypergraphs in other multi-agent settings (e.g., trajectory prediction, formation control), and this paper extends that thinking to a challenging planning domain. The research question \"Can hypergraphs scale beyond simple group settings to capture complex, highly-coupled multi-agent tasks?\" is well-posed and addresses a real gap in the literature.\n\nThe attention dilution problem is clearly articulated and convincingly demonstrated. Figure 6 shows that GNN models spread attention across many agents in the middle range, preventing high focus on truly critical interactions, while HGNN maintains better differentiation. The hand-crafted Scenario 1 illustrates this effectively—as irrelevant agents are added to less important regions, GNN's attention to important agents becomes increasingly variable, while HGNN remains stable. This is a genuine problem that matters in practice.\n\nThe Shapley value analysis in Scenario 2 provides valuable interpretability. The results effectively demonstrate that the model captures group coordination patterns—showing substantially higher influence for agents involved in coupled interactions compared to isolated ones, despite symmetric spatial positions. This kind of mechanistic understanding is useful and relatively uncommon in multi-agent learning papers.\n\nThe experimental evaluation is comprehensive and well-designed. Testing across 10 diverse map types with varying densities provides solid evidence. The Dense Warehouse results are particularly striking, showing dramatic improvements in success rates at high agent densities where baseline methods struggle significantly. The ablation study properly isolates contributions, and the progression shows consistent improvement. The paper is clearly written with good visualizations, and the promised code release aids reproducibility.\n\nThe parameter efficiency and inference speed improvements are practically significant. These gains matter for real-world deployment in warehouse automation or traffic management scenarios.", "weaknesses": "My primary concern is that while the motivation is sound, the execution lacks depth. The architecture in Equations (1)-(4) adopts standard hypergraph attention formulations without meaningful adaptation to MAPF's specific structure. I appreciate that you're bringing hypergraphs to this domain, but the technical contribution feels more like careful engineering than methodological advancement. For instance, you could exploit MAPF-specific structure—agents have goals, there are collision constraints, paths have temporal dynamics—but the hypergraph construction treats this as a generic spatial proximity problem. The Lloyd/k-means/shortest-distance strategies are standard clustering approaches applied fairly directly. Given that hypergraphs have been explored in related multi-agent domains, I'd expect deeper innovation in how the representation is tailored to pathfinding constraints and objectives.\n\nThe training data disparity undermines the paper's central claim. You train on 21K instances while MAPF-GPT uses 3.75M—a 100× difference. The conclusion that \"appropriate inductive biases are often more critical than training data size or sheer parameter count\" is stated boldly but not properly validated. You're comparing two confounded variables simultaneously (architecture AND data scale), making it impossible to isolate the effect. It's entirely plausible that MAPF-GPT is simply undertrained relative to its capacity. I recognize that generating millions of expert trajectories is expensive, but at minimum, you should show MAPF-GPT trained on your 21K instances to establish whether the gap persists under equal data conditions. This is a fundamental experimental control that's missing, and it weakens confidence in the main message.\n\nThe theoretical foundation is thin. You provide no formal analysis of when or why hypergraphs should outperform GNNs beyond intuition and two constructed scenarios. What types of coordination patterns can HGNNs represent that GNNs cannot? Are there expressiveness results or approximation guarantees? The attention dilution observation is insightful but empirical—showing it occurs systematically across many real benchmark instances (not just hand-crafted examples) would be more convincing. The paper would benefit substantially from even informal theoretical characterization of the representational differences.\n\nThe hypergraph generation lacks principled justification. Why these specific strategies? The shortest-distance method shows mixed results across different maps and has higher computational overhead, yet there's no clear guidance on when each strategy is appropriate. The \"soft boundary\" operation (discarding half the colors) appears to be a critical tuning choice but receives minimal discussion—what happens with different percentages? More fundamentally, there's no framework for thinking systematically about hypergraph design for MAPF. Should edges capture potential conflicts? Goal proximity? Historical collision patterns? The approach feels somewhat ad-hoc rather than principle-driven.\n\nThe failure analysis is missing. Even in scenarios where HMAGAT performs best, failure rates remain. What are these failure modes? Are they timeouts, deadlocks, or inefficient paths? Understanding when hypergraphs don't help would provide important insight into the method's limitations and scope.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)