The AS04-adjuvanted human papillomavirus (HPV)16/18 vaccine, an L1-based vaccine, provides strong vaccine efficacy (VE) against vaccine-targeted type infections, and partial cross-protection to phylogenetically-related types, which may be affected by variant-level heterogeneity. We compared VE against incident HPV31, 33, 35, and 45 detections between lineages and SNPs in the L1 region among 2846 HPV-vaccinated and 5465 HPV-unvaccinated women through 11-years of follow-up in the Costa Rica HPV Vaccine Trial. VE was lower against HPV31-lineage-B (VE=60.7%;95%CI = 23.4%,82.8%) compared to HPV31-lineage-A (VE=94.3%;95%CI = 83.7%,100.0%) (VE-ratio = 0.64;95%CI = 0.25,0.90). Differential VE was observed at several lineage-associated HPV31-L1-SNPs, including a nonsynonymous substitution at position 6372 on the FG-loop, an important neutralization domain. For HPV35, the only SNP-level difference was at position 5939 on the DE-loop, with significant VE against nucleotide-G (VE=65.0%;95%CI = 28.0,87.8) but not for more the common nucleotide-A (VE=7.4%;95%CI = -34.1,36.7). Because of the known heterogeneity in precancer/cancer risk across cross-protected HPV genotype variants by race and region, our results of differential variant-level AS04-adjuvanted HPV16/18 vaccine efficacy has global health implications.