Classifying Into a Deep Category Tree with Jev and Beam Search in Laravel

A client's product catalogue had to map onto Shopify's taxonomy — roughly 10,000 leaves, eleven levels deep in places. The first attempt put the whole tree in an LLM prompt and asked for a category; it was slow, expensive, and returned categories that did not exist. The second attempt asked Jev one Choice question per level and took the best child each time, which is faster and always returns a real category — and quietly files cat window beds under "Pet Chairs".

That second failure is the interesting one, because the answer looks confident. Here is how to fix it with a beam.

Load the taxonomy into a direct-children map#

Hierarchical classification in Laravel starts with a cheap lookup: given a path from the root, what are that node's direct children? Whether your taxonomy lives in a categories table with parent_id or in a flat A > B > C text file, flatten it once into a map of path key to child list and cache it. Sibling order is part of the question you will send, so the ordering has to be stable or your results stop being reproducible.

<?php

declare(strict_types=1);

namespace App\Support\Taxonomy;

final readonly class Taxonomy
{
    /** @param array<string, list<string>> $childrenByPath */
    private function __construct(private array $childrenByPath) {}

    /**
     * Build from lines like "Animals & Pet Supplies > Pet Supplies > Cat Supplies".
     *
     * @param iterable<string> $paths
     */
    public static function fromPaths(iterable $paths, string $separator = ' > '): self
    {
        $childrenByPath = [];

        foreach ($paths as $line) {
            $prefix = [];

            foreach (explode($separator, $line) as $label) {
                $key = self::key($prefix);
                $childrenByPath[$key] ??= [];

                // First sighting wins, so sibling order follows the source file.
                if (! in_array($label, $childrenByPath[$key], true)) {
                    $childrenByPath[$key][] = $label;
                }

                $prefix[] = $label;
            }
        }

        return new self($childrenByPath);
    }

    /**
     * @param list<string> $path
     * @return list<string>
     */
    public function childrenOf(array $path): array
    {
        return $this->childrenByPath[self::key($path)] ?? [];
    }

    /** @param list<string> $path */
    public function isLeaf(array $path): bool
    {
        return $this->childrenOf($path) === [];
    }

    /** @param list<string> $path */
    private static function key(array $path): string
    {
        // Unit separator: safe against category names containing slashes or pipes.
        return implode("\x1f", $path);
    }
}

Bind it once per taxonomy version so a rebuild is a cache bust rather than a deploy:

$this->app->singleton(Taxonomy::class, fn (): Taxonomy => Cache::rememberForever(
    'taxonomy:shopify:2026-02',
    fn (): Taxonomy => Taxonomy::fromPaths(
        File::lines(storage_path('taxonomy/shopify-2026-02.txt'))
    ),
));

Cache keys that include the taxonomy version matter later: when a category moves, only the nodes beneath the change need invalidating. If you are already caching derived structures per request, the memo cache driver in Laravel 13 will keep repeated childrenOf() lookups off the shared store within a single classification run.

Build one Choice question from a node's children#

Every node is a Choice question whose criteria are its direct children, and whose returned probabilities map is that node's outgoing edges. Send the options under opaque keys — c0, c1, c2 — and keep a reversible map back to the labels. Long category names then never have to round-trip exactly, and you are not relying on the model echoing "Cat Window Beds & Perches" character for character.

<?php

declare(strict_types=1);

namespace App\Support\Taxonomy;

use App\Support\Jev\Choice;

final readonly class ChildChoice
{
    /**
     * @param list<string> $labels
     * @return array{0: Choice, 1: array<string, string>} question and its key => label map
     */
    public static function for(array $labels): array
    {
        $keys = [];

        foreach (array_values($labels) as $index => $label) {
            $keys["c{$index}"] = $label;
        }

        return [
            new Choice(
                instructions: 'Which direct child category best matches this document?',
                criteria: $keys,
            ),
            $keys,
        ];
    }
}

The Choice class here is the one from the typed question set I use for every Jev call. Add one method to that article's Answers object, because the whole technique depends on reading the full distribution rather than the single winner:

/** @return array<string, float> */
public function probabilities(string $id): array
{
    return array_map(floatval(...), $this->answers[$id]['probabilities']);
}

Jev's Choice criteria are capped at 255 entries. That cap is the real reason you cannot flatten a large taxonomy into one question — it is a 422, not a quality argument.

Walk the tree greedily and watch it fail#

Greedy traversal is twenty lines and worth writing first, because you need to see the failure shape before the fix makes sense. Ask the root, take the highest-probability child, descend, repeat until you hit a leaf. A node with exactly one child is not a decision — skip the request and do not count it toward the score.

