# Predictive Spike Timing Enables Distributed Shortest Path Computation in Spiking Neural Networks

arXiv: https://arxiv.org/abs/2509.10077 · HTML: https://mlsanity.com/paper/2509.10077/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 144 references that are in the map.
- First posted on arXiv 12 Sep 2025.

## Builds on (most cited first, 19 of 19)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Emergence of grid-like representations by training recurrent neural networks to perform spatial localization](https://mlsanity.com/paper/1803.07770/) (2018)
- [EfficientZero V2: Mastering Discrete and Continuous Control with Limited Data](https://mlsanity.com/paper/2403.00564/) (2024)
- [Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition](https://mlsanity.com/paper/2012.04053/) (2020)
- [High-performance deep spiking neural networks with 0.3 spikes per neuron](https://mlsanity.com/paper/2306.08744/) (2023)
- [DYNAP-SE2: a scalable multi-core dynamic neuromorphic asynchronous spiking neural network processor](https://mlsanity.com/paper/2310.00564/) (2023)
- [The Backpropagation Algorithm Implemented on Spiking Neuromorphic Hardware](https://mlsanity.com/paper/2106.07030/) (2021)
- [Langevin Soft Actor-Critic: Efficient Exploration through Uncertainty-Driven Critic Learning](https://mlsanity.com/paper/2501.17827/) (2025)
- [A Survey of Shortest-Path Algorithms](https://mlsanity.com/paper/1705.02044/) (2017)
- [Metastable dynamics of neural circuits and networks](https://mlsanity.com/paper/2110.03025/) (2021)
- [Sequence learning, prediction, and replay in networks of spiking neurons](https://mlsanity.com/paper/2111.03456/) (2021)
- [Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps](https://mlsanity.com/paper/2311.11793/) (2023)
- [Motor control by precisely timed spike patterns](https://mlsanity.com/paper/1605.09023/) (2016)
- [Computation with Sequences in a Model of the Brain](https://mlsanity.com/paper/2306.03812/) (2023)
- [Cortical computations via metastable activity](https://mlsanity.com/paper/1906.07777/) (2019)
- [Learning Precise Spike Timings with Eligibility Traces](https://mlsanity.com/paper/2006.09988/) (2020)
- [Threshold Adaptation in Spiking Networks Enables Shortest Path Finding and Place Disambiguation](https://mlsanity.com/paper/2503.21795/) (2025)

## Abstract (arXiv)

Efficient planning and sequence selection are central to intelligence, yet current approaches remain largely incompatible with biological computation. Classical graph algorithms like Dijkstra's or A* require global state and biologically implausible operations such as backtracing, while reinforcement learning methods rely on slow gradient-based policy updates that appear inconsistent with rapid behavioral adaptation observed in natural systems. We propose a biologically plausible algorithm for shortest-path computation that operates through local spike-based message-passing with realistic processing delays. The algorithm exploits spike-timing coincidences to identify nodes on optimal paths: Neurons that receive inhibitory-excitatory message pairs earlier than predicted reduce their response delays, creating a temporal compression that propagates backwards from target to source. Through analytical proof and simulations on random spatial networks, we demonstrate that the algorithm converges and discovers all shortest paths using purely timing-based mechanisms. By showing how short-term timing dynamics alone can compute shortest paths, this work provides new insights into how biological networks might solve complex computational problems through purely local computation and relative spike-time prediction. These findings open new directions for understanding distributed computation in biological and artificial systems, with possible implications for computational neuroscience, AI, reinforcement learning, and neuromorphic systems.