Language Generation with Feedback: Queries and Mistakes

Steve Hanneke, Amin Karbasi, Anay Mehrotra, Grigoris Velegkas
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:40327-40352, 2026.

Abstract

We investigate language generation in the limit (Kleinberg & Mullainathan, 2024; Li et al., 2025) in variants where the generator receives some feedback based on its “actions.” We study two such variants. In the first, which is inspired by Littlestone’s model of online learning, the generator observes whether it made a mistake at each iteration. In the second, introduced by Charikar & Pabbaraju (2025a), the generator can query whether a string belongs to the target language. Our main result is a characterization of collections that are generable with mistake feedback. Using similar techniques, we also characterize when generation is possible in the query model with set-based generators; set-based generators have been studied in several works (Charikar & Pabbaraju, 2025a; Kalavasis et al., 2025; Kleinberg & Wei, 2025a; Li et al., 2025). Beyond the characterizations themselves, we derive several implications. First, our results imply new closure properties for generation with mistake and query feedback. Second, our results show that, under feedback, generation is robust to noise: it remains possible with arbitrary contamination in the adversary’s examples and with finite contamination in the feedback. Third, our techniques also yield new sufficient and necessary conditions for generation without feedback among other implications.

Cite this Paper


BibTeX
@InProceedings{pmlr-v306-hanneke26a, title = {Language Generation with Feedback: Queries and Mistakes}, author = {Hanneke, Steve and Karbasi, Amin and Mehrotra, Anay and Velegkas, Grigoris}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {40327--40352}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/hanneke26a/hanneke26a.pdf}, url = {https://proceedings.mlr.press/v306/hanneke26a.html}, abstract = {We investigate language generation in the limit (Kleinberg & Mullainathan, 2024; Li et al., 2025) in variants where the generator receives some feedback based on its “actions.” We study two such variants. In the first, which is inspired by Littlestone’s model of online learning, the generator observes whether it made a mistake at each iteration. In the second, introduced by Charikar & Pabbaraju (2025a), the generator can query whether a string belongs to the target language. Our main result is a characterization of collections that are generable with mistake feedback. Using similar techniques, we also characterize when generation is possible in the query model with set-based generators; set-based generators have been studied in several works (Charikar & Pabbaraju, 2025a; Kalavasis et al., 2025; Kleinberg & Wei, 2025a; Li et al., 2025). Beyond the characterizations themselves, we derive several implications. First, our results imply new closure properties for generation with mistake and query feedback. Second, our results show that, under feedback, generation is robust to noise: it remains possible with arbitrary contamination in the adversary’s examples and with finite contamination in the feedback. Third, our techniques also yield new sufficient and necessary conditions for generation without feedback among other implications.} }
Endnote
%0 Conference Paper %T Language Generation with Feedback: Queries and Mistakes %A Steve Hanneke %A Amin Karbasi %A Anay Mehrotra %A Grigoris Velegkas %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-hanneke26a %I PMLR %P 40327--40352 %U https://proceedings.mlr.press/v306/hanneke26a.html %V 306 %X We investigate language generation in the limit (Kleinberg & Mullainathan, 2024; Li et al., 2025) in variants where the generator receives some feedback based on its “actions.” We study two such variants. In the first, which is inspired by Littlestone’s model of online learning, the generator observes whether it made a mistake at each iteration. In the second, introduced by Charikar & Pabbaraju (2025a), the generator can query whether a string belongs to the target language. Our main result is a characterization of collections that are generable with mistake feedback. Using similar techniques, we also characterize when generation is possible in the query model with set-based generators; set-based generators have been studied in several works (Charikar & Pabbaraju, 2025a; Kalavasis et al., 2025; Kleinberg & Wei, 2025a; Li et al., 2025). Beyond the characterizations themselves, we derive several implications. First, our results imply new closure properties for generation with mistake and query feedback. Second, our results show that, under feedback, generation is robust to noise: it remains possible with arbitrary contamination in the adversary’s examples and with finite contamination in the feedback. Third, our techniques also yield new sufficient and necessary conditions for generation without feedback among other implications.
APA
Hanneke, S., Karbasi, A., Mehrotra, A. & Velegkas, G.. (2026). Language Generation with Feedback: Queries and Mistakes. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:40327-40352 Available from https://proceedings.mlr.press/v306/hanneke26a.html.

Related Material