Unpacking Interpretability: Human-Centered Criteria for Optimal Combinatorial Solutions

This paper establishes that human preference for equally optimal combinatorial packing solutions is reliably driven by three quantifiable structural properties—alignment with greedy heuristics, simple within-bin composition, and ordered visual representation—thereby providing a concrete framework for designing interpretable algorithmic support systems.

The Gist

Imagine you are the manager of a busy warehouse. You have a fleet of delivery trucks (bins) with specific weight limits, and a pile of boxes (items) of various sizes that need to be shipped. Your goal is to pack as many boxes as possible into the trucks without breaking them.

A super-smart computer algorithm solves this puzzle for you. It finds the perfect way to pack the boxes so that no space is wasted. But here's the catch: there isn't just one perfect way. There might be ten different ways to pack the trucks that are all equally efficient.

The computer picks one and says, "Here is the solution!" But you, the human manager, look at it and think, "Wait, this looks messy. I don't understand why the computer put that heavy box in the back truck and the light one in the front. Can I trust this? Can I explain it to my boss?"

This paper is about figuring out what makes a computer's perfect solution look "easy to understand" to a human brain.

The Big Question

When two solutions are mathematically identical (both are 100% perfect), why do humans prefer one over the other? Is it just random? Or is there a pattern?

The researchers set up a game to find out. They showed people pairs of these "perfect" packing solutions and asked, "Which one looks easier to understand?"

The Three Secrets of "Easy to Understand"

The study discovered that humans have a strong preference for solutions that follow three specific rules. Think of these as the "Golden Rules" for making AI look smart and friendly:

1. The "Greedy" Rule (Heuristic Alignment)

The Metaphor: Imagine you are packing a suitcase. The "greedy" way is to just throw the biggest, bulkiest items in first, then fill the gaps with smaller stuff. It's not the most scientific method, but it's how humans naturally think.
The Finding: Humans preferred solutions that looked like they were built using this simple, common-sense logic. If the computer's solution looked like it followed a "biggest-first" rule, people thought, "Ah, I get it. That makes sense." If the computer did something weird and counter-intuitive (even if it was perfect), people felt confused.

2. The "Neatness" Rule (Compositional Simplicity)

The Metaphor: Think of a bookshelf. You feel more comfortable looking at a shelf that is either completely empty or packed tight to the brim. You feel uneasy looking at a shelf that is half-full with a random jumble of books, magazines, and coffee mugs.
The Finding: People liked solutions where the trucks were either almost empty or almost full. They hated solutions where the trucks were half-full with a chaotic mix of items. Simple, extreme states are easier for our brains to process than "messy middle" states.

3. The "Order" Rule (Visual Order)

The Metaphor: Imagine a row of people waiting for a bus. If they are lined up from tallest to shortest, you can instantly see the pattern. If they are standing in a random, chaotic circle, it takes your brain longer to figure out who is who.
The Finding: Humans loved it when the trucks and boxes were displayed in a sorted order (e.g., biggest truck first, biggest box first). A messy, jumbled visual layout made the solution feel "harder" to understand, even if the math was the same.

What Happened When They Looked Closer?

The researchers didn't just ask people what they liked; they also measured how fast people clicked and where they looked (using webcams to track eye movement).

• Speed: When the difference between the two solutions was huge (e.g., one was super neat, the other was a total mess), people decided faster. But specifically, when the "Greedy Rule" difference was clear, people made up their minds quickly.
• Eyes: Surprisingly, the researchers didn't find a strong link between how long people stared at a solution and how complex it was. It seems our eyes don't always betray our confusion! We might stare at a messy solution just as long as a neat one, but we still prefer the neat one.

Why Does This Matter?

This isn't just about packing boxes. This applies to AI in the real world:

• Hospitals: Assigning patients to nurses.
• Logistics: Routing delivery trucks.
• Finance: Allocating money to projects.

