Fitting Every Hint Is Not Enough: Premature Floods in Recurrent Algorithmic Reasoners

Amin Najafgholizadeh; Mohsen Afsharchi

cs.LGOct 10, 2026

Fitting Every Hint Is Not Enough: Premature Floods in Recurrent Algorithmic Reasoners

Authors: Amin Najafgholizadeh, Mohsen Afsharchi

Organizations: University of Zanjan

Abstract

Recurrent algorithmic reasoners are trained with per-step hints on small graphs and run for many more steps on large ones. On breadth-first search in SALSA-CLRS, we find that a reasoner can reproduce every training hint and still fail on deep graphs: after some exact steps, it declares nodes reached before the search gets there. We call this a premature flood and trace two routes to it. In our GRU processor with a degree input, the flood is carried in the hidden state and set off when that input is in the tail of the training distribution. Setting the input higher at inference brings the flood sooner, and none of the six flooding models counts steps. Without the input, summing the neighbors' states instead of averaging them also breaks the processor. In the benchmark's own GIN and PGN, trained with its code, some seeds instead flood from a fixed step, on sparse and dense graphs alike. Clamping the degree input or adding 200 dense training graphs removes every failure of the GRU processor. Detaching the state between steps avoids the flood in that processor (0 of 23 seeds, against 6 under full backpropagation) but not with sums or a residual update, and two published remedies leave floods. None of the benchmark's test sets is both deep and dense, but its deepest one shows the second route: on its Delaunay graphs at 1,600 nodes, one GIN seed floods from step 18. We therefore recommend auditing the range of every input and aggregate, which catches the first route, and testing on deep graphs, which catches both.

Figures & tables

Figure 1: One deep dense test graph (a blob of 64 cliques, 1,024 nodes). For every true BFS distance, each panel shows the share of the nodes at that distance declared reached by step $t$ . The correct search fills the region below the dashed diagonal. (a) A reasoner trained with $K{=}1$ is exact. (b) The same seed trained with BPTT is exact until step 16, when it first declares nodes reached before the search arrives, and declares every node by step 17. (c) The weights of (b), with the degree input clamped to 1.0 at inference, are exact again. The model and the graph were chosen by a rule fixed in advance (Appendix C ).

	seeds perfect		node accuracy
rule	blob	maze	ER 800	deg. 17
BPTT	17/23	23/23	0.581	0.413
truncated, $K{=}2$	16/23	23/23	0.587	0.425
BPTT, progressive loss	18/23	23/23	0.615	0.468
BPTT, random $h_{0}$	22/23	23/23	0.538	0.346
$K{=}1$	23/23	23/23	0.771	0.722

Table 1: Seeds (of 23) at graph accuracy 1 at both deep blob cells (blob) and at maze16 and maze32 (maze), and mean node accuracy on ER 800 and degree-17 ER, for each training choice under the pool. Progressive loss and random initial states

h_{0}

are the literature’s remedies added to BPTT (§ 4.7 ); stateless is

K{=}1

without a carried state; residual replaces the GRU cell; sum replaces the two neighborhood means. The ER columns use a second sample of 20 graphs per cell, drawn separately from those of Table 3 .

Figure 2: The drift probe on blob16x64. (a) Median onset of the flood with the degree input set to one value

v

at every node. The panel shows the six failing BPTT models, three healthy BPTT models (one does not flood up to 3.0) and three

K{=}1

models. The dash-dotted line is the training pool’s 99th percentile. (b) The switch: delay of the flood, relative to its onset

t^{*}

under the true input, when the first

k

steps run under a typical input (

v{=}1

), for the six failing models. A drifting state is delayed by

k

(dashed line); a counting state is not delayed until

k

reaches

t^{*}

(dotted line, drawn for seed 13).

Figure 3: The readout of untouched nodes (true distance greater than the step) on blob16x64, with the true reach mask fed in so that no declaration enters the input, under the degree input set to

v

at every node. (a) The flooding BPTT model of seed 13, which first floods at

v{=}1.6

; dots mark the flood onsets of the model’s own rollouts at each input. (b) The

K{=}1

model of the same seed.

Appendix figures & tables30 assets

Supplementary material from the paper’s appendix.

Appendix

	lowest-index rule		all reached at 1
test set	node	graph	node	graph
ER 16 (A)	0.327	0.000	0.613	0.025
ER 80 (A)	0.285	0.000	0.380	0.000
ER 160 (A)	0.249	0.000	0.311	0.000
ER 800 (A)	0.240	0.000	0.257	0.000
Delaunay 16 (A)	0.257	0.000	0.523	0.025

Appendix

Table 2: Model-free reference points, node/graph accuracy. (A): the benchmark sample; (B): the deep sample (Appendix A ). A perfect reach mask scores 1/1 everywhere and is omitted. n/a: the all-reached rule was not scored on the benchmark sample’s degree-controlled cells.

test set	ecc	deg	BPTT	K $=$ 1	paired $\Delta$	sign	BPTT	K $=$ 1	BPTT	K $=$ 1	sign
			node accuracy on $\pi$				graph accuracy		exact-timing radius (hops)
