TL;DR
Standard autoregressive transformers often ignore user-specified chord constraints during melody harmonization because they generate music strictly left-to-right without looking ahead. This paper introduces B*, a novel decoding algorithm that combines beam search, $A^*$, and backtracking to force pretrained transformers to satisfy hard chord constraints at exact musical positions.
What Problem Does This Paper Address?
Melodic harmonization—the task of generating a chord progression to accompany a given melody—requires a deep understanding of both local chord transitions and global musical context. While autoregressive transformers (like GPT-2 or BART) excel at generating musically plausible progressions, they struggle with hard constraints. For example, if a user wants to force a specific chord (like a surprising secondary dominant) at bar 3, beat 1, a standard transformer will often simply ignore the request if it contradicts its learned statistical priors.
Because these models generate tokens sequentially from left to right, they cannot naturally plan backward from a future constraint. Simply appending the desired chord to the prompt ("soft constraints") fails because the model's predictive nature easily overrides the user's prompt in favor of a more "likely" continuation.
Methods
The authors evaluate two transformer architectures—BART (encoder-decoder) and GPT-2 (decoder-only)—across two different chord tokenization strategies:
- ChordSymbolTokenizer (CS): Treats chords as holistic symbols (e.g.,
C:maj). - PitchClassTokenizer (PC): Spells out chords note-by-note using their constituent pitch classes (e.g.,
chord_pc_0,chord_pc_4,chord_pc_7).
To guarantee constraint satisfaction, they propose the B* algorithm. B* operates in two stages:
- Stage 1 (Constraint Seeking): It uses a restricted beam-style, best-first approach ($A^*$) to explore the most probable generation paths. If a path reaches the designated bar but fails to produce the required constraint chord, the algorithm backtracks to parent nodes to try alternative token sequences.
- Stage 2 (Completion): Once the constraint is successfully generated, the algorithm reverts to standard beam search to finish the piece.
To keep the search efficient, the authors introduced a custom scoring function that penalizes "overcrowded" bars, preventing the model from generating excessively long, dense chord sequences just to accumulate high log-probability scores before reaching the constraint.
Datasets
The models were trained and evaluated on the Hook Theory dataset, consisting of 17,476 lead sheets of popular Western music (pop, rock, etc.) converted into MusicXML format. To eliminate key-specific biases, all pieces were transposed to relative keys with no sharps or flats (C major for major modes, A minor for minor modes). The data was split into a 90% training set (15,956 pieces) and a 10% testing/validation set (1,520 pieces).
Key Insights and Ideas
- Transformers are Stubborn: Pretrained language models are highly biased toward their training distributions. Even when explicitly prompted with a constraint token, they will actively ignore user input if it feels musically "unnatural" to the model's internal probabilities.
- Token Granularity Impacts Search Complexity: Representing chords as single symbols (CS) yields much faster convergence during backtracking than spelling them out via pitch classes (PC). Because PC sequences are significantly longer, they suffer from a much harsher combinatorial explosion during the backtracking phase.
- The Control vs. Quality Trade-off: Forcing a hard constraint inherently forces the transformer to choose sub-optimal paths according to its internal probability distribution. As a result, objective musicality metrics (like chord diversity and harmonic smoothness) drop slightly compared to unconstrained generation, representing a direct trade-off between user control and model-perceived naturalness.
Key Results
The authors tested the models by assigning random chord constraints to random positions within the test set:
- Baseline (No Constraints): Naturally hit the desired chord only 20% to 27% of the time.
- Soft Constraints (Prompting): Improved the success rate to 52% to 63%, proving that prompting alone is insufficient for reliable user control.
- B* Algorithm: Achieved a massive jump, satisfying the hard constraints in 90% to 98% of cases within a 10,000 model-call limit.
GPT-2 paired with the PitchClassTokenizer achieved the highest overall constraint success rate (98.62%), though it required significantly more computational steps. For efficiency, BART with Chord Symbol tokenization hit a 94.8% success rate while requiring an average of only 435 model calls (compared to thousands for the PC variations).
Limitations and Future Work
The primary limitation of the B algorithm is its worst-case exponential time complexity*. Because it relies on brute-force backtracking, it can become computationally expensive and slow, making it currently unsuitable for real-time interactive applications or deployment with massive scale models.
For future work, the authors suggest integrating more sophisticated look-ahead heuristics. Specifically, they propose training a lightweight secondary model (like an LSTM) to evaluate partial sequences as they are being built. This heuristic model could predict whether a path is likely to reach the constraint token down the line, allowing the B* algorithm to aggressively prune dead-end paths early on.
Summary updated