Large-Scale LLM Classification: From Brute Force To Tree Pruning
· 26 min read · Views --

Large-Scale LLM Classification: From Brute Force To Tree Pruning

Author: Alex Xiang

Engineering

Large-Scale LLM Classification: From Brute Force To Tree Pruning

I recently needed to automatically label thousands of API providers and tens of thousands of tools. The category system was a three-level tree, roughly L1 -> L2 -> L3, with more than one hundred leaf categories.

The naive method would call an LLM for every entity and every category. That quickly becomes more than a million calls. The final implementation reduced call volume to roughly 1% of that.

This article extracts the optimization ideas into reusable patterns. They are not limited to classification. Any task that uses an LLM to make structured judgments over large datasets can benefit from similar techniques.

The Naive Scale

Assume:

  • 200 providers
  • 50 tools per provider on average
  • 120 leaf categories

The brute-force approach is:

200 providers × 120 categories = 24,000 calls
10,000 tools × 120 categories = 1,200,000 calls
Total ≈ 1,224,000 LLM calls

Even with a cheap model, a few hundred tokens per call quickly becomes hundreds of millions of tokens. Time is another problem: even with high concurrency, a million requests can take hours.

This is clearly the wrong shape.

Optimization 1: Hierarchical Pruning

A three-level category tree naturally supports pruning. Instead of asking the model to evaluate all 120 leaf categories, classify level by level:

  1. Evaluate only L1 categories.
  2. Expand the matching L1 branches and evaluate their L2 nodes.
  3. Expand the matching L2 branches and evaluate the relevant L3 leaves.

This is the same basic idea as search pruning. Alpha-beta pruning and branch-and-bound both try to eliminate impossible branches early. Here, the scoring function is not numeric; it is an LLM judgment.

For one provider, 120 leaf-level calls become roughly three calls: one for L1, one for L2, one for L3. Token length per call increases because each prompt contains multiple candidates, but the total cost is still far lower.

This works especially well when entities are sparse. A provider usually belongs to one or two broad categories, so the first L1 pass can remove 80% to 90% of the search space.

The general rule: if your labels have hierarchy, do not enumerate all leaves at once. Filter coarse categories first, then refine.

Optimization 2: Inheritance From Parent Entities

Many datasets have containment relationships. In my case, tools belong to providers. A weather-data provider is unlikely to contain a financial-analysis tool.

So the process becomes:

  1. Classify the provider first.
  2. Classify each tool only inside the provider’s category range.

If a provider maps to two L1 categories, and each L1 branch contains around twelve leaves, a tool’s candidate set shrinks from 120 to 24.

The same idea applies elsewhere:

  • Classify a folder or project first, then classify files inside it.
  • Classify an organization first, then refine user tags.
  • Classify a product category first, then annotate category-specific attributes.

The parent classification becomes a prior constraint for children.

Optimization 3: Batch Multiple Entities Per Call

Calling an LLM once per entity wastes context capacity. Modern models support large contexts, so multiple entities can be packed into one request.

Example:

{
  "role": "user",
  "content": "Classify these tools:\n1. weather_current: ...\n2. weather_forecast: ..."
}

The model returns all results in one response:

{
  "results": {
    "1": ["meteorology_current"],
    "2": ["meteorology_forecast"]
  }
}

Batch size matters. Too small wastes requests; too large may hurt quality or exceed context limits. In practice, 8 to 15 entities per batch is often stable.

There is another benefit: tools under the same provider share the same provider context and category candidates. Put that shared part in the system message and the changing tool list in the user message. This is friendly to prompt caching.

Optimization 4: Incremental Skipping

If an entity already has some category labels, do not ask the LLM to judge those categories again.

When building candidates, remove existing labels. If a tool already has all applicable leaf categories within its provider scope, skip it entirely.

This becomes very valuable in incremental runs. If the job runs daily, most entities are unchanged. Over time, call volume drops sharply.

