In the smartphone era, instance recognition (IR) applications are widely used on mobile devices. However, IR applications are computationally expensive for a single mobile device, and usually they are delegated to back end servers. Nevertheless, even by exploiting the computational power offered by cloud services, IR tasks are not executed in real-time (i.e., in less than 30ms), which is crucial for interactive mobile applications. In this work, we present caching for instance recognition on cloud environments (CIRCE), a similarity caching (SC) framework designed to improve the performance of mobile IR applications in terms of execution time. Additionally, we introduce a parallel version of the Hessian-Affine detector combined with the SIFT descriptor, and a novel cache hit threshold (CHT) algorithm. Finally, we present two new public image datasets that we create to evaluate CIRCE. By using a cache size of just few hundreds, we obtain a hit ratio of at least 66% and a precision of at least 97%. In case of a cache hit, our system performs IR tasks in at most 14ms on three different applications.