Thank you for this insightful and detailed review. We are glad you have found our theoretical contributions novel and valuable. The papers that you have mentioned, especially regarding compositionality and input representation, are indeed relevant to our core contributions, and we will add references to them in our next revision.

We will now address your comments individually:

SS2: We agree that comparing our definitions to existing ideas is important. An interesting connection between our definitions and Topographic Similarity (topsim) is that while topsim considers the relationship between every pair of inputs, our definitions only consider pairs that correspond to similar messages. The latter follows an intuitive asymmetry: inputs with similar messages are expected to be similar, but inputs with dissimilar messages do not have to be different. Further discussion will be added in the next revision. On the empirical front, new experiments are described in the response for comment WS2, including correlation with topsim, posdis, bosdis, and speaker-posdis.

WO1, WQ1, WQ2: The missing citations will be added in the next revision. Thank you for the references.

WQ3: Section 2.3 will be expanded in the next revision.

WQ4: This explicit equation for explained variance will be added to the relevant paragraph: $\text{Var}_{m \sim S(X)}\mathbb{E}[X | S(X)=m]$

WC1: This is a good observation, which aligns with a central theme in our paper: distinguishing "solves the task" from "has (consistent) meaning." In the next revision, we will clarify that "meaningful" refers to human-recognizable properties.

WC2: We apologize for the mischaracterization. Our framework is mainly applicable to setups with a small-capacity messaging channel, where inputs necessarily get mapped to the same message. Nonetheless, research investigating larger message spaces is an important part of EC literature, including alternative types of messages such as quantization or explicit codebooks. We will reformulate the relevant paragraph accordingly.

WC3: The term 'unrestricted' means that the agent can assume any function from its domain to its range. This assumption allows closed-form, interpretable solutions for synchronized receivers. However, it is unrealistic in the context of natural language, as physical and mental limitations play an important role in shaping human communication. Removing this assumption motivated the second part of our paper (dealing with spatial meaningfulness), where agents are not assumed to be unrestricted.

WC4(1): We apologize for any confusion and definitely did not intend for the proofs to be hard to read. The referred-to third line is the law of total expectation, where the events are the assignment to message m. We have made efforts to ensure all proofs are written clearly and rigorously, so their correctness is easy to assert. We will add additional explanations for derivations in our revision.

WC4(2): This assumption simply prevents the degenerate case where every available communication protocol is semantically inconsistent, which would render every optimal solution inconsistent regardless of the objective function.

WC5: The KKT conditions characterize optimal solutions to convex problems. We will add the appropriate citation [2].

WC6: Thank you for the suggestion, we will add equation numbering to our lemmas and to key equations throughout the proofs section for easier reference.

WS1: The missing citations will be added in the next revision. Thank you for the references.

WS2: We fully agree with your comment. The empirical analysis will better support our findings if we experiment with more sophisticated data. With this in mind, we have conducted additional experiments on a special version of the Shapes dataset [1] where each input is an image of an object with several sampled attributes (shape, color, position, rotation, and size). The multiplicity of attributes allowed us to calculate compositionality/disentanglement measures from the literature, including your suggestions. The results are appended to the general author rebuttal (and will be added to the paper in the next revision).

The results show a significant gap in semantic consistency (lower message variance is preferable), on par with the previous evaluation on MNIST. Additionally, topographic similarity strongly favors the reconstruction setting (0.37, versus 0.08 for discrimination), confirming a positive relationship between semantic consistency (as measured by message variance) and compositionality (as measured by topsim). We also report correlations between every pair of measures, taken over 10 runs (5 for each task). These correlations should be considered with caution as they are affected by the inclusion of both tasks for calculation. We may report separate tables for each game type to avoid this issue.

WS3: We prefer to keep the theoretical and empirical parts separate to avoid splitting attention. However, it is crucial to present the metrics before the results, so we restructured the empirical section to mention the metrics before introducing any results. As for the codebase, it will be open-sourced with the publication, and you can access it now via the zip attached to the original submission.

WS4: See our responses to WS2 and SS2.

WS5: Systematic generalization is not included in our theoretical framework. Given our recent results, we might expect semantically consistent protocols to generalize better to unseen attribute values, as the relationship between topsim and systematic generalization has sometimes been shown to be positive.

We greatly appreciate your space-saving tips. We will try to implement them in the next revision as well.

