acceptodds
Under review as a conference paper at ICLR 2027

Agent Turns Are Not Chat Turns: Matching Draft Supply with Verification Cost

Abstract

Speculative Decoding (SD) accelerates LLM serving by verifying several draft tokens in one forward pass. Current SD approaches work well for conversation workloads, where contexts are short and content is largely new. Yet agent workloads are different: a coding agent solves tasks through tens of turns of generation, tool use and observation, building contexts that reach tens of thousands of tokens. Much of what the agent writes—re-edited files, re-issued commands, summarized context—closely follows text already in the prompt: 70% of generated tokens match the agent's own earlier output, and the reuse grows with the session. The prompt itself thus provides a growing candidate supply that needs no auxiliary model, but does need a retrieval-based drafter that can adapt it. Scaling retrieval-based drafting to concurrent serving raises two problems: building a per-request index blocks the scheduler thread, and the draft tree must be sized to the verification capacity the hardware affords. We present THRIFT, a training-free retrieval-based drafter that indexes the prompt with a suffix automaton and the current generation with a trie, builds each request's corpus asynchronously, and sizes the draft tree to the batch's verification capacity. We also propose an evaluation protocol that stratifies turns by their relation to the agent's earlier output and reports decode-stage next to end-to-end speedup. On BeyondSWE with Qwen3-14B at batch size 8, THRIFT achieves the best end-to-end speedup up to over autoregressive decoding; its accept length grows from to tokens per forward across a session while training-based baselines stay flat.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Agent, Speculative Decoding, LLM Efficiency

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.40 over 5 reviews, above 68% of the others.
Reviewer_uD9ROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

THRIFT retrieves draft tokens from an agent's prompt and earlier output. It scores candidates, adjusts draft width, and builds indexes asynchronously. The paper tests it on BeyondSWE request replays in SGLang.

Critical strengths
  • The analysis of token reuse in agent workloads is useful.
  • The paper measures serving time and CPU index costs, not just acceptance length.
Critical weaknesses
  • The core idea overlaps with SuffixDecoding, which already uses prompt/history retrieval, request-local indexes, and adaptive tree drafting for agent workloads. There is no direct comparison. The external-corpus SGLang SAM baseline is not a substitute.
  • Overall gains are small: 1.78x request speedup versus 1.75x for SGLang N-Gram on the cleaned Qwen3-14B greedy workload. Frequency-only scoring matches the full scoring method's acceptance length, and fixed width 24 matches adaptive-width latency.
  • Evidence is limited to BeyondSWE request replays. Trained draft model baseline is retrained on Open-PerfectBlend, not agent trajectories. The results do not establish an advantage over agent-adapted learned drafters or beyond reuse-heavy coding workloads.
Questions for authors
  1. How does THRIFT compare with SuffixDecoding under the same serving setup and draft budget?
  2. Which components reliably reduce latency beyond request-local indexes and asynchronous construction?
  3. Do the gains hold against EAGLE-3 or DFlash adapted to separate agent training data?
4 comments
AuthorsOpenReview ↗

Response to Reviewer uD9R

W1: Overlap with SuffixDecoding. See General Response. The design differences: (1) SAM (O(n) async construction) vs suffix tree (synchronous online updates); (2) scored expansion — the single largest contributor per our ablation; (3) cost-aware width selection — why SuffixDecoding at 5.38× loses to N-Gram at 6.16× (batch 8, 14B) while THRIFT reaches 7.86×.

W2: Small gains / ablation components. Beyond the average gain, we care about how consistently THRIFT wins across deployment settings. The 1.78× vs 1.75× figure compares against N-Gram at its default width. With each method at its best width under measured forward costs, THRIFT leads N-Gram in every setting we tested: 1.22–1.40× on 14B and 1.18–1.35× on 32B, across 1–4 GPUs and batch sizes 1–16, with every 95% interval above 1. The baselines' best width shifts with model and batch size (N-Gram: 20 at 14B batch 8, 12 at 32B batch 8), so a fixed default can lose about 10%. THRIFT picks its width from the cost model and needs no per-setting tuning.

  • Scoring. The original Table 7 compared scoring rules at one fixed width and on one view of the data. Replacing the scored ranking with upstream recency drops THRIFT below N-Gram (4.87× vs 5.42×, 14B batch 8), making it the largest single ingredient.
  • Width. A well-chosen fixed width matches the adaptive controller. Since the right width varies with model and batch size, we choose it from the cost model. We will revise the claims accordingly.

W3: Single workload / trained baseline data. BeyondSWE is the most complete public agent-trajectory dataset with multi-turn tool use, and its three tools (bash, file editor, search) cover the dominant patterns in coding agents. Regarding agent-adapted trained drafters: no public agent-trajectory training set exists for draft models. Training on agent data would require teacher-forced pairs from the same sessions — an interesting direction we will discuss. The fundamental limitation remains: a learned drafter predicts from hidden states, while agent reuse requires retrieval across the full prompt.

