The Viterbi process is the limiting maximum a-posteriori estimate of the unobserved path in a hidden Markov model as the length of the time-horizon grows. The existence of a such a process has the interpretation that data from the distant past or future have a vanishingly small influence on estimates of current states. This suggests that approximate inference algorithms which process data segments in parallel may be accurate. For models on state-space R^d satisfying a new "decay-convexity" condition, results are obtained which quantify the rate of convergence to the Viterbi process and relate it to the ingredients of the model and the data. This allows identification of model classes for which the parallelization strategy is effective and potentially scaleable to high-dimensional problems, since in some cases the rate of convergence does not depend on d.