🤖 AI

Tonal parsimony in chord-sequence analysis: combining modulation cost and tonal vocabulary

This paper introduces a "tonal parsimony" algorithm that optimizes chord-sequence analysis by lexicographically minimizing both the number of modulations and the distinct tonal vocabulary, achieving more concise and harmonically accurate results than standard dynamic-programming approaches on large datasets of jazz and popular music.

Original authors: François Pachet

Published 2026-06-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: François Pachet

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Mapping a Musical Journey

Imagine you are listening to a long jazz song. To a musician, this song isn't just a random string of notes; it's a journey through different "neighborhoods" called keys or tonalities.

For example, a song might start in the neighborhood of C Major, wander over to A Minor, and then visit G Major. Musicians need to know which neighborhood they are in at any given moment to improvise (make up music on the spot) or to understand the song's structure.

The problem this paper solves is: How do we automatically figure out the best map of these neighborhoods for a long list of chords?

The Three Competing Strategies

The author tested three different ways to draw this map. Think of them as three different travel guides trying to plan a road trip for a musician.

1. The "Smooth Driver" (Transition-Only)

The Goal: Change neighborhoods as rarely as possible.
The Logic: If you are in C Major, stay there as long as you can. Only switch to a new neighborhood if you absolutely have to.
The Flaw: Sometimes, to avoid changing neighborhoods, this guide forces you to take a weird, indirect route. It might say, "Stay in C Major," even when the music clearly sounds like it's visiting a distant, unrelated neighborhood. It minimizes the number of stops, but it might use a huge, confusing list of different neighborhoods to get there.

2. The "Minimalist" (Pure Vocabulary)

The Goal: Use the smallest possible list of neighborhoods for the whole trip.
The Logic: "Let's try to fit this entire 5-minute song into just two neighborhoods, no matter what."
The Flaw: To keep the list of neighborhoods small, this guide forces you to jump back and forth wildly. You might be in Neighborhood A, jump to B, jump back to A, then jump to B again. It minimizes the list of places, but the driving is jerky and chaotic.

3. The "Smart Navigator" (Tonal Parsimony) — The Winner

The Goal: Do both, but in a specific order.
The Logic: First, make the driving as smooth as possible (minimize jumps). Then, among all the smooth routes, pick the one that uses the fewest unique neighborhoods.
The Result: This method finds the "Goldilocks" zone. It keeps the road smooth (like the Smooth Driver) but avoids using unnecessary, exotic neighborhoods (unlike the Minimalist). It realizes that if you can explain a chord using a neighborhood you've already visited, you should do that instead of inventing a new one.

The Secret Ingredient: The "Jazz Translator"

The paper also introduces a special tool called Jazz Substitution.

In standard music, a chord usually belongs to one specific neighborhood. But in Jazz, musicians often play "tricks." For example, they might play a chord that looks like it belongs to a different neighborhood, but they are actually using it as a "substitute" to keep the flow moving toward the original neighborhood.

Without the Translator: The computer sees a weird chord and thinks, "This doesn't fit here! We must have changed neighborhoods!" It creates a new, unnecessary stop on the map.
With the Translator: The computer understands the trick. It says, "Ah, this is a 'Tritone Substitute.' It looks weird, but it's actually just a fancy way of staying in the current neighborhood."

By adding this translator, the computer stops making fake stops. It realizes that the song is simpler than it first appeared.

What the Numbers Say

The author tested these methods on over 31,000 real chord sequences and 1,500 professionally analyzed jazz standards.

The Smooth Driver was good at keeping the road smooth but used too many different neighborhoods.
The Minimalist used very few neighborhoods but made the road incredibly bumpy.
The Smart Navigator (Tonal Parsimony) kept the road smooth (same as the Smooth Driver) but reduced the number of neighborhoods used by 55.8%.

When they added the Jazz Translator, the Smart Navigator became even better. It matched professional musicians' annotations 95.6% of the time. This means it was almost as good as a human expert at figuring out which scale a musician should play over a chord.

Why This Matters

This isn't just about math; it's about making music analysis that feels "right" to a human ear.

If you are a robot trying to play jazz, you need to know which neighborhood you are in to pick the right notes.
If the map is too choppy (too many jumps), you sound confused.
If the map uses too many weird neighborhoods, you sound like you're lost.

The "Tonal Parsimony" method creates a map that is both smooth and simple, making it the best tool for helping computers understand, analyze, and even generate jazz music that sounds natural to human listeners.

Technical Summary: Tonal Parsimony in Chord-Sequence Analysis

Problem Statement
The paper addresses the task of assigning local tonalities to a sequence of chords ( $c_1, \dots, c_n$ ). For each chord, a set of candidate tonalities $T_i$ is pre-computed based on chord-scale compatibility (typically the 12 major and 12 minor keys). The goal is to select a sequence of tonalities $x_1, \dots, x_n$ where $x_i \in T_i$ that optimizes global criteria.

