Locally low rank (LLR) reconstruction is an effective strategy that has found application across a range of MRI applications. In lieu of processing all overlapping image blocks each iteration, most LLR implementations employ “cycle spinning”, where only a random subset of blocks is processed. Cycle spinning improves efficiency, but may compromise reconstruction convergence and introduce artifacts. We propose a primal-dual algorithm for LLR reconstruction and show that stochastically updating the dual variable provides similar computational advantage as cycle spinning but avoids its primary disadvantages. Reconstruction performance benefits are demonstrated on both a numerical phantom and in vivo.