acore-utils

Overview

The goals of this project are to:

1. Implement the whole Comparative Method (from historical linguistics) using LLM agents to iteratively optimize the three mutually-dependent components (represented as programs)
2. Explore the implications for solving this type of problems using agents for agentic solutions to other types of discrete optimization problems.

Specific research questions include the following:

• RQ1: Can LLM agents improve on non-agentic baselines at cognate detection, forward reconstruction, and backward reconstruction (with oracles)?
• RQ2: Can the whole comparative method be implemented using an agentic workflow?
• RQ3: Do metalearning approaches allow improved performance on reconstruction tasks? How well do capabilities developed when solving other tasks generalize to comparative reconstruction?
• RQ4: How do changes in how agents coordinate their actions (and specialization) affect their performance on comparative reconstruction tasks?

This list will evolve as discoveries increase.

The chances of this project succeeding are quite high:

• There is an existing proof-of-concept for forward reconstruction or $\rho$ (one of the major components)
• There is good initial evidence that $\pi$ or backward reconstruction is not as difficult as $\rho$
• There is considerable prior art for $\kappa$ or cognate set induction

What has never been done is to place all of these components in a common framework and produce a comparative method implementation that can operate autonomous (or, potentially, can collaborate with a human scholar).

Components of the Comparative Method

The Comparative Method, as implemented here, has three components, all of them functions:

• $\kappa: \mathcal L \rightarrow \mathcal K$, a function from lexicons in a set of lexicons from sister languages $\mathcal L = L_1, L_2, \dots, L_n$ to a set of cognate sets (sets of words believed to be descended from the same ancestral word or “protoform”) $\mathcal K$
• $\pi: \mathcal K \rightarrow \mathcal P$, a function from a set of cognate sets $\mathcal K$ to a set of corresponding protoforms $\mathcal P$
• $\rho: \mathcal P \rightarrow \mathcal K$, a function from a set of protoforms $\mathcal P$ to a set of corresponding cognate sets $\mathcal K$

The objective is to:

