Preference Reasoning under Indeterminacy in Large Language Models

Hadi Hosseini; Samarth Khanna; Xiyuan Wang

Source-linked AI summary

Preference Reasoning under Indeterminacy in Large Language Models

Hadi Hosseini, Samarth Khanna, Xiyuan Wang

arXiv:2608.18631v1Aug 19, 2026cs.AIcs.GTcs.LG

TL;DR

Preference reasoning in real-world settings is indeterminate because information may be incomplete or valid solutions may not exist, while current evaluations often assume otherwise. The paper formalizes epistemic and structural indeterminacy across increasingly complex tasks and finds that language models systematically misidentify determined and undetermined cases, including during verification.

Problem
Current LLM reasoning evaluations often assume a ground-truth solution exists, leaving limited assessment of whether models recognize incomplete information or nonexistent solutions.
Method
The paper formalizes determined versus undetermined preference reasoning across epistemic and structural indeterminacy and four task levels from atomic queries to solution construction.
Results
Across tasks, LLMs perform worse on undetermined cases, degrade with larger or infeasible markets, and remain poorly calibrated when verifying whether valid solutions exist.
Takeaways & Limitations
Robust preference reasoning requires evaluating whether answers are justified or impossible, not only whether outputs are correct.
Takeaways & Limitations
The evaluation covers four models and Impartial Culture instances, while structured preference distributions and deployment-scale reasoning remain untested.

Abstract

from arXiv · show

As large language models evolve into decision-making agents, the ability to reason over preferences becomes fundamental to alignment, coordination, and collective intelligence. Yet, unlike standard benchmarks, real-world preference reasoning is inherently indeterminate: information may be incomplete, and valid solutions may not exist. We argue that indeterminacy, rather than correctness alone, is a central challenge for AI reasoning. We formalize this challenge along two axes, (i) epistemic indeterminacy, arising from incomplete, partial, or expressive preferences, and (ii) structural indeterminacy, arising from the non-existence of solutions under standard social choice concepts. Across a hierarchy of tasks, we show that state-of-the-art language models systematically fail to distinguish between determined and undetermined instances, exhibiting miscalibrated reasoning even in verification settings.

1 Introduction

The paper frames preference reasoning in LLMs as a problem of distinguishing determined from undetermined cases, encompassing incomplete information and infeasible solution concepts. It introduces a taxonomy of increasingly complex tasks and finds systematic failures in epistemic, structural, verification, and assisted reasoning settings.

Motivation: Preference reasoning supports alignment, recommender systems, and agentic collective decision-making involving conflicting preferences.LLMs may need to infer, compare, and aggregate preferences on behalf of users and across agents.
Problem: Closed-world benchmarks assume solutions exist, unlike real-world decisions with incomplete preferences or infeasible objectives.The paper argues that evaluation must account for undetermined scenarios rather than correctness alone.
Taxonomy: The framework separates epistemic indeterminacy from structural indeterminacy caused by preference structure and solution concepts.Epistemic indeterminacy reflects incomplete information, whereas structural indeterminacy can make objectives infeasible even with fully specified preferences.
Taxonomy: The taxonomy covers atomic, comparative, aggregative, and solution-concept queries, distinguishing determined from undetermined reasoning across increasing complexity.Tasks range from retrieving a rank to aggregating preferences and determining feasibility under social-choice objectives.
Epistemic Indeterminacy: LLMs perform worse on undetermined questions, often imposing assumptions on underspecified preferences; an indeterminacy option helps only some tasks.The paper identifies systematic assumptions such as lexicographic ordering.
Structural Indeterminacy: Structural reasoning degrades with market size and infeasibility, while explicit null options improve detection but bias models toward rejecting feasible instances.Models fail both to identify infeasible cases and to generate valid solutions when they exist.
Verification of Solution Concepts: Even verification tasks show poor calibration: NOTA improves average accuracy, but models rarely abstain when no valid option exists.Models also exhibit intention–action misalignment in preference reasoning.
Assisted Reasoning: Feedback refinement and code execution improve performance, but gains rely mainly on brute-force enumeration for small markets and heuristic search for larger ones.Neither approach scales to difficult instances.

