One invented word can be expensive

An exact lookup in a finite dictionary may cost a handful of transitions. If the term is present, spelling correction can stop: there is nothing to correct. If it is absent, a simple corrector may compare it with every vocabulary entry.

Let $V$ be vocabulary size and let $u$ be the number of distinct absent terms in a query. A linear correction scan performs approximately

$$W_{correction}=uV$$

candidate visits, before the cost of each edit comparison. The query string can be short while $V$ is large. An adversary can invent arbitrarily many absent terms.

Autocomplete has a different boundary. It must expand the final prefix even when that prefix is itself a word, because membership does not answer “what extends this?” If one prefix traversal is always required, its simplified cost is

$$W_{query}=(1+u)V.$$

These formulas are not elapsed-time predictions. A dictionary traversal is a portable unit that scales with the corpus and can be counted deterministically.

Substitute the correction strategy

The preceding chapter offered several physical strategies. Their query costs have different variables:

The index can make ordinary execution sublinear without making it unbounded-input safe. A broad automaton frontier or a combinatorial deletion neighborhood still needs a ceiling. The resource vector must name what each strategy consumes:

dictionary states, transitions, candidate verifications, generated variants,
result slots, scratch bytes, retained explanations, descendant tasks, time

Validate query term count, decoded length, normalization expansion, and checked products before proportional allocation. A limit applied after constructing ten thousand term states is merely a limit on the last phase.

Per-term caps multiply the adversary

Suppose every absent term receives a cap of $c$ candidate visits. One honest typo can consume at most $c$, even when finding its correction requires a full walk of $V>c$. The ordinary case loses recall.

Now submit $N$ invented terms. Their total allowance is

$$W_{per-term}=Nc.$$

The cap grows linearly with the input the cap was meant to contain. It degrades the honest singleton and barely constrains the adversarial aggregate.

One query-wide budget $B$ reverses the allocation:

$$W_{aggregate}\leq B.$$

The honest typo may spend the entire lease. Later invented terms compete for the same finite credit and eventually receive none. A child expansion receives a sublease; unused credit can return, but already consumed credit cannot be refunded because another task was canceled.

Credit is conserved

Model a lease with finite remaining credit. Every admitted operation reserves before traversal. Sequence adds consumed effort and may reuse scratch. Parallel execution adds peak memory and concurrent descendants. Fan-out multiplies only through checked arithmetic. Retained results stay charged until released.

The conservation law is

$$reserved+remaining=capacity$$

for all live subleases, with consumed credit included in reserved history. No branch can create credit by splitting. If three providers each receive the parent's full budget, the system has tripled its promise.

EXPAND-QUERY(TERMS, DICTIONARY, LEASE)
Input:  finite TERMS, DICTIONARY, and admitted aggregate LEASE
Output: expansions and a settlement receipt

results ← empty sequence
receipt ← EMPTY-RECEIPT()
for each term in DISTINCT(TERMS)
    if DICTIONARY-CONTAINS(DICTIONARY, term)
        APPEND-EXACT(results, term)
    else
        while HAS-NEXT-CANDIDATE(DICTIONARY, term)
            if not RESERVE(LEASE, one candidate visit)
                return PARTIAL(results, receipt, LEASE)
            candidate ← NEXT-CANDIDATE(DICTIONARY, term)
            RECORD-VISIT(receipt, term, candidate)
            if WITHIN-EDIT-POLICY(term, candidate)
                APPEND-ALTERNATIVE(results, term, candidate)
return COMPLETE(results, receipt, LEASE)

The pseudocode is deliberately total. Exhaustion produces a value rather than an exception, hang, or plausible-looking complete list.

Partial is a settlement, not an embarrassment

A search answer includes results, its question boundary, and settlement:

These states are not synonyms. A timeout can yield partial computation or no settled computation. Cancellation is ownership, not proof that processing stopped. Truncation is an output decision, while exhaustion is resource state.

The receipt records capacity, consumption by resource, terms attempted, candidate visits, alternatives retained, refusal point, corpus generation, and algorithm identity. A UI may say “showing results found within the resource limit” and offer a narrower query. It may not silently render a partial list as though the dictionary had been exhausted.

Local cost becomes shared risk

Run the corrector in a person's browser and a pathological query consumes that person's processor. Move the same algorithm to a shared service and one request can delay everyone. Nothing in the recurrence changed; resource ownership did.

Crosby and Wallach demonstrated the broader pattern with attacker-selected worst cases in common data structures. Hash collisions, catastrophic regular expression backtracking, decompression bombs, and search expansion share a shape: small controlled input induces disproportionate shared effort.

Admission therefore occurs before traversal and is tied to a host profile. A browser may choose a smaller time slice to preserve interaction. A batch tool may admit more effort. A shared service also bounds concurrent leases, queue depth, and retained output. Per-request bounds without concurrency bounds still allow aggregate overload.

Cancellation is not containment

Cancel-and-restart improves freshness when a new query supersedes an old one. It is not a resource proof. A process, remote provider, or uninterruptible kernel may finish after cancellation. Credit already spent is not restored; retained buffers remain charged until their owner releases them.

The hard invariant is admission:

peak admitted effort across live queries ≤ host capacity

Cancellation may reduce actual consumption within that envelope. It cannot be the mechanism that makes an otherwise unbounded promise safe.

Test the cliffs

For every finite capacity $B$, run fixtures at:

• $B-1$, $B$, and $B+1$ requested units;
• zero capacity and the smallest legal unit;
• one honest absent term needing nearly all credit;
• many distinct absent terms;
• repeated terms, which should share traversal where the contract says distinct;
• maximal normalization expansion;
• cancellation before admission, during traversal, and after settlement; and
• sequential versus concurrent provider subleases.

Assert both result identity and receipt conservation. Differentially compare a generous-budget run with the unbounded reference: whenever the bounded run says complete, their results must be identical. If it says partial, every published result must still be valid and the receipt must locate the missing traversal.

Negative results

Lessons

• Count the effort controlled by input after parsing, not merely input bytes.
• Correction short-circuits on presence; autocomplete still expands a present prefix.
• Dictionary traversals are a portable work unit; milliseconds are host data.
• A per-term cap harms an honest singleton and multiplies an adversary's credit.
• One query-wide lease conserves aggregate work and supports honest partial settlement.
• Reserve before traversal; cancellation does not refund consumed resources.
• Moving computation from a personal device to a shared host changes its threat boundary even when the algorithm is identical.
• Complete, partial, truncated, canceled, unsupported, and rejected are different outcomes.
• Test capacity cliffs and require conservation in every receipt.

Practice

1. A vocabulary has one million terms and a query has three distinct absent terms. Express the scan corrector's candidate visits in dictionary traversals.
2. Compare a cap of 50,000 per term with one 50,000-visit query lease for 100 absent terms.
3. Extend the resource vector with retained explanation bytes. State when that credit can be released.
4. Divide a lease between two parallel providers without exceeding parent peak credit. What information must the join retain?
5. Design user-facing language for partial, truncated, and canceled settlement that cannot confuse one for another.
6. Construct a boundary test in which cancellation arrives after all traversal but before publication. Which receipt is correct?

References

1. Scott A. Crosby and Dan S. Wallach. “Denial of Service via Algorithmic Complexity Attacks.” 12th USENIX Security Symposium, 2003.
2. Klaus U. Schulz and Stoyan Mihov. “Fast String Correction with Levenshtein Automata.” International Journal on Document Analysis and Recognition 5, 2002.