Probabilistic Data Structures and LLMs
Bloom filters are a data structure that answers the question: is an element part of a set? It does it in a remarkably efficient way: the time needed to either add items or check whether an item is in the set is a fixed constant O(k) and independent of the number of items already in the set. A fixed-sized Bloom filter can represent an arbitrarily large number of elements. There’s no free lunch — Bloom filters don’t answer in yes/no but rather “possibly yes/definitely no.” That means no false neg
Bloom filters are a data structure that answers the question: is an element part of a set? It does it in a remarkably efficient way: the time needed to either add items or check whether an item is in the set is a fixed constant O(k) and independent of the number of items already in the set. A fixed-sized Bloom filter can represent an arbitrarily large number of elements. There’s no free lunch — Bloom filters don’t answer in yes/no but rather “possibly yes/definitely no.” That means no false negatives, but false positives are possible. LLMs are not probabilistic data structures, but it…
saved by
related reading
- Bloom Filters - Much, much more than a space efficient hashmap! | Ben E. C. Boyterboyter.org
- Bloom filter | Docsredis.io
- Bloom filters debunked: Dispelling 30 Years of bad math with Coq!kirancodes.me
- Bloom Filterssamwho.dev
- As Rocks May Think | Eric Jangevjang.com
- Patterns for Building LLM-based Systems & Productseugeneyan.com
- What We’ve Learned From A Year of Building with LLMs – Applied LLMsapplied-llms.org
- GitHub - brexhq/prompt-engineering: Tips and tricks for working with Large Language Models like OpenAI's GPT-4.github.com
- How LLMs Work, Explained Without Math - miguelgrinberg.comblog.miguelgrinberg.com
- Teaching LLMs to reason like Bayesiansresearch.google
- Recent LLMs can use filler tokens or problem repeats to improve (no-CoT) math performanceblog.redwoodresearch.org
- What sort of maths are LLMs good at?gowers.wordpress.com