acceptodds
Under review as a conference paper at ICLR 2027

Per-Layer Routing over Heterogeneous Experts for Shortest-Path Neural Algorithmic Reasoning

Abstract

Neural Algorithmic Reasoning (NAR) asks whether a neural processor can carry a classical algorithm beyond its training scale. Shortest-path algorithms differ in how their inner step aggregates and composes path lengths, yet most NAR processors commit to a single aggregation geometry, and an end-to-end selector trained on task loss alone falls short of the best single algebra on four of seven CLRS-30 tasks. We introduce PSAR, a processor that pools three attention algebras (softmax, α-entmax, tropical max-plus) and a triangular multiplicative pair-state update (TMU), and selects one expert per hint step with a hard router trained in stages over frozen, then jointly tuned, experts. Under teacher-forced evaluation on three CLRS-30 shortest-path tasks, no single expert is best on all three. PSAR, trained with the same recipe on each task, matches or exceeds the strongest attention algebra on every task, but falls below standalone TMU on Dijkstra. On Floyd–Warshall, most of the observed gain over attention is already present in the pair-state expert: standalone TMU is 13.0 percentage points above the strongest attention algebra at N=32. On the same task at N=48 and 64, PSAR outperforms a parameter-matched TMU by 7.2 and 8.1 pp, and surpasses its own step schedule retrained as a fixed routing rule by 16.1 and 12.6 pp. However, when PSAR and the parameter-matched TMU are trained and evaluated on their own predictions, the TMU leads on Floyd–Warshall. For shortest-path NAR, these results identify the pair-state update as a primitive worth adding to attention-based processors, and show that the ordering between processors can reverse with the hint contract under which they are trained and compared.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Neural algorithmic reasoning, CLRS-30, Shortest-path algorithms, Mixture of experts, Pair-state representations

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Xb68OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies neural algorithmic reasoning, which aims to train a graph neural network to simulate the execution of a classical algorithm step by step. The well-known benchmark in this area is CLRS-30, which contains 30 classical algorithms, including sorting algorithms and graph algorithms. For each algorithm in the benchmark, CLRS-30 provides intermediate states produced at each iteration of the algorithm (e.g., the current state of the array), called hints, and expects the trained neural network to predict the corresponding hint at each step. The authors observe that the operations between some hints do not match well with those of standard GNNs or graph transformers, but instead match the TMU operation mentioned in the literature; therefore, they propose replacing the node update function in the GNN with TMU. In the paper, the authors propose a mixture-of-experts neural network, where each expert corresponds to a way of updating GNN nodes (including TMU), and at the beginning of each inference step, a router network decides which expert to use for the GNN update at that step. The paper validates the effectiveness of the proposed method through experiments.

Critical strengths

The paper is overall clean and easy to follow. Although some similar ideas have already appeared in Triplet-GMPNN, using the TMU operation to update the GNN in NAR can be regarded as a novel point, and it may provide a GNN operator option for the future development of NAR.

Critical weaknesses

The main concern is the experimental section. The paper does not compare the results of the proposed network architecture with methods from the literature; instead, it compares several methods designed by the authors against one another within their own framework. The main comparison tables in the experimental section do not follow the setting used in prior literature, where at test time each step takes as input the hint predicted by the GNN at the previous step. The authors use ground-truth hints as input. The authors provide results without teacher forcing in the appendix, but the reported performance is far below that of some methods in the literature. Additionally, the paper only tests a few graph algorithm tasks in CLRS, but the proposed framework can also be applied to other types of algorithms in CLRS. These weaknesses make the experiments not that convincing.

Questions for authors

Could you compare the proposed method with existing methods under the same test setting (either both using teacher forcing at test time or both not using teacher forcing)? Such a comparison would help convince that the proposed method indeed has advantages.

3 comments
AuthorsOpenReview ↗

Response to Reviewer Xb68 (1)

Thank you for identifying the missing comparisons with established processors under a common setting. We have added MPNN-max and Triplet-GMPNN-based comparisons under both hint contracts, followed by retraining with reference-form decoders and length masking where applicable.

Response in brief. Within each comparison, the evaluation instances and hint contract are shared, and model-specific training schedules are disclosed. This directly addresses the missing-comparison concern. The results support a scoped conclusion: standalone TMU accounts numerically for most of the original Floyd–Warshall gain over attention, while the additional routing advantage depends on the configuration and comparator. This boundary now appears in the contribution statement. Table numbers refer to the revised PDF; changes are marked in blue.

Both use teacher forcing

Three literature processors replace our processor in the same harness: Relational Attention (Diao & Loynd; Table 35, already in the submission), the CLRS max-aggregation MPNN and Triplet-GMPNN (both new, not tuned; Appendix P). The comparisons share data, evaluation instances, hint contract and decoder design within each harness. PSAR retains its staged training; the baselines use the disclosed single-expert recipe. Four seeds each, on the held-out instances of Table 1. PSAR minus each processor, in pp (95% paired-bootstrap intervals for the two new processors, not corrected for multiplicity; N=32 / 48 / 64, or N=32 / 64 for Relational Attention):

