Stochastic computing

https://scottlocklin.wordpress.com/2025/10/31/stochastic-computing/

by emmelaich • 9 months ago

66 7 9 months ago

scottlocklin.wordpress.com

emil-lp• 8 months ago

How is using randomness in stochastic computing connected to how algorithms (eg in the complexity class BPP) use randomness to solve problems?

numbol• 8 months ago

It seems that those two (actually three or four) ideas are parallel and not always compatible.

[please forgive my grammar]

1. There is noisy computers which can work despite or because some unreliable part. Neural netwroks are quite ok with it for example, so some people speculate that it will be possible to build specialized noisy circuits for specific networks. 2. There is stochastic computing, in which complicated numerical functions represented as probability density distributions (?) 3. And then there is probabalistic computing, when state randomly updated in accordance with some "temprature". 4. And finally there is randomized algoritms, which are closer to classical computer science but with some stream of input. Howver, people like Avi Wigderson who succesfully removed the "random" parts of those algoritms.

Plus there is funny things with non-associativity of floating-point numbers which can lead to non-determinism when the order of execution (summation for example) is arbitary, which can lead to funny results. But because neural netwroks are robust to noise to some degree, it will still work.

And the stuff which done by Avi Wigderson requires that computers work in determinstic way (except of that random stream), so it will not be very compatible with unreliable noisy computations. However, it seems that stochastic, probabalistic and noisy computations could be combined.

mikewarot• 8 months ago

The key thing I would watch out for with real stochastic computing hardware is crosstalk[1], the inevitable coupling between channels that is bound to happen at some level. Getting hundreds or thousands (or millions?) of independent noise sources to avoid correlation is going to be one of the largest challenges in the process. For a small number of channels, it should be managable, but with LLM size problems, I think it's a deal killer.

[1] https://en.wikipedia.org/wiki/Crosstalk

kragen• 8 months ago

If your random bit streams are generated by deterministic processes such as LFSRs, and you're combining them with things like NAND gates, you should easily be able to get the bit error rate down below 10⁻²⁰, I'd think? (And crosstalk would be a bit error.) How often do the gates in your CPU produce the wrong answer?

observationist• 8 months ago

https://en.wikipedia.org/wiki/Noisy-channel_coding_theorem

You can precisely engineer arbitrary numbers of channels, design sampling methods to raise your data integrity to whatever your desired error rate is, and so on. This gives you an accuracy/efficiency tradeoff dial, which can be useful - you can choose to spend more time or energy for higher fidelity where the cost justifies it.

Feedback and crosstalk creating chaotic relationships, unintended synchronization, and other effects are non-trivial, however.

Neural networks are non-dimensional or unordered sets, meaning you can arbitrarily order the neurons in a layer so long as you maintain the links to the connected layers. If you permute the structure of a network to reorder neurons in a layer by some feature, the function of the network remains identical to the original, but you can highlight a particular function or feature of the layer, with the constellation of coordinates representing the particular configuration of synapse ordering and weight vectors. You can cycle through all possible configurations of orderings, and those represent possible states of a trained network. When trying to work with stochastic optimizations for neural networks, you're playing around in this same space - they're effectively a combinatorial minefield.

If you design a processing regime to sample a particular subset of possible configurations, it might be possible to exploit a traversal of random orderings associated with amplitude of signals where they correlate and coincide with useful computation - selecting and ordering a set of addresses whose function approximates the desired value.

I see some possibilities and interesting spaces to explore with these systems, but they're going to need some heavy duty number theorists just to eke out a set of useful primitives, and it's unclear to me that it can ever be generalized. You might be able to carefully handcraft an implementation for something like ChatGPT 5, for example, but I don't see how you could simply update it, finetune it, or otherwise. You'd have to put in just as much effort to implement any other model, and any sort of dynamic online learning or training seems to hit a combinatorial explosion right out of the gate.

RA_Fisher2• 8 months ago

How is this not rediscovering statistics in unprincipled ways?

RA_Fisher2• 8 months ago

Crickets, crickets, crickets ... :)

Stochastic computing

Related Stories