{"id":"61c3e20b-32a8-4653-8e34-16e1c9fc6362","arxiv_id":"2411.13820","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A cache that pre-generates answers to instructions a language model judges likely, achieving hit rates up to 2.3x the exact-repetition upper bound on WildChat and up to 50% faster token generation in vLLM.","lead":"InstCache is a cache for AI chatbot servers that guesses upcoming user questions and prepares answers ahead of time. In tests on real chat logs it served 2.3 times more requests from cache than an exact-match cache could, and cut the time to produce each token by up to 50%.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Load-bearing concern: the headline hit-rate gain is measured on random splits that include future data; the only temporal experiment shows degradation but no exact-match baseline, so the 2.3x deployment claim is not yet established.","rationale":"The paper's central claim is that NLL computed by a fine-tuned LLM creates spatial locality that lets a precomputed cache serve unseen future instructions at a rate far above exact-match repetition. The load-bearing evidence for that claim is the 2.3x hit-rate advantage in Section 5.2.1. But that evidence comes from random 80/10/10 splits, where the training set and the pre-population data include requests from after the test period. This makes the comparison a measure of overlap with a held-out random sample, not of prediction across time. The paper does include a temporal experiment in Section 5.2.4, which is a genuine attempt to address this, and the authors honestly acknowledge degradation and the need for periodic updates in the Discussion. However, that experiment does not report the exact-match baseline under the same split, so it cannot show whether the claimed advantage over traditional caching persists chronologically. This is a more precise version of the reader's weakest assumption about NLL ordering stability: the issue is not only whether the ordering drifts, but whether the main experimental design ever isolates the deployment-relevant temporal prediction task. For these reasons I partially agree with the reader's concern. The finding does not overturn the method; with a clean temporal evaluation the advantage might well persist, given the paper's own Figure 7 shows a steady rather than catastrophic decline. The appropriate verdict remains CONDITIONAL, with the temporal-split baseline as the key condition for acceptance.","tokens_in":21068,"tokens_out":11005,"duration_ms":112025,"concrete_test":"Re-run Figure 3 with a strict temporal split on WildChat, which has timestamps: fine-tune and pre-populate InstCache using only months 1-6, selecting sigma on a validation month within that window; for each later month m, report (i) InstCache hit rate and (ii) exact-match hit rate of a cache containing all requests from months 1..m-1, at the same sigma values. If the ratio falls below roughly 2.3x for WildChat (or below the random-split ratios for LMSys/Moss) for a 3-month horizon, the random-split result was inflated by future data; if it stays above, the temporal concern is resolved. Also overlay this exact-match baseline on Figure 7 to quantify the gap as a function of time.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5.1 splits each dataset randomly (80/10/10), and Figure 3 in Section 5.2.1 reports InstCache hit rate versus the fraction of test instructions that appear in the training set. Under a random split, the training set contains requests that occur after test requests, so this 'upper bound' is not the upper bound of a cache that only knows the past. InstCache itself is also trained and prepopulated on the random 80%, which includes future requests. The comparison therefore tests whether low-NLL generated texts overlap with a held-out random sample, not whether NLL predicts future requests, which is the stated mechanism in Section 3. The only chronological evaluation (Section 5.2.4, Figure 7) trains on the first six months and tests on later months; it shows hit rate steadily declining with temporal gap, but it never reports the exact-match baseline under the same chronological split. If the exact-match cache built from prior months also declines, or if the InstCache advantage shrinks, the headline 2.3x figure does not transfer to deployment. This is a correctness risk in the central claim, not a missing nicety: the reported ratio is the main evidence that predictive caching beats traditional exact-match caching in a realistic serving setting.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes InstCache, an instruction-level cache for LLM serving. The cache is constructed offline by fine-tuning a small LLM on observed user instructions and then enumerating, via a V-ary tree traversal, all instruction strings whose negative log-likelihood (NLL) under this model is below a threshold sigma; responses are generated with a larger serving model and stored in a hash table. At serving time, an incoming instruction is answered from the cache on an exact-match hit. The paper reports hit rates of 8.2% on WildChat (2.3x the repetition-rate upper bound), 20.1% on LMSys, and 23.4% on Moss, and latency reductions for vLLM of up to 42-50%. It also claims that hit rate and cache size can be predicted via the NLL cumulative distribution function (Eq. 1) and a power-law text-count theorem (Theorem 1).","tokens_in":21324,"tokens_out":8050,"duration_ms":135370,"significance":"The underlying idea of using an LLM's NLL to induce a total order on instruction space and caching the low-NLL region is interesting and potentially useful in serving systems where a small fraction of requests dominates traffic. The authors evaluate on several real-world conversation datasets, release code, and include a temporal drift experiment, which is the right instinct. If the comparison against exact-match caching is re-run under a causal split and the advantage survives, the paper would be a solid systems contribution. However, as presented, the headline hit-rate gain is not yet established because the main evaluation uses a random split that lets both InstCache and the baseline peek at future requests.","major_comments":[{"comment":"The central comparison is affected by temporal leakage. In Section 5.1 the data are split 80/10/10 randomly, so the 80% used to fine-tune the prepopulation LLM contains requests that occur after the test requests, and the exact-match 'upper bound' repetition rate in Figure 3 is computed from the same random 80% (for WildChat, 3.56%). Under deployment, a cache can only be built from the past, so this repetition rate is not an upper bound for a traditional cache that knows no future. The only chronological experiment (Section 5.2.4, Figure 7) trains on the first six months and tests on later months, but it reports no exact-match baseline under the same split, so it cannot show whether the 2.3x advantage over traditional caching survives temporal drift; indeed the figure shows InstCache's own hit rate declining steadily with the gap. To support the headline claim, the authors should report both InstCache hit rate and the exact-match repetition rate on a causal split (e.g., train on months 1-6, test on month 7, then months 8-12) and show the ratio over time.","section":"§5.1, §5.2.1, §5.2.4"},{"comment":"The 'hit-rate prediction' in Eq. (1) is a definitional identity rather than a predictive model. Because C is defined as { : NLL(s) <= sigma}, the equality Hit_Rate = P(N <= sigma) = F_N(sigma) holds by construction; no property of the LLM or of user behavior is used. The validation-set estimate described after Eq. (1) therefore only checks whether the NLL distribution on a held-out random sample matches the validation sample; it does not validate the paper's central assumption that low-NLL regions are stable over time. The evaluation in Figure 4 should be reframed accordingly, or supplemented with a genuine out-of-time prediction experiment in which the NLL CDF estimated from past months is used to predict hit rates on future months.","section":"§3, Eq. (1)"},{"comment":"The cache-size prediction rests on an assumption that is not stated as the strong idealization it is: the proof of Theorem 1 takes the next-token probabilities to follow the same power law P(t_i) = beta * i^{-alpha} at every position independently of context. Real LLM next-token distributions are highly context-dependent, and the power-law fit in Figure 8 is an aggregate over positions and contexts, not a per-node statement. The final formula also drops beta by assuming beta is close to 1. As a result, Theorem 1 is a heuristic estimate under a stylized model, not a theorem about the LLM's text space. The authors should either prove the claim under the actual conditional distributions (or state the needed conditions) or explicitly label Theorem 1 as an approximate scaling law and validate its error across datasets, thresholds, and sequence lengths; currently the claimed 'accurate' profiling in Section 5.2.1 is supported only by the single aggregate plot in Figure 4.","section":"§3, Theorem 1, Appendix A"}],"minor_comments":[{"comment":"The text says the baseline cache is built from 80% of the data and measured on the remaining 20%, but Figure 3 and the surrounding text define the repetition rate as the proportion of test instructions appearing in the training set, implying an 80/10/10 split; please make the split consistent.","section":"§5.1, Baselines"},{"comment":"The pseudocode does not specify how the candidate next-token set T is obtained from the LLM (full vocabulary, top-k, or a probability cutoff); without this, the enumeration is not fully reproducible from the pseudocode.","section":"§4.1, Algorithm 1"},{"comment":"References [9] (AttentionStore) and [11] (MeanCache) are both assigned arXiv:2403.19708; one of these identifiers is incorrect.","section":"References [9], [11]"},{"comment":"The x-axis labels ('Apr--Sep Oct Nov Dec Jan 2024 Feb Mar Apr') are ambiguous; please label the training and test months explicitly.","section":"§5.2.4, Figure 7"},{"comment":"The columns 'Mem Size' and 'Storage Size' are not defined in the text; clarify what each measures (e.g., in-memory hash table size vs. disk storage, or KV-cache memory vs. response storage).","section":"§5.2.1, Table 2"},{"comment":"The phrase 'upper bound of traditional caching mechanisms' is imprecise: the repetition rate is an upper bound for an exact-match cache with infinite capacity on a given training set, not for caching in general; please qualify it.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The paper's main empirical claim is currently supported only by random splits that leak future information into both the prepopulation model and the exact-match baseline. This is fixable within the paper's scope by re-running the evaluation on a causal temporal split and reporting the exact-match baseline under the same split. The theory section also needs reframing, since Eq. (1) is definitional and Theorem 1 relies on a strong context-independence assumption. If the authors supply the causal evaluation and the 2.3x advantage persists, I would support publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: InstCache is a genuinely new idea—use an LLM's NLL as a memory address to define a cache region, then enumerate that region offline and serve exact-match hits from a hash table. The paper does a lot right: real datasets, a clear pre-population algorithm with reported costs, and a temporal-drift experiment that shows the diagnosis. But the headline number—2.3x over the exact-match upper bound on WildChat—is measured on a random 80/10/10 split, so both the cache and the baseline see future requests. That is not the deployment setting the abstract implies. The only chronological experiment (Figure 7) shows hit rate decaying with time gap, and it never reports the exact-match baseline under the same split. So we don't yet know whether predictive NLL caching beats a simple exact-match cache that knows only the past. That's the load-bearing question.\n\nWhat is actually new: framing NLL as an address and pre-enumerating the low-NLL region offline. I haven't seen that in GPTCache/MeanCache/SCALM. The depth-first tree traversal with KV reuse is a sensible engineering contribution, and the cost numbers (e.g., ~10 hours for 18.7M instructions on 3 A100s) are useful.\n\nThe soft spots beyond the temporal leak: Eq. 1 is a definition, not a prediction—hit rate is the CDF of NLL, which is exactly how the cache is built. Calling it predicted is harmless but should be labeled as a consistency check. Theorem 1's cache-size formula depends on a fitted power-law assumption; it's an approximation, not a proof of the method's value. The serving benchmark (Section 5.2.2) never demonstrates a fully materialized response cache—they generate responses for only 5,000 sampled instructions and estimate the rest—so the 42%/50% latency numbers are not tied to an actual deployed cache. And there are no error bars, which matters when the main comparison is a ratio of small numbers.\n\nNone of this kills the core idea. It means the paper's central claim needs to be re-estimated under a chronological split with the exact-match baseline reported in the same figure. That's an addressable fix, and the idea is novel enough to deserve referee time.\n\nFor whom: systems researchers working on LLM serving and caching; anyone who wants a concrete alternative to semantic caching. I'd send it to review, but I'd tell the authors the temporal evaluation is the condition for acceptance.","headline":"Interesting and novel idea, but the headline 2.3x hit-rate claim is measured on random splits that leak future data; the only temporal experiment lacks an exact-match baseline, so the deployment case is not yet made.","tokens_in":21876,"tokens_out":3145,"would_cite":false,"duration_ms":28563,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A fine-tuned LLM's negative log-likelihood ordering can precompute answers to future user requests, beating exact-match caching by up to 2.3x.","keywords":["LLM serving","instruction caching","negative log-likelihood","spatial locality","cache pre-population","V-ary tree search","hit rate prediction","exact-match cache"],"falsifier":"Train InstCache on the first six months of WildChat and compute its hit rate at a fixed threshold for each subsequent month: if the hit rate collapses to the exact-match repetition rate within a month or two, the NLL-locality claim is falsified. A second check is to enumerate all cached instructions and have an oracle judge how many are meaningful user requests; if the low-NLL region is mostly generic filler, the hit-rate number is an artifact of the threshold rather than evidence of prediction.","tokens_in":20832,"feed_emoji":"⚡","tokens_out":10403,"duration_ms":91365,"temperature":0.7,"pith_summary":"Instruction-response caches for LLM serving normally only help when the same request appears twice, which is rare in real traffic. This paper argues that a language model fine-tuned on past user instructions can be used to predict which never-seen instructions are likely to arrive, by treating each instruction's negative log-likelihood (NLL) as a one-dimensional address. The proposed InstCache stores every instruction whose NLL falls below a threshold, together with its precomputed response, and serves exact matches from a hash table. On deduplicated WildChat data, the cache achieves an 8.2% hit rate, about 2.3 times the exact-repeat upper bound for traditional caching, and when integrated with a serving engine it reduces time per output token by up to 42.0% and 50.0% on the LMSys and Moss datasets. If the effect holds, serving systems could answer a substantial fraction of requests without running the large model at all.","feed_headline":"Predictive cache beats exact-match LLM caching 2.3x","feed_subtitle":"A model's likelihood score predicts unseen requests, cutting time per output token by up to half.","key_machinery":"The load-bearing mechanism is the use of a fine-tuned LLM's negative log-likelihood, $\\operatorname{NLL}(s) = -\\sum_i \\log p(t_i \\mid t_{