Task− Relational Attention− MPNN-max− Triplet port
Dijkstra+30.4 / +31.7+0.4 [−4.7, +6.2] / −7.0 [−13.6, −0.6] / −17.4 [−23.9, −10.6]−4.5 [−6.9, −2.3] / −7.6 [−10.2, −4.9] / −13.7 [−22.8, −4.9]
Bellman–Ford+0.6 / +0.9+23.4 [+7.3, +45.6] / +18.3 [−0.4, +46.3] / +18.5 [−0.5, +46.2]−2.5 [−5.2, +0.9] / −4.2 [−6.8, −1.7] / −5.1 [−8.7, −1.2]
Floyd–Warshall−3.2 / −4.8−0.6 [−2.2, +1.1] / −0.9 [−3.0, +1.2] / −4.4 [−10.0, +1.1]+11.0 [+8.1, +13.3] / +13.5 [+11.2, +15.3] / +9.2 [+3.1, +14.6]
  • Dijkstra. PSAR is above Relational Attention and below both message-passing processors at N=48 and 64; the latter differences are not statistically resolved with the reference-form decoders below.
  • Bellman–Ford. PSAR is within 1 pp of Relational Attention, above MPNN-max at N=32 (by 1.9 pp with the reference-form decoders below), and below the triplet port at N=48 and 64. At N=48 and 64 the interval against MPNN-max includes zero because one of its four seeds does not train; all four seeds are reported.
  • Floyd–Warshall. PSAR is above the triplet port at every size, not separable from MPNN-max, and below Relational Attention. An MPNN-max widened to approximately PSAR's parameter count is above PSAR at N=48 and 64 (by 2.3 [0.0, 4.5] and 5.8 [0.4, 11.3] pp).

Reference-form decoders. The main harness differs from the reference CLRS implementation in its read-outs and in not masking padded steps (Appendix N), and our triplet port pools the edge representation into the nodes, so it is not a faithful Triplet-GMPNN. We therefore retrained all models with decoders in the reference form (four seeds, 64 new instances per size).

Floyd–Warshall (Appendix Q). PSAR minus each model at N=48 / 64, trained and evaluated with ground-truth hints, with checkpoints selected on autonomous or teacher-forced accuracy:

SelectionTriplet-GMPNNMPNN-maxWider TMU
Autonomous+31.3 [+16.0, +46.4] / +26.5 [+8.4, +43.2]+5.4 [−9.5, +20.1] / +0.1 [−17.5, +17.3]+2.1 [−21.7, +33.5] / +1.0 [−21.9, +25.0]
Teacher-forced+15.7 [+11.9, +18.8] / +26.2 [+18.6, +32.8]+0.4 [−8.0, +9.6] / +6.2 [−9.1, +24.9]−11.4 [−17.9, −4.9] / −4.7 [−12.9, +3.7]

PSAR stays above Triplet-GMPNN and is not separable from MPNN-max under either rule. Against a single wider TMU it is below at N=32 under both rules (−25.8 [−47.3, −8.1] and −9.4 [−13.8, −4.1]) and at N=48 under teacher-forced selection, the rule of the submission. Against a parameter-matched TMU it is below at N=32 under both rules (−28.1 [−47.9, −9.6], −9.8 [−13.4, −5.2]); at N=48 and 64 the intervals include zero.

Dijkstra and Bellman–Ford (Appendix S, with length masking). Every model is above 0.89 at every size. PSAR is not separable from MPNN-max, Triplet-GMPNN or a wider TMU at N=48 and 64 on either task; at N=32 it is above MPNN-max on Bellman–Ford (+1.9 [+1.1, +2.8] pp) and below the wider TMU on Dijkstra (−0.3 [−0.6, −0.1]). On Dijkstra every trained model is below the baseline that copies the last fed hint (1.000 at N ≥ 32).

AuthorsOpenReview ↗

Response to Reviewer Xb68 (2)

Neither uses teacher forcing

The own-prediction retrainings do not establish a general advantage over the tested literature processors.

Submitted models evaluated on their own predictions. Every processor of the submitted paper falls below 0.19 on Dijkstra and Floyd–Warshall and below 0.29 on Bellman–Ford at N ≥ 32 (Appendix N). The two ported processors are above PSAR on Dijkstra and Bellman–Ford (MPNN-max 0.213 and 0.389, the triplet port 0.295 and 0.467, PSAR 0.068 and 0.280 at N=32); on Floyd–Warshall PSAR is above both (0.187 against 0.108 and 0.081). As the reviewer notes, these are far below published results obtained without teacher forcing. These models never saw their own predictions in training, and the main harness differs from the reference CLRS implementation in two disclosed ways (Appendix N): edge-level quantities are decoded without a per-edge term, and padded steps are not masked. The retrainings below use reference-form decoders, mask lengths where trajectories vary (three smaller differences remain and are listed in Appendix S), and train, select and evaluate every model on its own predictions.

Floyd–Warshall retrained (Appendix Q). Accuracy at N=32 / 64 is 0.472 / 0.197 for PSAR, 0.430 / 0.228 for MPNN-max, 0.406 / 0.168 for Triplet-GMPNN and 0.561 / 0.213 for a wider TMU. PSAR is not separable from MPNN-max or Triplet-GMPNN and is below the wider TMU at N=32 and 48 (−9.0 [−16.0, −4.2] and −9.3 [−18.8, −3.8] pp) and a parameter-matched TMU (−8.0 [−14.0, −4.0] and −4.3 [−7.5, −0.8]).

Dijkstra and Bellman–Ford retrained (Appendix S). Accuracy at N=32 / 64:

TaskPSARMPNN-maxTriplet-GMPNNWider TMU
Dijkstra0.795 / 0.5840.944 / 0.9010.947 / 0.8650.829 / 0.594
Bellman–Ford0.885 / 0.7680.929 / 0.8750.944 / 0.9070.873 / 0.624

