Hypergraph Rewriting Engine

A high-performance multiway hypergraph rewriting engine for the Wolfram Physics Project.

Status

v1.0.0-rc3: feature-complete, gated by CI, model checking and a brute-force oracle. APIs are stable from this release line onward.

Paper

The system, its algorithms, the full evaluation and the verification are described in the technical report Rewriting the Universe: High-Performance Hypergraph Rewriting for the Wolfram Physics Project. To cite it:

@techreport{assar2026rewriting,
    author      = {Assar, Richard},
    title       = {Rewriting the Universe: High-Performance Hypergraph Rewriting
                   for the Wolfram Physics Project},
    institution = {Wolfram Institute},
    year        = {2026},
    url         = {https://github.com/WolframInstitute/HypergraphRewritingEngine/blob/master/paper/main.pdf}
}

Background

• Stephen Wolfram, Finally We May Have a Path to the Fundamental Theory of Physics — and It's Beautiful (2020)
• The Wolfram Physics Project, and its technical introduction

Features

• Multiway Evolution: Parallel state evolution with causal and branchial graph construction, single synchronisation point (no intra-evolution phase barriers, online transitive reduction).
• Exact Canonicalization: McKay-style individualisation--refinement (IR) computes an exact canonical hash for every state; deduplication is isomorphism-correct, never heuristic. A content-ordered hash (Automatic) and no-dedup (None) modes exist for workloads that want them.
• Determinism Contract: the state set, event set and causal/branchial relations are a function of the inputs alone — independent of thread count and scheduling.
• Quotient Exploration: expand one representative per isomorphism class and reconstruct the raw events, causal edges and branchial pairs exactly.
• GPU Backend: CUDA port mirroring the CPU algorithms, with a resident evolution kernel (states re-enter as match tasks without returning to the host) and warp-collective canonicalization sharing the same IR implementation as the CPU.
• Parallel Pattern Matching: match-by-hyperedge join with signature-partitioned candidates and work-stealing scheduling.
• Incremental Match Forwarding: re-use parent-state matches in child states; only find new matches that involve newly produced edges (selected per rule set by static analysis).
• Lock-free Data Structures: concurrent hash map, key set, lock-free list, lock-free deque, thread-safe arena — the shared protocols model-checked under RC11/scoped-RC11 (GenMC, GPUMC) and TLA+ at their recorded bounds, sanitizer-gated in CI.
• Cost-Guided Evolution: a beam search over the multiway system. "StateCost" takes a function of a state's statistics, and with "MaxStatesPerStep" -> N each step keeps its N successor states of lowest cost, on the CPU and the GPU, with the same states at any thread count and on either device. "TransitionCost" costs a transition by the heat residual of a vertex field from parent to child, "BeamCost" -> "Path" ranks by path cost, and "Search" -> "BestFirst" takes the transition of lowest path cost one at a time on the CPU (docs/TRANSITION_COST.md).
• Single Histories: "Generational" -> True applies one generation of the Wolfram model per step (the matches in the standard order, each unless it shares a hyperedge with one taken before), "EventOrderingFunction" takes SetReplace's event orderings, and "MatchesPerStep" -> 1 with "UniformRandom" -> True applies one match per step drawn from "RandomSeed".
• Undirected Edges: "UndirectedEdges" -> True reads every hyperedge of two vertices as an unordered pair, in matching and in the canonical hash.
• Memory Limit: "Tuning" -> <|"MemoryLimit" -> bytes|> (default half of physical memory). An evolution that reaches it stops and returns a partial result with HGEvolve::overflow.
• Initial Conditions: the engine generates the named initial conditions (grids, cylinders, tori, spheres, Klein bottles, Möbius strips, Minkowski sprinklings, Poisson-disk and uniform point sets, and Brill-Lindquist points in two or three dimensions, optionally in a periodic box) in C++, for the paclet and the Python package. The "InitialCondition" property returns the edges and, for a point set, the points.
• GPU Fallback: "TargetDevice" -> "GPU" on a machine with no usable NVIDIA GPU runs on the CPU with HGEvolve::gpudev, which names the reason.
• Python Client: the hgevolve package (python/) runs the CPU engine in-process with HGEvolve's options and returns NumPy arrays.
• Mathematica Paclet: HGEvolve and the session functions, which run the engine in a worker process (hg_evolve --serve, over its standard input and output) and return the states, events, causal and branchial graphs, per-step statistics ("StepStatistics") with dimension, curvature, geodesic and branchial measures, and generated initial conditions.

Installation

Mathematica Paclet

Install the paclet from the GitHub release. rc1, rc2 and rc3 all carry paclet version 1.0.0, so uninstall an earlier release candidate first if one is installed (PacletUninstall["WolframInstitute/HypergraphRewriteEngine"]).

PacletInstall["https://github.com/WolframInstitute/HypergraphRewritingEngine/releases/download/v1.0.0-rc3/WolframInstitute__HypergraphRewriteEngine-1.0.0.paclet"]
Needs["HypergraphRewriting`"]

The paclet is not in the Wolfram Paclet Repository, so PacletInstall["WolframInstitute/HypergraphRewriteEngine"] does not install it. PacletFind["WolframInstitute/HypergraphRewriteEngine"] lists the installed versions; Needs loads the highest.

The paclet name is WolframInstitute/HypergraphRewriteEngine; its exported context is HypergraphRewriting` .

Building from Source

mkdir build_linux && cd build_linux
cmake .. -DBUILD_WOLFRAM_LANGUAGE_PACLET=ON
make -j32 paclet

Usage

Mathematica

Needs["HypergraphRewriting`"]

(* Rules use symbolic vertices (normalised to numeric internally). *)
rule = {{x, y}, {y, z}} -> {{x, y}, {y, z}, {z, x}};
init = {{1, 2}, {2, 3}, {3, 1}};

(* HGEvolve[rules, initialEdges, steps, property]. Passing a single rule is
   supported; a list of rules is also supported. *)
result = HGEvolve[rule, init, 5, "All"];

(* "All" returns an Association with these keys: *)
result["NumStates"]      (* integer: number of states *)
result["NumEvents"]      (* integer: number of events *)
result["States"]         (* association of state id -> state record *)
result["Events"]         (* association of event id -> event record *)
result["CausalEdges"]    (* list of records: producer and consumer event of each pair *)
result["BranchialEdges"] (* event pairs that share an input state AND consume a
                            common edge -- two events out of one state that
                            consume disjoint edges are not branchially adjacent *)

(* Graph properties evaluate directly to Graph objects: *)
HGEvolve[rule, init, 5, "StatesGraph"]
HGEvolve[rule, init, 5, "CausalGraph"]
HGEvolve[rule, init, 5, "BranchialGraph"]
HGEvolve[rule, init, 5, "EvolutionCausalBranchialGraph"]

(* Cost-guided evolution: each step keeps the 4 successor states whose ball dimension is
   closest to 2. *)
HGEvolve[rule, init, 10, "StepStatistics", "CanonicalizeStates" -> Full,
  "MaxStatesPerStep" -> 4, "StateCost" -> (Abs[#BallDimension - 2] &),
  "StepStatisticsMeasures" -> {"VolumeGrowth"}]

(* A single history of 10 generations, under a 2 GB memory limit. *)
HGEvolve[rule, init, 10, "NumEvents", "CanonicalizeStates" -> None, "Generational" -> True,
  "Tuning" -> <|"MemoryLimit" -> 2^31|>]

Python

import hgevolve as hg
r = hg.evolve(([[1, 2], [2, 3]], [[1, 2], [2, 3], [3, 1]]), [[1, 2], [2, 3], [3, 1]], 3)
r.num_states, r.causal_edges.array

python/README.md describes the installation, and python/docs/API.md the functions and options.

The reference page docs/en/ReferencePages/Symbols/HGEvolve.md lists every option and property.

C++ API

#include <hypergraph/parallel_evolution.hpp>
#include <hypergraph/hypergraph.hpp>

using namespace hypergraph;

int main() {
    Hypergraph hg;
    ParallelEvolutionEngine engine(&hg, 4);  // 4 threads

    // Rule: {x,y},{y,z} -> {x,y},{y,z},{z,x}
    auto rule = make_rule(0)
        .lhs({0, 1}).lhs({1, 2})
        .rhs({0, 1}).rhs({1, 2}).rhs({2, 0})
        .build();

    engine.add_rule(rule);

    std::vector<std::vector<VertexId>> initial = {{1, 2}, {2, 3}, {3, 1}};
    engine.evolve(initial, 5);

    std::cout << "States: " << hg.num_states() << "\n";
    std::cout << "Events: " << hg.num_events() << "\n";
}

Supported Platforms

The paclet includes native libraries for:

Platform	Architecture
Linux	x86-64, ARM64
Windows	x86-64, ARM64
macOS	x86-64 (Intel), ARM64 (Apple Silicon)

Build Requirements

• C++20 compiler (GCC 10+, Clang 12+)
• CMake 3.14+
• Google Test (automatically downloaded)
• Mathematica 13+ (optional, for paclet); the paclet is tested on 14.1 and 15.0

Cross-Compilation

Build every shipped artifact from Linux (six platform libraries and binaries, plus the CUDA executables where a toolchain is present):

./build_all_platforms.sh

Required packages (Ubuntu/Debian):

sudo apt install \
    cmake build-essential \
    gcc-aarch64-linux-gnu g++-aarch64-linux-gnu \
    gcc-mingw-w64-x86-64 g++-mingw-w64-x86-64 \
    clang lld

Target	Toolchain
Linux ARM64	gcc-aarch64-linux-gnu
Windows x86-64	MinGW-w64
Windows ARM64	Clang + LLD
macOS	OSXCross

See CROSS_COMPILATION.md for detailed setup.

Project Structure

hypergraph/     Core CPU engine: evolution, matching, IR canonicalization, storage
gpu/            CUDA port (optional, BUILD_GPU=ON), mirrors the CPU algorithms
job_system/     Work-stealing task scheduler the engine runs on
lockfree_deque/ Lock-free concurrent deque backing the scheduler
common/         Shared CPU/GPU rules: the IR canonicalization core, join, quotient DP,
                ring/termination/pool protocols, portable intrinsics
wxf/            Wolfram Exchange Format serialization (the WL boundary)

paclet/         Wolfram Language paclet (kernel code, bundled binaries, doc notebooks)
paclet_source/  FFI: run_rewriting_core, the standalone hg_evolve binary, GPU marshaling
python/         The hgevolve Python client (in-process CPU engine, NumPy replies)
reference/      Validation oracle (brute-force ground truth) + golden corpus
verification/   GenMC and GPUMC model-checking harnesses, TLA+ specifications
tools/          Standalone research/validation probes and profiling harnesses
testing/        Aggregate C++ test target (all_tests)
benchmarks/     Per-area benchmarks;  benchmarking/  is the framework library
visualisation/  Viz-event interface (the renderer lives in its own repository)

docs/           Specification, architecture, code map, quickstart; docs/en/ the paclet documentation sources
paper/          The technical report (LaTeX; tables generated by tools/dev)
examples/       Small C++ usage examples
cmake/          Cross-compilation toolchain files

New here? Users: docs/QUICKSTART.md. Developers: docs/ARCHITECTURE.md.

The paclet's documentation, the reference pages of HGEvolve and the session functions, a guide and seven tutorials, opens in the Wolfram Documentation Center once the paclet is installed; its sources are in docs/en/, and CONTRIBUTING.md describes how they are built and checked.

Testing

cd build_linux
./all_tests              # All tests
./core_tests             # Core functionality
./evolution_tests        # Evolution and pattern matching
./causal_tests           # Causal/branchial graph
ctest                    # Registers all_tests (the subset targets are direct-run only)

License

MIT — see LICENSE.md. The paclet declares the same in its PacletInfo.wl.