# Multi-Token Random-Walk Learning via Meeting-Triggered Information Exchange

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

## Key facts

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

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

- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Lower Bounds for Finding Stationary Points II: First-Order Methods](https://mlsanity.com/paper/1711.00841/) (2017)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization](https://mlsanity.com/paper/1804.06568/) (2018)
- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [A principled framework for the design and analysis of token algorithms](https://mlsanity.com/paper/2205.15015/) (2022)
- [Decentralized Consensus Optimization Based on Parallel Random Walk](https://mlsanity.com/paper/1911.09747/) (2019)
- [A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning](https://mlsanity.com/paper/2309.09977/) (2023)
- [Random Walk Learning and the Pac-Man Attack](https://mlsanity.com/paper/2508.05663/) (2025)
- [Self-Creating Random Walks for Decentralized Learning under Pac-Man Attacks](https://mlsanity.com/paper/2601.07674/) (2026)
- [RW-LoRA: Communication-Efficient Decentralized LoRA Fine-Tuning via Random Walks](https://mlsanity.com/paper/2609.00078/) (2026)

## Abstract (arXiv)

Random walk (RW)-based algorithms are widely used in decentralized learning due to their low communication overhead and scalability. While most existing methods rely on a single token, multiple tokens can explore the network in parallel and exchange information upon meeting. However, the fundamental benefits of such meeting-triggered interactions remain unclear. In this work, we investigate multi-token RW learning under two information exchange policies: textscAverage-Gradient and textscAverage-Model, which average stochastic gradients and updated models, respectively, when tokens meet. We establish iteration complexity lower bounds for non-convex, convex, and strongly convex objectives on complete graphs, which apply to both exchange policies. Compared with single-token RW learning, the scaling factor in these bounds is reduced by a factor of m2 for non-convex and convex objectives, and by an exponentially in m for strongly convex objectives, where m denotes the number of tokens. Numerical experiments reveal distinct behaviors of the two policies under two performance criteria: mean-token loss (the average loss across all tokens) and best-token loss (the minimum loss across all tokens). textscAverage-Model achieves lower mean-token loss and is relatively insensitive to the network-to-token ratio N/m, where N is the number of nodes. In contrast, textscAverage-Gradient achieves lower best-token loss but exhibits a trade-off between parallel exploration and gradient interference as N/m decreases.