acceptodds
Under review as a conference paper at ICLR 2027

Beyond Matching Stability: Solution Selection in Large Language Models

Abstract

Matching problems can have several stable matchings that favor different sides of a market. We measure which stable matching LLMs choose, comparing generic requests for a stable matching with explicit requests for a stable matching that is optimal for neither side of the market. On the same 50 markets with five participants per side and one response per market and request, Opus 5.5, Fable 5.1, and GPT-6 Astra return one side's optimum on 100% of generic requests, yet produce the requested alternative on 98 to 100% of explicit requests, with or without an assurance that one exists. Their one-sided default therefore does not come from an inability to find other stable matchings. GPT-6 Sol, GPT-6 Luna, and GPT-5.6 Terra follow the explicit request less reliably. Across six framings of these markets, the favored side is the one that meets at least two of three conditions: the prompt calls it "Group 1", lists its preferences first, and uses its members as the keys of the requested JSON answer. Evaluations should therefore measure the default choice and compliance with a stated selection rule alongside stability. We also discuss the implications of these results for using LLMs as neutral referees in allocation problems.

Primary area:
foundation or frontier models, including LLMs
Keywords:
stable matching, large language models, empirical evaluation, solution selection, algorithmic reasoning, prompt sensitivity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_AFUsOpenReview ↗
Rating
2
Confidence
3
Informativeness
3(+1)
Presentation
2
Soundness
3(+2)
Read review
Paper summary

This work studies which stable matchings LLMs select when multiple stable matchings exist, and how prompt framing influences that selection. Using small two-sided markets where the full stable set can be enumerated, this work pairs a generic request for a stable matching with a request for a stable matching that is neither side-optimal.

At last, they find several frontier modes that deal almost exclusively with one side's optimum under generic prompts yet can reliably produce non-endpoint stable matchings on the same instances when asked; and that the favoured side can be flipped by changing neutral-seeming prompt formats.

Critical strengths

The work focuses on selection among admissible stable matchings, rather than only feasibiity/stability or proposer-optimality. Filling a gap in current LLMs for matching evaluations.

Other than that, it introduces a paired evaluation on shared data, allowing strong within-instance comparisons that isolate default choice vs. capability to comply with a selection rule.

At last, clever use of distance-matched negative markets to probe non-existence reporting beyond trivial cues.

Critical weaknesses

There seems to be some issue with work; experiments are restricted to N=5 with strictly random preferences, where generalisation to larger markets or structured/correlated preferences is untested for the core selection findings.

Single-shot generations per market/request with no measurement of within-instance variance or sensitivity to stochasticity.

Use of different clients/system prompts and undisclosed sampling/compute defaults across providers introduces confounds that prevent attributing effects solely to model weights.

Other than the above, the assured vs unassured request changes two degrees of freedom at once, making it hard to isolate which element drives behaviour changes.

The JSON schema for the unassured case conflicts with instructions to withhold a matching, affecting withholding compliance; while noted and partially controlled, it remains a confound.

At last, limited exploration of alternative, normative selection objectives across all models; only a few supplementary workings were tested on a subset of models.

Questions for authors

The things mentioned in the weaknesses raise some questions, such as:

  1. Can you disentangle the effects of existence assurance vs permission to abstain by adding an ablation where you assure existence but also allow abstention or vice versa? This would clarify which change drives model behaviour.

  2. How stable are the framing effects under repeated sampling for the same market and prompt? Do model selections vary or remain locked to the same side's optimum?

  3. Did you try a DA step-by-step prompt that forces the model to choose the proposing side, and then vary which side is designated as proposer? Would that directly confirm the hypothesised mechanisms behind the framing-induced endpoints?

  4. For the instruction to withhold a match on nonexistence, if you provide a null matches schema and eliminate the conflict, do models still differ in withholding compliance? Any preliminary evidence?

  5. You show that several models can produce non-endpoints reliably. Do they concentrate on specific endpoints within a market or diversify across the non-endpoints?

I would or could raise the rating if the justification seems convincing enough.

4 comments

Thank you for the questions!

Q1 and Q4 (assurance versus permission; a null schema): We crossed the assurance with the permission sentence under a schema that allows a null matching on the positive markets, and ran the permitted request under that schema on the 50 negative markets, with the populated schema rerun as a control (Table 29). The assurance drives false nonexistence claims: with it, Sol, Terra, and Luna make 0 to 1, 2 to 3, and 11 to 13 such claims on the 50 positive markets; without it, 7, 5 to 11, and 30 to 32. The permission sentence changes little, except for Terra without the assurance (11 against 5). Opus, Fable, and Astra succeed in all four cells (47 to 50). On the negative markets, the null schema leaves withholding within two markets of the populated control for every model. Opus 5.5, which withheld the matching on 40 of the 50 negatives in Table 6, withholds on 49 in the control and on 50 under the null schema, so its earlier lapses vary between runs of the same prompt as Section 5 reports in the updated draft.