ER 16	2.6	6.4	1.000	1.000	+0.000	0+/0 $-$ /23=	1.000	1.000	4	4	0+/0 $-$ /23=
ER 80	3.5	9.4	0.998	0.999	+0.000	3+/2 $-$ /18=	0.991	0.992	7	7	0+/0 $-$ /23=
ER 160	3.6	11.6	0.972	0.979	+0.007	18+/3 $-$ /2=	0.867	0.914	4.74	4.61	1+/2 $-$ /20=
ER 800	4.1	15.1	0.651	0.802	+0.151	19+/3 $-$ /1=	0.378	0.567	1.43	2.91	12+/0 $-$ /11=
Delaunay 16	3.3	5.7	1.000	1.000	+0.000	0+/0 $-$ /23=	1.000	1.000	4	4	0+/0 $-$ /23=

Appendix

Table 3: Head-to-head over 23 paired seeds on the benchmark sample: our draw of the benchmark’s ER and Delaunay test cells, made with its sampler and configuration, and the degree-controlled ER family. Node accuracy, graph accuracy and the exact-timing radius are means over seeds. “Sign” counts seeds where

K{=}1

exceeds, trails and ties BPTT. At degree 33 both rules are near the model-free floor; at degree 25 BPTT is near it and

K{=}1

above it (Appendix A ). Tables 1 and 16 use a second sample of the ER 800 and degree-17 cells.

test set	$n$	graphs	ecc.	deg.	$L$
ER 16	16	40	2.6	6.4	3.6
ER 80	80	40	3.5	9.4	4.5
ER 160	160	40	3.6	11.6	4.6
ER 800	800	20	4.1	15.1	5.1
Delaunay 16	16	40	3.3	5.7	4.3
Delaunay 80	80	40	6.8	6.6	7.8

Appendix

Table 4: Test sets. The benchmark sample above the rule, the deep sample below; ecc., deg. and

L

are the mean eccentricity of the BFS source, the mean degree and the mean trajectory length.

Figure 4: The training-pool axis: seeds perfect at both deep blob cells, 23 seeds per pool. Each pool adds 2,000 graphs of one family to the 6,000 training graphs unless marked 200. Every dense pool, including one no deeper than the training graphs and one of 200 graphs, removes the flood for BPTT; Table 6 gives the band, which the dense pools also close and the sparse grid pool does not.

pool	graphs	mean $n$	mean deg.	mean	max	$P(\mathrm{ecc}\geq 5)$	$\geq 6$	$\geq 9$
				eccentricity			nodes first reached at step
SALSA-CLRS (benchmark)	6,000	10	4.5	2.7	8	0.05	156	0
blob16x4 $\times$ 2,000	2,000	64	15.2	5.5	7	0.83	13,789	0
blob16x8 $\times$ 200	200	128	15.2	10.9	15	1.00	11,687	5,751
blob16x8 $\times$ 2,000	2,000	128	15.2	11.0	15	1.00	115,789	58,245
grid4x24 $\times$ 2,000	2,000	96	3.4	20.0	26	1.00	130,414	93,915

Appendix

Table 5: Training pools. Each extended pool is the 6,000 training graphs plus the graphs listed. “Mean deg.” is each graph’s mean degree averaged over graphs; in the first row it counts the self-loop the benchmark’s sampler adds to every node, which the hand-constructed graphs of the other rows do not have. The degree feature’s mean in § 4.4 is taken over nodes, which weights the larger and denser training graphs more and gives a higher value. The last two columns count nodes (over the whole pool) whose true BFS distance is at least 6 and at least 9, that is, nodes still being reached at late steps.

		seeds perfect		node accuracy
rule	training pool	blob	maze	ER 800	deg. 17
BPTT	+2,000 blob16x4 ( $L\leq 8$ )	23/23	23/23	1.000	1.000
$K{=}1$	+2,000 blob16x4 ( $L\leq 8$ )	23/23	23/23	1.000	1.000
BPTT	+200 blob16x8 ( $L\leq 16$ )	23/23	23/23	1.000	1.000
$K{=}1$	+200 blob16x8 ( $L\leq 16$ )	23/23	23/23	1.000	1.000
BPTT	+2,000 blob16x8 ( $L\leq 16$ )	23/23	23/23	1.000	1.000

Appendix

Table 6: Rates under the extended training pools, 23 seeds per row: the 6,000 training graphs plus 2,000 (or 200) hand-constructed graphs of one family. Columns as in Table 1 ; every row is a separate training run.

	benchmark pool (GRU)		GRU processor, min of two rules			residual variant, min of two rules
cell (node/graph)	BPTT	$K{=}1$	$+$ blob16x4	$+$ 200 blob16x8	no deg.	$+$ blob16x4	$+$ 200 blob16x8
ER 16	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000
ER 80	0.999/0.993	0.999/0.989	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000
ER 160	0.969/0.824	0.981/0.917	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000
ER 800	0.581/0.226	0.771/0.520	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000
Delaunay 16	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000	1.000/1.000

