How I Cut "No Results" on Typos from 48% to 14% in Offline Search

The question

Our classroom panels needed search that works with no network. A teacher types “photosynthesis” or “Ohm’s law”, and the panel finds the right lesson boards from a few thousand NCERT-aligned slides downloaded in advance. There’s no server to ask and no embedding model to run, just text on the device.

The prototype used a small in-memory BM25 index written in Kotlin, with no database at all. The first question anyone asks about that is fair: why not SQLite’s full-text search? Android ships SQLite, FTS5 has bm25() ranking built in, and Room supports full-text tables.

My initial mental model

NCERT boards ──► FTS5 virtual table ──► MATCH 'user query' ORDER BY bm25(t)

If FTS5 was available and ranked at least as well, a maintained engine would beat a hand-written one. I built it as a second, quarantined engine inside the app, behind the same search API, so the two could be measured against each other.

What actually happens

The module isn’t there

On the panel we ship to, a Teachmint X running API 36, creating the table fails:

CREATE VIRTUAL TABLE t USING fts5(heading, body)
  → no such module: fts5 (code 1 SQLITE_ERROR)

I probed every module on the device:

sqlite_version() : 3.44.3
fts3 / fts4      : OK
fts5, fts5vocab  : no such module
rtree, spellfix1 : no such module

That could have been a version or API-level issue, so I checked the library itself. I pulled /system/lib64/libsqlite.so off the panel and ran strings over it: not one fts5 symbol. FTS3 and FTS4 are present, with matchinfo() and snippet(). The ROM’s SQLite was compiled without FTS5, and no app-side change can add it back.

FTS4 is not a fallback. It has matchinfo(), which returns raw term and document counts, but bm25() does not exist. Getting BM25 out of FTS4 means recomputing it in Kotlin from those counts, and at that point the in-memory index is simpler and already written. It’s also why Room has @Fts3 and @Fts4 and no @Fts5.

That’s one device: the OEM ROM we ship to. I couldn’t measure other Android builds, but the lesson generalizes. If a SQLite module can be missing at all, using it means a runtime probe and a full fallback, which means shipping two engines.

Where it does run, it ranks worse

To make sure I wasn’t keeping the in-memory engine out of habit, I ran both engines on a desktop SQLite (3.51.0, FTS5 compiled in). Both used the same corpus and our gold query sets:

Query set	Engine	hit@1	hit@5	MRR
Hard “tripwire” queries (114)	in-memory BM25	0.518	0.877	0.670
	FTS5	0.307	0.754	0.487
General queries (240)	in-memory BM25	0.871	0.975	0.916
	FTS5	0.854	0.963	0.908

FTS5 loses 41% of hit@1 on the hard set. The cause is structural, not tuning. FTS5 has no stopword facility: its porter tokenizer doesn’t filter, and a stoplist needs a tokenizer written in C. So “the”, “of”, “is” and the contraction debris (ve, ll, s) are all indexed. They inflate every document’s length, and BM25 normalizes every score by document length. The damage shows up even on single-word queries with no stopwords in them. “Amplitude” ranked its right answer 3rd in our engine and 10th in FTS5. “Insulin” went 3rd → 9th.

FTS5 also can’t express half of our ranking config:

k1 and b are hardcoded at 1.2 and 0.75.
Excluding “chatter” text changes corpus statistics, which needs a second table.
Per-term coverage costs an extra query per term.
Its idf goes negative for a term in more than half the corpus, so score thresholds don’t transfer.

The engine we kept

The in-memory index is plain BM25: tokenize, stem, drop stopwords, score. The tokenizer does a few things FTS5 couldn’t:

It folds H₂O to h2o, so the subscript and ASCII spellings meet.
It keeps single letters like C and O queryable, because chemistry needs them.
It strips combining marks before splitting, so Devanagari words stay whole.

Measured on the panel with the real corpus of a few thousand boards:


Index build, cold	2.63 s
Index build, warm	1.78 s
Query latency, mean / p95	1.54 ms / 4.00 ms
Hard-set hit@1 / hit@5 / MRR	0.518 / 0.877 / 0.671

The build time is FTS5’s one real advantage, and it’s worth attacking with a faster tokenizer or a background build rather than with a dependency the hardware doesn’t have.

The evaluation harness is a second implementation

