Abstract

Multi-label classification problems with thousands of classes are hard to solve with in-context learning alone, as language models (LMs) might lack prior knowledge about the precise classes or how to assign them, and it is generally infeasible to demonstrate every class in a prompt. We propose a general program, 𝙸𝚗𝚏𝚎𝚛--𝚁𝚎𝚝𝚛𝚒𝚎𝚟𝚎--𝚁𝚊𝚗𝚔, that defines multi-step interactions between LMs and retrievers to efficiently tackle such problems. We implement this program using the 𝙳𝚂𝙿𝚢 programming model, which specifies in-context systems in a declarative manner, and use 𝙳𝚂𝙿𝚢 optimizers to tune it towards specific datasets by bootstrapping only tens of few-shot examples. Our primary extreme classification program, optimized separately for each task, attains state-of-the-art results across three benchmarks (HOUSE, TECH, TECHWOLF). We apply the same program to a benchmark with vastly different characteristics and attain competitive performance as well (BioDEX). Unlike prior work, our proposed solution requires no finetuning, is easily applicable to new tasks, alleviates prompt engineering, and requires only tens of labeled examples.