Stable Matching as a Verifiable Training Ground for Iterative Reasoning

Language models trained with reinforcement learning on math problems get better at other subjects too, but one skill barely improves: running a procedure for many rounds while keeping track of a changing state. Stable matching is a textbook case of that skill, and current models fail at it badly. Stable matching pairs two groups, such as users and servers or workers and jobs, so that no two agents would both prefer each other over their assigned partners. When the market grows to 50 agents per side, almost every frontier model produces zero correct stable matchings, and supervised fine-tuning on execution traces does not help at that size (Matching Markets Meet LLMs).

We propose treating stable matching as a training domain rather than only a test. It has four properties that math lacks. New instances cost nothing to generate. Difficulty can be set exactly through market size and how correlated the preferences are. A proposed answer can be checked in quadratic time. Most importantly, the standard algorithm maintains simple invariants that can be checked after every round. That makes it possible to reward each correct round of execution without comparing against one fixed reference trace. The claim is that reinforcement learning with this round-by-round, reference-free reward gets past the size-50 failure point, and that the multi-round state-tracking skill it teaches carries over to code-execution and symbolic-reasoning benchmarks better than math-based training does at equal compute.

Core Claim

The standard algorithm for stable matching is Deferred Acceptance, also called Gale-Shapley. In each round, every unmatched proposer proposes to the next agent on its list. Each receiver tentatively holds the best proposal it has seen so far and rejects the rest. The final matching does not depend on the order in which proposals are processed. As a result, many different execution traces are equally valid, and three facts can be checked locally at every round. First, each proposer approaches receivers strictly in its preference order and skips no one. Second, each receiver holds its most-preferred proposer among all proposals it has received. Third, no rejected proposer returns to a receiver that rejected it.

Supervised trace imitation, the approach that failed in Matching Markets Meet LLMs, punishes any departure from a single canonical trace and gives no signal about where an execution first went wrong. We instead reward the valid prefix of the model's own execution:

$$ r(\tau) = \alpha \cdot \frac{k^*(\tau)}{K} + (1-\alpha)\cdot \mathbb{1}[\text{final matching is stable}] $$

The symbols are defined as follows. $\tau$ is the model's structured trace of rounds. $k^*(\tau)$ is the number of rounds completed before the first invariant violation. $K$ is the number of rounds needed to finish on that instance. $\alpha \in [0,1]$ balances the process reward against the outcome reward. Cutting credit at the first violation keeps the model from earning reward for fluent but wrong text that follows an early mistake.

The prediction has two parts. The first is in-domain: models trained on markets of size 20 or smaller should solve size-50 markets with random preferences at clearly above the best reported rate. The second is transfer: the gains should concentrate on benchmarks that require stepping through state, such as predicting code output, rather than on single-shot question answering.

Where This Sits

Prior work divides into three groups.

The first group motivates the gap. Matching Markets Meet LLMs built a four-tier benchmark: understanding preferences, detecting blocking pairs, repairing unstable matchings, and generating a stable matching. A blocking pair is two agents who would both rather be with each other than with their assigned partners. The benchmark contains 2,850 questions across 300 preference profiles, drawn either from random preferences ("Impartial Culture") or from preferences where one side shares a single ranking ("Master-list"). It documents the failure at size 50 and shows that LoRA fine-tuning on 10,000 traces fixes small instances but not large ones. It also finds that repairing an unstable matching is harder than solving from scratch, because local fixes create new blocking pairs. We keep its benchmark and its supervised baseline, but we replace imitation with reinforcement learning under a verifier.

The second group supplies the method and is also our main competitor on transfer. CPL trains on grade-school and competition math using search over high-level plan steps and step-level preference optimization, and reports gains on coding and science. Satori teaches a model to reflect and backtrack within one output sequence and reports gains on out-of-domain logic and code-execution benchmarks. Both use math as the source domain. Math offers no cheap check on intermediate steps and no exact dial for how long a procedure runs. That is why the file lists multi-round algorithmic loops as the place where transfer remains weakest. We keep their reinforcement learning machinery and change the source domain and the reward.

Reasoning Vectors extracts reasoning gains as a weight difference, the reinforcement-learned weights minus the supervised weights, and adds that difference to other models in the same family. We use it only as a secondary portability test, not as the core mechanism.

The third group sets the application regime. Network resource allocation work turns channel gains, delays, and trust scores into preference lists and runs Deferred Acceptance under capacity quotas (satellite incentive survey; D2D video allocation; FedMint). Here a device-to-device (D2D) link connects two phones directly without routing through a base station. Dynamic edge-computing work stresses that recomputing allocations every time a user arrives is too slow (online MEC allocation). These papers supply our held-out variants: many-to-one markets with quotas and ties, and repair after an arrival or departure. We do not claim a language model should replace a network matching solver.

The closest work at the intersection, When AI Agents Compete for Jobs, uses Gale-Shapley as a fixed central clearinghouse and improves agents only through prompting. None of these papers trains a model on matching and measures what transfers elsewhere.

Research Program

We will build a generator and verifier for three training tasks. The first is full Deferred Acceptance execution in a fixed round-by-round output format. The second is blocking-pair detection with a witness: the model must name an actual blocking pair or state that none exists. The third is repair: the model receives a stable matching plus a perturbation, such as a new agent, a departing agent, or a changed list, and must return a stable matching.

