Research map / Learning theory and algorithms / Prediction and decision losses
Optimal and Efficient Binary Questioning for Accelerated Annotation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Frames data annotation as a binary yes/no question-and-answer game, shows the optimal strategy is Huffman encoding, and proposes a practical lookahead-minimization method (IA, and ALIA with online active learning) that cuts annotation questions substantially on synthetic and real datasets.
Problem
Annotating binary classification datasets is costly; the question is whether an annotator can label N samples with fewer than N yes/no questions when a predictor is available, and how to do so efficiently.
Approach
Formulates annotation as an optimal prefix-free encoding problem (Huffman coding) and approximates the intractable optimum with set-based guess questions and lookahead minimization over a tree of knowledge states guided by a predictor's probabilities, with a "don't give up" heuristic and online learning from wrong guesses.
Key results
- On synthetic problems with N=10, the IA method is very close to the optimal Huffman encoding and near the entropy lower bound.
- With a fixed pretrained predictor, CIFAR10 question reduction is up to 20% and SVHN annotates all 6000 samples with fewer than 2500 questions.
- With an online predictor (ALIA), annotation cost is reduced by 70% on both MNIST and Fashion-MNIST.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use IA with a fixed pretrained predictor | Binary annotation on CIFAR10 · CIFAR10, first 6000 examples | annotation-question reduction: 20% | Helped |
| Use IA with a fixed pretrained predictor | Binary annotation on SVHN · SVHN, first 6000 examples | questions to annotate all samples: less than 2500 questions for 6000 samples | Helped |
| Train the predictor online and use it for accelerated annotation (ALIA) | Binary annotation on MNIST · MNIST, first 6000 examples | annotation-cost reduction: 70% | Helped |
| Train the predictor online and use it for accelerated annotation (ALIA) | Binary annotation on Fashion MNIST · Fashion MNIST, first 6000 examples | annotation-cost reduction: 70% | Helped |
Surprising findings
- Annotation with a predictor is theoretically reducible below N binary questions, with the optimal method given by Huffman decoding.
- For CIFAR10 with a weak predictor (accuracy 0.67), the reduction is only 20%, yet a strong predictor (SVHN, 0.93) lets all 6000 samples be annotated with fewer than 2500 questions.
Limitations
- Assumes errorless annotators and constant cost per answer; batch processing ability of annotators is required.
- Exact optimum (Huffman) is computationally intractable beyond about 20 samples.
- Benefit depends on predictor calibration; experiments are on relatively small datasets (first 6000 samples).
Experimental setup
Datasets: CIFAR10 SVHN MNIST Fashion-MNIST synthetic two-dimensional Gaussian and Guyon et al. 2006 datasets
Benchmarks: CIFAR10 SVHN MNIST Fashion-MNIST synthetic 2D problems
Metrics: number of binary questions needed to annotate samples annotation efficiency (% reduction) comparison to entropy lower bound
Baselines: Huffman encoding traditional one-question-per-sample annotation entropy-based active learning
Builds on: Huffman coding lookahead minimization (Bertsekas) Wordle resolution (Bhambri et al. 2022) one-bit supervision (Hu et al. 2020) entropy-based active learning
Closest papers by meaning
- Instance-wise Supervision-level Optimization in Active Learning (CVPR 2025 · similarity 0.84)
- The ALCHEmist: Automated Labeling 500x CHEaper than LLM Data Annotators (NeurIPS 2024 · similarity 0.83)
- Info-Coevolution: An Efficient Framework for Data Model Coevolution (ICML 2025 · similarity 0.83)
- Limits to scalable evaluation at the frontier: LLM as judge won’t beat twice the data (ICLR 2025 · similarity 0.82)
- LESS: Selecting Influential Data for Targeted Instruction Tuning (ICML 2024 · similarity 0.82)
- Collaborative Refining for Learning from Inaccurate Labels (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.