Both message-passing processors are above PSAR at every size: on Dijkstra by 14.8 [10.9, 18.4] and 31.7 [26.3, 36.6] pp (MPNN-max, N=32 and 64), on Bellman–Ford by 5.9 [4.5, 7.4] and 14.0 [11.7, 16.1] pp (Triplet-GMPNN). PSAR is above the wider TMU on Bellman–Ford at N=48 and 64 (+7.4 [+5.0, +9.7] and +14.4 [+11.0, +17.9]). On neither task is PSAR above all four of its own experts, with or without teacher forcing (computed after the other contrasts).

What the paper claims

The paper compares processors and routing controls under explicitly specified configurations. Standalone TMU accounts numerically for most of the gain over single-step attention on Floyd–Warshall under teacher forcing. The routed pool exceeds a parameter-matched TMU on Floyd–Warshall in the main teacher-forced harness (+7.2 and +8.1 pp at N=48 and 64), and this ordering reverses when both are trained and evaluated on their own predictions (−5.8 and −3.4 pp; §8, Table 4). §9 states that we do not contest the benchmark-wide state of the art on CLRS-30.

The new comparisons bound these claims, as stated in §6, Limitations and Appendices P, Q and S: max-aggregation message passing is either higher than PSAR or not statistically distinguishable from it on Dijkstra and Floyd–Warshall in the main teacher-forced harness, at a fraction of its cost; and the Floyd–Warshall margin over a single pair-state expert is not reproduced with upstream-form edge decoders. PSAR's favourable same-setting comparisons are against Relational Attention on Dijkstra, the triplet processor on Floyd–Warshall under both read-outs, and the unwidened MPNN-max on Bellman–Ford at N=32 under teacher forcing (23.4 pp in the main harness; 1.9 pp in Appendix S). §2 no longer says that Triplet-GMPNN was not run in our harness; the Edge Transformer and FloydNet remain untested.

Scope of tasks

The three tasks share shortest-path semantics but differ in update structure: greedy vertex selection, repeated edge relaxation and pivot-indexed pair updates. Appendix J.1 (Table 23) extends PSAR and the four single experts to seven CLRS-30 tasks under teacher forcing on the checkpoint-selection split, four outside shortest paths. PSAR's largest shortfall to the per-task best single expert is 6.6 pp, against 17.7 to 35.2 pp for any one expert used on all seven; it exceeds every single expert only on Floyd–Warshall and BFS. Appendix R adds their self-rollout (SCC retains ground-truth color). These tests do not establish a routing benefit. The literature processors and routing controls were run on the three shortest-path tasks only.

These additions provide the established-method comparisons requested in your review under both hint contracts. We would appreciate your reassessment of the concern arising from their original absence, and of the empirical support for the contribution within its stated scope.

Thanks for the additional experiments and clarifications. The new comparisons address my concern about the lack of evaluation against established methods under matched settings. However, I still remain concerned about the added value of routing and performance without teacher forcing, so I will maintain my original rating.

Reviewer_vjNTOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces PSAR, per-layer specialised aggregation routing, which combines four different expert operations, consisting of three single-step attentional algebras and one non-attentional expert (TMU). PSAR uses a hard top-1 router at inference time. The main evaluation covers three algorithms from CLRS-30 dataset.

Critical strengths
  1. The paper investigates a sensible architecture design, making use of a mixture of experts using different aggregation techniques for neural algorithmic reasoning.
  2. The paper provides a transparent discussion of the negative results, including the dominance of TMU on some of the tasks.
Critical weaknesses
  1. Primary Evaluation: Ground-truth hints are provided at every step, making the prediction task substantially different from ‘autonomous’ execution. The reported accuracy improvements may primarily reflect how well the processor preserves the available information rather than its ability to perform the desired algorithmic updates.
  2. Poor Empirical Benefits: Most improvements over attention-based processors seem to come from TMU. The ablations do not establish a clear benefit from the more complex routing mechanism, and the results under autonomous execution are less convincing. The main evaluation focuses on only three shortest-path algorithms, limiting the generalizability of the findings.

In general, the evaluation section is hard to read and lacks clarity.

Questions for authors
  1. Could the authors provide stronger evidence that PSAR improves actual algorithmic computation, rather than mainly preserving information provided through ground-truth hints? In particular, does the routing mechanism provide benefits under autonomous execution?
  2. Could the authors provide autonomous evaluation results on the four additional algorithms? It is unclear whether the benefits of PSAR generalize beyond the three shortest-path tasks under this evaluation setting.
3 comments
AuthorsOpenReview ↗

Response to Reviewer vjNT (1)

Thank you for distinguishing preservation of supplied hints from autonomous algorithmic computation. We have added analyses that examine these questions separately.

Response in brief. The new comparisons do not establish a general autonomous benefit from routing. They show that the original teacher-forced margin is concentrated on retained entries, while the tested TMU configuration still outperforms attention on Floyd–Warshall after own-prediction training. We therefore separate the primitive-level result from the narrower routing result. The additional-task experiments are self-rollout diagnostics of teacher-forced checkpoints; SCC retains ground-truth color. The decoder boundary is now explicit in the contribution statement. Table numbers refer to the revised PDF; changes are marked in blue.

Question 1: does routing help under autonomous execution, and do the gains reflect computation or preserved information?

The Floyd–Warshall comparison against a parameter-matched pair-state expert (TMU) is in Table 4 of §8 (the second harness has a reference-form edge read-out, length masking and new instances):