Q: Which components reduce latency? Ablation ladder: scored ranking (+6.1%), width increase enabled by scoring (+11.4%), prompt context in session Trie (+12.6%). Async lifecycle converts accept-length gains into wall-clock gains (Table 4: sync 1.66× → async 2.28× all-turns).

Dear Reviewers,

This is a friendly reminder that the rebuttal discussion period is approaching its deadline.

Please take some time to review the authors' rebuttal and actively participate in the discussion. If you have any remaining questions or concerns, please raise them and share your feedback with the authors and other reviewers.

As the discussion period is about to close, we kindly ask you to complete your discussion and provide your updated assessment before the deadline.

Thank you for your time and effort.

Best regards,

Area Chair

Thanks for adding the comparisons. I’m still unclear how the new speedups relate to the original end-to-end results, and whether acceptance-aware scoring improves over frequency-only scoring. I’m keeping my weak reject recommendation.

AuthorsOpenReview ↗

Thank you for the follow-up

Thank you for the follow-up.

After submission, we refined several indexing details to improve cross-turn reuse: retaining earlier outputs in both SAM and Trie, prepending a short prompt tail to stored outputs to support matching at turn boundaries, and routing tool outputs into the session Trie. The supplementary comparisons in our General Response use this updated implementation. We will make improved details explicit.

Regarding scoring, frequency-only scoring already achieves overall performance close to acceptance-aware scoring in our evaluated settings. Our main contribution lies in coordinating reusable token sources, candidate selection, and verification budgets across the decoding pipeline. Acceptance feedback provides a modest refinement: our diagnostic shows an approximately two-percentage-point improvement in prediction AUC for candidates with prior acceptance history, although its additional benefit to overall speed is limited. The comparison against recency-based expansion evaluates the complete pooled scoring mechanism, while the frequency-only ablation isolates the acceptance term.

We will clarify these contributions.

Reviewer_75vAOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper presents THRIFT, a training-free retrieval-based drafter that indexes the prompt using a suffix automaton (SAM) and the current generation using a trie. It asynchronously builds a corpus for each request and dynamically adjusts the draft tree size according to the batch's verification capacity. The authors compare THRIFT with DFlash, EAGLE-3, and SGLang's N-gram and SAM baselines, demonstrating improvements in decoding speedup.

Critical strengths

Well-motivated design. The analysis of different token types in Figure 1 provides a clear motivation for the proposed method. Based on these observations, using two different data structures to handle different types of reusable text is a natural and well-grounded design choice.

Critical weaknesses

1 Limited exploration of the combination strategy. The proposed method appears to be primarily a combination of trie-based retrieval and suffix automaton (SAM). Therefore, an important question is how to effectively combine these two components. However, the authors adopt a heuristic weighting strategy without providing sufficient ablation studies to justify this design. I would like to see a more detailed analysis of how different weighting strategies affect the accepted length and overall performance.

2 Insufficient comparisons with retrieval-based methods. Since long-context agent tasks are not necessarily well aligned with the training scenarios of DFlash and EAGLE-3, I believe retrieval-based speculative decoding methods should serve as the primary baselines. However, the paper only compares against two retrieval-based baselines provided by SGLang. Comparisons with other relevant methods, such as SuffixDecoding, are missing. Including these baselines would provide a more comprehensive and convincing evaluation of THRIFT.

Questions for authors

How does THRIFT support nonzero-temperature decoding? My understanding is that retrieval-based speculative decoding does not naturally support nonzero-temperature sampling under standard verification schemes. Could the authors clarify how speculative drafting and verification are performed in the experiments with a sampling temperature of 0.3? In particular, how is the correctness of the sampling distribution preserved?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 75vA

We thank the reviewer for their thorough and constructive feedback, here we address your concerns.

W1: Combination strategy. We ran ablations on how the two sources are combined, and the combination rule turns out to matter little: Fixed SAM/Trie splits (any ratio) give the same accept length under scored expansion. A split that adapts to recent acceptance is worse (8.21 vs 8.78 on 14B), because it starves the Trie that drafts the start of each turn. A per-step hindsight oracle that picks the best single source at every step gains only +3.8% (14B) / +5.7% (32B) over our pooled draft. So little is left for smarter weighting. What matters is what each structure indexes and how candidates are ranked. Ranking by acceptance-aware score instead of upstream recency is worth 1.49× / 1.35×. Placing the prompt tail in front of earlier outputs in the session Trie raises accept length at a turn's first step from 1.1 to 10.3.

W2: SuffixDecoding comparison. See General Response.

Q: Nonzero-temperature verification. SGLang uses standard token-tree verification. At T>0, each draft token is accepted with probability min(1,ptarget/pdraft)\text{min}(1, p_{target}/p_{draft}); rejected tokens are resampled from max(0,ptarget−pdraft)\text{max}(0, p_{target} − p_{draft}). For retrieval-based drafters, pdraft=1p_{draft}=1 for the proposed token, so acceptance probability = ptargetp_{target} — identical to typical acceptance. This preserves the target distribution exactly.

