My main concern is the scope of the countable-class convergence and optimality claims. Theorem 6.1 gives an O(logi) mistake bound, but no stream-independent last-mistake bound is proved for that instantiation. A finite mistake bound guarantees generation in the limit on each stream; it does not by itself establish non-uniform generation with a last-mistake bound depending only on the language. The introduction’s statement that the algorithm achieves logarithmic mistakes “by allowing for a slower convergence time” therefore suggests a guarantee that is not established. Conversely, Theorem 6.3 rules out the rate CGmaxi,m(Li), but does not resolve whether logarithmic mistakes are compatible with some slower non-uniform convergence guarantee. In fact, on the class constructed for Theorem 6.3 (Appendix D.1), a generator that outputs from the intersection of all consistent languages when possible, and otherwise from the intersection of all consistent languages except the lowest-indexed one, makes at most one mistake on each Li, and only at time m(Li+1)+1; the trade-off thus hinges on requiring the Charikar–Pabbaraju rate. The paper should distinguish optimality of the mistake count from the joint mistake–convergence trade-off, and qualify the claim that minimizing mistakes “does require sacrificing” convergence.
The computational model also needs clarification. Algorithm 1 takes an argmax over the infinite set X∖x1:t−1. Exact maximization can require determining which intersections of the active languages still contain unseen elements, information that membership queries alone do not generally provide. The uniform and non-uniform generators the paper builds on (Algorithms 2 and 3) rely on similar nonemptiness checks, so this requirement is shared with prior work in this line. This access requirement should be distinguished from the membership-oracle model used by Kleinberg and Mullainathan (2024) and the computational barriers studied by Arenas et al. (2025). In particular, the growth function bounds the number of active languages, rather than the computational cost of each step. The statement that it allows the algorithm to “handle infinite streams with finite computational resources” should be qualified, and the assumed oracle should be stated explicitly.
For finite classes, the bound is worst-case optimal as a function of cardinality, but does not characterize the optimal mistake count for an individual class. For example, consider N languages sharing a finite set of size n and otherwise disjoint. The optimal mistake count is one, and Algorithm 1 achieves it, while the stated bound gives min⌊log2N⌋,n+1. The contribution heading “Optimal Bounds for Finite Classes” should make the scope of this optimality explicit. A per-class lower bound, or even a characterization of classes admitting zero or one mistake, would help clarify the complexity measure introduced by the paper.
The relationship to established proof techniques could also be positioned more precisely. Because the adversary’s next element is unseen when the generator acts, it provides a feasible comparison point, and Lemma A.1 follows the classical halving/weighted-majority potential argument (Littlestone, 1988; Littlestone and Warmuth, 1994). The dual guarantee of Theorem 5.1, which uses Algorithm 1 itself, rests on a one-line observation: whenever the consistent languages share an unseen element, every max-weight output lies in their intersection, since all consistent languages have positive weight (Appendix B.1); the Cdim+1 term then follows from the last-mistake bound. Moreover, Appendix A proves the realizable results directly without the LfD reduction. Its substantive role is in the noisy setting, where Lemma 7.1 follows from Theorem 5 of Joshi et al. The abstract should distinguish the conceptual contribution of the LfD formulation from the proof ingredients needed for the realizable bounds.
The hallucination motivation would benefit from a discussion of breadth. Algorithm 1 favors intersections of consistent languages and may generate with little breadth, while prior work establishes tensions between breadth and consistency (Kalavasis et al., 2025). The noisy extension also provides upper bounds without matching lower bounds. As Section 7.1 acknowledges, under infinite but vanishing noise the bounds need not imply finitely many mistakes, whereas Mehrotra et al. (2025) guarantee a finite number of mistakes in that regime.
Minor comments: the definition of f−1 in Theorem 4.1 could be simplified to f−1(i)=supt≥0:f(t)<i with f(0):=0. Algorithm 1 permits w0:N→R≥0, whereas Theorem 4.1 requires strictly positive weights; this distinction should be clarified. “Proceeding” should be “following” in Appendix B.2, and “e.g.” should be “i.e.” in Section 3, Theorem E.1, and the proof of Lemma E.2. Section 4 states that the reduction to LfD is given in Appendix E.3, but it appears in Appendix E.1 (Lemma E.2).
Overall, the paper introduces a natural metric and a useful distinction between mistake count and last-mistake time. My main reservations concern the scope of the convergence and optimality claims, the unspecified oracle model, and the limited per-class characterization of mistake complexity. Clearer positioning relative to classical online-learning arguments would also help assess the technical contribution. I currently lean toward rejection, but would raise my score if the authors clarify the convergence guarantees of the logarithmic-mistake algorithm, qualify the trade-off claims accordingly, and state the assumed oracle model.
Thanks for your positive review! With regard to your point about the proof of Theorem 6.4, we believe you are referring to Theorem 6.3. In that proof, m(Li+1)=m(Li)+22i, rather than m(Li)+ni. Consequently, m(Li+1)/maxi,m(Li)→∞, so the same fixed class works for every finite CG. Please let us know if you still have concerns about the proof.