There is currently massive research effort to develop a cure for HIV infection, allowing patients to discontinue lifelong combination antiretroviral therapy. New latency-reversing agents may be able to purge the persistent reservoir of latent virus in resting memory CD4+ T cells, but the degree of reservoir reduction needed for cure remains unknown. In this paper, a stochastic model of infection dynamics is presented to estimate the efficacy of latency-reversing agents needed to prevent viral rebound after ART interruption. Clinical data are used to estimate population-level parameter distributions and outcomes. The findings suggest that 2,000-fold reductions are required to permit a majority of patients to interrupt ART for 1 year without rebound and that rebound may occur suddenly after multiple years. Greater than 10,000-fold reductions may be required to prevent rebound altogether. These results predict large variation in rebound times following latency-reversing agents therapy, which will complicate clinical management. This model provides benchmarks for moving latency-reversing agents from the laboratory to the clinic and can aid in the design and interpretation of clinical trials. These results also apply to other interventions to reduce the latent reservoir and can explain the observed return of viremia after months of apparent cure in recent bone marrow transplant recipients and an immediately-treated neonate. .