On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods

Dear reviewer QaJ5, thank you for your valuable comments. Below are our responses to your concerns.

If there are no regularization terms on the gating variable, why should the gating value decrease if there is still useful information in the historical embeddings?

Motivated by this comment, we have added a regularization term to G-ForgetNet and demonstrated its superb effectiveness for enforcing the Markov property in G-ForgetNet and improving model performance. We refer the reviewer to Section 4.2 and Section 5 to see the details of this new regularization term as well as an analysis of its performance and behavior. However, without this penalty term, we still observe that the gating value in G-ForgetNet decreases. As motivated by the Markov property and empirically shown in ForgetNet, the historical embeddings do not contain useful information, which is why we still observe that the gating value in G-ForgetNet decrease, allthough not to 0 as it does with the added penalty.

The authors do show a plot of the gating variable trajectory as training progresses, but the gating value only decreases slightly and never to 0. Are there any cases where the gating variable decreases to 0?

Without the added loss penalty, the gating value generally will not converge exactly to 0, allthough it does get close for many algorithms. However, when we add the penalty to G-ForgetNet, we see that the gating value does converge to 0. We analyze the behavior of the penalized gate in Section 5 and in Appendix A.2, and we have included an in-depth comparison of G-ForgetNet with and without this penalty in Appendix A.3 in order to address these questions.

Finally, we would like to thank the reviewer for the insightful points they raised

Dear reviewer gWrY,

We apologize for any confusion. To the best of our knowledge, there are not any inherent drawbacks of neural algorithmic reasoning in possessing the Markov property. When the algorithmic reasoning task is Markov, neural algorithmic reasoners are able to learn single-step execution, i.e., learning transitions between subsequent states or $`hints`$. As formalized in [1], intuitively, it is easier for neural networks to learn these simpler computations, and the removal of such Markov property would needlessly increase the complexity of the underlying task.

Additionally, prior works such as [2] have shown that using the $`hints`$ time series significantly increases the performance of neural algorithmic reasoning models compared to directly learning to map from the algorithm input to the final output. They do not analyze this in the context of the Markov property, however, based on the analysis in our work, we can see that the removal of such hints removes the Markov property from the neural algorithmic reasoning task, which explains observed the performance degradation.

[1] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2020.

[2] Beatrice Bevilacqua, Kyriacos Nikiforou, Borja Ibarz, Ioana Bica, Michela Paganini, Charles Blundell, Jovana Mitrovic, and Petar Veličković. Neural algorithmic reasoning with causal regularisation. In International Conference on Machine Learning, pp. 2272–2288. PMLR, 2023.

Dear reviewer gWrY, thank you for your valuable comments. Below are our responses to your concerns.

W1. Although ForgetNet perfectly possesses the Markov property of algorithm execution, the newly proposed G-ForgetNet still utilizes historical embeddings but outperforms ForgetNet. Is there an inherent drawback of neural algorithmic reasoning in possessing the Markov property?

The drawback of ForgetNet is not due to the Markov property, in fact, the Markov property is ForgetNet's biggest strength. The drawback of ForgetNet is the training difficulties that stem from removing the connections between layers. We have tried to clarify this point in Sections 4.1 and 4.2 of our revised manuscript. Additionally, motivated by comments from reviewers, we added a loss penalty to G-ForgetNet which better aligns G-ForgetNet with the Markov property. We demonstrate that, with the new loss penalty, the gate norm goes to 0 during training, i.e., the gate becomes entirely closed. We observe that enforcing the gate to be closed significantly improves the performance of G-ForgetNet, as it now outperforms the baseline on all 30/30 algorithms. As such, we further show the power of aligning neural algorithmic reasoners with the important Markov property. We refer the reviewer to the revised Section 5 to see these new results.

W2. For certain tasks, G-ForgetNet performs worse than ForgetNet, or ForgetNet performs worse than the baseline. Some task-specific explanations regarding this should be discussed

Generally ForgetNet struggles on algorithms where the $`hints`$ time series is very long, such as Jarvis' March, Articulation Points, or Heapsort, where the training time series lengths are 204, 163, and 91, respectively. This aligns with our expectations as it is incredibly difficult for the model to backpropagate signals through 100+ sequentially applied processor layers when the predictions early in the time series are inaccurate. We believe that ForgetNet underperforms on algorithms such as Naive String Matcher or Floyd-Warshall because the update step between consecutive $`hints`$ is non-trivial. E.g. in Floyd-Warshall, each step requires the model to simulate a double-nested for-loop, which is generally difficult to learn, and these difficulties are then compounded by the previously discussed training issues in ForgetNet.

Conversely, ForgetNet performs best on algorithms with very simple update steps between hints such as in DFS.

Dear reviewer fpct, thank you for your valuable comments. Below are our responses to your concerns.

The discussion of the Markov nature of algorithms could use some nuance. If it is the case that these algorithms, when processing entire graphs, therefore having some history in the 'state' are Markov, then the historical information in the hidden features shouldn't help

In our revised manuscript we have clarified our motivations for the G-ForgetNet model. The core motivation for the proposed G-ForgetNet is that, while inclusion of information from previous layers does not inherently align with the desired Markov nature, it can provide helpful support, especially during the early stage of training, where it can mitigate the effects of inaccurate intermediate predictions and facilitate higher quality backpropagation signals. I.e. the connection between layers in G-ForgetNet is beneficial not because the model is making use of historical information about the algorithm, but rather because of the important computational pathways it provides. We refer the reviewer to Section 4.1 and 4.2 for more elaboration. Additionally, we further introduce a loss penalty for G-ForgetNet and show that enforcing the gate to be closed further boosts performance, which aligns with our intuitions about the importance of obeying the Markov property. We hope that this new penalized G-ForgetNet model helps to clarify the story arc.

