Cache and Draft Validation Research Desktop

Search and experiment date: 2026-09-10. This paper provides a runnable NumPy mechanism experiment to distinguish the paper report, this actual verification and author’s interpretation.

Abstract

Generation can speed up in two distinct ways: reuse past states to avoid redundant computation, or commit several tokens in a single target-model call. We implemented key–value caching and speculative decoding in the same small causal decoder and checked numerical values, probabilities, and cache states before timing either method. Caching reduced elapsed time, while a poorly matched draft slowed generation down. What work did each method save, and what did a wrong guess cost?

Contents

  1. Reproducing Value and Evidence Boundaries
  2. Core ideas and formulas
  3. A guide to the official implementation
  4. A minimal experiment and its results
  5. Evaluation protocol
  6. Failure investigation
  7. Questions for further research
  8. Summary and References

Reproduce value: break the correctness into three problems

The first question is whether the cache is the same as the Logits of the full prefix recalculation. Logits are the vocabulary scores before normalization; only comparing the final tokens may cover up the numerical error that has not changed the maximum position. The second question is whether the condition prefix for batch validation is correct. The third problem is whether the sampling rules and the two sets of caches can be restored to the submitted history after rejecting the draft.

Paper report: The ICML 2023 paper of Leviathan, Kalman, and Matias constructs candidates with cheap drafts, and then scores in parallel by the target model, and maintains the target distribution by accepting rules. Its specific T5-XXL experiment reports about two to three times the acceleration; this depends on the model, implementation and hardware of the paper, and this paper does not reproduce this number. Conference page

**What we tested:** The small, untrained model serves only to check the mechanisms. It provides no results on natural-language accuracy, perplexity, or large-model throughput. **My interpretation:** For someone learning to run these experiments, being able to locate an error matters more than obtaining an initial speedup figure. Otherwise an algorithmic mistake can look like an optimization gain.

Core Ideas and Formulas: Cache History, Validate the Future

What the cache saves

Causal attention only allows the current position to read itself and the past. After fixing the model and position rules, subsequent tokens will not change the past keys and values, so each layer can keep them. Prefill refers to the first processing of prompt; decode refers to the gradual generation of new tokens after that. Official Cache Explanation

For new blocks can be written as:

