Noise in behavior is often viewed as a nuisance: while the mind aims to take the best possible action, it is let down by unreliability in the sensory and response systems. How researchers study cognition reflects this viewpoint – averaging over trials and participants to discover the deterministic relationships between experimental manipulations and their behavioral consequences, with noise represented as additive, often Gaussian, and independent. Yet a careful look at behavioral noise reveals rich structure that defies easy explanation. First, both (...) perceptual and preferential judgments show that sensory and response noise may potentially only play minor roles, with most noise arising in the cognitive computations. Second, the functional form of the noise is both non-Gaussian and non-independent, with the distribution of noise being better characterized as heavy-tailed and as having substantial long-range autocorrelations. It is possible that this structure results from brains that are, for some reason, bedeviled by a fundamental design flaw, albeit one with intriguingly distinctive characteristics. Alternatively, noise might not be a bug but a feature: indeed, we suggest that noise is fundamental to how cognition works. Specifically, we propose that the brain approximates probabilistic inference with a local sampling algorithm, one that uses randomness to drive its exploration of alternative hypotheses. Reframing cognition in this way explains the rich structure of noise and leads to a surprising conclusion: that noise is not a symptom of cognitive malfunction but plays a central role in underpinning human intelligence. (shrink)