Appendix

Table 7: The combined sample’s 21 cells, node/graph accuracy averaged over 23 seeds per rule: the GRU processor under the pool (both rules), then the minimum over the two rules under each remedy. A dagger marks a cell where the two rules differ by at least 0.005. Separately, the residual variant has seed-level imperfections on the mazes under the blob16x4 pool, and on blob16x64 and degree 33 under the 200-graph pool; every seed remains above 0.95 node accuracy. Under the original pool it fails Delaunay 800 (BPTT 0.44,

K{=}1

0.78), not shown here.

scheme	carried	gradient
SALSA baselines	own state	full
truncated BPTT	own state	last $K$
DEAR	fixed point	implicit
DNAR	true hints	none
ForgetNet	pred. hints	via hints
$K{=}1$ (here)	own state	none

Appendix

Table 8: Training schemes for iterated graph reasoners: what is carried across an application boundary, and whether the loss gradient crosses it. Truncated BPTT backpropagates through the last

K

applications; DEAR is the equilibrium reasoner of Georgiev et al. (2024) and DNAR the discrete reasoner of Rodionov and Prokhorenkova (2025) .

experiment	what we expected	refuted by	what happened
Head to head (2 seeds, then 3, then 23)	$K{=}1$ matches BPTT within 0.02 everywhere (45%); trails by 0.02–0.15 somewhere (35%)	$K{=}1$ trails by more than 0.15 (20%)	neither: matched on every cell but ER $n{=}800$ , where $K{=}1$ was ahead. No predicted outcome covered this, so we retested at 23 seeds under new predictions, which held
Degree sweep	BPTT falls monotonically with degree while $K{=}1$ stays above 0.90 (50%); both fall, BPTT faster (30%)	neither falls	the second, but only in the band, not as a slope: both perfect at low degree, both on the floor at high degree
Truncation axis, $K\in\{1,2,4,8,\infty\}$	a step at $K{=}1$ (40%); monotone in $K$ (35%)	flat in $K$ (25%)	the step
Learning-rate control	$K{=}1$ ’s advantage survives three learning rates at six seeds	$K{=}1$ ’s advantage disappears at some rate	held: $K{=}1$ wins at every rate, the two rules’ gradient norms are close, clipping is rare, and the runs at the operating rate reproduce the earlier ones
Deep families: grids and paths	the two rules separate on depth alone	they do not	they do not: both reach 508 hops on grids and 1,023 on paths in 3 of 3 seeds. The family was saturated
Deep families: blobs	the radius prediction at 3 seeds, then four at 23 seeds: $K{=}1$ perfect in at least 20 (60%); BPTT’s rate below it (70%); BPTT’s failures at a bounded radius; at least one $K{=}1$ failure (45%)	fewer than 15 $K{=}1$ seeds perfect, or BPTT’s rate at or above $K{=}1$ ’s	the radius prediction held; the first three held; the fourth did not ( $K{=}1$ failed in no seed), and $0/23$ is reported as a bound

Appendix

Table 9: What we expected from each experiment, and what happened. Percentages are the probabilities we wrote down for each outcome before the run. “Refuted by” is the outcome that would defeat the claim the experiment was meant to support.

experiment	what we expected	refuted by	what happened
Counting or drift, on the saved weights of 12 models	mixed (35%), drift (35%), counting (30%); the control holds in at least 5 of the 6 failing models (80%)	a drift outcome, for counting as the mechanism	mixed: no model counts, three drift and three lie between; the control held in 6 of 6 and every model reproduced its recorded results, so the paper does not describe the flood as counting
Onset against a uniform degree input	each failing model first floods above the pool’s 99th percentile (65%); its onset does not rise with the input (80%)	a failing model flooding at 1.3 or below	both: first floods at 1.4 to 2.0, onsets falling with the input in 6 of 6
Healthy models under the same input	a delayed flood up to 3.0 in at least one $K{=}1$ model (45%), in none (30%), or only immediate floods or stalls (25%); in at least one healthy BPTT model (65%)	a delayed flood in a $K{=}1$ model, for $K{=}1$ ’s protection	all three $K{=}1$ models and two of three healthy BPTT models: $K{=}1$ changes how far out the input must be
Mazes at the blob input	at least 4 of the 6 failing models flood on a maze with $x_{\mathrm{deg}}$ at 1.9 (60%); at most 1 (25%)	at most 1, for the input’s value as the trigger	6 of 6
Healthy models under the switch and transplant	none floods (85%)	none named	none floods
Progressive loss under BPTT, 23 seeds	at least 4 seeds fail, as floods (55%); 1 to 3 (30%); none (15%)	either remedy at 0/23	the first: 5 of 23 fail, all as floods; all runs have low logged training loss

Appendix

Table 10: What we expected from each experiment, and what happened (continued).

