5 papers
Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods
Avrim Blum, Daniel Hsu, Cyrus Rashtchian +1
Test-time augmentation, such as Retrieval-Augmented Generation (RAG) or tool use, critically depends on an interplay between a model's parametric knowledge and externally retrieved…
Proofs as Explanations: Short Certificates for Reliable Predictions
Avrim Blum, Steve Hanneke, Chirag Pabbaraju +1
We consider a model for explainable AI in which an explanation for a prediction consists of a subset of the training data (if it exists) such that all classifiers $h'…
Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking
Dhruv Rohatgi, Abhishek Shetty, Donya Saless +4
Test-time algorithms that combine the generative power of language models with process verifiers that assess the quality of partial generations offer a promising lever for elicitin…
PAC Learning with Improvements
Idan Attias, Avrim Blum, Keziah Naggita +3
One of the most basic lower bounds in machine learning is that in nearly any nontrivial setting, it takes samples to learn to error (and more, if th…
Regularized Robustly Reliable Learners and Instance Targeted Attacks
Avrim Blum, Donya Saless
Instance-targeted data poisoning attacks, where an adversary corrupts a training set to induce errors on specific test points, have raised significant concerns. Balcan et al (2022)…