Message passing based inference algorithms have immense importance in real-world applications. In this paper, error resilience of a message passing based Markov random field (MRF) stereo matching architecture is explored and enhanced through application of algorithmic noise tolerance (ANT) in order to cope with nanometer imperfections in post-silicon devices. We first explore the inherent robustness of iteration based MRF inference algorithms. Analysis and simulations show that for a 20-bit architecture, small errors (e ≤ 1024) are tolerable, while large errors (e ≥ 4096) degrade the performance significantly. Based on these error characteristics, we propose an ANT architecture to effectively compensate for large magnitude circuit errors. Introducing timing errors via voltage over scaling (VOS), experimental results show that the proposed ANT based hardware can tolerate an error rate of 21.3%, with performance degradation of only 0.47% at a gate complexity overhead of 44.7%, compared to an error-free full precision hardware with an energy savings of 41%.