Home / Curated / Algorithms / Llama clustering

Llama clustering

Algorithms AIMech:LlamaClustering DRAFT

Aliases: Lattices by Leveraging Agglomerations and Multiple Ancestors

An agglomerative clustering algorithm that unions each current cluster with a nearest neighboring cluster in successive rounds and retains the resulting overlapping sets as a directed acyclic clustering structure with multiple possible parents.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 661 native IDs, names, aliases and scoped synonyms for the full concept name, expanded method name and local ID; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 82, 0, 0 lines. All distinct match contents were read, including pending discovery entries and source-reading observations. Recovery hits concern pending Llama discovery and source-reading notes, plus the explicit provenance review of its handoff; none identifies an existing standalone Llama clustering record. Both other checkouts returned no matches including ignored and hidden files. Semantic matching covered 41 AIO and 224 native definitions, all read; unchanged definitions were byte-compared with the preceding full assessment. 11 full annotated AIO node/edge/generated contexts and 5 full native records were inspected. Retain nearest-neighbor union rounds that accumulate overlapping sets with multiple parents. This is distinct from disjoint reciprocal agglomeration, thresholded weak-component merging, grafted binary trees, learned probabilistic DAGs and language-model terminology.

Claims & Grounded Evidence

7 Claims

Mechanism #nearest-neighbor-unions

Begin with singleton observations. In each round, each current cluster chooses a nearest other cluster according to a supplied similarity linkage; the next round contains the unions of these pairs, with duplicate sets identified. Accumulating those sets permits one cluster to have multiple parents and one observation to belong to overlapping clusters. Nonreciprocal neighbor relationships create this branching; the operation is not merely reciprocal-pair agglomeration.

supports Source: DAG-Structured Clustering by Nearest Neighbors · Locator: Section 3.2, Equations 5–6 and Algorithm 1, main PDF pp. 3–4

Scope #size-and-round-controls

The optional round limit can stop construction before the full-data root exists, so a limited-round result need not satisfy the root condition of the paper’s complete DAG-clustering definition. The parent-cap variant retains eligible nearest-neighbor pairs only when selected by both endpoint parent sets and carries forward unmerged clusters. Those controls change the unrestricted construction; exact-recovery statements are not automatically transferred to every cap and stopping choice.

supports Source: DAG-Structured Clustering by Nearest Neighbors · Locator: Definition 2, main PDF p. 2; Section 3.3 and Algorithm 1, pp. 3–4

Scope #conditional-separation

The paper analyzes linkage functions that distinguish connected from disconnected unions in an unobserved graph whose components define a target partition. Its noisy variant permits specified singleton neighbor errors when an incoming within-component neighbor preserves the affected point. The appendix assumes symmetric tie-free linkage. Recovery statements concern this restricted setting and enough rounds, not arbitrary data, arbitrary tied neighbors or universal superiority over tree methods.

supports Source: DAG-Structured Clustering by Nearest Neighbors · Locator: Sections 4.1–4.3, Definitions 3–4, Theorem 1 and Propositions 1–5, main PDF pp. 4–5
supports Source: DAG-Structured Clustering by Nearest Neighbors: Supplement · Locator: Appendix B.1–B.3, supplement PDF pp. 1–3

Mechanism #sparse-linkage-and-overlap

The practical sparse-graph computation treats missing point-pair similarities as zero and restricts neighbor candidates to clusters connected by graph edges. For overlapping clusters, ordinary tree average-linkage updates can double-count shared observations and differ from an exact set-union average. The paper explicitly treats those updates as an approximation and compares them empirically; the approximation is not an algebraic identity.

supports Source: DAG-Structured Clustering by Nearest Neighbors: Supplement · Locator: Appendix A.1, supplement PDF p. 1
supports Source: DAG-Structured Clustering by Nearest Neighbors · Locator: Section 6.1 and Table 2, main PDF pp. 6–8

Scope #complexity-scope

For the unrestricted analysis with symmetric tie-free linkage, the paper bounds the number of stored clusters by O(N²) and the linkage computations over R rounds by O(RN²). These are node and linkage-call counts, not unconditional wall-clock bounds or a claim that an arbitrary linkage is constant-cost. Its K-round recovery statement uses the largest target-cluster size K, not the number of clusters.

