🤖 machine learning

Learning the Error Patterns of Language Models

This paper introduces "prefix filters" and the "Palla" algorithm to efficiently learn and apply domain-specific constraints that capture and correct common LLM error patterns, significantly improving output validity such as TypeScript compilation rates.

Original authors: Jinwoo Kim, Taylor Berg-KirkPatrick, Loris D'Antoni

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jinwoo Kim, Taylor Berg-KirkPatrick, Loris D'Antoni

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 very talented but slightly clumsy robot assistant. It's great at writing code, summarizing stories, or designing chemical molecules, but it has a few specific, repetitive bad habits. Sometimes it uses a word that doesn't exist in the language it's supposed to be speaking. Other times, it accidentally leaks a person's name when it's supposed to keep it secret.

The paper "Learning the Error Patterns of Language Models" introduces a new way to fix these robots without having to retrain them from scratch or hire a human to watch over them constantly.

Here is the breakdown of their solution, using simple analogies:

1. The Problem: The Robot's "Bad Habits"

When these AI models try to do specific tasks (like writing a program that must compile), they don't fail randomly. They fail in clusters.

The Analogy: Imagine a chef who is trying to bake a cake. They don't fail every single time in a different way. Instead, they always forget to add sugar, or they always burn the bottom because they set the oven too hot. They have specific "error modes."
The Reality: The researchers found that if you ask an AI to write TypeScript code, it might fail 50% of the time, but 80% of those failures happen because of just three or four specific mistakes (like trying to reassign a constant variable or putting an import statement in the wrong place).

2. The Solution: "Prefix Filters" (The Bouncer)

The authors propose creating "Prefix Filters." Think of these as a bouncer at a club, but instead of checking IDs, they check the beginning of what the robot is writing.

How it works: As the robot starts typing a sentence or a line of code, the bouncer (the filter) looks at the first few words.
The Decision: If the bouncer sees a pattern that matches a known "bad habit" (e.g., "Oh, you're starting with import inside the function body? That's a mistake we've seen a thousand times. Stop."), they cut the robot off immediately.
The Result: The robot is forced to try again, but this time it has to start differently. It's like a teacher saying, "No, that sentence starts wrong. Try again," before the student even finishes the paragraph.

3. The Algorithm: PALLA (The Detective)

How do you know what the robot's bad habits are? You don't need to guess. The paper introduces an algorithm called PALLA (Prefix-filters for Learning and Adapting to LLMs).

The Process:
1. Let the robot run wild: PALLA lets the AI generate hundreds of samples without any rules.
2. Catch the failures: It uses a "judge" (like a compiler for code or a safety checker for summaries) to find the bad outputs.
3. Group the mistakes: It notices that the failures aren't random; they cluster together.
4. Ask a smarter robot: PALLA asks a larger, smarter AI to look at these clusters of mistakes and write a simple "rule" (a Python function) that catches them.
5. Test the rule: It checks if the rule is fair. Does it catch the bad stuff? Does it accidentally stop the robot from writing good stuff? If it's too strict, it tweaks the rule.

4. The Results: A Massive Boost

The researchers tested this on five different AI models across four different tasks (writing MLIR code, designing molecules, summarizing HR dialogues, and writing TypeScript).

The "Magic" Number: They found that for many models, just 132 simple rules (filters) were enough to stop almost all the bad outputs.
The Analogy: It's like teaching a student to avoid the top 5 most common math errors. Suddenly, their test scores jump from a D to an A, not because they learned new math, but because they stopped making the silly mistakes they always made.
The Outcome:
- Code: A small AI model (Qwen-1.5B) that usually failed to compile code 84% of the time suddenly started compiling 70% of the time. With these filters, it performed as well as a much larger, more expensive AI model (Llama-8B) that had no filters at all.
- Safety: In summarizing HR conversations, the filters successfully stopped the AI from leaking names and phone numbers without making the summaries sound robotic or missing important details.

5. The Catch (Limitations)

The paper is honest about where this doesn't work perfectly:

The "Already Good" Problem: If an AI is already very good at a task (like Gemma-12B with TypeScript), there aren't enough mistakes to learn from, so the filters don't help much.
The "Tail" Problem: Sometimes the robot makes a mistake at the very end of a long sentence. The filter only catches the beginning. If the mistake happens late, the filter might miss it, or the robot might waste a lot of time trying to fix it.
Transferability: A filter trained on one AI model (like Qwen) doesn't always work perfectly on another (like Llama). Every robot has its own unique bad habits.

Summary

The paper argues that instead of trying to make AI models perfect (which is hard), we should just learn their specific, repetitive bad habits and build simple "bouncers" to stop them before they finish a bad sentence. This is a cheap, fast, and effective way to make AI much more reliable for specific jobs.

Technical Summary: Learning the Error Patterns of Language Models

Problem Definition

Large Language Models (LLMs) frequently generate outputs that violate specific validity constraints required by their application domains, such as code that fails to compile, chemically invalid molecules, or summaries that leak private information. While techniques like grammar-constrained decoding exist, they often fail to capture complex validity properties (e.g., type safety or semantic correctness) that cannot be precisely defined by a grammar. Conversely, fine-tuning approaches require significant computational resources and data.