2 Preference-Based Tasks and Methodology

The study evaluates preference reasoning across three increasingly complex economic domains and a hierarchy of query types, varying preference expressivity and solution feasibility. It tests whether large language models distinguish determined from undetermined instances under zero-shot, multi-shot, and code-execution settings.

Problem Domains and Solution Concepts: The benchmark covers house allocation, Shapley–Scarf housing markets, and two-sided matching, targeting Pareto optimality, the core, and stability, respectively.These domains increase in structural complexity and impose distinct axiomatic solution requirements.
Preference Expressivity: Preference structures range from strict complete or incomplete orders to complete or incomplete orders with ties and general partial orders.The study denotes these structures SO, SI, TO, and TI, alongside general partial orders.
Reasoning Tasks: The evaluation hierarchy progresses from atomic and comparative queries to aggregative and structural queries that construct or verify solution concepts.The taxonomy includes both determined and undetermined tasks at each category.
Determined and Undetermined Instances: Undetermined queries are counted correct only when models state that the answer cannot be determined, while committing to an answer is incorrect even if an assumption is disclosed.This scoring rule operationalizes the distinction between uniquely implied answers and insufficient information.
Evaluation Methodology: The study measures Invalid Rate, the frequency of determined responses to undetermined queries, across four state-of-the-art models queried 30 times per question type.Evaluations use zero-shot single-turn prompts at default temperature, with additional multi-shot feedback and code-execution variations.

3 Epistemic Indeterminacy: Preference Reasoning

The section studies epistemic indeterminacy, where preference information does not determine an answer, across atomic, comparative, and aggregative queries with varying expressivity. Models perform substantially worse on undetermined queries, often imposing assumptions instead of recognizing under-specification, though framing and input size affect this behavior.

Experimental Setup: Epistemic indeterminacy arises when the supplied preferences do not determine an answer, and is tested across atomic, comparative, and aggregative queries with varying expressivity.The experiments construct matched determined and undetermined instances using complete preferences, ties, and partial orders.
Determined vs. Undetermined Queries: Models perform substantially worse on undetermined than matched determined queries, with performance approaching zero in several settings.The gap is smallest for atomic queries and largest for comparative queries, where under-specification must be inferred rather than observed from a missing item.
Determined vs. Undetermined Queries: Models silently impose assumptions that suppress under-specification instead of indicating that a query is unanswerable.Determined queries are scored for answer accuracy, whereas undetermined queries are scored for correctly recognizing unanswerability.
LLMs’ Systematic Biases: On responsive-set-incomparable bundle comparisons, models rely on extra assumptions such as lexicographic ordering to resolve comparisons that the preferences do not determine.Responsive-set incomparability means neither bundle dominates the other item by item.
LLMs’ Systematic Biases: On partial-order pairwise queries, models either reject undetermined inputs as malformed or apply ad-hoc heuristics when no comparison chain connects the queried items.The passage identifies these as two model failure modes, including heuristics based on out-degree counts in the induced DAG.
Scaling: Accuracy declines as alternatives or agents increase from 100 to 200, with determined atomic and comparative queries beginning to fail at size 200.The decline is more pronounced on determined queries, which show essentially no errors up to size 100.

4 Structural Indeterminacy: Algorithmic Reasoning over Preferences

LLMs struggle with structural indeterminacy in preference reasoning: performance declines as instances scale, infeasible cases are often misclassified, and abstention options induce over-declaration of non-existence. In selection tasks, models may choose incorrect or weaker candidate solutions even when valid options exist.

Scaling: Performance degrades rapidly as market size increases, even for complete strict preferences where standard solution concepts are guaranteed to exist.The baseline covers Pareto optimality, core outcomes, stability, egalitarian, utilitarian, and rank-maximal solutions.
Deciding Infeasibility: Models show declining performance both in identifying infeasible instances and generating valid outputs when solution concepts are feasible.GPT-5.2 performs well at n = 10 but deteriorates to other models’ level by n = 30.
Indeterminacy Option: The indeterminacy option improves infeasibility detection but causes systematic over-declaration of non-existence, reducing performance on feasible instances.Models increasingly abstain rather than produce valid solutions.
Selection: Models frequently select incorrect candidates even when a valid solution is present, while removing NOTA increases incorrect selection on infeasible instances.Incorrect responses nearly always choose weaker versions of the intended notions, such as weak core instead of strict core.
Selection: GPT-5.2 substantially outperforms other models when a valid solution is present but degrades markedly on infeasible instances as problem size increases or NOTA is absent.When NOTA is available, no model selects it on feasible instances, while models under-select it on infeasible ones.