<?php

declare(strict_types=1);

namespace App\Support\Taxonomy;

use App\Support\Jev\Jev;
use App\Support\Jev\QuestionSet;

final readonly class GreedyClassifier
{
    public function __construct(
        private Jev $jev,
        private Taxonomy $taxonomy,
        private int $maxDepth = 12,
    ) {}

    /** @param string|array<string, mixed> $state */
    public function classify(string|array $state): PathCandidate
    {
        $candidate = new PathCandidate([]);

        for ($depth = 0; $depth < $this->maxDepth; $depth++) {
            $children = $this->taxonomy->childrenOf($candidate->path);

            if ($children === []) {
                break;
            }

            $probabilities = $this->distributionFor($state, $children);
            arsort($probabilities);

            $label = (string) array_key_first($probabilities);
            $candidate = $candidate->extend($label, $probabilities[$label], count($children) > 1);
        }

        return $candidate;
    }

    /**
     * @param string|array<string, mixed> $state
     * @param list<string> $children
     * @return array<string, float>
     */
    private function distributionFor(string|array $state, array $children): array
    {
        if (count($children) === 1) {
            return [$children[0] => 1.0];
        }

        [$question, $keys] = ChildChoice::for($children);
        $probabilities = $this->jev
            ->ask($state, QuestionSet::of(['child' => $question]))
            ->probabilities('child');

        $byLabel = [];

        foreach ($keys as $key => $label) {
            $byLabel[$label] = $probabilities[$key] ?? 0.0;
        }

        return $byLabel;
    }
}

Run this against anything with a near-tie near the root and you get TypeSafe's published results: on their hierarchical classification cookbook, greedy files a bird perch patent under "E99Z99/00 Subject matter not otherwise provided for" and a cat window shelf under "Pet Chairs". Both answers are plausible. Neither is right. Greedy matched 2 of their 4 labelled examples; beam search with K=3 matched 4 of 4.

Score a path by geometric-mean probability#

Before you can keep several paths, you need to compare them, and the obvious metric is wrong. Multiplying edge probabilities penalises depth: an eight-decision path at 0.9 an edge scores 0.43, while a three-decision path of coin flips scores 0.125 — but push the deep path to eleven decisions and it loses to noise. Length-normalise with the geometric mean, product(p) ** (1 / decisions). In PHP, compute it in log space from the start; exp(sum(log p) / decisions) is the same number without the underflow, and anything past ten levels will underflow.

<?php

declare(strict_types=1);

namespace App\Support\Taxonomy;

final readonly class PathCandidate
{
    private const EPSILON = 1e-9;

    /** @param list<string> $path */
    public function __construct(
        public array $path,
        public float $logProbabilitySum = 0.0,
        public int $decisionCount = 0,
    ) {}

    /** Geometric mean of the edge probabilities: exp(mean(log p)). */
    public function score(): float
    {
        if ($this->decisionCount === 0) {
            return 1.0;
        }

        return exp($this->logProbabilitySum / $this->decisionCount);
    }

    public function extend(string $label, float $probability, bool $isDecision): self
    {
        return new self(
            [...$this->path, $label],
            $this->logProbabilitySum + ($isDecision ? log(max($probability, self::EPSILON)) : 0.0),
            $this->decisionCount + ($isDecision ? 1 : 0),
        );
    }

    public function leaf(): string
    {
        return $this->path[array_key_last($this->path)] ?? '';
    }
}

Skipping single-child nodes in decisionCount is not cosmetic. A taxonomy with long single-child chains — CPC and MeSH both have them — will otherwise reward whichever branch happens to pass through more free edges.

Expand K frontiers in parallel with Http::pool()#

Beam search keeps the best K candidates, expands every unfinished one, then re-ranks the union of finished and newly expanded paths and trims back to K. Each frontier is an independent Jev request against the same state, which is exactly the shape Http::pool() is for — a width-3 beam costs one beam-step of latency, not three. Add an askMany() to the Jev client:

/**
 * @param array<string, array{state: string|array<string, mixed>, questions: QuestionSet}> $requests
 * @return array<string, Answers>
 */
public function askMany(array $requests): array
{
    $responses = Http::pool(fn (Pool $pool): array => array_map(
        fn (string $key) => $pool->as($key)
            ->withToken($this->apiKey)
            ->timeout(20)
            // 429 and 529 are the two documented back-off cases.
            ->retry(3, fn (int $attempt): int => $attempt * 250)
            ->post('https://api.typesafe.ai/v1/systemone', [
                'state' => $requests[$key]['state'],
                'model' => $this->model,
                'questions' => $requests[$key]['questions']->toPayload(),
            ]),
        array_keys($requests),
    ));

    $answers = [];

    foreach (array_keys($requests) as $key) {
        $response = $responses[$key]->throw();
        $answers[$key] = new Answers($response->json('answers'), $response->json('usage'));
    }

    return $answers;
}

