Many powerful frameworks in machine learning and computational physics rely on a simple, elegant representation: modeling complex systems as a collection of discrete, moving points known as particles.
In Bayesian inference, particle-based variational methods use a swarm of samples to map out intricate, multimodal probability distributions without forcing them into rigid parametric shapes. In physics and biology, particles represent everything from stars in a galaxy to red blood cells navigating a capillary.
The core appeal of these methods is their flexibility. However, they share a devastating computational flaw: quadratic interaction complexity. For a particle system to behave correctly, every particle must typically communicate with every other particle. This all-to-all interaction requirement creates a severe scaling wall that researchers across disciplines are actively working to dismantle.
The All-to-All Scaling Wall
To understand why the bottleneck occurs, consider how particles interact.
In physical simulations, particles exert long-range forces (like gravity or electrostatic attraction) on one another. In Bayesian sampling methods like Stein Variational Gradient Descent (SVGD), particles use a kernel function to calculate a repulsive force between all pairs, which ensures the particles spread out uniformly to capture the full target distribution rather than collapsing into a single point.
Mathematically, computing these interactions requires evaluating every unique pair in the system. For $N$ particles, this means performing $O(N^2)$ operations per time step.
Standard All-to-All Interaction: O(N²)
[Particle i] <========================> [Particle j]
(Every single pair must explicitly compute an interaction)
This quadratic scaling creates an immediate barrier to fidelity. If you double the number of particles to achieve a higher-resolution simulation or a more accurate posterior approximation, the computational cost quadruples.
As highlighted by Dong et al. and Sharrock et al., this bottleneck severely restricts the use of large particle swarms in high-dimensional spaces. For instance, Lambert et al. note that in robotic control loops, the $O(N^2)$ cost limits the number of trajectories a model predictive control system can evaluate within strict real-time constraints, forcing a compromise between planning accuracy and speed.
Breaking the Bottleneck via Spatial Hierarchies
How do we bypass this quadratic tax? The foundational intuition comes from classical physics: distant interactions do not need to be computed with perfect precision.
If you are calculating the gravitational pull of a distant galaxy on Earth, you do not compute the individual pull of each of its billions of stars. Instead, you treat the entire galaxy as a single collective mass located at its center of gravity.
This is the core principle behind the Fast Multipole Method (FMM). By organizing particles into a hierarchical tree structure (such as an octree), algorithms can group distant clusters of particles together.
Hierarchical Interaction (FMM): O(N log N) or O(N)
[Particle i] ----> [Local Neighbors (Explicit)]
----> [Distant Cluster (Aggregated Multipole)]
Instead of calculating $O(N^2)$ pairwise interactions, an element interacts directly and precisely with its immediate neighbors, but interacts with distant clusters via a single aggregated "multipole" expansion. This shifts the computational complexity from $O(N^2)$ down to $O(N \log N)$ or even $O(N)$.
As explored by Ghigliotti et al. and Agarwal et al. in fluid dynamics, achieving linear scaling is a prerequisite for moving beyond single-particle models to simulate the intricate, large-scale collective behaviors of concentrated cell suspensions or deformable capsules in blood flow. Similarly, Blackwell demonstrated that strategic kernel aggregation within these tree structures allows simulations to handle complex boundary conditions efficiently without incurring prohibitive costs.
Amortization and Functional Flows
While spatial hierarchies work beautifully for physical particles in three-dimensional space, they struggle in the high-dimensional spaces typical of machine learning posteriors, where the "curse of dimensionality" breaks traditional tree structures. To solve the quadratic bottleneck in inference, researchers have turned to functional and neural approximations.
Instead of calculating explicit pairwise kernel interactions at every single optimization step, the core idea here is to amortize the cost by training a neural network to learn the underlying continuous vector field or gradient flow that governs the particles.
Pairwise Kernels: [Particle] <--- O(N²) Matrix ---> [Particle]
Functional Flow: [Particle] ----> [Neural Network] ----> [Update Vector]
For example, Dong et al. introduced Preconditioned Functional Gradient Flow (PFG), which replaces traditional Reproducing Kernel Hilbert Space (RKHS) constraints with a functional regularization estimated via neural networks. This completely bypasses the $O(N^2)$ kernel matrix, achieving true $O(N)$ scaling and enabling provable linear convergence.
In a similar vein, Martinkus et al. designed hierarchical graph networks that explicitly mimic the logic of classical FMMs. By embedding this hierarchical clustering directly into a graph neural network architecture, the authors enabled models to learn long-range particle dynamics with $O(N)$ complexity, unlocking high-fidelity physical predictions for thousands of particles on a single GPU.
A Shared Path Forward
The transition from $O(N^2)$ to linear or near-linear scaling represents a profound paradigm shift across both physics and machine learning. Whether through the geometric clustering of FMMs or the functional amortization of deep neural networks, overcoming the all-to-all interaction bottleneck allows us to scale particle counts to the levels required for high-fidelity physical simulations, complex multi-agent coordination, and robust Bayesian uncertainty quantification.
Key Foundational Work
Fast multipole methods on graphics processors (2008) — contributed 1 concept elements to this direction.
A kernel-independent adaptive fast multipole algorithm in two and three dimensions (2004) — contributed 1 concept elements to this direction.