Abstract Belief propagation over Markov random fifields has been successfully used in many AI applications since it yields accurate inference results by iteratively updating messages between nodes. However, its high computation costs are a barrier to practical use. This paper presents an effificient approach to belief propagation. Our approach, Quiet, dynamically detects converged messages to skip unnecessary updates in each iteration while it theoretically guarantees to output the same results as the standard approach used to implement belief propagation. Experiments show that our approach is signifificantly faster than existing approaches without sacrifificing inference quality