Thank you for the additional comments. I decide to maintain my score.

Reviewer_xaX8OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes THRIFT, which targets multi-turn workloads for coding agents. It uses a SAM to index the request prompt and a Trie to index the currently generated content, merging candidates from both sources into a draft tree. It then adjusts the draft budget by combining acceptance statistics with verification costs. Moreover, THRIFT offloads index construction and deallocation from the scheduling thread to reduce the blocking of concurrent decoding caused by request lifecycle management.

Critical strengths
  • The problem has practical value. Agent histories contain a large amount of reusable content; how to translate these candidates into actual gains in concurrent serving is well worth investigating.

  • The two candidate sources show a degree of complementarity. Experimental results demonstrate that SAM + Trie outperforms SAM-Only, supporting the claim that the currently generated content can provide additional useful candidates.

  • The engineering value of the lifecycle optimizations is clear. In the all-turns results in Table 4, moving from the initial synchronous version to the final design reduces the admission overhead from 26.4 ms to 4.4 ms, and improves the latency speedup from 1.66× to 2.28×.

Critical weaknesses

Insufficient comparison with existing work

Both SuffixDecoding (NeurIPS) and SAM-Decoding (ACL) are recent works that utilize SAMs or suffix trees for speculative decoding. In particular, targeting repetitive content in agent workloads, SuffixDecoding already maintains a per-request suffix tree indexing the current prompt and generation, alongside a global suffix tree for historical outputs. It also estimates acceptance probabilities based on candidate frequencies, greedily constructs multi-branch draft trees, and adaptively adjusts the draft budget based on match length. Furthermore, SuffixDecoding has already been evaluated end-to-end with concurrent OpenHands runs on SWE-bench tasks. Although THRIFT features different designs in terms of the division of labor between index structures, cross-source candidate merging, hardware cost control, and asynchronous lifecycle management, the paper lacks a direct comparison with SuffixDecoding. This makes it difficult to assess how much benefit these new designs bring compared to existing methods.

Additionally, the paper emphasizes cross-session mixing in the worker-global Trie, yet does not evaluate a request-isolated N-Gram baseline with access to the same prompt and generated tokens as THRIFT. Such a comparison would help distinguish the benefits of request isolation from those of the proposed retrieval design.

Marginal overall end-to-end improvement over N-Gram

While THRIFT achieves a significant speedup over autoregressive decoding, its overall gains over the existing N-Gram approach are limited. In Table 2, across all cleaned requests at T=0, the speedups for N-Gram and THRIFT are 1.75× and 1.78× on the 14B model, and 1.46× and 1.53× on the 32B model, respectively. The authors also acknowledge that the end-to-end performance gap falls within run-to-run noise.

Moreover, N-Gram uses a fixed 20-token draft budget, whereas THRIFT uses an adaptive budget of up to 50 tokens. I suggest comparing the two methods under a common draft-budget constraint to more accurately assess THRIFT's actual incremental gains.

Incomplete definitions for candidate retrieval, merging, and expansion make it impossible to uniquely determine the final draft tree

This is primarily an issue of unclear writing.

  • §3.1 does not report the actual value of the Trie depth (dd) used in the experiments.
  • The Trie query algorithm considers a suffix of up to d−1d-1 tokens, but does not specify how the suffix length is selected, whether shorter suffixes are tried when a lookup fails, or whether candidates from multiple suffix lengths are combined.
  • The SAM section mainly explains the case where a long match yields a single chain, but lacks complete rules for handling candidates when there are multiple outgoing edges, calculating frequencies, and deciding whether to include shorter suffix-link matches.
  • More critically, how the two sources (SAM and Trie) are combined to form P(c∣v)P(c∣v) is not explicitly defined. A long context in the SAM might appear only once yet already be highly discriminative; a short context in the Trie might appear frequently but carry low information. The paper does not explain how this situation is handled.
  • The description of the "BFS by score" algorithm is also not clear enough. The expansion order is ambiguous: processing parent nodes one by one and sorting only their respective children, versus aggregating all candidates across an entire level and sorting them globally, will retain different trees under a finite budget.

I recommend providing algorithm pseudocode (at least in the appendix) to clarify these ambiguities.

Unexplained inconsistencies between the width control rules and the cost model

The paper refers to the controller as AIMD, which is not literally accurate. The actual rule steps up by half an interval and steps down by one level along a non-geometric width ladder, lacking a clear definition of multiplicative decrease; how "stepping up by half an interval" maps back to the discrete set of widths is also unclear.

More importantly, the paper's own cost analysis requires the acceptance length to be sufficient to offset verification inflation, with the approximate condition being αˉ>I(K)αˉ>I(K). However, the controller in the paper's algorithm uses αˉ>1αˉ>1 as the condition for increasing the budget. Since the acceptance length includes the bonus token, by the paper's definition, αˉ≤1αˉ≤1 essentially corresponds only to the case where no additional draft tokens are accepted. Consequently, this rule may continue to increase the budget even when it still cannot offset the cost. The authors do not explain why this inconsistency exists between the cost analysis model and the algorithm design.