If an AI gives a hospital manager a schedule that is mathematically perfect but looks chaotic, the manager might reject it or make mistakes trying to fix it. But if the AI gives a schedule that is equally perfect but follows the "Greedy," "Neat," and "Ordered" rules, the manager will trust it, understand it, and use it.

The Takeaway

The paper concludes that Optimality isn't enough. To work well with humans, AI needs to be Interpretable.

If you are building an AI system, don't just aim for the "best" number. Aim for the "best" number that also looks like it was built by a human using simple rules.

• Sort your data.
• Keep things simple and extreme.
• Follow common sense.

By doing this, we can build a future where humans and computers don't just work together, but actually understand each other.

Technical Summary

Here is a detailed technical summary of the paper "Unpacking Interpretability: Human-Centered Criteria for Optimal Combinatorial Solutions" by Pegler et al.

1. Problem Statement

Algorithmic optimization systems frequently generate multiple solutions that are mathematically equivalent in terms of objective value (e.g., total packed size) but differ significantly in their structural presentation. While these solutions are "optimal," humans often struggle to understand, justify, or trust specific configurations. The core research question is: When optimal solutions are tied in value, which structural properties make one solution more interpretable (easier to understand) than another?

The authors focus on Combinatorial Packing Problems, specifically the Multiple Subset Sum Problem (MSSP), a variant of the multi-knapsack problem where the goal is to maximize total packed size without exceeding bin capacities. In MSSP, multiple distinct item-to-bin assignments can yield the same maximum score, creating a need to distinguish solutions based on human interpretability rather than just mathematical optimality.

2. Methodology

Experimental Design

The study employed a within-subjects design consisting of an exploratory phase followed by a preregistered confirmatory study.

• Participants: 73 participants (after exclusions) from the US/UK recruited via Prolific.
• Task: Participants viewed pairs of equally optimal solutions to the same MSSP instance side-by-side.
• Measurement: Participants answered, "Which of the two solutions do you find easier to understand?" using a 4-point ordinal scale (Definitely Left, Slightly Left, Slightly Right, Definitely Right).
• Process Measures:
  • Reaction Time (RT): Time taken to make a choice.
  • Gaze Dwell: Aggregate eye-tracking data (via webcam) measuring relative attention to the left vs. right solution.
• Controls: The study included "catch trials" (identical solutions) to ensure attention and "coherence trials" (transitive logic checks) to estimate the theoretical ceiling of explainable variance.

Operationalization of Complexity Metrics

The authors defined three quantifiable solution-level metrics to predict interpretability, based on cognitive principles (heuristics, cognitive load, and perceptual organization):

1. Heuristic-Related Complexity (HC):
   • Concept: Measures deviation from a standard greedy construction rule.
   • Calculation: A reference "greedy" solution is generated using a Largest Bin First, Largest Item First (LBF-LIF) strategy. The HC is the Graph Edit Distance between the given solution and this greedy reference. Lower HC implies closer alignment with human intuition.
2. Compositional Complexity (CC):
   • Concept: Measures the "surprisal" of bin contents based on cognitive load theory.
   • Calculation: Uses a generative probabilistic model. It penalizes bins with many items, intermediate fill levels (half-full), and uneven size distributions. It favors bins that are nearly empty, nearly full, or contain few items with symmetric sizes.
3. Visual-Order Complexity (VC):
   • Concept: Measures the disorder of the visual layout.
   • Calculation: Uses an adapted Kendall's $\tau$ rank correlation. It quantifies how far the visual ordering of bins and items deviates from a perfectly sorted (ascending or descending) sequence.
4. Control Covariate (Diagonal Dissimilarity - DD):
   • Measures geometric similarity to a diagonal assignment pattern to distinguish between a preference for visual diagonals vs. heuristic alignment.

Statistical Analysis

