Risk of one wrong answer multiplying in large language model pruning
How Much Does One Wrong Answer Cost? Error Propagation in Constraint Pruning with Noisy LLM Oracles
Machine Learning
Summary
When using large language models to answer many yes/no questions, skipping some questions based on earlier answers can save time. However, if the model makes a mistake, the error can spread across many related answers, causing a big problem. The authors study how much damage one wrong answer can cause, depending on the order of questions and the type of logical rules involved. They find some orders and rules make errors worse, while others keep the spread limited.
What this means in practice
- •For entity resolution engineers: Reduce error spread in linking records by choosing query orders that minimize cascading mistakes in large language model decisions.
- •For data integration teams: Improve accuracy of automated data merging tools by limiting the multiplication of errors caused by wrong side decisions in constraint pruning.
Authors
Zhengtao Gui, Weining Shen
Abstract
Constraint pruning saves queries to a large language model (LLM) or another noisy oracle by skipping each yes/no question implied by answers accepted earlier, for example through transitivity. Entity-resolution systems and LLM-based rankers use this idea. However, their analyses typically assume a correct oracle. We argue that pruning should be judged by its risk when the oracle errs, since an accepted wrong answer spreads to every question it implies. When each answer is wrong independently with small probability $\varepsilon$, the first-order risk is set by how many facts one wrong answer corrupts on average. We consider two kinds of constraints. For implication rules, as in taxonomies, pruning in a random order adds no first-order risk: a wrong answer that would change $k$ facts is accepted with probability $1/k$, so it costs one fact on average. Rules with $s$ premises break this balance: a wrong answer at a premise shared by $r$ rules can cost order $r^{1-1/s}$ facts. For entity resolution with $m$ records of one entity, the first-order risk equals $\varepsilon$ times the Wiener index (the total pairwise distance) of the spanning tree built by the query order. Pivot orders, which first compare one record with all others, amplify errors by less than 2 and are optimal; random orders by order $m^{1/3}$; the common most-similar-first order is the worst in one dimension and, for large $m$, worse than random in two. With several entities, the cost of wrongly merging two does not depend on how many others exist. Simulations agree with every predicted constant within sampling error.