The principle of legality requires that individuals receive “fair notice” of conduct that is criminal. Courts enforce this fair notice requirement through various interpretive principles and practices, including the void-for- vagueness doctrine. The void-for-vagueness doctrine remains undertheorized, however, despite its centrality to the interpretation of criminal statutes. We offer a new theory of the void-for-vagueness doctrine that accounts for recent Supreme Court decisions. Specifically, we propose a scalar theory that fair notice is a matter of degree, dependent on various factors. We explore the implications of this theory for anti-abortion statutes post-Dobbs and explain why many of these statutes do not provide fair notice to either ordinary individuals or medical professionals.