Evaluating results from LLM pipelines is time-consuming and often I'd rather poke my eye with stick instead of looking at another 100 results to decide if they are "good".

But I do it anyway and I cannot understate how beneficial it is.

Here's why you should do it:

1. You'll know when your changes are working.
2. You'll improve your LLM pipelines faster.
3. You'll build a fine-tuning dataset along the way.
4. You'll build better intuition for what does and doesn't work well with LLMs.

These benefits compound if you evaluate LLM results regularly and systematically.

By regularly, I mean every time you make a change to your LLM pipeline. A change could be a new prompt, chunking strategy, model configuration, etc.

By systematically I mean that you carefully examine your results, capture how good or bad they are, and why.

If you are not already doing this, picture me grabbing you by the shoulders and screaming "WHY NOT?!!"

Then read the rest of this post, which is a more constructive attempt at persuading you to evaluate your LLM responses.

In the course of building the city council meeting tool described here, I spent many days trying to get gpt-4-turbo to accurately identify speakers in 4-hour meeting transcripts with upwards of 50 speakers.

I started with a simple approach: feed the entire transcript into gpt-4-turbo with a prompt. The problem is that gpt-4-turbo performs tasks quite poorly on long context chunks (~40K - 100K tokens). I talk briefly about the issue in this post.

So I pursued a new strategy: slice my transcript into manageable chunks and try identifying speakers in each chunk instead.

I spent a day or two feeling around in the dark for the right chunking strategy and prompt without getting great results. I eventually asked Gabriel (my partner at Baxter) if he'd be willing to cobble together a UI to help me evaluate my results quickly.

It took a thirty minute conversation, an afternoon of his time, and it was a complete game-changer for me.

I improved the performance of my approach dramatically over the course of a couple of days: my speaker identification accuracy went from 35-50% on Tuesday to 80-90% on Thursday.

To get to that point, I evaluated hundreds of responses and changed my prompt and chunking strategy to address specific classes of problems I observed.

Here are some problems I observed and changes I made to address them that improved speaker identification accuracy:

• The LLM responses would heavily weight self-introductions, like "I'm council member Brooks-Powers.", and fail to draw conclusions from sentences like "I'd like to pass the mic to council member Restler."
  • Solution: I added directions and examples showing how to identify a speaker based on neighboring context.