Finally, the cost-aware floor is intended to account for hardware cost constraints, but its description in the paper is vague and difficult to understand.

Replay orchestration is underspecified

The appendix states that the kk-th replay batch contains the kk-th turn of each instance, but does not specify whether there are synchronization barriers between batches, how requests are queued when the number of instances exceeds the actual batch size, whether waiting requests are immediately backfilled when active requests finish early, or how empty slots left by completed tasks are handled.

Grouping by turn is a viable controlled experimental method, but its representativeness needs justification. I would like to know why the authors did not use a replay method closer to real-world scenarios: preserving intra-session order while allowing different sessions to progress asynchronously. This can also be implemented using offline traces.

The authors' replay method might impact the Prefix Cache hit rate. For example, if the Prefix Cache hit rate drops due to KV Cache thrashing, the prefill time might be prolonged. The impact of these factors on the end-to-end gains remains unclear.

Questions for authors
  • Direct comparison with SuffixDecoding How much end-to-end benefit do THRIFT’s specific designs—division of labor between index structures, cross-source candidate merging, hardware cost control, and asynchronous lifecycle management—provide relative to SuffixDecoding?

  • ** Request-isolated N-Gram baseline** What is the performance of a request-isolated N-Gram baseline that has access to the same prompt and generated tokens as THRIFT?

  • N-Gram vs. THRIFT under a common draft budget Under the same draft-budget constraint, rather than N-Gram fixed at 20 tokens and THRIFT adaptive up to 50, does THRIFT still show a meaningful speedup over N-Gram?

  • Trie configuration and query rules What is the actual Trie depth dd used in the experiments? How is the suffix length selected during lookup? If a lookup fails, are shorter suffixes tried? Are candidates from multiple suffix lengths combined?

4 comments
AuthorsOpenReview ↗

Response to Reviewer xaX8

W1: SuffixDecoding / request-isolated N-Gram. See General Response.

W2: Marginal gain; same-budget comparison. Under a common draft budget (width 12), THRIFT still leads: 5.75× vs 5.42× at B=8 on 14B (accept length 5.91 vs 5.49). At width 20: THRIFT 6.41× vs N-Gram 6.16×. The advantage comes from the SAM's longer matches and scored expansion, not from a larger budget.

W3: Algorithm clarity. Below is the draft-tree construction and the adaptive width controller, in short:

  1. Anchors.
    • Trie: every context suffix up to depth D=18 that has children, so all matching lengths are used, not just the longest.
    • SAM: the longest match within the last 18 tokens, then each state along its suffix-link chain.
  2. Grouping. Anchors from all six sources (request/session/global × SAM/Trie) are grouped by matched length, longest first, and each group is expanded by one BFS.
  3. Scoring. At each node, every source proposes its top-10 children by count, which covers multiple SAM edges. Candidates are merged by token id and scored as 0.5·(source-weighted conditional frequency) + 0.5·(online accept rate).
  4. Selection. We keep the top-b children per node. b shrinks with depth and is smaller for longer matches. Ties break on token id.
  5. Stop. Expansion ends when W draft nodes are placed.

So the tree is uniquely determined, and sources are pooled inside one expansion rather than merged afterwards. The controller explores upward when drafting is productive and retreats when it is not. The cost guard ensures the tree never grows wider than what the current batch can verify profitably — this is why THRIFT uses width 50 at batch 2 but narrows to width 12 at batch 16 on 32B.

W4: AIMD vs cost model inconsistency. We thank the reviewer and would like to clarify the rule. The reported width for each model and batch size is w∗=argmaxw(1+a(w))/I(B,L,w)w^{*} = \text{argmax}_w (1+a(w)) / I(B,L,w). Here a(w)a(w) is the accept length at width ww, and I(B,L,w)I(B,L,w) is the measured forward-time inflation at batch size BB, context length LL and width ww. This is exactly the break-even condition, so the width never grows beyond what the batch can recover, and it shrinks as the batch grows (e.g. 32B: 33 at batch 2, 12 at batch 16). The online controller is an optional variant: it widens only when the draft tree is fully used and is capped by measured cost.

W5: Replay methodology. Turn-synchronous replay ensures every method sees the same batch composition at each step, enabling fair attribution of speedup to drafting quality rather than scheduling artifacts. Asynchronous replay would confound drafting gains with scheduling noise. Regarding prefix cache: all methods process the same prompts in the same order, so prefix-cache hit rates are identical across arms. We will add this justification.

Dear Reviewers,

This is a friendly reminder that the rebuttal discussion period is approaching its deadline.

Please take some time to review the authors' rebuttal and actively participate in the discussion. If you have any remaining questions or concerns, please raise them and share your feedback with the authors and other reviewers.

As the discussion period is about to close, we kindly ask you to complete your discussion and provide your updated assessment before the deadline.

Thank you for your time and effort.

Best regards,

Area Chair