This is the one place a pool belongs in a Jev integration. Within a single node you should still batch questions into one request, because Jev bills for the state and a pool re-sends it per request. Across frontiers you have no choice: they are different questions about the same state, and you want them in flight together. If you need the same fan-out over work that is not HTTP, the Concurrency facade covers the general case.

The classifier itself:

<?php

declare(strict_types=1);

namespace App\Support\Taxonomy;

use App\Support\Jev\Jev;
use App\Support\Jev\QuestionSet;

final readonly class BeamClassifier
{
    public function __construct(
        private Jev $jev,
        private Taxonomy $taxonomy,
        private int $beamWidth = 3,
        private int $maxDepth = 12,
    ) {}

    /** @param string|array<string, mixed> $state */
    public function classify(string|array $state): Classification
    {
        $beam = [new PathCandidate([])];

        for ($depth = 0; $depth < $this->maxDepth; $depth++) {
            $expandable = array_values(array_filter(
                $beam,
                fn (PathCandidate $candidate): bool => ! $this->taxonomy->isLeaf($candidate->path),
            ));

            if ($expandable === []) {
                break;
            }

            $finished = array_values(array_filter(
                $beam,
                fn (PathCandidate $candidate): bool => $this->taxonomy->isLeaf($candidate->path),
            ));

            $expanded = [];

            foreach ($this->distributionsFor($state, $expandable) as $index => $probabilities) {
                $isDecision = count($probabilities) > 1;

                foreach ($probabilities as $label => $probability) {
                    $expanded[] = $expandable[$index]->extend($label, $probability, $isDecision);
                }
            }

            // Finished leaves stay in contention — a shallow leaf can still win.
            $beam = $this->bestOf([...$finished, ...$expanded]);
        }

        $beam = $this->bestOf($beam);

        return new Classification($beam[0], $beam[1] ?? null);
    }

    /**
     * @param list<PathCandidate> $candidates
     * @return list<PathCandidate>
     */
    private function bestOf(array $candidates): array
    {
        usort(
            $candidates,
            fn (PathCandidate $a, PathCandidate $b): int => $b->score() <=> $a->score(),
        );

        return array_slice($candidates, 0, $this->beamWidth);
    }

    /**
     * @param string|array<string, mixed> $state
     * @param list<PathCandidate> $candidates
     * @return array<int, array<string, float>>
     */
    private function distributionsFor(string|array $state, array $candidates): array
    {
        $requests = [];
        $keyMaps = [];
        $distributions = [];

        foreach ($candidates as $index => $candidate) {
            $children = $this->taxonomy->childrenOf($candidate->path);

            if (count($children) === 1) {
                // Not a decision, so it never reaches Jev.
                $distributions[$index] = [$children[0] => 1.0];

                continue;
            }

            [$question, $keys] = ChildChoice::for($children);
            $keyMaps[$index] = $keys;
            $requests["f{$index}"] = [
                'state' => $state,
                'questions' => QuestionSet::of(['child' => $question]),
            ];
        }

        $answers = $requests === [] ? [] : $this->jev->askMany($requests);

        foreach ($keyMaps as $index => $keys) {
            $probabilities = $answers["f{$index}"]->probabilities('child');
            $byLabel = [];

            foreach ($keys as $key => $label) {
                $byLabel[$label] = $probabilities[$key] ?? 0.0;
            }

            $distributions[$index] = $byLabel;
        }

        ksort($distributions);

        return $distributions;
    }
}

Note that finished leaves are re-ranked alongside the expanded candidates rather than being set aside. That is what lets a shallow, decisive leaf beat a deep speculative one — and, in the other direction, lets deeper evidence overturn an early near-tie.

Gate on the separation ratio#

The geometric mean tells you how good the winning path is; the ratio between the top two tells you whether the win means anything. top_path_score / second_path_score near 1x says the two best leaves are indistinguishable, and that record should go to a human rather than silently acquiring a category. This is a different signal from the per-answer confidence field Jev returns, which describes one node's decision — the ratio describes the whole traversal.

<?php

declare(strict_types=1);

namespace App\Support\Taxonomy;

enum Outcome
{
    case AutoFile;
    case Confirm;
    case HumanReview;
}

