The idea
You can imagine a lot of scientific exploration or optimization as a state search graph or tree (hence, Yggdrisil) where modified versions of an existing state are downstream nodes and the modifications are edges. These modifications are candidates, not guaranteed improvements. Humans are often pretty good at intuiting what modification to make to get a more optimized version but are constrained by how many states they can explore. Computers can use simple algorithms to explore a massive number of states. In short, humans are sample-efficient and machines are compute-efficient. The idea is to combine informed proposals with automated search and test whether this finds better states with fewer expensive evaluations. By building a framework where we can use an "agent", or an LLM with access to some tools, to propose these modifications and then receive feedback from the state, we might be able to get the best of both worlds in terms of efficiency and being able to apply large amounts of compute to solving the problem. Slightly more formally: So if a scientist is trying to build or optimize something, they might have an initial stateThe Yggdrisil Framework
We built Yggdrisil, a Python library, to test this. The library includes a bunch of very flexible classes and search algorithms to make this easy to implement. Here are the primary building blocks with examples we will assemble into a minimal working run. To stick with the theme of the package name, we can use an example inspired by D&D.Example: Optimizing Your Pack
I won't go deep into D&D rules here, but this should be pretty easy to conceptualize without too much background. You can carry a maximum amount of weight; let's call it 10 units. You just broke into a dragon's den or whatever and are now making your escape. You want to maximize the value of items you're taking with you without exceeding your maximum carrying capacity. We define the items with values and weights below. Although this is a small combinatorial problem that we could solve directly, you can also imagine how it can be formulated as a state search problem. We'll come back to an example that's less trivial later.frozenset()
"potion" proposes packing the healing potion. An item can be added only once.
'potion'
frozenset is immutable, we must keep and return the result of union.
frozenset({'potion'})
apply, and state_key. weight and value sum the item properties. legal_actions lists every item we have not packed yet, including items that would make the backpack too heavy.
Unknown items and duplicate additions are still invalid actions. An overweight backpack is a valid candidate state: we can assemble it and then discover that we cannot lift it.
Packing a potion and then a spellbook reaches the same state as packing them in the opposite order. Hashing the set gives both paths the same state ID, so the graph can merge them.
measure is just a cheap calculation, shared by the objective and the evaluator. evaluate wraps those measurements in an EvaluationResult that Yggdrisil can store and cache. The example below tries the moonblade and shield together: 11 weight units in a 10-unit capacity.
goal_reached unset and search until the budget is used or there are no more proposals. This toy objective calls the evaluator's cheap measure method directly; an expensive experiment would need a deliberate evaluation and caching schedule.
15
Proposal identifies a parent state and an action. A Decision groups the proposals made by one policy operation. This example proposes adding the healing potion to the empty backpack. The live policy will construct decisions in the same way.
Decision(role='pack-item', proposals=[Proposal(parent_id='3a5728ac88514c33efe2ac2b80ca6b074b6b281904a89235ed815e1fe5a86241', action='potion', metadata={})], selected_state_ids=['3a5728ac88514c33efe2ac2b80ca6b074b6b281904a89235ed815e1fe5a86241'], model=None, input_context=None, tool_calls=[], output=None, metadata={})
NavigatorExplorerPolicy: the navigator selects an existing state, and the explorer uses tools and proposes actions. The inherited step() method returns the same Decision and Proposal objects as our local policy.
from yggdrisil.agents import NavigatorExplorerPolicy
from yggdrisil.agents.pydantic_ai import make_explorer, make_navigator
def inspect_pack(items: list[str]) -> dict[str, int | bool | str]:
"Measure a candidate pack, including packs that are too heavy."
unknown = set(items) - packing_problem.items.keys()
if unknown:
raise ValueError(f"Unknown items: {sorted(unknown)}")
if len(items) != len(set(items)):
raise ValueError("Each item can only be packed once")
return packing_evaluator.measure(frozenset(items))
class SmartPackingPolicy(NavigatorExplorerPolicy):
def __init__(self, model: str):
navigator = make_navigator(
model,
instructions=(
"Choose one existing frontier state to explore. "
"Use the explorer's saved notes to guide your choice. "
"Do not invent state IDs."
),
)
explorer = make_explorer(
model,
str, # Each action is a single item ID.
tools=[inspect_pack],
instructions=(
f"Available items (ID, weight, value): {gear}. "
"Inspect the current pack and try candidate packs with inspect_pack. "
"Return item IDs to add, each as an independent one-item addition "
"to the current state, never an item already in the pack. "
"Heavy packs are allowed proposals; use the feedback to judge them. "
"Include a short note describing what you tried and learned."
),
)
super().__init__(
navigator=navigator,
explorer=explorer,
goal=f"Maximize loot value while carrying at most {pack_capacity} weight.",
max_requests=1,
)
inspect_pack is the explorer's tool. It reports value, weight, and "I can't lift it" feedback without blocking overweight candidates. Tool probes are recorded in the explorer's decision; they only become graph states if the explorer proposes the corresponding action and the runner applies it.
This block is illustrative and is not executed by the notebook. To use it, install the yggdrisil[agents] extra, configure your provider credentials outside the notebook, instantiate SmartPackingPolicy(model="provider:model-name") with a real model identifier, and pass it as the runner's policy. The problem, evaluator, objective, and graph stay the same. The adapter records the explorer's tool calls and notes for inspection; those notes help guide later navigation. This does not make the runner automatically schedule evaluations.
Our best-first policy prioritizes the highest-scoring expandable backpack and proposes every item not already inside it. Some children will be too heavy. They are recorded, evaluated, and given a low score, rather than being filtered out before we try them.
Other branches stay available. This baseline can eventually expand overweight states too; it does not prune them. That is deliberately simple: a more informed policy could use the feedback to avoid wasting further effort on those branches. Each step expands one parent, and alphabetical ordering breaks ties reproducibly.
RunLimits(max_states=64, max_steps=64, max_wall_time_s=None)
evaluate_cached for every discovered state to persist its full feedback. The objective and these reports use the same cheap measurement, so their results agree. The runner itself does not automatically invoke the evaluator.
This web example uses a fresh temporary SQLite graph for each run and removes it afterward, so slider changes do not accumulate files. In a longer experiment, save the database to a persistent path so the built-in inspector can reopen it.
Best carryable backpack: Healing potion, Oak shield, Spellbook
23 value, 10 / 10 weight. Recorded 32 carryable and 32 overweight states, connected by 138 edges. Stopped because the state limit was reached.
Other Features of the Library
The library has several other features worth highlighting.- Save and resume a search. States, transitions, evaluations, and run progress are stored in SQLite, so we can return to a long search without starting over.
- Merge equivalent states. Different sequences of actions can reach the same result. The graph merges states with the same identity while keeping the different paths that reached them.
- Reuse expensive evaluations. Cached results are tied to the state and the evaluator's name, version, and configuration, so we can reuse a previous measurement when those match.
- Use several evaluators. We can store several kinds of evidence about the same state and define separately how the objective ranks it. The application decides when to run these evaluations.
- Swap search policies. Random search, best-first search, and LLM-based policies can use the same problem and graph interfaces, making it easier to compare how they choose candidates.
- Keep a record of decisions and attempts. Decisions can include the model, input context, tool calls, and output. Each proposal records whether it created a transition, reused one, failed, or was skipped.
- Inspect the search as it runs. The built-in web viewer shows the graph and lets us click through states, evaluations, decisions, and transitions.
- Export the results. JSON, GraphML, and NetworkX exports let us analyze the graph or build our own plots after a run.
Minimizing E. coli
For a more realistic use case, let's think about minimizing an E. coli genome. Let's start with a strain to be optimized, MG1655. Then we want to minimize the genome (why?). We can define the root node as the full MG1655 genome. To optimize, we can think about what genes we want to delete, then define each set of genes to delete as an action on an edge, and each resulting genome as another state node. This is where the framework and agent earn their pay. Genome minimization, as you might expect, is a much harder task for several reasons. Biology is filled with complex networks of genes, and the effects of combining deletions can be hard to predict. Some single-gene deletions are lethal under the chosen growth conditions. Other deletions are tolerated individually but become lethal in combination, a phenomenon known as synthetic lethality. This means that genes we can delete separately cannot always be deleted together. Côté et al. (2016) provide an E. coli example of these genetic interactions. We need to be able to navigate this network of candidate states (combinations of genes) and evaluate which combinations might be viable (model predictions alone cannot establish viability in a living cell) and which are not. The total number of combinations is also absolutely massive:Related work
This is, of course, not the first attempt at E. coli minimization, nor the first use of agents to search over candidate designs. The relevant work falls into three groups: genome reduction, optimization under limited evaluation budgets, and agentic search.Genome Reduction
Experimental work by Pósfai et al. (2006) showed that planned deletions could produce reduced E. coli genomes while preserving useful growth and protein-production properties under the tested conditions. On the computational side, Rees-Garbutt et al. (2020) introduced Minesweeper and GAMA, which alternate candidate design and whole-cell simulation to find reduced Mycoplasma genitalium genomes. These are direct precedents for treating genome minimization as a search problem, although their organism and evaluator differ from our proposed E. coli example. Gherman et al. (2025) provide an especially close domain comparison: they combine an adapted Minesweeper algorithm, an E. coli whole-cell model, and a machine-learning surrogate to accelerate genome reduction. Shcherbakova et al. (2025, preprint v2) take a generative-model approach in Designing minimal E. coli genomes using variational autoencoders. They train VAEs on E. coli pangenome data, modify the loss to encourage smaller gene sets, and computationally evaluate sampled designs with an E. coli whole-cell model. This connects directly to our proposal-policy comparison: a learned generative model could propose candidate gene sets or guide deletion choices within Yggdrisil, alongside simple algorithms and LLM-based policies.Optimization
Optimization is a major focus of both maths and machine-learning research, but several papers address either structurally similar problems or optimization in similar domains. Jones, Schonlau, and Welch (1998) use surrogate models to balance promising regions against uncertainty when objective evaluations are expensive. In biological sequence design, Angermueller et al. (2020) introduce P3BO, which allocates proposals across an ensemble of methods according to their previous performance.Agentic Search
Agentic search is a newer paradigm. Language Agent Tree Search, or LATS (Zhou et al., 2024) combines Monte Carlo tree search with language-model proposals, value estimates, reflection, and environmental feedback. AIDE (Jiang et al., 2025) frames machine-learning engineering as tree search over candidate code, while The AI Scientist-v2 (Yamada et al., 2025) uses agentic tree search within a broader research workflow. Branching exploration and building on previous attempts are therefore established ideas. An especially close biological example is PABLO (Maus et al., 2026, preprint). It coordinates planner, explorer, and worker agents for biological black-box optimization under an evaluation budget, using a history that includes successful and unsuccessful candidates. Its molecular and peptide design experiments make it relevant to our proposed agent-driven search. Using multiple agents, retaining failures, or optimizing biological designs is not by itself a new contribution. With all this existing work, what does this project contribute? A few things, I think. I'll dive into the specifics throughout the rest of this report, but:- Understanding how agents reason: some of our experiments yield surprising results about how models navigate trade-offs.
- Benchmarking proposal policies — in this framework, a policy can be just about anything. It's interesting to benchmark LLMs, simple algorithms, and other models on a new kind of task.
- The framework itself — this framework is open source and makes it straightforward to implement similar state search problems.
Framing the Problem
Using the same building blocks as the dungeon example, we can lay out the minimal E. coli problem. The walkthrough below follows the experiment implementation inyggdrisil-minimal-ecoli. We describe the reference search, which uses two growth checks: flux balance analysis (FBA) and resource balance analysis (RBA). Both are explained below.
The Python-style pseudocode below keeps the experiment's main logic and leaves out type annotations, validation details, and storage plumbing. Helper names describe operations rather than actual library APIs. These blocks are for explanation and are not executed here. Full runs require the application's model and data dependencies; LLM-based runs also require an API key.
State: which genes have we deleted?
In the dungeon example, the state was the set of items in the backpack. Here, our universe is the protein-coding genes in MG1655. We can think of a state as the genes we have retained: everything we have not deleted. The experiments store the equivalent set of deleted genes. Given the reference genome, either representation tells us the other. An empty deletion set therefore represents the root, the full MG1655 genome. We useb locus tags, such as b0001, as gene IDs. A frozen set makes deletion order irrelevant: deleting A then B reaches the same state as deleting B then A. Some experiments restrict which genes are eligible for deletion; genes outside that candidate set remain present.
all_genes = load_mg1655_gene_ids()
candidate_genes = load_candidate_gene_ids()
initial_state = frozenset() # No deletions yet.
def retained_genes(deleted):
return all_genes - deleted
Objective: how small can we make it while passing the growth checks?
The objective is simple: delete as many genes as possible while keeping the cell viable. Deleting genes is easy; deciding whether the cell could still grow is the interesting part. In the experiments, we approximate this with the FBA and RBA checks explained below. Among candidates passing both checks, we prefer more deletions, then higher FBA growth. The code keeps these measurements separate rather than combining everything into one weighted score. A model passing these checks still needs biological validation.def passes_growth_checks(evidence):
fba = evidence["fba"]
rba = evidence["rba"]
return (
fba["solver_status"] == "optimal"
and fba["growth_rate"] > 0
and rba["feasible_at_growth_floor"]
)
def candidate_rank(deleted, evidence):
return len(deleted), evidence["fba"]["growth_rate"]
fba-only ablation omits the RBA requirement but still records its result.
Action: which additional genes should we delete?
The action space is absolutely massive. We let the policy, which may be an agent or a simpler algorithm, choose a combination of genes that are still present and eligible for deletion. For the experiments described here, each action deletes between 1 and 20 genes. A policy step can propose several such actions. Keeping actions small lets us test changes incrementally; recovery comes from returning to a good parent and trying a different or smaller bundle after a failed child.available = candidate_genes - deleted
action = choose_deletions(
available,
min_genes=1,
max_genes=20,
)
Transition: apply the deletion
This is simple: apply the new deletions to the state. Conceptually, we remove genes from the retained genome. Because we store deletions, the code adds them to the deletion set. The problem checks that an action contains 1–20 eligible genes that have not already been deleted. For a valid action, the transition is just the set union below. Like an overweight backpack, a genome that fails a growth check is still recorded. Evaluation tells the policy whether to expand it.def apply(deleted, action):
return deleted.union(action)
Policy and proposal: where do we try next?
A policy chooses a parent state and proposes additional deletions. The agent version uses a deterministic scheduler to choose parents, then an LLM explorer to propose actions using the available evidence and previous outcomes. Random and heuristic baselines replace those choices with simpler rules. The important recovery behavior is that a good parent remains available after a failed child. We can return to it and try different genes or a smaller deletion bundle. We do not undo deletions inside the failed child. Each proposal pairs a parent with one action. In closed-book experiments, the model sees opaque gene labels; the saved states still use canonical gene IDs.def propose_next(graph):
parents = [
node for node in graph.states
if passes_growth_checks(node.evidence)
]
if not parents:
return []
parent = scheduler.choose(parents, history=graph.history)
available = candidate_genes - parent.deleted_genes
actions = explorer.propose(
parent,
available_genes=available,
max_genes=20,
history=graph.history,
)
return [(parent, action) for action in actions]
Runner, graph, and limits: put the pieces together
The runner evaluates the root, asks the policy for proposals, applies them, and evaluates the resulting states. It saves the states, transitions, measurements, and decision history in the graph. Different deletion orders can reuse the same state and cached measurements. We set limits on unique states, policy steps, and optionally wall time. The root counts as a state. LLM calls have additional limits on requests, tool use, tokens, and cost. The sketch below shows the main loop; the implementation also handles retries, interrupted runs, and checks that saved results match the current configuration.graph.add_state(initial_state)
graph.evaluate_cached(initial_state, evaluators)
for step in range(max_steps):
if state_or_time_limit_reached(graph):
break
proposals = propose_next(graph)
if not proposals:
break
for parent, action in proposals:
if state_or_time_limit_reached(graph):
break
child = apply(parent.deleted_genes, action)
graph.add_transition(parent, action, child)
graph.evaluate_cached(child, evaluators)
Evaluators: what do we know about this candidate?
The backpack needed weight and value. For a genome, we need several different kinds of evidence. We record five measurements: how much we removed, what experiments say about those genes, which annotated functions remain, and whether two mechanistic models predict growth. An evaluator takes a candidate genome and returns measurements. Only the FBA and RBA results determine whether a parent passes the reference search's growth checks. Essentiality and module retention provide additional evidence that a policy can use when choosing what to try.Genome size: how much have we removed?
Here, "size" means the number of protein-coding genes remaining in the reference registry. An annotation identifies genes and their positions in a genome; our registry takes these from the MG1655 reference annotation. The original K-12 genome sequence is described by Blattner et al. (1997). This evaluator simply counts the deletion set and subtracts it from the reference gene count. It counts a short gene and a long gene equally, so it measures gene reduction rather than DNA length. It says nothing about whether the resulting cell can grow. In the experiment snapshot, the full registry has 4,290 genes. The WCM comparison permits deletions from a 1,216-gene subset, but the remaining-gene count still starts from the full registry. Genes outside that subset have not disappeared.def measure_size(deleted):
return {
"genes_deleted": len(deleted),
"genes_remaining": len(all_genes - deleted),
}
Essentiality: what happens when these genes are disrupted experimentally?
An essential gene is required for growth under specified conditions. Conditions matter: a cell may need a gene to make a nutrient in minimal medium, but tolerate its loss when that nutrient is supplied. We use the experimental calls in Table S1 of Choe et al. (2023). Their transposon insertion sequencing, or Tn-seq, experiment inserts DNA into many genomic positions and sequences the surviving population. A shortage of insertions within a gene can suggest that disrupting it harms growth. The paper also investigates false calls, including cases where DNA-binding proteins prevent insertion. The dataset compares LB, a rich growth medium, with M9 glucose, a defined minimal medium. Our application summarizes the two calls as follows; these are the application's labels, not universal biological categories:| Label | Call in LB | Call in M9 glucose |
|---|---|---|
| Essential | Essential | Essential |
| Conditionally essential | Nonessential | Essential |
| Nonessential | Nonessential | Nonessential |
| Ambiguous | Essential | Nonessential |
| Unknown | No matched measurement | No matched measurement |
from collections import Counter
def measure_essentiality(deleted):
labels = [essentiality_table[gene] for gene in deleted]
return dict(Counter(labels))
unknown entry for genes without a matched measurement. This sketch shows the counts; the experiment also saves the genes in each category.
Module retention: do we still encode the pieces of a biological function?
KEGG, the Kyoto Encyclopedia of Genes and Genomes, organizes biological knowledge into pathways and other functional descriptions. A KEGG module is a smaller unit, such as the reactions needed to make a particular compound or the components of a molecular complex. Takami et al. (2012) describe using modules to infer functional capacity from gene sets. Genes are mapped to KEGG Orthology (KO) identifiers: labels for molecular functions. Several genes can support the same KO. A module then specifies which functions are required using AND and OR rules, with optional components where appropriate. For example,(A OR B) AND C needs either function A or B, plus function C. See the official KO definitions and module completeness rules.
Select genes to see how AND/OR logic determines module completeness. This toy module requires: (KO1 OR KO2) AND KO3.
def measure_modules(deleted):
remaining = all_genes - deleted
functions = functions_present(remaining, background_annotations)
broken = []
for module in reference_complete_modules:
if not module.requirements_met(functions):
broken.append(module)
return {
"n_complete": len(reference_complete_modules) - len(broken),
"broken_modules": broken,
}
requirements_met stands for the module's AND/OR logic, not a percentage-of-genes threshold.
FBA: can the metabolic network produce biomass?
Flux balance analysis (FBA) asks how material can flow through a network of biochemical reactions. A metabolite is a molecule consumed or produced by those reactions, and a flux is a reaction's rate. FBA assumes a steady state: production and consumption of each internal metabolite balance. Nutrient uptake and reaction bounds restrict the allowed flows. A numerical solver finds flows satisfying these constraints while optimizing a chosen objective. Orth, Thiele, and Palsson (2010) give an introduction. For growth, the objective is a biomass reaction: a bookkeeping reaction that consumes the building blocks needed to make cellular material in specified proportions. Its flux serves as the model's predicted specific growth rate, in inverse hours. It is a mathematical representation of growth, rather than a simulation of an individual cell dividing. See Feist and Palsson (2010).A simplified Boolean illustration, not an FBA solve or a prediction for a real cell. The displayed rates are illustrative constants. Select genes to knock them out. pykA/pykF are redundant: try knocking out just one, then both.
def measure_fba(deleted):
model = iml1515.copy()
modeled, unmodeled = split_by_model_coverage(deleted, model)
model.set_medium(aerobic_m9_glucose)
model.knock_out_genes(modeled)
solution = model.maximize_biomass()
return {
"growth_rate": solution.growth_rate,
"solver_status": solution.status,
"unmodeled_deletions": unmodeled,
}
knock_out_genes applies the gene-protein-reaction rules. The model is copied so one candidate's deletions do not change the next candidate's starting model.
RBA: can the cell build and maintain the machinery needed for growth?
Resource balance analysis (RBA) adds constraints on the machinery that carries out cellular processes. Metabolic reactions require enough enzymes to support their fluxes. Making those enzymes requires ribosomes, which synthesize proteins, and supporting processes such as chaperoning, which helps proteins fold, and secretion, which transports proteins. The model also limits how much machinery fits into cellular compartments and how the cell allocates its proteome, its complement of proteins. These requirements compete for finite resources. See the RBA overview and Bulović et al. (2019). Our evaluator uses the E. coli K-12 RBA model from that work. A deletion disables the modeled enzymes and process machinery requiring the corresponding protein. We then ask whether the remaining system can support balanced growth: sustained growth with a consistent cellular composition, including enough production to replenish its machinery. The mathematical constraints are described in the RBA theory guide. The experiment tests a fixed growth floor of 0.1 h⁻¹. This means asking whether the model can sustain that specific growth rate, rather than searching for each candidate's maximum rate. The floor is an experiment setting, not a universal boundary between living and dead cells. The result reports feasibility at that floor, modeled and unmodeled deletions, and solver diagnostics. RBA covers processes that ordinary FBA leaves out, but it still models only part of the cell. Passing both checks is evidence for a candidate worth studying further, not confirmation that it will divide experimentally.def measure_rba(deleted):
model = rba_reference.copy()
modeled, unmodeled = split_by_model_coverage(deleted, model)
model.disable_protein_machines(modeled)
solution = model.check_growth(rate=0.1)
return {
"feasible_at_growth_floor": solution.feasible,
"solver_status": solution.status,
"unmodeled_deletions": unmodeled,
}
Keep the evidence together, without collapsing it into one score
Each evaluator returns a different view of the same candidate. The experiment saves those measurements with coverage (what was actually assessed) and provenance (which data, model, and settings produced the result). A cached result can be reused when the candidate and evaluator configuration match.evaluators = {
"size": measure_size,
"essentiality": measure_essentiality,
"modules": measure_modules,
"fba": measure_fba,
"rba": measure_rba,
}
def evaluate(deleted):
return {
name: measure(deleted)
for name, measure in evaluators.items()
}
Illustrative candidates. These values explain the reporting format; they are not experimental results.