6 papers
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…
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'…
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 the…
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)…
Scalable Hypergraph Embedding System
Sepideh Maleki, Donya Saless, Dennis P. Wall +1
Many problems such as node classification and link prediction in network data can be solved using graph embeddings. However, it is difficult to use graphs to capture non-binary rel…