# KS-Adaptive Graph Halting

- ID: 1021
- Canonical URL: https://synthcore.org/idea/1021/ks-adaptive-graph-halting
- API JSON: https://synthcore.org/api/idea/1021.json
- API Markdown: https://synthcore.org/api/idea/1021.md
- Verification status: mechanism_failed
- Source: [arXiv:2607.16676](https://arxiv.org/abs/2607.16676)
- Category: architecture
- Solves: speedup, scalability, stability
- ML areas: graph-nn, inference-speedup, training-dynamics
- Math tags: probability, stochastic-processes, dynamical-systems
- Ratings: usefulness 7/10; difficulty 5/10; novelty 5/10

## Idea description

Use the KS ratio to decide how many message-passing layers to execute per graph or per node, rather than selecting a fixed depth. In the subcritical regime, stop once the predicted remaining effect is below a tolerance; in the supercritical regime, continue until the observed logit change becomes small or a larger budget is reached.

## Mathematical statement

For the paper's depth-\(\ell\) classifier, the error sequence satisfies \(|\mathcal{E}(\ell)-\mathcal{E}(\ell')|\leq C\kappa^{(\ell+1)/3}\) for \(\ell'>\ell\) when \(\kappa=\gamma^2\Delta<1\). Thus the uncomputed tail has an explicit geometric upper envelope with decay exponent \(1/3\), giving a sufficient stopping depth proportional to \(\log(1/\varepsilon)/\log(1/\kappa)\). The paper also states that under regularity, sufficiently deep layers still change the decision with probability at least \(c\kappa^{\ell/2}\), where \(c>0\) is a model-dependent anti-concentration constant. This suggests stopping only when both the theoretical tail estimate and the observed decision change are small.

## Key formulas

- $$\kappa=\gamma^2\Delta,$$
- $$|\mathcal{E}(\ell)-\mathcal{E}(\ell')|\leq C\kappa^{(\ell+1)/3}\qquad(\kappa<1,\ \ell'>\ell),$$
- $$\ell_{\varepsilon}=\left\lceil\frac{3\log(C/\varepsilon)}{\log(1/\kappa)}-1\right\rceil,$$
- $$\Pr\{\text{layer }\ell\text{ changes the decision}\}\geq c\,\kappa^{\ell/2}.$$

## Implementation notes

Add adaptive computation to an otherwise standard message-passing GNN. Process a sampled neighborhood one hop at a time, retain the current root logit \(s_\ell\), and define the empirical change \(d_\ell=|s_\ell-s_{\ell-1}|\) or, for classification, the fraction of nodes whose predicted class changed between layers. Estimate \(\Delta\) from the graph and estimate \(\gamma\) either from labels on a calibration split, from a fitted edge-correlation parameter, or as the sigmoid-constrained scalar used by the attenuated model. Compute \(\kappa=\gamma^2\Delta\). For \(\kappa<1\), choose a conservative budget using \(\ell_\varepsilon=\lceil3\log(C/\varepsilon)/\log(1/\kappa)-1\rceil\), with \(C\) calibrated by measuring the error gap between depths 2 and 4 on a validation set. At each layer, halt a node when \(d_\ell<\tau\) for two consecutive layers and the theoretical tail proxy \(C\kappa^{(\ell+1)/3}<\varepsilon\); batch nodes with the same active depth. For \(\kappa\geq1\), disable the subcritical certificate and use a maximum depth plus the empirical change criterion. The paper determines the geometric form, while \(C\), \(c\), and \(\tau\) are validation estimates. Test first on Reddit or ogbn-arxiv with a 2-to-12-layer GraphSAGE, comparing fixed depth, Ponder-style halting, and KS halting at equal accuracy. The target signal is 20–50% fewer message-passing FLOPs and sampled edges at unchanged accuracy, with no increase in worst-case error and a clear correlation between predicted \(\ell_\varepsilon\) and the empirically optimal depth.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built and ran a reproducible KS certificate sweep, stability-boundary sweep, and synthetic SBM message-passing halting experiment. The geometric ratio prediction and the decay/critical/growth boundary were exactly observed, but the literal stopping-depth formula underestimated the exact summed-tail depth by 1.17–1.59x because it omits the geometric-series prefactor. On the GNN task, adaptive halting matched fixed-depth accuracy (1.00 versus 1.00) but used 1.41x the message-work, so the proposed speedup was not observed.

### Mechanism check

- Verdict: Built and ran a reproducible KS certificate sweep, stability-boundary sweep, and synthetic SBM message-passing halting experiment. The geometric ratio prediction and the decay/critical/growth boundary were exactly observed, but the literal stopping-depth formula underestimated the exact summed-tail depth by 1.17–1.59x because it omits the geometric-series prefactor. On the GNN task, adaptive halting matched fixed-depth accuracy (1.00 versus 1.00) but used 1.41x the message-work, so the proposed speedup was not observed.
- Confidence: 9/10
- Limitations: Only a synthetic 600-node SBM was tested; no Reddit/ogbn-arxiv data, sampled-neighborhood implementation, Ponder baseline, wall-clock benchmark, or GPU execution was evaluated. The toy recurrence verifies the claimed scaling but does not establish the paper's bound constants for a trained GNN.

## Artifacts

- [ks_adaptive_experiment.py](https://synthcore.org/code/420/ks_adaptive_experiment.py)
- [ks_results.json](https://synthcore.org/code/420/ks_results.json)
- [report.md](https://synthcore.org/code/420/report.md)
- [Download all files as ZIP](https://synthcore.org/download/420)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.