dotnet/machinelearning · error · InvalidOperationException

failed to insert key: wrong key order

Error message

failed to insert key: wrong key order

What it means

Insert walks the trie in sorted key order; when it finds the current key's byte label is smaller than the existing sibling label at the current node, it throws this InvalidOperationException. The double-array build algorithm requires keys to be inserted in ascending byte order so it can flush completed nodes. Out-of-order insertion breaks the structure invariants, so it fails fast.

Source

Thrown at src/Microsoft.ML.Tokenizers/Utils/DoubleArrayTrie.cs:369

            for (; keyPos <= length; ++keyPos)
            {
                uint childId = _nodes[(int)id].Child;
                if (childId == 0)
                {
                    break;
                }

                byte keyLabel = key[keyPos];
                if (keyPos < length && keyLabel == 0)
                {
                    throw new InvalidOperationException("failed to insert key: invalid null character");
                }

                byte unitLabel = _nodes[(int)childId].Label;
                if (keyLabel < unitLabel)
                {
                    throw new InvalidOperationException("failed to insert key: wrong key order");
                }
                else if (keyLabel > unitLabel)
                {
                    _nodes[(int)childId].HasSibling = true;
                    Flush(childId);
                    break;
                }

                id = childId;
            }

            if (keyPos > length)
            {
                return;
            }

            for (; keyPos <= length; ++keyPos)
            {

View on GitHub (pinned to 7b76e69cf9)

Solutions

1. Sort keys by their UTF-8 byte representation before inserting them all (Ordinal string sort matches byte order for UTF-8).
2. Collect vocabulary entries into a List and sort with StringComparer.Ordinal before the Insert loop.
3. Ensure each key is inserted exactly once — deduplicate before building.
4. Verify no code inserts into an already-built trie; DoubleArrayTrie is a build-once structure.

Example fix

// before
foreach (var kv in vocabMap)
    trie.Insert(bytes(kv.Key), len(kv.Key), kv.Value);
// after
foreach (var kv in vocabMap.OrderBy(k => k.Key, StringComparer.Ordinal))
    trie.Insert(bytes(kv.Key), len(kv.Key), kv.Value);

var sorted = keys.OrderBy(k => k, StringComparer.Ordinal).ToList();
foreach (var k in sorted) trie.Insert(Encoding.UTF8.GetBytes(k), Encoding.UTF8.GetByteCount(k), id++);

static bool KeysAreOrdinalSorted(IEnumerable<string> keys) => keys.SequenceEqual(keys.OrderBy(k => k, StringComparer.Ordinal));

try { trie.Insert(key, len, value); }
catch (InvalidOperationException ex) when (ex.Message.Contains("wrong key order"))
{ throw new InvalidOperationException("Keys must be inserted in ascending ordinal order", ex); }

When it happens

Trigger: Calling Insert with keys not sorted in ascending byte order, e.g. BuildDawg iterating a Dictionary<string,...> whose enumeration order is arbitrary, or inserting keys after a prior duplicate key already completed the path.

Common situations: Building a trie from a HashSet/Dictionary instead of a sorted collection, adding a duplicate key (equal prefix then shorter key after longer one is fine, but out-of-order distinct keys are not), or merging multiple unsorted vocab sources.

Understand the failure class

Background: "Invalid state transition" errors: "status must be X, actually Y", "already rejected/charging/uninstalled", "cannot ... while running" — what they mean when a library rejects your call — this error's family across 31 libraries.

Related errors

• failed to insert key: negative value
• failed to insert key: zero-length key
• failed to insert key: invalid null character
• failed to modify unit: too large offset
• Failed to decode token ids

AI-assisted analysis of dotnet/machinelearning@7b76e69cf9 (2026-09-11). Data as JSON: /api/errors/fbca9aad1fab3994. Report an issue: GitHub.