The central observation motivating this work is that LLM errors are not uniformly distributed across the space of invalid outputs. Instead, a specific model operating on a specific domain tends to fail in a small number of repetitive, clustered ways (e.g., using a non-existent operator or inserting characters in invalid locations). The paper asks whether these specific error patterns can be learned and suppressed to constrain model outputs effectively.

Methodology

Prefix Filters

The authors propose prefix filters, which are per-domain-and-LLM symbolic functions (e.g., Python functions) that analyze the prefix of a generated sample. A filter triggers (returns false) if the prefix indicates the sample has already gone wrong or is likely to fail regardless of future completion.

Soundness vs. Distributional Soundness: Ideally, a filter should be "sound" (never rejecting a valid completion). However, enforcing strict soundness is often undecidable. Instead, the authors introduce distributional soundness: a filter is acceptable if it mis-triggers on valid generations with a probability below a small threshold $\epsilon$ . This allows for simpler, learnable filters that approximate the boundary between valid and invalid outputs by sacrificing rare, low-probability valid cases.

PALLA Algorithm

The paper introduces PALLA (Pattern Learning for Language Models), an algorithm to learn these prefix filters without extensive domain knowledge or human intervention. The process involves four steps:

Sampling: Unconditionally sampling the target LLM on domain-specific tasks to generate a set of outputs.
Validation: Using an external oracle (e.g., a compiler, chemical validity checker, or leak detector) to classify samples as valid or invalid.
Clustering: Grouping invalid samples based on the specific error cause provided by the oracle.
Synthesis: Querying a separate, larger "synthesizer" LLM (e.g., GPT-5.4-mini) with the grouped invalid samples and valid samples to distill concrete prefix filters (Python code) that capture the error patterns.
Verification: Validating candidate filters for distributional soundness and effectiveness. If a filter fails validation, the synthesizer is re-queried with feedback on the failure reason.

Constrained Generation

Once a set of prefix filters is learned, the paper employs Constrained Adaptive Rejection Sampling (CARS) during inference. As the model generates tokens, the current prefix is checked against all learned filters. If a filter triggers, the sample is rejected immediately, the probability trie is updated to ban the offending prefix, and sampling restarts. This allows the model to avoid clustered error modes dynamically.

Key Contributions

Prefix Filters: The proposal of per-domain-and-LLM symbolic functions as a mechanism to capture and suppress specific error modes, offering a middle ground between rigid grammars and heavy fine-tuning.
PALLA: An algorithm for automatically learning these filters from unconstrained samples using an external synthesizer, requiring no manual rule engineering.
Empirical Evaluation: A comprehensive evaluation across 4 domains (MLIR code generation, chemical molecule generation, dialogue summarization, and TypeScript generation) and 5 LLMs (Qwen2.5 variants, Llama3.1-8B, Gemma3-12B).

Results

The evaluation demonstrates that PALLA can learn effective prefix filters from a modest number of unconstrained samples:

Error Clustering: The "cluster hypothesis" is validated; a small number of filters (often the top 3) capture a significant portion of errors. For example, in MLIR generation, the top 3 filters for Qwen-7B caught 51.7% of all errors.
Validity Gains:
- TypeScript: PALLA boosted the compile rate for Qwen2.5-1.5B by over 60%, allowing the 1.5B model to achieve performance comparable to the unconstrained 8B Llama3.1 model.
- MLIR: Grammar-constrained decoding failed to prevent prevalent errors like using undefined operators, whereas prefix filters significantly improved compile rates (e.g., Qwen-14B improved from 27.5% to 71.0%).
- Summaries: Filters successfully reduced information leaks in dialogue summaries without significantly reducing the inclusion of non-sensitive information.
Transferability: Filter transferability is domain-dependent. Filters generalize well across models for domains with universal error modes (e.g., name leaks in summaries) but perform poorly for domains where error patterns are model-specific (e.g., MLIR and molecules).
Overhead: The token cost per sample increased moderately for most domains (e.g., ~30% for molecules, ~60% for MLIR) but was significantly higher for TypeScript with weaker models (up to 900% for Qwen-1.5B) due to repeated rejections of tail-end errors.

Significance and Limitations

The paper claims that prefix filters provide a practical, efficient method to constrain LLM outputs by targeting the specific, repetitive failure modes of a given model. This approach offers quantitative insights into how different LLMs fail and provides a mechanism to improve reliability without retraining.

Limitations acknowledged by the authors:

Competence Threshold: The method is ineffective for models that are already highly competent in a domain, as there are too few invalid examples to learn effective filters.
Non-Prefix Errors: If an error is not expressible as a prefix constraint (e.g., a valid prefix leading to an invalid suffix due to a global constraint), PALLA cannot learn a filter for it.
Transferability: Filters are often specific to the model they were trained on and do not always transfer to other models, particularly in complex domains like code generation.
Overhead: In cases where models make frequent errors or errors late in the generation process, the rejection sampling overhead can become substantial.

The authors conclude that while prefix filters do not solve all constrained generation problems, they offer a powerful tool for analyzing and mitigating specific, clustered error patterns in LLMs.