5 Performance Improvements with Assisted Reasoning

Assisted reasoning improves some forms of preference reasoning but does not reliably resolve indeterminacy. Feedback mainly helps on Shapley-Scarf markets, while code execution removes scale-related errors on determined queries yet fails on epistemically undetermined ones and does not scale reliably.

Refinements with Feedback: Feedback substantially improves performance on Shapley-Scarf markets but barely improves performance on matching markets.Models typically produce valid but incorrect allocations on Shapley-Scarf instances, whereas they tend to declare matching instances infeasible immediately.
Reasoning with Code Execution: Code execution completely eliminates scale-related errors on determined preference questions but leaves answers to undetermined bundle-comparison and ranking queries always incorrect.The models’ assumptions become implemented algorithmic steps, preserving errors on epistemically undetermined queries.
Reasoning with Code Execution: Code execution significantly improves algorithmic reasoning on feasible and infeasible problems, but models change strategies with input size rather than implementing the correct approach.They use brute-force enumeration on Small instances and somewhat more efficient heuristics on Modest and Medium instances.
Reasoning with Code Execution: On Medium instances, code-based approaches are not scalable: models often time out on infeasible Shapley-Scarf markets and misidentify feasible matching instances as infeasible.Code improves performance on smaller markets but does not enable deployment-level approaches.
Dissociating the two axes: The two indeterminacy axes respond differently: code improves structural reasoning, whereas prompt-level intervention improves indeterminacy detection on preference queries but not structural feasibility reasoning.This dissociation separates the axes from a single shared calibration failure.

6 Concluding Remarks

The paper identifies indeterminacy as a fundamental dimension of reasoning in preference-based AI systems. It argues that closed-world training biases language models toward hallucinating determinacy, feasibility, and preference information not entailed by the available evidence.

Indeterminacy is a fundamental dimension of reasoning in preference-based AI systems.The paper frames this challenge as increasingly important as language models mediate alignment, coordination, and collective decisions.
Closed-world training paradigms systematically bias models toward hallucinating determinacy, feasibility, and preference information where none is entailed.The paper characterizes this tendency as a broader form of verisimilitude in AI: outputs can appear plausible without logical grounding.

Technical Appendices and Supplementary Material · A Generative AI Use Statement

The authors disclose three uses of AI tools: implementation support, writing polish, and synthesis of reasoning-trace findings from model-generated judge outputs. AI tools polished the paper without generating its claims or results.

A Generative AI Use Statement: AI tools assisted with implementing the benchmark-generation, inference, and analysis code.This assistance included writing and debugging the code.
A Generative AI Use Statement: AI tools were used to polish the writing of the main paper.The authors state that these tools did not generate the paper’s claims or results.
A Generative AI Use Statement: AI tools helped synthesize findings about reasoning traces collected in the LLM-judge experiments.The experiments are described as occurring in Appendices L and P.
A Generative AI Use Statement: The disclosed AI use covered benchmark generation, inference, and analysis workflows.These activities were supported through code writing and debugging.
A Generative AI Use Statement: The writing assistance was limited to polishing rather than generating the paper’s claims or results.This distinction is explicitly stated in the use statement.
A Generative AI Use Statement: The reasoning-trace synthesis involved LLM-judge experiments whose judge outputs were themselves model-generated.This qualification applies to the experiments in Appendices L and P.

B Limitations and future directions … F.1.1 Instance Generation

The paper identifies evaluation limits and open questions about why models mishandle indeterminacy, then situates these findings in deployment, related work, formal solution concepts, and instance-generation procedures. The supplementary setup spans multiple preference structures, canonical social-choice algorithms, and controlled sampling regimes.

