Gamma-band rhythmic inhibition is a ubiquitous phenomenon in neural circuits, yet its computational role remains elusive. We show that a model of gamma-band rhythmic inhibition allows networks of coupled cortical circuit motifs to search for network configurations that best reconcile external inputs with an internal consistency model encoded in the network connectivity. We show that Hebbian plasticity allows the networks to learn the consistency model by example. The search dynamics driven by rhythmic inhibition enable the described networks to solve difficult constraint satisfaction problems without making assumptions about the form of stochastic fluctuations in the network. We show that the search dynamics are well approximated by a stochastic sampling process. We use the described networks to reproduce perceptual multistability phenomena with switching times that are a good match to experimental data and show that they provide a general neural framework that can be used to model other perceptual inference phenomena.