HNSW: Multi-Layer Graph Search

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.11%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22marimo%22%2C%0A%23%20%20%20%20%20%22numpy%3D%3D2.4.3%22%2C%0A%23%20%20%20%20%20%22matplotlib%3D%3D3.10.3%22%2C%0A%23%20%5D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.22.5%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22%2C%20app_title%3D%22HNSW%3A%20Multi-Layer%20Graph%20Search%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20How%20HNSW%20Builds%20and%20Searches%20a%20Multi-Layer%20Graph%0A%0A%20%20%20%20**Hierarchical%20Navigable%20Small%20Worlds**%20(HNSW)%20is%20the%20dominant%20index%20for%20approximate%0A%20%20%20%20nearest-neighbour%20search.%20The%20core%20idea%3A%20take%20a%20**proximity%20graph**%20(where%20each%20node%0A%20%20%20%20connects%20to%20its%20nearest%20neighbours)%20and%20overlay%20it%20with%20a%20**skip-list%20structure**%20--%0A%20%20%20%20a%20hierarchy%20of%20increasingly%20sparse%20layers.%0A%0A%20%20%20%20-%20**Layer%200**%20contains%20every%20point%20with%20short%2C%20local%20connections.%0A%20%20%20%20-%20**Higher%20layers**%20contain%20fewer%20and%20fewer%20points%2C%20but%20their%20connections%20span%20longer%20distances.%0A%20%20%20%20-%20**Search**%20starts%20at%20the%20top%20layer%20(few%20nodes%2C%20big%20jumps)%20and%20greedily%20descends%2C%0A%20%20%20%20%20%20refining%20at%20each%20layer%20until%20it%20reaches%20the%20dense%20bottom.%0A%0A%20%20%20%20The%20result%3A%20%24O(%5Clog%20N)%24%20search%20time%20instead%20of%20%24O(N)%24%20brute%20force.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Parameters%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20M_slider%20%3D%20mo.ui.slider(2%2C%2032%2C%20value%3D8%2C%20step%3D1%2C%20label%3D%22M%20(max%20connections%20per%20node)%22%2C%20show_value%3DTrue)%0A%20%20%20%20N_slider%20%3D%20mo.ui.slider(20%2C%20500%2C%20value%3D100%2C%20step%3D10%2C%20label%3D%22N%20(number%20of%20points)%22%2C%20show_value%3DTrue)%0A%20%20%20%20efSearch_slider%20%3D%20mo.ui.slider(1%2C%2050%2C%20value%3D10%2C%20step%3D1%2C%20label%3D%22efSearch%20(beam%20width)%22%2C%20show_value%3DTrue)%0A%0A%20%20%20%20mo.hstack(%0A%20%20%20%20%20%20%20%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.vstack(%5BM_slider%2C%20N_slider%5D)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20mo.vstack(%5BefSearch_slider%5D)%2C%0A%20%20%20%20%20%20%20%20%5D%2C%0A%20%20%20%20%20%20%20%20gap%3D2%2C%0A%20%20%20%20)%0A%20%20%20%20return%20M_slider%2C%20N_slider%2C%20efSearch_slider%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Section%201%3A%20Layer%20Assignment%0A%0A%20%20%20%20Each%20inserted%20point%20is%20assigned%20a%20random%20layer%20using%3A%0A%0A%20%20%20%20%24%24%5Cell%20%3D%20%5Clfloor%20-%5Cln(u)%20%2F%20%5Cln(M)%20%5Crfloor%24%24%0A%0A%20%20%20%20where%20%24u%20%5Csim%20%5Ctext%7BUniform%7D(0%2C%201)%24.%20This%20gives%20an%20exponentially%20decaying%20distribution%3A%0A%20%20%20%20most%20points%20live%20only%20on%20layer%200%2C%20a%20few%20reach%20layer%201%2C%20even%20fewer%20reach%20layer%202%2C%20and%20so%20on%20--%0A%20%20%20%20exactly%20like%20a%20skip%20list.%0A%0A%20%20%20%20The%20bar%20chart%20below%20simulates%20100%2C000%20insertions.%20Notice%20how%20changing%20**M**%20shifts%20the%0A%20%20%20%20distribution%3A%20higher%20M%20means%20each%20layer%20retains%20a%20smaller%20fraction%2C%20so%20fewer%20layers%20are%20needed.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(M_slider%2C%20mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20_M%20%3D%20M_slider.value%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(42)%0A%20%20%20%20_u%20%3D%20_rng.uniform(0%2C%201%2C%20size%3D100_000)%0A%20%20%20%20_u%20%3D%20np.clip(_u%2C%201e-15%2C%201.0)%0A%20%20%20%20_layers%20%3D%20np.floor(-np.log(_u)%20%2F%20np.log(_M)).astype(int)%0A%20%20%20%20_max_layer%20%3D%20int(_layers.max())%0A%0A%20%20%20%20_counts%20%3D%20np.bincount(_layers%2C%20minlength%3D_max_layer%20%2B%201)%0A%20%20%20%20_pcts%20%3D%20_counts%20%2F%20_counts.sum()%20*%20100%0A%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(10%2C%205))%0A%20%20%20%20_bars%20%3D%20_ax.bar(range(len(_counts))%2C%20_pcts%2C%20color%3D%22steelblue%22%2C%20edgecolor%3D%22white%22%2C%20linewidth%3D0.5)%0A%0A%20%20%20%20for%20_i%2C%20(_bar%2C%20_pct)%20in%20enumerate(zip(_bars%2C%20_pcts))%3A%0A%20%20%20%20%20%20%20%20if%20_pct%20%3E%3D%200.1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.text(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_bar.get_x()%20%2B%20_bar.get_width()%20%2F%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_bar.get_height()%20%2B%200.5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%7B_pct%3A.1f%7D%25%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22bottom%22%2C%20fontsize%3D9%2C%20color%3D%22white%22%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20%23%20annotate%20layer%200%0A%20%20%20%20_ax.annotate(%0A%20%20%20%20%20%20%20%20f%22%7B_pcts%5B0%5D%3A.0f%7D%25%20on%20layer%200%20only%22%2C%0A%20%20%20%20%20%20%20%20xy%3D(0%2C%20_pcts%5B0%5D)%2C%0A%20%20%20%20%20%20%20%20xytext%3D(2.5%2C%20_pcts%5B0%5D%20-%2010)%2C%0A%20%20%20%20%20%20%20%20fontsize%3D11%2C%20color%3D%22cyan%22%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20arrowprops%3Ddict(arrowstyle%3D%22-%3E%22%2C%20color%3D%22cyan%22%2C%20lw%3D1.5)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20annotate%20highest%20layers%0A%20%20%20%20_high_pct%20%3D%20_pcts%5B4%3A%5D.sum()%20if%20len(_pcts)%20%3E%204%20else%200%0A%20%20%20%20if%20_high_pct%20%3E%200%20and%20_max_layer%20%3E%3D%204%3A%0A%20%20%20%20%20%20%20%20_ax.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20f%22%7B_high_pct%3A.1f%7D%25%20reach%20layer%204%2B%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xy%3D(4%2C%20_pcts%5B4%5D%20if%20len(_pcts)%20%3E%204%20else%200)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(min(6%2C%20_max_layer)%2C%20max(_pcts%5B1%3A%5D)%20*%200.7)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D11%2C%20color%3D%22tomato%22%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20arrowprops%3Ddict(arrowstyle%3D%22-%3E%22%2C%20color%3D%22tomato%22%2C%20lw%3D1.5)%2C%0A%20%20%20%20%20%20%20%20)%0A%0A%20%20%20%20_ax.set_xlabel(%22Layer%22%2C%20color%3D%22gray%22%2C%20fontsize%3D12)%0A%20%20%20%20_ax.set_ylabel(%22%25%20of%20100k%20insertions%22%2C%20color%3D%22gray%22%2C%20fontsize%3D12)%0A%20%20%20%20_ax.set_title(%0A%20%20%20%20%20%20%20%20f%22Layer%20distribution%20%20(M%20%3D%20%7B_M%7D%2C%20%20max%20layer%20reached%20%3D%20%7B_max_layer%7D)%22%2C%0A%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20fontsize%3D13%2C%20pad%3D12%2C%0A%20%20%20%20)%0A%20%20%20%20_ax.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_fig.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_ax.tick_params(colors%3D%22gray%22)%0A%20%20%20%20for%20_sp%20in%20_ax.spines.values()%3A%0A%20%20%20%20%20%20%20%20_sp.set_color(%22gray%22)%0A%20%20%20%20plt.tight_layout()%0A%20%20%20%20mo.as_html(_fig)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Section%202%3A%20Multi-Layer%20Graph%20Construction%0A%0A%20%20%20%20Below%20we%20generate%20**N**%20random%202D%20points%2C%20assign%20each%20a%20layer%20using%20the%20formula%20above%2C%0A%20%20%20%20then%20connect%20each%20point%20to%20its%20**M**%20nearest%20neighbours%20at%20each%20layer%20it%20belongs%20to.%0A%0A%20%20%20%20The%20result%20is%20a%20skip-list-like%20overlay%20on%20a%20proximity%20graph%3A%0A%0A%20%20%20%20-%20**Gray%20thin%20lines**%3A%20layer%200%20connections%20(all%20points%2C%20short%20hops)%0A%20%20%20%20-%20**Blue%20medium%20lines**%3A%20layer%201%20connections%20(subset%2C%20medium%20reach)%0A%20%20%20%20-%20**Orange%20thick%20lines**%3A%20layer%202%2B%20connections%20(few%20points%2C%20long-range%20highways)%0A%0A%20%20%20%20The%20red%20star%20marks%20the%20**entry%20point**%20--%20the%20node%20on%20the%20highest%20layer%20where%20every%20search%20begins.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(M_slider%2C%20N_slider%2C%20np)%3A%0A%20%20%20%20_M%20%3D%20M_slider.value%0A%20%20%20%20_N%20%3D%20N_slider.value%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(7)%0A%0A%20%20%20%20points%20%3D%20_rng.uniform(0%2C%2010%2C%20size%3D(_N%2C%202))%0A%0A%20%20%20%20_u%20%3D%20_rng.uniform(0%2C%201%2C%20size%3D_N)%0A%20%20%20%20_u%20%3D%20np.clip(_u%2C%201e-15%2C%201.0)%0A%20%20%20%20node_layers%20%3D%20np.floor(-np.log(_u)%20%2F%20np.log(_M)).astype(int)%0A%0A%20%20%20%20max_layer%20%3D%20int(node_layers.max())%0A%0A%20%20%20%20%23%20build%20adjacency%20per%20layer%3A%20for%20each%20layer%2C%20connect%20each%20node%20to%20M%20nearest%20at%20that%20layer%0A%20%20%20%20graph%20%3D%20%7Blayer%3A%20%7B%7D%20for%20layer%20in%20range(max_layer%20%2B%201)%7D%0A%20%20%20%20for%20_layer%20in%20range(max_layer%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20_members%20%3D%20np.where(node_layers%20%3E%3D%20_layer)%5B0%5D%0A%20%20%20%20%20%20%20%20if%20len(_members)%20%3C%202%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20continue%0A%20%20%20%20%20%20%20%20_pts%20%3D%20points%5B_members%5D%0A%20%20%20%20%20%20%20%20for%20_idx_local%2C%20_global_idx%20in%20enumerate(_members)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_dists%20%3D%20np.linalg.norm(_pts%20-%20_pts%5B_idx_local%5D%2C%20axis%3D1)%0A%20%20%20%20%20%20%20%20%20%20%20%20_dists%5B_idx_local%5D%20%3D%20np.inf%0A%20%20%20%20%20%20%20%20%20%20%20%20_k%20%3D%20min(_M%2C%20len(_members)%20-%201)%0A%20%20%20%20%20%20%20%20%20%20%20%20_neighbours%20%3D%20_members%5Bnp.argsort(_dists)%5B%3A_k%5D%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20graph%5B_layer%5D%5Bint(_global_idx)%5D%20%3D%20%5Bint(n)%20for%20n%20in%20_neighbours%5D%0A%0A%20%20%20%20%23%20entry%20point%3A%20node%20on%20the%20highest%20layer%0A%20%20%20%20_top_nodes%20%3D%20np.where(node_layers%20%3D%3D%20max_layer)%5B0%5D%0A%20%20%20%20entry_point%20%3D%20int(_top_nodes%5B0%5D)%0A%20%20%20%20return%20entry_point%2C%20graph%2C%20max_layer%2C%20node_layers%2C%20points%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo%2C%20np%2C%20plt)%3A%0A%20%20%20%20%23%20Skip-list%20diagram%20with%20a%20small%20fixed%20example%20(16%20nodes)%20so%20every%20node%0A%20%20%20%20%23%20is%20individually%20visible.%20%20Uses%20the%20same%20layer-assignment%20formula.%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(42)%0A%20%20%20%20_N_small%20%3D%2016%0A%20%20%20%20_M_small%20%3D%204%20%20%20%23%20low%20M%20%E2%86%92%20more%20layers%20for%20variety%0A%20%20%20%20_u%20%3D%20np.clip(_rng.uniform(0%2C%201%2C%20_N_small)%2C%201e-15%2C%201.0)%0A%20%20%20%20_sl_layers%20%3D%20np.floor(-np.log(_u)%20%2F%20np.log(_M_small)).astype(int)%0A%20%20%20%20_sl_max%20%3D%20int(_sl_layers.max())%0A%20%20%20%20_n_layers%20%3D%20_sl_max%20%2B%201%0A%0A%20%20%20%20%23%20x%20positions%3A%20evenly%20spaced%0A%20%20%20%20_xs%20%3D%20np.arange(_N_small%2C%20dtype%3Dfloat)%0A%0A%20%20%20%20_layer_colors%20%3D%20%5B%22%23555555%22%2C%20%22%234a90d9%22%2C%20%22%23e8873a%22%2C%20%22%23e05555%22%2C%20%22%23c040c0%22%5D%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(14%2C%20max(3.5%2C%20_n_layers%20*%201.6)))%0A%0A%20%20%20%20%23%20vertical%20poles%20(each%20node%20is%20a%20column%20spanning%20its%20layers)%0A%20%20%20%20for%20_i%2C%20_ml%20in%20enumerate(_sl_layers)%3A%0A%20%20%20%20%20%20%20%20_ax.plot(%5B_xs%5B_i%5D%2C%20_xs%5B_i%5D%5D%2C%20%5B-0.15%2C%20_ml%20%2B%200.15%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%23333355%22%2C%20lw%3D1.5%2C%20alpha%3D0.7%2C%20zorder%3D1)%0A%0A%20%20%20%20%23%20horizontal%20edges%20within%20each%20layer%20(connect%20consecutive%20members)%0A%20%20%20%20for%20_l%20in%20range(_n_layers)%3A%0A%20%20%20%20%20%20%20%20_members%20%3D%20%5B_i%20for%20_i%20in%20range(_N_small)%20if%20_sl_layers%5B_i%5D%20%3E%3D%20_l%5D%0A%20%20%20%20%20%20%20%20_c%20%3D%20_layer_colors%5Bmin(_l%2C%20len(_layer_colors)%20-%201)%5D%0A%20%20%20%20%20%20%20%20for%20_a%2C%20_b%20in%20zip(_members%2C%20_members%5B1%3A%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.plot(%5B_xs%5B_a%5D%2C%20_xs%5B_b%5D%5D%2C%20%5B_l%2C%20_l%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D_c%2C%20lw%3D2%20%2B%20_l%20*%200.5%2C%20alpha%3D0.8%2C%20zorder%3D2)%0A%0A%20%20%20%20%23%20nodes%3A%20one%20dot%20per%20(node%2C%20layer)%20they%20participate%20in%0A%20%20%20%20for%20_i%2C%20_ml%20in%20enumerate(_sl_layers)%3A%0A%20%20%20%20%20%20%20%20for%20_l%20in%20range(_ml%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_c%20%3D%20_layer_colors%5Bmin(_l%2C%20len(_layer_colors)%20-%201)%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.plot(_xs%5B_i%5D%2C%20_l%2C%20%22o%22%2C%20color%3D_c%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20markersize%3D10%20%2B%20_l%20*%202%2C%20zorder%3D3)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.text(_xs%5B_i%5D%2C%20_l%2C%20str(_i)%2C%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D6%2C%20color%3D%22white%22%2C%20fontweight%3D%22bold%22%2C%20zorder%3D4)%0A%0A%20%20%20%20%23%20entry%20point%20star%0A%20%20%20%20_ep%20%3D%20int(np.where(_sl_layers%20%3D%3D%20_sl_max)%5B0%5D%5B0%5D)%0A%20%20%20%20_ax.plot(_xs%5B_ep%5D%2C%20_sl_max%2C%20%22*%22%2C%20color%3D%22red%22%2C%20markersize%3D22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D5%2C%20label%3Df%22Entry%20point%20(node%20%7B_ep%7D)%22)%0A%0A%20%20%20%20%23%20layer%20labels%20on%20left%0A%20%20%20%20_ax.set_yticks(range(_n_layers))%0A%20%20%20%20_ax.set_yticklabels(%0A%20%20%20%20%20%20%20%20%5Bf%22Layer%20%7B_l%7D%20%20%E2%80%94%20%7Bsum(_sl_layers%20%3E%3D%20_l)%7D%20nodes%22%20for%20_l%20in%20range(_n_layers)%5D%2C%0A%20%20%20%20%20%20%20%20color%3D%22gray%22%2C%20fontsize%3D10%2C%0A%20%20%20%20)%0A%20%20%20%20_ax.set_xticks(%5B%5D)%0A%20%20%20%20_ax.set_xlim(-0.8%2C%20_N_small%20-%200.2)%0A%20%20%20%20_ax.set_ylim(-0.5%2C%20_sl_max%20%2B%200.6)%0A%20%20%20%20_ax.legend(loc%3D%22upper%20right%22%2C%20fontsize%3D9%2C%20framealpha%3D0.7)%0A%20%20%20%20_ax.set_title(%0A%20%20%20%20%20%20%20%20f%22HNSW%20skip-list%20structure%20%E2%80%94%20%7B_N_small%7D%20nodes%2C%20%7B_n_layers%7D%20layers%5Cn%22%0A%20%20%20%20%20%20%20%20f%22Each%20node%20column%20spans%20all%20layers%20it%20belongs%20to.%20%20%22%0A%20%20%20%20%20%20%20%20f%22Layer%200%20(bottom)%20has%20every%20node%3B%20each%20higher%20layer%20is%20~1%2FM%20as%20dense.%22%2C%0A%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20fontsize%3D12%2C%20pad%3D10%2C%0A%20%20%20%20)%0A%20%20%20%20_ax.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_fig.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_ax.tick_params(colors%3D%22gray%22)%0A%20%20%20%20for%20_sp%20in%20_ax.spines.values()%3A%0A%20%20%20%20%20%20%20%20_sp.set_color(%22gray%22)%0A%20%20%20%20plt.tight_layout()%0A%20%20%20%20mo.as_html(_fig)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Section%203%3A%20Search%20Visualization%0A%0A%20%20%20%20Pick%20a%20query%20point%20with%20the%20sliders%20below.%20The%20search%20proceeds%20as%20follows%3A%0A%0A%20%20%20%201.%20Start%20at%20the%20**entry%20point**%20(red%20star)%20on%20the%20highest%20layer.%0A%20%20%20%202.%20**Greedy%20walk**%20on%20each%20layer%3A%20repeatedly%20move%20to%20the%20neighbour%20closest%20to%20the%20query%2C%0A%20%20%20%20%20%20%20until%20no%20neighbour%20is%20closer%20than%20the%20current%20node.%0A%20%20%20%203.%20**Drop%20down**%20to%20the%20next%20layer%20and%20repeat.%0A%20%20%20%204.%20At%20**layer%200**%2C%20run%20a%20beam%20search%20with%20width%20%3D%20efSearch.%0A%0A%20%20%20%20The%20diagram%20shows%20the%20full%20path%3A%20**yellow**%20%3D%20visited%20nodes%2C%20**blue**%20%3D%20beam%20candidates%20at%20layer%200%2C%0A%20%20%20%20**green**%20%3D%20final%20nearest%20neighbour.%20Arrows%20trace%20the%20greedy%20hops.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20qx_slider%20%3D%20mo.ui.slider(0.0%2C%2010.0%2C%20value%3D5.0%2C%20step%3D0.1%2C%20label%3D%22Query%20x%22%2C%20show_value%3DTrue)%0A%20%20%20%20qy_slider%20%3D%20mo.ui.slider(0.0%2C%2010.0%2C%20value%3D5.0%2C%20step%3D0.1%2C%20label%3D%22Query%20y%22%2C%20show_value%3DTrue)%0A%20%20%20%20mo.hstack(%5Bqx_slider%2C%20qy_slider%5D%2C%20gap%3D2)%0A%20%20%20%20return%20qx_slider%2C%20qy_slider%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20efSearch_slider%2C%0A%20%20%20%20entry_point%2C%0A%20%20%20%20graph%2C%0A%20%20%20%20max_layer%2C%0A%20%20%20%20np%2C%0A%20%20%20%20points%2C%0A%20%20%20%20qx_slider%2C%0A%20%20%20%20qy_slider%2C%0A)%3A%0A%20%20%20%20_query%20%3D%20np.array(%5Bqx_slider.value%2C%20qy_slider.value%5D)%0A%20%20%20%20_ef%20%3D%20efSearch_slider.value%0A%0A%20%20%20%20def%20_dist(idx)%3A%0A%20%20%20%20%20%20%20%20return%20float(np.linalg.norm(points%5Bidx%5D%20-%20_query))%0A%0A%20%20%20%20%23%20greedy%20search%20on%20layers%20max_layer%20down%20to%201%0A%20%20%20%20search_path%20%3D%20%5B%5D%20%20%23%20list%20of%20(from_node%2C%20to_node%2C%20layer)%0A%20%20%20%20visited_nodes%20%3D%20set()%0A%20%20%20%20current%20%3D%20entry_point%0A%20%20%20%20visited_nodes.add(current)%0A%0A%20%20%20%20for%20_layer%20in%20range(max_layer%2C%200%2C%20-1)%3A%0A%20%20%20%20%20%20%20%20_changed%20%3D%20True%0A%20%20%20%20%20%20%20%20while%20_changed%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_changed%20%3D%20False%0A%20%20%20%20%20%20%20%20%20%20%20%20_cur_dist%20%3D%20_dist(current)%0A%20%20%20%20%20%20%20%20%20%20%20%20_nbrs%20%3D%20graph%5B_layer%5D.get(current%2C%20%5B%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_nb%20in%20_nbrs%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_dist(_nb)%20%3C%20_cur_dist%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20search_path.append((current%2C%20_nb%2C%20_layer))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20visited_nodes.add(_nb)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20current%20%3D%20_nb%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_cur_dist%20%3D%20_dist(current)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_changed%20%3D%20True%0A%0A%20%20%20%20%23%20beam%20search%20on%20layer%200%0A%20%20%20%20beam%20%3D%20%5Bcurrent%5D%0A%20%20%20%20beam_visited%20%3D%20%7Bcurrent%7D%0A%20%20%20%20beam_candidates%20%3D%20set()%0A%20%20%20%20beam_candidates.add(current)%0A%0A%20%20%20%20for%20_%20in%20range(_ef%20*%205)%3A%0A%20%20%20%20%20%20%20%20_best%20%3D%20None%0A%20%20%20%20%20%20%20%20_best_dist%20%3D%20np.inf%0A%20%20%20%20%20%20%20%20for%20_node%20in%20list(beam)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_nb%20in%20graph%5B0%5D.get(_node%2C%20%5B%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_nb%20not%20in%20beam_visited%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_d%20%3D%20_dist(_nb)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_d%20%3C%20_best_dist%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_best%20%3D%20_nb%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_best_dist%20%3D%20_d%0A%20%20%20%20%20%20%20%20if%20_best%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20beam_visited.add(_best)%0A%20%20%20%20%20%20%20%20beam_candidates.add(_best)%0A%20%20%20%20%20%20%20%20visited_nodes.add(_best)%0A%20%20%20%20%20%20%20%20beam.append(_best)%0A%20%20%20%20%20%20%20%20beam%20%3D%20sorted(beam%2C%20key%3D_dist)%5B%3A_ef%5D%0A%0A%20%20%20%20%23%20search%20path%20on%20layer%200%3A%20trace%20from%20entry%20to%20best%0A%20%20%20%20for%20_i%20in%20range(len(beam)%20-%201)%3A%0A%20%20%20%20%20%20%20%20search_path.append((beam%5B_i%5D%2C%20beam%5B_i%20%2B%201%5D%2C%200))%0A%0A%20%20%20%20result_node%20%3D%20beam%5B0%5D%0A%20%20%20%20total_visited%20%3D%20len(visited_nodes)%0A%20%20%20%20return%20beam_candidates%2C%20result_node%2C%20search_path%2C%20total_visited%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(%0A%20%20%20%20beam_candidates%2C%0A%20%20%20%20entry_point%2C%0A%20%20%20%20max_layer%2C%0A%20%20%20%20mo%2C%0A%20%20%20%20node_layers%2C%0A%20%20%20%20np%2C%0A%20%20%20%20plt%2C%0A%20%20%20%20points%2C%0A%20%20%20%20qx_slider%2C%0A%20%20%20%20qy_slider%2C%0A%20%20%20%20result_node%2C%0A%20%20%20%20search_path%2C%0A%20%20%20%20total_visited%2C%0A)%3A%0A%20%20%20%20_query%20%3D%20np.array(%5Bqx_slider.value%2C%20qy_slider.value%5D)%0A%0A%20%20%20%20%23%20%E2%94%80%E2%94%80%20colour%20palette%3A%20one%20colour%20per%20layer%20%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%0A%20%20%20%20_layer_colors%20%3D%20%5B%22%234a90d9%22%2C%20%22%23e8873a%22%2C%20%22%23e05555%22%2C%20%22%23c040c0%22%2C%20%22%2340c0a0%22%5D%0A%20%20%20%20def%20_lc(layer)%3A%0A%20%20%20%20%20%20%20%20return%20_layer_colors%5Bmin(layer%2C%20len(_layer_colors)%20-%201)%5D%0A%0A%20%20%20%20%23%20%E2%94%80%E2%94%80%20sequential%20colour%20gradient%20for%20hop%20order%20(purple%20%E2%86%92%20yellow)%20%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%0A%20%20%20%20_cmap%20%3D%20plt.colormaps%5B%22plasma%22%5D%0A%20%20%20%20_n_hops%20%3D%20max(len(search_path)%2C%201)%0A%0A%20%20%20%20%23%20%E2%94%80%E2%94%80%20Figure%3A%20layer-descent%20diagram%20only%20%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%0A%20%20%20%20_fig%2C%20_ax%20%3D%20plt.subplots(figsize%3D(13%2C%20max(5%2C%20(max_layer%20%2B%201)%20*%202.2)))%0A%0A%20%20%20%20%23%20background%3A%20all%20nodes%20at%20each%20layer%2C%20very%20faint%0A%20%20%20%20for%20_i%2C%20_ml%20in%20enumerate(node_layers)%3A%0A%20%20%20%20%20%20%20%20for%20_l%20in%20range(_ml%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.plot(points%5B_i%2C%200%5D%2C%20_l%2C%20%22o%22%2C%20color%3D%22%232a2a4a%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20markersize%3D5%2C%20zorder%3D1)%0A%20%20%20%20%20%20%20%20if%20_ml%20%3E%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.plot(%5Bpoints%5B_i%2C%200%5D%5D%20*%202%2C%20%5B0%2C%20_ml%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22%23222240%22%2C%20lw%3D0.4%2C%20alpha%3D0.6%2C%20zorder%3D1)%0A%0A%20%20%20%20%23%20horizontal%20%22floor%22%20lines%20per%20layer%20showing%20how%20many%20nodes%20live%20there%0A%20%20%20%20for%20_l%20in%20range(max_layer%20%2B%201)%3A%0A%20%20%20%20%20%20%20%20_ax.axhline(_l%2C%20color%3D%22%23333355%22%2C%20lw%3D0.5%2C%20alpha%3D0.4%2C%20zorder%3D0)%0A%0A%20%20%20%20%23%20%E2%94%80%E2%94%80%20Greedy%20hops%20(layers%20%3E%200)%3A%20numbered%20arrows%20%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%0A%20%20%20%20_greedy_hops%20%3D%20%5B(f%2C%20t%2C%20l)%20for%20f%2C%20t%2C%20l%20in%20search_path%20if%20l%20%3E%200%5D%0A%20%20%20%20_step_log%20%3D%20%5B%5D%0A%20%20%20%20_step%20%3D%201%0A%20%20%20%20_cur_layer%20%3D%20max_layer%0A%0A%20%20%20%20_ax.plot(points%5Bentry_point%2C%200%5D%2C%20max_layer%2C%20%22*%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22red%22%2C%20markersize%3D22%2C%20zorder%3D10%2C%20label%3D%22Start%20(entry%20point)%22)%0A%0A%20%20%20%20for%20_hop_idx%2C%20(_from%2C%20_to%2C%20_layer)%20in%20enumerate(_greedy_hops)%3A%0A%20%20%20%20%20%20%20%20_hop_color%20%3D%20_cmap(_hop_idx%20%2F%20max(_n_hops%2C%201))%0A%0A%20%20%20%20%20%20%20%20%23%20descent%20drop%20when%20layer%20changes%0A%20%20%20%20%20%20%20%20if%20_layer%20%3C%20_cur_layer%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%22%2C%20xy%3D(points%5B_from%2C%200%5D%2C%20_layer)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(points%5B_from%2C%200%5D%2C%20_cur_layer)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrowprops%3Ddict(arrowstyle%3D%22-%7C%3E%22%2C%20color%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20lw%3D1.4%2C%20alpha%3D0.5%2C%20linestyle%3D%22dotted%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D7%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20_ax.text(points%5B_from%2C%200%5D%20%2B%200.18%2C%20(_cur_layer%20%2B%20_layer)%20%2F%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%E2%86%93%20L%7B_cur_layer%7D%E2%86%92%7B_layer%7D%22%2C%20fontsize%3D7.5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20alpha%3D0.75%2C%20va%3D%22center%22)%0A%20%20%20%20%20%20%20%20%20%20%20%20_cur_layer%20%3D%20_layer%0A%0A%20%20%20%20%20%20%20%20%23%20hop%20arrow%0A%20%20%20%20%20%20%20%20_ax.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%2C%20xy%3D(points%5B_to%2C%200%5D%2C%20_layer)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(points%5B_from%2C%200%5D%2C%20_layer)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20arrowprops%3Ddict(arrowstyle%3D%22-%7C%3E%22%2C%20color%3D_hop_color%2C%20lw%3D2.2%2C%20alpha%3D0.95)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D8%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%23%20step%20number%20at%20midpoint%0A%20%20%20%20%20%20%20%20_mx%20%3D%20(points%5B_from%2C%200%5D%20%2B%20points%5B_to%2C%200%5D)%20%2F%202%0A%20%20%20%20%20%20%20%20_ax.text(_mx%2C%20_layer%20%2B%200.1%2C%20str(_step)%2C%20fontsize%3D8%2C%20color%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22bottom%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.15%22%2C%20fc%3D%22%231a1a2e%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20ec%3D_hop_color%2C%20alpha%3D0.9%2C%20linewidth%3D1)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D9)%0A%20%20%20%20%20%20%20%20_d%20%3D%20float(np.linalg.norm(points%5B_to%5D%20-%20_query))%0A%20%20%20%20%20%20%20%20_step_log.append((_step%2C%20_layer%2C%20f%22Greedy%20hop%20%20%7B_from%7D%20%E2%86%92%20%7B_to%7D%20%20(d%3D%7B_d%3A.2f%7D)%22))%0A%20%20%20%20%20%20%20%20_step%20%2B%3D%201%0A%0A%20%20%20%20%23%20final%20descent%20to%20layer%200%0A%20%20%20%20if%20_cur_layer%20%3E%200%3A%0A%20%20%20%20%20%20%20%20_entry_l0%20%3D%20_greedy_hops%5B-1%5D%5B1%5D%20if%20_greedy_hops%20else%20max_layer%0A%20%20%20%20%20%20%20%20_last_node%20%3D%20_greedy_hops%5B-1%5D%5B1%5D%20if%20_greedy_hops%20else%20entry_point%0A%20%20%20%20%20%20%20%20_last_node%20%3D%20next(%0A%20%20%20%20%20%20%20%20%20%20%20%20(t%20for%20f%2C%20t%2C%20l%20in%20reversed(_greedy_hops))%2C%20entry_point%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_ax.annotate(%0A%20%20%20%20%20%20%20%20%20%20%20%20%22%22%2C%20xy%3D(points%5B_last_node%2C%200%5D%2C%200)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xytext%3D(points%5B_last_node%2C%200%5D%2C%20_cur_layer)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20arrowprops%3Ddict(arrowstyle%3D%22-%7C%3E%22%2C%20color%3D%22white%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20lw%3D1.4%2C%20alpha%3D0.5%2C%20linestyle%3D%22dotted%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20zorder%3D7%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20_ax.text(points%5B_last_node%2C%200%5D%20%2B%200.18%2C%20_cur_layer%20%2F%202%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%E2%86%93%20L%7B_cur_layer%7D%E2%86%920%22%2C%20fontsize%3D7.5%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20alpha%3D0.75%2C%20va%3D%22center%22)%0A%20%20%20%20%20%20%20%20_step_log.append((_step%2C%200%2C%20f%22Descend%20to%20layer%200%2C%20start%20beam%20search%22))%0A%20%20%20%20%20%20%20%20_step%20%2B%3D%201%0A%0A%20%20%20%20%23%20%E2%94%80%E2%94%80%20Layer%200%3A%20beam%20search%20%E2%80%94%20show%20explored%20cluster%2C%20no%20fake%20path%20%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%E2%94%80%0A%20%20%20%20_beam_nodes%20%3D%20list(beam_candidates%20-%20%7Bresult_node%7D)%0A%20%20%20%20_greedy_visited%20%3D%20%7Bf%20for%20f%2C%20t%2C%20l%20in%20_greedy_hops%7D%20%7C%20%7Bt%20for%20f%2C%20t%2C%20l%20in%20_greedy_hops%7D%0A%20%20%20%20_upper_only%20%3D%20list(_greedy_visited%20-%20beam_candidates%20-%20%7Bresult_node%2C%20entry_point%7D)%0A%0A%20%20%20%20if%20_upper_only%3A%0A%20%20%20%20%20%20%20%20_upper_y%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20next((l%20for%20f%2C%20t%2C%20l%20in%20_greedy_hops%20if%20t%20%3D%3D%20n%20or%20f%20%3D%3D%20n)%2C%20max_layer)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20n%20in%20_upper_only%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20%20%20%20%20_ax.scatter(points%5B_upper_only%2C%200%5D%2C%20_upper_y%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20s%3D40%2C%20color%3D%22gold%22%2C%20alpha%3D0.7%2C%20zorder%3D6%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3D%22Greedy%20visited%22)%0A%0A%20%20%20%20if%20_beam_nodes%3A%0A%20%20%20%20%20%20%20%20_ax.scatter(points%5B_beam_nodes%2C%200%5D%2C%20%5B0%5D%20*%20len(_beam_nodes)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20s%3D60%2C%20color%3D%22dodgerblue%22%2C%20alpha%3D0.8%2C%20zorder%3D6%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3Df%22Beam%20explored%20(%7Blen(beam_candidates)%7D%20nodes)%22)%0A%0A%20%20%20%20_ax.scatter(%5Bpoints%5Bresult_node%2C%200%5D%5D%2C%20%5B0%5D%2C%20s%3D200%2C%20color%3D%22limegreen%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edgecolors%3D%22white%22%2C%20linewidths%3D1.5%2C%20zorder%3D11%2C%20marker%3D%22*%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20label%3D%22Nearest%20found%22)%0A%0A%20%20%20%20_ax.axvline(_query%5B0%5D%2C%20color%3D%22white%22%2C%20lw%3D1.2%2C%20alpha%3D0.35%2C%20ls%3D%22--%22)%0A%20%20%20%20_ax.text(_query%5B0%5D%20%2B%200.12%2C%20-0.42%2C%20f%22query%20x%3D%7B_query%5B0%5D%3A.1f%7D%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20fontsize%3D8%2C%20color%3D%22white%22%2C%20alpha%3D0.65)%0A%0A%20%20%20%20%23%20y-axis%0A%20%20%20%20_ax.set_yticks(range(max_layer%20%2B%201))%0A%20%20%20%20_ax.set_yticklabels(%0A%20%20%20%20%20%20%20%20%5Bf%22Layer%20%7Bl%7D%20%20(%7Bsum(node_layers%20%3E%3D%20l)%7D%20nodes)%22%20for%20l%20in%20range(max_layer%20%2B%201)%5D%2C%0A%20%20%20%20%20%20%20%20color%3D%22gray%22%2C%20fontsize%3D10%2C%0A%20%20%20%20)%0A%20%20%20%20_ax.set_xlim(-0.5%2C%2010.5)%0A%20%20%20%20_ax.set_ylim(-0.65%2C%20max_layer%20%2B%200.55)%0A%20%20%20%20_ax.set_xlabel(%22Node%20x-coordinate%22%2C%20color%3D%22gray%22%2C%20fontsize%3D11)%0A%20%20%20%20_ax.set_ylabel(%22Layer%20%20(bottom%20%3D%20densest)%22%2C%20color%3D%22gray%22%2C%20fontsize%3D11)%0A%20%20%20%20_ax.legend(loc%3D%22upper%20right%22%2C%20fontsize%3D9%2C%20framealpha%3D0.7)%0A%20%20%20%20_pct%20%3D%20total_visited%20%2F%20len(points)%20*%20100%0A%20%20%20%20_ax.set_title(%0A%20%20%20%20%20%20%20%20f%22HNSW%20search%20%E2%80%94%20greedy%20hops%20numbered%201%E2%80%A6%7B_step-2%7D%2C%20%22%0A%20%20%20%20%20%20%20%20f%22then%20beam%20search%20at%20layer%200%5Cn%22%0A%20%20%20%20%20%20%20%20f%22Total%20visited%3A%20%7Btotal_visited%7D%2F%7Blen(points)%7D%20nodes%20(%7B_pct%3A.1f%7D%25)%22%2C%0A%20%20%20%20%20%20%20%20color%3D%22white%22%2C%20fontsize%3D12%2C%20pad%3D10%2C%0A%20%20%20%20)%0A%20%20%20%20_ax.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_fig.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_ax.tick_params(colors%3D%22gray%22)%0A%20%20%20%20for%20_sp%20in%20_ax.spines.values()%3A%0A%20%20%20%20%20%20%20%20_sp.set_color(%22gray%22)%0A%20%20%20%20plt.tight_layout()%0A%0A%20%20%20%20%23%20step%20log%20table%0A%20%20%20%20_rows%20%3D%20%5B%22%7C%20Step%20%7C%20Layer%20%7C%20Action%20%7C%22%2C%20%22%7C-----%3A%7C------%3A%7C--------%7C%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20f%22%7C%20%20%20%20%E2%80%94%20%7C%20%20%20%7Bmax_layer%7D%20%20%20%7C%20**Start**%20at%20entry%20point%20(red%20%E2%98%85)%20%7C%22%5D%0A%20%20%20%20for%20_sn%2C%20_lyr%2C%20_desc%20in%20_step_log%3A%0A%20%20%20%20%20%20%20%20_rows.append(f%22%7C%20%7B_sn%7D%20%7C%20%7B_lyr%7D%20%7C%20%7B_desc%7D%20%7C%22)%0A%20%20%20%20_rows.append(f%22%7C%20%E2%80%94%20%7C%200%20%7C%20Beam%20search%3A%20%7Blen(beam_candidates)%7D%20nodes%20explored%20(blue)%2C%20%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%22nearest%20%3D%20green%20%E2%98%85%20%7C%22)%0A%0A%20%20%20%20mo.vstack(%5Bmo.as_html(_fig)%2C%20mo.md(%22%5Cn%22.join(_rows))%5D)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Section%204%3A%20efSearch%20vs%20Recall%0A%0A%20%20%20%20How%20does%20beam%20width%20affect%20search%20quality%3F%20For%20each%20value%20of%20efSearch%2C%20we%20run%20the%20HNSW%0A%20%20%20%20search%20for%2050%20random%20queries%20and%20measure%20**recall%4010**%20--%20the%20fraction%20of%20the%20true%2010%20nearest%0A%20%20%20%20neighbours%20that%20the%20search%20actually%20finds.%0A%0A%20%20%20%20The%20curve%20shows%20classic%20diminishing%20returns%3A%20recall%20shoots%20up%20quickly%2C%20then%20plateaus.%0A%20%20%20%20The%20orange%20line%20tracks%20how%20many%20nodes%20are%20visited%20on%20average%20--%20the%20cost%20of%20higher%20recall.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(entry_point%2C%20graph%2C%20max_layer%2C%20mo%2C%20np%2C%20plt%2C%20points)%3A%0A%20%20%20%20_rng%20%3D%20np.random.default_rng(99)%0A%20%20%20%20_n_queries%20%3D%2050%0A%20%20%20%20_queries%20%3D%20_rng.uniform(0%2C%2010%2C%20size%3D(_n_queries%2C%202))%0A%20%20%20%20_k%20%3D%2010%0A%0A%20%20%20%20%23%20brute-force%20true%20top-k%20for%20each%20query%0A%20%20%20%20_true_topk%20%3D%20%5B%5D%0A%20%20%20%20for%20_q%20in%20_queries%3A%0A%20%20%20%20%20%20%20%20_dists%20%3D%20np.linalg.norm(points%20-%20_q%2C%20axis%3D1)%0A%20%20%20%20%20%20%20%20_true_topk.append(set(np.argsort(_dists)%5B%3A_k%5D))%0A%0A%20%20%20%20def%20_hnsw_search(query%2C%20ef)%3A%0A%20%20%20%20%20%20%20%20def%20_dist(idx)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20float(np.linalg.norm(points%5Bidx%5D%20-%20query))%0A%0A%20%20%20%20%20%20%20%20_cur%20%3D%20entry_point%0A%20%20%20%20%20%20%20%20_visited%20%3D%20%7B_cur%7D%0A%20%20%20%20%20%20%20%20for%20_layer%20in%20range(max_layer%2C%200%2C%20-1)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_changed%20%3D%20True%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20_changed%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_changed%20%3D%20False%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_cd%20%3D%20_dist(_cur)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20_nb%20in%20graph%5B_layer%5D.get(_cur%2C%20%5B%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_dist(_nb)%20%3C%20_cd%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_visited.add(_nb)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_cur%20%3D%20_nb%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_cd%20%3D%20_dist(_cur)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_changed%20%3D%20True%0A%0A%20%20%20%20%20%20%20%20_beam%20%3D%20%5B_cur%5D%0A%20%20%20%20%20%20%20%20_bv%20%3D%20%7B_cur%7D%0A%20%20%20%20%20%20%20%20for%20_%20in%20range(ef%20*%205)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_best%20%3D%20None%0A%20%20%20%20%20%20%20%20%20%20%20%20_bd%20%3D%20np.inf%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20_node%20in%20list(_beam)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20_nb%20in%20graph%5B0%5D.get(_node%2C%20%5B%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_nb%20not%20in%20_bv%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_d%20%3D%20_dist(_nb)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20_d%20%3C%20_bd%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_best%20%3D%20_nb%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20_bd%20%3D%20_d%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20_best%20is%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%20%20%20%20_bv.add(_best)%0A%20%20%20%20%20%20%20%20%20%20%20%20_visited.add(_best)%0A%20%20%20%20%20%20%20%20%20%20%20%20_beam.append(_best)%0A%20%20%20%20%20%20%20%20%20%20%20%20_beam%20%3D%20sorted(_beam%2C%20key%3D_dist)%5B%3Aef%5D%0A%20%20%20%20%20%20%20%20return%20sorted(_beam%2C%20key%3D_dist)%5B%3A_k%5D%2C%20len(_visited)%0A%0A%20%20%20%20_ef_values%20%3D%20list(range(1%2C%20min(len(points)%2C%20101)%2C%202))%0A%20%20%20%20_recalls%20%3D%20%5B%5D%0A%20%20%20%20_avg_visited%20%3D%20%5B%5D%0A%0A%20%20%20%20for%20_ef%20in%20_ef_values%3A%0A%20%20%20%20%20%20%20%20_rec_sum%20%3D%200%0A%20%20%20%20%20%20%20%20_vis_sum%20%3D%200%0A%20%20%20%20%20%20%20%20for%20_qi%2C%20_q%20in%20enumerate(_queries)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20_found%2C%20_nvis%20%3D%20_hnsw_search(_q%2C%20_ef)%0A%20%20%20%20%20%20%20%20%20%20%20%20_rec_sum%20%2B%3D%20len(set(_found)%20%26%20_true_topk%5B_qi%5D)%20%2F%20_k%0A%20%20%20%20%20%20%20%20%20%20%20%20_vis_sum%20%2B%3D%20_nvis%0A%20%20%20%20%20%20%20%20_recalls.append(_rec_sum%20%2F%20_n_queries)%0A%20%20%20%20%20%20%20%20_avg_visited.append(_vis_sum%20%2F%20_n_queries)%0A%0A%20%20%20%20_fig%2C%20_ax1%20%3D%20plt.subplots(figsize%3D(10%2C%205))%0A%0A%20%20%20%20_ax1.plot(_ef_values%2C%20_recalls%2C%20color%3D%22cyan%22%2C%20lw%3D2.5%2C%20label%3D%22Recall%4010%22)%0A%20%20%20%20_ax1.set_xlabel(%22efSearch%20(beam%20width)%22%2C%20color%3D%22gray%22%2C%20fontsize%3D12)%0A%20%20%20%20_ax1.set_ylabel(%22Recall%4010%22%2C%20color%3D%22cyan%22%2C%20fontsize%3D12)%0A%20%20%20%20_ax1.tick_params(axis%3D%22y%22%2C%20labelcolor%3D%22cyan%22)%0A%20%20%20%20_ax1.set_ylim(0%2C%201.05)%0A%20%20%20%20_ax1.axhline(y%3D1.0%2C%20color%3D%22cyan%22%2C%20ls%3D%22%3A%22%2C%20alpha%3D0.3)%0A%0A%20%20%20%20_ax2%20%3D%20_ax1.twinx()%0A%20%20%20%20_ax2.plot(_ef_values%2C%20_avg_visited%2C%20color%3D%22orange%22%2C%20lw%3D2%2C%20alpha%3D0.8%2C%20label%3D%22Avg%20nodes%20visited%22)%0A%20%20%20%20_ax2.set_ylabel(%22Avg%20nodes%20visited%22%2C%20color%3D%22orange%22%2C%20fontsize%3D12)%0A%20%20%20%20_ax2.tick_params(axis%3D%22y%22%2C%20labelcolor%3D%22orange%22)%0A%0A%20%20%20%20%23%20annotate%20the%20knee%0A%20%20%20%20_knee_idx%20%3D%20next((_i%20for%20_i%2C%20_r%20in%20enumerate(_recalls)%20if%20_r%20%3E%3D%200.95)%2C%20len(_recalls)%20-%201)%0A%20%20%20%20_ax1.annotate(%0A%20%20%20%20%20%20%20%20f%2295%25%20recall%20at%20ef%3D%7B_ef_values%5B_knee_idx%5D%7D%22%2C%0A%20%20%20%20%20%20%20%20xy%3D(_ef_values%5B_knee_idx%5D%2C%20_recalls%5B_knee_idx%5D)%2C%0A%20%20%20%20%20%20%20%20xytext%3D(_ef_values%5B_knee_idx%5D%20%2B%2010%2C%20_recalls%5B_knee_idx%5D%20-%200.15)%2C%0A%20%20%20%20%20%20%20%20fontsize%3D10%2C%20color%3D%22white%22%2C%20fontweight%3D%22bold%22%2C%0A%20%20%20%20%20%20%20%20arrowprops%3Ddict(arrowstyle%3D%22-%3E%22%2C%20color%3D%22white%22%2C%20lw%3D1.5)%2C%0A%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.3%22%2C%20fc%3D%22%231a1a2e%22%2C%20ec%3D%22white%22%2C%20alpha%3D0.9)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20%23%20annotate%20diminishing%20returns%0A%20%20%20%20_ax1.text(%0A%20%20%20%20%20%20%20%200.75%2C%200.15%2C%0A%20%20%20%20%20%20%20%20%22diminishing%20returns%3A%5Cnmore%20nodes%20visited%2C%5Cnlittle%20recall%20gain%22%2C%0A%20%20%20%20%20%20%20%20transform%3D_ax1.transAxes%2C%20fontsize%3D9%2C%20color%3D%22gray%22%2C%20fontstyle%3D%22italic%22%2C%0A%20%20%20%20%20%20%20%20ha%3D%22center%22%2C%20va%3D%22center%22%2C%0A%20%20%20%20%20%20%20%20bbox%3Ddict(boxstyle%3D%22round%2Cpad%3D0.3%22%2C%20fc%3D%22%231a1a2e%22%2C%20ec%3D%22gray%22%2C%20alpha%3D0.7)%2C%0A%20%20%20%20)%0A%0A%20%20%20%20_lines1%2C%20_labels1%20%3D%20_ax1.get_legend_handles_labels()%0A%20%20%20%20_lines2%2C%20_labels2%20%3D%20_ax2.get_legend_handles_labels()%0A%20%20%20%20_ax1.legend(_lines1%20%2B%20_lines2%2C%20_labels1%20%2B%20_labels2%2C%20loc%3D%22center%20right%22%2C%20fontsize%3D9%2C%20framealpha%3D0.7)%0A%0A%20%20%20%20_ax1.set_title(%22efSearch%20vs%20Recall%4010%20and%20Nodes%20Visited%22%2C%20color%3D%22white%22%2C%20fontsize%3D13%2C%20pad%3D12)%0A%20%20%20%20_ax1.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_fig.set_facecolor(%22%231a1a2e%22)%0A%20%20%20%20_ax1.tick_params(colors%3D%22gray%22)%0A%20%20%20%20_ax2.tick_params(colors%3D%22gray%22)%0A%20%20%20%20for%20_sp%20in%20_ax1.spines.values()%3A%0A%20%20%20%20%20%20%20%20_sp.set_color(%22gray%22)%0A%20%20%20%20for%20_sp%20in%20_ax2.spines.values()%3A%0A%20%20%20%20%20%20%20%20_sp.set_color(%22gray%22)%0A%20%20%20%20plt.tight_layout()%0A%20%20%20%20mo.as_html(_fig)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20numpy%20as%20np%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20matplotlib%20as%20mpl%0A%20%20%20%20mpl.rcParams.update(%7B%22text.color%22%3A%20%22white%22%2C%20%22axes.labelcolor%22%3A%20%22white%22%7D)%0A%20%20%20%20return%20mo%2C%20np%2C%20plt%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A