🤖 AI

Preference Reasoning under Indeterminacy in Large Language Models

This paper argues that indeterminacy—stemming from incomplete information and non-existent solutions—is a central challenge for AI preference reasoning, demonstrating that state-of-the-art large language models systematically fail to distinguish between determined and undetermined instances, leading to miscalibrated reasoning.

Original authors: Hadi Hosseini, Samarth Khanna, Xiyuan Wang

Published 2026-08-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hadi Hosseini, Samarth Khanna, Xiyuan Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where artificial intelligence acts as a personal assistant, a mediator for group decisions, or a matchmaker for complex systems. In these roles, the machine must understand what people want, often when those wants are vague, incomplete, or even contradictory. It must decide not just what the best choice is, but also when a best choice simply cannot be found. This is the realm of preference reasoning, a field where computers learn to navigate human desires. For years, researchers have tested these systems using puzzles with clear, single correct answers, much like a math test where every problem has a solution waiting to be found. But real life is rarely so tidy. In the real world, information is often missing, or the rules of the situation make a solution impossible to construct. The question facing scientists today is whether our most advanced AI can tell the difference between a problem that needs solving and a problem that has no answer at all.

A team of researchers at Penn State University set out to test this exact ability. They built a series of challenges based on classic economic problems, such as assigning houses to people or matching partners in a market. In these scenarios, every person has a list of what they prefer. The researchers created thousands of these scenarios, ranging from simple lists of ten items to complex networks involving hundreds of agents. They designed the tests to include two types of uncertainty. The first type happens when the information provided is simply incomplete, like a person who lists only half their favorite foods. The second type happens when the structure of the problem itself makes a solution impossible, such as a set of preferences where no fair arrangement can ever exist without someone being unhappy. The researchers then asked four of the most powerful language models currently available to solve these puzzles. They wanted to see if the machines could correctly identify when a question was unanswerable and, if so, admit that they did not know, rather than guessing.

The results revealed a significant blind spot in how these systems think. When faced with a problem that had a clear answer, the models performed well, often getting the details right. However, when the information was incomplete or the solution was impossible, the models consistently failed to recognize the dead end. Instead of saying "I cannot determine this," they confidently invented answers. They did this by silently making assumptions to fill in the missing gaps. For instance, if a person's preference list was cut short, the models would assume the missing items were ranked in alphabetical order or by some other arbitrary rule, and then proceed to give a definitive answer based on that guess. In cases where no solution existed, the models would often generate a fake solution anyway, or they would claim a solution existed when it did not. This behavior was not a random error; it was a systematic pattern. The models seemed unable to distinguish between a situation where they needed to think harder and a situation where thinking harder would not help because the answer simply did not exist.

The researchers also tested whether giving the models a way to say "I don't know" would fix the problem. They added a specific option for the models to choose when they felt the information was insufficient. While this helped the models admit uncertainty in some cases, it created a new problem. The models began to overuse this option, declaring that no solution existed even when one was perfectly possible. It was as if the models had swung from one extreme of blind confidence to another of excessive caution, unable to find the middle ground. Even when the researchers allowed the models to write computer code to solve the problems—a method that usually improves accuracy—the models struggled. They could solve small, simple versions of the problems by checking every possibility, but as the problems grew larger, they reverted to guessing or giving up, unable to scale their reasoning to the size of real-world applications.

Perhaps the most telling finding came from a test where the models were not asked to create a solution, but simply to pick the correct one from a list of options. Even in this simpler task, where the models only had to verify an answer rather than build one, they frequently chose the wrong option. They often selected a solution that looked plausible but failed to meet the strict rules of the problem. The study showed that these models have a deep-seated tendency to prioritize appearing helpful and decisive over being accurate about what is possible. They are trained to complete patterns and generate text that looks right, which makes them excellent at filling in blanks in a story but poor at recognizing when a story has no ending.

This research suggests that as we integrate these systems into critical decision-making roles, we must be careful about what we expect from them. The ability to recognize when a question cannot be answered is just as important as the ability to answer one. Currently, the most advanced models are not yet equipped to reliably make that distinction. They will likely continue to offer confident, plausible-sounding answers even when the data is missing or the rules make a solution impossible. Until this changes, relying on these systems for high-stakes decisions involving human preferences requires a human in the loop to verify not just the answer, but the very possibility of the answer itself. The study does not claim that these models are broken, but rather that they are operating with a different kind of logic than humans, one that struggles to accept the limits of what can be known.

Technical Summary: Preference Reasoning under Indeterminacy in Large Language Models

1. Problem Definition

As Large Language Models (LLMs) evolve into decision-making agents, their ability to reason over preferences is critical for alignment, coordination, and collective intelligence. However, current evaluation paradigms rely on closed-world benchmarks where a ground-truth solution is assumed to exist. This paper argues that real-world preference reasoning is inherently indeterminate, characterized by two distinct axes of uncertainty:

Epistemic Indeterminacy: Arises from incomplete, partial, or expressive preferences where the input information is insufficient to derive a unique answer (e.g., an item missing from a preference list or incomparable bundles).
Structural Indeterminacy: Arises from the interaction between preference structures (e.g., ties, weak orders) and solution concepts (e.g., strict core, super stability), rendering a valid solution non-existent for a given instance even when preferences are fully specified.

The central challenge is not merely determining correctness but evaluating whether models can distinguish between determined instances (where an answer is entailed or a solution exists) and undetermined instances (where no answer is entailed or no solution exists).

