This paper proposes the ε-Advanced Color Passing (ε-ACP) algorithm to overcome the limitations of the existing Advanced Color Passing (ACP) algorithm. The ACP algorithm requires perfect matching of object identities to perform efficient lifted inference, but latent variables learned from real data inevitably show differences. The ε-ACP algorithm introduces a tolerance ε between latent variables, enabling efficient lifted inference by leveraging object identities even when there is a perfect match. In this paper, we prove that the approximation error induced by the ε-ACP algorithm is strictly bounded, and experimentally demonstrate that the actual approximation error is close to zero.