final readonly class Classification
{
    public function __construct(
        public PathCandidate $best,
        public ?PathCandidate $runnerUp,
    ) {}

    public function separation(): float
    {
        if ($this->runnerUp === null) {
            return INF;
        }

        return $this->best->score() / max($this->runnerUp->score(), 1e-9);
    }

    public function outcome(): Outcome
    {
        // Thresholds are yours to calibrate against a labelled set — these are a starting point.
        return match (true) {
            $this->separation() >= 2.0 => Outcome::AutoFile,
            $this->separation() >= 1.2 => Outcome::Confirm,
            default => Outcome::HumanReview,
        };
    }
}

Calibrate those numbers against your own labelled data rather than trusting mine. The approach is the same one I use for confidence-gated intent routing: the model gives you a number, your code owns the threshold, and the threshold is a product decision.

Persist every decision for observability#

The accuracy bump is the smaller half of the argument for decomposing a classifier into a tree. The bigger half is that every intermediate decision becomes a row you can query. Write one record per node visited — the path asked, the options offered, the distribution returned, the edge taken:

Schema::create('classification_decisions', function (Blueprint $table): void {
    $table->id();
    $table->morphs('classifiable');
    $table->string('taxonomy_version')->index();
    $table->string('node_path', 1024);
    $table->string('node_path_hash', 64)->index();   // sha256 of node_path, for grouping
    $table->unsignedTinyInteger('depth');
    $table->json('probabilities');                    // label => p, as returned
    $table->string('chosen_label');
    $table->decimal('chosen_probability', 8, 6);
    $table->boolean('on_winning_path')->default(false);
    $table->timestamps();
});

That table answers the questions you will actually be asked in three months. Which node do our misclassifications cluster under? How often is edge X traversed? Did last week's taxonomy edit change anything? Group by node_path_hash and the heat map falls out. The same decompose-then-record instinct is what makes composite scoring with weights you own debuggable, and it is worth the extra table.

An Artisan command that prints both strategies side by side makes the difference concrete for whoever signs off on the rollout:

php artisan taxonomy:compare --limit=50 --beam=3

Document                         Greedy leaf        Beam K=3 leaf                 sep
-------------------------------- ------------------ ----------------------------- -----
Wall-mounted cat window shelf    Pet Chairs         Cat Window Beds & Perches      1.31x
Freestanding wooden bird perch   E99Z99/00          A01K31/12 Perches for poultry  4.02x

Test the traversal against a labelled fixture tree#

A beam search with a faked HTTP layer is fully deterministic, so build the one fixture that matters: a small tree where greedy is wrong and beam is right. Keep the probabilities arithmetic simple enough to verify by hand, because the test is also your explanation of why the beam earns its keep.

<?php

declare(strict_types=1);

use App\Support\Jev\Jev;
use App\Support\Taxonomy\BeamClassifier;
use App\Support\Taxonomy\GreedyClassifier;
use App\Support\Taxonomy\Taxonomy;
use Illuminate\Support\Facades\Http;

beforeEach(function (): void {
    $this->taxonomy = Taxonomy::fromPaths([
        'Pet Supplies > Pet Beds > Cat Window Beds & Perches',
        'Pet Supplies > Pet Beds > Dog Beds',
        'Pet Supplies > Pet Chairs',
    ]);

    Http::fake([
        'api.typesafe.ai/*' => function (): array {
            // Keyed by option count: two children at "Pet Supplies", two under "Pet Beds".
            static $responses = [
                ['c0' => 0.48, 'c1' => 0.52],   // Pet Beds vs Pet Chairs — a near tie
                ['c0' => 0.97, 'c1' => 0.03],   // Cat Window Beds & Perches vs Dog Beds
            ];

            $probabilities = array_shift($responses);

            return [
                'model' => 'jev-1.13',
                'answers' => [
                    'child' => [
                        'type' => 'choice',
                        'choice' => array_key_first($probabilities),
                        'confidence' => 0.6,
                        'probabilities' => $probabilities,
                    ],
                ],
                'usage' => ['input_tokens' => 120, 'output_tokens' => 12],
            ];
        },
    ]);
});

it('loses the right leaf when it only keeps the best child', function (): void {
    $greedy = new GreedyClassifier(app(Jev::class), $this->taxonomy);

    expect($greedy->classify('A padded floating window shelf for one cat.')->leaf())
        ->toBe('Pet Chairs');
});

it('recovers the right leaf by keeping a second path', function (): void {
    $beam = new BeamClassifier(app(Jev::class), $this->taxonomy, beamWidth: 2);

    $classification = $beam->classify('A padded floating window shelf for one cat.');

    // sqrt(0.48 * 0.97) = 0.682 beats the single-decision 0.52 of Pet Chairs.
    expect($classification->best->leaf())->toBe('Cat Window Beds & Perches')
        ->and(round($classification->best->score(), 3))->toBe(0.682)
        ->and(round($classification->separation(), 2))->toBe(1.31);
});