2. Methodology

The authors formalize a taxonomy of preference reasoning tasks across increasing complexity levels, grounded in classical economic problems: House Allocation, Shapley-Scarf Housing Markets, and Two-Sided Matching Markets.

Task Hierarchy

The evaluation spans four task types:

Atomic Queries: Retrieval of specific preference data (e.g., "What is the rank of item $a$ ?").
Comparative Queries: Relational entailment (e.g., "Does the agent prefer $a$ over $b$ ?").
Aggregative Queries: Collective computation (e.g., "How many agents prefer $a$ over $b$ ?").
Structural (Algorithmic) Queries: Construction or verification of outcomes satisfying axiomatic solution concepts (e.g., finding a matching in the core or a stable matching).

Experimental Setup

Models: Four state-of-the-art models were evaluated: GPT-5.2, Gemini-2.5-Pro, Claude-4.5-Sonnet, and OSS-120B.
Preference Expressivity: Experiments varied preference structures including strict complete orders, strict incomplete orders, complete orders with ties, and incomplete orders with ties.
Indeterminacy Options: The study tested whether providing explicit "abstention" options (e.g., "cannot determine," "None of the Above," or returning an empty set {}) improves model calibration.
Assisted Reasoning: Two interventions were tested: (i) Refinement via feedback, where models receive violation reports (e.g., blocking pairs) to iteratively repair solutions, and (ii) Code execution, where models generate and run code to solve instances.
Verification: A deterministic verifier and an LLM-as-a-judge were used to assess solution correctness and to infer the "intended" algorithm or solution concept from model reasoning traces.

3. Key Results

Epistemic Indeterminacy (Preference Reasoning)

Systematic Failure to Abstain: LLMs perform significantly worse on undetermined queries compared to determined ones. Instead of indicating uncertainty, models systematically hallucinate determinacy by imposing silent assumptions (e.g., lexicographic ordering for incomparable bundles or alphabetical completion for missing items).
Bias Patterns: Models default to specific heuristics. For bundle comparisons, all models default to lexicographic ordering even when bundles are RS-incomparable. For partial-order queries, models either prematurely conclude incomparability or invent chains to force a comparison.
Framing Effects: While providing an explicit "if known" qualifier or Multiple Choice Question (MCQ) format with an "unknown" option improves detection of indeterminacy in some cases, it introduces new biases. For instance, MCQ formats can cause models to over-select the "unknown" option even for determined queries.

Structural Indeterminacy (Algorithmic Reasoning)

Scalability Issues: Performance degrades rapidly as market size increases, even for concepts where solutions are guaranteed to exist (e.g., weak stability).
Infeasibility Detection: Models struggle to correctly identify infeasible instances (where no solution exists).
- Default-to-Empty Bias: When provided with an option to return "no solution," models often over-declare infeasibility on feasible instances, leading to a systematic bias toward abstention.
- Prompt Dependence: The ability to detect infeasibility is heavily dependent on the prompt explicitly allowing an empty return; without this "escape hatch," models rarely identify infeasibility.
Intention-Action Misalignment: In selection tasks (verifying candidates), models frequently claim to target a specific solution concept (e.g., "strict core") but select outcomes that satisfy a weaker concept (e.g., "weak core") or fail to satisfy the concept entirely.

Assisted Reasoning

Feedback: Iterative refinement with feedback improves performance on Shapley-Scarf markets but fails on matching markets, largely because models often declare infeasibility in the first round, leaving no solution to repair.
Code Execution: While code execution eliminates scaling errors on determined tasks, it fails to resolve undetermined queries. Models compile their implicit assumptions into the code, leading to incorrect deterministic outputs. Furthermore, code-based strategies (e.g., brute-force enumeration) do not scale to deployment-relevant market sizes.

4. Contributions

Formal Taxonomy: The paper introduces a structured framework for evaluating LLMs on both epistemic and structural indeterminacy, moving beyond binary correctness to assess the ability to recognize the boundary between determinacy and indeterminacy.
Empirical Evidence of Failure: It demonstrates that state-of-the-art models systematically fail to distinguish between determined and undetermined instances, exhibiting miscalibrated reasoning even in verification settings.
Diagnosis of Failure Modes: The study identifies specific failure modes, including silent assumption-making (epistemic) and the inability to correctly identify infeasibility or distinguish between solution concept refinements (structural).
Limitations of Interventions: The paper shows that current mitigation strategies (prompt framing, feedback loops, code execution) are insufficient to resolve these fundamental reasoning gaps, often merely shifting the error from over-commitment to over-abstention or failing to scale.

5. Significance and Claims

The paper claims that indeterminacy is a fundamental dimension of reasoning in preference-based AI systems. It argues that the current "closed-world" training and evaluation paradigms systematically bias models toward hallucinating determinacy, feasibility, and preference information where none is entailed.

The authors conclude that robust AI for alignment and collective decision-making requires:

Open-world reasoning frameworks (e.g., multi-valued semantics like Kleene's three-valued logic).
Richer notions of non-entailment and impossibility in model training and evaluation.
Benchmarks that evaluate not just correctness, but the model's ability to recognize when no justified answer exists.

The work suggests that without addressing these calibration failures, agentic systems may take actions users have not authorized or generate artificial consensus in collective decision-making platforms, presenting outputs as plausible despite lacking logical grounding.