experiment	what we expected	refuted by	what happened
The sums brought back into range, on the saved weights	at the pool’s median count at least 20 of the 25 failing models are exact (65%); failures begin only above the pool’s 95th percentile (60%)	more than 5 models failing at a count of 7, for the range as the cause	17 of 25 repaired, but 12 fail at 7: the range is not the whole account
The same, further predictions	at five, at least 19 of 21 healthy models stay exact (85%); further out, floods come no later and stalls grow no smaller (70% and 60%); at thirty, at least 11 healthy models fail (55%) and at least 20 of the 25 keep their type (70%); capping the sums at eleven helps the dense ER cells in at least 18 of 25 (60%)	none named	19 of 21 stay exact; the predicted flood trend held in 10 of 11 models, but the predicted stall trend held in only 6 of 14; at thirty, 13 healthy models fail on blob16x64 and 14 on either deep cell (Table 18 ); only 15 of 25 keep their type; the cap helps in 8 of 25, all $K{=}1$ , and hurts most BPTT models
The readout of untouched nodes, degree input, 6 failing models	with the true reach mask fed in, its median climbs over steps 2 to 20 at $v{=}1.9$ , and at most a quarter as fast at 1.0, in at least 5 of 6 models (70%)	none named; descriptive	held in 6 of 6, at most a fifth as fast
The same for the 25 failing sum models	floods: the untouched nodes’ readout climbs at 30 neighbors’ worth and at most a quarter as fast at five, in at least 8 of 11 (60%); stalls: the readout of nodes due at the step falls at 30 and at most a quarter as fast at five, in at least 10 of 14 (50%)	none named; descriptive	held for the floods, 10 of 11; failed for the stalls, 2 of 14, so the stalls stay unexplained
The sum models with the training graphs’ self-loops	the failing models still fail (65%); at five neighbors’ worth at least 20 of 25 are exact (50%); at seven at most 5 fail (45%); at least 19 of 21 healthy models stay exact (70%)	13 or more exact under the self-loops, for the missing self-loops as the cause	none of the 25 repaired, so the failures are not an artifact of the missing self-loops; but only 15 are exact at five (17 without them), the same 12 fail at seven, and 4 of the 21 healthy models break
The benchmark’s own models (GIN, PGN and RecGNN as released; GIN with sums), 10 seeds each	the three released models reproduce their published accuracy (65%); in each, at most 1 fitting seed floods at blob16x64 (40%), or 3 or more in one of them (35%); GIN with sums floods in at least 3 (55%) and more often than GIN in at least 7 paired seeds (55%); at most 1 per model floods on maze32 (55%)	a released model flooding in 3 or more seeds, for our account of the trigger in models of that kind	all three reproduce; GIN floods in 3 of 7 fitting seeds, PGN in 1 of 10, RecGNN in 0 of 8 (one seed timed out), each flooding seed on the mazes too, from nearly the same step; GIN with sums declares nodes early in 7 of 7; only 4 seeds fit in both GIN models, too few for the paired predictions. Our account of the trigger covers our processor only

Appendix

Table 11: What we expected from each experiment, and what happened (continued).

comparison	where	counts [95% interval] (discordant)	test	$p$	Holm $p$
Floods, BPTT against $K{=}1$ (GRU processor)	§ 4.1	6/23 [0.10, 0.48] vs. 0/23 [0.00, 0.15] (6, 0)	McNemar	0.031	0.156
Failures, sums against means, BPTT	§ 4.5	15/23 [0.43, 0.84] vs. 0/23 [0.00, 0.15] (15, 0)	McNemar	$<$ 0.001	$<$ 0.001
Failures, sums against means, $K{=}1$	§ 4.5	10/23 [0.23, 0.66] vs. 0/23 [0.00, 0.15] (10, 0)	McNemar	0.002	0.012
Failures with sums, BPTT against $K{=}1$	§ 4.5	15/23 [0.43, 0.84] vs. 10/23 [0.23, 0.66] (10, 5)	McNemar	0.302	0.604
Floods, progressive loss against BPTT	§ 4.7	5/23 [0.07, 0.44] vs. 6/23 [0.10, 0.48] (1, 2)	McNemar	1	1
Floods, random initial states against BPTT	§ 4.7	1/23 [0.00, 0.22] vs. 6/23 [0.10, 0.48] (0, 5)	McNemar	0.062	0.250

Appendix

Table 12: The paper’s main comparisons. Counts are seeds out of those trained: failing seeds (floods or stalls) in the rows on failures, and flooding seeds in the rows on floods, where every failing seed floods; for the benchmark’s GIN, seeds that declare nodes early among the four seeds fitting both versions. Intervals are two-sided 95% Clopper–Pearson intervals, and in parentheses are the seeds that fail under only the first or only the second choice. The

p

values are two-sided: exact McNemar tests for paired counts, including the four shared fitting GIN seeds, and exact sign tests for node accuracy. Holm

p

: Holm’s correction over the eight comparisons, a family chosen after the fact. The interventions act on trained models, each its own control, and are reported as models repaired and broken, outside the family.

model	reproduced	16-node sets	15 sets	fitting	F/S/M/E	early	F/S/M/E	blob16x64 (floor)
		node accuracy			blob16x64		maze32	$\pi$ node acc.
