Resource specialization and ecological speciation arising through host-associated genetic differentiation (HAD) are frequently invoked as an explanation for the high diversity of plant-feeding insects and other organisms with a parasitic lifestyle. While genetic studies have demonstrated numerous examples of HAD in insect herbivores, the rarity of comparative studies means that we still lack an understanding of how deterministic HAD is, and whether patterns of host shifts can be predicted over evolutionary timescales. We applied genome-wide single nucleotide polymorphism and mitochondrial DNA sequence data obtained through genome resequencing to define species limits and to compare host-plant use in population samples of leaf- and bud-galling sawflies (Hymenoptera: Tenthredinidae: Nematinae) collected from seven shared willow (Salicaceae: Salix) host species. To infer the repeatability of long-term cophylogenetic patterns, we also contrasted the phylogenies of the two galler groups with each other as well as with the phylogeny of their Salix hosts estimated based on RADseq data. We found clear evidence for host specialization and HAD in both of the focal galler groups, but also that leaf gallers are more specialized to single host species compared with most bud gallers. In contrast to bud gallers, leaf gallers also exhibited statistically significant cophylogenetic signal with their Salix hosts. The observed discordant patterns of resource specialization and host shifts in two related galler groups that have radiated in parallel across a shared resource base indicate a lack of evolutionary repeatability in the focal system, and suggest that short- and long-term host use and ecological diversification in plant-feeding insects are dominated by stochasticity and/or lineage-specific effects.