• Choice: Ordinal Mixed-Effects Models (CLMM) predicting the preference choice based on signed differences ($\Delta$) in complexity metrics between the two solutions.
• Reaction Time: Linear Mixed-Effects Models (LMM) predicting log-RT based on absolute differences ($|\Delta|$) in complexity.
• Gaze: Binomial Generalized Linear Mixed Models (GLMM) predicting gaze bias ($R/(R+L)$) based on signed differences.

3. Key Contributions

1. Quantifiable Framework for Interpretability: The paper moves beyond qualitative descriptions of "explainability" by defining three specific, computable structural metrics (HC, CC, VC) that directly correlate with human preference in combinatorial optimization.
2. Empirical Validation of Heuristic Alignment: It provides strong evidence that humans prefer solutions that align with simple greedy heuristics, even when evaluating completed solutions rather than generating them.
3. Actionable Design Principles: The study offers concrete guidelines for "Interpretability-Aware Optimization," suggesting that optimization algorithms should use these metrics as tie-breakers or secondary objectives when multiple optimal solutions exist.
4. Methodological Rigor: The use of a preregistered confirmatory study, coherence trials to establish an empirical ceiling for model fit, and a combination of behavioral and eye-tracking data provides a robust validation of the proposed metrics.

4. Results

Preference for Simpler Solutions

The primary hypothesis was confirmed: participants consistently preferred solutions with lower complexity across all three metrics.

• Heuristic-Related Complexity (HC): A 1-SD increase in the difference favoring the simpler solution reduced the odds of choosing the complex one by 27% (OR = 0.73).
• Visual-Order Complexity (VC): The strongest predictor; a 1-SD increase reduced odds by 31% (OR = 0.69).
• Compositional Complexity (CC): Also significant; a 1-SD increase reduced odds by 21% (OR = 0.79).
• Diagonal Dissimilarity (DD): Did not significantly predict choice, indicating the preference is for heuristic structure, not just visual diagonals.

Reaction Time (Decision Speed)

• HC Effect: Larger absolute differences in heuristic complexity ($|\Delta HC|$) led to faster decision times (approx. 4% reduction per SD). This suggests that when the heuristic difference is clear, decisional conflict is reduced.
• CC and VC Effects: Differences in compositional or visual order did not significantly speed up responses in the confirmatory study, suggesting these factors influence preference but not necessarily the speed of the decision in low-pressure settings.

Gaze Dwell

• No Complexity Effect: Aggregate webcam-based gaze data showed no reliable effect of complexity metrics on where participants looked.
• Left Bias: A small, consistent left-gaze tendency was observed, but complexity did not modulate this. The authors suggest that webcam tracking may lack the sensitivity to detect subtle, complexity-driven attentional shifts in paired comparisons.

5. Significance and Implications

• Human-AI Collaboration: The findings bridge the gap between algorithmic optimality and human usability. In real-world applications (e.g., hospital nurse scheduling, capital budgeting), presenting the "most interpretable" optimal solution can increase trust and adoption.
• Optimization Strategy: The authors propose treating interpretability as a secondary objective in multi-objective optimization. Algorithms can:
  • Break ties between equal-value solutions by selecting the one with lower HC/CC/VC.
  • Apply soft penalties for complexity in the objective function.
  • Screen a shortlist of optimal solutions to present the most human-friendly one.
• Theoretical Insight: The results extend the literature on heuristics, showing that humans apply familiar construction rules (like "largest first") even when evaluating pre-computed solutions, not just when solving problems.
• Limitations & Future Work: The study used small problem instances (4–6 bins, 7–9 items). Future work needs to validate these metrics on larger, more complex problems and integrate physiological measures (pupillometry, lab eye-tracking) to better capture cognitive load dynamics.

In conclusion, the paper establishes that visual order, heuristic alignment, and compositional simplicity are the primary drivers of human interpretability in combinatorial solutions, providing a roadmap for designing optimization systems that are not only mathematically optimal but also cognitively accessible.