LSH-SMILE: Locality Sensitive Hashing Accelerated Simulation and Learning

Chonghao Sima, Yexiang XueNeurIPS 2021 · OpenReview

Scientific discovery is increasingly driven by machine learning, specifically by learning Partial Differential Equations (PDEs) directly from experimental data. However, simulating or learning the physics of a complex system—like fluid flowing through a pipe or grains growing in a metal alloy—presents a massive computational bottleneck.

To model these systems, researchers typically use "finite difference" methods, breaking the environment down into billions of tiny elements. In a standard brute-force approach, every single element is updated at every time step. This method is incredibly slow and memory-intensive, especially for "backward learning," where a model must run thousands of simulations to reverse-engineer the underlying physical laws.

Presented at NeurIPS 2021, LSH-SMILE (Locality Sensitive Hashing Accelerated Simulation and Learning) introduces a clever way to bypass this "curse of scale." By grouping similar elements together using a classic computer science tool, LSH-SMILE slashes simulation time by up to 95% and enables the discovery of complex physics models that were previously too computationally expensive to learn.

The Core Method: Hashing Physics Updates

The authors noticed a missed opportunity in standard simulations: in many physical systems, most elements aren't doing anything unique. Large chunks of material stay the same, while the interesting physics only happens at the boundaries. LSH-SMILE treats these physics updates as a grouping problem rather than a massive matrix math problem.

  1. Vector Representation: Each element in the simulation is represented as a vector containing its own value and the values of its immediate neighbors.
Local updates in nanovoid simulation
  1. Locality Sensitive Hashing (LSH): Instead of using LSH for finding nearest neighbors in a database, the authors use it to hash elements into buckets. Elements with similar local neighborhoods—and therefore similar future trajectories—end up in the same bucket.
  2. Bulk Updates: Instead of calculating the next state for every element, LSH-SMILE calculates the update for one representative element per bucket and applies it to all elements in that bucket simultaneously.
  3. Dynamic Re-hashing: Because physics is dynamic, local "neighborhoods" change over time. The algorithm monitors the change in values; if an element's value shifts beyond a certain threshold, it is re-hashed into a new bucket.

This shifts the computational complexity from being proportional to the total number of elements to being proportional to the number of non-empty hash buckets.

Key Insights: Sparsity and Temporal Redundancy

The efficiency of LSH-SMILE relies heavily on the sparsity of action. In many systems, significant updates occur in less than 1% of the total area (the "interfaces").

Phase field simulation showing sparsity of action and hash bucket distribution

As seen in phase field simulations, LSH-SMILE naturally focuses its computational power on these active boundary regions. Elements that look the same locally will behave the same way over short time intervals. By "bulk-updating" these elements, the algorithm avoids redundant calculations.

Furthermore, the authors proved a novel error bound, showing that the approximation error is strictly controlled by the size of the hash buckets, ensuring the simulation remains physically accurate.

Experimental Results

The researchers evaluated LSH-SMILE on complex nano-physics phenomena, including microscopic grain growth and nanovoid evolution in materials subjected to high temperatures.

  • Massive Speedups: Compared to a standard PyTorch implementation, LSH-SMILE was 70% faster for grain growth simulations and 95% faster for nanovoid simulations.
  • High Precision: Despite being an approximation, the error relative to the exact brute-force method was as low as $10^{-5}$ after 100 simulation steps.
  • Enabling "Deeper" Learning: In backward learning, models must simulate the system forward to see if guessed physics parameters match reality. Because LSH-SMILE is so fast, it allows the learning process to simulate 30 time steps into the future instead of just 10. This provided a much stronger signal for the optimizer, allowing LSH-SMILE to successfully identify hidden physics constants that the brute-force baseline failed to find.

Limitations and Future Work

The primary limitation of LSH-SMILE is its reliance on the "clustering assumption." The system must have many elements that behave similarly. In a highly chaotic or turbulent system where every point is unique, the number of buckets would equal the number of elements, neutralizing the speedup. Additionally, users must carefully tune hyperparameters like bucket size and re-hashing thresholds to balance speed and accuracy.

Moving forward, the authors suggest applying this framework to other domains like fluid dynamics, heat transfer, and crack formation, where interface dynamics are the primary focus and computational bottlenecks remain a significant hurdle.

Summary updated

Abstract

The advancement of deep neural networks over the last decade has enabled progress in scientific knowledge discovery in the form of learning Partial Differential Equations (PDEs) directly from experiment data. Nevertheless, forward simulation and backward learning of large-scale dynamic systems require handling billions of mutually interacting elements, the scale of which overwhelms current computing architectures. We propose Locality Sensitive Hashing Accelerated Simulation and Learning (LSH-SMILE), a unified framework to scale up both forward simulation and backward learning of physics systems. LSH-SMILE takes advantage of (i) the locality of PDE updates, (ii) similar temporal dynamics shared by multiple elements. LSH-SMILE hashes elements with similar dynamics into a single hash bucket and handles their updates at once. This allows LSH-SMILE to scale with respect to the number of non-empty hash buckets, a drastic improvement over conventional approaches. Theoretically, we prove a novel bound on the errors introduced by LSH-SMILE. Experimentally, we demonstrate that LSH-SMILE simulates physics systems at comparable quality with exact approaches, but with way less time and space complexity. Such savings also translate to better learning performance due to LSH-SMILE's ability to propagate gradients over a long duration.
BibTeX
@inproceedings{sima2021lsh,
  author = {Chonghao Sima and Yexiang Xue},
  title = {{LSH-SMILE: Locality Sensitive Hashing Accelerated Simulation and Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=Pf9RjFoUdLZ},
}
Figure