Preference 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
| 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 |
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. |
| 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 |
| 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 |
| 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 | — |
| 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 |
| 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 |
| 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 |
| 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 |
| 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) |
| 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 |
| 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) |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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 |
| 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% ∗ |
| 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 |
| 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 |
| 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 |
| 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>. |
| 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). |
| 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. |
| 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 |
| 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 |
| 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% |
| 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) |
| 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) |
| 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 |
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