The ranking numbers above came from the Kotlin index on the panel. A separate Python harness, running the same corpus and gold sets on a laptop, produced the same numbers to three decimals. Two code paths on two machines agreeing is the cross-check that the measurement is measuring the right thing. It also meant I could prototype ranking changes in Python and trust them before porting.

The surprising part: a typo blanked the screen

Search had a confidence gate. If too little of the query matched (low coverage), it showed “no confident results” rather than guessing. That’s reasonable, until you notice a misspelled word matches nothing at all.

A synthetic typo set, one character changed in each hard-set query, showed that 47.7% of typo’d queries returned an empty screen. A typo didn’t rank badly. It removed results entirely.

The fix that worked expands a query term only when it matches nothing (df == 0):

// Simplified.
fun expand(term: String): List<Variant> = when {
    df(term) > 0    -> listOf(Variant(term, 1.0))  // exact: never touch
    term.length < 5 -> listOf(Variant(term, 1.0))  // keep C, H, O, N exact
    else -> prefixMatch(term).ifEmpty { editDistance(term, max = 2) }
                .take(3)
                .ifEmpty { listOf(Variant(term, 1.0)) }  // fail honestly
}

Because expansion only fires on terms that would otherwise contribute nothing, it never displaces an exact match. Clean queries gave bit-identical results with fuzzy matching on or off, all 114 of 114.

On the desktop harness, typo’d hard-set hit@1 went 0.198 → 0.459, and empty screens went from 47.7% → 8.1%. On the panel, with its own test run, empty screens went 48.6% → 14.4%, at a cost of +2.16 ms mean per query.

Three details mattered more than I expected:

Damerau, not plain Levenshtein. Porter stemming makes edit distances bigger. “Alltoropy” stems to alltoropi, and reaching allotropi is a transposition. Plain Levenshtein scores that as 2. Counting a transposition as 1 edit fixes it.
Distance 2 is an optimum, not a dial. Distance 3 was worse (hit@1 0.351 vs 0.459), because the extra candidates are mostly wrong.
Truncation is not a typo. “photosynt” is four edits from “photosynthesis”. Every character is right, there are just fewer of them, so raising the edit budget is the wrong fix. A prefix tier first handles it, and the order is load-bearing. With edit distance first, the prefix tier fired zero times, because distance 2 always returned something. Prefix-first took truncated-query hit@1 from 0.354 → 0.456 without losing any of the typo gains. That works because a typo is almost never a prefix of a real word.

A crash hiding in `MATCH`

One more reason the FTS5 experiment was worth running: it showed how easy it is to ship a crash with FTS5. Its MATCH operand is a query language, not a string. Two of our own gold queries throw when passed through unescaped:

MATCH 'Acid-Base Indicators'          → no such column: Base
MATCH 'ATP (Adenosine Triphosphate)'  → fts5: syntax error near "ATP"

A hyphen is a column filter, and parentheses group. The only safe construction is to split the input and emit every term as a double-quoted string, joined with an explicit OR. A quoted string can’t be an operator, so a user typing “NOT” searches for the word “not”. The tests run 20 hostile strings through a real table, and assert that the unescaped forms do throw, so nobody can later “simplify” the escaping away.

Practical consequences

The in-memory BM25 index shipped. It went into the whiteboard app as offline content search, with the corpus built and published from the backend and downloaded to panels in the background.

Two details from the rollout:

Figures: the boards’ AI-generated figures were 2000×2000 PNGs, 23 MB in total. Re-encoded as WebP (800 px, quality 75), the pack is about 3.7 MB. Lossless WebP came out 3–7× larger than the PNGs, because these figures have photographic texture.
A production bug that had nothing to do with ranking. Searches for “acid” returned nothing on a panel that had the full corpus installed. The index had been built from a six-record sample bundled for debugging, while the real download was still in flight, and then cached process-wide. Downloads now invalidate the index, and a corpus that fails to open reports itself as unavailable instead of falling back to sample content.

What I would remember

Probe the platform you ship to, not the one in the docs. One strings over libsqlite.so settled a week of design.
A standard engine isn’t automatically better. FTS5 ranked worse on our data for a structural reason: no stopwords.
Expand only what would otherwise match nothing. Fallback-only fuzzy matching is safe by construction, and you can prove it with bit-identical clean results.
Order your candidate generators by precision. Prefix before edit distance, because each tier should only run when the cheaper, more precise one finds nothing.
Make the eval harness an independent implementation. Agreement to three decimals is evidence. Agreement with yourself isn’t.