Elamur Research⌕
☰
home / papers / 2020 / A simple repair mechanism can alleviate computational demands of pragmatic reasoning: simulations and complexity analysis

A simple repair mechanism can alleviate computational demands of pragmatic reasoning: simulations and complexity analysis

Paper · 2020 · Jacqueline van Arkel, Marieke Woensdregt, Mark Dingemanse et al.

Summary

The paper asks how people can resolve ambiguity in conversation without heavy mental computation. It compares two disambiguation strategies, each isolated in its own agent-based model. In the first, agents reason pragmatically about one another, following the rational speech act (RSA) framework. In the second, agents interpret signals only literally but can initiate repair. The repair mechanism is new. A listener computes the conditional entropy over possible referents. If that uncertainty exceeds a tolerance threshold, the listener sends an open request, roughly a "Huh?". The speaker then sends another signal compatible with the intended referent, and the listener intersects the candidate sets. Simulations over binary signal–referent lexicons measure communicative success and interaction length, and a computational complexity analysis estimates the cost of reasoning. Repair agents reach roughly the same success as pragmatic agents with far less computation, but their exchanges take more turns. The outcome depends heavily on how each mechanism is formalised. The work matters because it shows that interaction can serve as a cheap substitute for expensive inference.

Key points

  • Two isolated baselines are compared. One model uses RSA-style recursive pragmatic reasoning without repair. The other uses literal agents (order of inference n = 0) that can repair.
  • Repair is triggered when the conditional entropy H(R | signal, dialogue history) exceeds a threshold H_t. Once uncertainty drops below H_t, the listener picks the referent with maximum posterior probability.
  • Repair is resolved by conjunction: each new signal's referent vector is intersected with those of earlier signals in the dialogue history. The example lexicon (4 signals × 4 referents) has an ambiguity level of 0.5.
  • Efficiency is defined as success divided against total cost, where cost is computation plus interaction. Repair lowers the computational burden at the price of longer dialogues.
  • Background figures and limitations:
    • Cross-linguistic data show conversational repair occurs about once every 1.4 minutes.
    • Repair initiations come in three types: open request, restricted request and restricted offer.
    • All agents share an identical lexicon, which is a major simplification.
    • Inferring a partner's lexicon would mean searching an exponential space of 2^n possible lexicons.
    • Code and simulation data are on OSF.

Interesting ideas

  • I1. Entropy over candidate interpretations works as an explicit "I'm not sure" gate: below the threshold the system commits, above it the system asks instead of guessing, which keeps failure points visible.
  • I2. Cheap literal processing plus iterative intersection of constraints can rival costly recursive reasoning, which is a strong argument for trying the simple filter before deep inference.
  • I3. Cost accounting should separate computation from interaction, so one strategy can trade one cost for the other and both are measured, not just accuracy.
  • I4. A proposed hybrid agent stays cheap by default and escalates to deeper reasoning only after a repair signal, though the paper warns that the meta-level decision has its own cost.
  • I5. Complexity analysis exposes hidden intractability, such as reasoning over all 2^n possible partner lexicons, before anyone builds the system.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (frames): coreference and implicature resolution in prag could compute entropy over candidate antecedents or readings and emit a logged clarification or "ambiguous" flag rather than a forced pick.
  • I2 (world): when several facts each narrow down which entity is meant, intersecting their candidate sets step by step gives an auditable resolution trail before any heavier reasoning is invoked.
  • I3 (learn): evaluations could report accuracy alongside compute per item and the number of teacher/LLM queries or clarification turns, exposing real efficiency trade-offs.
  • I4 (answer): readers could answer with literal frame matching first and escalate to pragmatic or world-level inference only when confidence is low, while tracking the extra cost of escalation.
  • I5 (learn): self-induced repair rules and dialect-adaptation ideas should get a quick search-space size check, so that exponential hypothesis spaces are avoided by design.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of GroningenGroningen · Netherlands49 works · 4,843 citations🎓Radboud University NijmegenNijmegen · Netherlands12 works · 1,092 citations🎓Center for Language StudiesNijmegen · Netherlands2 works · 198 citations