Floyd–Warshall, PSAR − parameter-matched TMU (pp, 95% interval)N=48N=64
Trained and evaluated with ground-truth hints+7.16 [+3.14, +11.07]+8.09 [+5.47, +10.45]
Trained and evaluated on own predictions−5.84 [−8.83, −2.83]−3.44 [−6.17, −0.24]
Second harness, ground-truth hints+7.95 [+1.55, +14.56]+7.15 [+2.09, +13.56]
Second harness, own predictions−5.39 [−7.58, −3.14]−5.68 [−7.60, −3.13]

We retrained the compared models with reference-form edge decoders (Appendix Q). On its own predictions PSAR is below a wider TMU at N=32 and 48 (−9.0 and −9.3 pp) and below a parameter-matched TMU (−8.0 and −4.3 pp; all four intervals exclude zero), and is not separable from a max-aggregation MPNN. On Dijkstra and Bellman–Ford (Appendix S), MPNN-max and Triplet-GMPNN are above PSAR at every size, by 14.8 to 31.7 pp and 4.5 to 14.0 pp at N ≥ 32.

Standalone TMU also has an advantage over the tested attention experts under own-prediction training, selection and evaluation. With the Appendix Q decoders it exceeds Entmax, the strongest tested attention expert on Floyd–Warshall, by 18.0 [14.3, 23.3] pp at N=32 and 11.1 [5.4, 16.9] pp at N=48 (post-hoc 95% paired-bootstrap intervals as in Appendix Q, computed for this response, uncorrected; the N=64 interval includes zero).

Where the teacher-forced margin lies. Appendix N splits every pointer target by whether it differs from the last hint the model was given. A baseline with no processor that copies that hint scores 1.000 on Dijkstra and 0.930 on Floyd–Warshall at N=32, above every trained model (Table 1, last row).

  • On Floyd–Warshall, PSAR's margin over the parameter-matched TMU at N=48 and 64 is +7.5 and +8.4 pp on entries that already equal the last fed hint, and +0.2 and +1.0 pp on the 4 to 5% of entries that the last step changes, with intervals that contain zero (Tables 37 and 38). This locates the teacher-forced margin; it does not identify the cause of the ranking reversal after retraining. Autonomous models still need to preserve intermediate states, but those states are model-generated and may contain errors.
  • Against the max-aggregation MPNN ported into the harness (Appendix P), PSAR is below on the Floyd–Warshall entries that the last step changes, by 10.3, 8.3 and 7.8 pp at N=32, 48, 64 (intervals exclude zero); on the entries that equal the last fed hint the two are not separable.
  • On Dijkstra at N ≥ 32 the output equals the last fed hint on every entry, so output accuracy there measures retention only. On the per-step entries that do change, PSAR is above standalone TMU (+11.7 [+3.9, +19.4] and +11.5 [+5.3, +17.5] pp at N=48 and 64) and more than 30 pp below the ported MPNN.

The split against TMU was chosen after the main results were seen and the paper labels it exploratory.

Without retraining. Evaluated on their own predictions, every processor of the submitted paper falls below 0.19 on Dijkstra and Floyd–Warshall and below 0.29 on Bellman–Ford at N ≥ 32. On Floyd–Warshall PSAR stays above the parameter-matched TMU (+4.2 [+2.2, +6.9] and +2.7 [+1.0, +4.7] pp at N=48 and 64) and the ported MPNN (+7.9 [+2.3, +13.5] and +4.5 [+1.1, +8.0] at N=32 and 48); on Dijkstra and Bellman–Ford it is below both ported processors. These models never saw their own predictions in training, so the answer above rests on the retrainings.

What the teacher-forced numbers support. They order processors under one fixed contract and measure how much of a supplied trace a processor preserves and transforms beyond the training size. These scores alone do not establish autonomous algorithm execution. The abstract's last sentence and §8 state that the ordering between processors can reverse with the hint contract.

AuthorsOpenReview ↗

Response to Reviewer vjNT (2)

Question 2: additional-task rollout diagnostics (SCC partially teacher-forced)

We evaluated the Table 23 checkpoints on the held-out split of Table 1 (four seeds, trained and selected under teacher forcing). BFS, MST-Prim and matrix-chain use predicted hints after initialization; SCC retains ground-truth color at every step. Accuracy at N=32 / 64 (Appendix R gives all sizes and teacher-forced results):

ModelBFSMST-PrimMatrix-chainSCC (gold color)
Softmax0.794 / 0.5040.069 / 0.0350.279 / 0.2070.234 / 0.088
Entmax0.793 / 0.4950.073 / 0.0340.389 / 0.2500.221 / 0.080
Tropical0.894 / 0.6200.056 / 0.0310.499 / 0.4060.168 / 0.076
TMU0.337 / 0.1300.092 / 0.0330.216 / 0.1330.187 / 0.091
PSAR0.535 / 0.2790.058 / 0.0320.323 / 0.2530.115 / 0.054
  • BFS. Under teacher forcing PSAR has the highest point estimate (0.937 at N=32). On its own predictions it is 22 to 36 pp below each attention expert at N=32 and 64 (all intervals exclude zero) and above TMU (+19.8 and +14.9 pp).
  • MST-Prim. Under teacher forcing PSAR has the highest point estimate at N=64 (0.787). On their own predictions all models are at 0.20 to 0.24 at N=16 and below 0.10 from N=32.
  • Matrix-chain order. PSAR's point estimates are below Tropical under both protocols; under self-rollout the contrast is −17.6 [−32.0, +0.3] at N=32 and −15.4 [−26.0, −1.3] at N=64.
  • SCC. All models are below 0.24 at N=32; PSAR is below Softmax and Entmax by 11.9 and 10.6 pp (intervals exclude zero). The categorical hint color has no branch in our training loss, so this evaluation supplies the ground-truth color at every step while all other hints are the model's own.

