Only few previous studies have explored cross-national variation in the relationship between educational certificates and competences. In this paper, we investigate the certificate-competence relationship, operationalized as skills gaps by level of educational attainment. More importantly, we scrutinize how two aspects of educational stratification processes, vertical stratification and occupation-specificity, affects skills gaps. Using data on 25-54 year olds from the 2011/12 round of the Programme for the International Assessment of Adult Competencies (PIAAC), we find that more occupation-specific education systems produce smaller differences in basic general skills between adults with low and intermediate levels of education. Higher levels of vertical stratification, by contrast, result in larger low-intermediate skills gaps. None of the two stratification aspects can however explain variations in the skills gaps between intermediate and high educated adults. We conclude by discussing the implications of our findings for labor market research.