Q2 (repeated sampling): Astra gives the same outcome in all five draws on every market, under both requests and both opposing framings. One more draw from Opus 5.5 repeats its original outcome on every market except one where the original assured answer was unstable. Sol's generic outcome repeats in all five draws on 48 of 50 markets and each opposing framing on 19 of 20. Terra and Luna vary more, mostly between stable and unstable answers: Across 200 generic draws they return Group 1's optimum 141 and 155 times, and Group 2's 5 and 13 times (Table 28).

Q3 (mechanism): With a named proposing side, Opus, Fable, and Astra return that side's optimum on 50 of 50 for each side, Sol on 48 and 49, and Luna on 44 and 44; Terra's answers are often unstable (25 and 29 successes; Table 30). Without the instruction, Opus 5.5 and Fable 5.1 name the favored side as proposer in 346 and 325 of 350 responses (Table 5). So the endpoint follows the stated proposer.

Q5 (which non-endpoint): They concentrate near Group 1's optimum: 126 of 135 at N = 5 (86.5 expected under uniform choice; Table 17), and at N = 10, on the 27 markets with two to eight non-endpoints, 122 of 132 for all models but Luna (69.5 expected; Table 27). Opus and Astra return the same alternative in every repeated draw on 12 and 10 of the 12 markets with several.

The central comparisons are all within one model and client but Appendix A.2 lists every setting in detail.

Reviewer_AFUsOpenReview ↗

Response to the Authors

Thanks for the rebuttal. In Table 31, an independent written prompt (set 1/ set 2) breaks the "favoured side meets two of three conditions" rule. Five out of six models favour set 1 even when set 2 is listed first and keys the answer. So the existence of one-sided default looks robust, but the specific three-condition rule seems to depend on the template. The abstract states that the rule has general findings, so the authors should tone it down. In any case, I have increased my score of soundness from 1 to 3 and informativeness from 2 to 3.

Thank you for taking the time to review this!

We agree with your reading of Table 31: The one-sided default holds under both prompts, and the two-of-three rule is specific to the main prompt. In the revised abstract, the rule is replaced by "Which side the default favors depends on the framing and wording of the prompt." In the introduction, the Set 1 result now follows the rule directly.

If this resolves your remaining concern, we would be grateful if you would reconsider your overall rating!

Reviewer_AFUsOpenReview ↗

Response to the Authors

As said previously, and in your new response, I acknowledge, but I will maintain my overall ratings.

Reviewer_jqPKOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies stable matching using LLMs and which group they favor under different prompts: generic vs. explicit.

Critical strengths

The experiments are clean.

Critical weaknesses

The scope and insight are limited.

Questions for authors

What insight does the default selection reveal?

What are the concrete practical implications?

What distinguishes these findings from established prompt-sensitivity results? LLM sensitivity to ordering, labels, and output formats is already documented. Does this study reveal a distinct mechanism or a generalizable principle about solution selection, or mainly demonstrate the distributional consequences of familiar prompt sensitivity in matching problems?

1 comment

Thank you for the questions!

Prompt-sensitivity studies report accuracy that changes with format. Here accuracy does not change: For Opus 5.5, Fable 5.1, and GPT-6 Astra every answer is stable in all six framings, so any correctness score is identical across them, and the framing decides which correct answer is returned. This follows a rule: The side meeting at least two of the three conditions receives its optimum on 50 of 50 markets in every framing (Table 4), and Astra repeats its choice on every market across five draws. Under an independently written prompt, the default remains but five of the six models favor the side called Set 1 (Table 31). The models' reasoning names the procedure: Opus 5.5 and Fable 5.1 say the favored side proposes in 346 and 325 of 350 responses, each returning that side's optimum (Table 5).

The same models return a non-endpoint on 49 or 50 of 50 markets when asked (Table 3), and again at ten participants per side (Table 27), so they can produce the alternatives; without a stated rule they still choose one side's optimum. Correctness-based evaluation does not measure this choice.

When a model allocates people to positions, whoever writes the prompt decides which side gets its best stable outcome, and a stability check passes either way. The difference is large: 201 of 250 participants on each side are worse off under the other side's optimum, and Group 1's mean partner rank moves from 1.49 to 3.09 (Table 18). Stating the rule fixes the outcome for the strongest models: asked to run deferred acceptance with a named proposing side, Opus, Fable, and Astra return that side's optimum on all 50 markets, and Sol on 48 and 49 (Table 30).

Reviewer_kf49OpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies which stable matching LLMs return when a two-sided matching market admits several stable solutions, rather than whether the returned matching is stable. The authors build a paired evaluation on 50 small markets (five participants per side) whose complete stable sets are enumerated exhaustively, contrasting a generic request for a stable matching with an explicit request for one that is optimal for neither side. Three frontier models return one side's optimum on every generic request yet produce the requested alternative on 98–100% of explicit requests, showing that their one-sided default is not a capability failure.

