Searching Song Plans as Graphs, Not Trees

Music generators can now produce convincing 30-second clips, but full songs still wander. Keys drift, and a chorus that should come back never quite does. A promising fix is to write a plan first: a short list of sections with labels such as verse and chorus, and markers saying which sections should be repeats of one another. Audio is then rendered from that plan. Today the plan is written in one left-to-right pass and never revisited. The natural next step is to search over plans with a learned critic, the way game-playing programs search over moves. Classical search theory warns that this can go badly. When the critic's errors grow with the distance still to go, search effort explodes exponentially. The explosion is worse when the space contains many different routes to equivalent situations and the search treats each route as new.

This note proposes to build a plan-level search for full-length songs that merges equivalent partial plans instead of re-exploring them. It also proposes to measure, rather than assume, how the critic's error grows as the unfinished part of the song gets longer. The central claim is testable. Look-ahead search beats simply sampling many complete plans and keeping the best one only when songs have many recurrence constraints, and only when partial-plan critic error grows slowly with the number of remaining sections. Merging equivalent plan prefixes is what keeps expansion counts tractable under the critic errors we actually observe. Either outcome is informative. If best-of-N matches search, the field learns that plan-level search is unnecessary at current song lengths.

Core Claim

Two results from search theory motivate the work. First, Exactly How Good Are Heuristics? and Pearl's survey Heuristic Search Theory: Survey of Recent Results show the following for best-first search. If the absolute error of the estimate of remaining cost grows linearly with remaining depth, the number of expanded nodes grows exponentially. Growth stays polynomial only if error grows at most logarithmically. An Average-Case Analysis of Graph Search shows this as a sharp transition on job-sequencing graphs: more than 185,000 expansions under linear error versus about 15 under logarithmic error at $N=16$. Second, How Good is Almost Perfect? shows that in state spaces with transpositions (distinct paths reaching the same state), an estimate that is off by a single constant can still force expansion of about half the reachable states. The authors conclude that symmetry reduction, not better estimates, is what rescues search.

Music generation has not taken either lesson on board. Controlling Perceived Emotion in Symbolic Music Generation with Monte Carlo Tree Search shows that look-ahead decoding works. Its tree search over bars reaches 71% emotion accuracy on high-valence, high-arousal targets, against 59% for stochastic bi-objective beam search and 35% for conditional sampling. But it searches a plain tree, uses an emotion classifier and discriminator it knows to be error-prone, and never asks how those errors shape the search.

Our claim is that song structure is the right level at which to apply both lessons. Token-level states essentially never recur, because each depends on its entire history, so a transposition table (a cache of already-evaluated states) at the token level buys nothing. Plan-level states, by contrast, recur constantly. MusicLayout represents repeated sections as "families." Two prefixes that differ only in how families are named, or in small timestamp jitter, face identical futures. That makes the plan space a genuinely reconvergent graph where Helmert and Röger's analysis applies.

Research Program

We would build a planner in the style of MusicLayout on FreeMIDI. A language model emits layout tokens: segment boundaries, functional labels, family identifiers, and instrument-role tuples. These are rendered to audio by a frozen renderer, as in the original work. MusicLayout builds on ACE-Step 1.5; if its layout checkpoint is not available, we reimplement the layout stage on the same data. On top of this planner we add three components.

The first is a canonical state for partial plans. A prefix is mapped to four things: its quantized time position, its sequence of functional labels, its family assignment up to renaming, and a set of open obligations. An example obligation is "family 0 has appeared once and a return is expected." Prefixes with the same canonical state share a node, and the planner's continuation and the critic both see only the canonical form. That restriction is what makes merging sound. We will also study coarser abstractions, such as dropping instrument roles from the key, which merge more prefixes at the cost of information. The question is where on this trade-off search effort and quality are best.

The second is a partial-plan critic. It is a lightweight model that scores a layout prefix by predicting the Structural Clarity and Coherence of its best completion. It is trained on renders of sampled layouts, with labels from a scorer trained on SongEval. To avoid optimizing and grading with the same signal, evaluation uses a separately trained scorer, MuseCritic, and human raters. Obligations that become impossible to satisfy, for example when too little time remains for a promised reprise, prune a node and all its descendants outright. This is a direct use of the observation from Optimal Searches From AND and OR Nodes that failures are correlated across branches.

The third is an error-scaling measurement. For held-out prompts we estimate the true value of each prefix. We sample many completions, render them, and score them with the evaluation scorer. We then fit the critic's absolute error as a function of remaining sections $r$, comparing constant, logarithmic, and linear forms. Under the multiplicative model of On the Value of Good Advice, where A* expands roughly $d^{\epsilon k}$ nodes with branching $d$, relative error $\epsilon$ and depth $k$, the fitted error predicts an expansion curve. We then check whether tree search and graph search follow or depart from that prediction. That paper explicitly lists missing transpositions as a limitation of its tree model, and we test exactly that gap.