None of these checkpoints was trained on its own predictions. These rollout diagnostics do not establish a routing benefit, and on BFS the teacher-forced ordering reverses.

Weakness: most of the improvement comes from TMU, and the benefit of routing is unclear

We agree that TMU accounts numerically for most of the observed Floyd–Warshall margin over attention: standalone TMU is 13.0 pp above the strongest attention algebra at N=32, and adding TMU to a routed three-algebra pool adds 13.3 pp [+11.7, +14.7] (Table 18). What routing adds beyond the pair-state expert is bounded in §7 (Table 3; Floyd–Warshall, teacher-forced, PSAR minus each control):

ControlN=48N=64
Parameter-matched single TMU+7.16 [+3.14, +11.07]+8.09 [+5.47, +10.45]
PSAR's step schedule retrained as a fixed rule+16.07 [+11.21, +20.81]+12.58 [+8.16, +16.96]
Static convex mixture of the four experts, no router+3.41 [+1.77, +5.13]−0.24 [−3.38, +2.91]
Router that sees only the step index, 8 seeds+4.05 [+0.79, +7.85]+2.95 [−2.06, +7.89]

The routed pool is above a widened single expert and above a retrained fixed schedule. Against a mixture with no router and against a step-only router the margin is small and not separable at N=64. On Dijkstra the router selects TMU on 96% of steps and standalone TMU stays above PSAR; on Bellman–Ford PSAR is not separable from Softmax. These results establish an advantage over particular controls in the main teacher-forced configuration.

Two new results narrow this further. An MPNN-max widened to approximately PSAR's parameter count is above PSAR on Floyd–Warshall at N=48 and 64 (by 2.3 [0.0, 4.5] and 5.8 [0.4, 11.3] pp; Appendix P). With the upstream-form edge decoders of Appendix Q the first row of the table is not reproduced: PSAR is below a wider TMU and a parameter-matched TMU at N=32 under either checkpoint-selection rule, below the wider TMU at N=48 under the rule of the submission (−11.4 [−17.9, −4.9] pp), and otherwise not separable.

Weakness: only three shortest-path algorithms

The three tasks share shortest-path semantics but differ in update structure: greedy vertex selection, repeated edge relaxation and pivot-indexed pair updates. On the seven-task panel (Table 23, teacher-forced, checkpoint-selection split) PSAR's largest shortfall to the per-task best single expert is 6.6 pp, against 17.7 to 35.2 pp for any one expert used on all seven; it exceeds every single expert only on Floyd–Warshall and BFS. The routing controls cover the three shortest-path tasks only.

Weakness: the evaluation section is hard to read

The revision defines the six controls in the introduction, points from §5 to the seven-task panel and additional-task rollout diagnostics, and adds a table to §6 placing parameters, latency and training cost beside accuracy, with a paragraph stating the comparison scope. The evaluation contract and copy baseline are stated in §5 before the main table. We retained the section structure to make the additions easy to locate.

The revision separates the evidence for TMU from the evidence for routing. We would appreciate your reassessment of the evaluation's clarity and support for these scoped claims.

Thank you for your response. However, my original concerns still remain. The new results show that most of the teacher-forced improvement on Floyd–Warshall is concentrated on entries already present in the supplied hints. Also, PSAR does not consistently outperform simpler alternatives under autonomous execution and the additional-task experiments do not demonstrate a clear benefit from routing. The readability of the evaluation section remains a challenge, with overloaded sentences and dense numerical results within the prose.

Given all this, I maintain my original recommendation of Weak Reject.

Reviewer_oMC2OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes per-layer specialized aggregation routing (PSAR) to dynamically route aggregation functions used in processors for neural algorithmic reasoning (NAR). The proposed method routes between four experts (softmax, \alpha–entmax, tropical max-plus, and triangular multiplicative pair-state update (TMU)). The training process contains three stages that freeze the rest and train the router, encoder and decoder, and joint training, respectively. Evaluation is done on three shortest–path algorithms from the CLRS benchmark. Results show that no single attention function works for all three algorithms, while PSAR performs on par with or exceeds the single expert.

Critical strengths
  1. The question studied in this paper – NAR architectures mostly use a single aggregation function – is a valid problem in NAR.
  2. The proposed mixture-of-experts and routing (PSAR) is interesting. The routing and training stages are adapted to NAR, such as its encoder-processor-decoder design.
  3. In the evaluation, PSAR demonstrates effectiveness over single-attention algebra baselines, as well as fixed routing on three shortest-path algorithms from CLRS.
Critical weaknesses
  1. [Major] The paper focuses on improving the attention algebra in NAR models. However, most NAR models use max-aggregation functions rather than attention aggregation and already achieve near-perfect accuracy on shortest-path algorithms (such as Bellman-Ford). Therefore, the motivation for having a more complicated routing system for attention-based NAR models is unclear.
  2. [Major] The training (3-stage training) and inference costs for having a mixture-of-experts and routing system are significantly higher than single-algebra baselines. Different attention algebras also come with different computational costs. Such costs are not discussed or compared in the evaluation.
  3. [Medium] As also mentioned in Limitations, only three shortest-path algorithms from CLRS are tested in the paper, limiting the scope and applicability of the proposed method. IMO, the proposed method is not inherently restricted to these algorithms; therefore, a broader evaluation scope would help justify the effectiveness of the proposal.
  4. [Medium] More ablations can help justify why the three training stages or four loss terms are needed in the design. Current experiments mainly compare the attention algebra and PSAR.
  5. [Minor] The generalization of trained models is only up to a graph size of 64 (trained on 16-node), which is not a strong test of generalization.
  6. [Minor] The overall writing of the paper can be improved. Some sentences are hard to understand, and some terms are not clearly explained (e.g., lines 71-73: “a homogeneous pool, constant, step-only and retrained fixed-schedule policies, a routing-free mixture and a parameter-matched specialist”).
Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer oMC2 (1)