• Maximize the mean proportion of $\mathcal L$ that can be reconstructed (grouped into cognate sets by $\kappa$, encoded as protoforms by $\pi$, and decoded back into cognate sets by $\rho$
• Minimize the complexity of $\pi$ (number of atoms)
• Minimize the complexity of $\rho$ (number of atoms)

More precisely, the goal is to maximize the following objective:

Let $\mathcal{L} = {L_1, \dots, L_n}$ be a set of lexicons, and let $\Sigma^\ast$ be the set of all strings over the alphabet $\Sigma$. Let $B(\cdot)$ denote the length in bits of an object under a fixed encoding.

• $W = \bigsqcup_{i=1}^{n} L_i$ is the set of all words.
• $\kappa$ is a function that induces a partition $\mathcal{K} = \kappa(\mathcal{L})$ of $W$ into cognate sets, such that $|C \cap L_i| \le 1$ for every $C \in \mathcal{K}$ and every $i$.
• $\mathcal{K}^\ast = {, C \in \mathcal{K} : |C| \ge 2 ,}$ is the set of non-singleton cognate sets.
• $U = W \setminus \bigcup \mathcal{K}^\ast$ is the set of unexplained words.
• $\pi : \mathcal{K}^\ast \to \mathcal{P}$ maps each cognate set to a protoform, where $\mathcal{P} = \pi(\mathcal{K}^\ast)$.
• $\rho : \mathcal{P} \to 2^{\Sigma^\ast}$ maps each protoform to a set of reflexes, with at most one reflex per language.
• $E_C = \rho(\pi(C)) \setminus C$ is the set of overgenerated reflexes for $C \in \mathcal{K}^\ast$.

The objective is

\min_{\kappa,\,\pi,\,\rho}\;
B(\kappa) + B(\pi) + B(\rho)
+ \sum_{p \in \mathcal{P}} B(p)
+ \sum_{C \in \mathcal{K}^\ast} B(E_C)
+ \sum_{w \in U} B(w)

subject to

C \subseteq \rho(\pi(C)) \quad \forall\, C \in \mathcal{K}^\ast

Decoding can be formalized as

W = U \,\sqcup \bigsqcup_{C \in \mathcal{K}^\ast} \big( \rho(\pi(C)) \setminus E_C \big)

At first glance, it might not be clear why both $\pi$ and $\rho$ are necessary since, ideally, they are inverses of one another ($\pi = \rho^{-1}$) and therefore encode the same relationship. They are both essential, however, because $\pi$ ensures that the protoforms $\mathcal P$ contain only information that is present in $\mathcal K$ and $\rho$ ensures that $\mathcal K$ contains only information that is present in $\mathcal P$. Optimizing them jointly ensures that the protoforms approach a lossless encoding of the cognate sets. Linguists have found that such an encoding can be independently demonstrated to mirror ancestral languages (or protolanguages). The complexity penalties are also important:

• The complexity penalty on $\pi$ prevents degenerate solutions where the proposed protolanguage has an arbitrarily large number of sounds or an arbitrarily large number of insertions and deletions, compared to the cognate sets.
• The complexity penalty on $\rho$ prevents degenerate solutions where the phonemes (sounds) in the proposed protolanguage do not resemble those in the daughter languages (in the cognate sets $\mathcal K$).

The Regularity Principle

The Comparative Method is made possible by the Neogrammarian Principle or Regularity Principle which says that changes in phonemes are systematic. They may involve replacing one phoneme with another phoneme (e.g., d > r) or they may only apply in a certain type of context (e.g., d > r at the beginning of a word) but they are always systematic. This allows us to define $\rho$ as sequences of string rewrite rules (e.g., replace d with r at the beginning of a string). The prefixes of these sequences (from the different languages in the family) will sometimes overlap, meaning that we can construct a family tree for the language group (a phylogenetic tree). This also means that there will be regular patterns of correspondence, shared across cognate sets that make it possible to write rules that form a classifier which predicts the phonemes in a protoform from the aligned reflexes (descendant words) in the corresponding cognate set.

Implementing $\kappa$

Cognate set induction is the component of the Comparative Method with the most prior work, but it is still not solved. When humans are identifying cognate sets, they look at three things:

1. Are the words pronounced similarly (are the phonological similar)?
2. Do the words have similar meanings (are the words semantically similar)?
3. Do the words show patterns of correspondence in their phonemes that are shared by other words?

State-of-the-art cognate set induction methods take all of these facts into account. They do not generally assume a fully-articulated $\pi$ or $\rho$, so their ability to find new true cognates and prune false cognates is somewhat hindered.

Implementing $\pi$

$\pi$ assumes that each cognate set is aligned to form a matrix so as to maximize the similarity in pronunciation of the phonemes in the words (with gaps to make better alignments possible, when the number of phonemes in reflexes is not the same or when phonemes are very different, e.g. a and k). $\pi$ can be represented as a set of implications with an antecedent and a consequence:

• Antecedent: a set of statements about phonemes that are found in the current column of the matrix and (perhaps) what phonemes are found in the preceding and following columns.
• Consequent: the proto-phoneme that is predicted to go in the current column in the protoform.

This program is a kind of rule-based classifier.

My lab has done a lot of earlier work with neural (specifically, sequence-to-sequence) implementations of $\pi$ (or $\pi$ jointly with $\rho$):

• Transformed Protoform Reconstruction
• WikiHan: A New Comparative Dataset for Chinese Languages
• Semisupervised Neural Proto-Language Reconstruction
• Improved Neural Protoform Reconstruction via Reflex Prediction

Implementing $\rho$

$\rho$ is a cascade of string-rewrite rules (sound laws) or, in the more general case, a tree in which nodes correspond to ordered sound laws rules. It reflects the fact that changes in the pronunciation of words progress in time and that it is possible to reason about the sequences of the rules.

Some relevant readings:

• PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics
• ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis
• Programming by example meets historical linguistics: A large language model based approach to sound law induction
• Can Large Language Models Code Like a Linguist?: A Case Study in Low Resource Sound Law Induction

Relevance of Agents

The problem of finding optimal $\kappa$, $\pi$, and $\rho$ functions, individually, are relatively intractable search problems. It is possible to develop symbolic algorithms that will generate such programs (especially for $\pi$ and $\kappa$) if one is given $\mathcal K$ and $\mathcal P$, but it is not clear that there is a traditional search algorithm that will find an optimal $R=\langle \kappa, \pi, \rho \rangle$. Humans solve this problem by a process of iterative refinement (editing one program, then editing another, then checking the results). LLM agents provide a way to automate this workflow.

In the simplest case, a single agent could edit any of the files, in addition to running the whole system—$\rho(\pi(\kappa(\mathcal L)))$, inspecting errors, analyzing the training data, etc. Edits would be made synchronously. This agent would be responsible for the planning of optimization strategies and their execution.

However, there are other configurations of agents that may be better. For example, there may be one agent responsible for overall planning, other agents responsible for updates to the code, and other agents responsible for analyzing data and errors. In this case, edits would take place asynchronously and some means of coordinating the activities of the agents would have to be provided (which could range from a rigid set of protocols to a text file of notes to which the agents could write.

A Note on Models and Harnesses

We plan on carrying out the initial experiments using Claude Opus as a model and OpenHands as a harness. We will extend the range of models after we have working prototypes of the $\kappa$, $\pi$, and $\rho$ models. We will then expand our scope to three types of models:

1. Other frontier models (e.g., Gemini and GPT-5.x). We will have funds that can be used for Gemini, so we prioritize it.
2. Open weights models (GLM, Qwen, etc.)
3. Open source models (probably Horizon K2)

In some cases, we may use different models for different kinds of agents.

I prefer to stick with OpenHands as an agent harness because (1) I like it and (2) it will make it relatively easy to switch any of these models in and out without significant architectural changes. Other harnesses can be considered.

TODO

• Add functionality to select which dataset to use

Roadmap

• Datasets
  • Austronesian
  • Uralic
  • Romance

Claude Code prototype

• Complete Claude Code version
  • Develop $\rho$ execution and evaluation ability
    • Evaluation (reward function)
      • Code complexity
      • Accuracy
      • Skill for performing and interpreting evaluation
    • Error reporting (after the fashion of pytest)
  • Develop $\rho$-discovery capability
  • Code format definitions
    • Heuristic initialization of $\rho$
      • Protoform-reflex alignment function
      • Correspondence aggregation function
      • Code generation for correspondences
    • Iterative update of $\rho$
  • Develop $\pi$-discovery capability
    • Heuristic initialization of $\pi$
    • Iterative update of $\pi$
  • Develop $\mathcal K$-discovery capability

Open Hands prototype