Thank you for adding the detailed comparisons with SuffixDecoding and request-isolated N-Gram, as well as the other clarifications. Overall, these responses look reasonable to me. While I still have concerns about the not-so-significant speedup over SuffixDecoding and request-isolated N-Gram, I am somewhat more positive now and am happy to raise the score to weak acceptance.

AuthorsOpenReview ↗

Appreciation for constructive feedback

Thank you for reconsidering the paper and for your constructive feedback throughout the discussion. We will distinguish measured request latency from the additional offline forward-cost estimates and make the matched-budget comparisons explicit.

Reviewer_vqGtOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper looks at speculative decoding for coding agents instead of chat. The observation is that agents mostly re‑emit stuff that’s already in the prompt (they say ~70% of generated 4‑grams match earlier turns), so you can draft by retrieval from the prompt instead of running a draft model. THRIFT indexes the prompt with a suffix automaton and the current turn with a trie, merges both into one draft tree with a frequency + acceptance score, picks the tree width with an AIMD rule on a fixed ladder with a profiled cost cap, and builds the per‑request corpus asynchronously during prefill so it doesn’t block the scheduler. They also propose an evaluation protocol that classifies turns (fresh, rewrite, rerun, stall, periodic repetition), drops stalls/repetition from the main tables, and reports decode‑stage and end‑to‑end speedup separately. On BeyondSWE with Qwen3‑14B at batch 8 they get up to 3.86× end‑to‑end and win 11/12 cells at 16K+, with accept length growing over a session while EAGLE‑3/DFlash stay flat.

Critical strengths
  • The problem framing is right and timely. Agent decode really is mostly copying, and the per‑turn‑class breakdown (Table 3) showing the SAM owns rewrites/reruns and the trie only matters on fresh output and periodic repetition is a nice, honest piece of analysis.

  • The systems finding is good and clearly shown: synchronous per‑request corpus build costs 26 ms admission and makes you slower than the stock n‑gram drafter despite 62% more accepted tokens; moving it off the scheduler thread is what gets the win (Table 4). The authors are also upfront that the end‑to‑end margin is within noise, which I appreciate

Critical weaknesses
  • The closest prior work isn’t compared. SuffixDecoding (Oliaro et al. 2025) already does a per‑request suffix tree over prompt + generation, updated online, evaluated on concurrent SWE‑bench agents — i.e. basically the “two corpora” idea. The paper acknowledges there’s no direct comparison, and the “SGLang SAM” baseline is a suffix automaton over task statements, not over the prompt, so it doesn’t stand in. Likewise the stock N‑Gram baseline is handicapped by scope (worker‑global, loses 41% of supply per the paper’s own number), not by structure: a per‑request n‑gram trie over the prompt is the fair ablation and it isn’t there. Hard to say what’s novel vs. engineered without these

  • Over all requests the gain over the stock n‑gram drafter is tiny: 1.78x vs 1.75x (Table 2, T=0), 1.77 vs 1.73 at T=0.3, 1.53 vs 1.46 on 32B. The 3.86× headline is one cell where N‑Gram gets 3.18×. “Mean over four GPU pairs” but no std, no per‑cell request counts — and some cells look like a handful of requests (DepMigrate 24K: Acc 22.5, AR throughput 45 tok/s vs 53–69 everywhere else). THRIFT also loses every 8K cell. The intro’s “clear” decode margin is 3.06 vs 2.94

  • The paper’s own ablations say two of the four listed contributions don’t do anything: scored expansion with the acceptance estimate gives identical tokens/forward to frequency‑only (Table 7, 8.63 vs 8.64; identical on cleaned view), and fixed width 24 matches AIMD latency (Table 4). That’s fine to report but the contribution list and conclusion should reflect it. What’s left is SAM‑over‑prompt (known) + async lifecycle (the real contribution)

Questions for authors
  • Can you add SuffixDecoding, or at minimum a per‑request version of the N‑Gram trie over the prompt? That’s the comparison that determines whether the two‑structure design matters.

  • The cleaned view drops 46% of turns at T=0 and 57% at T=0.3 (Appendix B). Please show the uncleaned Table 1 too. stalls/repetition are where retrieval does best (Table 3), so I’d like to see both, and the “drop any request >10 s in any method” rule needs some justification.

  • Where does the 3.06x/2.94x decode number in the intro come from? Table 4 says 4.22 vs 3.31, Fig 3b at B=8 looks like ~2.9 vs ~3.1. Why does THRIFT lose all four 8K buckets to N‑Gram?

  • Main results are batch 8; the motivation is concurrency. Fig 3b shows the lead shrinking to ~2.4× at B=32. can you give end‑to‑end at 16/32?

  • Is the 70% reuse figure (40 instances, 4‑gram match) counting the stalls and repetition you later exclude? What is it on the cleaned view?

2 comments
AuthorsOpenReview ↗

Response to Reviewer vqGt

We thank the reviewer for their thorough and constructive feedback, here we address your concerns.

W1: SuffixDecoding / request-isolated N-Gram. See General Response.

