🔢 mathematics

Two Black Boxes, One Solver: Encoder Probing and Decoder Attribution for Neural Multi-Attribute VRP under Hard-Mask and Recourse Decoders

This paper introduces a unified protocol for interpreting neural multi-attribute vehicle routing problem solvers by combining encoder probing and decoder attribution techniques, revealing that graph inductive biases and recourse training regimes significantly enhance both the representational clarity of constraints and the generation of actionable, counterfactual explanations for infeasible decisions.

Original authors: Sohaib Afifi

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sohaib Afifi

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 you have a brilliant, super-fast robot dispatcher that plans delivery routes for a fleet of trucks. It's great at finding the cheapest paths, but it's a "black box." It just says, "Turn left here," without telling you why. If a human manager asks, "Why did you skip that customer?" or "What if we had one more truck?", the robot has no answer. This is risky in the real world because managers need to trust and verify these decisions.

This paper is like a detective kit designed to open up two of these black boxes at once: the part that understands the map (the Encoder) and the part that makes the decisions (the Decoder). The authors tested different versions of these robots to see which ones are not only smart but also "honest" and explainable.

Here is the breakdown of their investigation using simple analogies:

1. The Two Parts of the Robot

The Encoder (The Brain that Sees): This part looks at the map, the traffic rules, the truck capacity, and the time windows. It turns all that messy data into a secret code (a "latent representation").
- The Test: The researchers asked, "Can we read this secret code to see if the robot actually understands the rules?" They found that robots built with Graph Encoders (which understand how cities connect like a web) were much better at organizing this secret code than the standard "Transformer" robots.
- The Surprise: One special robot (UNIMPMOE) didn't just store rules in neat, separate drawers. Instead, it stored them in a distributed way, like a hologram where the whole picture is spread out across the whole code. You can't find "time limits" in just one spot; you have to look at the whole pattern to see them.
The Decoder (The Brain that Decides): This part looks at the secret code and picks the next stop for the truck.
- The "Hard-Mask" Robot: This robot is like a strict teacher. It physically blocks the robot from picking illegal moves (like driving a truck that's too heavy). It never makes a mistake, but because it's forced to be perfect, it doesn't learn what "almost" looks like.
- The "Recourse" Robot: This robot is like a student learning by trial and error. It is allowed to pick illegal moves during training, but it gets "punished" (a cost) for doing so. It learns to avoid them naturally.

2. The Three Ways to Ask "Why?"

To understand the Decoder, the authors used three different "reading angles" (methods) to ask the robot why it made a choice:

Abductive (The "Why this?"): "What was the most important reason you picked this customer?"
Contrastive (The "Why not that?"): "You picked Customer A, but Customer B was very close. What was the tiny difference that made you choose A?"
Counterfactual (The "What if?"): "What is the smallest change we could make to the world (e.g., give the truck a little more fuel or extend the time window) to make a different choice possible?"

3. The Big Discoveries

The researchers ran a "scorecard" comparing six different robot combinations. Here is what they found:

The "Strict Teacher" vs. The "Learner":
The Hard-Mask robot (the strict one) was great at following rules, but it was terrible at explaining why it couldn't do something. If you asked, "What if we changed the rules slightly to make this impossible route possible?", the Hard-Mask robot had no answer because it was never trained to think about "almost possible" routes.
The Recourse robot (the learner), however, was amazing at this. Because it learned to handle "almost" situations, it could tell you exactly what tiny change would make an impossible route work. It produced "Make-Feasible" counterfactuals—essentially saying, "I can't go there yet, but if you add 5 minutes to the time window, I can."
The "Sanity Check":
They tested if the robots were just "faking" their explanations. They scrambled the robot's brain (randomized the weights) and asked the same questions.
- The Hard-Mask robot with standard architecture gave answers that looked the same even when its brain was scrambled. This means its "explanations" were just a trick of its design, not real learning.
- The Graph-based robots (especially the Recourse ones) gave totally different, nonsense answers when scrambled. This proved their explanations were actually based on what they learned, not just a glitch in the code.
The Trade-off:
The Recourse robots were slightly less efficient (they took a tiny bit longer to find the perfect route) compared to the Hard-Mask ones. However, the authors argue this small cost is worth it because the Recourse robot provides richer, more actionable explanations. It tells a human manager not just what to do, but how to fix a problem if the plan fails.

The Bottom Line

The paper concludes that to build trustworthy AI for logistics, you can't just look at how cheap the routes are. You need to look at how the robot thinks.

Graph-based encoders help the robot organize its knowledge better.
Recourse training (letting the robot make mistakes and learn from them) creates a robot that can explain its decisions and suggest realistic fixes for impossible situations.

The best combination found was a Graph Encoder paired with a Recourse Decoder. This robot is not only competitive in cost but is also the only one that can truly answer the question: "What is the smallest change needed to make this work?"

Technical Summary: Two Black Boxes, One Solver

Problem Context
Neural autoregressive solvers for the Multi-Attribute Vehicle Routing Problem (MAVRP) have achieved competitive costs against strong heuristics and other learning-based baselines. However, these models operate as "black boxes," offering no per-step justification for their decisions. In logistics operations, dispatchers require more than just a route; they need to validate decisions against business rules, diagnose anomalies, and compare candidate solver families. Current opacity prevents this, as the policy emits actions without exposing which inputs mattered, which constraints dominated, or what minimal changes would alter the decision. The paper argues that a joint Explainable AI (XAI) account of both the encoder (representation) and decoder (decision) stages is necessary to address this operational liability.

Methodology
The authors propose a unified protocol to "open" two complementary black boxes: the encoder and the decoder. The study evaluates six solver variants formed by combining three encoder families (ATT baseline, UNIMP graph encoder, UNIMPMOE with Mixture-of-Experts) and two decoder variants (HARD-MASK and RECOURSE).

Encoder Probing (Pillar 1):
The protocol analyzes the frozen latent representations ( $h$ ) at the graph, node, and edge levels using four metrics:
- Predictability: Linear probes determine if active constraint families can be recovered from $h$ . Unsupervised readouts (axis-unique vs. top- $k$ subspace) distinguish between axis-aligned and distributed coding.
- Spontaneous Organization: Clustering metrics (NMI, silhouette) assess if $h$ naturally partitions instances by constraint family without supervision.
- Richness: Effective and stable ranks measure the dimensionality of the representation to detect collapse.
- Discovered Directions: PCA/ICA axes are aligned with constraint indicators and validated causally via intervention (perturbing the latent to check if the concept moves as predicted).
Decoder Attribution (Pillar 2):
Three attribution methods (Gradient, Integrated Gradients, DeepLIFT) are applied to the decoding step under three reading angles:
- Abductive: Aggregating attribution mass to identify "why this action?"
- Contrastive: Attributing the margin between the chosen action and the best feasible alternative to identify what separates the decision from its closest rival.
- Counterfactual: A directed search for the smallest input perturbation that either flips the chosen action or restores feasibility to an infeasible alternative ("make-feasible").
Evaluation Grid:
All outputs are scored on five criteria: Fidelity (does removing attributed inputs flip the decision?), Concentration (is the explanation focused?), Stability (do independently seeded models agree?), Sanity (does the attribution survive weight randomization?), and Actionability (can small changes lead to different decisions?).

Key Contributions

Two-Pillar Protocol: A joint XAI framework that probes encoder predictability/organization and attributes decoder decisions through abductive, contrastive, and counterfactual lenses.
Constraint-Family Taxonomy: A method to aggregate raw input gradients into operationally readable groups (capacity, geometry, time windows, route-recourse).
Comprehensive Benchmarking: Application of the protocol to six MAVRP variants, explicitly comparing a "strong-mask" decoder (HARD-MASK, feasibility-by-construction) against a "weak-mask" decoder (RECOURSE, feasibility-by-learning).
Revealing Hidden Phenomena: The protocol exposes phenomena invisible to inference cost alone, including distributed coding in MoE encoders, sanity gaps between architectures, and representational gaps between decoder policies.

Results

Encoder Performance: Graph encoders (UNIMP, UNIMPMOE) significantly outperform the ATT baseline in predictability (macro-F1) and spontaneous organization (NMI). UNIMPMOE exhibits distributed coding: while it underperforms UNIMP on single-axis probes, it catches up when evaluated on top- $k$ subspaces, indicating constraints are represented across a subspace rather than a single axis.
Decoder Performance & Cost: HARD-MASK decoders achieve lower inference costs (1.39–1.82% gap to BKS) compared to RECOURSE (2.73–2.91%). However, RECOURSE offers superior interpretability.
Sanity and Stability: Graph encoders pass the sanity check (trained vs. randomized weights) decisively, whereas ATT shows architectural artifacts. RECOURSE policies produce richer explanations but exhibit lower stability in identifying a single dominant constraint family compared to HARD-MASK, reflecting a trade-off between richness and reproducibility.
Counterfactuals (The Critical Finding): The RECOURSE decoder is the only variant capable of producing "make-feasible" counterfactuals (small changes that turn an infeasible alternative feasible). HARD-MASK policies fail to produce these even when fed infeasible alternatives externally. This is attributed to the training regime: RECOURSE learns to assign meaningful logit mass to infeasible candidates, whereas HARD-MASK policies, constrained by construction, do not.

Significance and Claims
The paper claims that the choice of decoder is not merely a performance trade-off but an interpretability choice. The RECOURSE training regime, rather than just its softer masking, produces policies that represent infeasibility usefully, exposing actionable counterfactuals that HARD-MASK policies cannot. Furthermore, the study demonstrates that graph inductive bias improves both representational predictability and decoder sanity. The authors conclude that neural combinatorial optimization solvers require a joint XAI account of both representation and decision stages to be operationally viable, as a legible encoder does not guarantee a legible decoder, and vice versa. The protocol serves as a standard grid for comparing solver families on the same checkpoints, revealing that the "best" solver depends on whether the priority is raw cost or the ability to validate and compare decisions.

1. The Two Parts of the Robot

2. The Three Ways to Ask "Why?"

3. The Big Discoveries

The Bottom Line

Technical Summary: Two Black Boxes, One Solver

More like this