GIN (max), as released	yes	0.982	0.787	7/10	3/1/0/3	3 [0.10, 0.82]	3/2/0/2	0.21 (0.19)
PGN (max), as released	yes	1.000	0.889	10/10	1/0/0/9	1 [0.00, 0.45]	1/0/0/9	0.34 (0.19)
RecGNN (max), as released	yes	1.000	0.853	8/9	0/0/0/8	0 [0.00, 0.37]	0/0/0/8	0.48 (0.19)
GIN with sums	–	0.993	0.651	7/10	6/0/1/0	7 [0.59, 1.00]	3/0/3/1	0.27 (0.19)

Appendix

Table 13: The benchmark’s own models, trained with its code, configurations and hints, ten seeds each (RecGNN nine: one seed hit the time limit), and read on our families. Reproduced: mean

\pi

node accuracy of at least 0.98 on the benchmark’s three 16-node test sets and within five points of the mean over its fifteen published for models trained with hints ( Minder et al., 2023 ) . Fitting: early and late-or-never fractions each below 1% on our ER 16 set; the classes count fitting seeds only. F/S/M/E: flood, stall, mixed, exact; the exact class has both timing-error fractions below 1%. Early: fitting seeds with at least 1% of nodes declared early, with a two-sided 95% Clopper–Pearson interval conditional on fitting. Last column: mean

\pi

node accuracy of the fitting seeds, with the lowest-index floor in brackets; these models predict

\pi

with their own output head, so it is not decoded from timing as ours is. Their

\pi

is poor on the deep graphs even for seeds in the exact reach class, for a reason we do not study.

flooding seed	blob16x32	blob16x64	maze16	maze32	Delaunay 1,600
GIN seed 42	18 [18–19] (20/20)	18 [18] (20/20)	18 [18] (40/40)	18 [18] (20/20)	18 [18–19] (199/200)
GIN seed 43	40 [40–43] (7/20)	39 [39–43] (20/20)	39 [38–43] (40/40)	39 [38–40] (20/20)	–
GIN seed 46	– (0/20)	94 [94–95] (4/20)	98 [95–135] (15/40)	94 [94–102] (20/20)	–
PGN seed 46	28 [27–28] (13/20)	28 [28] (20/20)	30 [29–36] (29/40)	28 [27–38] (20/20)	–

Appendix

Table 14: When the benchmark’s unmodified flooding seeds flood: the median step of the first early declaration over the graphs that have one, its range in brackets, and in parentheses the graphs with an early declaration out of those read. A seed floods only on graphs whose search runs past its onset. Zero counts on shorter trajectories do not test behavior beyond that horizon.

	WS 16	WS 80	WS 160	WS 800	WS 1,600	ER 1,600	Delaunay 1,600
mean trajectory length	3.7	7.2	8.0	12.9	9.9	5.4	23.3
GIN	0/7	0/7	0/7	0/7	0/7	0/7	1/7
PGN	0/10	0/10	0/10	0/10	0/10	0/10	0/10
RecGNN	0/8	0/8	0/8	0/8	0/8	0/8	0/8
GIN with sums	1/7	6/7	7/7	7/7	7/7	7/7	7/7

Appendix

Table 15: The benchmark’s own models on its own test sets that we had not read step by step (first 200 graphs each; WS: Watts–Strogatz). Each cell: fitting seeds that declare at least 1% of the nodes reached early, of the fitting seeds. The first row gives each set’s mean trajectory length; every flood of the unmodified models has its first early declaration at step 18 or later (Table 14 ). Zero counts on shorter trajectories do not establish behavior beyond their observed horizons.

Figure 5: Fraction of nodes at each BFS distance that are declared reached at exactly the right step, on blob16x64. A

K{=}1

model is exact to the last node; a flooding BPTT model is exact to eleven hops and then declares everything reached; the same weights with

h

zeroed every four steps are exact to the last node.

model, rule (23 seeds)	std.	$x_{\mathrm{deg}}{=}1.0$	$0.5$	std.	$1.0$	$0.5$	(max, deep sets)	std.	$1.0$	std.	$1.0$
	perfect at blob 32 & 64			cells exact (of 21)			radius lost	ER 800 node		Delaunay 800 node
GRU, BPTT	17/23	23/23	23/23	9	21	21	0	0.581	1.000	1.000	1.000
GRU, $K{=}1$	23/23	23/23	23/23	13	21	21	0	0.771	1.000	1.000	1.000
residual, BPTT	0/23	0/23	10/23	2	6	4	534	0.379	0.998	0.439	0.381
residual, $K{=}1$	0/23	11/23	16/23	2	9	11	533	0.653	1.000	0.781	0.749

Appendix

Table 16: The degree input clamped at inference, on all 23 seeds of both rules, for the GRU processor and its residual variant, over the 21 cells of the combined sample. This is an intervention on trained models: the same weights and the same graphs as the standard (std.) columns, with the degree input overwritten at inference. “Cells exact” counts the cells on which every seed is at graph accuracy 1. “Radius lost” is the largest loss of exact-timing radius on any blob or maze set. For the GRU processor either clamp makes every model exact on every cell; for the residual variant it closes the ER cells but repairs the deep family only partly and breaks the mazes.

		unscaled	rescaled count $c$