For the request-isolated ablation: THRIFT at width 12 with no session state is effectively a request-isolated retrieval baseline (SAM over the prompt + Trie over the current generation). At the same width 12:

Configuration14B B=8Source
SGLang N-Gram (worker-global, w=12)5.42×Global Trie
THRIFT request-isolated (w=12, no session)5.75×Request SAM + Trie
THRIFT full (w=20, session context)7.22×SAM + session Trie

This isolates the contribution of request-local retrieval (+6%) from the session context (+13%) and the wider draft tree (+11%).

W2: Small overall gain (1.78× vs 1.75×). Table 2 compared THRIFT (adaptive, up to 50) vs N-Gram at its default width 12. A fairer comparison, each at its best width under measured forward costs, shows a clear gap at every batch size (see General Response table). At B=8 on 14B: N-Gram's best width is 20 (6.16×), not its default 12; THRIFT at width 20 reaches 7.86×. Even at the same width 20, THRIFT leads by 1.28× (1.19 vs 1.38).

W3: Scored expansion and AIMD don't help. Table 7's "identical tok/fwd" (8.63 vs 8.64) measures at the same width, hiding the fact that scoring enables profitable use of wider trees. Our new ablation, changing one ingredient at a time with measured forward costs:

Change from N-Gram baseline14B B=8
SAM over prompt + scored ranking1.061 [0.995, 1.127]
Width 12 → 201.114 [1.056, 1.174]
Session Trie (output only)1.000
+ 8 prompt-context tokens in Trie1.126 [1.096, 1.166]

Without scored ranking, THRIFT falls below N-Gram (4.87× vs 5.42× at B=8 on 14B). Scoring is the single largest contributor.

AIMD's benefit is in the all-turns view (+12%) where it avoids wasting budget on stalls. On cleaned turns, a fixed good width matches it — we will state this explicitly.

Q: Source of 3.06×/2.94× decode numbers. Table 4 reports all-turns; Fig 3b reports cleaned turns at varying batch sizes.

Q: THRIFT loses at 8K. At 8K, sessions are early (1–3 turns) with little reuse, so THRIFT's SAM/Trie have sparse content while N-Gram's worker-global Trie captures the rolling context window including the generation prompt.

Q: 70% reuse on cleaned view. The 70% is over all turns (40 instances, 4-gram match). On the cleaned view the fraction is lower but still grows monotonically with session progress.

Q: B=16/32 end-to-end. Compare with N-Gram baseline, at we have B=16 THRIFT 2.04× vs N-Gram 1.87×; at B=32 we have THRIFT 1.74× vs 1.62×.

Q: Uncleaned Table 1. We will add it. The cleaning drops stalls (empty output, no drafting opportunity) and periodic repetition (inflates all retrieval methods equally). The >10s filter removes scheduling outliers that affect wall-clock but not drafting quality.

Dear Reviewers,

This is a friendly reminder that the rebuttal discussion period is approaching its deadline.

Please take some time to review the authors' rebuttal and actively participate in the discussion. If you have any remaining questions or concerns, please raise them and share your feedback with the authors and other reviewers.

As the discussion period is about to close, we kindly ask you to complete your discussion and provide your updated assessment before the deadline.

Thank you for your time and effort.

Best regards,

Area Chair

Reviewer_hvSKOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies speculative decoding for multi-turn coding agents, where generated text frequently reuses content from earlier interactions. The proposed system, THRIFT, combines a suffix automaton over the prompt with a Trie over the current generation, merges their candidates into a draft tree, builds request-specific indices asynchronously, and adjusts the draft budget according to acceptance feedback and verification cost. On BeyondSWE with Qwen3-14B at batch size 8, THRIFT achieves the highest request-level speedup in 11 of the 12 settings with contexts of 16K or longer, reaching up to 3.86× over autoregressive decoding. The work addresses a practically relevant problem, although its novelty relative to existing retrieval-based methods and the fairness and coverage of its evaluation require further clarification.

Critical strengths
  1. Long prompts and relatively short generation bursts make index construction and request management important contributors to latency. The asynchronous index lifecycle reduces admission overhead from 26.4 ms to 4.4 ms, demonstrating attention to actual serving bottlenecks beyond draft acceptance alone.

  2. The prompt suffix automaton targets long reused spans, while the generation Trie captures recurring local patterns within the current turn. On fresh output, combining them increases accepted tokens per forward to 2.81, compared with 1.89 for the Trie and 2.12 for the suffix automaton individually.

  3. Stratifying turns by their relationship to earlier outputs, excluding stalls and periodic repetition from the primary results, and reporting speedups that include prefill provide a more informative assessment than acceptance length alone.

