💬 NLP

Algorithmic Consequences of Particle Filters for Sentence Processing: Amplified Garden-Paths and Digging-In Effects

This paper argues that while large language models fail to capture structural ambiguity's impact on sentence processing, particle filter models explicitly represent such ambiguity and algorithmically predict amplified garden-path effects and "digging-in" phenomena—where disambiguation difficulty increases with ambiguous region length due to the resampling mechanism.

Original authors: Amani Maina-Kilaas, Roger Levy

Published 2026-03-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Amani Maina-Kilaas, Roger Levy

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

The Big Picture: How We Read Sentences

Imagine your brain is a detective trying to solve a mystery as you read a sentence word by word. Every time you see a new word, your brain has to guess: "What is this sentence going to be about?"

Sometimes, the sentence is tricky. You might read: "The old man the boat."

First thought: "The old man" is the subject (a person).
Second thought: Wait, "man" is actually a verb here (to operate). The sentence means "The old people operate the boat."

This moment of confusion is called a garden-path effect. Your brain went down the wrong path and has to backtrack.

For a long time, scientists thought our brains were like super-computers that kept every single possible meaning of a sentence in their head at once. If you read a tricky sentence, the computer just checks all options and picks the right one.

However, recent studies showed that super-computers (like advanced AI) are actually too good at this. They predict that tricky sentences should be easy to read, but humans find them very hard. This suggests our brains aren't super-computers; they are more like resource-limited detectives who can only hold a few ideas in their head at a time.

The Solution: The "Particle Filter" Model

The authors of this paper suggest our brains use a method called a Particle Filter.

The Analogy: The "Guessing Game" with Marbles
Imagine you are trying to guess the ending of a story. Instead of writing down every possible ending, you have a bag of 100 marbles.

Each marble represents a different guess about the story's structure.
If a guess seems likely, you have more marbles of that color.
If a guess seems unlikely, you have fewer marbles.

As you read new words, you update your marbles:

Check: Does this new word fit the story on the marble?
Discard: If a marble's story doesn't fit, you throw it away.
Resample: This is the crucial step. To keep your bag full, you reach in and pull out new marbles based on the ones that survived. If you have 80 red marbles (likely) and 20 blue marbles (unlikely), you are very likely to pull out red ones and maybe lose the blue ones entirely.

The Problem: "Digging In"

The paper proves a surprising mathematical fact about this "Resampling" step.

The Analogy: The Treadmill of Doubt
Imagine you are walking on a treadmill. Every time you take a step (read a word), the machine shakes the bag of marbles.