[1] Kuhnle, Alexander and Copestake, Ann. "ShapeWorld - A new test methodology for multimodal language understanding". arXiv preprint arXiv:1704.04517

[2] Bertsekas, Dimitri P. "Nonlinear programming". Journal of the Operational Research Society.

Thank you for your response and for adjusting the score. We appreciate your feedback.

Discrimination accuracy in the reconstruction setting

We define the referential prediction of the reconstruction setup as the candidate that minimizes the loss when paired with the target's reconstruction. Namely, we pass the given message to the receiver agent which outputs a reconstruction of the target, and then pick the candidate with the lowest Euclidean distance to that output.

Train/test split

The results are measured over the test split only. The train/test split is done uniformly, without splitting values of specific attributes.

Systematic generalization

We wish to emphasize that the primary contributions of this paper are theoretical, and that the empirical analysis is intended to support those findings. The relationship between our definitions/measures and systematic generalization is interesting and worth exploring, but we prefer to keep the experiments within the scope of the existing theoretical framework. We do recognize, however, that future works could offer significant value to the field by extending both the theory and experiments to explore systematicity.

If you would like any further clarifications or have additional concerns, please let us know.

Thank you for this insightful review. We are glad you have found the novel theoretical tools useful. Following your feedback and others, we have prepared some major modifications to be added in the next revision.