• Mistranscriptions would cause issues: "Jose" instead of "Ossé", "Adrian" instead of "Adrienne".
  • Solution: I provided a list of council member names and added directions to infer mistranscriptions. The LLM starting figuring out when a name was a likely mistranscription and got many more inferences correct.
  • (If you're interested in learning about other ways to handle mistranscriptions, I wrote this post about a voice search use case involving an Italian restaurant and sommeliers.)
• Because roll calls happen so fast, speaker diarization (identifying distinct speakers in audio and giving them a label) fails badly. As such, it is not reliable to infer a speaker's identity based on them saying "Present" in a roll call. (The image showing the eval tool above shows an example of this problem.)
  • Solution: I added examples to deter the LLM from doing this in my prompt.
• In a few cases, the LLM hallucinated a council member's district and got the wrong answer: "Adams is part of District X but the speaker said District Y, so I must infer that it is not Adams.", when actually it was Adams.
  • Solution: I added the district and borough to my council member list.
• I noted that my chunks didn't always have the context required to identify a speaker.
  • Solution: I modified my chunking strategy until they did.

I did this over and over again for many classes of errors, evaluating hundreds of responses until I consistently managed to get an 80-90% accuracy rate.

These changes were all easy to make, but I didn't know to make them until I systematically reviewed my inputs and outputs. Once I did, getting better performance from my LLM pipeline took very little time.

As a bonus, I've stashed away every evaluated response so that when it makes sense for me to fine-tune a model for my task, I already have the dataset to do it.

This post shares that ~2K data points is when a fine-tuned gpt-3.5-turbo begins performing on par with an optimized prompt.

The last thing that evaluating my LLM results systematically has helped me with: I've built useful intuition around what a good prompt needs to have and what improvements are worth making now vs. later.

Today, my initial attempts at prompting LLMs work more effectively and my improvements are swift and significant. I know that a good, diverse set of few-shot examples is the highest leverage way to improve a prompt so I race to get good examples, fast.

My guesses around how I should I should chunk lengthy passages are more accurate, and I have a sense for how big those chunks should be (4-6K tokens is an anecdotal sweet spot, but up to 10K can work well in many cases).

I've picked up tricks and techniques that I use constantly, like this one about making up your own markup language to prevent hallucinations, and using chain-of-thought not only to get better answers, but to observe why the LLM did what it did so I know how it screwed up or, occasionally, how it made a surprising and accurate association.

All this is to say: if the performance of your LLM results matters for your use case, you should be systematically evaluating them. And I mean you, specifically: the person implementing the feature that relies on LLM output.

Scaling requires you to outsource this work, and you might need to eventually.

But you can get very far doing this work on your own, you will learn a ton, and you will gain important context and control over the quality of your LLM-powered feature by doing it yourself.

So do it, please!

(Or tell me why this is a pointless exercise on Twitter, Threads, or by sending me an email at voberoi@gmail.com.)

I've been using LLMs to glean information from NYC city council meetings as part of my work writing this newsletter on NYC city council activity.

For a lot of this work I write prompts and pipe text from bills, memos, and transcripts into Simon Willison's llm tool. It is incredibly handy.

Where this approach fails is when I'm using LLMs to navigate long council meetings (and, unfortunately, most council meetings are long).

My goal is to find things that are "notable" in these meetings so I can write about them. Notability is hard to define, but here are some things that might fit my criteria:

• New facts that emerge from hearings.
• Contentious exchanges between council members and a city agency.
• Surprising testimonies from entities in NYC.
• Passionate statements by council members about hot-button topics.
• Things the public does not know about, but might find interesting.

Transcripts for these meetings are regularly 40k to 100K tokens, which gpt-4-turbo's context window fits comfortably. Unfortunately, I run into two problems:

1. My output is way less useful with long contexts, which is likely due to the lost-in-the-middle problem: LLMs don't effectively use long contexts and disproportionately weight context at the beginning and end of inputs.
2. Prompts are more effective when they have the right context and clear instructions, but "notability" is hard to define and requires context around the NYC council's workings and NYC current events.

I find myself having many conversations using the llm CLI, and then reading the raw transcript/watching the video to seek neighboring context and verify answers I get. It's not that effective: I still have to read a lot and I have to get lucky in my quest for notable bits of info.

What I've really wanted for these meetings is an index that lets me browse a transcript quickly and jump to potentially high-signal segments. I want to skip procedural content, like roll calls, and jump straight to an exchange that starts with a council member's question. Or I want to browse all the public testimonies at the end and see who showed up to the hearing and why.

Here is a prototype that attempts this with two council meetings:

• A December 7th, 2023 hearing on the rat problem in NYC.
• A December 20th, 2023 city council stated meeting

Visit citymeetings.nyc to use the tool (it is not designed for mobile).

For these, I use GPT-4 to generate chapters and I worked with my parter at Baxter to glue it together in the UI you see above.

Using this tool, I can browse chapters and click on one to seek to that point in both the video and transcript. After clicking on a chapter, I can seek in a finer-grained way by clicking on a timestamp in the transcript.

That second feature is not AI, but it's important because it leaves a margin for error when LLMs inevitably mess up chapter boundaries. The chapters in the prototype need a lot of improvement, but this UX is still orders of magnitude better for research than:

• ... piping 50K tokens into llm and praying for something useful.
• ... reading a city council transcript.
• ... watching a city council meeting.

I'm wildly excited about research tools using LLMs because things like this are possible now that were not possible a year ago (GPT-4 only came out 10 months ago).

I'm also excited about how these tools can be applied to repurpose virtually all audio and video content out there for personal use

Tomasz Tunguz linked to a video in today's newsletter that I was about to watch, but I immediately bounced when I saw it was 3 hours long. I will never watch the video he linked to, but I would have spent 10 minutes browsing it using the tool I built and probably gotten what Tomasz got out of it.

I'm continuing work on this tool in service of my newsletter on city council activity and because it is gobs of fun.

I'll be releasing it for the public when it's ready. (Update: It is available now at citymeetings.nyc)

I'll also be writing about specific challenges involved in things like speaker identification, improving chapter quality, extracting pull quotes, search (semantic and otherwise), and the realities of operating software like this.

Questions? Comments? Feedback? Please send me a note!

Email me at voberoi@gmail.com or holler at me on Twitter or Threads.

Every bill that makes it to a vote in the NYC city council passes.

(One bill didn't pass in 2022. Before that, the last time a bill didn't pass was in the 90s.)

The council holds Stated Meetings twice a month to introduce new legislation and vote on bills, and the outcome of these meetings is determined by the time the agenda is up days in advance on Legistar, the council's public records system.

Stated Meetings are 90% procedural and 10% performative. Council members use whatever time they get on the floor to tout legislative achievements and explain "nay" votes they cast.

The meetings are predictable, -- everything passes! -- but the number of bills passed is surprising: the council passes dozens of bills every two weeks, passing over fifty at the last meeting.

Bills take anywhere from months to years to go from introduction to vote. Timelines exceeding one year are not unusual.

Introduction 638 from the NYPD transparency package passed two weeks ago.

It took 1 year and 4 months to come to a vote.

At some point in 2022, Councilmember Althea Stevens decided to prioritize NYPD transparency and her office worked with the council's Legislation Division to write the first draft of the law.

(The Legislation Division's Bill Drafting Manual is an interesting read!)

Then Stevens formally introduced the bill at a Stated Meeting in August 2022, where it was assigned to the Committee on Public Safety.

(Whenever a bill is introduced, it gets assigned to one of 36 committees responsible for deliberating and holding hearings on bills pertinent to them.)

A bill's public record starts the moment it is introduced. Here is 638's timeline over 16 months:

• August 2022: the bill was introduced.
• March 2023: a multi-hour hearing was held and the bill was on the agenda.
• December 2023: the bill was revised, brought to the floor, and passed.

There are 18 documents in the public record for Introduction 638 clustered around these three moments. They include every version of the bill, hearing transcripts, written testimonies, and reports with additional context and data.

Here's what all this looks like on Legistar:

With this data you can:

• Find out what a bill does by reading its text and summaries.
• Gather context and motivations behind a bill in committee reports.
• Learn what agencies and individuals who testified at hearings think about it.
• Find out how much a piece of legislation will cost the city by reading fiscal reports.

The vast majority of bills never make it to the floor.

Out of 1,281 bills that were introduced in the last two years, only ~20% made it to a vote. Close to 1,000 bills were drafted and then hit a snag somewhere.

Introduction 396 is one such bill. It requires preschools to maintain lead levels in drinking water below some amount determined by the Department of Health (DOH), with a yearly inspection.

Councilmember Robert Holden, the bill's sponsor, introduced 396 at a Stated Meeting in May 2022. It got assigned to the Committee on Health and then nothing happened: there were no hearings, reports, or votes.

396 seems important, but information beyond the bill's text isn't in the public records. I can't tell you how much of a risk lead poisoning is in our preschools, but a council member's office thought it might be high enough to address it with legislation.

Even when bills pass, the records don't tell us the story behind them. The public information on Legistar is sparse and lacks broader context.

But there's still a lot to discover. The council, like every legislative body in the US, puts out reams of documents that barely anyone reads.

Surprising details are buried in reports. Here are two from issues one and three of this newsletter:

• From a committee report found here: the city pays service providers so late that they keep themselves afloat with loans, paying an average of $223K annually in interest.
• From a fiscal impact report found here: noise cameras used to detect noise violations cost $35,000 each.

Bills might get revised and change materially from when they are first introduced. This happened with the bike lane bill covered in this first issue of Keys to the City Council:

• The first version enables bike lane improvements fewer than 4 blocks in length without a notice period or community board hearing, on par with other transportation infrastructure.
• The final version of the bill subjects bike lanes of any length to this red tape, unlike other transportation infrastructure.

Exchanges between council members and city agencies reveal new information. For the second issue of Keys to the City Council I poked around a hearing on small business contracts. In it, agencies share how one caterer takes advantage of NYC's bureaucracy by charging rates ranging from $3/meal to $15/meal to different agencies for the same meals.

As I read documents and build tools and techniques to navigate them -- how I spend most of my time on Keys to the City Council -- I'm able to find notable details more quickly.

I want to share some of the techniques I use to help me navigate legislative documents and hearings with AI. You can try these out at home using ChatGPT.

I pay for ChatGPT ($20/mo) so I get access to GPT-4, a more powerful language model that I use exclusively because GPT-3.5's performance on these tasks is much worse.

The prompts below use bills found on Legistar and sections of the NYC legal code found on American Legal Publishing.

Here's the prompt I use to explain what a bill does, with a section to provide context from the legal code if necessary:

Please summarize this NYC bill and explain its implications in a way that a high schooler would understand.

The bill may refer to sections in the NYC legal code. I have provided the bill and relevant sections of the legal code below.

--- THE BILL ---

Copy and paste the bill text

--- RELEVANT SECTIONS FROM THE NYC LEGAL CODE ---

Copy and paste relevant sections of the legal code

Asking ChatGPT to explain implications "in a way that a high schooler would understand" is a proxy for "keep it simple" that encodes instructions like "don't go clause by clause and explain it to me like a legal scholar" and "keep the summary high-level and use basic prose". It works well.

I'll then have follow-up questions and have a full conversation about the bill. I use questions to verify my understanding, dig into details, and ask ChatGPT to spit out clauses, verbatim, that achieve something in particular.

It's important to verify ChatGPT's answer because ChatGPT hallucinates.

Collectively, all this takes me 2-10 minutes where reading and parsing a bill alone might take me 30 minutes or more.

To understand how versions of a bill differ, here is how I prompt ChatGPT:

I will give you two versions of a NYC bill that passed, Version A and Version B. Please tell me what changed from Version A to Version B and what the implications are in a way a high schooler would understand?

--- VERSION A ---

Copy and paste the text from Version A

--- VERSION B ---

Copy and paste the text from Version B

I used this prompt + followup question to find subtle but material changes in the bike bill covered in the first issue of Keys to the City Council

I also use it to skip revisions that aren't notable and save time. The screenshot below compares both versions of Introduction 638: the changes are immaterial.

Outside using prompts to analyze bills, I've been building custom tools to find interesting information in hearings. This turns out to be a much more challenging task.

Part of this is because it's hard to articulate what "interesting information" even looks like in a hearing. To prompt language models so you get output that you want, you need to be wildly pedantic or use proxies that express your intent well enough, like "explain this to me like I'm a high schooler."

Saying "tell me surprising facts people said in this hearing" doesn't work.

The other reason this is hard is because hearings are long, on the order of 30K to 100K messily-transcribed words. Language models struggle to get useful information out of large bodies of text even when your prompt works well on smaller chunks of text.

So I'm hacking on research tools to help me navigate hearings more quickly instead of relying on GPT-4 to give me answers.

In particular, I'd like a page where I can see a video of a hearing on the top and on the bottom:

• Neatly segmented chapters of the hearing: "Roll Call", "Brooks-Powers expresses concern about NYC's rat problem in her opening statement", "An exchange about wheelie bins with DSNY", etc.
• Each chapter has an associated summary that I can skim, with relevant pull quotes.
• I can expand the transcript in each chapter if I need to skim it.
• I can click on any of these things to automatically seek to a point in a 1-to-4-hour video: a chapter, a pull quote, a single word in the transcript.

Doing this requires creating smaller transcript chunks for GPT-4 to digest, multiple steps involving different prompts, and a lot of manual evaluation to test and improve the quality of chapters, summaries, and pull quotes.

I share more about this work on Twitter and Threads if you'd like to follow along.

I'm building this tool for Keys to the City Council. I think it could be useful to reporters and government affairs folks. If you or someone you know would like to chat about it, please send me a message!

Going forward, I'm going to focus Keys to the City Council on bills and records that are interesting but not widely covered: new legislation, important nuances in bills and revisions, and context buried in hearings and reports.

In some cases I'll add to mainstream stories -- for example, sharing multiple major bills in the NYPD transparency package that were overshadowed by the one that Adams is likely to veto. Those bills, alone, should generate significant, new public information about NYPD's operations in the next 12-24 months.

I'm also going to match the council's cadence and write the newsletter every two weeks when the council votes. I'll play around with same format I used in issue 1 and issue 3, sharing new legislation along with details.

I won't cover major stories like the budget cuts in issue 2. The cuts were covered everywhere, and stories like it require context absent from public records that I don't have, that journalists gather, think, and write about all day.

It was fun to write that issue, but it's not in my wheelhouse and it took effort and time away from what I want do: poke my (AI-enabled) nose into public records and share what I find.

Questions? Comments? Feedback? Please send me a note!

Email me at voberoi@gmail.com or holler at me on Twitter or Threads.

Over at Baxter we've been working with a client to build an LLM-powered chat bot that we're deploying into Fortune 100 enterprises.

Employees at these enormous companies will chat with this bot and, uh, unfortunately I cannot share much more than that.

I recently had to ballpark how many concurrent chats we could support before we'd hit our OpenAI rate limit. I came up with a basic model and am sharing it here in case it comes in handy for others.

Here's the kind of bot for which this ballpark estimate makes sense:

• It uses OpenAI's ChatCompletion APIs.
• The user talks, the bot talks, the user talks, the bot talks, and so on...
• Every time a user sends a chat, that chat is sent to a ChatCompletion endpoint along with the entire message stack: all system, assistant, and user messages up to and including the user's message.

This seems like it holds for gobs of products and features I see in the market.

Here are assumptions the model makes:

• The concurrent chats are all fresh, new conversations as opposed to a long conversation being re-entered.
• They all start at the same time.
• We're looking for the number of these conversations that can run concurrently...
• ... without any of them running into one of OpenAI's rate limits.

Deriving a ballpark estimate

OpenAI's rate limits are comprised of two values:

1. TPM: tokens per minute.
2. RPM: requests per minute.

GPT-4’s base values for these are 40,000 TPM, 200 RPM. You are rate limited the moment you hit one of these.

This means that if 200 people log in and send a message, your service falls over immediately. Everyone will send one message, and then their next message will fail.

What we want is: what is the maximum # of users can sustain a conversation without getting rate limited?

That number, whatever it is, is far less than 200.

To get a rough estimate, you want to grab these numbers for your bot:

• The average Chat RPM: The average # of requests a regular chat session makes per minute.
• The average Chat TPM: The average # of tokens a regular chat session sends per minute.

I recommend computing these from real chat sessions your users have done:

• Chat RPM maps to the number of user role messages sent per minute in a session.
• Chat TPM takes more work. Whenever a user sends a message, you have to sum up all the tokens of all messages up to and including the user's message. Add up each of these token counts, divide them by the # of minutes the chat lasted.
• Use tiktoken to count tokens.

Between OpenAI's response times, a user pausing/thinking, and then sending a message, you're likely to get somewhere between 1-3 requests per minute per chat.

Meanwhile, because the number of tokens you send to OpenAI every time a user chats grows cumulatively, Chat TPM is your likely bottleneck and it might even surprise you how big it gets.

I recommend capping the length of these conversations at what you believe is a reasonable duration. You want to remove outliers – for example, if a user had a conversation on day 1 and then came back on day 2 to send another message.

(Unless that's the norm for your app, in which case you might not want to use this model.)

Once you have these numbers, the # of users who can sustain a conversation concurrently is the lesser of:

• OpenAI RPM Rate Limit / the average Chat RPM
• OpenAI TPM Rate Limit / the average Chat TPM

That's it!

The longer your user's conversations last, the fewer of them you'll be able to sustain concurrently. Again, this is because of the cumulative growth in the tokens you send over the course of a conversation: whenever you send a ChatCompletion request, you're sending over the entire conversation every time.

Questions? Comments? Feedback? Please send me a note!

Email me at voberoi@gmail.com or holler at me on Twitter or Threads.

I wrote this tweet about my Amazon internship in 2007 as I rolled out of bed yesterday morning and it went viral.

How fun!

That internship was my first work experience overall in software and I got incredibly lucky being placed on the Similarities team.

One could do way worse as a 20-year old landing an internship at Amazon: the Similarities team was doing cutting edge recommendations and experimentation work, I got to deploy and see feedback from my work on-site every week, and I was paired with a kind and helpful mentor on a great team.

My experience that summer is the reason I continued doing data & systems work in college and after I graduated.

The Similarities team was responsible for producing the dataset that powered "Customers who bought this also bought". The dataset was also used in personalized recommendations they'd surface to customers elsewhere: on-site and in emails.

~20% of revenue was attributed to similarities at the time if I remember correctly (my mentor was kind enough to terrify me with an estimate of the revenue Amazon lost from an an outage I initiated). So they were an effective and important part of the site. But there were still a number of unintuitive similarities that would appear in the "Customers who bought this also bought" widget.

While there was a long tail of random issues in different product categories, – Amazon had begun a rapid expansion beyond books and was working on fixing them – the biggest problem, by far, was Harry Potter.

More specifically, in the summer of 2007 it was Harry Potter and the Deathly Hallows.

It would show up as a similarity everywhere. Like, you'd be on Amazon buying a mop and the similarities widget would show a recommendation for Harry Potter and the Deathly Hallows, followed by Pine-Sol and a bucket.

The team computed item-to-item similarities using collaborative filtering with customer order baskets as the input. Put simply, if customers bought products A and B together frequently enough, then Amazon would present A and B as similar items.

But what happens when the same product appears in virtually every order basket? The Harry Potter problem.

The similarities team deployed me to one idea they had to address the Harry Potter problem: could they use feedback from users to cull unintuitive similarities?

Amazon got feedback in two ways:

• Implicitly: clickstream and conversion data from the similarities widget ("Customers who bought this also bought")
• Explicitly: users could provide feedback on personalized recommendations they received in emails/on-site. I don't know if this still exists.

So I spent the summer trying to use the output of Amazon's collaborative filtering algorithm + all this clickstream/conversion/feedback data to address unintuitive similarities. The thinking was that if a similarity was unintuitive, then presumably it'd underperform by some measure based on user feedback.

My primary target was Harry Potter and the Deathly Hallows: it stuck out like a sore thumb and it was an easy way to see if an approach was working qualitatively.

Amazon similarities were served by a Berkeley DB (BDB) file at the time. BDBs are embedded key-value stores – a file you can ship around with a format optimized for key-value lookups. Amazon would crunch numbers and emit a new similarities BDB nightly or weekly (I don't remember which).

The similarities BDB mapped ASINs (product IDs in Amazon parlance) to lists of ASINs, like this:

B00P0H6836: B07K8Y6CMP, B07K8RWVF9, B07K8S9ZQZ, B00P0H6836

That's the ASIN for this great cat litter mapped to different sizes of pee pad refills in the "Compare with similar items" section. This is also an example of an unintuitive similarity: if I use clumping litter for my cat, it is unlikely that I will use pee pads too.

So each week I'd write a Perl script to crunch clickstream/conversion/feedback data and then remove or reorder some of the mappings in the BDB file based on my algorithm that week. We'd now have two sets of similarities:

• A: the similarities emitted by Amazon's collaborative filtering algorithm
• B: vikrams_algorithm_of_the_week(A), Amazon's similarities from A with mappings removed or reordered using whatever approach I was trying.

Then I'd send an email to the team with a link to a CGI script I wrote that allowed us to qualitatively assess B against A. It was a little web page with an input box at the top where you could enter an ASIN and it would show you similarities from A compared to similarities from B.

We'd exchange emails about the quality of my similarities or talk about them in a meeting. Then my mentor would decide whether or not we would push it to production.

Most weeks we'd push something to production and A/B test it. I don't know what percentage of the site saw my similarities, but I suspect it was low: it would take a few days for us to get conclusive results and even in 2007 Amazon got tons of traffic.

I threw a lot of things at the wall.

Two approaches that I remember relied on the idea that users will simply click more on items on the left side of a page. It is well-known that page position is a massive determinant of clickthrough rates. The "Customers who Bought this Also Bought" widget was laid out from left to right, so items in the first slot had a baked-in "boost".

So, if that is true yet we see a similarity in the first slot "underperform", maybe we should reorder it. Here are two different ways I did that:

1. A basic approach: if an ASIN in slot 1 has a lower clickthrough rate than an ASIN in slot 2, swap slots 1 and 2.
2. A more complicated approach: if an ASIN in slot 1 has a statistically lower clickthrough rate compared to the ASIN in slot 2, swap slots 1 and 2.

I don't remember the specifics for #2. It might have been something like:

1. Get the difference in clickthrough rate between slots 1 and 2.
2. See where it falls on the distribution of "difference in clickthrough rate between slots 1 and 2".
3. Decide it's underperforming if it is some distance away from the mean.

I spent the entire summer trying stuff like this and published a log of what I did on Amazon's internal wiki.

Some takeaways I recall:

• None of these approaches improved conversions over the baseline: I do remember thinking my similarities were better in some of our qualitative assessments, but, site-wide, customers voted with their $ and showed that they were worse.
• Simple approaches are better than complicated ones: any time I got fancy, like in the more complicated approach above, the performance of my similarities tanked.
• Invalidating a bunch of approaches and documenting them is still useful: with this work, the team had a set of hypotheses they could either ignore or approach again in the future with more clarity. It's a great project to deploy an intern to.
• None of these approaches come close to solving the Harry Potter problem: that book's Amazon detail page will be forever etched in my brain.

There are many wildly qualified people who have worked on similarities and recommendations at Amazon, Netflix and elsewhere the last 15 years. Greg Linden started and led a lot of the personalization work at Amazon and has written about some of it on his blog.

I don't know if Greg was there in 2007. My mentor and the team's manager during my internship keep a much lower profile, but were also extremely talented.

👋 to Wes & Brent if you see this! Thank you for setting me up with a delightful and impactful experience 16 years ago.

Questions? Comments? Feedback? Please send me a note!

Email me at voberoi@gmail.com or holler at me on Twitter or Threads.

I recently prototyped a hands-free inventory counting system for sommeliers at a popular Manhattan Italian restaurant with Gabriel, my partner at Baxter.

I know the general manager (GM) at this restaurant – henceforth referred to as Ristorante – personally and he hates inventory counts. Most restaurant GMs do. They're labor-intensive yet extremely important: regular inventory audits are critical for restaurants to control their margins.

Ristorante can clear well into 5 figures of revenue in a day. And its GM, being a skilled and responsible operator, requires his team to do an inventory audit every month. So Ristorante's two sommeliers arrive early in the morning on the 1st of every month to count over 1,500 different wines stored across 3 bars, a cellar, a fridge, and a storage room. It takes them over 6 hours, and the task bleeds into daily operations.

It's painful.

It's also just the kind of messy real-world problem that Gabriel and I want to try to solve for a market: is there any way we could cut the time it took these sommeliers to count inventory by half?

I popped into Ristorante on April 1st, a busy Saturday, to observe an inventory count.

Ristorante's wine storage is organized but cramped. At the bars, many wine bottles sit on high shelves and sommeliers might be standing precariously on a stool or counter. Their hands are often not available – they're moving boxes, bottles, or holding a bottle up so they can identify what it is.

Counting wine looks something like this:

1. Identify the box/bin or a bottle of wine you want to count. Count it.
2. With a laptop or phone next to you, look up the wine you're looking for in Bevager, Ristorante's inventory management system.
3. Enter the count and save it.

Each wine takes anywhere from 15-60 seconds, of which 80% of the time goes to step 2: looking up the wine in Bevager. This is due to a combination of the following:

• Context switching: from using one's arms and being perched somewhere, to using a laptop or phone.
• Wine names are entered into Bevager inconsistently: in some cases they use the wine name, in others they use the producer. These names might be on the front or back of the wine.
• Words in wine names are frequently repeated: "chateau", for example.
• Vintages: you might need to pick the right vintage from 5+ entries.
• Bevager bugginess/search quality: Bevager is a fine system, but its inventory audit feature could use some love.

These are all solvable problems that take up a significant percentage of the time it takes to inventory one wine bottle.

So we decided to start by helping a sommelier retrieve a wine in Ristorante's inventory system quickly and accurately without having to use her hands, with her voice.

Prototyping voice search for wines in 3 days

A critical component of our prototype was a voice search feature that allowed a sommelier to say the name of a wine and retrieve it correctly from over 1,500 SKUs in her inventory.

There are a bunch of obstacles to getting this kind of voice search to work well.

• Getting accurate transcriptions, even with state of the art models, is hard. We have to deal with French and Italian wines, various accents, and restaurant background noise.
• Inaccurate transcriptions are different from typos and misspellings. Handling them requires a different set of tricks.
• The user's not at a keyboard. Auto-complete is an incredible feedback mechanism, but we don't have access to it.
• There is exactly one relevant record. A sommelier's search for the wine they're looking for has only one matching record. It must be a top result, otherwise the search failed.

Perhaps the closest analog to this search use case is when you ask your phone to call a contact (e.g. "Google, call Katie."). It turns out that this is pretty challenging!

Our goal was to validate feasibility and demand for a solution, so we needed to show something working well enough quickly.

I also wanted this to be easy to understand and operate: I didn't want to have to (re-)learn, configure, and tune Solr, ElasticSearch, or Typesense. Besides, I only had about 1,500 records and these tools aren't really designed to deal with the search use case I describe above, out of the box.

I managed to cobble together workable voice search in about 3 days using off-the-shelf components, a bag of information retrieval tricks, ~300 lines of Python, and a bunch of trial and error. It's imperfect but it's quick to implement, simple to operate, and it works with many classes of transcription errors with plenty of avenues for improvement.

• Code: The codebase is on Github.
• Demo: You can give it a try on Streamlit Cloud.
• Is this available? What happened next? Can you make this for me? I answer these questions in the Appendix.

Here's how it works!

A summary of my approach

I use OpenAI's Whisper for audio transcription and DuckDB to store and query my search index.

DuckDB's full text search (FTS) extension easily handles the happy path: accurate transcriptions. The FTS extension is easy to use, but it does not handle misspellings or, in my case, poorly-transcribed audio.

OpenAI's Whisper model is impressive, but:

• There is background noise in restaurants.
• Non-native speakers pronounce French and Italian wines poorly.
• Both of these issues affect audio clarity and, in turn, transcription quality.
• Even without these issues, Whisper is not perfect.

So my implementation needs to handle inaccurate transcriptions.

While there's plenty of prior art on handling misspellings in search, the same techniques don't work as well with bad audio transcriptions. This is because inaccurate transcriptions don't look like misspelled words. They often look like gibberish – made up words, or strings of words that sound like the audio but don't make sense together.

So I built two of my own search indexes in DuckDB to handle "mistranscriptions" using Metaphone, a phonetic algorithm that maps similar-sounding words to the same pronunciation.

In total, I have 3 indexes: 1 full text search index on wine names, and 2 that use Metaphones, which I'll cover in greater detail below

At query time I do the following:

1. Query the indexes in 5 different ways. Each method excels at different kinds of queries or transcription errors. I get 10 results from each method, increasing the likelihood that the wine the user is looking for is in my result set.
2. Rank all those results using text similarity. I get the Jaro-Winkler similarity score between each result and the transcription. This tends to bubble the result up to the top 5.
3. Return the top 5 ranked results. I'd say 80%+ of the time the result I was looking for ended up in the top 5, and it fared well with "adversarial" audio (comically bad accents, yelling in the background, etc.)

What do inaccurate transcriptions look like?

Inaccurate transcriptions are usually close to how the words actually sound.

Let's say we have a wine in our inventory called Chateau Champignon.

Here are some potential transcriptions of "chateau":

• shadow
• shatto
• chat oh

Here are some potential transcriptions of "champignon":

• champagne on
• shomp inyon
• champ onion
• sham pig non

We may end up with any permutation of transcriptions for "chateau" and "champignon". For example:

• shadow champagne on
• chat oh shomp inyon
• shatto sham pig non

Traditional search techniques to handle misspellings fail spectacularly on these kinds of errors. None of them look like misspellings or typos.

But they do sound the same, and this is where phonetic algorithms come in.

You can map inaccurate transcriptions to the same string using phonetic algorithms

Phonetic algorithms map words to pronunciations.

Different phonetic algorithms have different goals in mind, but there is a whole class of them that is designed to map similar-sounding words to the same pronunciation.

The earliest one of these is called Soundex, which was developed in the late 1800's and patented in 1920, well before the advent of computing!

Why? To map similar-sounding surnames to each other for the US Census. The history here is really neat, and you can read this post by Luke Otwell to learn more if you're interested.

In my implementation I used Metaphone, a successor to Soundex, for which there is an open-source Python implementation in pyphonetics.

Metaphone maps chateau champignon to XTXMPNN.

Here's how Metaphone maps our transcriptions of Chateau Champignon above:

chateau

• shadow: XT
• chat oh: XT
• shatto: XT

champignon

• champagne on: XMPNN
• shomp inyon: XMPNYN
• champ onion: XMPNN
• sham pig non: XMPNN

various permutations of the above

• shadow champagne on: XTXMPNN
• chat oh shomp inyon: XTXMPNYN
• shatto sham pig non: XTXMPNN

Almost all of these map directly to the same Metaphone as Chateau Champignon!

To put this insight to work, our code creates two additional indexes: the Exact Metaphone Index and the Metaphone Token Index. These indexes are constructed in index.py.

The two Metaphone-based indexes

Assume we have three wines in our inventory:

1. Chateau Champignon
2. Cavalleri Collezione Esclusiva Chardonnay
3. Chateau la Bridane Saint Julien

Here's how we construct our two Metaphone indexes on those wines.

1. The Exact Metaphone Index

In this index we map the Metaphone for each wine's full name to itself:

• XTXMPNN → Chateau Champignon
• KFLRKLSNSKLSFXRTN → Cavalleri Collezione Esclusiva Chardonnay
• XTLBRTNSNTJLN → Chateau la Bridane Saint Julien

This index is just a 1-to-1 mapping. It allows us to reverse look up a metaphone to a wine's full name as it exists in our index.

2. The Metaphone Token Index

In this index we tokenize each wine name, get the Metaphone for each token, and construct an index on those tokens.

Here's what the first step looks like:

1. Chateau Champignon → XT XMPNN
2. Cavaelleri Collezione Esclusiva Chardonnay → KFLR KLSN ESKLSF XRTN
3. Chateau la Bridane Saint Julien → XT L BRTN SNT JLN

Let's call these "Metaphone strings". Each token in the string is the Metaphone for a token in the original wine name. These strings are what we index.

Assuming that 1, 2, 3 are IDs that map to the wines in the list above, the Metaphone Token Index looks like this:

• XT → [1, 3]
• XMPNN → [1]
• KFLR → [2]
• KLSN → [2]
• ... and so on.

Conveniently, this is just a regular full text search index on the Metaphone strings above. So we can use DuckDB's full-text search extension again, saving the work to write code to construct or query the index.

This index allows us to reverse look up Metaphones for individual words in our transcript.

For example, a speaker might say only "champignon", for which we get an inaccurate transcription like "shampinon". Or a speaker might say 3 words in a wine name, but two of them are transcribed entirely incorrectly while the third has a Metaphone match.

This index gives us the means to salvage an inaccurate transcript as long as there's a Metaphone match in it, somewhere.

Five query-time approaches

Combined, the following approaches are greater than the sum of their parts. Individually, they excel at dealing with different kinds of queries and transcription errors.

Each of the query methods is implemented in search.py.

Let's add one more wine to our index for the following explanations. There are now 4 wines in our inventory:

1. Chateau Champignon
2. Cavalleri Collezione Esclusiva Chardonnay
3. Chateau la Bridane Saint Julien
4. Guy Breton Morgon

Here are the five query approaches we use.

1. DuckDB Full-Text Query

This was the first one I implemented, and it uses DuckDB's full-text search extension.

Under the hood, DuckDB's FTS extension implements BM-25, a widely-used ranking function.

It constructs the index with some basic defaults for English: a list of 571 stopwords, the Porter stemmer, lowercasing all text, ignoring all non-alphabetic lowercase characters, and stripping accents.

Pros

• BM-25's ranking algorithm performs well: a query for "chateau champignon" will rank Chateau Champignon first, followed by the other hundred that include "chateau".
• It works well as long as the most unique words of the wine name are transcribed accurately. For example, "shadow champignon" will likely return "Chateau Champignon", but "chateau shampinyon" is a crapshoot because there are hundreds of wines with "chateau" in their name.

Cons

• It fails spectacularly on inaccurate transcriptions, usually returning zero or irrelevant results.

2. Exact Metaphone Query

Here, we do a reverse lookup for the transcription's Metaphone in the Exact Metaphone Index I describe above:

1. Get transcription metaphone: "shadow champagne on" yields XTXMPNN
2. Reverse-lookup: XTXMPNN yields the record for Chateau Champignon.

Pros

• Works with inaccurate transcriptions.
• High precision: it tends to match the exact wine the user is searching for, and nothing else.

Cons

• The user must say the entire wine as it exists in our index. If they just say "champignon" instead of "chateau champignon", we are out of luck.
• Fails when a transcription's Metaphone does not match. An example is the Metaphone for "shadow shomp inyon": XTXMPNYN, which has a "Y".

3. Metaphone Token Query

Here, we first form our query. Let's say the speaker is retrieving Chateau la Bridane Saint Julien.

They say only "julien bridane", but they incorrectly pronounce each word. It is transcribed as "julian breedan".

1. Tokenize the transcript: "julian breedan" becomes ["julian", "breedan"]
2. Get the Metaphone for each token: ["julian, "breedan"]becomes ["JLN", "BRTN"]
3. Join the Metaphones: ["JLN", "BRTN"]becomes "JLN BRTN"

Then we query the Metaphone Token Index described above with our query.

Because our query contains "JLN" and "BRTN", the wine Chateau la Bridane Saint Julien will rank highly. Its tokens map to: ["XT", "L", "BRTN", "SNT", "JLN"].

Guy Breton Morgon will also rank. Its tokens map to ["K", "BRTN", "MRKN"].

Recall that we built this index using DuckDB's full-text search extension, so we query it with the extension too.

Pros

• Works with inaccurate transcriptions.
• Works when speakers partially say the name of a wine.
• Works when the order of the words spoken do not match the wine's record.

Cons

• This approach sometimes yields many irrelevant results that have similar-sounding words in their names.
• Fails when a transcription's Metaphones do not match.

4. "Similar Token Metaphones" Query

Methods 1 to 3 handle:

• Accurate transcriptions
• Inaccurate transcriptions with matching Metaphones

This takes us far! But I would still get transcriptions without any matching Metaphones and I wanted to handle those.

I attempted a number of approaches, all using Levenshtein edit distance in creative ways on increasingly worse transcriptions. All of them worked.

The catch? They also introduced a lot of noise: the worse a transcription, the more permissive I had to be, which meant that my result set would also include lots of wines that looked and sounded nothing like the wine I was retrieving.

In information retrieval parlance, my search recall suffered: I was retrieving an ever-higher percentage of irrelevant records.

I had a prototype to ship, so I settled with a basic method that:

1. Didn't return a torrent of random records.
2. Could handle one extra, absent, or incorrect consonant that caused a token to generate a different Metaphone. For example, "bribane" maps to BRBN, while "bridane" – a token in our index – maps to BRTN.

Here's how it works. Let's say the speaker is retrieving Chateau la Bridane Saint Julien (Metaphones: XT L BRTN SNT JLN).

They say "bridane saint julien", but we get a really bad transcription: "brenton sane julia", whose tokens map to ["BRNTN", "SN", "JL"].

We're out of luck here with methods 1 to 3. Each will return zero results because we have no matching tokens nor matching Metaphones.

A "Similar Token Metaphone" query does the following:

1. Tokenize the transcription: "brenton sane julia" turns into ["brenton", "sane", "julia"].
2. Get all tokens in our index that are exactly 1 edit distance away from each token in our query: for "brenton" this is ["breton"], for "sane" this is [] (an empty set), for "julia" this is [] (an empty set). So we get ["breton"].
3. Join all tokens from step 2: ["breton"] becomes "breton". If we had more than one token, we'd join all of them with a space.
4. Use the string from step 3 to run a Metaphone Token Query. Our input to the query method described above is "breton".

Because the Metaphone for "breton" is BRTN we get two records, one of which is our target wine:

• Chateau la Bridane Saint Julien (Metaphones: XT L BRTN SNT JLN)
• Guy Breton Morgon (Metaphones: K BRTN MRKN)

Using a Metaphone Token Query in Step 4 instead of a DuckDB Full-Text Query casts a slightly wider net, which increases the likelihood that we catch the result we want when all our other query methods have failed.

In my limited observation, it worked spookily well without returning lots of irrelevant results. It is a total delight to read an awful transcription like "brenton sane julia" after you speak yet have it retrieve the record you're looking for.

Pros

• Might succeed even when there are no matching Metaphones in a transcription.

Cons

• Might return a lot of irrelevant results.

5. "Metaphone Substring" Query

I added this final query approach to handle exactly one class of transcription error: transcriptions that break one word into multiple words. This happened fairly frequently.

Let's say the speaker is retrieving Chateau Champignon, they say "champignon", and the transcription we receive is "champ onion".

Query approaches 1 through 4 all fail:

1. There is no wine that matches the tokens "champ" or "onion".
2. The Exact Metaphone for "champ onion" is XMPNN, for which there is no match in the Exact Metaphone Index.
3. The Metaphone Tokens for "champ onion" are XMP and ONN, for which there are no matches in the Metaphone Token Index.
4. There are no tokens 1 edit distance away from "champ" and "onion"

It turns out that many of these cases have Exact Metaphones that are substrings of their target wine. In this case:

• The Exact Metaphone for "champ onion" is XMPNN.
• The Exact Metaphone for "chateau champignon" is XTXMPNN.

... so a substring search in our Exact Metaphone Index succeeds where all our other query methods have failed.

Pros

• It's simple.
• Handles a transcription error that happens frequently.
• Doesn't return a lot of irrelevant results.

Cons

• Doesn't help with anything other than this one class of error.
• Doesn't always work: "shomp inyon" maps to "XMPNYN".

Ranking results from all five approaches using Jaro-Winkler similarity

When we execute all five of our query approaches:

• We don't know which approach, if any, has the result the speaker is looking for.
• Each approach might return multiple results.

So how do we surface the target wine from all these results?

It's safe to assume that the transcript we receive is similar, by some measure, to the speaker's target wine. If it's not, then the transcript is probably too inaccurate – would a human be able to figure out which wine the sommelier is referring to?

The challenge here is determining an objective measure that consistently brings the target wine into our top 5 results. Doing this well requires data from real users and time to experiment, neither of which we had.

Aiming for a quick solution, I tried using text similarity using whatever was available off-the-shelf using DuckDB.

It turns out that Jaro-Winkler similarity works well enough for our purposes.

My implementation:

1. Gets up to 10 results from every query approach.
2. De-duplicates the set of results, because the same result might appear from multiple approaches.
3. Calculates Jaro-Winkler similarity between each result and the transcription.
4. Returns the top 5 ranked results.

This is a workable implementation, but if you play around with the demo you'll observe it fail in basic ways, like ranking the target wine 5th when it seems implausible that the 1st, 2nd, 3rd, or 4th results are correct.

The problem with using text similarity is that we're discarding everything we know about our query approaches and the kinds of results they return. For example, if we get results from a DuckDB full-text search, it means the transcript contains correctly-spelled tokens in our search index, which increases the probability that we have an accurate transcript. That's information we could use to rank our search results!

How can this be improved?

With lots of experimentation! It helps enormously to have data from real users searching for wines.

In a real setting, I'd want to:

• Know what percentages of searches are successful over time.
• Have a set of (transcript, target wine) pairs that I can test against.
• Run A/B tests pitting search algorithms against each other.

Alas, we did not promote this prototype to production.

If I spent more time on this voice search implementation, here are some of the things I might try.

Ranking results: scores, weights, and phonetic algorithms

• Weight results from query approaches differently.
• Come up with a way to score results phonetically.
• Give higher scores to results if they surface in multiple approaches.
• Use different, or multiple phonetic algorithms for the task.

Using LLMs

• Use an LLM to surface the likeliest wines. I tried this briefly and couldn't get it to work well, but it has promise.
• Use an LLM to generate plausible mis-transcriptions of every wine. (GPT-4 generates great, plausible transcriptions). Index all of these.
• Use the mis-transcriptions from the above to fine-tune an LLM to do this task.

Appendix

Is this product live? If not, will it be?

No, and probably not. Everyone hates inventory counts, but this was not a pressing enough problem for the GM at Ristorante or the 10 wine stores, meat/cheese shops, and restaurants I spoke with.

In the time following the week we spent building our initial prototype, we did not gather enough evidence for us to continue working on this product.

Can you build this, or something else, for us?

Yes.

I co-own Baxter, a product development and contracting company, with Gabriel Garrido. We're a two-person team of seasoned engineers and we've built software and teams at numerous early stage startups.

Questions? Comments? Feedback? Please send me a note!

Email me at voberoi@gmail.com or holler at me on Twitter or Threads.

Ten years ago, while starting the Data Engineering team at Harry’s, I wrote a suite of cohort analysis queries that looked more-or-less like the queries in this post.

The success of the razor and blades model hinges on high customer retention so we tracked it religiously from day one. Retention was so critical at Harry’s that I even wrote a haiku about it once.*

I wrote 15-20 permutations of cohort queries that we would analyze regularly. At Harry’s we cut our cohorts in a bunch of ways: the channel customers came from, the contents of their first order, age/gender, geography, etc. We analyzed account creation -> 1st order, 1st order -> 2nd order, 2nd order -> 3rd order separately.

There were a lot of charts. We wanted to compare them and see how they changed week-over-week and month-over-month.

I could have sent our data to Mixpanel at the time, but it didn’t allow us to explore our data this way. So I hand-rolled a lot of SQL queries and my colleague analyzed the data in Excel. It was cumbersome and time-consuming, but it was a critical analysis for the business.

This year I was retained as a fractional Head of Product for a long-time client and this summer I took a few days to dive into my client’s retention metrics. They have a loyal base of regular users and I wanted to figure out how they differed from folks who churned. So I reached for my trusty friend: the cohort analysis!

Imagine my surprise when my options were no different than they were a decade ago:

1. I can send my data to tool like Amplitude, Mixpanel, or Heap and use its tools.
2. I can write SQL and visualize data in Excel or a BI tool.

I didn’t like either of these options ten years ago! I still don’t.

While product analytics suites provide useful tools for exploratory analyses, I usually need to drop down to SQL to answer common follow-up questions. And ensuring accuracy is challenging: the data that ends up in these tools is frequently suspect because event instrumentation is so brittle. Last week I came across Olga Berezovsky’s feedback on Amplitude after its most recent conference and it resonates — Amplitude and its competitors don’t serve me well when I’m doing deeper analyses and I can’t rely on their accuracy.

Meanwhile, I love the flexibility I have when I’m writing SQL: I can query my data however I'd like to. I can clean it up, run spot checks, and write data quality tests to make sure my analysis is correct. But SQL queries for funnel and cohort analyses are challenging to write correctly and scale. Exploring funnels and cohorts this way — asking follow-up questions like, “Why is our March cohort so much more active than our February cohort?” — is time-consuming and I miss out on the interactivity I get from product analytics tools.

I want to be able to analyze behavioral data with the affordances that existing product analytics tools provide. But I don’t want to be shackled to those tools.

The tool I want sits in a happy middle:

• It’s interactive, like product analytics tools. I want to select parameters for my funnels and cohorts and get charts. I want to click around to answer follow-up questions.
• I can use the data I have. I don’t want to send the data to a third-party. I want to use the data I have in my application database, data warehouse, or on my local machine.
• It’s SQL-native and integrates with my workflows. I want to generate queries for 90+% of the charts I explore so I can use them in my BI tool, data pipeline, or notebook.
• I can go deep without having to write SQL. I want to be able to answer questions and explore data well beyond the point that product analytics tools fall short.

I want this to exist! So I'm working on it.

If you analyze behavioral data and the above resonates, I would be delighted to speak with you. Please say hello!

*You can read about my pursuit of poetry in the workplace on my secret sandwich blog. (Currently on hiatus.)

Questions? Comments? Feedback? Please send me a note!

Email me at voberoi@gmail.com or holler at me on Twitter or Threads.

I came across Roaring bitmaps when I learned about this fun hack to do retention analyses at scale with bitmaps. Using Roaring bitmaps instead of traditional bitmaps in that application reduced memory usage from ~125GB to 300MB, an impressive 99.8% savings.

But... how?

You can learn about Roaring bitmaps over two research papers:

1. This one proposes the data structure.
2. This one introduces a critical optimization.

In this post I briefly describe what bitmaps are, what they're used for, and what Roaring bitmaps solve that traditional bitmaps don't. Then, I distill the high-level structure of Roaring bitmaps and how they work, one step at a time.

Roaring bitmaps employ a number of algorithms, techniques, and heuristics that I won't go into in detail. They also offer some operations beyond the ones I describe. These details are not critical to understanding the basic internal structure and operation of Roaring bitmaps which is the focus of this post.

Let's begin!

What are bitmaps and what are they used for?

Bitmaps are arrays of bits used to store sets of integers.

They work by setting the Nth bit when an integer N is in the set, as illustrated in Figure 1.

By storing sets of integers this way, bitmaps can take advantage of extremely fast bitwise-AND and bitwise-OR CPU instructions to compute set intersections and unions.

It turns out that fast set intersections and unions are critical for many search and database applications. Various operations exist in search and database indexes that boil down to having two sets of integers and needing to intersect or union them quickly.

Take an inverted search index, for example:

• You've indexed billions of documents. Each document has an integer id.
• The index maps terms to a set of documents in which they appear. For example, the term pigeon appears in documents with these ids: {2, 345, 2034, ...}.
• Queries that search across terms use set operations. In order to resolve a search query like carrier AND pigeon you need the intersection of the set of documents that contain carrier and the set of documents that contain pigeon.
• Bitwise operations can perform these set operations quickly. If you represent sets of document ids as bitmaps, the query above is a bitwise-AND.

Columnar databases use set operations similarly for certain classes of queries.

If you'd like to dive into a use case outside search and databases, a previous post I wrote discusses how bitmaps can be used to analyze user retention for SaaS products.

Unfortunately, bitmaps suffer from awful compression in common cases involving very large sets of integers – scenarios that appear frequently in the use cases I just described.

Recall the figure I cited at the beginning of the post:

Using Roaring bitmaps instead of traditional bitmaps in that application reduced memory usage from ~125GB to 300MB, an impressive 99.8% savings.

That's the problem with bitmaps, and I'll walk you through why this happens shortly.

What are Roaring bitmaps?

From roaringbitmap.org:

Roaring bitmaps are compressed bitmaps. They can be hundreds of times faster.

A great, pithy marketing statement on the Roaring bitmap website! Let's expand on it a wee bit.

Roaring bitmaps are just optimized bitmaps, which I'll refer to henceforth as "traditional bitmaps".

Both traditional and Roaring bitmaps offer a set data structure for integers. You can insert integers, check the existence of an integer, and get the intersection and union of two sets of integers.

Roaring bitmaps offer better compression than traditional bitmaps. Importantly, they do so without significantly sacrificing the performance of set operations.

roaringbitmap.org boasts an impressive list of OLAP databases and search systems that use Roaring bitmaps under the hood. These are all applications that:

• ... need to store large sets of integers
• ... in as little memory as possible
• ... and execute fast set operations.

What problem do Roaring bitmaps solve that traditional bitmaps don't?

When a set is sparse, traditional bitmaps compress poorly.

Recall that traditional bitmaps will set the Nth bit when you add an integer N to it (see Figure 1).

Let's say you have an empty traditional bitmap to which you add the integer 8,000,000. Here's what will happen:

• It will allocate 1,000,000 bytes.
• It will set the 8,000,000th bit.

This is illustrated in Figure 2.

Why is this bad?

• Your set has 1 integer.
• An integer takes up 4 bytes.
• Your traditional bitmap has allocated 1 megabyte.

That's 6 orders of magnitude more memory than you need.

Whoops!

Roaring bitmaps solve this problem. Importantly, they do so while maintaining fast set operations. This is what makes Roaring bitmaps special.

Prior research attempts to solve poor compression in bitmaps achieve impressive results too, but at the cost of efficient set operations.

How do Roaring bitmaps work?

There isn't one deep insight that allows Roaring bitmaps to perform well. But there is a lot of stuff going on that is greater than the sum of its parts.

The following builds up an understanding of Roaring bitmaps one concept at a time.

Part 1: how Roaring bitmaps are represented in memory

All 32-bit integers are partitioned into contiguous chunks.

Each chunk shares the same 16 most significant bits.

As shown in Figure 3, the partitioning scheme used by Roaring bitmaps ensures that an integer will always belong to the same chunk of 2^16, or 65,536 consecutive integers.

Note: there are 64-bit implementations of Roaring bitmaps, but this post does not go into them. See CRoaring, this native Go implementation, and, uh, this paper written in French (if you find a translation, please let me know).

Integers in the same chunk are stored in containers.

Chunks are how integers are logically partitioned in Roaring bitmaps. All integers that belong to a chunk are physically (in memory) stored in the same container.

Figure 4 shows examples of three different containers for three different chunks.

A chunk will always only have one container in a Roaring bitmap, defined by the 16 most significant bits of all the integers in the chunk.

If your program inserted the first 1,000 multiples of 62 into a Roaring bitmap, then they would be end up in the left-most container in Figure 4. That container's cardinality would be 1,000.

If you later inserted the integer 63, it would end up in the same container. The container's cardinality would then be 1,001.

As you'll see next, the cardinality of a container determines how it will be represented in memory.

Sparse containers contain <= 4,096 integers. These are stored as sorted packed arrays.

Two of the containers in in Figure 4 are sparse (with cardinalities 1,000 and 100) so they will be stored as sorted packed arrays of 16-bit integers.

By packed, we mean that we will be packing 32-bit integers into 16-bit integers as shown in Figure 5.

Packing integers is possible because each container can store at most 2^16 distinct integers. To get the original 32-bit integer in a sparse container, we have to unpack it by combining the 16-bit integer with its 16 most significant bits.

These arrays are dynamically allocated so the memory used by a sparse container grows as it accrues integers.

Dense containers contain > 4,096 integers. These are stored as bitmaps.

One of the containers in Figure 4 is dense (with cardinality 2¹⁵) so it will be stored as a traditional bitmap.

Dense containers are bitmaps containing 2^16 bits (8 kilobytes), allocated outright. The Nth bit in the bitmap maps to the Nth integer in a chunk.

A first-level index points to all containers. The index is stored as a sorted array.

The first-level index stores the 16 most significant bits for each container in the Roaring bitmap along with a pointer to the corresponding container.

The index is stored as a sorted array and grows dynamically as new containers are added to the Roaring bitmap.

Part 2: how set operations work with Roaring bitmaps

Integer insertion varies by container type and may cause a container's type to change.

To insert an integer, N, get N's 16 most significant bits (N / 2^16) and use it to find N's corresponding container in the Roaring bitmap.

Insertions in array and bitmap containers work differently:

• Bitmap: set the bit at N % 2^16.
• Array: insert N % 2^16 in its position in the sorted array.

Insertions may change the container type. If an array container has 4,096 integers, first convert it to a bitmap container. Then set the bit at N % 2^16.

If a container doesn't already exist then create a new array container, add it to the Roaring bitmap's first-level index, and add N to the array.

Checking for existence varies by container type.

To check if an integer N exists, get N's 16 most significant bits (N / 2^16) and use it to find N's corresponding container in the Roaring bitmap.

If the container doesn't exist, then N is not in the Roaring bitmap.

Checking for existence in array and bitmap containers works differently:

• Bitmap: check if the bit at N % 2^16 is set.
• Array: use binary search to find N % 2^16 in the sorted array.

Intersect matching containers to intersect two Roaring bitmaps. Algorithms vary by container type(s), and container types may change.

To intersect Roaring bitmaps A and B, it is sufficient to intersect matching containers in A and B.

This is possible because of how integers are partitioned in Roaring bitmaps: matching containers in A and B store integers with the same 16 most significant bits (the same chunks).

Intersection algorithms vary by the types of the containers involved, as do the resulting container types:

• Bitmap / Bitmap: Compute the bitwise AND of the two bitmaps. If the cardinality is <= 4,096, store the result in an array container, otherwise store it in a bitmap container.
• Bitmap / Array: Iterate over the array, checking for the existence of each 16-bit integer in the bitmap. If the integer exists, add it to the resulting array container – note that intersections of bitmap and array container types will always create an array container.
• Array / Array: Intersections of two array containers always create a new array container. The algorithm used to compute the intersection varies by a cardinality heuristic described at the bottom of page 5 here. It will either be a simple merge (as used in merge sort) or a galloping intersection, described in this paper.

If there is a container in either Roaring bitmap without a corresponding container in the other, it will not exist in the result: the intersection of an empty set and any set is an empty set.

Union matching containers to produce a Roaring bitmap union. Algorithms vary by container type(s), and container types may change.

To union Roaring bitmaps A and B, union all matching containers in A and B.

Union algorithms vary by the container types involved, as do the resulting container types:

• Bitmap / Bitmap: Compute the bitwise OR of the two bitmaps. Unions of two bitmap containers will always create another bitmap container.
• Bitmap / Array: Copy the bitmap and set corresponding bits for all the integers in the array container. Unions of a bitmap and array container will always create another bitmap container.
• Array / Array: If the sum of the cardinalities of the two array containers is <= 4,096, the resulting container will be an array container. In this case, add all integers from both arrays to a new array container. Otherwise, optimistically assume the resulting container will be a bitmap: create a new bitmap container and set all corresponding bits for all integers in both arrays. If the cardinality of the resulting container is <= 4,096, convert the bitmap container back into an array container.

Finally, add all containers in A and B that do not have a matching container to the result. Remember: this is a union, so all integers in Roaring bitmaps A and B must be in the resulting set.

Part 3: how a third and final container type – the "run" container – optimizes long runs of consecutive integers.

Parts 1 and 2 of this post cover most of the internal structure and operation of Roaring bitmaps. This final part covers an important optimization described in the second Roaring bitmap paper.

Run containers represent runs of consecutive integers with two 16-bit integers: the run start and run length.

From page 3 of the second Roaring bitmap paper:

The new container is conceptually simple: given a run (e.g., [10, 1000]), we store the starting point (10) and its length minus one (990) ... packing the starting points and the lengths in pairs, using 16 bits each ...

This technique is known as run-length encoding and seems to back most of the prior art described in the two papers. Run-length encoding can compress bitmaps effectively but degrades performance for set operations in many cases.

Run containers are formed explicitly when a client invokes a runOptimize function or, in some cases, implicitly when a large range is added to the Roaring bitmap.

Unlike sparse and dense containers, run containers generally do not materialize automatically.

1. Clients can invoke runOptimize to optimize their Roaring bitmap for large runs of consecutive integers. Run containers may replace existing array or bitmap containers in this case.
2. Roaring bitmaps offer an operation to add a range of values. Run containers may materialize automatically in this case.

The papers don't actually prescribe how or when #2 should happen. I'd guess that if a range of values were added for a chunk that does not yet have a container, it makes sense to create a run container instead of an array or bitmap container.

runOptimize only creates a run container if it will be smaller than the container it would replace.

runOptimize first counts the number of runs in a container.

Then, it decides whether or not to create a run container using a simple heuristic: the run container must be smaller than its equivalent array or bitmap container.

The algorithms used to count runs and a description of how to compute the heuristic above are described on page 6 and 7 in the second Roaring bitmap paper.

If you'd like to work out computing the heuristic yourself, it'll help to recall the following:

• ... array containers contain no more than 4,096 integers, packed into 16-bits each.
• ... bitmap containers contain > 4,096 integers in a bitmap with 2^16 bits (8,192 bytes).
• ... each run in a run container takes up 32 bits (16 bits for the start, 16 bits for the length).

The addition of run containers introduces new algorithms for all set operations.

The Roaring bitmap papers do not describe the algorithms used to insert and check for the existence of integers in run containers: these operations are relatively straightforward.

But the addition of run containers requires that Roaring bitmaps implement performant algorithms for unions and intersections of three new container type pairs:

• Run / Run
• Run / Array
• Run / Bitmap

These algorithms also introduce new heuristics to determine the resulting container type from these operations.

I won't go into the details of these algorithms as I did in Part 2. The algorithms are not significantly more complicated (their descriptions start on page 10 here if you're curious), but the numerous details are beyond the scope of this post and the paper is well-written and makes them extremely accessible.

Roaring bitmaps: a game of performance whack-a-mole!

Roaring bitmaps use a kitchen sink of algorithms and techniques to achieve better compression and faster performance than other bitmap implementations.

They're challenging to implement but they do the job extremely well, especially when used in OLAP workloads. The creators managed to root out inefficiencies in common yet very different scenarios – sparse data, dense data, data with a lot of runs – and address all of them at once.

And they go even further!

A third paper describes an implementation the creators wrote in C that leverages vectorized algorithms they designed to use SIMD (single instruction multiple data) instructions. That implementation, CRoaring, along with bindings and implementations in multiple other languages are available here. They're used in mainstream columnar databases and search applications and are actively maintained, improved, and optimized regularly.

Very cool.

Further reading

If you enjoyed reading this post and want to dig in further, I recommend reading the Roaring bitmap papers. They're well-written and accessible.

• Better bitmap performance with Roaring bitmaps
• Consistently faster and smaller compressed bitmaps with Roaring
• Roaring Bitmaps: Implementation of an Optimized Software Library

Roaring bitmap implementations are available on Github.

Questions? Comments? Feedback? Please send me a note!

Email me at voberoi@gmail.com or holler at me on Twitter or Threads.