We prove that if a parabolic Lipschitz graph domain has the property that its caloric measure is a parabolic $A_\infty$ weight with respect to surface measure, then the function defining the graph has a half-order time derivative in the space of (parabolic) bounded mean oscillation. Equivalently, we prove that the $A_\infty$ property of caloric measure implies that the boundary is parabolic uniformly rectifiable. Consequently, by combining our result with the work of Lewis and Murray we prove that the $L^p$ solvability (for some $p > 1$) of the Dirichlet problem for the heat equation is equivalent to parabolic uniformly rectifiability. This is joint work with S. Bortz, S. Hofmann, and J.M. Martell.