A fast acceptance-rejection scheme that can boost the performance of Monte Carlo methods for particle coagulation has been designed and validated in this article. The central idea behind this scheme is to perform a fast evaluation of the maximum coagulation rate by making full use of the information of those particle pairs that are already generated to determine the desired coagulation pair. To this end, numerical experiments are carried out to establish a connection between the average coagulation rate obtained from information of those already generated particle pairs and the maximum coagulation rate. The correctness of the proposed scheme is then validated by comparing it to some established methods, adopting a physically realistic Brownian coagulation kernel. The computational efficiency of the fast AR scheme is finally measured.