We investigated network principles underlying mental search through a novel phonological verbal fluency task. Post exclusion, 95 native-language Mandarin speakers produced as many items that differed by a single lexical tone as possible within one minute. Their verbal productions were assessed according to several novel graded fluency measures, and network science measures that accounted for the structure, cohesion and interconnectedness of lexical items. A multivariate regression analysis of our participants’ language backgrounds included their mono- or multi-lingual status, English proficiency, and fluency in other Chinese languages/dialects. Higher English proficiency predicted lower error rates and greater interconnectedness, while higher fluency in other Chinese languages/dialects revealed lower successive similarity and lower network coherence. This inverse relationship between English and other Chinese languages/dialects provides evidence of the restructuring of the phonological mental lexicon.