K′=[K;XWK],V′=[V;XWV],O=softmax⁡(QK′⊤/dh+M)V′.K'=[K;XW_K],\quad V'=[V;XW_V],\quad O=\operatorname{softmax}(QK'^\top/\sqrt{d_h}+M)V'.

Batch and head dimensions are omitted here; new inputs are mm OK, history has TT line, the attention score shape is [m,T+m]. dhd_h is the width of each head, MM Set the future position to negative infinity. Although the historical projection is no longer recalculated in a single step, the historical key value must still be read; the block verification must also maintain the causal mask in the block.

Directly counted by the shape of the cache array, the payload of the standard full-length cache is:

bytes=2LBHkvTdhs.\text{bytes}=2LBH_{kv}Td_hs.

LL is the number of layers, BB for batch size, HkvH_{kv} is the number of keys, ss It is the number of bytes per element, and the first two represent keys and values. This is the array load budget, which does not contain the model, temporary score matrix, allocator and draft cache. The single-layer bond tensor in this experiment is [2,29,8], omit batch dimensions of size one; two layers, double precision is 14848 bytes, which is consistent with the actual array count.

Why can't the acceptance draft be rolled back at will?

Make pp for the target distribution, qq For the draft distribution, all correspond to the same accepted prefix. first qq Draw candidates xx, and then accept the following formula; to extract the correction tokens from the residual distribution on the first rejection:

a(x)=min⁡(1,p(x)/q(x)),r(x)=[p(x)−q(x)]+∑y[p(y)−q(y)]+.a(x)=\min(1,p(x)/q(x)),\qquad r(x)=\frac{[p(x)-q(x)]_+}{\sum_y[p(y)-q(y)]_+}.

x,yx,y It is a vocabulary item, square brackets are taken to the positive part; the items drawn by the draft must have a positive one q(x)q(x). Here p,qp,q It is the normalization probability after the actual sampling transformation. The independent work of Chen et al. also uses correction refusal to sample; floating-point realization is also subject to hardware numerical accuracy. Full paper

This paper uses three distributions for visual calculations: p=(0.1,0.6,0.3)p=(0.1,0.6,0.3)、q=(0.7,0.2,0.1)q=(0.7,0.2,0.1), the probability mass of the accepted part is (0.1,0.2,0.1), the remaining quality should be supplemented to the last two items. If rejected directly from the original pp Re-draw, the first item will get the probability again, and eventually become (0.16,0.56,0.28), has deviated from the target. This is a specific counterexample with code verification.

Draft generation continuously γ\gamma item, the goal is achieved at one time γ+1\gamma+1 group conditional probability. From left to right until the first rejection; all subsequent candidates are void. If all are accepted, an additional token is drawn from the last set of target probability. The same distribution does not require different algorithms to produce verbatim samples under the same random seed. Algorithm one

First rejected branch: accept prefix, crop cache, correction and commit

The picture only shows the first rejection branch: two green candidates are left, two orange suffixes are discarded, and a blue tokens are added. The triangular grid is a representation of causality, which does not correspond to the exact matrix dimensions of the experiment. Submitting tokens does not mean that its key value has been calculated; the next round still needs to process the tail that has not been cached.

Guide to the official implementation: read along the state

This article is fixed to read Transformers v4.57.1 label, avoid writing the current main branch interface as an eternal rule. It is the implementation of the official framework and does not pretend to be the experimental code released by the author of the original paper; this time the framework did not run or download the pre-training weight.

First generation/utils.py Look for _assisted_decoding, string candidate generation, take the last logits, accept judgment and crop(new_cur_len - 1). Look again _speculative_sampling The probability ratio is normalized with the positive part; focus on tracking "Which line predicts which candidate". This version entry limits the batch size to one, and excludes some static cache paths. Generate source code

Read after candidate_generator.py of get_candidates and _update_past_and_masks. The draft state has its own cache, length and mask, and you cannot just modify the target model. Compare the input length, cache length and the number of new tokens to help understand why one subtract and extra crop occurs in the code. Candidate source code

Final reading cache_utils.py of DynamicLayer.update/crop: Added key-value splicing along the sequence axis, and clipping preserves valid prefixes. The state that the sliding window has been discarded cannot be restored by slices, and this version has an explicit restriction on this. This is the applicable boundary of the actual implementation. Cache source code

If you continue to access the pre-trained model, and then check the assistant configuration and tokenizer conditions in the official generated policy document, the model version, device compatibility and real task performance are all manually verified. strategy

Minimum experiment: from array to full generation loop

code/minimal_decode.py Only depend on NumPy. The goal is two layers, and the draft is one layer; the width is 16, two ends, the feedforward width is 32, and the vocabulary is eight items. The two share the front section of the initialization rule, but the output header is different; all weights remain randomly initialized and are not trained. The input is an integer tokens, without tokenizer, padding or ending.

Execute from the catalog of this article:

python3 -m pip install -r code/requirements.txt
python3 code/minimal_decode.py > code/smoke_test.txt
python3 -m py_compile code/minimal_decode.py code/audit_results.py
python3 code/audit_results.py

The installation line is ready for the reader to prepare the environment. This use has Python 3.12.14 and NumPy 2.3.5, which are executed in the macOS ARM64 CPU. Write the script directory by default, keep a new round of results can be specified --out, the same directory is sent to the audit.

The first group divided the twenty-nine items into blocks of length three, one, seven, two, and sixteen. Differences between block logits and full forwards are 1.11e-15; Replace the last item without changing the previous position output. The second group of fixed eight items, continue to write forty-eight items, and the three initialization seeds are completely the same as the three types of draft lengths. Each round also validates the logits and cropped two sets of caches with full forward recheck.

The third group was sampled randomly at temperature, and the three seeds were checked by round-by-round state; the same distribution draft was separately tested for full acceptance and additional tokens branches. 200,000 independent three distribution experiments were sampled, and the correct realization frequency was (0.099175,0.601680,0.299145); the total variation distance from the target is 0.00168, the error falls back as 0.05903. The total variation is half the absolute difference of the probability. The code also accurately checks the same distribution, disjoint support set and zero probability term; limited sampling only provides diagnostic evidence, and cannot replace general proof.

Evaluation protocol: Results and Costs Report Separately

The following table is the measured output of 69 seeds, the same prompt and forty-eight greedy items. Each path is warmed up once, and then the median is repeated seven times; the complete loop includes pre-filled, draft, sample and cache copy, does not include model initialization, disk write and additional audit forward.

Path median time-consuming MS target call draft call The total number of projected positions in the target layer
full prefix recalculation 7.93 48 0 3024
key-value cache only 4.54 48 0 110
Cache plus four speculations 15.99 48 179 464

The position of the last column accumulated layer by layer cannot be regarded as a floating-point operation. The draft proposed 178 items, but only one actually accepted; in addition to the 47 rounds of target verification, there is a pre-filling, so the target call has not been reduced. It gives the specific reason for failure: the draft is too much, the reserve is less, and the additional score matrix and copy are also introduced.

Acceptance rate must declare the denominator. When the seeds 71 and 4 drafts, 35 items, 49 items, and 39 actual inspections are accepted; Paper performance estimation also relies on the assumption of accepting process and computation parallelism, which cannot be directly introduced end-to-end time by a percentage. This article only reports native short sequence observations, and seven repetitions do not constitute cross-hardware Confidence interval.

Failure Troubleshooting: Let Errors Have Visible Signals

If the greed is the same but the logits are different, first check the position offset, normalization and mask; if the replacement last item will affect the past output, it means that there is a future information leakage. If only an error occurs after the first rejection, print the length before and after the crop, and check the tail of the next input. The script target cache is kept until the penultimate item of the submitted sequence, and sometimes there is less than one draft of the non-terminal round, which is made up by the next round.

When there is only one left of the output budget, the program will no longer generate a draft and submit it directly to the target tokens. Therefore, the termination wheel draft cache can be shorter, and there is no need to generate supplements for the end of the end. The independent audit has failed to check this place with the length rule of the non-termination wheel; the correction is passed after the actual valid prefix is tracked. When checking an invariant, also make it clear which boundaries it holds.

If the frequency deviates from the target, first use the above three counterexamples to check the residual normalization, and do not increase the sample size first. The first round of development checks have mistaken the distance threshold of error reversion to greater than 0.1; the analytical calculation shows that it should be 0.06 Therefore, it is changed to check the distribution error distribution, and requires the actual measurement to be greater than 0.04. This is the test threshold correction, the sampling algorithm has not been changed; the failure and correction are recorded in the verification statement.

If the video memory or time-consuming does not drop, distinguish between payload and peak value. NumPy crops use replication so that the slices are not preserved the underlying memory of the rejected suffix; the cost is also time-consuming. The script does not measure the process peak or GPU memory, and the number of cached bytes cannot be written as the peak occupied. The ending, batch, rotary position code and low-precision rounding have not been verified at present.

Questions for further research

The author's inference: You can first study "how long the draft should be written", and then fix it to the test set on the development set according to the length and real time-consuming of each round. The control must contain a constant length and no draft is used, and the record is stopped early, rather than just showing the highest acceptance rate.

Another problem is where the cost comes from. Fixed the target model and the output budget, change the prompt length, draft size and cache copying method respectively, disassemble the pre-filled and continue writing time-consuming; then check whether the saved calls are canceled by a larger verification block. Finally, it is migrated to the public pre-trained model and fixed task set, supplementing the multi-prompt duplication, terminator boundary and random sampling distribution diagnosis. These are the research plans to be implemented, not found in this experiment.

Summary

Reliable reproduction should hold the three invariants of value, distribution and state at the same time. This small experiment verified the cache and speculated decoding mechanism, and also retained a set of significantly slower controls. Readers can start with the failure round log, explain why each candidate is retained or discarded, and then judge whether the added calculation is worth it.

References

The following first-hand information is 2026-09-10 It is actually opened; the frame source code is fixed to V4.57.1, and the latest version is not claimed to be used.

  1. Yaniv Leviathan、Matan Kalman、Yossi Matias,2023, Fast Inference from Transformers via Speculative Decoding,ICML,PMLR 202:19274–19286. Conference page; Full text of publication.
  2. Charlie Chen、Sebastian Borgeaud、Geoffrey Irving、Jean-Baptiste Lespiau、Laurent Sifre、John Jumper,2023, Accelerating Large Language Model Decoding with Speculative Sampling,arXiv:2302.01318 v1. Inscriptions and versions; Full text.
  3. Hugging Face Transformers contributors,v4.57.1, Caching. computer file.
  4. Hugging Face Transformers contributors,v4.57.1, Generation strategies. computer file.
  5. Hugging Face Transformers Contributors, v4.57.1, generate loop, candidate generation and cache implementation. utils.py; candidate_generator.py; cache_utils.py.