The cold start problem in recommender systems (RSs) makes the recommendation of high-quality content to new users difficult. While preference elicitation (PE) can be used to “onboard” new users, PE in music recommendation presents unique challenges to classic PE methods, including: a vast item (music track) corpus, considerable within-user preference diversity, multiple consumption modes (or downstream tasks), and a tight query “budget.” We develop a PE framework to address these issues, where the RS elicits user preferences w.r.t. item attributes (e.g., artists) to quickly learn coarse-grained preferences that cover a user’s tastes. We describe heuristic algorithms that dynamically select PE queries, and discuss experimental results of these methods onboarding new users in YouTube Music.