You have mentioned as a weakness the empirical results with regard to spatial meaningfulness (the "cluster variance" metric"). We would like to emphasize that the key contributions of our work are theoretical, and that the empirical analysis is intended to be a complementary proof-of-concept supporting our findings. With that said, we admit that our proposed metric for spatial meaningfulness does not yield interesting results, unlike its counterpart (message variance). We hypothesize that the size of each cluster (16 messages) is too large, and perhaps a different partitioning method will provide more insight. This hypothesis will be added in the next revision.

We now like to address your questions.

1. The agents cannot communicate raw information due to the limited capacity of the communication channel, i.e., the "discrete bottleneck". In most EC setups, the message space is constructed as sequences of tokens and is therefore often small in comparison to the input space. For example, in our MNIST experiments, there are 10K possible messages, which is smaller than the size of the dataset.
2. There are several benefits of simple two-agent communication games. To name a few: optimization is easier, language analysis is more straightforward (there is only one speaker), and each message functions as a latent representation of the input, so concepts from representation learning literature can be applied to study the setup. With that said, EC with many agents is also studied frequently, but outside the scope of this paper.
3. The experiment that revealed the agents' ability to perform well on random noise [1] trained discrimination agents on natural images (imagenet) and then performed inference where both the target and the (single) distractor are just sampled noise. Surprisingly, the agent were able to play the game (i.e., the receiver was able to detect the target) with high accuracy. This result indicates that the features perceived by the agents are not high-level classes or objects ("human-recognizable properties"), illustrating the potential for counterintuitive communication protocols to emerge.
4. The goal of inducing characteristics of natural language in communication protocols is what often sets apart EC from related fields such as Multi-Agent Reinforcement Learning (MARL), which focus on long-term expected reward. Creating learning environments that induce protocols similar to natural language is desirable in several aspects: it may improve our understanding of the underlying deep learning architectures, advance the goal of human-AI interaction, and even provide insights into language evolution.
5. It doesn't have to, because M is embedded into the functions S and R.
6. A situation where both agents are synchronized is a situation where neither agent can 'do any better' given the fixed state of the other (Nash equilibrium). This pair of agents does not necessarily minimize the expected loss. This kind of suboptimal equilibrium can happen with an alternating optimization method (e.g., local minimum at the end of kmeans).
7. Yes. Investigating the effect of noise in the communication channel is an interesting idea for future work.
8. Quantization is a viable discretization method for EC research. However, it often defines very large message spaces, which means that most used messages likely represent a single input. For that reason, it does not fit the required setting for our analysis.
9. Sorry for the confusion. We avoided additional arrows to maintain an elegant figure. To clarify this, we added an explanation in text below the figure.
10. The distractors are given to the receiver by the game, as independent input. The only thing going through the communication channel is a single message, which the sender generates based on seeing only the target (the "correct" candidate).
11. Right, this is an important clarification. The input itself is only the location of each object (a vector), not the attributes themselves. We used shapes and colors to illustrate how distance between inputs can be indicative of their semantic similarity. This clarification has been added to the caption for the next revision.
12. Thank you for the observation, we fixed it.
13. It does not. By definition, a synchronized receiver minimizes the loss for a specific sender. As a result, when we plug in the closed-form synchronized receiver into the loss function, we get the best achievable loss value for the sender (as a function of the sender agent).
14. We have added a clarification note, the word "Binomial" refers to the binomial distribution, over which the expectation is taken.
15. We are not sure how one should go about verifying this assumption in practice. While the constant k can be empirically estimated, one would have to bound (from above) the norm of the receiver's gradient to ensure that this definition is satisfied.
16. The motivation behind the non-degeneracy definition is to prevent a situation where the fixed receiver in theorem 6.1 is constant, which means that the sender agent doesn't affect the game performance, and therefore isn't incentivized to use a spatially meaningful communication protocol. Our proof for theorem 6.1 requires the receiver to be strictly better than constant and this bound is performed twice, so any constant smaller than ½ can replace the ¼ in definition 6.
17. Indeed a typo. Thank you for the observation, we fixed it.
18. We use slightly different settings and notations, so we chose to include the proof for completeness.
19. Thank you for the observation, we fixed it.
20. Of course. Done.

[1] Bouchacourt, Diane and Baroni, Marco. "How agents see things: On visual representations in an emergent language game". arXiv preprint arXiv:1808.10696

Thank you for this insightful review. We are glad you have found the theoretical part innovative and well structured. Following your feedback and others, we have prepared some major modifications to be added in the next revision. We would now like to address your comments one by one.

Comment 1: The paper could benefit from additional experiments with more diverse datasets or more complex tasks to further validate the theoretical findings.

Indeed. While our key contributions are theoretical, we agree more experiments can help validate our findings. While the simplicity of MNIST has its benefits, we have recently conducted additional experiments on a special version of the Shapes dataset [1], where each input is an image of an object with several sampled attributes (shape, color, position, rotation, and size). The multiplicity of attributes allowed us to calculate compositionality/disentanglement measures from the literature, and the results are appended to the general author rebuttal (and will be added to the paper in the next revision).

The results show a significant gap in semantic consistency (lower message variance is preferable), on par with the previous evaluation on MNIST. Additionally, topographic similarity strongly favors the reconstruction setting (0.37, versus 0.08 for discrimination), confirming a positive relationship between semantic consistency (as measured by message variance) and compositionality (as measured by topsim). We also report correlations between every pair of measures, taken over 10 runs (5 for each task). These correlations should be considered with caution as they are affected by the inclusion of both tasks for calculation. We may report separate tables for each game type to avoid this issue.

Comment 2: The empirical analysis of spatial meaningfulness using message clusters may not fully explore the nuances of this concept. Further investigation into different methods of evaluating spatial meaningfulness could provide more actionable insights.

Investigating other estimation methods of spatial meaningfulness would indeed be an interesting addition. We wish to emphasize that the major contributions of this paper are theoretical, and the empirical analysis is intended to be a complementary proof-of-concept supporting our findings. With that said, we admit that our proposed metric (cluster variance) for spatial meaningfulness does not yield interesting results, unlike its counterpart (message variance). We hypothesize that the size of each cluster (16 messages) is too large, and perhaps a different partitioning method will provide more insight. This hypothesis will be added in the next revision.

Comment 3: The paper could be improved by discussing the limitations of using Euclidean distance and the potential impact of using alternative metrics.

We do mention this limitation on page 6 (footnote) and in the limitations section, but perhaps not elaborately enough. In some types of data, like images, Euclidean distance on raw pixels might not be indicative of desirable properties. Note that all our theoretical results hold anyway, and that some of our results do not depend on distance (e.g., Corollary 5.4). Furthermore, a solution that we implement in our experiments is the use of embeddings generated by a pretrained continuous model. Within that embedding space, the meaningfulness of Euclidean distance becomes an easier assumption. This discussion will also be added to the next revision.

Comment 4: Including a discussion on the scalability of the approach and its computational requirements would provide a more comprehensive understanding of its practical applicability

Appendix D is written precisely to supply technical information regarding the experiments. The first stage of training is a continuous autoencoder training procedure, which is very quick (especially on MNIST). It takes approximately 10 minutes using a standard GPU. This detail will be included in the next revision.

[1] Kuhnle, Alexander and Copestake, Ann. "ShapeWorld - A new test methodology for multimodal language understanding". arXiv preprint arXiv:1704.04517 (2017)

Thank you for this insightful review. We are glad you have found the paper to be rigorous and well written. Following your feedback and others, we have prepared some major modifications to be added in the next revision.

Question 1

The explained variance relates to the average proximity of inputs with identical messages. The absence of explained variance (which we refer to as semantic inconsistency) means that inputs mapped to the same message are not closer to each other (in expectation) than two randomly selected inputs. This would indicate an inherently unintuitive communication protocol.

Question 2

Since our main contributions are theoretical, we used MNIST to generate proof-of-concept results. That said, given your question, we have conducted additional experiments on a more sophisticated dataset—a special version of the Shapes dataset [1] where each input is an image of an object with several sampled attributes (shape, color, position, rotation, and size). The results are appended to the general author rebuttal (and will be added to the paper in the next revision).

The results show a significant gap in semantic consistency (lower message variance is preferable), on par with the previous evaluation on MNIST. Additionally, topographic similarity strongly favors the reconstruction setting (0.37, versus 0.08 for discrimination), confirming a positive relationship between semantic consistency (as measured by message variance) and compositionality (as measured by topsim). We also report correlations between every pair of measures.

Question 3

Interesting question. In general the field of EC as we know it did not catch up with the advance of LLMs. One might try to use LLMs for EC interpretation and decipherment, but this seems quite challenging. This idea is empirical in nature and not entirely in the spirit of our paper. In any case, we will add discussion of these possible connections in a revision.

Question 4

Our analysis only considers two-agent setups. The generalization of Lewis' games to multiple agents is not straightforward but could provide interesting insights.

Question 5

The sender-receiver EC setups are indeed built to resemble encoding and decoding, which is why we can consider messages as latent representations. What distinguishes EC setups from general representation learning is the discreteness of the communication channel, which is key to our analysis. The discreteness induces the many-to-one nature of the communication protocol, which is why the perspective of equivalence classes makes sense in this context. As for the significance of our (theoretical) results: a greatly desired goal in EC literature is the characterization of communication properties that separate human language from EC protocols. We discover, precisely define, and rigorously support two such properties, which can be used in future research. For example, our analysis led us to question the generative vs. discriminative division of objectives, in favor of a distance-based vs. probability-based distinction. This move is reflected in our choice to rebrand the probabilistic reconstruction variant (which is generative) as "global discrimination." These results are novel and non-trivial.

Question 6

Thank you for this insightful question. With regard to the empirical results, we admit that our proposed metric (cluster variance) for spatial meaningfulness does not yield interesting results. We hypothesize that the size of each cluster (16 messages) is too large, and perhaps a different partitioning method will provide more insight. This hypothesis will be added in the next revision. On the theoretical front, for the next revision we have improved our results by modifying the simplicity condition (ln 271) so that theorem 6.1 applies to any desired threshold (previous version applies to the minimal threshold $\varepsilon_M$). The interest behind the spatial meaningfulness definition is twofold: a) it allows an analysis that takes into account distances between messages, and b) the analysis does not assume an unrestricted hypothesis class, which is a major shortcoming of the theorems in section 5.