The search itself is best-first or PUCT over canonical nodes with a fixed budget of critic calls. The planner language model supplies the prior over next sections.

Baselines

The naive reference is the planner as MusicLayout uses it. It samples a single layout in one pass and renders it with no search. No numeric acoustic-boundary $F_{0.5}$ or $F_{3.0}$ values are reported on Lacuna for MusicLayout; the file states only that it outperforms MusicGen-Large and Stable Audio 3. We will therefore re-measure this baseline ourselves. Every method uses the same planner weights, renderer, prompts, and evaluation scorers.

The most dangerous simple competitor is best-of-N over complete layouts. We sample $N$ full plans, score each finished plan with the same critic, and render the winner, with $N$ set so that critic calls match the search budget. Plans are short, and complete plans are easier for a critic to score than prefixes, so this baseline may simply win at short lengths. Search counts as beating it only if it attains higher held-out Structural Clarity and Coherence at equal critic calls. We predict the gap opens as the number of family-recurrence constraints grows. The reason is that the probability that an unguided sample satisfies all of them should fall roughly geometrically, since each is an approximately independent chance of failure.

The strongest existing method is bar-level tree search following the emotion MCTS paper. We port PUCT with 50 iterations per step, as reported there, to operate over layout tokens with our critic as its value function, and give it the same critic-call budget. Its reported result, 71% emotion accuracy on the high-valence, high-arousal quadrant of VGMIDI, is on a different task. We therefore also run our graph search on that setting as a secondary check that merging does not hurt where recurrence is weaker. Beating it means equal or better quality with fewer expansions.

A trained-policy alternative fine-tunes the planner with GRPO (group relative policy optimization, a reinforcement-learning method) against the same critic, as MuseCritic does. We use matched total compute, counting both training and inference. Finally, the key ablation is identical search with merging disabled, which is the plain tree. It isolates the contribution of canonical states from that of the critic and the pruning.

Why not just…?

Why not just sample many full plans and keep the best? This is a real threat, and it is why the experiments sweep song length and constraint count rather than reporting one operating point. If best-of-N matches search across the whole sweep, we will report that plan-level search is unnecessary for three-minute songs. The error-scaling measurement would then explain why: partial-plan critic error would be too large to guide search better than finished-plan scoring.

Why not just fine-tune the planner with reinforcement learning against the critic? MuseCritic shows that scalar rewards cluster near the mean and give weak signal, and it needed critique-then-score to recover range. Even with a good reward, a fine-tuned planner still commits in a single pass with no backtracking. That is the failure mode MusicLayout itself lists as open, since a frozen renderer cannot repair an early layout error. The matched-compute GRPO baseline settles whether amortizing the critic into the planner is enough.

Why not just train a better critic instead of changing the search? Helmert and Röger's planning results suggest that in reconvergent spaces accuracy gains yield diminishing returns without merging. The (Un)Scalability of Informed Heuristic Function Estimation argues that exact learned estimates do not scale for hard search problems. We test this directly by training critics of increasing size and data. We then check whether the tree-versus-graph gap in expansions shrinks as critic error falls.

Why not just use a longer-context generator? PyramidCodec and ProGress both find that explicit hierarchy beats raw scale. ProGress's 3M-parameter model beats the 516M-parameter NotaGen, which suggests structure matters more than context length. Our proposal operates at the plan layer and is compatible with any renderer.

Proposed Experiments

The main experiment sweeps target song length and the number of required family returns, from one to about six. For each setting we compare all baselines at matched critic budgets. We report three things: held-out SongEval-scorer Structural Clarity and Coherence (the SongEval paper reports a UTMOS-based scorer reaching Pearson 0.912 with human averages); MuseCritic scores; and a self-similarity check on rendered audio, testing whether sections sharing a family actually sound related.

The decisive checks are three. First, the fitted error-versus-remaining-sections curve should predict where search starts to beat best-of-N, and where tree search blows up while graph search does not. If expansions under tree search do not grow faster than under graph search at matched critic error, the transposition argument fails for music. Second, the abstraction-coarseness study should show an interior optimum. Merging too little should recover tree-search cost, and merging too much should lose quality because states stop being Markov, meaning they no longer carry everything the future depends on. Third, a listening study with musically trained raters on the longest settings should confirm that scorer gains correspond to audibly clearer form and not to critic exploitation.