Once that passes, point the same harness at a labelled sample of real records and track leaf-level accuracy per taxonomy version. It is the same golden-dataset discipline I use for LLM evals in Pest and CI, just with a cheaper oracle: your taxonomy already has correct answers in it.

Gotchas and Edge Cases#

A DAG is not a tree. MeSH is the canonical example — one descriptor sits under several parents. Expand the official paths into distinct branches before loading, as TypeSafe's cookbook does, or your traversal will revisit nodes and your childrenOf() cache will disagree with itself.

Request count is K per level, not K total. A width-3 beam on a twelve-level taxonomy is up to 36 requests for one document. Cap maxDepth, and treat hitting the cap as an error signal about the tree rather than a normal outcome.

255 options per Choice is a hard ceiling. Most taxonomies have a node somewhere that breaks it — Shopify's does. Either split that node into alphabetical sub-questions and treat the split as a free, non-counted decision, or fix the taxonomy. Do not silently truncate.

High confidence on easy decisions is not evidence. A leaf reached through six two-child nodes can post a geometric mean of 0.95 and still be wrong, because none of those decisions was hard. The separation ratio is the better gate precisely because it compares two paths rather than grading one.

Cache per node, not per document. The same node gets asked over and over across a batch of similar documents only if the state is identical, which it usually is not. Key the cache on (document_hash, node_path, taxonomy_version, model) so a taxonomy edit invalidates only what changed.

Wrapping Up#

Start greedy, measure it against a labelled sample, then add the beam — the diff is about eighty lines and the Http::pool() fan-out means it barely costs you latency. The decision table you build along the way will outlive the accuracy argument.

If you are wiring this into an existing pipeline, the typed Jev question set is the right foundation to build the traversal on, and scoring passages before they reach an LLM is the same pattern applied to retrieval rather than taxonomy.

FAQ#

How do I classify text into a taxonomy with thousands of categories?

Do not try to do it in one question. Jev caps Choice criteria at 255 options, and quality degrades long before that ceiling. Instead walk the tree: ask one Choice question per node whose options are that node's direct children, and descend until you reach a leaf. A 10,000-leaf taxonomy eleven levels deep becomes eleven small questions rather than one impossible one.

What is beam search in classification?

Beam search keeps the best K candidate paths at every level instead of committing to one. At each step you expand every unfinished candidate, score the union of finished and newly expanded paths, and trim back to K. With K=3 you are exploring three plausible branches in parallel, so evidence found deeper in the tree can overturn a decision made near the root. Setting K=1 gives you greedy search exactly.

Why is greedy classification wrong for deep hierarchies?

Greedy takes the highest-probability child at every node and discards the alternatives, so one near-tie near the root sends the whole traversal into the wrong branch with no way back. The failure is hard to spot because the final answer is a real category that looks plausible. In TypeSafe's published four-taxonomy comparison, greedy matched 2 of 4 expected leaves while beam search with K=3 matched 4 of 4.

How does Jev's Choice primitive return probabilities?

A Choice answer carries three things: choice, the name of the highest-probability option; confidence, a calibrated 0–1 certainty in that selection; and probabilities, the full distribution over every option you supplied, keyed by option name and summing to roughly 1. Hierarchical classification uses the whole distribution, not just choice — those probabilities are the node's outgoing edge weights.

How many API requests does hierarchical classification need?

Greedy needs one request per level, minus any single-child nodes, which are not decisions and should never be sent. Beam search needs up to K requests per level, so a width-3 beam on an eight-level tree is up to 24 requests for one document. Because each frontier is independent, Http::pool() runs them concurrently and the wall-clock cost stays close to one request per level.

How do I know when a hierarchical classification is ambiguous?

Compute the separation ratio: the winning path's geometric-mean score divided by the runner-up's. A ratio near 1x means the two best leaves are effectively indistinguishable and the record should go to a human. A large ratio means the winner is clearly separated. Calibrate the thresholds against a labelled sample rather than picking numbers in the abstract.

Can I use this for product categories or support ticket routing?

Yes — product catalogues mapping onto Shopify's taxonomy and support desks routing into a multi-level department structure are the two most common cases. The method only needs a stable tree, a document, and a Choice question per node. For a shallow routing tree of a dozen departments, a single Choice question gated on confidence is simpler and enough; reach for a beam when the tree is deep enough that one early mistake is unrecoverable.