Sound and Complete: Formally Verified Guitar Player
November 18, 2026
It has always been difficult for me to understand how much of music comes down to formulas and how much to creativity. While brainstorming projects for Vibecheck, a formal methods hackathon, I think I came up with a nice formulation of the problem. I realized many of the mathematical aspects of music come down to constraints, and the point of music is to be creative within these constraints. This is a category of problem that maps well onto formal methods.
My first idea was Bach-style counterpoint, which follows exact rules about how melodies can move against each other. But I wanted something that would make a better demo, so I looked at other kinds of music played under constraints and found that the blues fit surprisingly well. My brother and I built it over the weekend and won first place.
In call and response, a staple of the blues, one player plays a short phrase and the other answers it. In our app, Claude plays the calls and you answer on guitar. Before you start, you pick rules for your answers, such as playing fewer notes than the call or starting near the call’s last note. These constraints are what force you to be more creative. But some combinations of rules can’t be satisfied. For example, if you have to echo the call’s rhythm exactly, you need to play as many notes as the call did, so you can’t also play fewer. Claude has no way to definitely know whether its call can be answered under your rules.
Hence, every call is checked in Lean before it plays. A two-bar phrase has about 1040 possible answers, too many to try one by one, so the checker runs a search. We proved that the search finds an answer whenever one exists.
What the rules mean
The rules are the only trusted Lean in the project, since
everything else is proved against them. Each rule has a short definition in
Spec.lean. For example, the “Small steps” pedal means no two notes in a row are
more than k frets apart, with rests in between not counting, and its Lean definition
says almost exactly that. The whole file is about 120 lines.
We tested the spec too. SpecExamples.lean has proofs that the rules accept
answers a person would actually play, reject ones they shouldn’t, and catch conflicts like
the echo-and-say-less one above. The main proofs only show that the code matches the spec,
so if the spec said the wrong thing, these examples are where we’d catch it.
Sound and complete
The title comes from two properties of the search. It’s sound, meaning any answer it suggests really does keep every rule. It’s complete, meaning that if any answer exists, it finds one. Together they mean the app only says a call can’t be answered when that’s actually true.
Trying every possible answer isn’t an option. Each of the 24 slots in a two-bar phrase holds a rest or one of 49 notes, which comes to about 6×1040 phrases. Instead, each rule gets a small checker that reads an answer one slot at a time and keeps a little memory, like the last note it heard or how many notes have been played in the current bar. Two half-finished answers that leave every checker with the same memory can be finished in exactly the same ways, so the search only needs to keep one of them. In the hardest case we benchmarked, that brings 6×1040 phrases down to at most 1,568 half-finished answers per slot, and the whole search takes about a fifth of a second.
We proved the search sound and complete once, for any set of checkers. After that, each rule only needed its own proof that its checker passes exactly the answers its definition allows, and that it never gives up on an answer too early.
When no call can work
Checking a call is one question. A harder one is whether any call at all could work with your rules, and the app answers it before you play. If you turn on “echo the rhythm” and “say less,” it tells you right away that no answer could keep both.
This works because a call only affects your answer through a few things: its rhythm, its first few notes, and its last note. Given an answer, you can build the one call that suits it best, so it’s enough to search over answers alone, and the same search does the job. That means the warning comes from a proof, not from a list of contradictory rules.
What’s proved and what isn’t
The main theorems say that each checker means its rule, that the report card at the end marks each rule correctly, that every call you hear can be answered no matter what Claude proposed, and that the app says your rules are impossible exactly when they are. No proof is left unfinished, the proofs rely only on Lean’s three standard axioms, and Comparator confirms that they prove the theorems as stated. It came to about 4,000 lines of Lean.
Some parts aren’t proved. The app trusts that its pitch detection hears the notes you actually played, that it snaps your timing to the right slots, and that the code passing data between the browser and Lean doesn’t alter it. So the proofs cover the app’s decisions but not its hearing. If the mic mishears a bend, the report card will be right about the wrong notes.
What’s next
Right now Claude is only there to make the calls sound good. Everything it writes gets checked, and when none of its calls pass, the app plays a call our search found instead. Those calls can always be answered, but they’re plain, because the search only looks for a call that works, not one that’s worth playing.
The next step is to take Claude out of the loop and instead play guitar directly with Lean. I would augment the search to find a call that is both answerable and interesting. The hard part is defining “interesting” precisely enough to write down in Lean. My first thought is to score calls on things like rhythmic variety, the shape of the line, and landing on chord tones, and have the search return the highest-scoring call instead of any call that satisfies hard constraints, like a weighted partial MaxSAT problem. The search already goes through every reachable state slot by slot, so finding the best call should take about the same work as finding one that works. Then every call would come from the proven search, with no LLM involved.
The code is on GitHub, with instructions for running it. It works best in Chrome with headphones and an electric guitar plugged into your laptop through an audio interface. A laptop mic picking up an acoustic guitar also works, though in my experience it’s not ideal. I'm hoping there is more work at the intersection of formal methods and music!