cs.AIAug 19, 2026
SavePreference Reasoning under Indeterminacy in Large Language Models
Organizations: Penn State University, USA
Abstract
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.
Figures & tables
Figure 1: Overview of our taxonomy of evaluating LLMs’ reasoning with indeterminacy.
| Task Type | Subtype | Example (Determined / Undetermined) |
| Atomic | Rank retrieval | Determined: rank of in Undetermined: rank of under incomplete list |
| Comparative | Pairwise, RS-extension, ranking | Determined: holds Undetermined: under partial information |
| Aggregative | Preference aggregation (counts) | Determined: Undetermined: count under missing comparisons |
| Structural | Core, stability (weak/strong/super) | Determined: existence of stable matching Undetermined: existence under ties / incompleteness |
Table 1: Taxonomy of preference reasoning tasks, each exhibiting determined or undetermined instances depending on preference expressivity and feasibility of solutions.
Figure 2: Comparing LLMs’ performance (a) on determined vs. undetermined preference queries, and (b) with different prompting formats on undetermined preference queries, split by task type.
Figure 3: Behavior of LLMs on RS-incomparable bundle comparisons (a), aggregated across different preference types, and partial-order pairwise queries (b).
Figure 5: Errors made by models on generation (a) and selection (b) tasks as a function of problem feasibility and availability of an indeterminacy option, averaged over different solution concepts (Modest instance size). An ideal model would cluster near the origin in all four quadrants.
Figure 6: The effect of allowing models to refine their solutions using feedback. Each bar shows the fraction of instances that were ultimately answered correctly or incorrectly after up to three attempts with verification feedback.
Appendix figures & tables41 assets
Supplementary material from the paper’s appendix.
Appendix
| Preference Expressivity | Description | Determining Property |
| Complete Strict Linear Order | Asymmetric, transitive, and total. | Always determined. |
| Complete Order with Ties | Allows ties ( ); total. | Determined (indifference is explicit). |
| Incomplete Order with Ties | Allows ties and missing pairs. | Undetermined if incomparable ( ). |
| Partial Order / Pairwise Sets | Transitive and asymmetric; missing pairs. | Determined only if in the transitive closure. |
Table 2: Preference expressivity, axioms, and properties. In each case, we consider complete orders and incomplete orders where the preference is truncated (missing the tail).
| Task family | Pref. Type | Question types | Profile sizes | Formats | Prompts |
| Atomic | Strict + complete | Item query, position query, | 50, 100, 200 | ff, MCQ | 360 |
| Strict + incomplete | Item query (undetermined), position query (undetermined), | 50, 100, 200 | ff, ff_if_known, MCQ | 540 | |
| Comparative | Strict + complete | item comparison, item ranking | 50, 100, 200 | ff, MCQ | 360 |
| Strict + incomplete | item comparison (undetermined), item ranking | 50, 100, 200 | ff, ff_if_known, MCQ | 720 | |
| Bundle comparison | Strict + complete | RS-comparable, RS-incomparable, larger bundle, unequal bundle sizes | 50, 100 | ff, ff_if_known, MCQ | 300 |
| Strict + incomplete | RS-comparable, RS-incomparable | 50 | ff_if_known | 60 |
Table 3: Preference reasoning benchmark composition. Profile size refers to the number of items in the preference list. In formats, “ff” refers to free-flow prompt, “ff_if_known” refers to free-flow prompt, added with "if known" phrase, and MCQ refers to multiple-choice question.
| Domain | Pref. type | Notions (generation) | Prompts | ||
| House allocation | Strict + complete | Core, PO, UW, EW, RM | 6 | 1 | 210 |
| Strict + incomplete † | Core, RM, MCPO | 4 | 1 | 150 | |
| Ties + complete | Weak core, PO ‡ , UW, EW, RM | 6 | 1 | 210 | |
| Object allocation | Strict + complete | PO, UW, EW, RM | 5 | 1 | 180 |
| Stable matching | Strict + complete | Stable, UW, EW, RM | 5 | 1 | 180 |
| Ties + complete | Weakly stable, UW, EW, RM | 5 | 1 | 180 |
Table 4: Benchmark composition for standard tasks (solution concepts guaranteed to exist). Each setting uses 30 instances. Generation includes one prompt per listed notion (each with the instruction by default) plus one unspecified prompt; selection asks the model to choose its most preferred candidate without specifying a target notion. and denote prompts per instance; total . Harder notions under preferences with ties (strict core; strong and super stability) are excluded from this table and evaluated separately. Treated as a secondary setting. PO for house allocation with ties is verified via strong Pareto-optimality under weak preferences.
| Label | Provider / API | Model identifier | Max tokens | Timeout | Reasoning effort |
| GPT-5.2 | OpenAI (Responses API) | gpt-5.2 | k (gen) k (sel) | min | medium (concise summary) |
| Claude Sonnet 4.5 | Anthropic (Messages API) | claude-sonnet-4-5- 20250929 | k (gen) k (sel) | min | — |
| Gemini 2.5 Pro | Google ( google.genai ) | gemini-2.5-pro | provider default | provider default | — |
| GPT-OSS 120B | Groq (chat-completions) | openai/gpt-oss-120b | k (gen) k (sel) | provider default | — |
Table 5: Inference settings for the four evaluated models. “Max tokens” lists the per-call output budget on the generation task and (where it differs) the selection task. “Reasoning effort” is the provider-side knob exposed by the OpenAI Responses API; the other three providers do not expose an analogue.
Figure 7: The models’ accuracy degrades with increasing problem size in both determined and undetermined queries.
Figure 8: Comparing LLMs’ performance with different prompting formats on determined preference queries, split by task type. The most notable effect of format is OSS-120B on aggregative tasks. While completely failing to perform accurate aggregation in free-flow format, it selects the correct count in MCQ for a certain portion, yet still significantly trailing other 3 models
| Item query | Position query | Comparison | Ranking | |||||||||
| Model | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 |
| Gemini-2.5-P | 1.00 | 0.967 | 0.50 | 1.00 | 1.00 | 0.70 | 1.00 | 1.00 | 0.80 | 1.00 | 0.967 | 0.633 |
| OSS-120B | 1.00 | 1.00 | 0.68 | 1.00 | 1.00 | 0.59 | 1.00 | 1.00 | 0.83 | 1.00 | 0.967 | 0.45 |
| Claude-4.5-S | 1.00 | 0.967 | 0.50 | 1.00 | 1.00 | 0.73 | 1.00 | 1.00 | 0.90 | 1.00 | 1.00 | 0.80 |
| GPT-5.2 | 1.00 | 0.967 | 0.60 | 1.00 | 1.00 | 0.633 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.667 |
Table 6: Accuracy on determined atomic and comparative queries, under free-form prompt.
| Item query | Position query | Comparison | Ranking | |||||||||
| Model | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 | 50 | 100 | 200 |
| Gemini-2.5-P | 0.50 | 0.30 | 0.00 | 0.63 | 0.40 | 0.23 | 0.63 | 0.50 | 0.37 | 0.17 | 0.20 | 0.00 |
| OSS-120B | 1.00 | 0.93 | 0.87 | 1.00 | 1.00 | 1.00 | 1.00 | 0.57 | 0.22 | 0.00 | 0.00 | 0.00 |
| Claude-4.5-S | 0.87 | 0.80 | 0.93 | 1.00 | 1.00 | 0.83 | 0.70 | 0.90 | 0.47 | 0.00 | 0.00 | 0.00 |
| GPT-5.2 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.43 | 1.00 | 1.00 | 0.00 | 0.00 | 0.00 |
Table 7: Accuracy on undetermined atomic and comparison tasks, with "ff + if known" prompts. Correct response is: for item query, “unknown” (queried item absent from profile); for position query, “unknown” (queried position out of bounds); for comparison, “unknown” (both items not listed); for ranking, return only the listed items. A score of 0 indicates the model never gives the correct response.
| Strict + complete | Strict + incomplete | Complete + ties | ||||
| Model | Size 50 | Size 100 | Size 50 | Size 100 | Size 50 | Size 100 |
| Gemini-2.5-P | 0.90 | 0.57 | 0.10 (0.89) | 0.17 (0.52) | 0.70 | 0.50 |
| OSS-120B | 0.00 | 0.00 | 0.00 (—) | 0.00 (—) | 0.00 | 0.00 |
| Claude-4.5-S | 0.70 | 0.13 | 0.30 (0.43) | 0.23 (0.17) | 0.30 | 0.10 |
| GPT-5.2 | 1.00 | 0.40 | 0.40 (0.83) | 0.40 (0.33) | 0.80 | 0.33 |
Table 8: Accuracy on the aggregative task. For incomplete preferences, values in parentheses give the fraction of incorrect responses matching the assumption made above.
| Strict + complete | Complete + ties | |||
| Model | Size 50 | Size 100 | Size 50 | Size 100 |
| Gemini-2.5-P | 1.00 | 4.54 | 1.08 | 3.93 |
| OSS-120B | 4.60 | 27.7 | 9.60 | 32.5 |
| Claude-4.5-S | 1.80 | 2.62 | 2.65 | 3.22 |
| GPT-5.2 | 0.00 | 2.83 | 1.13 | 2.69 |
Table 9: Mean absolute error of incorrect responses for the aggregation task.
| Strict + complete | Strict + incomplete | Complete with ties | ||||
| Model | RS-comp. | RS-incomp. | RS-comp. | RS-incomp. | RS-comp. | RS-incomp. |
| Gemini-2.5-P | 1.00 | 0.00 (1.00) | 1.00 | 0.00 (1.00) | 1.00 | 0.20 (0.80) |
| OSS-120B | 1.00 | 0.00 (1.00) | 0.85 | 0.00 (1.00) | 1.00 | 0.00 (1.00) |
| Claude-4.5-S | 1.00 | 0.00 (0.90) | 1.00 | 0.00 (0.90) | 1.00 | 0.10 (0.90) |
| GPT-5.2 | 1.00 | 0.17 (0.83) | 1.00 | 0.07 (0.93) | 1.00 | 0.10 (0.90) |
Table 10: Bundle comparison accuracy ( ). For RS-comparable pairs (a definite answer exists), accuracy is reported. For RS-incomparable pairs (no determinate answer exists), the main value is the fraction of responses that correctly select “can’t decide,” with the fraction applying lexicographic ordering by highest-ranked element in parentheses.
| scoring | Gemini-2.5-P | OSS-120B | Claude-4.5-S | GPT-5.2 |
| Abstention only (strict) | 0.10 | 0.00 | 0.03 | 0.17 |
| Plus flagged assumption (lenient) | 0.23 | 0.00 | 0.20 | 0.20 |
Table 11: Bundle comparison scoring for RS-incomparable pairs. In the strict scoring, only “can’t decide” is accepted. In the lenient scoring, returning a lexicographically preferred bundle while explicitly stating the rule as an “assumption” is allowed
| model | increased bundle size | one vs many |
| Gemini-2.5-P | 0.00 (1.00) | 0.00 (1.00) |
| OSS-120B | 0.00 (1.00) | 0.00 (1.00) |
| Claude-4.5-S | 0.00 (0.80) | 0.00 (1.00) |
| GPT-5.2 | 0.00 (1.00) | 0.00 (1.00) |
Table 12: Additional results on RS-incomparable bundles. The main value is the fraction of responses that correctly indicate the comparison is undetermined (“can’t decide”), with the fraction using lexicographic ordering in parentheses.
| Prompt 1 | Prompt 2 | Prompt 3 | ||||
| Model | uncertain | yes/no | keeps tie | breaks tie | yes | no |
| Gemini-2.5-P | 0.00 | 0.90/0.10 | 0.00 | 1.00 | 1.00 | 0.00 |
| OSS-120B | 0.30 | 0.70/0.00 | 0.10 | 0.90 | 0.90 | 0.10 |
| Claude-4.5-S | 0.40 | 0.60/0.00 | 0.50 | 0.50 | 1.00 | 0.00 |
| GPT-5.2 | 0.63 | 0.37/0.00 | 0.60 | 0.40 | 0.90 | 0.10 |
Table 13: Top- selection task under preferences with ties. is chosen so that the th position falls within a tie group, and item is a member of that tie. Prompt 1 directly asks whether is in the top- ; Prompt 2 asks for the top- list only; Prompt 3 asks for the list and then asks whether belongs.
| Chain length = 9 | Edges = 150 | |||||
| Model | 50 edges | 80 edges | 150 edges | chain of 7 | chain of 5 | chain of 3 |
| Gemini-2.5-P | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |
| OSS-120B | 1.00 | 1.00 | 0.23 | 0.50 | 0.73 | 1.00 |
| Claude-4.5-S | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |
| GPT-5.2 | 1.00 | 0.93 | 0.17 | 0.47 | 0.80 | 1.00 |
Table 14: Accuracy on comparable item pairs in partial orders ( items). Left block: chain length fixed at 9, edge count varied. Right block: edge count fixed at 150, chain length varied.
| Free-flow | MCQ | |||||
| Model | 50 edges | 80 edges | 150 edges | 50 edges | 80 edges | 150 edges |
| Gemini-2.5-P | 0.80 | 0.63 | 0.50 | 1.00 | 1.00 | 1.00 |
| OSS-120B | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |
| Claude-4.5-S | 0.13 | 0.07 | 0.00 | 1.00 | 1.00 | 1.00 |
| GPT-5.2 | 1.00 | 0.97 | 0.97 | 1.00 | 1.00 | 1.00 |
Table 15: Accuracy on incomparable item pairs in partial orders ( items), across graph densities and prompt formats.
| Model | Gemini-2.5-P | Claude-4.5-S |
| Determining via relative preference | 0.30 | 0.87 |
| Assuming typo in query or conditions | 0.30 | 0.00 |
| Acknowledging lack of chain yet still committing a choice | 0.40 | 0.13 |
Table 16: Distribution of assumptions that models make to give a definite answer to the unanswerable partial order comparison task under free-flow prompt.
| Model | Free-flow | MCQ |
| Gemini-2.5-P | 1.00 | 1.00 |
| OSS-120B | 0.23 | 0.10 |
| Claude-4.5-S | 1.00 | 0.33 |
| GPT-5.2 | 0.17 | 0.10 |
Table 17: Accuracy on comparable item pairs in partial-order preferences ( items, 150 edges, target chain length 9), under free-flow and MCQ formats.
| Free-flow | MCQ | |||
| Model | 30 edges | 50 edges | 30 edges | 50 edges |
| Gemini-2.5-P | 0.50 | 0.20 | 1.00 | 1.00 |
| OSS-120B | 1.00 | 1.00 | 1.00 | 1.00 |
| Claude-4.5-S | 0.20 | 0.00 | 1.00 | 1.00 |
| GPT-5.2 | 1.00 | 1.00 | 1.00 | 1.00 |
Table 18: Accuracy on incomparable item pairs in partial-order preferences using the query-answer representation ( items), across graph densities and formats.
| Task | Model | Level 1 | Level 2 | Level 3 |
| RS-incomparable bundle | GPT-5.2 | 0.00 | 0.00 | 0.00 |
| RS-incomparable bundle | OSS-120B | 0.00 | 0.00 | 0.02 |
| unranked item | GPT-5.2 | 0.48 | 0.50 | 0.42 |
| unranked item | OSS-120B | 0.50 | 0.53 | 0.33 |
| determined bundle (control) | both | 1.00 | 1.00 | 1.00 |
Table 19: Accuracy on undetermined problems, with different levels of natural language representation of preferences. Level 1: original symbolic list ("A38": ["C9", …]). Level 2: same items, natural sentences. Level 3: items replaced by real dishes, narrated as a person choosing a meal. Each cell is the fraction of 60 responses that correctly indicate indeterminacy. The last row is the matched determined control, where one bundle dominates and a definite answer exists.
Figure 9: Performance of LLMs in terms of achieving specific notions across all three domains under strict and complete preferences, for instance sizes Small and Modest. Each cell is the fraction of instances where the model’s output satisfies the target notion.
Figure 10: Performance on house allocation under strict and complete vs. strict and incomplete preferences.
Figure 11: Difference in LLMs’ performance in computing various types of solutions with strict preferences (S) and preferences having ties (T).
Figure 12: Fraction of responses where LLMs intend to use the canonical algorithm (hatched) and where they achieve the corresponding solution (solid), across domains and preference types, for and .
| Claude-4.5-S | OSS-120B | Gemini-2.5-P | GPT-5.2 | |||||||
| Notion | with {} | without {} | with {} | without {} | with {} | without {} | with {} | without {} | ||
| Strict Core | 10 | E | 0% | 10% | 3% | 3% | 17% | 17% | 100% | 77% |
| NE | 0% | 0% | 0% | 0% | 3% | 0% | 80% | 20% | ||
| 30 | E | 0% [3%] | 0% | 0% [17%] | 0% | 0% [3%] | 3% | 10% | 7% | |
| NE | 0% | 0% | 13% | 0% | 0% | 0% | 0% | 0% | ||
| Strongly Stable | 10 | E | 0% | 7% | 23% [67%] | 37% [20%] | 70% [10%] | 90% | 97% [3%] | 90% ∗ |
Table 20: Hard notions: accuracy by model, notion, instance size, and treatment. Each cell shows the fraction of correct responses. For E rows, the value in brackets is the fraction where the model returned an invalid solution—i.e., a response that is neither a timeout nor a valid one-to-one allocation. For NE rows with the {} instruction, a response is correct only if the model returned {} . For NE rows without the instruction, a response is correct if it is neither a timeout nor a valid one-to-one allocation. A superscript ∗ indicates that at least one response timed out and was counted as incorrect; timeout counts are given in the note below.
Figure 13: Selection outcomes for harder notions (strict core, strong and super stability), separated by whether a solution exists (E/NE) and whether a “None of the Above” (NOTA) option was included, at and .
Figure 14: Share of selections for each solution concept across models, domains, and preference types, at and . The number on top of each bar represents the percentage of responses where the intended notion matches the actual notion, i.e. that satisfied by the selected option.
| Pair | |
| GPT-5.2 vs. Gemini-2.5-P | |
| GPT-5.2 vs. Claude-4.5-S | |
| GPT-5.2 vs. OSS-120B | |
| Gemini-2.5-P vs. Claude-4.5-S | |
| Gemini-2.5-P vs. OSS-120B | |
| Claude-4.5-S vs. OSS-120B |
Table 21: Hard-notion generation: pairwise McNemar tests over 360 paired instances. Per-model accuracies are given in Table 20 .
| Model | Significant cells |
| Gemini-2.5-P | 11 of 20 |
| GPT-5.2 | 10 of 20 |
| Claude-4.5-S | 10 of 19 |
| OSS-120B | 8 of 20 |
Table 22: Format effect (free-flow vs. MCQ) on undetermined preference queries: cells with non-overlapping 95% intervals.
| Model | Feasible (NOTA is wrong) | Infeasible (NOTA is correct) |
| GPT-5.2 | 0.00 | 0.61 |
| Gemini-2.5-P | 0.00 | 0.59 |
| OSS-120B | 0.00 | 0.56 |
| Claude-4.5-S | 0.00 | 0.03 |
Table 23: Selection with a “none of the above” option: fraction of instances on which the model selects NOTA.
| Task string | Format string |
| What position is [choice] at in [agent]’s preference list? | Return<answer>X</answer>, where X is the number indicating the position, if known . |
| What is [agent]’s [k]th most preferred choice? | Return<answer>X</answer>, where X is the name of the choice, if known . |
| Which alternative does [agent] prefer between [choice 1] and [choice 2]? | Return<answer>X</answer>, where X is the name of the choice, if known . |
| Rank [4 choices] according to [agent]’s preference. | Return the solution in the following format: <answer>ranking</answer>, with only ranked choice names in descending order connected by ’>’ sign. |
| How many agents prefer [choice 1] over [choice 2]? | Return <answer>X</answer>, where X is the number of agents. |
| Which bundle does [agent] prefer between {[choice 1], [choice 2]} and {[choice 3], [choice 4]}? | Return the solution in the following format: <answer>{A, B}</answer>, where {A, B} is the preferred bundle. If there is no preference, return <answer>Can’t decide</answer>. |
Table 24: Preference reasoning prompts: task and formatting instructions. The base free-flow prompt is shown, while the wordings in italics are added for free-flow + "if known" format.
| Notion | Definition |
| Pareto-optimal | An allocation is Pareto-optimal if there is no other feasible allocation that makes at least one agent strictly better off without making any other agent worse off. |
| MCPO | A max-cardinality Pareto-optimal (MCPO) allocation matches as many agents as possible to alternatives they rank, and among all such maximum-size matchings it is Pareto-optimal (no Pareto-improving reassignment exists). |
| Core (weak core) | An allocation is in the core if there is no coalition of agents that can reshuffle their initially endowed houses among themselves so that every coalition member is strictly better off than in the allocation. |
| Strict core | An allocation is in the strict core if there is no blocking coalition that can reshuffle endowed houses so that every member weakly improves and at least one member strictly improves. |
| UW-maximizing | A utilitarian welfare-maximizing allocation minimizes the total sum of agents’ assigned ranks (equivalently, maximizes total ordinal utility). |
| EW-maximizing | An egalitarian welfare-maximizing allocation minimizes the worst (largest) rank any agent receives (i.e., it optimizes the welfare of the worst-off agent). |
Table 25: Definitions provided to models for Shapley-Scarf market and house allocation tasks. The prompts label this notion core under strict preferences and weak core under ties. Both labels carry the same blocking condition, because the two notions coincide, so we merge the rows here. The refinement that genuinely differs is the strict core, which blocks when every member of a coalition weakly improves and at least one improves strictly.
| Notion | Definition |
| Weakly stable | A matching is weakly stable if there is no blocking pair where both agents strictly prefer each other to their current partners; ties do not create blocking unless both sides strictly gain. |
| Strongly stable | A matching is strongly stable if there is no blocking pair where both agents weakly prefer each other to their current partners and at least one agent strictly prefers the other. |
| Super stable | A matching is super stable if there is no blocking pair where both agents weakly prefer each other to their current partners; even indifference on both sides can block. |
| UW-maximizing | A utilitarian welfare-maximizing matching minimizes the sum of (ordinal) partner ranks. |
| EW-maximizing | An egalitarian welfare-maximizing matching minimizes the maximum (worst) assigned partner rank. |
| Rank-maximal | A rank-maximal matching lexicographically maximizes the rank-count vector: as many agents as possible get a 1st-choice partner; subject to that, as many as possible get a 2nd-choice; and so on. |
Table 26: Definitions provided to models for matching market tasks.
| Model | L1 bare | L2 MCQ | L3 general | L3 specific | L4 few-shot |
| GPT-5.2 | |||||
| Claude-4.5-S | |||||
| Gemini-2.5-P | |||||
| OSS-120B |
Table 27: Accuracy on bundle comparison problems, with different levels of prompt mitigation. Levels: 1 bare, 2 MCQ with an explicit "not enough information" option, 3 caution (general = source-agnostic, specific = names the structure), 4 few-shot demos. Each is run on 30 instances, with accuracy reported as determined undetermined
| Model | L1 | L4 in-domain | L4 cross-domain |
| GPT-5.2 | 0.00 | 0.10 | 0.13 |
| Claude-4.5-S | 0.00 | 0.97 | 0.00 |
| Gemini-2.5-P | 0.00 | 0.90 | 0.00 |
| OSS-120B | 0.00 | 0.83 | 0.00 |
Table 28: Accuracy on undetermined atomic query, with different levels of prompt mitigation. Levels: L1 bare, L4 few-shot demos (in-domain = examples about the tested source of indeterminacy. cross-source = examples about the other source). Each is run on 30 instances, with accuracy reported.
| Shapley-Scarf Market | Matching Market | |||||||||||
| Small | Modest | Medium | Small | Modest | Medium | |||||||
| Model | F | I | F | I | F | I | F | I | F | I | F | I |
| Gemini-2.5 | 10% | 0% | 10% | 0% | – | – | 20% | 70% | 0% | 60% | – | – |
| Claude-4.5-S | 100% | 100% | 0% | 70% | – | – | 90% | 100% | 30% | 100% | – | – |
| GPT-5.2 | 100% | 100% | 90% | 70% | 100% | 30% | 100% | 100% | 90% | 90% | 0% | 10% |
Table 29: Code-based task accuracy by domain, problem size, and feasibility (F = feasible and I = infeasible). Each cell shows the percentage of correct responses out of 10 instances. Dashes indicate conditions not evaluated. Timeouts and invalid responses are counted as incorrect.
| Notion | E/NE | Dominant approach | |
| Core (HA, strict) | 10–50 | – | Top Trading Cycles (correct) |
| Strict Core (HA, ties) | 10 | E/NE | TTC attempted; on verification failure, falls back to exhaustive enumeration with complete blocking-coalition check (sound) |
| 30 | E | Randomised TTC: repeat with random tie-breaking until a strict-core allocation is found and verified | |
| 30 | NE | Heuristic search failure; MILP in some responses; not always sound | |
| 50 | E | Randomised TTC; all instances correct | |
| 50 | NE | Timeout (no result produced) |
Table 30: GPT-5.2: dominant approach in the code-assisted condition, by task and instance size. For notions with feasibility variation, E and NE rows are shown separately where approaches differ.
| Notion | E/NE | Dominant approach | |
| Core (HA, strict) | 10–30 | – | Top Trading Cycles (correct; minor cycle-detection bugs fixed in later iterations) |
| Strict Core (HA, ties) | 10 | E/NE | TTC attempted; on verification failure, falls back to exhaustive enumeration with full blocking-coalition verification (sound) |
| 30 | E | Heuristic random allocation search with limited coalition-size checks ( ); low accuracy | |
| 30 | NE | Heuristic: blocking coalition found quickly; mostly correct | |
| Rank-Max. Alloc. (HA, ties) | 10 | – | Mixed: some exhaustive enumeration, some greedy rank-by-rank |
| 30 | – | Greedy rank-by-rank fixation (incorrect; accuracy) |
Table 31: Claude-4.5-Sonnet: dominant approach in the code-assisted condition, by task and instance size.
| Notion | E/NE | Dominant approach | |
| Core (HA, strict) | 10–30 | – | Top Trading Cycles (correct; two failures at due to cycle-detection bugs) |
| Strict Core (HA, ties) | 10–30 | – | TTC with arbitrary tie-breaking and no verification step (incorrect; never identifies infeasible instances) |
| Rank-Max. Alloc. (HA, ties) | 10–30 | – | Greedy sequential maximum matching per rank (incorrect heuristic; near-zero accuracy at ) |
| Super Stable (SM, ties) | 10 | E | Custom iterative elimination or modified Gale-Shapley variants |
| 10 | NE | Heuristic failure or custom elimination; partially correct | |
| 30 | E/NE | Ad-hoc Gale-Shapley modifications; high rate of false NE claims regardless of ground truth |
Table 32: Gemini-2.5: dominant approach in the code-assisted condition, by task and instance size.
Figure 15: Judge prompt used in the generation setting.
Figure 16: Judge prompt used in the selection setting.
More in this topic
LLM Reliability
Large language model reliability studies whether outputs remain correct, calibrated, robust, and controllable across prompts, contexts, and deployment conditions.
See all 789 papers