"""Toy coarse-to-fine key search (NOT the LSA implementation).
Compares brute-force top-k over all keys with a 2-level cluster search."""
import numpy as np
rng = np.random.default_rng(0)
T, d, k = 65_536, 32, 64
# keys drawn around 256 semantic "topics", then unit-normalised
topics = rng.normal(size=(256, d))
keys = topics[rng.integers(0, 256, T)] + 0.3 * rng.normal(size=(T, d))
keys /= np.linalg.norm(keys, axis=1, keepdims=True)

def kmeans(x, m, iters=8):
    c = x[rng.choice(len(x), m, replace=False)]
    for _ in range(iters):
        a = np.argmax(x @ c.T, axis=1)
        for j in range(m):
            pts = x[a == j]
            if len(pts):
                c[j] = pts.sum(0) / np.linalg.norm(pts.sum(0))
    return c, np.argmax(x @ c.T, axis=1)

# level 0: buckets of ~64 keys; level 1: groups of buckets
b_cent, b_of_key = kmeans(keys, T // 64)
g_cent, g_of_bucket = kmeans(b_cent, 32)

def search(q, beam_groups=4, beam_buckets=8):
    scored = len(g_cent)
    groups = np.argsort(-(g_cent @ q))[:beam_groups]
    cand = np.flatnonzero(np.isin(g_of_bucket, groups))
    scored += len(cand)
    buckets = cand[np.argsort(-(b_cent[cand] @ q))[:beam_buckets]]
    idx = np.flatnonzero(np.isin(b_of_key, buckets))
    scored += len(idx)
    return idx[np.argsort(-(keys[idx] @ q))[:k]], scored

recalls, costs = [], []
for _ in range(50):
    q = keys[rng.integers(T)] + 0.2 * rng.normal(size=d); q /= np.linalg.norm(q)
    exact = set(np.argsort(-(keys @ q))[:k])
    got, scored = search(q)
    recalls.append(len(exact & set(got)) / k); costs.append(scored)
print(f"keys={T}  brute-force scores per query={T}")
print(f"coarse-to-fine scores per query≈{np.mean(costs):.0f} ({np.mean(costs)/T:.1%}), top-{k} recall={np.mean(recalls):.2f}")
