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

Abstract: How can people communicate successfully while keeping resource costs low in the face of ambiguity? We present a principled theoretical analysis comparing two strategies for disambiguation in communication: (i) pragmatic reasoning, where communicators reason about each other, and (ii) other-initiated repair, where communicators signal and resolve trouble interactively. Using agent-based simulations and computational complexity analyses, we compare the efficiency of these strategies in terms of communicative success, computation cost and interaction cost. We show that agents with a simple repair mechanism can increase efficiency, compared to pragmatic agents, by reducing their computational burden at the cost of longer interactions. We also find that efficiency is highly contingent on the mechanism, highlighting the importance of explicit formalisation and computational rigour.

## introduction natural languages are rife with ambiguity @xcite , yet people seem to communicate efficiently regardless. how can people communicate successfully in the face of ambiguity while keeping resource costs low? there seem to be at least three strategies communicators have at their disposal. first, contextual information can be used to disambiguate the speaker's intended meaning @xcite @xcite , though context-sensitive computations are notorious in computational cognitive science for the astronomical demands they make on computation time @xcite @xcite . second, pragmatic reasoning allows taking into account the speaker's goal (e.g. 'being informative') @xcite @xcite , but this alone is not always enough to fully disambiguate meaning @xcite . finally, communicators can leverage the interaction itself by explicitly requesting clarification (e.g. by asking 'huh?' or 'who?') in a process known as other-initiated repair @xcite . this provides a possible way for communicators to reduce their computational burden through interaction, potentially increasing communicative efficiency @xcite . to investigate the computational plausibility of this potential gain in communicative efficiency we present a theoretical analysis of other-initiated repair and pragmatic reasoning. following @xcite , we define efficient communication as communication in which participants reach mutual understanding while requiring minimal effort in terms of resource costs (deconstructed here as the sum of computational and interactional cost). we compare a novel agent-based model of otherinitiated repair with one of pragmatic reasoning @xcite for both their communicative success and use of computational and interactional resources. simulations are used to evaluate the models' success and interactional resource costs while a computational complexity analysis is used to determine the computational resource demands @xcite . the results show that, on roughly equal terms of communicative success, agents with a simple repair mechanism can reduce their computational burden compared to pragmatic agents, at the cost of longer interactions. while this shows that an efficiency-increasing trade-off is in principle possible, the question remains whether the computational advantage scales to more complex forms of other-initiated repair. the work we present here makes two contributions: 1) a proof of concept that a simple form of repair can help communicators outsource computational demands in interaction, and 2) a framework for the careful theoretical anal-ysis of the interplay of cognitive and interactional resources in human communication. as mentioned above, another mechanism that human communicators use to reach mutual understanding is repair @xcite . cross-linguistic work on informal face-to-face conversation has shown that repair is frequent (on average once every 1.4 minutes) and that it is highly similar in form and function across unrelated languages @xcite . attested repair initiations fall into three basic types, which differ in the grasp they display of the trouble source: (i) open request (e.g. 'huh?'), (ii) restricted request (e.g. 'who?') and (iii) restricted offer (e.g. 'at the market?'). these types are used according to similar principles across languages, with participants requesting clarification when necessary and reusing material when possible, resulting in repair sequences that appear to minimise the joint effort of speaker and listener @xcite . interactive repair is a universal and frequently used mechanism for resolving trouble in communication. here we hypothesise that it provides an affordance that inference based on context or pragmatic reasoning does not: it allows at least part of the computational burden of making inferences to be offloaded onto interaction, in effect distributing the process of reaching mutual understanding over multiple interactional turns @xcite . this can be seen as a form of cognitive offloading @xcite , with turns at talk constituting material symbols that can augment cognitive processes @xcite . in this paper we combine agent-based simulations with a computational complexity analysis to investigate the relative resource demands of pragmatic reasoning and interactive repair. we aim to find out whether other-initiated repair can increase communicative efficiency by relieving communicators of the computational demands of pragmatic reasoning, without that causing a decrease in communicative success. ## results figure 2a shows the mean communicative success for the different agent types and lexicon sizes. the frugally pragmatic listeners were always sufficiently certain about the intended referent of the speaker when using a lexicon of size 6x4, resulting in the agents staying with their first order inference for that lexicon size. for the lexicon sizes of 15x10 and 30x20, the frugally pragmatic listeners were always too uncertain about the speaker's intended referent, and therefore always went up to order @xmath0. 5 as figure 2a shows, the pragmatic agents have an advantage in terms of communicative success for the smallest lexicon size (6x4), while for bigger lexicon sizes (15x10 and 30x20) the interactional agents have an advantage. this can be accounted for by the fact that the interactional agents do not use oir for a lexicon with only 4 referents and an ambiguity level of 0.5 (see figure 2b ), as they are already certain enough 6 , and therefore choose ran5 this model behaviour depends on the entropy threshold (lower values mean agents tolerate less uncertainty), ambiguity level (more ambiguous lexicons lead to more uncertainty), and lexicon size (larger lexicons result in more dispersed probability distributions, which causes higher uncertainty). see appendix a for results with different parameter settings. 6 recall that the entropy threshold of 1.0 bits corresponds approximately to an equal distribution of probability mass over two referents. domly between two referents straight away (resulting in ∼50% communicative success). for bigger lexicons, however, they do use oir, which explains the increased communicative success: through multiple turns they can reduce referential uncertainty. interactional agents perform approximately equally well with the bigger lexicons of 15x10 and 30x20, while the pragmatic agents show a steady decline in communicative success for bigger lexicon sizes. this decline can be explained by bigger lexicons resulting in more dispersed probability distributions, which causes less certainty for both speakers and listeners when choosing their productions and interpretations. this is more of a problem for pragmatic agents as they cannot do anything other than go one level up in pragmatic reasoning, while interactional agents can take as many turns as needed to reduce referential uncertainty (for as far as their lexicon allows). for pragmatic agents, we see no difference in communicative success between the frugally pragmatic and fully pragmatic strategies. this is as expected since they have access to the same pragmatic reasoning mechanisms and differ only in the successive deployment of orders of reasoning. figure 2b shows the distribution of the number of turns for the interactional agents. here, a clear effect of lexicon size is visible: the bigger the lexicon, the more turns are used. this is unsurprising given that larger lexicons (given a constant ambiguity level) contain more referent associations per signal. therefore, a larger lexicon causes more uncertainty, which results in more turns. (note that we allowed agents to take more turns for bigger lexicons: we set a cap at 2 × |s| -1 turns.) for the smallest lexicon size of 6x4, only one turn (i.e. one speaker production) is needed for the listener to be certain enough to end the interaction, meaning that listeners do not make use of oir for this lexicon size. most interactional sequences take less than 10 turns in total regardless of lexicon size. this means that interactional listeners need on average less than 5 repair attempts to reach a sufficiently certain interpretation. figure 2c shows the computation cost (as means of the computational complexity) by agent type and lexicon size. for the interactional agents, the average number of turns per lexicon size (6x4: 1.0, 15x10: 3.0, and 30x20: 4.7 turns) is entered into the computation cost, since the worst case is defined by an artificial limit on interaction length. as mentioned above, the frugally pragmatic agents always went up to order @xmath1, resulting in almost the same computation cost as for the fully pragmatic agents (see also there is a substantial difference in computation cost between the interactional and pragmatic agent types. especially for larger lexicons the computation cost is considerably lower for interactional than for pragmatic agents. compared to this difference, the degree to which computation cost is reduced for frugally pragmatic compared to fully pragmatic agents is a lot smaller. the effect of lexicon size is smaller for the interactional compared to the pragmatic agents, as the computation cost increases linearly with lexicon size for interactional agents, while it increases quadratically with lexicon size for pragmatic agents (see ## discussion can communicators reduce their computational burden through interaction? we showed using a theoretical analysis that the use of other-initiated repair can be more efficient than pragmatic reasoning in communication, by reducing the computational demands of pragmatic reasoning through interaction. the chief computational advantage of repair in our model derives from the fact that it trades recursive pragmatic inferences (which scale quadratically with lexicon size) for computationally simpler conjunctions (which scale linearly). this advantage seems to scale to bigger lexicon sizes as well, with the communicative success of the interactional agents not being affected by lexicon size, whereas pragmatic agents' communicative success decreases. this supports the hypothesis that communicating agents can leverage interactive repair to reduce their computational burden, essentially outsourcing individual computation to interaction. a number of design choices may affect the generalisability of these results. first, we have modelled only a simple form of interactive repair, albeit one corresponding to a widely used repair format (the open request). other forms of repair may have different computational complexity profiles. for instance, restricted offers hold up a candidate understanding for confirmation, and their formulation likely requires some degree of pragmatic reasoning, adding to the computational complexity @xcite . also, dealing with some forms of repair may involve belief revision @xcite , which requires context-sensitive abductive inferences known to be computationally intractable @xcite @xcite . in sum, other-initiated repair is not a monolithic phenomenon, and the analytical tools we supply here can be used to systematically investigate the computational tractability of a range of possible interactional strategies (see e.g. @xcite . another limitation is that the conditions under which the agents communicate are unrealistic in that all agent pairs share the exact same lexicon. any potential misunderstanding thus stems solely from ambiguity, and not from one agent associating a given signal with a slightly different set of referents than their interlocutor. relaxing this assumption is likely to cause problems for the simple repair strategy presented here, because it is based on conjunction. if interactional agents would base their (literal) productions and interpretations on conjunctions of more asymmetrical lexicons, divergences between intended referent and interpretation would soon arise, in which case we predict a decrease in communicative success, and therefore in efficiency. pragmatic agents, on the other hand, have been shown to be able to leverage a moderate level of ambiguity in their lexicons to overcome asymmetry @xcite . we now consider two possible extensions to the current modelling work. note, however, that these both come with additional computational demands and require careful theoretical re-analysis to investigate where efficiency trade-offs may play a role. first, a hybrid model of pragmatic inference and other-initiated repair might combine the best of both worlds. the question then is if agents can achieve communicative success while keeping resource demands low by having their choice of strategy depend on an assessment of the situation. for example, in a speaker role, such a hybrid agent could 'level up' to a higher order of pragmatic reasoning in response to a repair initiator. such hybrid agents will of course need a meta-cognitive capacity to decide which strategy to use (for instance by reasoning about the level of asymmetry between themselves and their interlocutor). this meta-level reasoning would bring additional computational resource demands that would affect the agents' efficiency. while a hybrid strategy may be able to preserve some of the efficiency trade-offs we have documented here, it is an open question whether they would not be dwarfed by the added computational cost of meta-cognition (see e.g. @xcite . second, agents may revise their beliefs about the way their interlocutors use signals on the basis of conversation history, in order to overcome asymmetry @xcite . this form of updating might be able to explain why people are successful communicators while spending minimal interactional resources, but it comes at a computational cost too. consider that agents would have to entertain the possibility that their interlocutor has any in principally possible lexicon, and from those infer the ones that are most likely given their conversation history. there exist, however, exponentially many possible lexicons (viz. 2 n for a lexicon of binary mappings, where n is the lexicon size, @xcite 7 . which of these (or other) models best explains the relation between interactive repair and pragmatic reasoning is an empirical question. here we have shown that formal models informed by research on human interaction @xcite ) can bring us closer to an understanding of the cognitive and communicative capacities of interacting people. the question of communicative efficiency is inherently one of computational plausibility. this question is best addressed through careful theoretical analysis as we have shown here. further modelling can be used to refine our computational understanding of the phenomenon prior to empirical testing (cf. van rooij and baggio, 2020). ## conclusion using theoretical analysis, we showed that a simple form of other-initiated repair can ease the computational burden of pragmatic reasoning and thereby contribute to communicative efficiency. our models make several simplifying assumptions, so scaling them to other interactional strategies will increase computational demands and perhaps alter the division of labour. besides offering a proof of concept of how repair can ease the computational demands of communication, our methods pave the way for principled theory-driven analyses of how people balance cognitive and interactional resources in human interaction.