Q1. In most algorithms ForgetNet beats the baseline (Figure 3). Is there any intuition or hypothesis around which particular algorithms the baseline is better? For example, for Naive String Matcher the baseline looks considerably better. Why might that be?

Generally ForgetNet struggles on algorithms where the $`hints`$ time series is very long, such as Jarvis' March, Articulation Points, or Heapsort, where the training time series lengths are 204, 163, and 91, respectively. This aligns with our expectations as it is incredibly difficult for the model to backpropagate signals through 100+ sequentially applied processor layers when the predictions early in the time series are inaccurate. We believe that ForgetNet underperforms on algorithms such as Naive String Matcher or Floyd-Warshall because the update step between consecutive $`hints`$ is non-trivial. E.g. in Floyd-Warshall, each step requires the model to simulate a double-nested for-loop, which is generally difficult to learn, and these difficulties are then compounded by the previously discussed training issues in ForgetNet.

Q2. I really like the visualization with bars in Figure 1, I think adding G-ForgetNet to that graphic or otherwise including a plot with the G-ForgetNet results would help. Can the authors provide such a visualization?

We have added this visualization as Figure 6 in Appendix A.1.

Dear reviewer PbVk,

We thank you for your insightful comments. We have addressed your comments in the revised manuscript.

The discussion about the motivation could be improved.

Prior works such as [1] have shown the importance of aligning the computational graph of neural networks with the structure of the underlying task. This motivates us to restructure the computational graph of neural algorithmic reasoners to be better aligned with the Markov nature of the algorithms in the CLRS-30 benchmark. In our revised manuscript we have clarified the motivation for our G-ForgetNet model. We refer the reviewer to Sections 4.1 and 4.2 to see our refined motivation for G-ForgetNet, including the mentioned connections with residual links.

It should be clarified that this work is about algorithmic reasoning tasks that can be modeled by finite-state automata. In general, whether the process is Markov or not depends the definition of the state space.

Firstly, thank you for raising an interesting perspective on finite-state automata, which may broaden this direction in the future. Indeed, the algorithms in the CLRS-30 can be modeled by finite automata under a slightly irregular definition of the state space because the graphs used for training and testing are of fixed size. We leave further theoretical analysis of algorithmic reasoning in the context of finite automata or other models of computation to future work.

Even though the Markov observation motivates to remove history information, history information proves to be important for stabilizing training (hence the proposal of G-ForgetNet). This is similar to the effect of residual links, which can be discussed more in the paper.

We appreciate the insightful comments about the similarities with residual links. We have added some discussion on these similarities in Section 4.1.

Fig 4 (b): what are execution steps, and how are the labels acquired? Since there are labels to compute the per-step loss, can we also compare with per-step teacher forcing?

This part of Figure 4 was moved to Appendix B.2 in our updated manuscript in order to make room for the rest of our updates. However, the execution steps in this figure are the time series of $`hints`$ for each intermediate step in the algorithm process. Per your suggestion, we evaluated ForgetNet with 100% teacher forcing. Allthough the losses for ForgetNet with teacher forcing are incredibly low, the model fails to generalize to the test data for most algorithms. The figure with the training losses for ForgetNet trained with teacher forcing on the Floyd-Warshall algorithm can be sound in the Supplementary Material, and the performance for ForgetNet with teacher forcing on each algorithm can be found below. Allthough the overall average performance of ForgetNet with teacher forcing is significantly below the baseline, it outperforms our best model, G-ForgetNet, on several algorithms, including naïve string matcher, where it achieves a remarkable 100% test accuracy. We believe teacher forcing shows significant potential for future works, however further study is outside the scope of our paper.

Fig 5: for better comparison, could you also provide the norm of the residual branch in the baseline?

Yes, per your suggestion, we have included the norm of the residual branch in the baseline in Figure 5 as well as in Figure 7 in Appendix A.2. In order to provide a fair comparison between G-ForgetNet and the baseline, we now report the norm of the gated hidden states instead of the norm of the gate itself.

[1] Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? In International Conference on Learning Representations, 2020.

Dear reviewer VNPs, thank you for your valuable comments. Below are our responses to your concerns.

Why is gating better than the NN more generally learning how to combine historical and current embeddings, as in the baseline?

In response to your comments and those of other reviewers, we have added a regularization term to the loss function which penalizes the magnitude of the gate norm, ensuring that the gate is aligned with the Markov property as desired. However, to answer your original question, the G-ForgetNet model without this penalty performs better than the baseline because, while it still may fit some historical noise, it is less reliant on historical embeddings than the baseline model, and therefore closer aligned with the Markov property. We further analyze your question in Appendix A.3 of our revised manuscript.

Lastly, the TripletGMPNN includes a gating layer in the single-task setup. A discussion on how this differs from the gating in G-ForgetNet should be included.

The gate in Triplet-GMPNN is placed ahead of the decoder and is meant to bias the model towards only updating a subset of the hidden states at each step, while the remaining hidden states are left unchanged. Our gate is placed ahead of the processor and is meant to bias the model towards not including any hidden states at all, which we further enforce using a loss penalty. We have added further clarification about the difference between our gates in Section 5 of the revised manuscript.

Moreover, what are other solutions, possibly not involving learning?

We previously tried to use a manual annealing schedule for the gate in which the gate is initially fully open, and is linearly decayed until the end of training, where it would be entirely closed, thus explicitly enforcing the Markov property. However, we found that this did not significantly improve the performance over the baseline. The results of this experiment for each algorithm are given in the table below.

Results outperforming G-ForgetNet are highlighted in bold