wenmin-wu/llm-binary-search-entity-narrowing

Binary Search Entity Narrowing

Overview

When an LLM agent must identify an unknown entity from a large candidate set using yes/no questions, a hierarchical binary search strategy is far more efficient than open-ended questioning. Ask about broad categories first (person/place/thing), then sub-categories (continent/country), then discriminating features (first letter). Each answer halves the remaining candidate space.

Quick Start

CATEGORIES = ["place", "person", "thing"]
CONTINENTS = ["Europe", "Asia", "Africa", "North America", "South America", "Oceania"]

def ask_question(obs, candidates, cat_guess, con_guess, let_guess,
                 category_yes, continent_yes):
    if cat_guess < len(CATEGORIES) and not category_yes:
        q = f"Is the keyword the name of a {CATEGORIES[cat_guess]}?"
        return q, cat_guess + 1, con_guess, let_guess

    if con_guess < len(CONTINENTS) and not continent_yes:
        cat = category_yes[0] if category_yes else "thing"
        q = f"Is the {cat} located in {CONTINENTS[con_guess]}?"
        return q, cat_guess, con_guess + 1, let_guess

    filtered = apply_filters(candidates, category_yes, continent_yes)
    letters = filtered['first_letter'].value_counts().index.tolist()
    if let_guess < len(letters):
        q = f"Does the keyword begin with the letter {letters[let_guess]}?"
        return q, cat_guess, con_guess, let_guess + 1

    return filtered.sample(1).iloc[0]['keyword'], cat_guess, con_guess, let_guess

Workflow

1. Prepare a candidate keyword list with metadata (category, continent, first letter)
2. Ask category questions first (3 questions max → identifies type)
3. Ask continent/region questions (6 questions max → identifies location)
4. Ask first-letter questions to discriminate remaining candidates
5. When candidate set is small enough, guess directly

Key Decisions

• Question order: broad→narrow maximizes information gain per question
• Category granularity: 3-5 top-level categories; more = more questions wasted
• First letter: high entropy discriminator — 26 possible values
• When to guess: when ≤3 candidates remain, guess the most common one
• Budget: 20 questions total — typically 3 category + 6 region + 5 letter + 6 guess attempts

References

• Starter Code for Llama 8B LLM - [LB 0.750+]