Instances come from both preference distributions. A curriculum raises market size from 5 to 20. Sizes 30 through 50 are never seen in training. Ground truth for the capacity-quota and tie variants is computed with a standard solver; MATWA is one available toolkit. The repair task gets outcome reward only, since repair has no single canonical procedure.

We will train with GRPO, a reinforcement learning method that scores each answer against a group of other answers sampled for the same prompt. The base models are Qwen-2.5-Math-7B-Instruct, chosen so results are comparable to Satori, and the 8B DeepSeek model that Matching Markets Meet LLMs LoRA-tuned, chosen so the supervised comparison uses the same model. All runs share one compute budget measured in generated tokens. Every model answers without tool calls or code execution, because the question is what the model's weights learn.

Baselines

The "do nothing" reference is the untuned base model on every benchmark. On the matching benchmark the reported bar is concrete. Matching Markets Meet LLMs reports a 0% success rate for almost all models on size-50 random-preference generation, and 8% for Gemini 2.5 Pro, which is the strongest reported number. Beating the reported state of the art in-domain means a 7–8B model exceeding 8% on that split.

The supervised baseline reproduces that paper's LoRA training on 10,000 execution traces with the same base model and the same instance sizes. The paper reports 0% improvement at size 50. We add one change that makes it stronger: we give it the same token budget as our reinforcement learning runs, so that "more data" cannot explain any gap.

The strongest transfer competitor is math reinforcement learning in the style of Satori and CPL, run on the same base model and budget. Satori reports that the average across its math benchmarks rises from 59.9% to 64.4%, and AIME2024 from 16.7% to 23.3%. CPL reports +12.2% on HumanEval and +8.6% on GPQA over DeepSeekMath-7B. For CRUXEval, BGQA, and TableBench, where Satori claims out-of-domain gains, no reported absolute result was found on Lacuna. We will therefore re-run this baseline ourselves rather than borrow numbers. Beating it means a larger gain on CRUXEval and BBH at equal compute, without losing more than a point or two on GSM8K or MATH.

A procedural-control baseline runs GRPO with outcome reward on other generated algorithmic tasks, such as multi-step sorting and breadth-first search traces, at matched budget. This separates "matching is special" from "any synthetic multi-round procedure helps."

Two ablations isolate the key ingredients. The first compares the invariant-prefix reward ($\alpha>0$) against outcome-only reward ($\alpha=0$) on identical matching data. The second removes the repair task. As a secondary check, we extract the weight difference between the matching-trained and base models and add it to the 1.5B Qwen2.5 model. For comparison, Reasoning Vectors reports +12.3% on BBH at 1.5B from a GSM8K-derived vector.

Why not just…?

Why not just have the model call a Gale-Shapley routine? For fixed preference tables, this wins outright: a tool call reaches 100% at any size, and we will report it as the in-domain ceiling. We do not claim to compete with it. Matching serves here as a training signal for multi-round state tracking, and a tool call teaches the weights nothing that transfers to predicting the output of arbitrary code. The transfer benchmarks are where this proposal succeeds or fails.

Why not just scale supervised trace fine-tuning? The file's own evidence is against it: LoRA reached 100% on some small subsets but gave 0% improvement at size 50 (Matching Markets Meet LLMs). Our budget-matched supervised run tests whether that was just a data shortfall. If budget-matched supervised training reaches the same size-50 accuracy as our method, the reinforcement learning component is unnecessary, and we will say so.

Why not just do math RL, which already transfers? Math training does transfer to science and coding (CPL). It cannot check intermediate rounds cheaply, though, and the file flags iterative algorithmic loops as the place where transfer stays fragile. The matched-compute comparison on CRUXEval and BBH settles this directly. We also test the combination, a math-plus-matching mixture, because the useful outcome may be that the two are complementary.

Why matching instead of any synthetic procedure? This is the most serious threat. If the sorting and breadth-first-search control matches our transfer gains, the contribution shrinks to "invariant-checked process rewards on procedural tasks." That is still worth reporting, but it is not a claim about matching. Our reason to expect a difference is that matching requires tracking two interacting sides at once, and repair forces the model to follow cascading consequences. The procedural control measures whether that difference exists.

Proposed Experiments

The decisive in-domain check trains only on markets of size 20 or smaller and evaluates on the size-50 random-preference split of the matching benchmark. The metrics are exact stability rate, mean blocking pairs per output, and the position of the first invariant violation. If the outcome-only ablation stalls near 0% while the invariant reward rises, the round-by-round reward is doing the work.

The repair check measures stability after perturbation, plus the number of new blocking pairs each edit introduces. This tests whether training on repair reverses the paper's finding that repair is harder than generation.

The held-out-structure check evaluates, with no further training, on many-to-one markets with capacity quotas and ties, shaped after edge-server and federated-client assignment (FedMint).

The decisive transfer check compares all conditions at equal token budget on CRUXEval, BBH, TableBench, FOLIO, and CrossWordBench, with GSM8K and MATH as guards against forgetting. We will also break results down by how many steps each benchmark item requires. The hypothesis predicts that gains grow with the number of iterations an item needs. Flat gains across step counts would count against it, even if the average improves.