We extend miniKanren with a collection of primitives for describing probabilistic generative models and describe modifications to the language’s stream-based implementation that permit the efficient variational learning of such models via weighted model counting, with runtimes of within an order of magnitude of their manual implementations. We begin with a naive implementation that requires minimal changes to the core miniKanren implementation, and then describe two modifications to achieve practical levels of efficiency. The first alters the search to factorize conditionally independent conjuncts, avoiding unnecessary combinatorial explosion. The second modifies tabling to recover standard probabilistic dynamic programming algorithms such as Viterbi, forward-backward, and Baum-Welch. The end result is a simple extension to miniKanren that is nevertheless efficient enough to be of use in writing practical probabilistic relational programs.