B Limitations and future directions: The evaluation covers only four frontier models and samples Impartial Culture instances to create matched determined and undetermined profiles with controlled feasibility.Per-model results are reported instead of a pooled number because the panel spans two closed families and one open-weights family.
B Limitations and future directions: The input-output methodology leaves the mechanisms behind robust failure patterns, including lexicographic bundle tie-breaking and premature termination on partial-order chains, opaque.Mechanistic interpretability is proposed as a way to investigate these assumptions.
B Limitations and future directions: Prompt framing is varied along free-flow, free-flow + “if known”, and MCQ axes, but the threshold for reliable abstention remains uncharacterized.Finer-grained probing could map when prompts become informative enough to elicit abstention.
B Limitations and future directions: Scalable data attribution and calibration-shift analyses could test whether targeted fine-tuning fixes indeterminacy calibration or merely masks surface symptoms.The open question concerns which training-data and post-training factors determine calibration.
C Broader Impacts: In deployment, confidently aggregating incomplete or infeasible preferences can generate an artificial consensus, motivating measurement before higher-stakes use.The concern applies to agentic systems making purchases, scheduling commitments, or mediating conflicting goals.
D Extended Related Work: Related work shows gaps in algorithm execution, strategic rationality, fairness alignment, preference elicitation, and abstention, while this benchmark targets structured-preference reasoning under incomplete information and aggregation.Prior studies report model biases, welfare-maximizing allocation behavior, optimistic assumptions about preference reasoning, and unresolved abstention failures.
E.1 Solution Concepts: The preliminaries define Pareto optimality, MCPO, core variants, welfare objectives, rank-maximality, and three nested stability notions, alongside canonical TTC, SD, and DA algorithms.Strict-core and strong or super-stability solutions may be absent, whereas weak core and weakly stable matchings always exist under the stated conditions.
F.1.1 Instance Generation: Instance generation uses Impartial Culture rankings, uniform truncation for incomplete preferences, randomly merged contiguous tie groups, and Erdős–Rényi DAGs with up to 100 nodes and 50, 80, or 150 edges.Complete-profile sizes are reported at 50, 100, and 200 items, while denser partial-order graphs yield fewer incomparable pairs.

F.1.2 Benchmark Design … H.1 Additional Figures

The benchmark spans preference retrieval, comparison, aggregation, partial-order reasoning, and algorithmic solution tasks under both determined and indeterminate conditions. Across additional analyses, performance declines with larger profiles, while temperature changes do not materially improve infeasibility detection or abstention.

F.1.2 Benchmark Design: Strict complete preferences yield unique answers, whereas strict incomplete preferences can make queries undetermined; tied preferences additionally support top-k questions affected by tie groups.Models must indicate when an answer cannot be determined, including when an item is absent or k exceeds the list length.
F.1.2 Benchmark Design: The benchmark tests atomic position/item retrieval, comparative preference queries, bundle comparisons, aggregative counts, and partial-order comparisons, including comparable and incomparable cases.Bundle tasks distinguish RS-comparable from RS-incomparable pairs, while partial-order tasks test whether models recognize missing comparison chains.
F.2.1 Instance Generation: Instances are sampled from strict, incomplete, and tied preferences, then filtered so evaluated solution concepts have distinct outcomes and cannot simultaneously be satisfied.Strict and complete rankings use impartial culture, while ties are formed by independently merging adjacent items with probability p.
F.2 Algorithmic Reasoning Tasks: Algorithmic reasoning tasks separate generation from candidate selection and evaluate solution concepts across house allocation, object allocation, and stable matching.Generation asks models to compute solutions from preference profiles, while selection asks them to choose among presented candidates.
F.2.2 Benchmark Design: Harder notions use 30 feasible and 30 infeasible instances per notion with generation escape-hatch and selection-NOTA ablations testing whether models express or recognize infeasibility.The design covers strict core, strong stability, and super stability, whose solutions are not guaranteed under ties.
G Model and Inference Details: The four evaluated frontier models use hosted APIs without fine-tuning at temperature 1.0, while only Claude-4.5-Sonnet and OSS-120B receive a temperature-0 re-evaluation.GPT-5.2 and Gemini-2.5-Pro do not expose temperature control; the re-evaluation uses a 40-instance hard-notion subset at n = 10.
H.1 Additional Figures: As profile size increases, accuracy falls on determined queries; atomic and comparative tasks remain near-perfect through size 100 but fail at size 200, while aggregative errors rise at size 100.The appendix attributes aggregation difficulty to the quadratic growth caused by more agents and longer preference lists.

