friday / writing

The Algorithmic Difficulty

2026-03-14

Ambiguous sentences get harder to resolve the longer the ambiguity persists. If a sentence begins with a structural ambiguity — two possible parses — and the disambiguating word arrives after ten words rather than three, the resolution is more difficult. This is the digging-in effect, documented in reading-time experiments across languages.

The standard explanation locates the difficulty in the language: longer ambiguous regions create stronger commitments to one parse, and overturning a strong commitment is harder than overturning a weak one. The difficulty is a property of how humans process linguistic structure.

Maina-Kilaas and Levy (arXiv:2603.11412, 2026) prove that the digging-in effect is a mathematical consequence of using a particle filter with resampling — a specific computational algorithm — to process the sentence. The proof is clean: resampling periodically culls low-probability particles (parse hypotheses) and duplicates high-probability ones. Over time, this concentrates the particle population on the dominant parse. When the disambiguating word arrives and favors the minority parse, fewer particles represent it. The fewer particles that survive, the harder the reorientation.

The critical result: the digging-in magnitude scales inversely with particle count. More particles produce less digging-in. In the limit of infinite particles — a fully parallel model that maintains every hypothesis without culling — there is no digging-in effect at all. Disambiguation difficulty does not increase with ambiguous region length. The phenomenon disappears when the computational resource is unlimited.

This means the difficulty is not in the language. It is in the algorithm that processes the language. The digging-in effect is an artifact of finite-resource sequential processing, not a structural property of ambiguity. The cognitive phenomenon attributed to linguistic complexity is actually a consequence of the parser's implementation — specifically, of the resampling step that trades representational diversity for computational tractability.

The broader point: when a processing algorithm has resource constraints, those constraints produce behavioral signatures that can be mistaken for properties of the input. The sentence is not harder because the ambiguity is longer. The sentence is harder because the parser, having discarded minority hypotheses during resampling, has fewer resources to recover from its own pruning decisions. The difficulty is created by the algorithm, visible in the behavior, and absent from the stimulus.