rule	seed	type	exact at 5	first failure $c_{f}$	fails at 7	type at 30
BPTT	0	stall	no	5	yes	exact
BPTT	1	flood	yes	13	no	flood
BPTT	2	flood	yes	15	no	flood
BPTT	3	flood	yes	11	no	flood
BPTT	6	stall	no	5	yes	flood

Appendix

Table 17: The 25 sum models that fail at the deep cells, run from their saved weights with both neighborhood sums rescaled at inference to

c

neighbors’ worth (

c

times the neighborhood mean). Columns: the failure type under the true count; exact at

c{=}5

;

c_{f}

, the smallest

c\geq 5

of the grid at which the model fails at blob16x64; failing at

c{=}7

; the type at

c{=}30

. The training pool’s count has median 5, 95th percentile 9 and maximum 15; a blob node has 15 to 18 neighbors.

rescaled at inference	$c{=}5$	$c{=}7$	$c{=}30$
hidden-state sum only	15 / 1	16 / 1	0 / 21
reach-mask sum only	0 / 21	0 / 20	7 / 8
both sums	17 / 2	13 / 2	2 / 14

Appendix

Table 18: The 46 sum models (25 failing and 21 healthy at the deep cells), run from their saved weights with one neighborhood sum or both rescaled at inference to

c

neighbors’ worth; a sum not rescaled keeps its true count. Each cell: failing models made exact / healthy models broken.

rule (23 seeds)	none	$R{=}4$	$R{=}8$	(max, any set)
	perfect at blob 32 & 64			radius lost
full BPTT	17/23	22/23	22/23	0
$K=1$	23/23	23/23	23/23	0

Appendix

Table 19: The reset, specified before it was run:

h\leftarrow 0

every

R

steps at inference,

f

kept, the same

R

for every seed. This is an intervention on already-trained models. The 46 models of Table 1 ’s BPTT and

K{=}1

rows are measured again on the same graphs, with one thing changed at inference.

residual model	radius	early	late	$R{=}2$	$R{=}4$
	standard rollout			radius, reset
BPTT, seed 0	1	0.976	0.000	1	1
BPTT, seed 1	2	0.975	0.000	2	2
BPTT, seed 9	2	0.975	0.000	2	2
$K{=}1$ , seed 0	6	0.901	0.000	108	108
$K{=}1$ , seed 1	3	0.952	0.000	108	3

Appendix

Table 20: The residual-variant probe: three failing seeds per rule re-run from the saved weights on eight blob16x64 graphs. “Early” and “late” are fractions of nodes declared reached before and after the correct step; every model reaches every node.

model	$q{=}4$	$8$	$16$	at 16	radius	early
	$q$ -clique chains			early	$x_{\mathrm{deg}}{=}1.0$
BPTT, seed 3	87	102	5	0.92	108	0.00
BPTT, seed 0	87	102	11	0.81	108	0.00
BPTT, seed 13	87	102	16	0.75	108	0.00
BPTT, seed 16	87	102	21	0.58	108	0.00
BPTT, seed 22	87	102	23	0.59	108	0.00

Appendix

Table 21: The trigger, on the saved weights of § 4.1 : exact-timing radius on newly generated chains of 64 cliques of

q

nodes (mean degree 4.0, 7.5, 15.2 and eccentricity 68, 83, 91 for

q{=}4,8,16

; largest distances 87, 102, 106), the fraction of nodes reached early at

q{=}16

, and blob16x64 with the degree input set to 1.0 at inference (0.5 gives the same). These chains are a separate sample of eight graphs per size, each with its own random source, so their depths differ from blob16x64’s. Every model reproduces every training hint on every step of all 6,000 training graphs.

	radius at $l$ cliques (mean ecc.)				early
BPTT model	8 (11)	16 (21)	32 (41)	64 (77)	at 64
seed 3	5	5	5	5	0.92
seed 0	12	11	11	11	0.81
seed 13	15	16	16	16	0.74
seed 16	15	28	26	19	0.55
seed 22	15	28	26	24	0.57

Appendix

Table 22: Exact-timing radius of the six BPTT models that fail at blob16x64, on the four blob sizes, and the share of blob16x64’s nodes each declares reached early. The radius is pooled over the graphs of a set, so the graphs that flood earliest set it; a radius that stops growing with the graph marks a flood that begins at a model-specific step. Every

K{=}1

model reaches the set’s largest distance at every size.

Figure 6: Exact-timing radius per seed on blob16x64 (77 hops deep on average, degree 15) for four training rules under the pool. A radius of 108, the set’s largest distance, meets the 95% timing criterion at every distance.

K{=}1

and the stateless block never fall below it; BPTT and

K{=}2

do in about a quarter of seeds.