This is the same principle as incremental indexing or incremental compilation: process only what changed. The key is to persist structured LLM outputs using stable IDs or slugs, not natural-language category names.

Optimization 5: Ancestor Expansion

In a three-level tree, if an entity matches an L3 leaf, it also belongs to the L2 parent and L1 grandparent. Therefore, only leaf-level judgments are necessary. Parent categories can be filled by traversing the tree.

Example:

def expand_with_ancestors(slugs, slug_map, id_map):
    result = set(slugs)
    for slug in list(slugs):
        node = slug_map.get(slug)
        pid = node.parent_id
        while pid:
            parent = id_map.get(pid)
            if parent:
                result.add(parent.slug)
                pid = parent.parent_id
            else:
                break
    return result

In graph and knowledge-base systems, this is a form of transitive closure. In a category tree, it means deriving all ancestor labels for free.

Optimization 6: Prompt Caching

Prompt caching can have a large cost impact.

For tools under the same provider, the system message often contains the provider description and candidate category list. That prefix is identical across batches; only the tool list changes.

To use caching well:

  • Put stable instructions, candidate lists, and background information first.
  • Put entity-specific data later.
  • Keep the shared prefix exactly identical, including whitespace.

If a request has 2,000 tokens of shared system prompt and 500 tokens of changing user content, repeated batches can reuse much of the prefix. The more batches share the same prefix, the larger the saving.

This is also why batching by provider is useful: it maximizes shared context and cache hit rate.

Concurrency With asyncio And Semaphore

Reducing call volume is one part. Running remaining calls efficiently is another.

For Python, asyncio plus Semaphore is a straightforward pattern:

sem = asyncio.Semaphore(concurrency)

async def process_batch(batch):
    async with sem:
        return await llm_classify(batch)

results = await asyncio.gather(
    *[process_batch(b) for b in batches],
    return_exceptions=True,
)

Start with a low concurrency such as 5 to 10, observe rate-limit errors, then increase carefully. A semaphore controls simultaneous requests, not requests per minute. If strict rate limits matter, add a token bucket or sliding-window limiter.

Combined Effect

For the original example, the rough call count changes like this:

OptimizationProvider CallsTool Calls
Brute force24,0001,200,000
Hierarchical pruning60030,000
Inheritance60010,000
Batch 8 entities per call751,250
Skip 50% existing labels38625
Ancestor expansion38625

The result is a drop from more than a million calls to fewer than a thousand. In practice, a full classification of thousands of providers and tens of thousands of tools can finish in minutes instead of hours.

The Shared Ideas

These optimizations all come from three principles.

Shrink the search space before calling the LLM. Hierarchical pruning, inheritance, and incremental skipping all remove unnecessary combinations before the expensive judgment.

Amortize call cost. Batching and prompt caching increase the amount of useful work per request and reduce repeated prefix cost.

Use structure for free inference. Ancestor expansion and parent-child constraints use data structure rather than model calls.

This is the same pattern used in search engines, recommender systems, databases, and compilers. The LLM is just an expensive evaluator; the surrounding engineering principles are not new.

Further Improvements

Several directions can push cost even lower:

  • Model cascade: use a cheap model first, then escalate uncertain cases to a stronger model.
  • Embedding prefilter: embed entity and category descriptions, then filter low-similarity candidates before calling the LLM.
  • Structured output: use JSON Schema or Pydantic-like validation to reduce parse failures and retries.
  • Active learning: send low-confidence results to human review and use feedback to improve prompts.

Closing

Using an LLM for large-scale data processing easily falls into the “one API call per record” trap. Once data grows from dozens to tens of thousands, cost and latency become unacceptable.

The good news is that computer science has decades of experience handling “large scale plus repeated patterns.” Search, databases, compilers, and distributed systems all solved similar shapes. LLMs are new, but many surrounding optimization techniques are old and reliable.