H.2 Detailed results of reasoning over total-order preference profiles … I.3 Generation without a Specific Objective

Across preference-reasoning tasks, models often replace epistemic or structural indeterminacy with definite answers, while performance also depends on task complexity, prompt format, solution concept, and input size. In algorithmic settings, models generally follow canonical procedures but may fail to execute them or select stronger procedures inconsistently.

H.2 Detailed results of reasoning over total-order preference profiles: On undetermined total-order queries, models usually force definite answers through assumptions such as lexical ordering, typographical correction, or manually completing missing items.In ranking, this produces full rankings even when only listed items can be determined.
H.3 Special undetermined queries: detailed bundle comparison and top-k results: 80% or more of responses in every model-by-preference-type bundle cell apply lexicographic ordering to RS-incomparable pairs, while silent completion dominates flagged assumptions.Lenient scoring raises accuracy by at most 0.17, and flagged assumptions account for at most 0.17 of responses.
H.4 Partial-order pairwise comparison: detailed results: For partial-order queries, GPT-5.2 and OSS-120B reliably acknowledge incomparability under free flow, Gemini-2.5-P declines with density, and Claude-4.5-S collapses to 0% at 150 edges.Switching to MCQ recovers near-perfect accuracy across all four models.
H.5 Alternative preference presentation: natural language rendering: Natural-language rendering does not restore correct abstention: bundle-task abstention is at or near 0.00 for GPT-5.2 and OSS-120B, despite perfect matched determined accuracy.Models distinguish indeterminacy by source, flagging unknown items more often than formally incomparable bundles.
I.1 Performance Differs Across Solution Concepts: Canonical solution concepts such as core/TTC, PO/SD, and stability/DA receive higher and more consistent accuracy than non-canonical notions such as UW, EW, and RM.At n=30, accuracy on UW and RM approaches zero for all models except GPT-5.2.
I.2 Robustness to Preference Structure: Truncating preference lists or introducing ties generally does not reduce performance when the underlying algorithm is unchanged, except for Pareto-optimality in house allocation under ties.MCPO remains reasonable with incomplete preferences but declines more sharply with size than the core.
I.3 Generation without a Specific Objective: Without a specified objective, models default to canonical domain algorithms but often identify them more successfully than they execute them, especially at n=30.At n=10 in object allocation, some models instead attempt stronger notions such as UW rather than applying SD; this largely disappears at n=30.

I.4 Failures in Infeasibility Detection · I.5 Selecting from Options · J Statistical analysis of quantitative results

Models struggle to detect infeasibility and select among candidate solutions, relying on prompt-provided escape hatches and heuristics while exhibiting systematic preference biases. Quantitative comparisons use confidence intervals and paired statistical tests on collected responses.

I.4 Failures in Infeasibility Detection: Models cannot reliably detect infeasibility, with failures driven by heuristic search that worsens as instance size increases.They largely fail on strict core, strong stability, and super stability even at n = 10, with further decline at n = 30.
I.4 Failures in Infeasibility Detection: High NE accuracy can reflect a default-to-empty bias, where models return {} indiscriminately and produce invalid solutions on feasible instances.This apparent accuracy therefore reflects claiming infeasibility rather than genuinely detecting it.
I.4 Failures in Infeasibility Detection: Removing the {} escape hatch causes NE accuracy to collapse for most models, while GPT-5.2 remains more robust but degrades at n = 30.Infeasibility claims also track notion difficulty: {} is rare for strict core but common for strong and super stability.
I.4 Failures in Infeasibility Detection: Models frequently select incorrect candidates even when a correct option exists, and use NOTA poorly when no correct option is present.GPT-5.2 performs better when intended solutions exist but drops substantially when they do not, especially for larger instances or without NOTA.
I.5 Selecting from Options: When selecting from candidates, models favor utilitarian welfare-maximising outcomes in allocation domains more often than canonical solutions.This selection behavior diverges from their default generation behavior and recovers the utilitarian bias.
I.5 Selecting from Options: Models often select solutions satisfying properties different from those they intend, especially with incomplete or tied preferences.Incomplete preferences encourage max-cardinality outcomes, while ties blur weaker and stronger notions.
I.5 Selecting from Options: Reasoning traces show that models primarily assess matchings by the absence of weak blocking pairs, then compare weakly stable options using welfare or Pareto-improvements.The reported disagreement between judges makes the incomplete-preference result judge-sensitive rather than pooled.
J Statistical analysis of quantitative results: The statistical analysis reports 95% Wilson confidence intervals, McNemar’s tests for paired instance comparisons, and Fisher’s exact tests across instance sizes.All analyses use already collected responses, with each prompt scored from a single draw.

