# 3. Method-level n-gram clustering before inference

**Date:** 2026-07-03

**Status:** Accepted

## Context

The BEX ensemble (CRX, iDRegEx, kORE) infers grammars from sets of symbol sequences. When we run inference on *all methods in a codebase*, the sequences are too diverse — each file has different conventions, and the ensemble produces only a flat vocabulary bag like `(any+assertEquals+assertTrue+every+listOf+verify)+`.

This doesn't capture the *ordering* of calls or the distinct methodological styles present in the codebase.

## Decision

Group methods by shared n-gram (default: 3-gram) call patterns *before* running inference.

Pipeline: `preprocess_by_method` → `frequency_filter` → `cluster_methods` → per-cluster `infer_ensemble`

The clustering algorithm:
1. Extract call tokens from each method sequence (filter to `function`, `reference.call`, `reference.class` captures).
2. Build an n-gram index: for each method, for each sliding window of size N, record the n-gram.
3. Sort n-grams by frequency (most shared first).
4. Assign each method to the largest matching cluster, then remove assigned methods.
5. Remaining unclustered methods go to `(other)`.

This produces 10-30 clusters for a typical test suite, each with 3-100+ methods sharing a call-order pattern.

## Consequences

**Positive:**
- iDRegEx and kOREInference now produce ordered grammars (e.g. `every+.assertEquals.verify+.any?`) because small, focused clusters have enough signal.
- Each cluster reveals a distinct *methodological style* in the codebase (mockist TDD vs data-driven testing vs pure assertion).
- The `(other)` cluster still captures the full vocabulary bag for diverse methods.

**Negative:**
- Clustering adds a hyperparameter (`ngram_size`, default 3). Wrong value can produce too many tiny clusters or one giant cluster.
- `min_cluster_size` (default 3) filters out tiny but potentially interesting patterns.
- Methods in `(other)` never get ordered grammar inference — just vocabulary.

## Alternatives Considered

- **Infer on all methods (no clustering)**: Produces flat vocabulary only. CRX works at 100% coverage, but iDRegEx and kORE fail on diverse inputs.
- **Infer per file**: Too fine-grained — most files have 1-5 methods, not enough for inference.
- **Infer per directory**: Better, but directories mix unrelated conventions (setup/teardown vs actual test logic).