Critical strengths
  1. Separating admissibility from selection provides a useful evaluation perspective. The paired design distinguishes a default preference for side-optimal outcomes from an inability to produce alternative stable matchings.
  2. Exhaustive enumeration and deterministic checks make matching validity, stability, and endpoint membership precisely verifiable. Paired markets, negative cases, and distance-matched controls further strengthen the evaluation.
Critical weaknesses
  1. Although market-level Wilson intervals are reported, one response per market-request leaves within-market repeatability unmeasured. The central generic-versus-explicit comparison also remains restricted to N=5.
  2. Despite broader supplementary experiments, the central paired selection result has limited cross-family validation under a common protocol. Its generality beyond the main evaluated models remains uncertain.
  3. The framing experiment covers only six of eight combinations within one prompt family. Completing the factorial design and testing independent wording and randomized identifiers would establish whether the observed pattern generalizes beyond the current template.
Questions for authors

See the weaknesses.

2 comments

Thank you for your review!

Size issues: On 50 new positive markets with ten participants per side, Opus 5.5, Fable 5.1, and Astra return Group 1's optimum on all 50 generic requests and a non-endpoint on 49 or 50 assured ones; Sol and Terra stay within two markets of their N = 5 counts, and Luna drops (28 stable generic answers, 3 explicit successes; Table 27).

Repeatability: With four more draws per market for the OpenAI models and one for Opus, Astra and Opus repeat their generic outcome on every market, including two opposing framings on 20 markets; Sol's generic outcome repeats on 48 of 50. The weaker models vary mostly in stability, and the favored side rarely changes (Table 28). Appendix B.7 gives intervals across markets.

Cross-family issues: Opus 5.5, Fable 5.1, and GPT-6 Astra each return Group 1's optimum on all 50 generic requests and a non-endpoint on 49 or 50 explicit ones on the same prompts and markets (Table 3), and again at ten participants per side.

Framing: The side meeting at least two of the three conditions receives its optimum in both missing cells (Opus 50 and 49, Fable and Astra 50 and 50, Sol 50 and 42, Terra 35 and 40, Luna 32 and 39) and with random participant identifiers (Opus, Fable, and Astra 50 and 50, Sol 50 and 39, Terra 30 and 26, Luna 35 and 36). Under an independently written prompt, Astra still follows the listing order and the answer keys (50 and 49), while the other five models return the optimum of the side called Set 1 in both framings, on 31 to 49 of 50 markets when Set 2 is listed first and keys the answer (Table 31).

Reviewer_kf49OpenReview ↗

Response to the Authors

Thank you for the additional experiments and clarifications. I decide to maintain my original score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

Thank you for the reviews. Changes in the revised PDF are in blue. Besides new analyses of the recorded responses, we ran the experiments the reviews asked for on all six models (Opus 5.5, Fable 5.1, GPT-6 Astra, GPT-6 Sol, GPT-6 Luna, and GPT-5.6 Terra) (Appendix F).

Larger markets: On 50 new positive markets with ten participants per side and 3 to 10 stable matchings, Opus 5.5, Fable 5.1, and GPT-6 Astra return Group 1's optimum on all 50 generic requests and a non-endpoint on 49 or 50 assured ones. GPT-6 Sol and GPT-5.6 Terra stay within two markets of their N = 5 counts; GPT-6 Luna drops to 28 stable generic answers and 3 explicit successes (Table 27).

Repeated draws: With four more draws per market for the OpenAI models and one for Opus 5.5, Astra and Opus give the same outcome in every draw on every market under the generic request and two opposing framings. For the weaker models the draws differ mainly in whether the answer is stable, and the favored side rarely changes (Table 28).

Assurance and permission, separated under a schema that allows a null matching: The assurance reduces false nonexistence claims, the permission sentence changes little, and the null schema leaves withholding on negative markets within two markets of the populated schema (Table 29).

Designated proposer: When we ask models to run deferred acceptance with a named proposing side, Opus, Fable, and Astra return that side's optimum on all 50 markets for either side, and Sol on 48 and 49 (Table 30).

Framing: The side meeting at least two of the three conditions receives its optimum in the two missing cells and with random participant identifiers. Under an independently written prompt that calls the sides Set 1 and Set 2, only Astra follows the listing order and the answer keys; the other five models return Set 1's optimum even when Set 2 is listed first and keys the answer (Table 31). The default persists, and which side it favors depends on the wording.

From the recorded responses: The stated proposing side (Table 5), which alternative is chosen (Table 17), the gap between the endpoints (Table 18), and intervals (Appendix B.7).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.