Compact Example-Based Explanations for Language Models

1. Problem Statement

Training data influence estimation methods (e.g., Influence Functions, DataInf, LESS) aim to quantify how specific training documents contribute to a model's prediction. While these methods offer a theoretical basis for example-based explanations (explaining a model's output by showing relevant training examples), they face a critical practical bottleneck: selection.

• The Scale Issue: Influence estimates often rank thousands of documents. Humans cannot interpret such large sets, necessitating the selection of a small subset (e.g., $k=5$ to $k=25$).
• The Flaw in Naive Selection: Existing systems typically select the top-$k$ examples based on influence scores. The authors argue this is suboptimal because:
  1. Global Outliers: High-influence examples are often global outliers (e.g., mislabeled data or unique edge cases) that are not locally relevant to the specific test instance.
  2. Redundancy: Top-ranked examples often cluster in feature space, providing redundant information rather than a diverse set of supporting evidence.
• Evaluation Gap: Previous evaluations focused on the accuracy of the influence estimates (e.g., correlation with leave-one-out retraining) or user studies of the full system. They largely ignored the selection strategy itself, meaning a system could appear helpful even if the selected examples were poor.

2. Methodology

The paper proposes a new evaluation framework and a novel selection strategy, moving away from costly retraining experiments.

A. Selection Relevance Score ($\xi_{SR}$)

The core contribution is a retraining-free metric called the Selection Relevance Score. It treats explanation selection as a gradient reconstruction task.

• Concept: A set of selected training examples is considered "relevant" if their loss gradients can linearly reconstruct the loss gradient of the test instance.
• Mathematical Formulation:
  • Let $\nabla L'$ be the gradient of the loss for the test instance.
  • Let $A$ be a matrix where columns are the gradients of the $k$ selected training examples.
  • The goal is to find coefficients $t$ such that $\hat{\nabla}L' = At \approx \nabla L'$.
  • The score is defined as the ratio of the expected squared norm of the true gradient to the expected squared reconstruction error:
    $$\xi_{SR} = \frac{E[\|\nabla L'\|^2]}{E[\|\nabla L' - At\|^2]}$$
  • Constraints: The coefficients $t$ are constrained to be non-negative (examples should support or oppose the prediction, not cancel each other out) and sum to 1 (normalizing relative importance).
  • Interpretation: Scores are reported in decibels (dB). A score $>0$ dB indicates the selection provides non-redundant, relevant information. A score $<0$ dB implies the selection is worse than a trivial baseline (zero vector).

B. Validation via Fine-Tuning

To validate $\xi_{SR}$ without ground truth, the authors compare it against two fine-tuning-based metrics:

1. Prediction Support ($\xi_+$): Does fine-tuning on the selected set increase the likelihood of the original prediction?
2. Prediction Shift ($\xi_{JSD}$): Does fine-tuning on the set cause a significant shift in the model's output distribution compared to a random set?

C. Proposed Selection Strategy: Facility Location with Influence

The authors propose a new selection strategy that balances influence and representativeness (coverage) by framing selection as a Facility Location Problem.

• Objective: Maximize a submodular function that combines the marginal gain of coverage (diversity) with the cost of influence.
• Formula: $\Delta_\lambda(j | S) = (\Delta(j|S) + 1)^\lambda \cdot c_j^{1-\lambda}$
  • $\Delta(j|S)$: Marginal gain in coverage (diversity) by adding example $j$ to set $S$.
  • $c_j$: Normalized cost based on influence (lower cost = higher influence).
  • $\lambda$: A hyperparameter balancing coverage ($\lambda=1$) vs. pure influence ($\lambda=0$).
• Implementation: A greedy algorithm selects examples from the top-100 ranked by influence until the budget $k$ is filled.

3. Experimental Setup

• Models: Olmo2-1B, Llama-3.2-1B, Qwen2.5-0.5B.
• Datasets: Tülu3 instruction-tuning dataset (10% sampled for attribution, 1,000 test instances).
• Influence Estimators: DataInf (approximates Influence Functions), LESS (Gradient Similarity), and a BM25 baseline (token overlap).
• Baselines: Naive selection (Top/Bottom $k$ by influence), DIVINE (Diversity + Influence), AIDE.

4. Key Results

A. Naive Selection Fails

• Counter-Intuitive Finding: For gradient-based estimators (DataInf, LESS), selecting the most influential examples (Top-$k$) often yields negative selection relevance scores (worse than random).
• Reasoning: The most influential examples are often unique outliers. Removing them causes large parameter shifts, but they do not reconstruct the test gradient well because they lack local representativeness.
• Best Naive Strategy: Surprisingly, selecting the least influential examples (smallest absolute scores) often outperforms the most influential ones. These examples are "prototypical" and redundant; removing them causes little deviation, making them better at reconstructing the local gradient landscape.

B. The Proposed Strategy Works

• Coverage Improvement: The Facility Location-based strategy (with $\lambda > 0$) significantly improves selection relevance compared to naive Top-$k$ selection.
• Quantitative Gains:
  • For DataInf and LESS, the proposed strategy increased selection relevance by 4–9 dB over naive selection for $k=5$ and $k=10$.
  • It successfully reduced redundancy (fewer examples with similar prompts) while maintaining high influence.
• BM25 Baseline: BM25 (token overlap) performed well on its own but suffered when forced into a pure coverage strategy ($\lambda=1$), confirming that token overlap is a strong proxy for relevance in this context.

C. Validation Correlation

• Correlation with Fine-Tuning: While the overall correlation between $\xi_{SR}$ and fine-tuning metrics was low (due to noise in low-relevance selections), the correlation became substantial ($\rho \approx 0.58$ for support) when filtering for selections with $\xi_{SR} > 0$ dB.
• Implication: The score effectively predicts whether a set of examples will support the model's original prediction during fine-tuning.

5. Significance and Contributions

1. New Evaluation Metric: Introduced $\xi_{SR}$, a retraining-free, gradient-based metric that specifically evaluates the quality of the selection rather than the raw influence estimate.
2. Paradigm Shift in Selection: Demonstrated that "most influential" $\neq$ "most relevant" for explanations. Naive top-k selection often fails, and balancing influence with diversity (representativeness) is crucial.
3. Practical Strategy: Proposed a facility-location-based selection strategy that is computationally efficient and significantly improves the quality of example-based explanations for LLMs.
4. Insight into LLM Behavior: Highlighted that for instruction-tuned models, the most "influential" training points are often outliers, while the most "representative" (and thus best for explanation) are prototypical, lower-influence examples.

Conclusion

The paper argues that the quality of example-based explanations for LLMs depends more on how examples are selected than on the accuracy of the influence estimation itself. By introducing a gradient reconstruction score and a diversity-aware selection strategy, the authors provide a robust framework for generating compact, human-interpretable, and faithful explanations.