Programmable Probabilistic Computer with 1,000,000 p-bits
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Programmable Probabilistic Computer with 1,000,000 p-bits".
Paper summary: Tom: So we’re looking at this paper today, "Programmable Probabilistic Computer with one million p-bits <ref:2606.25313#pg1,Programmable Probabilistic Computer with 1,000,000 p-bits>." Basically it says we can take these probabilistic computers that are usually stuck on a single chip because of memory limits and make something huge.
Jane: That sounds ambitious. So what’s the main idea here? What is this paper actually claiming about what they built?
Tom: They’re proposing a way to network FPGAs together into one massive Ising machine. They claim this setup realizes a programmable probabilistic computer with one million p-bits, which is far bigger than any single device can handle.
Lu: It’s not just about making it bigger; they are tackling the fundamental question of how to make a partitioned machine behave like one big machine again. They introduce this key dimensionless parameter, eta equals fcomm divided by fp-bit, and how that ratio controls the performance.
Meng: So if I understand right, this whole system is designed for Gibbs sampling at over a trillion flips per second while keeping all those coupling weights in local on-chip memory across the network. What does that mean for deployment?
Lalam: It means they are doing the heavy lifting locally, and only sending small boundary information across devices. The core mechanism involves duplicating cut-edge weights as shadow weights on both sides of each partition so only one bit crosses a device boundary at a time <ref:2606.25313#pg2>.
Tom: That sounds like they’re trying to minimize the communication overhead. But what is the practical catch when you distribute computation like that? How does it actually perform compared to just running it on one big machine?
Jane: The paper explores a tradeoff here, showing that performance depends entirely on this timing ratio, eta equals fcomm divided by fp-bit. If eta is above some threshold, the distributed machine acts exactly like a single monolithic device.
Lu: Below that threshold, the residual energy still decays as a power law but with a reduced exponent. It turns parallelism into something you can measure as throughput versus accuracy <ref:2606.25313#pg3>.
Meng: A tradeoff? That’s what I care about when I’m thinking about running models in production. So, if eta is low, we get less quality for the effort of parallelizing it across FPGAs. How does that translate to actual cost?
Lalam: They define a communication-cost metric called Cmax which identifies the tightest bottleneck created by the physical interconnect when you actually place this design on hardware <ref:2606.25313#pg3>. This bounds the local update clock given by fp-bit less than fcomm squared times Ncolor <ref:2606.25313#pg3>.
Tom: Okay, so we have the ideal theoretical setup, but now we have physical constraints like interconnects and topology. How do they handle that in practice?
Jane: They use a topology-aware Potts partitioning strategy to help manage this cost <ref:2606.25313#pg2>. This function penalizes placing strongly connected partitions on devices that are far apart, which helps concentrate the cut edges at short hop distances.
Paper summary: Lu: That strategy avoids having to search through all possible partition orderings explicitly by aligning the partition with the existing chain topology to minimize worst-path congestion <ref:2606.25313#pg2>. Plus, they confirmed that testing with disconnected links showed that any slope loss comes from those boundary exchanges rather than problems with the local updates themselves.
Meng: So it seems like they solved the partitioning problem by letting the topology guide where we put the partitions, minimizing traffic jams on long wires. But what about the actual results? Did they prove this is good?
Lalam: They validated their findings on three dee Edwards–Anderson spin glasses <ref:2606.25313#pg3>. The optimization quality of a distributed run depends only on that eta ratio, not on how fast you run the clock or how slow you run the local updates individually <ref:2606.25313#pg3>.
Tom: That’s interesting because it means we don't need to tune the clock and the update speed separately as much as we thought. The fitted curves from their hardware implementations and cluster mean-field theory models collapse onto the same functional form after rescaling <ref:2606.25313#pg3>.
Jane: That collapse really confirms what they’re saying, which is that the main thing shaping this distributed system is indeed that delayed boundary information in partitioned stochastic dynamics <ref:2606.25313#pg3>. It shows the system isn't just random noise; it follows a predictable pattern related to how often those boundaries are refreshed relative to the local updates.
Lu: What this implies for distributed sampling is that we have a universal rule for quality control across different graph structures and hardware layouts, as long as you respect that eta ratio <ref:2606.25313#pg3>.
Meng: From a production standpoint, if I were deploying this idea, I’d focus on figuring out the Cmax metric to see where the biggest traffic bottlenecks are going to be when we map our specific graph onto the physical interconnect <ref:2606.25313#pg3>. That seems like a concrete first step for me.
Lalam: It means that for any graph, if you can manage those boundary exchanges efficiently according to the eta ratio, the scaling quality remains predictable regardless of how big the machine gets <ref:2606.25313#pg3>.
Tom: So we’re moving from just hoping it works on a big chip to having a principled way—using eta—to predict if our distributed setup will actually achieve the performance we need <ref:2606.25313#pg1>. That’s a step in the right direction for hardware acceleration.
Jane: It sounds like they took an abstract concept about scaling and turned it into a measurable engineering constraint that any distributed sampler needs to address <ref:2606.25313#pg2>.
Lu: And the paper addresses the practical issue of stale boundary information, which is a huge hurdle in distributed systems where you have to rely on neighboring partitions <ref:2606.25313#pg3>.
Meng: I just hope this doesn't introduce new complexities in the software layer for managing those boundary exchanges <ref:2606.25313#pg1>. Because if the communication management becomes too hard, the whole promise of scaling vanishes <ref:2606.25313#pg4>.
Lalam: Based on what’s written in this paper, they are quite confident that by managing that single timing ratio correctly, you get a solid performance guarantee for any topology you throw at it <ref:2606.25313#pg1>.
Conclusion: Tom: So we’re wrapping up our look at this paper on the programmable probabilistic computer with one million p-bits and what it means for scaling up these types of simulations.
Jane: The authors are showing how you can take these probabilistic computers, which are usually stuck on a single chip because of memory limits, and network them together into something much bigger.
Tom: It’s about using FPGAs to build one massive Ising machine that can do Gibbs sampling at over a trillion flips per second while keeping all the coupling weights local.
Lu: They introduce this idea of how often you have to refresh boundary information when you partition the machine, which they call eta equals fcomm divided by fp-bit.
Meng: That ratio basically tells you if your distributed setup is acting like one big machine or if it’s starting to break down because of communication lag.
Lalam: The key result is that performance only depends on that timing ratio, not how fast you run the clock or how slow your local updates are, as long as you respect eta.
Jane: So what does this mean for someone who just wants to understand the big picture? It suggests we have a universal rule for quality control in these distributed sampling systems based on that one ratio.
Tom: Exactly. They show that whether you’re running on a small setup or this million-bit machine, the scaling quality is determined by how well you manage those boundary exchanges.
Lu: It’s about taking an abstract idea and turning it into a concrete engineering constraint for building any distributed sampler.
Meng: If we can figure out that communication cost metric called Cmax, we can start predicting where the physical bottlenecks will be when we map our specific problem onto actual hardware.
Jane: That seems like a solid next step, moving from theory to figuring out the real-world cost of deployment across different physical layouts.
Navid Anjum Aadit, *Xiuqi Zhang, Shuvro Chowdhury, Kevin Callahan-Coray, Kyle Lee, Saleh Bunaiyan, Sanjay Seshan, Clayton Thomas, Jason Twigg, Andrew Seawright, *Forrest Brewer, Tathagata Srimani and Kerem Y. Camsarı
Department of Electrical & Computer Engineering, University of California, Santa Barbara · Electrical Engineering Department, King Fahd University of Petroleum & Minerals · Department of Electrical and Computer Engineering, Carnegie Mellon University · Siemens Digital Industries Software
cs.DC, cs.AR
Submitted: 2026-06-24
Updated: 2026-11-18
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 100/100
The gist: Programmable probabilistic computers built from p-bits have been proposed as hardware accelerators for sampling and optimizing Ising models…
Key concepts
- p-bits
- These are the fundamental programmable bits used in the proposed computer architecture. They serve as the basic units for performing probabilistic computations, allowing the system to model complex Ising models and optimize them.
- $\eta = fcomm/fp-bit$
- This dimensionless parameter measures how frequently boundary information must be refreshed compared to local updates. A large $\eta$ means frequent refreshing is needed, while a small $\eta$ indicates that boundary states can remain stale between exchanges.
- $C_{max}$
- This metric identifies the worst communication bottleneck in the physical interconnect. It represents the cluster pair that creates the tightest transport bottleneck, helping designers bound local update clocks based on this maximum cost.
Terminology
Summary
Programmable probabilistic computers built from p-bits have been proposed as hardware accelerators for sampling and optimizing Ising models, but existing systems have been confined to a single chip, capped by its capacity and memory bandwidth Here we break this limit by networking FPGAs into a single Ising machine far larger than any one device could hold, realizing a programmable probabilistic computer with one million p-bits
System Architecture and Scaling
The architecture involves networking FPGAs into a single Ising machine far larger than any one device could hold, which realizes a programmable probabilistic computer with one million p-bits The machine performs Gibbs sampling at over a trillion flips per second while keeping every coupling weight in local on-chip memory This architecture exposes a question fundamental to any distributed sampler: how frequently boundary information must be refreshed for a partitioned machine to behave as an unpartitioned one The key dimensionedless parameter is η = fcomm/fp-bit (1) which is large when boundary information is refreshed frequently relative to local updates and small when boundary states grow stale between exchanges.
Performance Tradeoff Analysis
The performance of a distributed stochastic machine depends on one timing ratio, η = fcomm/fp-bit Above a topology-dependent threshold, the distributed machine is indistinguishable from an unpartitioned baseline Below it, residual energy still decays as a power law but with a reduced exponent, turning parallelism into a quantifiable throughput–accuracy tradeoff. This tradeoff is universal to partitioned stochastic dynamics, as shown by cluster mean-field theory (CMFT). p. 0 Below it, residual energy still decays as a power law but with a reduced
exponent, turning parallelism into a quantifiable throughput–accuracy tradeoff. A theoretical cluster mean-field
model reproduces the same behavior, showing that this tradeoff is a universal property of partitioned stochastic
dynamics.Where the paper says it
Communication Cost Modeling
The communication-cost metric Cmax identifies the cluster pair that creates the tightest boundary-transport bottleneck once the design is placed on the physical interconnect This cost is defined as Cmax = max a<b bab dab Pab (S.3) and bounds the local update clock given Cmax by fp-bit ≤ fcomm 2 Ncolor Cmax ≡ fp-bit,max (S. p. 2 For any partition, a worst-case congestion
metric Cmax combined with the coloring schedule
bounds the feasible local update clock (Supplementary
Sec. Each device updates its local p-bits at a clock
rate fp-bit, while boundary states are transferred at a
separate communication clock rate fcomm. 2c): the optimization quality of a
distributed run depends only on the ratio, not on either
clock individually. The collapse saturates once η exceeds
roughly 300 for this system and mapping, quantitatively
matching the prediction η ≈ 305 of the conservative
bound
fp-bit ≤
fcomm
2 Ncolor Cmax
, (2)
evaluated with the measured partition parameters, where
Ncolor is the number of color groups in the update
schedule and Cmax is a worst-case congestion metric 2c): the optimization quality of a
distributed run depends only on the ratio, not on either
clock individually. The collapse saturates once η exceeds
roughly 300 for this system and mapping, quantitatively
matching the prediction η ≈ 305 of the conservative
bound
fp-bit ≤
fcomm
2 Ncolor Cmax
, (2)
evaluated with the measured partition parameters, where
Ncolor is the number of color groups in the update
schedule and Cmax is a worst-case congestion metricWhere the paper says it
Where the paper says it
Where the paper says it
Topology and Hardware Considerations
The topology-aware Potts partitioning introduces a cost function that penalizes placing strongly connected partitions on distant devices, concentrating cut edges at short hop distances This strategy avoids the need for explicit search over orderings, as it aligns the partition with the chain topology to minimize worst-path congestion. Furthermore, testing with disconnected links confirmed that slope loss originates from boundary exchange dynamics rather than local update failures. p. 5 Timing closes at 1 MHz; the 3 MHz point is the same synthesis globally overclocked, and beyond 3 MHz read/write synchronization
fails. Timing violations strike the longest paths first, the boundary transfers rather than the local update logic, so overclocking lowers
the effective η at fixed nominal ratio: the 3 MHz point probes the stale-boundary regime of the rule established on DSIM-1.Where the paper says it
Benchmark Results and Validation
Experiments on 3D Edwards–Anderson spin glasses show that the optimization quality of a distributed run depends only on the ratio η, not on either clock individually The fitted exponent curves from hardware and CMFT models collapse onto the same functional form after rescaling, confirming that both systems are shaped by delayed boundary information in partitioned stochastic dynamics. The architecture successfully handles non-cubic graph topologies, achieving results comparable to optimized classical baselines on a highly irregular 3SAT instance. p. 5 The η-governed behavior above is established on cubic
lattices, but the architecture applies to any sparse graph
that can be colored and partitioned; we close with three
capability demonstrations on harder topologies. The G81
instance from the Gset library [52] is a 20,000-node
toroidal grid, open since 2000, whose best known cut
improved only incrementally until the Cosm algorithm,
a dynamical-systems heuristic running on CPUs, found
14,060 [53, 54], since certified optimal by an exact
solver [54].Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
- Distributed Probabilistic Computer Architecture
The system can perform Gibbs sampling at over a trillion flips per second while keeping every coupling weight in local on-chip memory by networking FPGAs into a single Ising machine far larger than any one device could hold.
- Quantitative Throughput Accuracy Tradeoff
The system can operate above a topology-dependent threshold where it matches a monolithic GPU reference,
or below it, where parallelism buys throughput at a quantifiable cost in solution quality,
determined by the timing ratio η = fcomm/fp-bit.
- Design Rule for Scaling Probabilistic Computers
A quantitative design rule is provided for scaling probabilistic computers beyond the single-chip limit, based on the finding that a single timing ratio, η = fcomm/fp-bit, determines the performance of a distributed stochastic machine.
- Topology Aware Partitioning
The system can utilize a Potts cost function to penalize placing strongly connected partitions on distant devices to concentrate cut edges at short hop distances (Fig. 1c and Supplementary Sec. S5).
- Hardware-Agnostic Performance Prediction
A theoretical cluster mean-field model reproduces the same behavior, showing that this tradeoff is a universal property of partitioned stochastic dynamics,
allowing the cost to be predicted in software before hardware is built.
- Robustness Against Boundary Staleness
The underlying reason for performance degradation when boundary information is stale is that stochastic dynamics tolerate stale information gracefully, much as Hogwild-style parallel Gibbs sampling survives stale reads across threads.
- Architecture Flexibility for Diverse Problems
The architecture can be applied to any sparse graph that can be colored and partitioned, including 3D Edwards–Anderson spin glasses, Max-Cut, and Boolean satisfiability problems.
Abstract
Many problems in physics and machine learning require sampling the collective states of large numbers of interacting variables. On modern graphics processors, repeated movement of interaction data between memory and compute units can limit how efficiently these calculations can scale. Here we demonstrate a programmable probabilistic computer with one million interacting probabilistic bits (p-bits) across 18 field-programmable gate arrays, sustaining 10 12 probabilistic updates per second. Coupling weights remain beside the update circuits in on-chip memory, and only single-bit boundary states pass between devices. Experiments on three-dimensional and quasi-two-dimensional spin glasses show that the ratio of boundary-exchange frequency to local update frequency controls the effect of communication delays on optimization. A bound derived from the graph partition and interconnect identifies operating conditions that recover the residual-energy decay of an unpartitioned GPU reference. Infrequent exchange reduces the decay exponent, although faster local updates can shorten the time to reach a target energy. A cluster mean-field model reproduces this dependence, while ferromagnetic sampling experiments reveal a corresponding dependence of magnetization relaxation on the same frequency ratio. These results establish a million-p-bit computing architecture in which processing and local memory scale together, and provide a quantitative design principle for exploiting tolerance to communication delays in larger probabilistic computers.
Sources
- How to Build a Quantum Supercomputer: Scaling from Hundreds to Millions of Qubits
- The Future of Memory: Limits and Opportunities
- Next-generation Probabilistic Computing Hardware with 3D MOSAICs, Illusion Scale-up, and Co-design
- A Generalized Mean Field Algorithm for Variational Inference in Exponential Families
- KaHIP v3.00 -- Karlsruhe High Quality Partitioning -- User Guide
- Performance report of heuristic algorithm that cracked the largest Gset Ising problems (G81 cut=14060)
- Cosm: Collective Switched Motion for Fast and Accurate Sparse Ising Optimization
Related papers
- BatchGen: An Architecture for Scalable and Efficient Batch Inference
- Seamless Reconfiguration for DAG-BFT (Technical Report)
- ELDR: Expert-Locality-Aware Decode Routing for PD-Disaggregated MoE Serving
- iScheduler: Reinforcement Learning-Driven Continual Optimization for Large-Scale Resource Investment Problems
- TIRx: A Unified Tile Primitive ML Compiler Across Heterogeneous Backends
- AgentWeave: Efficient Distributed Agent Serving via Flow Decomposition