J.1 Indeterminacy gap of preference reasoning tasks … K Prompt Templates

The appendix shows that models often separate determined from undetermined preference instances, but this gap varies by task, model, input size, and format. It also documents prompt templates for preference and algorithmic reasoning, including explicit handling of missing solutions, multiple-choice options, preference encodings, and reasoning traces.

J.1 Indeterminacy gap of preference reasoning tasks: Determined bundle queries achieve accuracy near 1 while undetermined queries are near 0, with non-overlapping confidence intervals across every task and model.On bundle comparison, determined accuracy is 1.00 in eleven of twelve model × preference-type cells and 0.85 in the twelfth; undetermined accuracy never exceeds the reported near-zero pattern.
J.1 Indeterminacy gap of preference reasoning tasks: The determined-versus-undetermined gap is model-dependent for atomic and aggregative queries and mixed or reversed for partial-order queries.At 150 edges, Claude-4.5-S scores 1.00 versus 0.00, Gemini-2.5-P scores 1.00 versus 0.50, and GPT-5.2 follows a different pattern.
J.2 Model differences on hard notions of algorithmic reasoning: All six pairwise model comparisons on hard notion problems are significant, with p ≤0.004 on McNemar’s test, and GPT-5.2 is the only model with non-trivial accuracy on matched feasible instances.The pairwise tests cover 360 paired instances, while per-model accuracies are reported in Table 20.
J.3 Scaling of input size on generation tasks: 32 of 53 small-versus-modest market-size comparisons are significant under Fisher’s exact test, with declines possible for models that perform on small markets.The significance comparison is reported for Figure 4a(a), and the relevant models achieve at least some small-market performance.
J.4 Format effect on undetermined preference queries: Format effects on undetermined preference queries are significant in approximately half of cases and strongly task-dependent, so results are reported per cell rather than as one average.Table 22 identifies cells with non-overlapping 95% intervals between free-flow and MCQ formats.
J.5 Influence of "NOTA" option on hard selection problems: No model selects NOTA when a solution exists, whereas models under-select it on infeasible instances, indicating failure to abstain when abstention is correct.The provided option has a significant one-sided effect and does not induce spurious abstention.
K.1 Preference reasoning tasks: Preference-reasoning prompts use a common algorithm-expert template with JSON-encoded preferences, while undetermined queries add “if known” wording or an MCQ insufficient-information option.The base template describes object allocation over [n] alternatives and [n] agents, followed by a preferences_json block.
K.2 Algorithmic reasoning tasks: Algorithmic prompts specify the domain and notion, require structured allocation outputs or option letters, return {} when no solution exists, and encode ties, incomplete preferences, markets, and endowments explicitly.Some models additionally receive a scratchpad instruction, while notion definitions remain constant across models and instance sizes.

L Reasoning Strategies on Feasible and Infeasible Tasks (GPT-5.2) … M Prompt-level mitigation

GPT-5.2 uses structure-sensitive heuristics on feasible matching and allocation tasks, but their reliability degrades with size, while prompt hints strongly control whether it produces correct impossibility arguments. Prompt-level interventions fail to calibrate indeterminacy reliably, instead shifting errors between commitment and abstention.

