Systems that generate music on request usually fail quietly. You ask for "the melody returns in bar 17, a fourth higher, over a cadence," and you get something close. When it goes wrong, nothing tells you whether the system misread the request, planned the piece badly, or simply ignored its own conditioning. We propose treating a piece of music like a scene in computer vision: a graph whose nodes are voices or phrases and whose edges are musical relations. Examples of such relations are "imitates," "harmonizes," "is a variation of, transposed by $k$," and "cadences into." A requested piece then becomes a small program that builds this graph. The program is written in two parts. A neural model drafts a sketch, a partial program with blanks called holes. Each hole is confined to one node of the graph over a short time window. A bounded symbolic solver then fills each hole. It tries notes in the order the neural model ranks them and returns the first completion that satisfies every relation touching that node.
This layout gives two things together. First, the search stays small: each hole is local, so the solver never has to search over the whole piece. Second, every note in the output can be traced to either a sketch decision or a solver fill, and every unmet request can be traced to a specific node or edge. That makes the system auditable in the way diagnostic medical models are, where a prediction is grounded in intermediate evidence a person can check. Here the explanation is faithful by construction, because the trace is the actual computation that produced the output, not a summary written afterwards.
Core Claim
Our central claim is that long-horizon relational controls are best handled by learned sketches with holes scoped to individual graph nodes, filled by a solver ordered by the neural model's preferences. Long-horizon relational controls here means thematic return, transformed variation, inter-voice relations, and cadence placement across 32 or more bars. We expect this approach to satisfy such controls exactly and far more often than end-to-end neural generators or rule-based rejection, at comparable musical quality. It also yields failure traces that correctly localize injected faults.
Three ingredients are each borrowed. The fourth is ours. The sketch-with-holes recipe comes from Learning to Infer Program Sketches (SketchAdapt), where a neural model writes a partial Lisp program and an enumerator fills holes within a time budget. That paper reports 90.0% on AlgoLisp, against 7.3% for the enumerator alone and 88.6% for the neural generator alone. SketchAdapt also names the failure we must avoid: holes that cover too much hit a combinatorial wall. The idea of letting a network order the solver's choices comes from DeepCoder, which predicts which primitives a program uses in order to speed up search. The graph view of music comes from ProGress and Graph-based Polyphonic Multitrack Music Generation. ProGress places scale degrees and voice-leading edges in a graph diffusion model. The second paper uses chord-level graphs with track, onset and next edges.
What is new is the scoping rule. Holes are defined by the scene graph rather than by program syntax, and the sketch model is trained to place holes so that each local fill is solvable within budget. Because of this, the cost of search is roughly $$C \approx \sum_{h} |V_h|^{L_h}$$ rather than $|V|^{L}$. Here $h$ indexes holes, $V_h$ is the set of note events allowed for hole $h$ after its neighbouring constraints are applied, $L_h$ is the hole's length in events, $V$ is the global event vocabulary, and $L$ is the full piece length. The form follows directly from searching holes independently once their boundary relations are fixed by the sketch.
How this differs from the closest work
ProGress is the nearest musical relative. It enforces voice-leading rules by rejection sampling after diffusion, depends on a fixed rhythmic skeleton, and is evaluated only on Bach chorales. In our system, constraints guide the search instead of pruning finished samples, and rhythm is part of what holes contain. Cosenza et al. report that their graph model degenerates into loops when stretched from 2 to 16 bars. We address this with explicit "variation-of" edges that carry a transformation program, such as transposing, inverting, augmenting or re-rhythmizing a source phrase. Development across sections is therefore stated in the graph rather than hoped for.
SceneCraft is the nearest structural relative. It parses text into a relational scene graph, has a language model write Blender code, and repairs the code with a visual critic. It reports 88.9% constraint satisfaction against 5.6% for unstructured BlenderGPT. SceneCraft's search is "generate whole program, critique, regenerate." Ours is "generate sketch, solve locally, report which hole failed." This is closer to counterexample-guided synthesis (CEGIS modulo theories), which separates structural search from constant solving.
XNMs shows that programs executed over scene graphs give fully transparent reasoning. It reaches 100% on CLEVR with true graphs, using 0.22M parameters. It never synthesizes programs under search pressure and has never been applied to temporal or musical graphs. We take its claim that the trace is the explanation and apply it to generation.
The interpretability motivation comes from diagnostic imaging. PN-SAMP predicts clinical attributes alongside malignancy. Pisov et al. force midline estimates through a coordinate bottleneck that yields calibrated intervals. Both also constrain our design. Bottlenecks can drift away from the computation they claim to explain, and rigid structural assumptions break on unusual inputs. We avoid the first problem by making the bottleneck executable. We treat the second as a measured risk: pieces whose structure the graph vocabulary cannot express should produce unsatisfiable-spec reports, not silent garbage.
Research Program
The representation. A musical scene graph has nodes for (voice, phrase-span) entities. Each node carries attributes: role (melody, bass, accompaniment), register, note density and metrical position. Edges are typed relations with parameters: harmonizes-under with a chord label, imitates at an interval and delay, variation-of with a transformation, cadences-into with a cadence type, and doubles. A small domain-specific language realizes these graphs. Its primitives emit notes into a node, its combinators apply the edge transformations, and holes stand for unspecified note content within a node and window.
Training pairs. We obtain (graph, program, piece) triples by analysing existing symbolic music. This step is where earlier attribute pipelines such as MuseCoco and TeleMelody became brittle, because they relied on heuristic extractors. We limit that risk in two ways. First, we use corpora where the hard labels already exist: POP909 supplies separated melody, bridge and piano tracks with chord and beat annotations, and Bach chorales supply four explicit voices. Second, we detect variation-of and imitation edges by exact symbolic matching over a finite transformation set. These relations are verified rather than guessed.
The sketch model. A Transformer encodes the graph spec and decodes a sketch program. Following SketchAdapt, the training target for each spec is the most concrete sketch whose holes the solver can fill within a time budget $T$. This target is found by hole-ifying the true program node by node and keeping the deepest hole-ification that still solves. Hole boundaries are restricted to node-and-window units, which is the scoping rule.
The solver. For each hole, a finite-domain enumerator proposes candidate note sequences in the order given by a small neural scorer, trained as a language model over node content. It checks every edge incident to the node and returns the first candidate that passes. If no candidate passes within budget, the hole is reported as failed, together with the edges that rejected the best candidates.
The diagnostic layer. Each output note is tagged with its origin, either sketch or a specific hole fill. Each requested relation is tagged satisfied or unsatisfied, and unsatisfied relations carry a cause: the sketch omitted it, the solver timed out, or the spec is unsatisfiable. Unsatisfiability is confirmed by exhaustive search on small holes.
Baselines
The naive reference point is the unconditioned and lightly conditioned GPT-2-style Transformer released with POP909. That paper reports a next-token test accuracy of 54.5% (POP909). This metric is not comparable to constraint satisfaction. We retrain the model with the relational spec serialized as a text prefix, which gives the "just condition on it" floor.
The strongest attribute-conditioned neural generator is a MuseCoco-style pipeline: the spec is flattened to attributes and fed as a prefix to a Transformer. MuseCoco reports an average sample-wise attribute accuracy of 77.59% at base scale and 87.15% at 1.2B parameters on its own attribute set (MuseCoco). It also reports 4.06/5 musicality and 4.15/5 controllability in a comparison against GPT-4 writing ABC notation. We retrain it at matched parameter count on our training split with the relational spec as prefix. For relational constraint satisfaction on POP909 or Bach chorales, we found no reported result on Lacuna. Its number on our metric will therefore be measured, not quoted.
The strongest constraint-enforcing neural method is the same Transformer with grammar-masked constrained decoding plus beam search with backtracking. Tokens that would violate a local rule are masked, and beams that dead-end are abandoned. It receives the same wall-clock search budget as our solver.
The structured-graph competitor is ProGress-style generation with post-hoc rejection on Bach chorales, using its own fixed rhythmic skeleton. That paper reports only a listening study (significantly more enjoyable, fewest "weird or bad" flags) and no scalar we can quote. We run it under the same rejection budget measured in solver calls.
The LLM-coder competitor follows SceneCraft. A large language model is given the DSL documentation and the spec, writes the full program, and receives verifier feedback in a loop for the same number of rounds and tokens our method spends.
The synthesizer-only reference is the enumerator with no sketch and uniform ordering. On AlgoLisp the analogous baseline scored 7.3% (Learning to Infer Program Sketches).
The ablations isolate the key ingredient. In one, hole boundaries are fixed-size windows ignoring the graph. In another, the sketch model is generator-only with no holes. In a third, the solver's ordering is uniform instead of neural. In a fourth, the graph is replaced by a flat attribute vector. All systems share training data, a matched parameter budget for neural parts, equal hyperparameter search trials, and an equal wall-clock budget per piece at generation time.
Beating a baseline means a higher exact relational constraint satisfaction rate at 32+ bars, with a confidence interval that excludes the baseline. It also requires that listening-study quality not be statistically worse.
Why not just…?
Why not just use constrained decoding on a strong Transformer? This is the real threat. Masking illegal tokens already guarantees local rules such as no parallel fifths. Its weakness is global relations whose satisfaction depends on content not yet generated, such as "bar 17 restates bars 1–4 transposed up a fourth over a perfect cadence." Greedy masking either cannot express these or commits early and dead-ends, and backtracking over a whole piece is exactly the $|V|^L$ search our scoping avoids. The experiment that settles this is satisfaction rate as a function of edge span, the distance in bars between the endpoints of a relation. If constrained beam search matches us at long spans within equal budget, the search contribution collapses. The paper then becomes a claim about diagnostic traces alone, and we would say so.
Why not just have an LLM write the whole program and repair it with a critic, as SceneCraft does? SceneCraft's own gap over unstructured BlenderGPT (88.9% vs 5.6%) shows that structure matters. It does not show that whole-program regeneration is efficient, and a critic loop never says which part to keep. We measure satisfaction per unit of compute and the number of repair rounds. We also test whether the LLM's failures are localizable at all. If the LLM coder matches our satisfaction at lower cost, we would adopt it as the sketch generator and keep only the scoped solver and trace.
Why not just sample from a good generator and reject violations, as ProGress does? Rejection cost grows with the number of constraints that must hold together, since each sample must pass all of them. The ablation that varies constraint count per piece from 2 to 20 should show rejection's acceptance rate collapsing while ours degrades gracefully. If it does not, rejection is the simpler answer.
Why not just read attention maps to diagnose failures? The imaging work cited above found that post-hoc saliency does not give verifiable evidence. More concretely, our fault-injection test below gives attention maps from the MuseCoco-style baseline the same localization task. They must point to the faulty bar and voice as accurately as our traces do.
Proposed Experiments
The main test runs on POP909 full songs cut into 32- and 64-bar excerpts, using graphs extracted from held-out songs as specs. The primary metric is exact relational satisfaction rate, broken down by edge type and edge span. Secondary metrics are per-piece solver time, the fraction of holes solved within budget, a repetition statistic (proportion of bars that exactly duplicate an earlier bar without a spec edge requiring it), and a blind listening study with musicians.
The predicted decisive pattern is as follows. All neural baselines degrade as edge span grows. Graph-scoped holes stay flat. Fixed-window holes fall between, because windows that cut across a node force the solver to resolve relations it cannot see. If the fixed-window ablation matches graph-scoped holes, the scene-graph contribution is not supported.
On ComMU, which pairs 11,144 composer-made samples with 12 metadata tags including track role, we test whether node attributes alone are controlled as accurately as by the MuseCoco-style baseline. This guards against our method winning on relations while losing on simple attributes. On Bach chorales we compare against ProGress for voice-leading violation counts and listener preference, with rhythm generated rather than given.
The diagnostic test injects known faults. We corrupt the sketch model so it drops a specific edge type, tighten a node's register until its hole becomes unsatisfiable, and insert contradictory edges. We then score whether the trace names the correct cause and location, comparing against attention-based localization from the neural baseline. A second, smaller study gives musicians failing outputs and asks them to repair the spec, measuring time to a satisfying revision with traces versus without.
Finally, we report where the graph vocabulary fails. These are excerpts whose extracted graphs are unsatisfiable or whose listening scores fall sharply. Following Pisov et al., we treat breakdown of the structural prior on unusual inputs as a result to measure, not hide.
References
- Learning to Infer Program Sketches
- DeepCoder: Learning to Write Programs
- ProGress: Structured Music Generation via Graph Diffusion and Hierarchical Music Analysis
- Graph-based Polyphonic Multitrack Music Generation
- SceneCraft: An LLM Agent for Synthesizing 3D Scene as Blender Code
- Counterexample Guided Inductive Synthesis Modulo Theories
- Explainable and Explicit Visual Reasoning over Scene Graphs
- Joint learning for pulmonary nodule segmentation, attributes and malignancy prediction
- Incorporating Task-Specific Structural Knowledge into CNNs for Brain Midline Shift Detection
- MuseCoco: Generating Symbolic Music from Text
- TeleMelody: Lyric-to-Melody Generation with a Template-Based Two-Stage Method
- POP909: A Pop-Song Dataset for Music Arrangement Generation
- ComMU: Dataset for Combinatorial Music Generation