Fast Regex Search Indexing for AI Agent Tool Performance

cursor · Tech · 2026 · source Agentic: yes · promotional bias: low · source-backed · extracted with prompt 0.5.6 (schema v2)

Generated from extraction.json — do not edit by hand. Every claim cites verbatim source evidence; stated means the quote directly asserts the claim, implied means it supports it indirectly.

Problem

Domain: AI coding-agent tool latency

Cursor needed regular-expression search to stay fast for coding agents in very large monorepos, because even ripgrep searches over all files could take more than 15 seconds and stall interactive agent workflows.

Constraints:

• Agents frequently use grep-style tools even when semantic indexes are also available.
• Ripgrep is fast per file but still must scan all files in large projects.
• Large enterprise monorepos make grep latency scale with repository size and complexity.
• Regex search needs freshness because agents search for text they just wrote.
• Server-side indexes would require file synchronization or roundtrips and raise privacy/security concerns.
• The editor process must keep memory usage minimal.

Architecture

Cursor built a local, client-side sparse n-gram index for regular-expression search. At index time it extracts deterministic sparse n-grams over source code using character-pair weights, stores posting lists and a compact hash/offset lookup table in separate files, memory-maps only the lookup table in the editor, and at query time uses a covering algorithm to generate minimal n-grams, fetch candidate postings, then performs deterministic regex matching on the scoped-down files.

Diagram confidence: explicit (topology described by the source).

flowchart LR
  agent-grep-tool["Agent grep tool"] --> regex-query-decomposer["Regex query decomposer"]
  source-code-indexer["Source-code indexer"] --> character-pair-frequency-table["Character-pair frequency table"]
  source-code-indexer --> sparse-n-gram-lookup-table["Sparse n-gram lookup table"]
  source-code-indexer --> posting-files["Posting files"]
  regex-query-decomposer --> sparse-n-gram-lookup-table
  sparse-n-gram-lookup-table --> posting-files
  posting-files --> candidate-file-scanner["Candidate file scanner"]
  candidate-file-scanner --> agent-grep-tool
  git-backed-update-layer["Git-backed update layer"] --> source-code-indexer

Components

Data flow

Source files are indexed locally by extracting sparse n-grams into posting lists and a lookup table. A regex query is decomposed into minimal sparse n-grams, candidate documents are found from postings, the candidate files are loaded from the local workspace, and the regex is matched normally on the reduced set so agents avoid scanning the whole codebase.

Why this architecture

Cursor chose local sparse n-grams because regex search is a latency-critical agent operation that semantic indexes cannot replace. Sparse n-grams pay more work at indexing time to reduce query-time lookups; keeping the index local avoids network roundtrips, security concerns, and stale reads when agents search for their own edits.

Models used: Composer 2 · Ripgrep · Sparse n-gram index · Inverted index · Posting lists · Memory-mapped lookup table · Git-backed update layer

Scale

• Cursor routinely saw rg invocations taking more than 15 seconds.
  “We routinely see rg invocations that take more than 15 seconds”article, stated
• The issue is pronounced in large Enterprise monorepos.
  “many of Cursor's users, particularly large Enterprise customers, work out of very large monorepos.”article, stated
• The weighting table uses a couple terabytes of open-source code.
  “we can pick up a couple terabytes of Open-Source code from the internet and build a frequency table”article, stated
• The example performance chart spans workflows up to about 240 seconds.
  “Investigation in chromiumRefactoring in chromiumInvestigation in cursorMinor feature in cursor0s30s60s90s120s150s180s210s240sThinkingGrepReadEdit”article, stated

Alternatives considered (roads not taken)

Plain ripgrep over all files.

Rejected because: Ripgrep is fast but still scans every file and stalls agents in large monorepos.

Naive source-code tokenization.

Rejected because: Language-aware tokenization is hard and historically did not support regex matching well.

Classic trigram inverted index.

Rejected because: Trigrams are a good middle ground but can still create large indexes and query-time tradeoffs.

Suffix-array search.

Rejected because: Suffix arrays are hard to scale and dynamically update for large or many codebases.

Server-side regex indexes.

Rejected because: Server-side search would require synchronizing files or expensive client roundtrips and adds privacy concerns.

Patterns

tool-use-orchestration (coding-agent search)

Cursor optimizes the grep-style search tool that agents repeatedly call while navigating codebases.

latency-optimization (local regex indexing)

The sparse n-gram index scopes down candidate files so agents avoid slow whole-repository scans.

privacy-preserving-processing (local indexing)

Cursor keeps regex indexes local so matching does not require syncing files to a server.

Tradeoffs

Where to pay the computational cost.

Chose High upfront indexing cost over Scanning all files at query time.

Rationale: The sparse n-gram index makes repeated agent queries fast, which matters more than one-time indexing cost.

Where to store and query the index.

Chose Local client-side indexes over Server-managed regex indexes.

Rationale: Local indexes avoid file sync, network latency, and privacy/security risks for constant agent operations.

How to minimize editor memory.

Chose Two files with only the lookup table mmap'd over Loading full index data into the editor process.

Rationale: Posting lists stay on disk while the compact hash/offset table supports fast binary search.

Gotchas (what bit them)

Semantic indexes do not replace regex search for agents.

Root cause: Some questions require exact text or regex lookup rather than semantic nearest-neighbor retrieval.

Resolution: Build a dedicated regex index alongside semantic context systems.

Trigram and bloom-filter indexes have scaling and update pathologies.

Root cause: Posting lists can be too broad or bloom filters can saturate under updates.

Resolution: Use sparse n-grams and deterministic weighting as a middle ground.

Stale regex indexes waste agent tokens.

Root cause: If the agent searches for specific text it just wrote and does not find it, it may chase the wrong path.

Resolution: Keep a fast local Git-based update layer for user and agent changes.

Evaluation

Cursor evaluates the index through agent workflow traces comparing normal grep and instant grep, especially in large Enterprise repositories and bug-investigation workflows.

Metrics: rg invocations over 15 seconds · Normal Grep versus Instant Grep timeline segments · Time saved in bug investigations · Candidate-document reduction · Memory footprint through mmap-only lookup table

Outcomes

• Cursor created local sparse n-gram regex indexes for agent search.
• The approach reduces grep latency bottlenecks in large enterprise repositories.
• Agent bug-investigation workflows become more iterative because search time is removed or reduced.
• The design keeps privacy-sensitive code search local to the user's machine.

The strongest reported impact is in large Enterprise monorepos where rg can exceed 15 seconds and grep latency scales with codebase size.