L Reasoning Strategies on Feasible and Infeasible Tasks (GPT-5.2): GPT-5.2 is the only evaluated frontier model with non-trivial correctness on strict-core, strongly stable, and super-stable tasks containing both feasible and infeasible instances.The qualitative analysis uses GPT-5.2 self-reported scratchpads, deterministic algorithmic verification, and LLM-judge feature extraction.
L.1 Strict core in Shapley–Scarf housing markets: On strict-core tasks, constructive-chain tie-breaking yields 29/30 correct trajectories at Small size, but only 2/60 at Modest size, where mechanical TTC behavior dominates.At Small size, 30/60 trajectories are constructive-chain and 29/30 are correct; at Modest size, 2/60 are constructive-chain and neither is correct.
L.1 Strict core in Shapley–Scarf housing markets: On infeasible strict-core instances, empty-answer prompting elicits correct non-existence claims in 24/30 Small trajectories, versus 0/30 without the hint.The model uses iterative mandatory-pair enumeration, but at Modest size the empty-hint prompt no longer suffices.
L.2 Strongly stable matchings: For strongly stable matching, deferred acceptance plus forced-pair repair achieves 56/60 at Small size but only 19/60 at Modest size.The combined totals include super-stable matchings, which strictly imply strong stability; larger instances make the local repair loop the bottleneck.
L.2 Strongly stable matchings: On infeasible strongly stable instances, empty-hint prompting produces correct impossibility arguments in 19/30 Small and 17/30 Modest trajectories, while no-hint prompting produces 0/30 at either size.Every one of the 36 traces containing an impossibility argument is correct.
L.3 Super stable matchings: For super-stable matching, GPT-5.2 produces 49/60 correct matchings at Small size but only 1/60 at Modest size, with non-production becoming the dominant failure mode.At Modest size, 52/60 trajectories produce no parseable matching, while the model often names Irving–Manlove without executing its edge-deletion procedure in detail.
L.4 LLM-judge setup: The LLM judge extracts structured scratchpad features and compares canonical strategies, while deterministic verification assigns per-cell correctness strata.DeepSeek V4 Pro runs at temperature 0 in JSON mode using the problem, scratchpad, parsed answer, and cell-specific probes.
M Prompt-level mitigation: No prompt intervention calibrates indeterminacy: general caution shifts GPT-5.2 from 1.00 | 0.00 to 0.43 | 0.80, relocating rather than removing error.Specific cautions can collapse other models, explicit abstention is ignored by three of four models, and few-shot gains do not transfer across indeterminacy sources.

N Code-Assisted Reasoning: Approaches by Model and Size … N.3 Gemini 2.5 Pro

In code-assisted reasoning, models use distinct strategies across notions and instance sizes, with verification and fallback behavior varying substantially. GPT-5.2 and Claude Sonnet 4.5 verify textbook outputs at n = 10, whereas Gemini 2.5 Pro generally omits explicit verification and cannot identify infeasible instances.

N Code-Assisted Reasoning: Approaches by Model and Size: At n = 10, GPT-5.2 and Claude Sonnet 4.5 commonly verify textbook algorithms and fall back when verification fails.The recurring pattern covers Top Trading Cycles, deferred acceptance, and Irving’s super-stable algorithm.
N Code-Assisted Reasoning: Approaches by Model and Size: Code-assisted accuracy is reported by domain, problem size, and feasibility, with each table cell giving correct responses out of 10 instances.Timeouts and invalid responses count as incorrect.
N.1 GPT-5.2: GPT-5.2 runs Top Trading Cycles with first-in-list tie-breaking, checks complete blocking-coalition feasibility, and exhaustively enumerates all n! allocations after failure at n = 10.It returns {} when enumeration finds no strict-core allocation and switches to randomised TTC at n = 30.
N.2 Claude Sonnet 4.5: Claude Sonnet 4.5 matches GPT-5.2’s n = 10 exhaustive verification pattern but uses more limited heuristics at n = 30.For strict core with ties at n = 30, it samples allocations and checks blocking coalitions only up to size ≤5, producing low feasible-instance accuracy but accidentally high infeasible-instance accuracy.
N.3 Gemini 2.5 Pro: Gemini 2.5 Pro does not use exhaustive enumeration at any size, and its code typically lacks an explicit verification step.Its strict-core procedure applies TTC with arbitrary tie-breaking and accepts the output regardless of whether it satisfies strict-core conditions.
N.3 Gemini 2.5 Pro: On strict core with ties, Gemini 2.5 Pro never identifies infeasible instances because it treats TTC’s output as the answer without checking strict-core membership.This behavior contrasts with approaches that verify the generated allocation and fall back when the check fails.
N.3 Gemini 2.5 Pro: For super stable, Gemini 2.5 Pro uses an ad-hoc Gale-Shapley modification without a super-stability check and has a high false-NE-claim rate at n = 30.The supplied passage reports the false-NE behavior but does not provide its numerical rate.

