Incorporating Structure and Chord Constraints in Symbolic Transformer-based Melodic Harmonization

Maximos Kaliakatsos-Papakostas, Konstantinos Soiledis, Theodoros Tsamis, Dimos Makris, Vassilis Katsouros, Emilios CambouropoulosarXiv 2025 · DOI · arXiv

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:

  1. ChordSymbolTokenizer (CS): Treats chords as holistic symbols (e.g., C:maj).
  2. PitchClassTokenizer (PC): Spells out chords note-by-note using their constituent pitch classes (e.g., chord_pc_0, chord_pc_4, chord_pc_7).
Examples of the two chord tokenization strategies across musical bars.

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.

Figure 1: Simplified illustration of two algorithm steps. The left side shows that the children of the blue and green nodes are better rated than the children of the red and purple nodes. However, they fail to reach the constraint and on the next step (right side) the children of the red and purple nodes are tried out, since they are are better scored than the next best children of the red and blue. One of the children of the purple node achieves the constraint and continues from this point on using the typical beam search algorithm.

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

Abstract

Transformer architectures offer significant advantages regarding the generation of symbolic music; their capabilities for incorporating user preferences toward what they generate is being studied under many aspects. This paper studies the inclusion of predefined chord constraints in melodic harmonization, i.e., where a desired chord at a specific location is provided along with the melody as inputs and the autoregressive transformer model needs to incorporate the chord in the harmonization that it generates. The peculiarities of involving such constraints is discussed and an algorithm is proposed for tackling this task. This algorithm is called B* and it combines aspects of beam search and A* along with backtracking to force pretrained transformers to satisfy the chord constraints, at the correct onset position within the correct bar. The algorithm is brute-force and has exponential complexity in the worst case; however, this paper is a first attempt to highlight the difficulties of the problem and proposes an algorithm that offers many possibilities for improvements since it accommodates the involvement of heuristics.
BibTeX
@misc{kaliakatsospapakostas2025incorporating,
  author = {Maximos Kaliakatsos-Papakostas and Konstantinos Soiledis and Theodoros Tsamis and Dimos Makris and Vassilis Katsouros and Emilios Cambouropoulos},
  title = {{Incorporating Structure and Chord Constraints in Symbolic Transformer-based Melodic Harmonization}},
  year = {2025},
  eprint = {2512.07627},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2512.07627},
}
Figure