If the sentence is clear, the shaking doesn't matter much.
But if the sentence is ambiguous (you don't know which path to take yet), the shaking causes a problem.

Because you only have a limited number of marbles (say, 100), random chance might make you lose the "correct" path's marbles just by accident.

Short Ambiguity: You read a tricky phrase for 2 words. You shake the bag twice. You probably still have the right marble.
Long Ambiguity: You read a tricky phrase for 10 words. You shake the bag 10 times. The more you shake it, the more likely you are to accidentally throw away the "correct" marble and keep only the "wrong" one.

This is called the "Digging-In Effect."
The longer the confusing part of the sentence lasts, the harder it becomes to fix your mistake later, even if you haven't learned any new information. You have "dug in" to the wrong path simply because you kept shaking the bag of guesses.

Why This Matters

Why AI is different from Humans: Large Language Models (AI) act like they have infinite marbles. They never lose the "correct" path by accident. That's why they think confusing sentences are easy. Humans, with our limited "marbles," get stuck.
The Cost of Memory: The paper proves that the more limited our memory (fewer particles/marbles), the more we suffer from these "digging-in" effects.
Real-Time Confusion: It explains why, if you are stuck in a confusing sentence for a long time, it feels harder to recover the more time passes, even if the sentence hasn't changed. The act of trying to maintain the confusion (resampling) actually makes the confusion worse.

The Takeaway

Our brains are efficient, but they are not perfect. To save energy, we only keep a few "hypotheses" (marbles) in our head at once. The paper shows that this strategy has a side effect: the longer a sentence is confusing, the harder it becomes to fix, simply because our limited memory keeps accidentally deleting the right answer.

It's like trying to find a specific needle in a haystack while someone keeps shaking the haystack. If the shake lasts too long, you might accidentally throw the needle away before you even realize it was there.

1. Problem Statement

The paper addresses a discrepancy in Surprisal Theory, the dominant framework for understanding sentence processing difficulty.

The Gap: Surprisal theory posits that processing difficulty is proportional to the information content (surprisal) of a word, calculated as $-\log P(w|context)$ . Large Language Models (LLMs) operationalize this by implicitly marginalizing over all possible syntactic structures. While LLM surprisal predicts reading times well, it systematically underpredicts difficulty when structural expectations are violated (e.g., in garden-path sentences).
The Hypothesis: The underprediction suggests that human parsers do not maintain all possible structural hypotheses simultaneously (total parallelism) as LLMs do. Instead, humans likely use limited parallelism, maintaining only a finite set of hypotheses.
The Question: How does a limited-parallelism architecture, specifically Particle Filter (PF) models, behave algorithmically? Does the mechanism used to manage these limited hypotheses (resampling) introduce specific processing costs, such as "digging-in" effects, that standard surprisal theory misses?

2. Methodology

The authors employ a rigorous mathematical and theoretical analysis of Particle Filter models applied to syntactic parsing, rather than empirical behavioral experiments.

Model Definition: They define a Particle Filter where $N$ particles represent a finite set of syntactic hypotheses ( $T$ ). Each particle has a weight based on its plausibility.
The Process:
1. Update: Weights are updated based on how well the particle's structure predicts the incoming word.
2. Resampling: Particles are resampled with replacement according to their weights. This step is crucial: it converts a weighted set into an unweighted set, potentially eliminating low-probability structures entirely due to sampling variance.
Formal Setup:
- They assume a "neutral" ambiguous region where new words provide no new structural information ( $Q$ and $\pi$ remain fixed). This isolates the resampling mechanism as the sole source of change.
- They analyze the Expected Surprisal ( $E[S]$ ) over the distribution of possible particle sets.
- They derive the Surprisal Delta ( $\Delta S$ ), representing the increase in expected surprisal per resampling step.
Approximations: To analyze the non-linear dynamics of resampling, they utilize:
- Jensen's Inequality: To prove monotonic increases in surprisal.
- Second-Order Taylor Expansion: To approximate the surprisal delta based on the coefficient of variation of word probabilities.
- Linear-Diffusion Approximation: Drawing from Wright-Fisher genetic drift models to estimate the time to convergence (when only one structure remains).

3. Key Contributions & Theoretical Results

The paper provides formal proofs for three major algorithmic consequences of using particle filters in sentence processing:

A. Limited Parallelism Increases Expected Surprisal (Theorem 1)

Finding: Even without new information, the act of resampling particles causes the expected surprisal of a word to increase monotonically.
Mechanism: Due to the convexity of the $-\log(x)$ function (Jensen's Inequality), the expectation of the log-probability is less than the log of the expectation. Sampling variance shifts the distribution, increasing the average surprisal.
Implication: Particle filter models inherently predict higher processing costs than fully parallel models (like LLMs) simply because they maintain fewer hypotheses.

B. Amplification of Garden-Path Effects (Theorems 3 & 4)

Finding: The increase in surprisal is not uniform; it is amplified for words that disambiguate toward dispreferred structures.
Mechanism: The "Surprisal Delta" is proportional to the coefficient of variation of word probabilities across the current set of particles.
- In a garden-path scenario, the parser holds a preferred structure (high weight) and a dispreferred one (low weight).
- If the incoming word supports the dispreferred structure, the probability $Q$ varies wildly across the particles (some say 0, some say high).
- This high variance maximizes the surprisal delta, making the "reanalysis" step significantly harder than in unambiguous contexts.

C. Resampling Produces Real-Time "Digging-In" Effects

Finding: This is the paper's most critical contribution. Digging-in (where disambiguation difficulty increases with the length of the ambiguous region) is an inherent property of particle filters with resampling.
Mechanism:
- Longer ambiguous regions induce more resampling steps.
- Each step introduces sampling variance, which can randomly eliminate the correct (but currently dispreferred) structural hypothesis.
- As the number of resampling steps increases, the probability that the correct structure has been "drifted out" of the particle set increases.
- If the correct structure is lost, the parser cannot recover, leading to a massive spike in surprisal (or parse failure).
Scaling: The magnitude of the digging-in effect is inversely proportional to the particle count ( $N$ ).
- Low $N$ : Strong digging-in effects.
- High $N$ (approaching infinity): The effect vanishes, recovering the predictions of fully parallel models.

4. Results & Simulations

The authors validate their theorems through simulations:

Figure 1: Shows expected surprisal rising over resampling steps. The rise is steeper for contexts where the word strongly disambiguates to a dispreferred structure.
Figure 2: Demonstrates that as $N$ decreases, the gap between ambiguous and unambiguous contexts (garden-path effect) widens, and the slope of difficulty over ambiguous region length (digging-in) increases.
Approximation Accuracy: The Second-Order Approximation (based on variance) and the Linear-Diffusion Approximation (based on convergence time) both closely match the empirical surprisal delta. The second-order approximation is particularly strong for correlation ( $r^2 = 0.82$ ).

5. Significance and Implications

Bridging Rational and Dynamical Models: Traditionally, "digging-in" effects were associated with dynamical systems models (e.g., Tabor & Hutchins), which rely on feedback loops where preferred states grow stronger over time. This paper proves that rational approximation models (Particle Filters) also predict digging-in, but through a different mechanism: stochastic drift and sampling variance during resampling.
Re-evaluating LLMs: The results explain why LLMs (which effectively use infinite parallelism) fail to capture the full magnitude of garden-path difficulties. Human parsers, being resource-limited, suffer from the "cost of resampling."
Empirical Predictions:
- If human data shows robust real-time digging-in, it supports limited-parallelism models with regular resampling.
- If digging-in is absent, it suggests human parsers might use selective updating (keeping low-probability parses alive longer than a standard PF would) rather than standard resampling.
- The degree of digging-in observed in human behavior could be used to estimate the effective particle count ( $N$ ) of the human parser.

Conclusion

Maina-Kilaas and Levy demonstrate that the algorithmic necessity of resampling in particle filter models creates a specific, quantifiable processing cost: real-time digging-in. This provides a principled, rational account for why structural violations are harder to process than standard surprisal theory predicts, linking the cognitive architecture of limited parallelism directly to observable psycholinguistic phenomena.