The state's ability to identify where its citizens reside is crucial to public service delivery and enforcing citizen obligations. However, even where immobile residences constrain evasion, households may remain invisible to the state because public agents lack local knowledge and are poorly motivated or risk-averse to discovering new households. To better understand who the state overlooks, this study asks which households are least legible to the state in developing contexts: those at the periphery of their communities or those in dense informal settlements? It also evaluates whether legibility can be borrowed from other arms of the state, for example public clinics and schools, or coproduced with private actors such as religious institutions and markets. These patterns of legibility are empirically evaluated in the context of Northern Nigeria's polio eradication campaign, which sought to repeatedly visit every household in the region. Combining a newly-constructed dataset of residential buildings in Northern Nigeria produced using remote sensing data and machine learning with GPS tracks of polio vaccination team activities, spatial regression models test which geographical characteristics of households are most conducive to their legibility. The conclusions provide new insights into which households are most often excluded from emerging social contracts or spared from authoritarian practices.