Thank you for highlighting the need to position PSAR against strong message-passing processors and to account for its computational cost. We have added these comparisons, including widened MPNN-max controls, and placed cost alongside accuracy in the main text.

Response in brief. The new results distinguish the primitive-level finding from the routing result. With the Appendix Q decoders and own-prediction training, selection and evaluation, standalone TMU exceeds the strongest tested attention expert on Floyd–Warshall by 18.0 and 11.1 pp at N=32 and 48. The additional routing gains are conditional: the main teacher-forced comparisons are positive against specific controls, while the decoder boundary is now explicit in the contribution statement. Below we address motivation, cost, scope and ablations. Table numbers refer to the revised PDF; changes are marked in blue.

Major 1: motivation, given max-aggregation processors

We ported the CLRS max-aggregation MPNN and Triplet-GMPNN and trained them with the single-expert recipe (four seeds, not tuned; Appendix P). Teacher-forced accuracy on the held-out split of Table 1 at N=32 / 48 / 64:

TaskPSARMPNN-maxWidened MPNN-maxTriplet (node-pooled port)
Floyd–Warshall0.387 / 0.284 / 0.1920.393 / 0.293 / 0.2370.399 / 0.307 / 0.2500.277 / 0.149 / 0.100
Dijkstra0.924 / 0.813 / 0.6420.921 / 0.882 / 0.8160.972 / 0.955 / 0.9090.969 / 0.889 / 0.779
Bellman–Ford0.902 / 0.890 / 0.8410.668 / 0.706 / 0.6560.738 / 0.814 / 0.7560.927 / 0.931 / 0.892

PSAR minus the other model (pp, 95% paired intervals, uncorrected). The widened MPNN-max approximately matches PSAR's parameter count on Floyd–Warshall; that width is retained on the other tasks.

  • Floyd–Warshall. Not separable from MPNN-max (−0.6 [−2.2, +1.1], −0.9 [−3.0, +1.2], −4.4 [−10.0, +1.1]); below the widened MPNN-max at N=48 and 64 (−2.3 [−4.5, −0.0], −5.8 [−11.3, −0.4]); above the triplet port at every size (+11.0, +13.5, +9.2; intervals exclude zero).
  • Dijkstra. Both ported processors are above PSAR at N=48 and 64 (against MPNN-max: −7.0 [−13.6, −0.6] and −17.4 [−23.9, −10.6]); the widened MPNN-max is above it from N=32 (−4.7, −14.2, −26.7; intervals exclude zero).
  • Bellman–Ford. Above MPNN-max at N=32 (+23.4 [+7.3, +45.6]); at N=48 and 64 the point estimates are +18.3 and +18.5 with intervals that include zero, because one of four MPNN-max seeds does not train (all four are reported). Against the widened MPNN-max the intervals include zero at every size (+16.4, +7.6, +8.5; N=32 seeds: 0.923, 0.924, 0.715, 0.389 against PSAR's 0.958, 0.897, 0.894, 0.861). The triplet port is above PSAR by 4.2 and 5.1 pp at N=48 and 64 (intervals exclude zero).

Reference-form decoders (Appendix S). We retrained all models on Dijkstra and Bellman–Ford with reference-form node-pointer decoders and per-sample length masking. With ground-truth hints every model is above 0.89 at every size, and PSAR is not separable from MPNN-max or Triplet-GMPNN at N=48 and 64 (against MPNN-max: +1.3 and +2.2 pp on Dijkstra, +1.8 and +2.3 on Bellman–Ford; the +23.4 at N=32 becomes +1.9 [+1.1, +2.8]). With own-prediction training and evaluation, MPNN-max is above PSAR by 14.8, 28.0 and 31.7 pp on Dijkstra and by 4.5, 8.9 and 10.7 pp on Bellman–Ford at N=32, 48, 64 (all intervals exclude zero).

Motivation clarified by the new comparisons. With the Appendix Q decoders and own-prediction training, selection and evaluation, standalone TMU exceeds Entmax, the strongest tested attention expert on Floyd–Warshall, by 18.0 [14.3, 23.3] pp at N=32 and 11.1 [5.4, 16.9] pp at N=48 (means in Table 49; post-hoc 95% paired-bootstrap intervals as in Appendix Q, computed for this response, uncorrected; the N=64 interval includes zero). This supports the tested TMU configuration beyond teacher forcing; it does not isolate capacity or establish a routing benefit. Two comparisons with the ported processors favour PSAR, each with a limit:

  • Floyd–Warshall against Triplet-GMPNN. The table's port pools the triplet edge representation into the nodes. With upstream-form edge decoders that receive it (Appendix Q), PSAR is above Triplet-GMPNN under ground-truth hints at N=48 and 64 (+15.7 [+11.9, +18.8] and +26.2 [+18.6, +32.8] under the submission's checkpoint selection); there it is not separable from MPNN-max and is below a wider TMU at N=32 and 48.
  • Bellman–Ford against MPNN-max at N=32 in the main harness (not against the widened one); +1.9 pp in Appendix S, and reversed on own predictions.
AuthorsOpenReview ↗

Response to Reviewer oMC2 (2)

