Controllable music generators let a user specify a chord per bar, a rhythmic density, a polyphony level, or a key and meter, and then check whether the output obeys. These systems report impressive control accuracy: MuseCoco reaches 87.15% average attribute accuracy, MuseMorphose reaches Spearman correlations of 0.95 and 0.88 with requested rhythm and polyphony, and Mustango matches requested chords about 75% of the time. All of these numbers are averages over control requests drawn from held-out natural music. A composer does not ask for average requests, though. They ask for a specific progression in a specific rhythm, and the question that matters is how often a perfectly reasonable request breaks the model. This proposal measures that question with an idea borrowed from complexity theory. If a solver fails on some inputs, one can often build a cheap sampler of inputs on which it fails a large fraction of the time.
We build such samplers for music controllers using planted control specs. Each test request is extracted from a real piece of music, so a correct answer is known to exist. We then search over these requests with edits that always keep a real witness piece attached, such as transposition, splicing bars from two pieces, or retempo. The search looks for distributions on which a given generator fails often. The gap between natural-prompt accuracy and accuracy on the found distribution is a direct, reproducible measure of how far average-case controllability overstates the controllability users actually get. The same machinery then lets us test whether training on these hard requests closes the gap or whether a new hard distribution simply reappears.
Core Claim
The claim is that current controllability metrics hide a large, cheaply discoverable gap. For each major controllable generator, a black-box search over witness-carrying control specs will find an efficiently sampleable distribution of musically valid requests on which control accuracy falls far below the published average. A random sample from the same edit space at the same budget will not find a comparable drop. If this holds, controllability should be reported against an adversarially searched, feasibility-certified distribution as well as a natural one. The gap's size, and how it changes after targeted fine-tuning, become first-class evaluation quantities.
The theoretical template comes from If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances. Gutfreund, Shaltiel and Ta-Shma show that, assuming worst-case hardness, every efficient algorithm has an efficiently sampleable distribution on which it fails a constant fraction of the time: at least 1/6 for deterministic algorithms and 3/100 for randomized ones. They also show that a fixed quasi-polynomial-time sampler defeats all efficient algorithms at once. We do not claim any formal reduction to music. A neural music model is not a SAT solver, and music control is not known to be hard in any technical sense. What we take is the evaluation stance: algorithm-specific hard distributions, a separate question of whether one distribution transfers across algorithms, and the insistence that a "hard instance" must be a genuine instance.
That last requirement is where planting comes in. In The Planted Orthogonal Vectors Problem, Kühnemann, Polak and Rosen build hard average-case instances by hiding a known solution inside random-looking data. A solution is guaranteed to exist, and any failure belongs to the solver. Our analogue keeps a witness piece attached to every spec, so a failure can never be blamed on asking for impossible or unmusical constraints. Without that guarantee, adversarial prompting of music models produces nonsense requests and uninterpretable failure rates.
A second, motivating thread comes from diffusion theory. Koehler et al. (Sampling Multimodal Distributions with the Vanilla Score: Benefits of Data-Based Initialization) show that diffusion sampling converges when the learned score, the model's estimate of which direction increases data likelihood, is accurate only in an $L^2$ average over the data distribution. Gupta et al. (Sample-Efficient Training for Score-Based Diffusion) relax this further to accuracy on all but a $\delta$ fraction of the data. These results explain why audio diffusion models such as Mustango sound good on average. They say nothing about conditioning values that are rare under the data, which is exactly where a $1-\delta$ guarantee permits failure. Our experiments test whether discovered hard specs concentrate in such low-density conditioning regions, which would be the empirical face of the gap these theorems leave open.
Research Program
Specs come from witnesses. A witness is a real symbolic excerpt drawn from POP909 (POP909: A Pop-Song Dataset for Music Arrangement Generation), AILabs.tw-Pop1K7, or EMOPIA (EMOPIA: A Multi-Modal Pop Piano Dataset For Emotion Recognition and Emotion-based Music Generation), or a MusicBench audio clip for the audio model. From each witness we extract the full control vector each model accepts. For MuseMorphose, that is bar-level rhythmic intensity and polyphony classes. For MuseCoco, it is key, tempo, meter, instruments and the other attributes in its prefix vocabulary. For Mustango, it is beat and chord sequences.
A self-consistency filter guards against checker error. A spec is admitted only if the same attribute checker used to score the generator also scores the witness as satisfying it. This matters because chord recognizers can fail on unusual material, and we must not count checker errors as model errors.
The search operates through witness-carrying edits, meaning operations whose output is again a real, checkable piece. These are transposition by any interval, splicing a bar range from one witness onto another at a downbeat, tempo rescaling, instrument reassignment where the model supports it, and voice-preserving bar substitution between pieces in the same key. Every edited spec therefore has a witness, and the self-consistency filter is reapplied to it. Splices can produce musically awkward but valid pieces, so a listening panel rates a random subset of witnesses from the final hard distributions for musicality. This tells us whether the search drifts toward strange but technically valid music, and we report that drift explicitly.
The refuter is a population-based black-box search. Its fitness is the generator's empirical failure rate over $m$ samples per spec, under a fixed total budget of $B$ generator calls. We define the hardness gap of generator $G$ as
$$\Delta(G) = \mathrm{Acc}_{\mathcal{N}}(G) - \mathrm{Acc}_{\mathcal{H}_G}(G),$$
Here $\mathcal{N}$ is the natural held-out spec distribution, $\mathcal{H}_G$ is the distribution the refuter outputs for $G$ (a sampler over edit programs applied to witnesses), and $\mathrm{Acc}$ is the model's own published control metric. $\mathcal{H}_G$ is evaluated on fresh samples from that sampler, not on the specs the search optimized. This keeps $\Delta$ from being inflated by selection on noisy estimates.
The program then asks three questions. The first is the size of $\Delta$ for each model, and whether hard specs share interpretable structure: non-diatonic chords, rapid density changes across a bar line, rare key-and-meter combinations, or low density under the training corpus as estimated by a separate symbolic language model. The second is transfer. Does $\mathcal{H}_{G_1}$ also defeat $G_2$, and can a single distribution found jointly against several models defeat held-out models? This is the empirical counterpart of the single fixed distribution in Gutfreund et al. The third is repair. We fine-tune each model on witnesses sampled from $\mathcal{H}_G$, rerun the refuter at the same budget, and track $\Delta$ over rounds. The outcome is open. If the gap shrinks steadily, the failures were a fixable data gap. If a new distribution with a similar gap is found each round, controllability behaves more like the theory's picture, where every efficient solver has its own hard distribution. Either result is informative.
Baselines
The naive reference point is the published natural-distribution accuracy, reproduced on our held-out witnesses so that checkers match. The reported figures are an ASA of 87.15% for the 1.2B MuseCoco model (MuseCoco), Spearman correlations of 0.95 for rhythmic intensity and 0.88 for polyphony on AILabs.tw-Pop1K7 for MuseMorphose, and roughly 75% chord-matching accuracy for Mustango, against 20–30% for MusicGen and AudioLDM2. Mustango is the strongest existing chord-controllable audio method, and its figure is the anchor the audio experiments must move. We report our reproduced numbers alongside these and treat any discrepancy as calibration rather than as a result.
The strongest competitor on our actual question is random witness-carrying editing. It draws edit programs uniformly from the same edit space and applies them to the same witnesses, at exactly the same budget $B$ of generator calls and with the same checkers and self-consistency filter. It is strong because, if the edit space alone produces off-distribution specs, it might reveal the whole gap without any search. The refuter beats it only if its held-out failure rate exceeds random editing's by a margin outside bootstrap confidence intervals at every budget we test.
A second competitor is rare-stratum evaluation. Here the existing held-out set is reweighted toward its least frequent attribute combinations, with no edits at all. This isolates whether the gap is simply rarity within natural data.
The ablation that isolates the key ingredient is the refuter run without witnesses. It searches freely over control vectors, with no guarantee that any real piece satisfies them. We expect it to report even larger failure rates. We also expect its specs to be rejected far more often when a symbolic constraint solver checks satisfiability, in the spirit of the rule systems of An Expert System for Chorale Harmonization, and its witness-free specs to be rated less musical. That combination shows that planting is what makes the measured gap attributable to the model.
For the repair experiments, the competitor is rejection sampling with the attribute checker at equal generation compute. Generation stops at the first sample that passes, with up to $k$ draws, and we report the success rate and average number of draws. Fine-tuning on random-edit witnesses of matched count serves as the data-matched control.
Why not just…?
Why not just evaluate on random edits or rare combinations, without any search? This is the real threat. If random witness-carrying edits produce the same drop as the refuter, our contribution shrinks to "use a harder, feasibility-certified test set." That is still useful, but it is not evidence of model-specific hard distributions. The comparison at matched budget in our first experiment settles it directly, and we will report the result whichever way it falls. The transfer experiment adds a second test. Random edits are model-agnostic by construction, whereas a refuter that finds model-specific weaknesses should show a large gap on its target model and a smaller one on other models.
Why not just filter outputs with a constraint checker or solver, as rule-based systems did? Rejection sampling or a downstream constraint solver can raise the pass rate on any spec. It does not tell us how often the model fails, and it costs many generations exactly on hard specs. Ebcioglu's harmonizer needed over 350 hand-written rules for a single style (An Expert System for Chorale Harmonization). We include rejection sampling as the repair baseline and report the number of draws it needs on $\mathcal{H}_G$ versus $\mathcal{N}$. If it needs few draws on hard specs too, the practical gap is small, and we will say so.
Why not just ask a language model to write tricky prompts? Free-form red-teaming produces requests with no guarantee that they are satisfiable or musical, so a failure cannot be attributed to the generator. The witness-free ablation is precisely the measurement of how much an unconstrained search overstates failure. An LLM-prompt variant can be added to the same ablation group, and we expect it to show the same attribution problem.
Proposed Experiments
The first experiment establishes the gap. For MuseMorphose on AILabs.tw-Pop1K7, MuseCoco's attribute-to-music stage on POP909 and EMOPIA witnesses, and Mustango on MusicBench, we compare $\mathrm{Acc}_{\mathcal{N}}$, rare-stratum accuracy, random-edit accuracy, and refuter accuracy. We run budgets of $B$ spanning an order of magnitude and report bootstrap confidence intervals. The decisive check is whether refuter accuracy sits significantly below random-edit accuracy at matched budget for all three models. A secondary check, using a held-out symbolic language model, asks whether hard specs fall in low-density regions of conditioning space, as the diffusion robustness results would predict.
The second experiment tests attribution. On a sample of refuter specs, with and without witnesses, we report constraint-solver satisfiability, witness self-consistency rates, and listener ratings of musicality for witnesses versus natural excerpts. Planted specs should be satisfiable by construction and rated comparably musical, while witness-free specs should not be.
The third experiment tests transfer and a shared hard distribution. We cross-evaluate each $\mathcal{H}_G$ on the other symbolic model and run a joint search against both. The question is whether one distribution defeats both models, and whether a distribution found on MuseCoco at one scale transfers to another scale.
The fourth experiment runs repair rounds. We alternate fine-tuning on hard witnesses with rerunning the refuter for several rounds, and compare against random-edit fine-tuning and checker-based rejection sampling at equal compute. We track $\Delta$ on fresh refuter runs and natural accuracy, to catch any regression on ordinary requests. The decisive outcome is the shape of the $\Delta$ curve over rounds: a steady decline toward zero, or a plateau with new hard distributions found each time.
References
- If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances
- The Planted Orthogonal Vectors Problem
- Mustango: Toward Controllable Text-to-Music Generation
- MuseMorphose: Full-Song and Fine-Grained Piano Music Style Transfer With One Transformer VAE
- MuseCoco: Generating Symbolic Music from Text
- An Expert System for Chorale Harmonization