Phytophagous insects locate suitable hosts through volatile compounds. Polyphagous species face a particular challenge because their hosts emit diverse chemical profiles, yet their olfactory strategies remain unclear. A long-standing assumption suggests that these insects respond primarily to compounds shared across hosts. Here we show that olfactory responses of various polyphagous fruit fly species (Tephritidae) are instead tuned to species-specific fruit compounds from 28 host fruits. This tuning translates into a behavioural preference for species-specific over shared fruit compounds, but only at low doses. Previously, response probability in the same species had been reported to be tuned to shared fruit compounds. To reconcile these observations, we propose a working hypothesis, supported by a computational model: an inverse relationship between olfactory response amplitude and probability may have evolved under the ecological need to detect and discriminate hosts. Together, these results highlight how polyphagous Tephritidae balance detection and discrimination through finely tuned olfactory mechanisms. This insight not only advances our understanding of host selection in polyphagous insects but also has potential applications for ecological management and pest control strategies.