Also on the byline: Donders Centre for Cognition.

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 510 works

Cite

Cite as Jacqueline van Arkel, Marieke Woensdregt, Mark Dingemanse and Mark Blokpoel. 2020. A simple repair mechanism can alleviate computational demands of pragmatic reasoning: simulations and complexity analysis. Proceedings of the 24th Conference on Computational Natural Language Learning.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2020.conll-1.14

@inproceedings{arkel2020simple,
  title = {{A simple repair mechanism can alleviate computational demands of pragmatic reasoning: simulations and complexity analysis}},
  author = {Jacqueline {van Arkel}, Marieke Woensdregt, Mark Dingemanse and Mark Blokpoel},
  booktitle = {Proceedings of the 24th Conference on Computational Natural Language Learning},
  year = {2020},
  doi = {10.18653/v1/2020.conll-1.14},
  url = {https://doi.org/10.18653/v1/2020.conll-1.14}
}

References

37 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Aashraf M. Abdelbar and Sandra M. Hedetniemi. 1998. Approximating MAPS for belief networks is NP-hard and other theorems. Artificial Intelligence, 102(1):21–38. ↗
  2. Saul Albert and Jan-Peter de Ruiter. 2018. Improving Human Interaction Research through Ecological Grounding. Collabra: Psychology, 4(1). ↗
  3. Mark Blokpoel, Mark Dingemanse, Marieke Woensdregt, George Kachergis, Sara Bögels, Ivan Toni, and Iris van Rooij. 2020. Pragmatic communicators can overcome asymmetry by exploiting ambiguity. Preprint, Open Science Framework. ↗
  4. Tom Bylander, Dean Allemang, Michael C Tanner, and John R Josephson. 1991. The computational complexity of abduction. Artificial Intelligence, 49(1–3):25–60. ↗
  5. Andy Clark. 2006. Material Symbols. Philosophical Psychology, 19(3):291–307. find
  6. Herbert H. Clark and Edward Schaefer. 1987. Collaborating on contributions to conversations. Language and Cognitive Processes, 2(1):19–41. ↗
  7. Herbert H. Clark and Deanna Wilkes-Gibbs. 1986. Referring as a collaborative process. Cognition, 22(1):1–39. ↗
  8. Micheal R Garey and David S. Johnson. 1979. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman, San Francisco, CA. find
  9. Edward Gibson, Richard Futrell, Steven T. Piandadosi, Isabelle Dautriche, Kyle Mahowald, Leon Bergen, and Roger Levy. 2019. How Efficiency Shapes Human Language. Trends in Cognitive Sciences, 23(5):389–407. ↗
  10. Jonathan Ginzburg and Raquel Fernández. 2010. Computational models of dialogue. In Alexander Clark, Chris Fox, and Shalom Lappin, editors, The handbook of computational linguistics and natural language processing, Blackwell handbooks in linguistics. Wiley-Blackwell, Chichester, West Sussex ; Malden, MA. ↗
  11. Noah D. Goodman and Michael C. Frank. 2016. Pragmatic language interpretation as probabilistic inference. Trends in Cognitive Sciences, 20(11):818– 829. ↗
  12. Herbert P. Grice. 1975. Logic and Conversation. In Herbert P. Grice, editor, Studies in the Way of Words, pages 305–315. Harvard University Press. ↗
  13. Pim F. Haselager. 1997. Cognitive Science and Folk Psychology: The Right Frame of Mind. Sage, London. find
  14. Robert X. D. Hawkins, Michael C. Frank, and Noah D. Goodman. 2017. Convention-formation in iterated reference games. Proceedings of the 39th Annual Meeting of the Cognitive Science Society. ↗
  15. Maryellen C. MacDonald, Neal J. Pearlmutter, and Mark S. Seidenberg. 1994. Lexical nature of syntactic ambiguity resolution. Psychological Review, 101(4):676–703. find
  16. David J. C. MacKay. 2003. Information Theory, Inference and Learning Algorithms. Cambridge University Press. ↗
  17. Maria Otworowska, Mark Blokpoel, Marieke Sweers, Todd Wareham, and Iris van Rooij. 2018. Demons of ecological rationality. Cognitive Science, 42(3):1057–1066. ↗
  18. Mark Dingemanse. 2020. Resource-rationality beyond individual minds: the case of interactive language use. Behavioral and Brain Sciences, 43:e9. ↗
  19. Mark Dingemanse, Seán G. Roberts, Julija Baranova, Joe Blythe, Paul Drew, Simeon Floyd, Rosa S. Gis-ladottir, Kobin H. Kendrick, Stephen C. Levinson, Elizabeth Manrique, Giovanni Rossi, and Nick Enfield, J. 2015. Universal principles in the repair of communication problems. PLoS ONE, 10(9):1–15. ↗
  20. Robert Downey and Mike Fellows. 1999. Parameterized complexity. Springer, Berlin. find
  21. Jerry A. Fodor. 2000. The Mind Doesn’t Work That Way: The Scope and Limits of Computational Psychology. MIT press, Cambridge, MA. find
  22. Michael C. Frank and Noah D. Goodman. 2012. Predicting pragmatic reasoning in language games. Science, 336(6084):998. ↗
  23. Steven T. Piantadosi, Harry Tily, and Edward Gibson. 2012. The communicative function of ambiguity in language. Cognition, 122(3):280–291. ↗
  24. Matthew Purver, Julian Hough, and Christine Howes. 2018. Computational Models of Miscommunication Phenomena. Topics in Cognitive Science. ↗
  25. Evan F. Risko and Sam J. Gilbert. 2016. Cognitive Offloading. Trends in Cognitive Sciences, 20(9):676– 688. find
  26. Jan-Peter de Ruiter and Chris Cummins. 2012. A model of intentional communication: AIRBUS (Asymmetric Intention Recognition with Bayesian Updating of Signals). Proceedings of SemDial 2012, pages 149–50. find
  27. Emanuel A. Schegloff. 1992. Repair After Next Turn: The Last Structurally Provided Defense of Intersubjectivity in Conversation. American Journal of Sociology, 97(5):1295–1345. ↗
  28. Emanuel A. Schegloff, Gail Jefferson, and Harvey Sacks. 1977. The Preference for Self-Correction in the Organization of Repair in Conversation. Language, 53(2):361–382. ArticleType: primary article / Full publication date: Jun., 1977 / Copyright c 1977 Linguistic Society of America. ↗
  29. Julian J. Schlöder and Raquel Fernández. 2015. Clarifying Intentions in Dialogue: A Corpus Study. In Proceedings of the 11th International Conference on Computational Semantics (IWCS-2015), London. find
  30. Dan Sperber and Deirdre Wilson. 1986. Relevance: Communication and Cognition, first edition. Blackwell Publishing. find
  31. Paul Thagard and Karsten Verbeurgt. 1998. Coherence as constraint satisfaction. Cognitive Science, 22(1):1–24. ↗
  32. Iris van Rooij. 2008. The Tractable Cognition Thesis. Cognitive Science, 32(6):939–984. ↗
  33. Iris van Rooij and Giosuè Baggio. 2020. Theory before the test: How to build high-verisimilitude explanatory theories in psychological science. Preprint, PsyArXiv. ↗
  34. Iris van Rooij, Mark Blokpoel, Johan Kwisthout, and Todd Wareham. 2019. Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis. Cambridge University Press. find
  35. Iris van Rooij, Johan Kwisthout, Mark Blokpoel, Jakub Szymanik, Todd Wareham, and Ivan Toni. 2011. Intentional Communication: Computationally Easy or Difficult? Frontiers in Human Neuroscience, 5. ↗
  36. Thomas Wasow, Andrew Perfors, and David Beaver. 2005. The puzzle of ambiguity. In O Orgun and P Sells, editors, Morphology and The Web of Grammar: Essays in Memory of Steven G. Lapointe, pages 265–282. CSLI Publications. find
  37. Deanna Wilkes-Gibbs and Herbert H Clark. 1992. Coordinating beliefs in conversation. Journal of Memory and Language, 31(2):183–194. ↗

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/arkel-2020-simple-repair-mechanism-can-alleviate/