Cursor's Local Trigram Indexes Speed Up Regex Search in Large Repositories
Cursor has implemented local indexes for regex search right in the IDE. This solves the problem of slow scanning in large monorepos, where classic ripgrep takes 15+ seconds per call, and the AI agent generates dozens of such queries.
The technology is based on the trigram inverted index from 1993. The text is broken down into all 3-character sequences (trigrams), which serve as keys in a dictionary. Each key corresponds to a list of files containing that sequence. The regex query is decomposed into a set of trigrams, posting lists are intersected to select candidates. Then grep is applied only to a dozen files instead of thousands.
Sparse n-grams for Precise Scoping
On top of the base index, sparse n-grams are added. The length of each n-gram is computed deterministically: using weights of character pairs based on crc32 or a frequency table built from terabytes of open-source code.
During indexing, all possible n-grams are generated; during search, a minimal covering set. This reduces the number of lookups and improves filtering accuracy.
// Example dekompozitsii regex in n-grams
regex: \w+@\w+\.com
n-grams: ['@', 'w+', '.c', 'com', ...] // sparse pokryodkrycie
candidates = intersect(postings(ngrams))Local Storage and Commit Binding
The index is stored locally on the user's machine in two mmap files. Reasons:
- The AI agent still reads files locally for final verification anyway.
- Network roundtrips destroy the speed gain.
The index is tied to a specific git commit. Uncommitted changes are overlaid on top without rebuilding.
- mmap advantages: zero overhead on loading, fast navigation through posting lists.
- Update: triggered on git pull/push or manual rebuild.
- Size: proportional to codebase; for 10M LoC — ~500MB.
Performance Comparison
| Approach | Time per query (10k files) | Candidates for grep |
|----------|----------------------------|---------------------|
| ripgrep | 15–20 sec | 10k |
| Cursor index | 50–200 ms | 10–50 |
In real-world scenarios with 100+ queries from the agent, the overall speedup reaches 100x.
Trigrams ensure completeness (recall=1 for exact substrings), while sparse n-grams add precision without false positives.
Key Points
- Trigram index reduces candidates from thousands to dozens of files.
- Sparse n-grams minimize lookups via minimal covering set.
- Local mmap storage eliminates network delays.
- Binding to git commit with overlay of uncommitted changes.
- 100x speedup for regex search for AI agents in large monorepos.
— Editorial Team
No comments yet.