O Refinement Experiment Details

The refinement experiment tests whether models can correct invalid allocations or matchings through up to three rounds of verifier-generated feedback. It compares feasible and infeasible instances across two models and uses programmatic, informative-but-nonprescriptive feedback with preserved conversation history.

Experimental setup: The experiment evaluates 30 feasible and 30 infeasible instances per solution notion, using OSS-120B on Small instances (n = 10) and GPT-5.2 on Modest instances (n = 30).All instances use Generation format, requiring a JSON allocation or matching, or {} when no solution exists.
Interaction protocol: Each instance allows up to three attempts, with later attempts receiving feedback after an incorrect answer while preserving the full conversation history.A correct answer ends evaluation early; timeouts or errors skip remaining attempts.
Feedback design: Feedback is generated automatically by the same programmatic verifier used for scoring and identifies violations without prescribing a repair strategy.Strict-core feedback reports blocking coalitions, while super-stable feedback reports blocking pairs and explains their blocking conditions.
Feedback design: When a feasible instance receives {}, feedback reveals that a valid solution exists without revealing the solution itself.For infeasible instances, feedback never explicitly states that no solution exists, although many reported violations may indirectly signal infeasibility.

P LLM-Judge Analysis Details … P.3 Additional judges and human validation

The paper uses separate LLM judges to identify reasoning strategies and prioritized solution concepts, while deterministic scripts and feasibility checkers handle other analyses and correctness. Additional-model agreement and human validation support the reliability of the judge-based findings.

P LLM-Judge Analysis Details: The generation judge identifies which algorithm or solution concept a model appears to invoke, independently of whether its final allocation is correct.It distinguishes generation without a specified target from selection among candidate solutions.
P LLM-Judge Analysis Details: Judging uses Gemini-2.5-Flash with default sampling, presenting the original prompt and full response and requiring one closed-list label based only on explicit textual evidence.The judge is instructed not to recompute solutions or verify the algorithm independently.
P.1 Generation Setting: The generation setting classifies algorithms including Top Trading Cycles, Hungarian min-cost, Hopcroft–Karp, exhaustive search, deferred acceptance, stability algorithms, serial dictatorship, and no algorithm described.The option set also includes “some other algorithm”.
P.2 Selection Setting: The selection setting asks models to choose among pre-labeled candidate solutions, then classifies the solution concept or criterion prioritized in their written justification.Its option set covers eleven concepts, including core, welfare, rank-maximality, stability, and Pareto-optimality.
P.2 Selection Setting: Selection records Intended, Actual, and Achieved, with Achieved equal to one exactly when the chosen candidate satisfies the concept the model’s reasoning claims to prioritize.Actual is recovered from each candidate’s pre-assigned concept label.
P.3 Additional judges and human validation: The generation-side judge supports Appendix I.3 and Appendix L, whereas the selection-side judge supports the intention-action analysis behind Figure 14.Figure 3’s lexicographic-completion and premature-termination findings use a deterministic script instead of a judge.
P.3 Additional judges and human validation: Three-judge Fleiss’ κ is 0.64 for reasoning-strategy judgments and 0.82 for intention-action judgments across reruns with GPT-5.6-Luna and Gemini-3.5-Flash.Lower reasoning-strategy agreement reflects ambiguity in borderline “strongly stable” cases.
P.3 Additional judges and human validation: Human-versus-Gemini-2.5-Flash Cohen’s kappa is 0.86 for 36 independently annotated responses, while alternate judges score 0.72 and 0.76.Disagreement is concentrated mostly in the incomplete house-allocation cell.