model	$t^{*}$	switch	transplant	control		at $v$	at $v{=}1.9$
	onset	share of typical steps that count			reading	first flood	maze32 early
BPTT seed 3	4	0.33	0.33	1.00	mixed	1.4	0.99
BPTT seed 0	10	0.40	0.44	1.00	mixed	1.9	0.97
BPTT seed 13	16	0.27	0.29	1.00	mixed	1.6	0.96
BPTT seed 16	24.5	0.12	0.17	1.00	drifts	2.0	0.91
BPTT seed 22	23	0.11	0.18	1.00	drifts	1.9	0.92

Appendix

Table 23: The drift probe per model, on 20 blob16x64 graphs.

t^{*}

: median onset of the flood under the true input. Switch and transplant: the model’s median, over graphs and

k

, of the statistic

s

of Eqs. ( 1 ) and ( 2 ) (Appendix C ), the flood’s observed advance on drift’s prediction as a share of the advance counting predicts: 0 under drift, 1 under counting.

c_{P}

: the control, the flood’s advance as a fraction of

k

when the transplanted state comes from the rollout under the true input, 1 under both readings. Reading: drifts at 0.25 or below, counts at 0.75 or above, mixed between. First flood: the smallest uniform degree input

v

at which at least 1% of the nodes are declared early. Maze32 early: the fraction of maze32’s nodes declared early within 150 steps with the degree input at 1.9.

		$k{=}2$			$k{=}8$			$k{=}32$
model	$t^{*}$	observed	drift	count	observed	drift	count	observed	drift	count
BPTT seed 3	4	6	6	4	11	12	9	35	36	33
BPTT seed 0	10	12	12	10	17	18	10	38	42	33
BPTT seed 13	16	18	18	16	22	24	16	40	48	33
BPTT seed 16	24.5	30	26.5	24.5	31	32.5	24.5	53	56.5	33
BPTT seed 22	23	33	25	23	33	31	23	50	55	33

Appendix

Table 24: Median flood onset on blob16x64 after the first

k

steps under the typical input (the switch), for the six failing BPTT models, against the two predictions: drift,

k+t^{*}

; counting,

\max(t^{*},k+1)

	failing	McNemar $p$ against		paired with BPTT		node acc. against BPTT
added to BPTT	seeds	BPTT	$K{=}1$	repaired	broken	ER 800	deg. 17
progressive loss, $\alpha{=}0.5$	5/23	1	0.062	2	1	$+$ 0.034 (14+/5 $-$ )	$+$ 0.055 (13+/6 $-$ )
random initial state	1/23	0.062	1	5	0	$-$ 0.043 (5+/15 $-$ )	$-$ 0.067 (5+/15 $-$ )

Appendix

Table 25: The literature’s remedies added to BPTT, 23 seeds each, on the combined sample.

\alpha

: the weight of the progressive loss’s extra rollout. Failing seeds: seeds not at graph accuracy 1 at both deep blob cells; every one floods. Exact McNemar

p

against the 6 of 23 of BPTT and the 0 of 23 of

K{=}1

, on the same seeds. Paired with BPTT by seed: seeds repaired and broken. Node accuracy: the mean paired difference from BPTT, with the numbers of seeds above and below.

	node accuracy, mean of 8 seeds					$K=1$ wins
test set	$K=1$	$K=2$	$K=4$	$K=8$	BPTT	vs $K=2$	vs BPTT
ER 800	0.854	0.652	0.662	0.688	0.688	8/8	8/8
ER 800, deg. 17	0.837	0.537	0.555	0.604	0.604	8/8	8/8

Appendix

Table 26: Top: the truncation axis on the ER cells, seeds 0 to 7 of Table 3 ;

K{=}1

wins every paired comparison in 8/8 seeds, and

K{=}8

gives the same results as BPTT in every seed. Bottom: the learning-rate control, seeds 0 to 5; “wins” counts seeds in which

K{=}1

beats

K{=}2

at the same rate, and the last two columns give the ratio of mean pre-clip gradient norms and the largest percentage of steps on which clipping fired in any run.

	node accuracy		graph accuracy		radius
test set	BPTT	$K=1$	BPTT	$K=1$	BPTT	$K=1$
ER 16	0.000	0.000	0.000	0.000	0.000	0.000
ER 80	0.003	0.003	0.018	0.018	0.000	0.000
ER 160	0.038	0.042	0.120	0.147	0.864	1.033
ER 800	0.107	0.192	0.101	0.261	0.507	2.130
Delaunay 16	0.000	0.000	0.000	0.000	0.000	0.000

Appendix

Table 27: Sample standard deviations across the 23 paired head-to-head seeds. Means and paired sign counts are in Table 3 . Radius is in hops; accuracy is a fraction. The graph samples are fixed.

family	MB/appl.	OOM at $L$	GB, all $L$
	BPTT		$K{=}1$
Delaunay $n=800$	284	64	0.39
grid $4\times 256$	273	64	0.36
blob $16\times 64$	569	32	0.91

Appendix

Table 28: Recorded peak allocated GPU memory in a separate training-memory stress probe, batch 16 on a T4.

