A spatial transcriptomics slide measures gene counts at thousands to millions of small tissue locations ("spots"), and most spots contain several cells. Deconvolution means estimating what fraction of each spot belongs to each cell type. Get it wrong and a change in cell mixture looks like a change in how cells regulate their genes, which is the cellular composition confounding problem. Today's choice is unpleasant. Fast per-spot methods ignore that neighbouring spots share tissue context. Spatially coupled methods either run as one centralized model over the whole slide, which hits memory walls, or they smooth neighbours together so strongly that thin tissue layers and tumour margins blur. That blurring is itself a composition artifact: it leaks one region's cell mixture into the next.
We propose to treat each spot as an agent in a swarm, the way multi-robot localization treats each robot. Every spot holds a belief about its own cell-type proportions and exchanges small messages only with its physical neighbours. The coupling between neighbours uses a robust penalty that switches itself off when two spots clearly disagree, so smoothing stops at real boundaries. A small set of shared "calibration" variables absorbs systematic differences between the single-cell reference and the spatial platform, much as robots estimate their sensor offsets while localizing. Cost per spot stays constant, total cost grows linearly with the number of spots, and each spot gets an uncertainty estimate for free.
Core Claim
The method is a direct transfer of Distributed Simultaneous Localisation and Auto-Calibration using Gaussian Belief Propagation, which supplies the machinery. That paper has each robot refine its pose and its sensor calibration through Gaussian belief messages with observed neighbours only. A robust kernel called dynamic covariance scaling down-weights inconsistent measurements, and the system scales to 128 robots with constant per-node cost.
We make the same three moves for tissue. Each spot's unknown is its cell-type composition, written in additive log-ratio coordinates $z_i \in \mathbb{R}^{K-1}$ so that the proportions $w_i = \mathrm{softmax}([z_i, 0])$ are automatically non-negative and sum to one. Neighbour factors are robust rather than quadratic. Gene-wise platform effects are explicit variables solved jointly with composition.
The slide-wide objective is
$$ E(z,\alpha) = \sum_i -\log \mathrm{NB}\Big(y_i \,\Big|\, s_i \textstyle\sum_k w_{ik}\, \alpha \odot c_k\Big) + \sum_{(i,j)\in \mathcal{N}} \rho_{\mathrm{DCS}}\big(\lVert z_i - z_j\rVert_{\Lambda}\big) + \tfrac{1}{2\sigma^2}\lVert \log \alpha\rVert^2, $$
where the symbols are:
- $y_i$ is the count vector at spot $i$ and $s_i$ its library size.
- $c_k$ is the reference profile of cell type $k$.
- $\alpha$ is a vector of gene-wise platform scale factors.
- NB is a negative binomial likelihood.
- $\mathcal{N}$ is the set of physically adjacent spot pairs.
- $\rho_{\mathrm{DCS}}$ is the dynamic-covariance-scaling robust penalty with neighbour precision $\Lambda$.
We minimize this by Gaussian belief propagation. The non-Gaussian count likelihood is relinearized at each round, the same way the robot paper relinearizes its nonlinear geometric factors.
The claim is twofold. First, this local solver reaches the accuracy of a centralized optimizer of the same objective, with linear wall-clock and fixed per-worker memory to several million spots. Second, robust coupling measurably reduces composition leakage at boundaries, and with it the false "layer-specific expression" signals that leakage creates downstream.
Relation to Prior Work
GraphST and DeepST are the closest existing work. Spatially informed clustering, integration, and deconvolution of spatial transcriptomics with GraphST and DeepST also treat spots as graph nodes connected to spatial neighbours. Both train centralized graph networks with a contrastive objective that pulls neighbour embeddings together, and they then map a single-cell reference onto spots. They motivate this proposal in two ways. They report 100,000 spots in roughly 30 minutes on one GPU, and they acknowledge both the need to move to distributed computation for sub-cellular platforms and the risk of over-smoothing thin structures. We differ in three respects. Our coupling acts directly on proportions rather than on learned embeddings. It is robust rather than homophilous. And the computation is genuinely local rather than full-graph.
POLARIS motivates the confounding angle. POLARIS fits a negative binomial deconvolution model with layer-specific expression shifts. Because it shares one shift across all cell types, mis-estimated composition near a layer edge is absorbed into that shift. This is exactly the composition-versus-intrinsic-change confusion we want to measure.
Two benchmark sources constrain the design. The benchmark of 18 methods across 50 datasets, A comprehensive benchmarking with practical guidelines for cellular deconvolution of spatial transcriptomics, names CARD, Cell2location and Tangram as the most robust and accurate tools. It notes that Cell2location is heavy on large grids and that the fastest methods give up posterior uncertainty, and it identifies reference-versus-target platform effects as a systematic error source. Our calibration variables target that last point directly. NNICE shows in bulk data that point estimates of fractions are unreliable for closely related lineages, with CD4+ T cells reaching only R = 0.383. We take from this that calibrated per-spot uncertainty is a requirement, not an extra.
On the multi-agent side, the locality principle behind EGO-Swarm and the million-agent pathfinding results reported in Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning justify expecting constant per-agent cost when neighbourhood size is bounded. A tissue grid satisfies that condition naturally: a hexagonal Visium array has six neighbours per spot.
We deliberately do not build on DoF. Its linear noise factorization exists to preserve Gaussian diffusion noise in agent policy generation, a generative problem we do not have. The log-ratio parametrization handles the simplex constraint more simply. The LLM "multi-agent" systems CellAgent and PhenoGraph orchestrate analysis code rather than solve the unmixing problem, so they are not competitors.
Research Program
Solver. We will build a GBP deconvolution solver in which each spot node holds a Gaussian belief over $z_i$. A spot's per-iteration cost is $O(GK + dK^2)$ for $G$ genes, $K$ cell types and $d$ neighbours, so total cost per sweep is linear in the number of spots.
Calibration variables. These cannot be global without breaking locality. Following the consensus idea in distributed ADMM planners such as Decentralized iLQR for Cooperative Trajectory Planning of Connected Autonomous Vehicles via Dual Consensus ADMM, we keep one copy of $\alpha$ per spatial region, tie the copies with consensus factors, and let each region's spots update only their local copy. This avoids the seams of naive tiling, because neighbour factors still cross region borders.
Uncertainty. The Gaussian belief in log-ratio space maps to a logistic-normal distribution on proportions. That distribution can be skewed near zero, which partly answers the concern that Gaussian messages misrepresent count data. We test whether that is enough rather than assume it.
Analyses. We will run three. A boundary-stratified error analysis bins spots by distance to annotated tissue edges. A leakage-to-confounding analysis plants no cell-intrinsic layer shift in simulation and counts how many false layer-specific genes a POLARIS-style test reports downstream of each deconvolution method. A scaling analysis covers 10,000 to roughly 5 million spots.
Known failure modes. The robot paper documents that sparse connectivity unanchors the solution. We will probe the analogue, which is large regions with nearly empty or low-count spots, by subsampling counts until the method degrades.
Baselines
The naive reference point is per-spot independent deconvolution under the identical negative binomial likelihood and calibration, with neighbour factors removed. This is the main ablation. It is already linear and embarrassingly parallel, so any benefit we claim must come from coupling. We run it with the same reference, gene set and stopping tolerance. Beating it means lower proportion error in tissue interiors and low-count spots, with no loss within two spots of a boundary.
The second ablation replaces the robust kernel with a plain quadratic penalty at the same precision $\Lambda$, which isolates the boundary-gating ingredient. Beating it means a significant reduction in boundary-band error and in downstream false layer-specific genes, with interior accuracy unchanged. A third ablation removes the calibration variables, to isolate the platform-effect correction on real data where reference and target come from different assays.
The strongest existing competitors are the three top performers in A comprehensive benchmarking with practical guidelines for cellular deconvolution of spatial transcriptomics: Cell2location, CARD and Tangram. We add RCTD as the standard per-spot probabilistic method and GraphST deconvolution as the closest spatial-graph method. All receive the same reference atlas, gene panel and preprocessing, with each method's documented defaults plus an equal small hyperparameter search on a held-out simulated slide. They run on the same hardware budget of one GPU or an equal CPU-core allotment. No reported numerical deconvolution accuracy for Cell2location, CARD or Tangram was found on Lacuna; the file records only rankings. For runtime, the reported anchor is GraphST/DeepST processing about 100,000 spots in roughly 30 minutes (GraphST).
We also run a centralized optimizer of our exact objective (L-BFGS over the full graph) as a ceiling. The robot paper reports how large the distributed-versus-centralized gap was in its setting: 0.054 m against 0.043 m RMSE at 64 robots (DSLAC). We consider the solver successful if its proportion error stays within a comparable relative gap of the centralized optimum, while scaling past the point where the centralized run exhausts memory.
Why not just…?
Why not just run per-spot deconvolution in parallel, since it is already linear? This is the most serious threat. If neighbours carry little information beyond each spot's own counts, coupling buys nothing. We expect coupling to matter most where counts are low, as in sub-cellular bins and sparse Slide-seqV2 beads, and least on deep Visium spots. The count-subsampling experiment measures exactly this crossover. If the independent baseline matches us at every depth, the scalability argument collapses to "parallelize RCTD," and we would report that.
Why not just smooth independent estimates afterwards with an edge-aware filter? A bilateral or graph filter applied to per-spot proportions is cheap, linear and boundary-aware. It is also a genuine competitor. The difference is that our coupling enters the likelihood. A spot whose counts strongly identify its mixture resists its neighbours, while an uncertain spot borrows from them, and the result comes with an uncertainty that reflects both. We include a tuned bilateral post-smoother as a baseline. If it matches us on accuracy and boundary leakage, the remaining argument rests only on calibrated intervals and must be judged on coverage.
Why not just tile the slide and run Cell2location or CARD per tile on a larger GPU? The benchmark already flags Cell2location as memory-heavy on large grids. Tiling also cuts neighbour edges at tile borders, so spatially coupled methods lose context exactly at seams. We will run the tiled versions and measure error as a function of distance to the nearest seam. Our regional-consensus design should show no seam effect. Tiled methods should show one if the coupling they lose actually mattered.
Why not just use GraphST/DeepST, which already treat spots as a graph? Their smoothing is homophilous by design and operates on embeddings, and their own discussion points to scaling limits on sub-cellular platforms. The boundary-band analysis on DLPFC and HER2+ breast slides, together with the scaling curve, compares us to them directly.
Proposed Experiments
Ground-truth accuracy. We use pseudo-spots built by aggregating single cells from the mouse VISp STARmap dataset (as in POLARIS), where true proportions are known, together with simulated slides following the protocol of the 50-dataset benchmark. Metrics are per-spot root-mean-square error and Jensen–Shannon divergence on proportions, reported separately for interior and boundary bands. The same data give uncertainty calibration: the empirical coverage of nominal 50% and 90% intervals, which also tests whether the logistic-normal approximation is adequate for rare cell types.
Real tissue without ground-truth proportions. We use human DLPFC and HER2+ breast cancer Visium data. On DLPFC we measure whether layer-marker cell types stay confined to their annotated layers, focusing on thin Layer 4. On breast tissue we check whether exhausted T-cell signal localizes as GraphST reported, using LAG3 and PDCD1 as independent markers.
Confounding test. In simulations with composition gradients but no planted cell-intrinsic layer shift, we count the false layer-specific genes a POLARIS-style test calls downstream of each method's proportions. This is the direct measure of composition masquerading as regulation.
Scaling. We use the 100,000-spot mouse embryo Stereo-seq slide and synthetic slides up to about 5 million spots, reporting wall-clock time, peak memory per worker, iterations to convergence, and the gap to the centralized optimum where it still fits in memory.
Decisive checks. Three results would decide the proposal:
- The robust-coupled solver beats both the independent and the quadratic-coupled ablations in boundary-band error at low count depth.
- It cuts downstream false layer-specific genes relative to every baseline.
- It holds near-nominal interval coverage while runtime grows linearly.
If the bilateral post-smoother or the independent baseline closes these gaps, we will report that the multi-agent formulation adds scalability bookkeeping but not inferential value.
References
- Distributed Simultaneous Localisation and Auto-Calibration Using Gaussian Belief Propagation
- Spatially informed clustering, integration, and deconvolution of spatial transcriptomics with GraphST
- DeepST: A versatile graph contrastive learning framework for spatially informed clustering, integration, and deconvolution of spatial transcriptomics
- Cell composition inference and identification of layer-specific spatial transcriptional profiles with POLARIS
- A comprehensive benchmarking with practical guidelines for cellular deconvolution of spatial transcriptomics
- NNICE: a deep quantile neural network algorithm for expression deconvolution
- EGO-Swarm: A Fully Autonomous and Decentralized Quadrotor Swarm System in Cluttered Environments
- Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning
- DoF: A Diffusion Factorization Framework for Offline Multi-Agent Reinforcement Learning
- CellAgent: LLM-Driven Multi-Agent Framework for Natural Language-Based Single-Cell Analysis
- PhenoGraph: A Multi-Agent Framework for Phenotype-driven Discovery in Spatial Transcriptomics Data Augmented with Knowledge Graphs
- Decentralized iLQR for Cooperative Trajectory Planning of Connected Autonomous Vehicles via Dual Consensus ADMM