Stimulus-specific associative learning, which is essential for animals’ survival, is aided by temporal correlation between sensory and reinforcing signals and accurate neuronal sensory representations. However, reinforcing signals alone could induce neuromodulation without coincident sensory-evoked neuronal activity, thereby generating unspecific associations. Here, we use two-photon in vivo functional imaging, along with pharmacological and optogenetics manipulations, and behavior experiments to report a crucial neuromodulatory mechanism that prevents unspecific association by counteracting the signals evoked by sensory and reinforcing cues. In Drosophila, olfactory signals are sparsely represented by cholinergic Kenyon cells (KCs), which receive dopaminergic reinforcing input. We find that KCs have numerous axo-axonic connections, mediated by the muscarinic type-B receptor (mAChR-B), which suppress both odor-evoked calcium responses and dopamine-evoked cAMP signals in neighboring KCs. Strikingly, mAChR-B knockdown impairs olfactory learning by inducing undesired changes to the valence of an odor that was not associated with reinforcer. Thus, this local neuromodulation acts in concert with sparse sensory representations and global dopaminergic modulation to achieve effective and accurate memory formation.