L

counts the initial step; each sweep executes

L-1

applications. BPTT’s slope is between the first and last completed lengths; OOM is the first tested length that exhausted memory.

K{=}1

has the listed peak at every tested power of two from

L=4

through 8,192. These are controlled horizon sweeps, not peak memory measurements for every training run.

Explore similar work

Oct 13, 2026

Input-Conditioned Search for Efficient Test-Time Scaling of Recursive Reasoners

People often tackle difficult problems by thinking more deeply or exploring more possibilities. Similarly, recursive reasoners, which reason by repeatedly applying a learned update rule to latent states, can also scale inference through more updates (depth) or additional trajectories generated by perturbing latent states (width). When people hit a dead end in their thinking, they may step back and approach the problem from a fresh angle. However, neither depth scaling nor perturbation-based width scaling of recursive reasoners can reliably achieve this: both may converge to incorrect attractors. To address this, we propose to explore diverse reasoning traces by applying different update maps to the same latent state, without any additional training. We realize this idea through Input-Conditioned Search (ICS), which searches over input conditions to induce alternative update maps from the pretrained reasoner. Across six reasoning tasks, ICS achieves the highest mean accuracy, while requiring up to two orders of magnitude fewer model FLOPs than the evaluated scaling baselines. Controlled experiments confirm that ICS can redirect trajectories from the same state. Our theoretical analysis and rigorous numerical verification also confirm that ICS can locally eliminate incorrect attracting fixed points. Together, these findings establish ICS as an effective axis for efficient test-time scaling and motivate further research on shaping recursive reasoning during training and at test time.

Haochen Shi, Tianwen Fu, Qianggang Ding +7

Mila – Quebec AI Institute · Université de Montréal · University of Southern California +2

Inference-Time Search Inference-Time Scaling Test-Time Scaling Efficient Language Model Reasoning Continuous Latent Reasoning

Ask PDF

Aug 18, 2026

Think Shallow, Solve Deep: Controlling Recurrent Dynamics for Reliable Test-Time Depth

Recurrent-depth reasoners aim to solve harder problems by iterating their update longer at test time, but additional iterations can improve, preserve, or degrade an answer. We show that a measurable property of the trained operator, its finite-time dynamical regime (estimated as settling, marginal, or drifting), indicates which of these occurs. We give a sufficient condition for depth-safety: once an operator's per-step displacement is small relative to the decoder margin, the decoded answer cannot change under further iterations. Empirically, on algorithmic tasks trained from

800

unaugmented examples per difficulty tier, settling operators do not degrade with added depth, and on some tasks convert it into higher accuracy on harder unseen instances (Sudoku,

0.19

0.34

past the training horizon). A single terminal fixed-point objective moves the regime and the depth behavior together: removing it induces drift and removes the gains, and adding it to a generic recurrence yields depth-safe extrapolation on carry propagation. We give four operational criteria for useful test-time depth, use them to catalogue failure modes, and, as a consistency check, apply the same measurements to Huginn-3.5B, which falls in the non-settling family.

Ivan Viakhirev, Kirill Borodin, Amirah Almutairi +3

FRC RAS, Saint-Petersburg, Russia · ITMO, Saint-Petersburg, Russia · lab260, Moscow, Russia +4

Test-Time Scaling Recurrent Neural Networks Neural Algorithmic Reasoning Algorithmic Reasoning

Ask PDF

Sep 28, 2026

Not All Thinking is Created Equal: Latent Reasoning Discovers a Recurrent Search Algorithm for Depth Generalization

Large Language Models can perform multi-step reasoning and improve task performance through different forms of intermediate computation, from token-based traces to computation carried out in latent space. However, a question remains open: do these different forms of thinking rely on the same underlying mechanism? To address this, we train and compare five variants of the same GPTNeoX backbone from scratch on an extended multi-hop reasoning task (ProsQA-Ext): a vanilla model, a Chain-of-Thought (CoT) model, a Pause Token model, and two latent-reasoning models that are optimized end-to-end without intermediate reasoning traces. We find that, strong in-distribution (ID) performance does not guarantee depth generalization. Vanilla, CoT, and Pause Token models solve ID problems well, but rely largely on local graph features and generalize poorly to out-of-distribution (OOD) problems with longer hops. In contrast, latent variants generalize better and show internal dynamics consistent with forward reachability propagation on the graph. Causal interventions and circuit analysis localize this computation to a sparse recurrent search circuit in the bottleneck latent model: an attention head retrieves graph relations, an MLP and the residual stream update the reachability state across recurrent steps, while multiple attention heads together then do the candidate matching. Together, these results show that different thinking mechanisms can learn distinct computational solutions, even at similar ID performance. In this setting, latent recurrence supports a reusable forward-search algorithm that generalizes beyond the training depth.

Huzi Cheng, Zhewei Zhang

University of Minnesota · Independent Researcher

LLM Reasoning with Graphs LLM Interpretability Neural Algorithmic Reasoning Recurrent Transformers Latent Reasoning

Ask PDF