Harper Evolves

I want you to read that ti­tle as lit­er­ally as pos­si­ble. Harper is now ca­pa­ble of evo­lu­tion.

This past week, I’ve been work­ing on a sys­tem that should al­low us to han­dle more com­plex gram­mat­i­cal cases and con­texts, faster. I be­lieve it will im­prove our abil­ity to add new gram­mat­i­cal rules to Harper by some­where be­tween 500% and 1,000%.

To top it off, this sys­tem does it with­out slow­ing Harper it­self down or in­creas­ing the mem­ory foot­print.

Let’s get into it.

The Problem

There are sev­eral unique method­olo­gies at play when Harper goes about gram­mar check­ing. Which strat­egy de­pends on the gram­mat­i­cal rule in ques­tion. To­day, we’re in­ter­ested in ex­pres­sion rules.

For the cu­ri­ous, I have re­cently writ­ten a re­flec­tion on ex­pres­sion rules, as well as a guide for any­one in­ter­ested in pro­duc­ing them. This post, how­ever, will not re­count in­for­ma­tion I’ve al­ready writ­ten on this blog.

By count, ex­pres­sion rules make up the ma­jor­ity of gram­mat­i­cal rules Harper is cur­rently ca­pa­ble of de­tect­ing. This is be­cause they are fast, easy to write, and most im­por­tantly, easy to re­view.

There are, how­ever, oc­ca­sional hic­cups that I en­counter when tack­ling a prob­lem. The English lan­guage is tricky and of­ten it con­tra­dicts it­self. I will of­ten try to write a rule which cov­ers a cer­tain case, only to find that it does­n’t cover all cases. I can it­er­ate, but it of­ten be­comes te­dious and time-con­sum­ing.

The Solution

Last week, I threw in the towel. I was tired of it­er­at­ing cease­lessly to­wards a goal, only to have a new one to tackle af­ter that. So I de­cided I would let the com­puter it­er­ate for me.

Harper’s ex­pres­sions are es­sen­tially small pro­grams which are able to iden­tify the lo­ca­tions of given pat­terns in nat­ural lan­guage. They are con­structed at run­time, but they run ex­ceed­ingly fast be­cause they tend to be amenable to mod­ern branch pre­dic­tion. We can use this fact to our ad­van­tage.

When gen­er­at­ing an ex­pres­sion that de­tects a par­tic­u­lar gram­mat­i­cal rule, the new sys­tem (which I’ve called The Ripper) fol­lows three steps.

1. Generate N ran­dom Harper ex­pres­sions
2. Score the per­for­mance of these ex­pres­sions by test­ing them against a cu­rated dataset. The dataset con­tains la­beled rows of sen­tences that do and do not con­tain the gram­mat­i­cal rule of in­ter­est.
3. Take the best K ex­pres­sions and mu­tate them to left with L new “child” ex­pres­sions. Go to step 2.

That’s it! We’re es­sen­tially treat­ing ex­pres­sions as liv­ing crea­tures and sub­ject­ing them to ar­ti­fi­cial se­lec­tion. It works re­mark­ably well.

Since these datasets are hand­crafted (or gen­er­ated by an LLM), they don’t need to be large. Plus, the ex­pres­sions them­selves are quite fast to gen­er­ate and test, so we can do so at an ex­cep­tional rate.

My lap­top is able to churn through about 90 thou­sand can­di­dates per sec­ond, al­low­ing us to con­verge on an ac­cept­able re­sult in just a few min­utes. Given more time, it’s able to pro­duce an ex­pres­sion rule that is more ac­cu­rate than what I could write my­self.

What’s Next?

I in­tend to spend some time op­ti­miz­ing the process, par­tic­u­lar for the hu­man el­e­ment. I’d like to be able to cre­ate batches of these datasets and let The Ripper take care of them all at once, overnight or on a beefy server in the cloud.

I’d also like to set up au­to­mated work­flows for pip­ing data from an LLM di­rectly into the Ripper. Ideally, I want this sys­tem to get to a point where I can feed in­for­ma­tion from a style guide into an LLM and get a guar­an­teed func­tion­ing Harper ex­pres­sion rule out of it.