Technical Summary: Teaching and Learning under Deductive Errors

Problem Statement

Traditional models of machine teaching and learning operate under the assumption that learners perform perfect deductive inference. Specifically, it is assumed that a learner can consistently and completely check whether a hypothesis is consistent with a given example. However, this assumption fails for significant classes of learners, including humans and Large Language Models (LLMs) in few-shot learning regimes. These learners exhibit deductive errors: they may fail consistency checks stochastically, meaning they might incorrectly classify an example as consistent (or inconsistent) with a concept even when the ground truth suggests otherwise.

The paper argues that standard learning protocols, which discard concepts inconsistent with evidence, fail catastrophically under these conditions because a single stochastic error can permanently eliminate the correct target concept. Furthermore, traditional Probably Approximately Correct (PAC) learning frameworks attribute stochasticity to the sampling of examples, not to the learner's internal inference mechanisms. This paper addresses the gap by introducing a framework where the stochasticity arises from deductive errors in consistency checking.

Methodology

The PAC Teaching Framework

The authors propose an adaptation of the PAC setting, termed PAC Teaching, where examples are chosen deterministically by a teacher rather than sampled randomly. The framework introduces:

1. Deductive Error Function ($\gamma_L$): A probability function $\gamma_L(c, x)$ representing the likelihood that learner $L$ makes an error when checking the consistency of concept $c$ with example $x$.
2. Approximate Consistency: Instead of a binary consistency check, the learner uses an approximate consistency function $\hat{c}_L$.
3. Two Teaching Goals:
   • Teaching for Identification: The goal is for the learner to select a concept $c$ that is similar to the target $c^*$ (i.e., $c(x) = c^*(x)$ with high probability).
   • Teaching for Employment: The goal is for the learner to select a concept $c$ that performs well from the learner's own perspective, accounting for the same errors the learner makes during inference ($\hat{c}(x) = c^*(x)$).

The core objective is to find a teaching set $S$ such that the concept $L(S)$ chosen by the learner satisfies a similarity threshold $q$ with probability at least $p$.

Learner and Teacher Behaviors

The paper defines specific behavioral models to analyze the problem:

• Naive Learner ($L_N$): Discards any concept that appears inconsistent with an example. This learner is highly susceptible to deductive errors.
• Prudent PAC Learner ($L_P$): Aware of potential errors, this learner maintains a count of how many examples each concept is consistent with and selects the concept with the highest count.
• Naive Teacher ($T_N$): Assumes zero error and selects a set to uniquely identify the target for a perfect learner.
• Heuristic PAC Teacher ($T_H$): Uses heuristics (e.g., Uniqueness or Homogeneity scores) to select examples that minimize the impact of errors.
• Optimal PAC Teacher ($T_P$): Computes the mathematically optimal teaching set for the Prudent learner under specific optimization criteria (minimizing set size, maximizing probability, or maximizing approximation ratio).

Experimental Validation

The authors conducted experiments using GPT-5-nano as the learner on a concept class involving divisibility by prime numbers (5, 7, 11, 13, 17).

• Deductive Error Derivation: They measured the frequency of incorrect consistency checks (e.g., "Is 7 a divisor of 735?") to quantify $\gamma_L$.
• Correlation Analysis: They demonstrated a positive correlation between mean deductive error and total teaching error. Crucially, they showed that selecting examples with low deductive error significantly reduces total teaching error, validating the utility of the PAC teaching framework for LLMs.

Key Contributions

1. Formal Framework: The introduction of the PAC Teaching framework, which formally integrates stochastic deductive errors into the machine teaching problem.
2. Complexity Analysis: The paper provides tight computational complexity bounds for computing optimal teaching sets. It identifies six distinct optimization problems (combinations of identification/employment and optimizing for size, probability, or approximation).
   • XP Algorithms: The authors present algorithms with runtime $O(k^3 |C| |X|^k)$ for problems parametrized by the teaching set size $k$.
   • Hardness Results: They prove these problems are W[2]-hard when parametrized by $k$, implying that removing $k$ from the exponent (achieving Fixed-Parameter Tractability) is unlikely unless the W-hierarchy collapses.
   • ETH Bounds: For size-optimization, they show that under the Exponential Time Hypothesis (ETH), no algorithm can run in $2^{o(m)}$ time (where $m$ is the example set size), and under Strong ETH, no algorithm can run in $(2-\epsilon)^m$.
3. Heuristic Algorithms: The proposal of two heuristic strategies for teaching set construction:
   • Uniqueness: Selecting examples that uniquely identify the target with high probability.
   • Homogeneity: Selecting examples where competing concepts are similar to the target, ensuring that even if the learner picks a competitor, it is still "approximately correct."
4. Empirical Evidence: Experimental results with LLMs confirming that deductive errors are measurable and that teaching strategies accounting for these errors (low deductive error examples) yield significantly better learning outcomes than naive strategies.

Results

• Theoretical: The paper establishes that finding optimal PAC teaching sets is computationally hard but solvable with XP algorithms. The runtime bounds are shown to be tight under standard complexity assumptions (ETH, Strong ETH, W-hierarchy).
• Experimental:
  • In low-inductive-load scenarios (teaching sets of size 1), selecting examples with low deductive error resulted in near-zero total teaching error, whereas high-error examples led to failure rates often exceeding 50%.
  • In high-inductive-load scenarios (teaching sets of size 2), the correlation between deductive error and total error remained positive, though the effect was slightly softened by the increased complexity of the inductive task.
  • Heuristic algorithms (Uniqueness and Homogeneity) successfully identified teaching sets with low total error in the size-1 scenario, demonstrating practical utility even without knowing the internal learning algorithm of the LLM.

Significance and Claims

The paper claims that the PAC Teaching framework is a necessary evolution for teaching and learning systems involving imperfect deductive reasoners, such as humans and LLMs. Its significance lies in:

1. Correcting a Fundamental Assumption: It challenges the standard assumption of perfect deductive consistency in machine teaching, offering a model that better reflects the stochastic nature of real-world learners.
2. Bridging Theory and Practice: By providing both rigorous complexity bounds and practical heuristics, the framework offers a theoretical foundation for designing teaching strategies that are robust to learner errors.
3. Explainable AI (XAI) Relevance: The authors note that this framework is particularly relevant for XAI, as it addresses the common assumption that errors originate solely from inductive inference, whereas this work highlights the critical role of deductive fallibility.
4. Applicability to LLMs: The experimental validation suggests that deductive errors in LLMs can be quantified and leveraged to improve few-shot learning outcomes, providing a pathway for more effective human-AI interaction and teaching protocols.

The authors remain modest, noting that while the framework is useful, the derivation of deductive errors and the specific teaching strategies must be adapted for different LLMs and tasks. They do not claim to solve all learning problems but rather provide a robust theoretical and algorithmic toolkit for the specific case of teaching learners with stochastic deductive errors.