wenmin-wu/llm-exhaustive-permutation-early-stopping

Exhaustive Permutation with Early Stopping

Overview

For short sequences (up to 10-12 elements where n! is tractable), enumerate all permutations, score them in batches via a fast LLM scorer, and track the global best. Early-stop when the score drops below a known threshold (e.g., from leaderboard or theoretical bound). Batched evaluation makes this surprisingly fast — 10! = 3.6M permutations at batch_size=256 takes ~14K forward passes.

Quick Start

import itertools
import math
import numpy as np

def exhaustive_search(words, scorer, batch_size=256, threshold=None):
    best_score = float('inf')
    best_text = None
    total = math.factorial(len(words))
    batch = []
    for i, perm in enumerate(itertools.permutations(words)):
        batch.append(' '.join(perm))
        if len(batch) == batch_size or i == total - 1:
            scores = scorer.score(batch, batch_size=batch_size)
            min_idx = np.argmin(scores)
            if scores[min_idx] < best_score:
                best_score = scores[min_idx]
                best_text = batch[min_idx]
            batch = []
            if threshold and best_score < threshold:
                break
    return best_text, best_score

result, score = exhaustive_search(
    text.split(), scorer, batch_size=256, threshold=475)

Workflow

1. Generate all n! permutations via itertools.permutations
2. Accumulate into batches of size B
3. Score each batch with batched LLM perplexity
4. Track running best score and corresponding text
5. Early-stop if score falls below the target threshold

Key Decisions

• Feasibility: practical up to n=10 (3.6M); n=12 (479M) is borderline; n>12 needs heuristics
• Batch size: 128-512 balances GPU utilization and memory
• Threshold: set from leaderboard probing or known optimal — avoids wasting compute
• Enumeration order: reversed order sometimes hits good solutions faster for specific LLMs

References

• Brute Force First Sample - Perplexity 470