Major 2: training and inference cost

The revision moves the cost comparison from Appendix G to §6. Parameters count the processor; latency is per step, batch 8, one A100. Training is GPU-h per task-and-seed (the two ported processors used a different GPU model); accuracy is teacher-forced on the held-out split.

SoftmaxEntmaxTMUPSARMPNN-maxTriplet port
Processor parameters0.22M0.22M0.34M1.24M0.34M0.53M
Latency, N=32 / 64 (ms)0.55 / 0.5323.47 / 24.141.05 / 2.6731.08 / 34.180.47 / 1.100.87 / 1.98
Training (GPU-h per cell)0.140.580.18≈1.70.050.06
Floyd–Warshall, N=32 / 640.203 / 0.0680.238 / 0.1220.368 / 0.1040.387 / 0.1920.393 / 0.2370.277 / 0.100
Dijkstra, N=640.3840.5600.7410.6420.8160.779
Bellman–Ford, N=640.7710.7510.7290.8410.6560.892
  • PSAR executes all four experts at every step and keeps the selected output, so hard routing saves no computation in the submitted implementation. Training costs 3 to 12 times one single-algebra baseline (Table 11).
  • Cost differs by algebra. Entmax bisection takes about 23 ms, roughly three quarters of PSAR's latency. A pool retrained without Entmax (new table in Appendix G) runs at 3.2–5.2 ms per step against 28–31 ms, and is 5.9 to 11.6 pp lower on Dijkstra and Floyd–Warshall at N=48 and 64 (intervals exclude zero, against a retrained four-expert pool); on Bellman–Ford the intervals include zero.
  • Executing only the selected expert. We implemented an inference path that computes the route first and runs each expert only on the graphs that selected it (new table in Appendix G). Per-step latency falls from 25.5–28.2 ms to 3.7–5.4 ms on Dijkstra, 5.1–9.6 ms on Bellman–Ford and 13.2–14.0 ms on Floyd–Warshall, and per-instance accuracy is identical to full execution in 35 of 36 (task, seed, size) cells. All paper accuracies use full execution. PSAR remains roughly 5 to 30 times slower per step than MPNN-max.
  • Accuracy obtained for this cost. Against standalone TMU at N=32, PSAR is +1.9 pp on Floyd–Warshall and 0.902 against 0.765 on Bellman–Ford, and it is below TMU on Dijkstra at every N (main harness). Against a TMU widened to PSAR's parameter count it is +7.2 and +8.1 pp on Floyd–Warshall at N=48 and 64 (Table 3). Against MPNN-max it gives no established accuracy advantage on Floyd–Warshall or Dijkstra in the main teacher-forced comparisons, at roughly 30 to 65 times its per-step latency under full execution.

Medium: evaluation scope

The three tasks share shortest-path semantics with greedy selection, edge relaxation and pivot-indexed updates. Appendix J.1 (Table 23) extends PSAR and the four single experts to seven CLRS-30 tasks, four outside shortest paths (BFS, MST-Prim, matrix-chain order, SCC), teacher-forced at N=32 on the checkpoint-selection split. PSAR's largest shortfall to the per-task best single expert is 6.6 pp, against 17.7 to 35.2 pp for any one expert used on all seven; it exceeds every single expert only on Floyd–Warshall and BFS. Appendix R adds self-rollout of these checkpoints (SCC retains ground-truth color). These tests do not establish a routing benefit, and §7 routing controls cover only the three shortest-path tasks.

Medium: ablations for the training stages and loss terms

  • Loss terms (Table 17, 36 runs). With all routing-supervision losses off, accuracy changes by 0.2 to 0.4 pp on the three tasks, inside the seed standard deviation (N=32, selection split). We observed no stable benefit from these losses.
  • Pool composition (Table 18). Adding TMU to the three-algebra pool changes accuracy by +8.0 [−2.3, +19.2], +3.1 [+0.6, +5.7] and +13.3 [+11.7, +14.7] pp on Dijkstra, Bellman–Ford and Floyd–Warshall. For the KL term all intervals include zero.
  • Stages. We did not ablate individual stages, so stage necessity is not established. The §7 StepOnly and SoftMix controls keep the expert pool and three-stage recipe, so they assess routing choices within that recipe. The closest end-to-end selector comparison (Table 20) changes pool, routing granularity, size and schedule at once.
  • Other ablations. Initialisation of the shared encoder and decoder (Table 28), hard against soft routing at inference (Table 22), and a pool of four TMU copies (Table 21), which is 3.9 pp below PSAR on Floyd–Warshall and 20.7 pp below it on Bellman–Ford.

Minor points

Graph size. We train at N=16 and test at N=32, 48 and 64; N=64 is the canonical CLRS-30 test size. We measured latency at N=128 (41.5 ms per PSAR step), but no accuracy beyond N=64.

Lines 71–73. The revision defines all six controls in the introduction (in blue).

The revision makes the measured benefits and costs visible together. We would appreciate your reassessment of the motivation and empirical support in light of the autonomous TMU comparison and the routing controls, with their scope stated explicitly.

[W1] Thanks for the additional experiments. From the table, MPNN-max performs better than PSAR (other than Bellman-Ford, which is a surprise because CLRS Benchmark reports "92.01% ± 0.28 (Table 2)" with MPNN-max). While I understand that PSAR has favorability on Floyd-Warshall (over Triplet-MPNN) and Bellman-Ford (over MPNN-max), it still does not strongly support its routing and MoE design, which is significantly more costly.

[W2] The computational table is helpful, thank you. As shown, PSAR is significantly more expensive, with limited improvement over other baselines (even with TMU, one of the experts used).

