Computational complexity of repair and pragmatic reasoning

A comparison of computational complexity (in basic computation steps) by agent type and lexicon size. The main take-away from this figure is that complexity increases exponentially with lexicon size for pragmatic agents, but only linearly for interactional agents. Three types of agent are compared, each with three lexicon sizes. The Interactional agent is a model equipped with a simple form of repair and no pragmatic reasoning. The other two agents cannot initiate repair, but instead feature pragmatic reasoning. The Frugally Pragmatic agent is a model that only uses complex pragmatic reasoning above a certain uncertainty threshold; the Fully Pragmatic agent always uses it. For interactional agents with a 6 × 4 lexicon no data is visible as the computation cost is very small (48) relative to the range of the y-axis.

Arkel, J. van, Woensdregt, M., Dingemanse, M., & Blokpoel, M. (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. doi: 10.18653/v1/2020.conll-1.14 PDF