Critical weaknesses
  1. The additional contribution over SuffixDecoding and SAM-Decoding remains insufficiently established. SuffixDecoding already studies repetitive agent outputs using request-level prompt/generation indexing, frequency-based scoring, and adaptive speculation. SAM-Decoding likewise uses suffix automata to retrieve continuations from generated text and a static corpus. The distinction between the contributions of this article and the aforementioned article requires a more detailed explanation.

  2. The training context lengths of EAGLE-3 and DFlash are insufficiently documented, leaving the fairness of the long-context comparison unclear. The current SpecForge does not support context training with more than 8k words, and will encounter the OOM issue. Only by using Megatron and CP can this problem be solved. The paper reports retraining DFlash with SpecForge, but does not specify the maximum training sequence length, the training-length distribution, whether drafter was adapted or retrained for contexts of 8K and above and whether EAGLE-3 was retrained. It is unclear whether the authors modified the original training implementations or the SpecForge configuration to enable the relevant long-context training. If these drafters were trained primarily on short sequences, their weaker performance at longer contexts could partly reflect a training–evaluation mismatch rather than an inherent limitation of learned drafting. Training on longer, representative sequences could improve acceptance and speedup. The authors should disclose the exact training configurations and any code changes, and evaluate suitably trained long-context draft models before drawing broad conclusions about their inability to benefit from growing agent histories.

  3. The temperature evaluation does not cover higher-temperature sampling settings in the mainstram using. The experiments use temperatures 0 and 0.3, leaving performance under more stochastic multi-turn agentic generation untested. When the model is being processed online, a more effective temperature configuration is usually used, such as 0.8 or 1.0. And higher temperatures can change both the amount of reusable text and the draft acceptance rate, while also producing different interaction trajectories. Therefore, the relative advantage observed at low temperatures may not persist under these settings. The authors should include temperatures 0.8 and 1.0, generate trajectories under each configuration, and compare acceptance lengths and request-level speedups across methods.

  4. The context-length evaluation does not establish effectiveness at 64K or 128K tokens. The experiments use a configured context window to 32K. Multi-turn agent sessions that accumulate repository content and tool outputs can exceed this range easily in the practical usage, making substantially longer contexts relevant to the paper's motivation. Longer prompts may provide more reusable content, but also increase index construction costs, CPU memory consumption, and verification-related KV traffic; the balance between these effects is not established by the current results. Evaluation at 64K and 128K, using target checkpoints and context configurations that support those lengths, would clarify whether THRIFT's advantage persists as agent histories continue to grow.

Questions for authors

See the weakness.

3 comments
AuthorsOpenReview ↗

Reply to Reviewer hvSK

We thank the reviewer for their thorough and constructive feedback, here we address your concerns.

W1: Novelty over SuffixDecoding / SAM-Decoding. See General Response above.

W2: Training baseline fairness. DFlash was retrained with SpecForge on Open-PerfectBlend for one Epoch; EAGLE-3 uses the SpecForge pretrained checkpoint. We apply SpecForge's maximum training sequence length is 8,192 tokens and we made no modifications. Actually the fundamental limitation of learned drafters on agent workloads is not training length but architectural: a draft model predicts the next token from target model's hidden state, while the agent's decision to re-emit a file it saw 20K tokens ago is a retrieval problem. Retraining on longer sequences may improve short-range prediction but cannot substitute for indexing the full prompt.

W3: Higher temperatures (0.8, 1.0). Agent frameworks (OpenHands, SWE-Agent, Agentless) universally use T=0 or T≤0.3 as their serving default. T=0.8–1.0 is a conversational setting; under it, agent task-completion rate drops substantially, we will add a discussion of why higher temperatures are atypical for agents.

W4: 64K / 128K contexts. We have tried to extend existing agent benchmark to longer context like 64K or 128K, we found that extend directly will mast of the latter loop become dead-loop, which will created many duplicated but useless context, this will further increase the speed up result as our method focusing on identify repeated content, but can not reflect real agent workload.