Question 7

There is an interesting relationship between our definitions and the most common compositionality measure, Topographic Similarity (topsim): topsim evaluates the correlation between distances in the input space and the corresponding distances in the message space. Notably, topsim considers the relationship between every pair of inputs, whereas our definitions only consider pairs that correspond to similar messages. The latter follows an intuitive asymmetry: inputs with similar messages are expected to be similar, but inputs with dissimilar messages do not have to be different. This paragraph will be added to the paper in the next revision. In addition, we performed additional experiments comparing message variance to existing compositionality measures from the literature. See the response to question 2.

The implication <...> seems to fall out from classical results on classification vs generative modeling.

An illustration of why this is not the case can be seen in the "global discrimination" game, which is generative but equivalent to a special case of the discrimination game (on the classification side).

Spatial meaningfulness appears to be a fancy name for clustering of messages in the latent space.

If anything, spatial meaningfulness describes the clustering of clusters! Recall that the message space M is given and constant; the sender only determines the mapping to messages. Each message corresponds to a set of inputs, and spatial meaningfulness requires those sets of inputs to be close (in the input space) when their message vectors are close.

[1] Kuhnle, Alexander and Copestake, Ann. "ShapeWorld - A new test methodology for multimodal language understanding". arXiv preprint arXiv:1704.04517 (2017)