acceptodds
Withdrawn from ICLR 2027

Do the Same Hints Matter Across Input Sizes? Intervening on Semantic Intermediate States in Neural Algorithmic Reasoning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Neural algorithmic reasoners often generalize poorly to inputs larger than those seen during training. Although CLRS models are supervised with intermediate algorithmic states (HINTs), it remains unclear whether these states retain the same functional role when input size increases. Unlike opaque latent activations, CLRS HINTs correspond to named algorithmic variables with exact ground-truth trajectories, allowing their role in recurrent execution to be tested directly through intervention. We study this question across 28 CLRS algorithms and two recurrent processors at N=16 and N=64. We separately test the effect of restoring an individual HINT to its ground-truth trajectory, disrupting its input-specific semantic value through valid semantic resampling, and changing the surrounding HINT context in which the same HINT acts. Both restoration and semantic dependence retain cross-size structure, yet at N=64 their HINT-level rankings are nearly unrelated: execution can remain sensitive to a HINT's semantic content even when correcting that HINT in isolation is not beneficial. Native HINT prediction error is insufficient to explain this dissociation. Nevertheless, the explicit HINT interface remains collectively consequential: restoring all HINT trajectories improves N=64 task accuracy by 15.96 percentage points. Surrounding-context interventions further show that the effect of correcting an individual HINT changes more between the two surrounding HINT states at the larger input size. These results indicate that size extrapolation does not simply eliminate dependence on semantic intermediate states; instead, semantic dependence and isolated repairability remain distinct, while individual correction effects vary more across surrounding HINT states at N=64.

Primary area:
interpretability and explainable AI
Keywords:
neural algorithmic reasoning, out-of-distribution generalization, size extrapolation, causal intervention, intermediate representations, interpretability, CLRS

Reviews

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

This paper focuses on the field of neural algorithmic reasoning (NAR) and investigates the role of a certain hidden state in NAR. Specifically, NAR refers to using a neural network to simulate, step by step, the iterative execution of a classical algorithm. Each iteration of the classical algorithm produces a corresponding intermediate state (for example, the state of the array after each round of insertion sort). These intermediate states are called hints in NAR, and they are also what the neural network is expected to output at each step. This paper studies how the correctness of these hints affects the final network output. The authors design multiple experiments to examine the impact of intervening on hints on algorithmic reasoning capability, for example, altering the hint at a certain step (to the ground truth or to a deliberately incorrect value), and analyze the resulting changes in algorithmic reasoning accuracy to draw conclusions.

Critical strengths

Studying the role of hints in NAR is an interesting topic. It is analogous to research on chain-of-thought reasoning in LLMs. This line of work can help us better understand how the neural network operates in NAR and provide observations that can inform further improvements in NAR training.

Critical weaknesses
  • One weakness is that the paper is very difficult to read, starting from the abstract, and the overall structure is also weird. For example, in the second paragraph of the abstract, some details, such as the value of N, are unnecessary, and the sentences in Lines 21–24 are very difficult to read and are not readable. Many undefined terms appear that should not be in the abstract. The motivation at the beginning of the Introduction is relatively clear, but the later part introducing the authors' own work is too detailed, making it hard to grasp the contributions at once. Moreover, many notations, such as ρ\rho, are used without formal definition. Sections 3–6 correspond to different experiments, but there is a lack of a high-level picture, and there is no concluding discussion at the end.

  • Another weakness is that although the paper conducts many experiments on intervening in hints, it does not seem to yield many unexpected conclusions. Basically, these observations align with normal expectations, which makes the value of the experiments seem less important. The paper also does not further discuss how these experimental phenomena and observations would affect NAR in the future.

Questions for authors

None

Reviewer_qqMHOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies how the roles of supervised intermediate algorithmic states (HINTs) change under size extrapolation. The authors evaluate 28 CLRS algorithms with two processors and three training seeds at input sizes of 16 and 64. They measure isolated restoration effects by replacing individual HINT trajectories with ground truth, and semantic-resampling effects by replacing them with valid values from other examples. They also examine how restoration effects change with the surrounding HINT states. Both measures show positive cross-size rank correspondence, but their within-size rank association is close to zero at N = 64. Restoring all HINTs raises task accuracy at N = 64 by 15.96 percentage points, while individual restoration effects differ more between the two surrounding contexts at the larger size. The authors conclude that semantic dependence and isolated repairability are distinct properties.

Critical strengths

1. A useful distinction between semantic dependence and isolated repairability. A HINT can carry information that the model uses even when correcting it in isolation does not improve accuracy. The paper makes this distinction explicit and measures isolated repairability, semantic dependence, and sensitivity to surrounding HINT states through separate interventions. Since the algorithmic variables have exact ground truth, these interventions have a clear interpretation. This gives a useful basis for understanding why different measures of a HINT's role can disagree.

2. Evidence that correct HINT trajectories remain useful under size extrapolation. Across the evaluated algorithms and processors, restoring all HINT trajectories raises aggregate accuracy at N = 64 by 15.96 percentage points, with a 95% confidence interval of [11.14, 21.13]. The trained models can therefore still benefit substantially from correct intermediate states at the larger input size. Together with the individual-HINT results, this supports the distinction between collective usefulness and isolated repairability.

Critical weaknesses

1. Limited model coverage. The evaluation uses only PGN and Triplet-GMPNN on CLRS. Although the paper acknowledges this scope, it remains unclear whether the same patterns hold for other architectures or training regimes. This limits how broadly the findings can be interpreted beyond the evaluated models.

2. Inconsistencies between figures and reported statistics. Figure 1 shows 27 algorithms, whereas the text reports 25 with valid correlations. Figure 2 (left) shows 25 algorithms, compared with 20 in the text and Table 6. Some correlations listed as undefined in Table 6 also appear as numerical values in the figures. It is unclear whether these discrepancies affect only the plots or also the aggregate estimates and confidence intervals. This makes it difficult to verify which results support the main claims.

Questions for authors
  1. Which eligible algorithm sets were used to calculate the headline estimates and confidence intervals in Figures 1 and 2? Were any correlations listed as undefined in Table 6 included as numerical values in those calculations, or are the discrepancies limited to the figures?

  2. The maximum number of donor candidates falls from 31 at N = 16 to 7 at N = 64. Have the main semantic-resampling findings been checked with donor availability matched across input sizes? If not, how do the shared-HINT and distance controls separate input-size effects from changes in the replacement distribution?

  3. How stable is the reported prevalence of R<0,D>0R < 0, D > 0 cases when uncertainty in individual HINT effects is taken into account? Does the pattern persist under paired resampling or thresholds that exclude near-zero effects? The algorithm-level confidence intervals do not establish how reliably the signs of individual effects are estimated.

Reviewer_yKy7OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies how GNNs trained to imitate execution of classical algorithms generalize across sizes. Specifically, it analyses the functional role of the hints, intermediate states of such execution, which model was trained to predict to align their internal computations with the original algorithm. To study this, authors consider multiple patching experiments, replacing predicted intermediate states with ground-truth hints, valid hints from other samples, or predicted hints while all other hints being replaced with ground-truth.

Critical strengths

None

Critical weaknesses

The paper is very difficult to follow. Despite being very familiar with the area, I couldn't understand the paper's contribution from the abstract.

While I believe that hints give us a great entry point for analyzing the internals of NARs, I don't think that the current revision provides any valuable insights (or fails to communicate them).

Questions for authors

None

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

Related papers

Discussion (0)

Sign in to comment.