4 ms·
KV Cache Compression 900000x Beyond TurboQuant and Per-Vector Shannon Limit
- tomrod 6mo agoExtraordinary claims! I don't follow the argument though.
- EGreg 6mo agoAuthor here. Since starting to teach AI at IENYC, I started publishing my papers recently on arXiv, and considering submitting them to a journal. This is based on my original "PLT" paper: Probablistic Language Tries (https://news.ycombinator.com/item?id=47743585 https://news.ycombinator.com/item?id=47743585). A "Trie" is basically a tree of prefixes. While working on https://safebots.ai https://safebots.ai I became obsessed with caching generated artifacts as a means to do a lot of things: extremely cheap inference, near-optimal compression, modeling decision trees for strategies, and so on. The PLT model was about compression in general. My main insight there was that the LLM's own weights actually contain an incredibly detailed probability distribution of "the next token" in any sequence, which can therefore be very useful to supercharge statistical compression. Sequences which occur frequently in the domain of the model receive short codes. The other insight is that if we allowed lossy compression, we could compress well below the Shannon information limit, and just have an "overflow" bag for surprising sequences. When TurboQuant came out, I realized we can also go way below the Shannon limit in the same way, and take advantage of PLT. In fact, I'm working on publishing a paper that generalizes this to robotics (which needs to do cheap fast on-board inference "in the field"). I also believe this is how animals actually learn. In other words, over time they learn overall "sequences" of actions and then can check whether they are "good enough" to solve the problem, or whether to switch to a full analysis -- this corresponds to System 1 and 2 of Daniel Kahneman's "Thinking Fast and Slow". If you want more specific information, or see the code for a working prototype, you can write me at the email in the paper.
- Rekindle8090 6mo ago[flagged]
- EGreg 6mo agoHaha, yes I always used -- when I typed an em-dash manually. What bot detection extensions? :-P
- cristoperb 6mo agoI can't speak for the person you're replying too, but I use -- for emdash for two reasons: I never remember how to type an actual emdash in linux/X11, and more importantly, I do most of my writing in Asciidoc which converts -- to an emdash automatically. It's nothing to do with bot detection or whatever. But it does get me confused sometimes because in LaTeX (and other markup languages) -- gets converted to an endash whereas it takes three hyphens --- to make an emdash.
- rhet0rica 6mo agoyou are hereby sentenced by the council of dashers to type "—" ten million times using Windows-1252 alt codes you have 5 seconds to comply before your planet will be demolished to make room for a giant space-typographer's punctuation case
- stingraycharles 6mo agoDropping a grand theory of animal cognition into a defense of a KV cache compression bound is not something I was anticipating. I don’t think it’s a great argument.
- wholinator2 6mo agoAt least some random pseudocrackpotery like that is points in the direction of it being a human. There's some strange human tendencies that AI just doesn't usually replicate
- usernametaken29 6mo agoKahnemans book is considered outdated by modern neuroscience.
- himata4113 6mo agoThe reasoning around the 900000x claim isn't sound and violates way too many information density principles. I was incredibly curious since I had a pet theory in my mind about something extremely similar, but arrived at a conclusion that the time complexity of such cache would end up being extremely slow. This is like saying that you've achieved single token compression when you're passing a single token into a model and letting it regenerate the entire output since at the end of the day models are probabilistic stateless devices. At that point you don't have a cache and are just replaying the tokens or have a caching algorithm with a complexity similar to that of a model defeating the purpose of such cache. I've never considered that arXiv had a problem, now I do.
- EGreg 6mo agoNo, the 914,000x in the paper is talking about the ratio between two entropy floors, it's not a claim about practical compression. The point is that per-vector quantization has been chasing the wrong theoretical limit: the sequential entropy bound is just fundamentally lower, by that factor, because KV vectors aren't independent samples! On complexity, that's fair concern, and the paper doesn't fully resolve it. But the analogy to "replaying tokens through the model" isn't exactly right. The delta coding layer uses the model's own next-token prediction, which is already happening during normal autoregressive inference. You're not adding a forward pass, you're using the one already running and storing only the residual, which is much smaller than the raw vector -- precisely because the model is a good predictor of its own next state. The trie index lookup is O(sequence length), not O(model forward pass). Whether that's fast enough in practice at scale is actually a legitimate open question and I'd be the first to admit the paper doesn't settle it. But the contribution here is simply establishing that the bound exists and is dramatically lower than what the field has been targeting. That's what I wanted to put out. The engineering question of how close you can get is the natural next step. Your pet theory about time complexity sounds interesting actually, did you write it up anywhere?
- mbernstein 6mo agoThis is a compute memory trade, not compression vs. turobquant? Lemma 1 is something like, "forward pass is deterministic because it's deterministic" which means the input tokens were always the lower bound...which isn't caching? Smells tautological. What am I missing?
- EGreg 6mo agoWell yeah, I just wrote it as a lemma, but it's basically close to tautological. Its only job is to formally ground the entropy argument that follows it. The interesting claim is what comes after: because KV vectors are deterministic functions of tokens, and because the model is a near-optimal predictor of its own distribution, the conditional entropy of each new KV vector given all previous ones is bounded by token-level perplexity. TurboQuant compresses against the marginal distribution of each vector in isolation -- that's the gap. And yes, it's a compute/memory tradeoff, all caching is. The claim is just that the memory floor is much lower than anyone had formally established. Whether the compute cost of getting there is worth it is a fair open question the paper doesn't settle. But what if it is? Caching is the thread running through most of my work, and I intend to find out.
- tomrod 6mo agoCan you show a working example/implementation of these theoretical improvements? Working code would also go far for replication.
- deleted 6mo ago[deleted]
- gaze 6mo agothis paper looks AI generated to me... I mean, there's no experiments to go along with it.
- ddtaylor 6mo agoVery intersting. A compression strategy that uses the model itself as the dictionary.
- thethirdone 6mo ago> the ratio remains approximately 914x over TurboQuant, with compression improving rather than degrading as context length grows. This line from the abstract got me really suspicious. Obviously a compression scheme that incorporates the entire sequence shouldn't get worse compared to a per element one as the length increases. It is important to note that this paper is PURELY theoretical. I couldn't find much meat on the bone from a quick skim. The single author, Gregory Magarshak, has only published one paper on arxiv before and appears to be a professor of business / music. I don't plan to give it more of a read hoping for something of value.
- stingraycharles 6mo agoMe neither. There are no actual experiments / data, no peer reviews, and the innovation relies almost entirely on citations from the author’s other paper. The author is not an ML researcher but rather an AI startup CTO / founder. Previously worked on “social operating systems” for the web, blockchain of course. And now an AI innovator. I’m suspicious. This was part of the author’s reply in another thread: > When TurboQuant came out, I realized we can also go way below the Shannon limit in the same way, and take advantage of PLT. In fact, I'm working on publishing a paper that generalizes this to robotics (which needs to do cheap fast on-board inference "in the field"). I also believe this is how animals actually learn. In other words, over time they learn overall "sequences" of actions and then can check whether they are "good enough" to solve the problem, or whether to switch to a full analysis -- this corresponds to System 1 and 2 of Daniel Kahneman's "Thinking Fast and Slow". Which doesn’t exactly inspire confidence and makes me wonder who they think their audience is. ML researchers or LinkedIn.
- gaze 6mo agothe irritating thing about LLM generated papers like these is that they're wrong but are generated using LLMs that are capable enough to bury the absurd claim pretty deep in there.
- stingraycharles 6mo agoAnalyze it using an LLM. Claude was pretty ruthless about this one.
- EthanFrostHI 6mo ago[dead]
- sabareesh 6mo agoSounds like speculative decoding but for KV cache
- aesthesia 6mo ago> The second layer, predictive delta coding, stores only the residual of each new KV vector from the model's own prediction of it I don't understand this. The key and value vectors for any given layer + token are created by the model. By definition, they are exactly equal to the model's prediction of them! Extreme KV cache compression is easy to get---you can get an infinite compression ratio by just regenerating the key and value vectors on every forward pass. The point of a KV cache is to reduce the amount of repeated computation during generation, though. Compression only helps if you have an efficient decompression algorithm.
- binsquare 6mo agoIncredulous claims and unreviewed paper. Attention really is all you need.
- CyberDildonics 6mo agoI think you mean incredible claims. You would be incredulous about them.
- binsquare 6mo agoYou're right, thanks for the correction
- EGreg 6mo agoThe prediction being used is the model's prediction of the next token's KV vector, given all previous KV vectors. Because the model was trained on language, it has strong priors about what comes next. The residual, i.e the difference between the predicted next KV vector and the actual one -- is much smaller in entropy than the raw vector, for the same reason language model perplexity is low on fluent text.
- aesthesia 6mo agoWhat model is doing this prediction? The only way a transformer predicts the "next KV vector" is by sampling the next token and then running a forward pass with that token.
- WithinReason 6mo ago> The tokens stored in a KV cache are not arbitrary floating-point data -- they are samples from the exact formal language the model was trained on, and the model is by construction a near-optimal predictor of that language. You can compress the KV cache to 0 bytes by just recomputing it every token. This observation is not worth an ArXiv paper though.
- OutOfHere 6mo agoEGreg: Can we please have substantive code with reproducible results to go with each of your papers? It would go a long way in shutting up naysayers.