Thank you for your patient response!

  1. In your general response, you mentioned that you ported SuffixDecoding from its official vLLM implementation to SGLang. However, the results reported in the table show that SuffixDecoding does not outperform the n-gram trie baseline. This is inconsistent with the benchmark results reported in the SGLang GitHub issue (https://github.com/sgl-project/sglang/issues/13165), opened in November 2025, where SuffixDecoding achieves substantially better performance than n-gram decoding. I suggest referring to the implementation discussed in this issue to verify the correctness and efficiency of your implementation. Could you explain the reasons for this discrepancy and clarify whether it stems from implementation differences, experimental configurations, or workload characteristics?

  2. In your second response, you mentioned that you retrained DFlash for one epoch. However, draft models based on bidirectional attention, such as DFlash, may require more training data and additional epochs to achieve convergence. For example, Domino trains its draft model for three epochs on Open-PerfectBlend. Therefore, I would like to know whether the DFlash baseline used in your comparison was sufficiently trained and whether its convergence was verified.

Furthermore, I remain concerned about the fairness of evaluating draft models on long-context inference when they have not been adequately trained on contexts of comparable lengths. Such a training–inference mismatch may underestimate the actual capabilities of these baselines. I suggest conducting additional experiments with publicly available models, such as MiMo with DFlash and Qwen3.5 with MTP. They not only support 32K-context inference but can also handle context lengths of up to 256K. These comparisons would provide more convincing evidence that your proposed method can outperform well-trained, training-based speculative decoding approaches in agentic workloads.

  1. Regarding the claim that "Agent frameworks universally use T=0 as their serving default," I would like to point out that such a configuration is primarily motivated by execution stability, experimental reproducibility, and ease of debugging, rather than maximizing task success rates. However, T=0 is not necessarily the optimal decoding configuration, as the optimal temperature varies across models and tasks. For instance, the official Qwen3 model card on Hugging Face recommends T=0.6 for thinking mode and T=0.7 for non-thinking mode, and explicitly advises against greedy decoding in thinking mode due to potential performance degradation and endless repetitions. While I understand the choice of T=0, given that greedy decoding is a standard evaluation setting in the speculative decoding literature, prior studies also commonly report results under T=1. I encourage the authors to evaluate their method under appropriate sampling temperatures to better demonstrate its effectiveness and practical applicability.
AuthorsOpenReview ↗

Reply to Reviewer hvSK

Thank you for the following-up comments and suggestions. Our SGLang implementation uses the same ArcticInference suffix cache and drafting policy as the Arctic-backed vLLM implementation. Issue #13165 reports similar acceptance lengths and throughput on GSM8K. The speedup comes from the later SpecBench and Blazedit runs, where SuffixDecoding drafted fewer tokens while accepting similar totals. Shorter drafts could make each verification step cheaper when the number of verified positions follows the actual draft length, although the issue does not isolate this cost. Our evaluation uses multi-turn BeyondSWE traces in which the prefix cache pool is larger, which require larger verification cost (selected via best E2E by HPO) and under this experiment setting, which is close to N-Gram, but N-Gram accepted more tokens per forward. The results are therefore compatible across the two evaluation settings. For training data, currently there is not standard training pipeline for DFlash over long context, but the final version of origin paper also report long context results, so we follow the setting in SpecForge. For additional models like Qwen 3.5/3.6, we have test Qwen 3.5/3.6 previously, they can achieve similar accept length (comparable with on Qwen 3, better than MTP or DFlash on Qwen 3.5/3.6) but the main bottom neck is the intermediate state buffers created by linear attention, we will mark this as our future works. And for Higher Temperature, we execute additional test on Qwen3-14B with 2 ×\times H100 GPU, batch size 8, the result is presented as follows:

TempuratureOurs methods
09.91 / 7.53$\times$
0.37.45 / 6.12$\times$
0.77.04 / 5.82$\times$
1.06.64 / 5.58$\times$

The speed up drops but not so much, we believe that's the results of lower PPL in coding agent workload.

Thanks again for your additional comments and corrections, we will keep working on improving look up based SD on agent severing and try to adapt it to linear attention model.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response for shared concerns

We thank all reviewers for their thorough and constructive feedback. We address the shared concern first, then respond to each reviewer individually. We migrate the SuffixDecoding from its official vllm implementation (arctic-inference library) to SGLang and evaluate it in our evaluation framework, as shown in following table (N-Gram and SuffixDecoding are evaluated in some widely used settings and our method is evaluated with its adaptive strategy):

ModelBatchN-Gram w=12 / 20 / 33SuffixDecoding w=12 / 20 / 33THRIFT (adaptive)
14B85.56× (6.49) / 6.16× (7.71) / 5.55× (8.46)5.01× (5.85) / 5.38× (6.71) / 4.73× (7.19)7.86× (9.82)
14B165.29× (6.49) / 5.04× (7.71) / 4.72× (8.46)4.77× (5.85) / 4.40× (6.71) / 4.02× (7.19)6.44× (11.44)
32B83.97× (4.70) / 3.85× (5.17) / 3.36× (5.33)3.81× (4.53) / 3.73× (5.02) / 3.35× (5.32)4.91× (6.60)
32B163.73× (4.70) / 2.98× (5.17) / 2.79× (5.33)3.57× (4.53) / 2.88× (5.02) / 2.78× (5.32)4.38× (5.54)

From the table we can see SuffixDecoding's performance is comparable to SGLang's stock N-Gram, and our THRIFT has advance stably. The experiments is done upon same settings: 2 ×\times H100 80G SGlang with Prefix Caching (98% hit rate), so the main time cost is decoding; Qwen 3 Model; Using tasks from 4 categories in Beyound-SWE, the context of each task is about 20K in average.


The key design difference is that THRIFT combines a SAM (suffix automaton) with an N-Gram Trie: the SAM retrieves long-range matches from the full prompt history, while the Trie captures local generation patterns. Both contribute candidates to a shared pool, and scored expansion selects the best from either source. SuffixDecoding and stock N-Gram each rely on a single retrieval structure. Further: (a) SAM's O(n) construction runs asynchronously off the scheduler thread, while SuffixDecoding's online tree update is synchronous; (b) scored expansion ranks candidates by acceptance history, not just frequency — the single largest contributor per our ablation; (c) cost-aware width selection adapts to the batch's verification capacity.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.