batch-speculative-decoding

name	batch-speculative-decoding
title	Batch Speculative Decoding Done Right
version	0.0.2
engine	skillxiv-v0.0.2-claude-opus-4.6
license	MIT
url	https://arxiv.org/abs/2510.22876
keywords	["Decoding","Inference Optimization","Speculative Execution","Batching"]
description	Fixes batch speculative decoding ragged tensor problem where sequences in batches accept different token counts, desynchronizing state. EQSPEC guarantees output equivalence through proper synchronization. EXSPEC reduces overhead 40% via cross-batch scheduling. Enables efficient parallel decoding with 95% equivalence.

Batch Speculative Decoding Done Right: Fixing the Ragged Tensor Problem

Speculative decoding accelerates inference by using draft models to generate multiple tokens, verified by main model. However, batched versions have critical synchronization bugs: sequences accepting different draft lengths causes KV-cache and attention mask misalignment.

EQSPEC and EXSPEC fix these issues, enabling correct and efficient batch speculative decoding.

Core Concept

The problem: in batches, each sequence may accept different numbers of draft tokens, leading to:

• Misaligned KV-cache states
• Inconsistent attention masks
• Incorrect position IDs
• Near-zero output equivalence (wrong answers)

Solutions:

• EQSPEC: Formal synchronization protocol guaranteeing output equivalence
• EXSPEC: Efficient scheduling reducing computational overhead by ~40%

Architecture Overview

• Draft model generates K tokens per sequence
• Verification: main model checks draft token acceptance
• Synchronization: enforce ragged tensor handling
• Cross-batch scheduling: group sequences by similar acceptance patterns

Implementation Steps

Implement proper speculative decoding with synchronization. The key is tracking which draft tokens each sequence accepted:

class SpeculativeDecodingEQSpec:
    def __init__(self, draft_model, main_model, draft_tokens=4):
        self.draft_model = draft_model
        self.main_model = main_model
        self.draft_tokens = draft_tokens

    def speculative_generate(self, input_ids, max_length=256):
        """Speculative decoding with synchronization (EQSPEC)."""
        batch_size = input_ids.shape[0]
        current_ids = input_ids.clone()

        # Track accepted tokens per sequence
        accepted_counts = torch.zeros(batch_size, dtype=torch.long)

        while current_ids.shape[] < max_length:
            
            draft_ids = .draft_model.generate_tokens(
                current_ids, num_tokens=.draft_tokens
            )  

            
            
            acceptance_mask = ._verify_draft_tokens(
                current_ids, draft_ids
            )  

            
            per_seq_accepted = ._count_accepted_per_sequence(
                acceptance_mask
            )  

            
            max_accepted = torch.(per_seq_accepted)

            
            synchronized_sequences = []
            synchronized_kv_cache = {}

             seq_idx  (batch_size):
                
                num_accepted = per_seq_accepted[seq_idx].item()
                new_tokens = draft_ids[seq_idx, :num_accepted]

                
                 num_accepted < max_accepted:
                    padding = torch.full(
                        (max_accepted - num_accepted,),
                        .main_model.pad_token_id,
                        dtype=torch.long
                    )
                    new_tokens = torch.cat([new_tokens, padding])

                synchronized_sequences.append(new_tokens)

            
            synced_ids = torch.stack(synchronized_sequences)
            current_ids = torch.cat([current_ids, synced_ids], dim=)

            
            current_ids = ._remove_padding(current_ids)

             torch.(accepted_counts >= .draft_tokens):
                
                next_tokens = .main_model.generate_tokens(
                    current_ids, num_tokens=
                )
                current_ids = torch.cat([current_ids, next_tokens], dim=)

         current_ids

     ():
        
        
        main_logits = .main_model(
            torch.cat([context, draft_ids], dim=)
        )[]

        
        
        context_len = context.shape[]

        acceptance_mask = torch.zeros_like(draft_ids, dtype=torch.)

         token_pos  (.draft_tokens):
            logit_pos = context_len + token_pos
            main_probs = torch.softmax(main_logits[:, logit_pos, :], dim=-)

            
            draft_token = draft_ids[:, token_pos]
            draft_probs = main_probs.gather(, draft_token.unsqueeze()).squeeze()

            
            acceptance_mask[:, token_pos] = draft_probs > 

            
              torch.(acceptance_mask[:, token_pos]):
                

         acceptance_mask

     ():
        
        counts = torch.zeros(acceptance_mask.shape[], dtype=torch.long)

         seq_idx  (acceptance_mask.shape[]):
            
             token_idx  (acceptance_mask.shape[]):
                 acceptance_mask[seq_idx, token_idx]:
                    counts[seq_idx] += 
                :
                    

         counts

     ():
        
        
        non_pad_ids = []
         seq  ids:
            end_idx = (seq != .main_model.pad_token_id).nonzero()
             (end_idx) > :
                end_idx = end_idx[-].item() + 
                non_pad_ids.append(seq[:end_idx])
            :
                non_pad_ids.append(seq)

        
         non_pad_ids