Reducing rigidity in labor markets is key to lowering unemployment. Theoretical models suggest that the impact of such reforms depends on the country-specific regulatory framework. We test this hypothesis by estimating the impact of changes in six categories of regulation conditional on the country-specific regulatory environment for 26 OECD countries. We overcome problems of modeling a large set of institutional interdependencies by applying a machine learning type model selection approach. We provide evidence for the existence of higher-order institutional interdependencies. We further document that especially for changes in employment protection and the unemployment benefit system the impact on unemployment is mixed across countries.