supports Source: DAG-Structured Clustering by Nearest Neighbors · Locator: Section 4.3, Propositions 3–5, main PDF p. 5
supports Source: DAG-Structured Clustering by Nearest Neighbors: Supplement · Locator: Appendix B.3, supplement PDF p. 3

Scope #evaluation-measures

The paper evaluates recovery using best-match Jaccard overlap per reference cluster and per point-membership, and evaluates excess structure using best-match Jaccard overlap per predicted node. These measure different properties: recovering all reference groups does not establish a compact or precise output. A conventional tree dendrogram-purity score alone can reward trivial large DAG families and does not establish useful overlapping structure.

supports Source: DAG-Structured Clustering by Nearest Neighbors · Locator: Section 5, Equations 9–12, main PDF pp. 5–6
supports Source: DAG-Structured Clustering by Nearest Neighbors: Supplement · Locator: Appendix C.1, supplement PDF pp. 3–5

Scope #empirical-scope

Experiments use partition-labelled and multi-label covering datasets plus WordNet reconstruction from word embeddings. Results vary by metric and dataset, and the method is not uniformly best. The timing comparison uses 100 rounds, ten threads, approximate average linkage and precomputed sparse graphs, excluding graph construction. The appendix distinguishes 1.2 million large-ILSVRC clustering inputs from a sampled 50,000-point evaluation. These source-specific results are not portable runtime guarantees or reproduced experiments.

supports Source: DAG-Structured Clustering by Nearest Neighbors · Locator: Sections 6.1–6.3, Tables 1–5 and Figure 3, main PDF pp. 6–9
supports Source: DAG-Structured Clustering by Nearest Neighbors: Supplement · Locator: Appendix C.2–C.4, Tables 6–7 and Figure 6, supplement PDF pp. 5–6

⚠️ Curated Limitations & Negative Results

This Llama is the 2021 clustering algorithm, not a language model. A cluster-inclusion DAG does not assert causal or conditional-independence semantics.
The literal Lemma 1 proof writes argmin where the main similarity algorithm uses argmax. Its noisy-recovery proof also states a first-round pair-cover argument without the singleton-target exception, whose singleton already exists in the accumulated structure. No formal theorem certification or refutation is claimed.
Printed dendrogram-purity Equations 18–19 sum ordered unequal pairs but normalize by unordered-pair counts. A conventional unordered-pair interpretation is needed for unit-normalized purity; no metric implementation was inspected.
Standalone exact calculations illustrate finite-round root absence, overlap double-counting and the printed purity normalization. They are not author implementation runs or general correctness proofs.
All 12 main and six supplementary PDF pages were read, including figures, tables, references and proofs. Author code, datasets, alternative source revisions and historical experiments were not audited or executed.
No training, model execution, paid service, data upload, benchmark replication or formal proof certification was performed. This record remains DRAFT.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:UnsupervisedClustering` Unsupervised Clustering	related_match	The algorithm groups observations into overlapping sets from supplied linkage scores; this target denotes the grouping task, not this algorithm.
`AIO:HierarchicalClustering` Hierarchical Clustering	related_match	The method extends nested cluster-tree construction to a structure with overlapping groups and multiple parents. This related-task mapping does not identify its DAG with a tree or assert equivalence to every hierarchical-clustering definition.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`llama2021`	DAG-Structured Clustering by Nearest Neighbors Nicholas Monath, Manzil Zaheer, Avinava Dubey, Amr Ahmed, Andrew McCallum	primary paper full_text	ID: PMLR:130:monath21a sha256:88876e633ff1…
`llama-supplement`	DAG-Structured Clustering by Nearest Neighbors: Supplement Nicholas Monath, Manzil Zaheer, Avinava Dubey, Amr Ahmed, Andrew McCallum	primary paper full_text	ID: PMLR:130:monath21a sha256:12f635c9983b…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-14T00:04:51Z

Updated: 2026-10-14T00:04:51Z

Source File: data/curated/LlamaClustering.yaml