With the rise of big data and complex modeling, probabilistic inference (i.e., computing probability of an event given some observation) has emerged as a key problem. The current state of art techniques are either exact and face scalability issues or provide very weak approximation guarantees. We introduce a new computational paradigm, which makes only few feasibility queries on models augmented with random constraints, that provides (ε-δ) guarantees and scalable practical algorithms. Our new approach builds upon our prior work in computational theory and techniques based on universal hashing. I will discuss how we can further use these techniques to generate sample from complex distributions which has been key to constrained-random verification over last two decades.