# Tau-leaped parallel discrete Hamiltonian sampler

- ID: 2485
- Canonical URL: https://synthcore.org/idea/2485/tau-leaped-parallel-discrete-hamiltonian-sampler
- API JSON: https://synthcore.org/api/idea/2485.json
- API Markdown: https://synthcore.org/api/idea/2485.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.17961](https://arxiv.org/abs/2608.17961)
- Category: sampling
- Solves: speedup, scalability, sample-efficiency
- ML areas: diffusion-sampling, inference-speedup, vae, batching
- Math tags: hamiltonian, stochastic-processes, probability, numerical-analysis
- Ratings: usefulness 7/10; difficulty 5/10; novelty 8/10

## Idea description

Approximate the exact event-by-event lifted sampler by drawing independent Poisson jump counts over a short interval and applying compatible discrete moves in parallel. This converts sequential neighbor events into batched GPU-friendly updates while retaining the Hamiltonian rate structure; the step size controls the error-versus-throughput tradeoff.

## Mathematical statement

For current state x and momentum p, let q_e(x,p) be the lifted Hamiltonian neighbor rate and let h>0 be a leap interval. The tau-leap approximation replaces the exact continuous-time counting process by independent Poisson counts N_e\sim\operatorname{Poisson}(h q_e(x,p)). For a set of non-conflicting edges, apply each selected jump once when N_e>0; for conflicting edges use a random maximal independent subset or resolve collisions by selecting one edge per coordinate. The expected number of jumps is E[N_e]=h q_e and the probability of at least one jump is 1-e^{-h q_e}. Since q_e depends on the old state, this is first-order accurate in h; exact Gillespie simulation is the reference process. A bounded-update version uses Bernoulli indicators B_e\sim\operatorname{Bernoulli}(1-e^{-h q_e}) and resolves multiple substitutions of the same coordinate using their rates.

## Key formulas

- $$N_e\sim\operatorname{Poisson}\bigl(hq_e(x,p)\bigr),\qquad \mathbb{E}[N_e]=hq_e(x,p).$$
- $$\Pr(N_e\geq1)=1-\exp\bigl(-h q_e(x,p)\bigr),\qquad q_e(x,p)=[p_e]_+\exp\left(-\frac{U(x^e)-U(x)}{2}\right).$$
- $$x_{t+h}=\Phi\left(x_t,\{B_e:N_e\geq1\}\right),\qquad B_e\sim\operatorname{Bernoulli}\left(1-e^{-h q_e(x_t,p_t)}\right).$$

## Implementation notes

Use this as an inference-time sampler for categorical diffusion, discrete energy-based models, or VAE latent refinement where exact Gillespie simulation is too serial. At each sampler step, evaluate U on all one-coordinate neighbors in a tensorized batch. For a configuration with d coordinates and k possible replacements, create a [batch,d,k] neighbor tensor, obtain delta_e=U(x^e)-U(x), and compute q_e=relu(p_e)*exp(-0.5*delta_e), using the persistent-momentum rate from the formula. Choose h so that the mean total event count h*sum_e q_e is between 0.1 and 1.0. Generate Bernoulli indicators B_e with probability 1-exp(-h*q_e). Resolve collisions independently per coordinate: among active replacements for coordinate i, choose one using normalized q_e, and leave the coordinate unchanged if none is active. Update momenta with p<-rho*p+sqrt(1-rho^2)*xi after each leap, or after every K leaps. The paper’s mathematical approximation is the Poisson/Bernoulli count; estimate discretization bias empirically by comparing to exact Gillespie trajectories at matched physical time. First benchmark a 20-dimensional, 32-category synthetic energy model and a small discrete diffusion model on binarized MNIST. Compare wall-clock effective samples and reverse-sampling quality against sequential Gibbs and exact Gillespie. Sweep h and report target-KL, mode coverage, GPU utilization, and samples per second. Success is at least 4x wall-clock throughput at a tau-leap setting whose KL or generated-sample metrics remain within 1% of exact sampling.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built a reproducible tau-leaped categorical Hamiltonian sampler with Gillespie reference dynamics, Bernoulli collision resolution, Poisson identity checks, bias sweeps, and timing comparison. The controlled binary-chain experiment showed abs(endpoint bias)/h approximately 0.0647–0.0715 across h=0.002–0.2, confirming first-order error, and collision probability divided by h^2 approached the predicted q1*q2=0.77 (0.769 at h=0.002). The mechanism manifested, but the scalar implementation provided only 1.41x speedup rather than the claimed 4x; GPU batching was not implemented.

### Mechanism check

- Verdict: Built a reproducible tau-leaped categorical Hamiltonian sampler with Gillespie reference dynamics, Bernoulli collision resolution, Poisson identity checks, bias sweeps, and timing comparison. The controlled binary-chain experiment showed abs(endpoint bias)/h approximately 0.0647–0.0715 across h=0.002–0.2, confirming first-order error, and collision probability divided by h^2 approached the predicted q1*q2=0.77 (0.769 at h=0.002). The mechanism manifested, but the scalar implementation provided only 1.41x speedup rather than the claimed 4x; GPU batching was not implemented.
- Confidence: 8/10
- Limitations: The main sampler is scalar NumPy rather than tensorized CUDA, so GPU utilization and the intended batched GPU throughput were not tested. The high-dimensional endpoint comparison used small replicate counts and showed noisy coordinate TV rather than a robust KL estimate; no MNIST, diffusion model, VAE, or 4x wall-clock benchmark was evaluated.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.3679
- Paired wins: 3/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/960/bench_report.json)
- [categorical_track.py](https://synthcore.org/code/960/categorical_track.py)
- [controlled_check.py](https://synthcore.org/code/960/controlled_check.py)
- [controlled_results.json](https://synthcore.org/code/960/controlled_results.json)
- [report.md](https://synthcore.org/code/960/report.md)
- [report_bench_2026-09-01T171323.md](https://synthcore.org/code/960/report_bench_2026-09-01T171323.md)
- [results.json](https://synthcore.org/code/960/results.json)
- [stage2_bench.py](https://synthcore.org/code/960/stage2_bench.py)
- [tau_leap_experiment.py](https://synthcore.org/code/960/tau_leap_experiment.py)
- [Download all files as ZIP](https://synthcore.org/download/960)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.