# Percolation-Certified Neural Cellular Automaton

- ID: 604
- Canonical URL: https://synthcore.org/idea/604/percolation-certified-neural-cellular-automaton
- API JSON: https://synthcore.org/api/idea/604.json
- API Markdown: https://synthcore.org/api/idea/604.md
- Verification status: failed_benchmark
- Source: [arXiv:2607.08914](https://arxiv.org/abs/2607.08914)
- Category: dynamics
- Solves: stability, scalability, accuracy
- ML areas: cnn, ssm, world-model, training-dynamics
- Math tags: stochastic-processes, probability, dynamical-systems, combinatorics
- Ratings: usefulness 7/10; difficulty 5/10; novelty 8/10

## Idea description

Construct a finite-range, translation-equivariant recurrent convolutional module with an absorbing inactive state, then train its local dynamics so that seeded activity crosses coarse-grained space-time blocks with probability above an oriented-percolation threshold. This should produce reliable long-range propagation without dense global attention while remaining robust to non-monotone local updates and perturbations. Block statistics also provide a diagnostic for vanishing propagation or unstable exploding activity.

## Mathematical statement

The update is represented as a measurable random local map $\eta_{n+1}=F(\eta_n,U(\cdot,n+1))$, where $\eta_n\in E^{\mathbb Z}$ is the spatial state and $U(y,n)$ are i.i.d. local random variables. Translation equivariance requires $F(\theta_x\eta,\theta_xU)=\theta_xF(\eta,U)$, and finite-range locality requires $\eta_{n+1}(x)$ to depend only on $\eta_n(y)$ and $U(y,n+1)$ for $y\in B_R(x)$; the absorbing condition is $\eta_n|_{B_R(x)}=0\Rightarrow\eta_{n+1}(x)=0$. Space-time is coarse-grained into blocks indexed by $(z,t)\in\mathbb L=L_{\mathrm{bl}}\mathbb Z\times T_{\mathrm{bl}}\mathbb N_0$, with $\mathtt{Block}(z,t)=\{(x,n):x\in B_{K L_{\mathrm{bl}}}(z),\ t<n\le t+T_{\mathrm{bl}}\}$. Define $Y(z,t)=\mathbf 1_{U\in G^{U}_{\mathrm{loc}}(z,t)}$, where $G^{U}_{\mathrm{loc}}(z,t)$ is the event that a block successfully propagates a well-started seed to required neighboring blocks. The key assumption is a coupling to i.i.d. Bernoulli variables $\widetilde Y(z,t)$ satisfying $Y(z,t)\ge\widetilde Y(z,t)$ and $p=\mathbb P(\widetilde Y(0,0)=1)>p_c$, where $p_c$ is the critical probability for oriented site percolation with edges from $(z,t)$ to $(z',t+T_{\mathrm{bl}})$ whenever $|z-z'|\le L_{\mathrm{bl}}$. The neural adaptation estimates $p$ empirically and maximizes a lower-confidence estimate of the block-success probability. The extracted parameter choice is $L_{\mathrm{bl}}=\frac{16}{|\log\kappa|}\lceil R\log R\rceil$, $T_{\mathrm{bl}}=\left\lceil\frac{3L_{\mathrm{bl}}}{\lceil sR\rceil}\right\rceil$, and $K=\lceil10/s\rceil$, where $R$ is the receptive-field radius, $\kappa\in(0,1)$ is a local forgetting parameter, and $s\in(0,1)$ is the target comparison-profile speed. The synchronization estimate is $|A_{h_1,T_{\mathrm{bl}}}|\kappa^h$, where $A_{h_1,T_{\mathrm{bl}}}$ is the finite space-time target set and $h$ is the common interior depth; this expresses exponentially decreasing sensitivity to initial local states.

## Key formulas

- $$\eta_{n+1}=F(\eta_n,U(\cdot,n+1)),\qquad F(\theta_x\eta,\theta_xU)=\theta_xF(\eta,U).$$
- $$\eta_n(x)\text{ depends only on }\{\eta_{n-1}(y),U(y,n):y\in B_R(x)\},\qquad \eta_{n-1}|_{B_R(x)}=0\Rightarrow\eta_n(x)=0.$$
- $$Y(z,t)=\mathbf 1_{U\in G^{U}_{\mathrm{loc}}(z,t)},\qquad Y(z,t)\ge \widetilde Y(z,t),\qquad \widetilde Y\stackrel{\mathrm{i.i.d.}}{\sim}\mathrm{Bernoulli}(p),\quad p>p_c.$$
- $$L_{\mathrm{bl}}=\frac{16}{|\log\kappa|}\lceil R\log R\rceil,\qquad T_{\mathrm{bl}}=\left\lceil\frac{3L_{\mathrm{bl}}}{\lceil sR\rceil}\right\rceil,\qquad K=\left\lceil\frac{10}{s}\right\rceil.$$

## Implementation notes

(1) Exact integration point: replace one or more spatially local recurrent blocks in a neural cellular automaton, convolutional SSM, or video/world-model backbone. For a feature field $h_t\in\mathbb R^{C\times H\times W}$, use a shared depthwise or ordinary convolution with radius $R$, followed by a gated residual update. Add an explicit inactive channel and enforce the absorbing condition by multiplying the output gate by $a_t(x)=\mathbf 1[\|h_t(x)\|_2>\epsilon]$, or set the update to zero when every site in the receptive field is inactive. Shared convolution weights enforce translation equivariance. During training, inject fixed-amplitude Gaussian or uniform local noise $U_t(x)$ so that shared-noise coupling can be evaluated.

(2) Pseudocode:
```text
for each minibatch sample:
    h = seeded_state()
    for t in range(T):
        u = iid_noise_like(h)
        q = local_conv(h, radius=R) + noise_projection(u)
        h_new = gated_update(h, q)
        active = local_norm_pool(h, radius=R) > eps
        h = h_new * active
    for each coarse block (z,t):
        Y[z,t] = block_success(seed_at_bottom, shared_noise, target_blocks)
    p_hat = mean(Y)
    L = task_loss + lambda_block * relu(p_target - p_hat)^2
        + lambda_sync * disagreement_loss(shared_noise, perturbed_seed_pair)
    backpropagate(L)
```
`block_success` is one when a seed at the bottom of a window of width $K L_{\mathrm{bl}}$ and duration $T_{\mathrm{bl}}$ reaches every required neighboring block within distance $L_{\mathrm{bl}}$ while remaining above an activity threshold. Set $L_{\mathrm{bl}}$ and $T_{\mathrm{bl}}$ using the displayed formulas, initially with $\kappa$ estimated from disagreement decay and $s$ chosen as the desired normalized propagation speed.

(3) Mathematical versus empirical quantities: translation equivariance and locality are architectural constraints. The percolation threshold $p_c$ should be estimated once by Monte Carlo for the selected neighbor geometry. Estimate $p=\mathbb P(Y=1)$ over held-out noise seeds and use a Wilson lower confidence bound rather than the raw mean. Estimate $\kappa$ by fitting $\log D(h)$ against $h$, where $D(h)$ is the probability that two states with different interiors disagree at a target site after $h$ common local layers. The percolation argument is treated as a certificate only when the lower confidence bound on $p$ exceeds $p_c$.

(4) First cheap experiment: train a $32\times32$ neural cellular automaton on Moving-MNIST or a binary cellular-automaton prediction task, comparing a standard local ConvGRU against the constrained model at equal parameter count and FLOPs. Measure task loss, survival from a one-cell seed, front displacement per recurrent step, and agreement between two perturbed initial states under identical noise. The expected signal is higher survival probability and longer reliable propagation at equal depth, with disagreement decreasing approximately exponentially in common interior depth; a useful target is at least twice the reliable propagation distance before activity dies without increasing false activation outside the propagation cone.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: inconclusive
- Verdict: Built a vectorized finite-range stochastic neural cellular automaton with exact absorbing inactivity, local shared dynamics, block-success estimation, Wilson confidence certification, and an oriented-percolation threshold sweep. The mechanism predictions were confirmed: displacement matched R*T across five radius/time settings, shared-noise disagreement matched kappa^h to numerical precision, and certification transitioned from false at beta<=0.45 to true at beta>=0.55 with estimated pc=0.537. The secondary survival comparison favored the high-transmission certified setting, but it was not a fair trained equal-compute neural baseline comparison.

### Mechanism check

- Verdict: Built a vectorized finite-range stochastic neural cellular automaton with exact absorbing inactivity, local shared dynamics, block-success estimation, Wilson confidence certification, and an oriented-percolation threshold sweep. The mechanism predictions were confirmed: displacement matched R*T across five radius/time settings, shared-noise disagreement matched kappa^h to numerical precision, and certification transitioned from false at beta<=0.45 to true at beta>=0.55 with estimated pc=0.537. The secondary survival comparison favored the high-transmission certified setting, but it was not a fair trained equal-compute neural baseline comparison.
- Confidence: 7/10
- Limitations: This is a 1D toy binary stochastic CA, not a trained 2D neural cellular automaton or ConvGRU. The contraction check uses an explicitly affine contractive coupling, so it verifies the scaling law but does not establish learned neural dynamics. The baseline comparison changes transmission strength and is only secondary; no equal-parameter/equal-FLOP task-training experiment, perturbation robustness study, or rigorous i.i.d. block coupling proof was performed.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 8/8
- Benchmark verdict: idea better (significant)

## Artifacts

- [bench_report.json](https://synthcore.org/code/273/bench_report.json)
- [percolation_toy.py](https://synthcore.org/code/273/percolation_toy.py)
- [report.md](https://synthcore.org/code/273/report.md)
- [report_bench_2026-08-31T003744.md](https://synthcore.org/code/273/report_bench_2026-08-31T003744.md)
- [results.json](https://synthcore.org/code/273/results.json)
- [stage2_bench.py](https://synthcore.org/code/273/stage2_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/273)

## Disclaimer

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