[W3] Thanks for pointing out the experiments on other algorithms. Given that the routing benefit is not significant for the other algorithms, this does not support the motivation for the proposed method.

[W4] Thanks for the additional ablations. These address my concern and help make the paper more rigorous.

[W5] Graph size 64 is still considered relatively small for a generalization test.

[W6] Thanks for revising the 6 controls. However, the overall writing of the paper can be made more human-readable.

Given that the motivation and effectiveness of the proposed method are not convincing enough yet, I am leaning towards keeping my original rating. I thank the authors for the detailed rebuttals.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We thank the reviewers. The revised PDF marks every change in blue, and table numbers refer to it. No submitted result is altered.

Where PSAR is ahead. Teacher-forced unless stated; intervals are in the responses.

  • Over single-step attention. Standalone TMU is 13.0 pp above the strongest attention algebra on Floyd–Warshall at N=32; PSAR is 7.0, 13.1 and 8.2 pp above it on Dijkstra at N=32, 48, 64. This holds beyond teacher forcing: on own predictions with the Appendix Q decoders, TMU is 18.0 and 11.1 pp above the strongest attention expert at N=32 and 48.
  • Over a single pair-state expert of the same size. +7.2 and +8.1 pp on Floyd–Warshall at N=48 and 64 (Table 3), reproduced with a reference-form edge read-out (+8.0 and +7.2, Table 4) and not with the decoders of Appendix Q.
  • Over its own controls. On Floyd–Warshall at N=48 and 64, +16.1 and +12.6 pp over its learned schedule retrained as a fixed rule; a pool of four TMU copies is 3.9 pp below PSAR on Floyd–Warshall and 20.7 pp below on Bellman–Ford.
  • Over existing processors. Above Relational Attention on Dijkstra (+30.4 and +31.7 pp at N=32, 64); above the triplet processor on Floyd–Warshall under both read-outs (+9.2 to +13.5 pp in the main harness, +15.7 to +31.3 at N=48 and 64 in Appendix Q, where a single wider TMU is not below PSAR); above the unwidened MPNN-max on Bellman–Ford at N=32 (+23.4 pp in the main harness, +1.9 in Appendix S).
  • Across seven tasks. PSAR's largest shortfall to the per-task best of its four experts is 6.6 pp, against 17.7 to 35.2 pp for any one expert used on all seven (N=32, checkpoint-selection split).
  • On its own predictions. Above a wider TMU on Bellman–Ford at N=48 and 64 (+7.4 and +14.4 pp, Appendix S).

The first two items are the paper's main claims: the new experiments support the first beyond teacher forcing and limit the second to the main-harness read-outs. No task-level overall-accuracy comparison establishes a statistically supported advantage over the tested max-aggregation processors under own-prediction training.

New experiments.

  • Literature processors in the same harness (Appendix P, §6). A max-aggregation MPNN and a node-pooled port of Triplet-GMPNN, trained with the recipe of our single experts and not tuned, on Dijkstra, Bellman–Ford and Floyd–Warshall. Under teacher forcing the MPNN is not separable from PSAR on Floyd–Warshall, is above it on Dijkstra at N=48 and 64, and widened to PSAR's size is above it on Floyd–Warshall at those sizes and on Dijkstra from N=32. PSAR is above the triplet port on Floyd–Warshall at every size and above the MPNN on Bellman–Ford at N=32. In the harness of Appendix S the Dijkstra and Bellman–Ford differences shrink to at most 2.3 pp.
  • Floyd–Warshall with upstream-form edge decoders (Appendix Q). All models retrained under both hint contracts with reference-form edge decoders. PSAR is above Triplet-GMPNN under ground-truth hints and not separable from the MPNN. Against a wider TMU under ground-truth hints it is below at N=32 under both selection rules, and at N=48 it is below under teacher-forced selection and not separable under autonomous selection; on its own predictions it is below the wider TMU at N=32 and 48.
  • Self-rollout of the teacher-forced checkpoints on the four additional tasks (Appendix R; SCC keeps one ground-truth hint). No benefit from routing; on BFS the teacher-forced ordering reverses.
  • Dijkstra and Bellman–Ford with reference-form node-pointer decoders and length masking (Appendix S). Under ground-truth hints every model is above 0.89 and PSAR is not separable from the MPNN, Triplet-GMPNN or a wider TMU at N=48 and 64. On their own predictions both message-passing processors are above PSAR at every size, by up to 32 pp on Dijkstra and 14 pp on Bellman–Ford.
  • A parameter-matched TMU with the decoders of Appendix Q. PSAR is below it at N=32 under both contracts and at N=48 on its own predictions; at N=48 and 64 under ground-truth hints the intervals include zero.
  • A pool without Entmax (new table in Appendix G). Six to nine times faster per step under full execution, and 6 to 12 pp lower on Dijkstra and Floyd–Warshall at N=48 and 64.

Main text. §6 gains a cost table and a paragraph stating that the gains are over single-step attention; the introduction defines the six controls; §2 and Limitations report the new comparisons.

Corrections. The parameter count of the Tropical block (0.30M, Table 10) includes 74,112 parameters of two projections whose outputs its forward pass does not use, so 0.22M affect its output. The three adjacency features of the router input (Appendix F.3, item iv) are the same number for any graph and reduce to a constant after normalisation. The caption of Table 35 said "OOD-dev"; its numbers are from the shared held-out split. §4 called the decoders CLRS-native; they differ from the reference as §5 states. None of these changes a reported accuracy.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.