Standard approaches utilize dynamic programming to minimize the modulation cost ( $C$ ), defined as the number of adjacent tonality changes ( $x_i \neq x_{i+1}$ ). However, minimizing $C$ alone does not constrain the total number of distinct tonalities used ( $K$ ). This can lead to analyses that are smooth in terms of transitions but utilize an unnecessarily large and complex tonal vocabulary. Conversely, minimizing $K$ alone (a hitting-set problem) often results in implausibly frequent modulations. The paper proposes tonal parsimony, a lexicographic objective that minimizes modulation cost first, and then minimizes the number of distinct tonalities among all solutions with the minimal modulation cost:
$\min_{lex} (C(x), K(x))$

Methodology
The authors model the problem as a finite-domain constraint optimization problem over a fixed universe of 24 tonalities ( $|T|=24$ ). They compare three specific optimization strategies:

Transition-only Dynamic Programming (DP): A standard Bellman recurrence that minimizes $C$ . It runs in $O(nm^2)$ time.
Pure NValue Minimization: A hitting-set approach that finds the smallest set of tonalities $S$ such that every chord has a compatible candidate in $S$ . This minimizes $K$ but ignores transition costs.
Tonal Parsimony (Lexicographic Optimization): The proposed method. It employs a specialized exact algorithm that combines a cost-regular path criterion with an $NValue$ criterion.
- Algorithm: The method decomposes the problem into finding minimal constant-tonality segments. It uses a two-phase approach: a backward pass to compute the minimum number of segments required from any position to the end, and a forward pass that extends partial segmentations only if they can still reach the global optimum.
- Pruning: The algorithm utilizes dominance pruning on labels $(i, t, S, C)$ , where $S$ is a bit-mask of used tonalities. A label is discarded if another exists at the same position and tonality with a lower or equal modulation cost and a subset of used tonalities.
- Complexity: While the problem is NP-hard in the general case (reducible from Hitting Set), it is fixed-parameter tractable with respect to the number of tonalities $m$ . With $m=24$ , the exponential dependence on $m$ is manageable in practice.

Substitution Layer
To address the limitations of literal chord-scale compatibility (which fails to capture common jazz functions like tritone substitutions), the authors introduce a weighted substitution closure.

This layer enriches the candidate domains $T_i$ by adding non-diatonic interpretations (e.g., interpreting $Bb7$ as a tritone substitute for $E7$ in the key of A).
These interpretations are pre-computed as a finite closure of recursive functional rules (e.g., secondary dominants, backdoor dominants, borrowed chords) and flattened into a standard finite-domain problem.
The optimization objectives remain unchanged; the substitution rules simply expand the search space, allowing the optimizer to find paths that are functionally coherent without introducing new tonal centers.

Key Contributions

Formulation: Defining tonal parsimony as a lexicographic optimization of modulation cost and tonal vocabulary size.
Algorithm: Providing an exact, specialized dynamic programming algorithm that solves this joint objective efficiently for the fixed 24-tonality universe, avoiding the scalability issues of generic constraint solvers (e.g., MiniZinc/Gecode).
Substitution Integration: Demonstrating how weighted jazz substitution rules can be integrated as a pre-processing step to expand candidate domains, improving the functional plausibility of the analysis without altering the core optimization logic.

Results
The methods were evaluated on two datasets: the LMD Chords corpus (31,032 sequences) and 1,555 professionally annotated jazz standards.

Corpus Statistics (LMD Chords):
- Tonal parsimony preserves the minimum modulation count of the transition-only DP while reducing the mean number of distinct tonalities ( $K$ ) in 55.8% of cases.
- With substitution enrichment, the mean number of tonalities drops from 3.802 to 3.206, and mean modulations drop from 16.728 to 12.141.
- The specialized Python implementation processes the full corpus in under one minute of CPU time, whereas a direct MiniZinc model fails to terminate on larger instances within hours.
Professional Validation (Jazz Standards):
- Tonal parsimony achieves 81.1% strict chord-scale agreement and 95.6% conservative compatible agreement with professional annotations.
- This outperforms both the transition-only DP (94.3% compatible) and the pure NValue method (94.3% compatible).
- In specific examples (e.g., The Gift, Nuages), the method successfully combines the low transition count of the DP with the compact vocabulary of the NValue method, resolving ambiguities where standard DP introduces unnecessary tonal centers.
CokerBench Validation:
- On 19 functional jazz examples, the substitution-enriched models solved 16/18 cases correctly regarding expected tonality counts and 13/15 regarding root analysis.
- The results indicate that many previous "optimization failures" were actually "missing domain" problems solvable by functional reinterpretation.

Significance and Claims
The paper claims that tonal parsimony offers a more musically intuitive and compact objective for harmonic analysis than transition-only minimization. By prioritizing smoothness (low $C$ ) but breaking ties with vocabulary size (low $K$ ), the method produces analyses that are both smooth and cognitively efficient for improvisation and reharmonization.

The authors emphasize that while the joint objective is combinatorially hard in general, the fixed nature of the major/minor tonal universe ( $m=24$ ) renders the problem tractable for professional-scale analysis. Furthermore, the study demonstrates that the optimized value $K$ serves as a meaningful structural descriptor of harmonic complexity, capable of distinguishing generated sequences into distinct regimes of tonal richness. The work concludes that minimizing both transition cost and tonal vocabulary is a viable and superior approach for jazz-oriented harmonic analysis, particularly when augmented with functional substitution rules.