From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models

1 Introduction

• Token-level generation, or decoding, samples tokens individually or searches token-level spaces, typically using logits, next-token distributions, or probability scores.The survey covers methods from greedy decoding and beam search to nucleus sampling (Holtzman et al., 2020) and η-sampling (Hewitt et al., 2022).Source: §1 · p. 3
• Meta-generation treats the LLM as a black box and operates on partial or full sequences, using parallel generation, search, or refinement to improve performance or steer outputs.Methods may use multiple model calls, external data, or tools; reported applications include problem solving (Lewkowycz et al. (2022)) and preference steering (Stiennon et al. (2020)).Source: §1 · pp. 3–4
• Efficient generation addresses both token costs and systems-level latency and throughput, while shared computation in meta-generation can create opportunities to improve efficiency.The survey distinguishes token-cost tradeoffs, especially for API models, from weight-access methods for speeding generation; efficiency can also expand which algorithms are feasible to develop.Source: §1 · pp. 3–4
• The survey presents a unified mathematical framework for classical generation algorithms and modern meta-generators, connecting NLP, LLM, and machine-learning-systems perspectives to promote inference-time research.It aims to help researchers connect algorithmic patterns, historical context, and practical efficiency constraints.Source: §1 · p. 4
• Earlier surveys treat decoding, prompting, or inference speed largely separately, whereas this survey connects those areas with meta-generation and focuses on autoregressive generation.It distinguishes its scope from Xiao et al. (2023), which focuses on non-autoregressive generation.Source: §1 · p. 4

2.1 The user’s goal in generation

• Users’ diverse, often unenumerable goals are modeled as acceptability scores over output sets, normalized into a target distribution q*, which generation aims to approximate.In practice, acceptability and the desired proximity measure are unknown, so algorithms optimize proxies of acceptability.Source: §2.1 · p. 5

2.2 The modeling problem

• An autoregressive LM factorizes pθ(y|x) into next-token conditionals, while a generation model g maps an input, model, and parameters to an output distribution.The distribution is generally analytically intractable, so algorithms obtain samples from it; the framework groups generation methods into maximization, model sampling, and target-distribution sampling.Source: §2.2 · p. 6

2.2.1 Maximization

• Decoding is score maximization, performed deterministically or with high probability, using approaches such as greedy, concave, combinatorial, or stochastic algorithms.Source: §2.2.1 · p. 6

2.2.2 Sampling

• Sampling algorithms draw from a distribution derived from the model, and their samples can be used for purposes such as maximizing a task-specific quality-diversity metric.Source: §2.2.2 · p. 6

2.2.3 Sampling from a specified target distribution

• A sampler for a specified target distribution approximates that target, with an optimal algorithm yielding unbiased samples from q*(·|x).Source: §2.2.3 · p. 7

3.1 MAP decoding algorithms

• MAP decoding can favor short or empty outputs under wide or exact search and trap approximate decoding in repetition; its mode may be arbitrary or outside the typical set.Length normalization can mitigate short-output bias but does not fully prevent degradation at the largest beam sizes.Source: §3.1 · p. 8

3.2 Sampling and adapters

• Ancestral sampling recursively draws next tokens to sample from pθ(y|x), avoiding MAP repetition traps but risking incoherence; truncation and temperature strategies seek to balance diversity and coherence.Nucleus, top-k, η- and ϵ-sampling filter tokens by probability thresholds, while temperature scales logits.Source: §3.2 · p. 9

3.3 Token-level sampling adapters

• Sampling adapters transform next-token distributions, sometimes using lookahead or another language model for sequence criteria, correction, speed, or style; APIs increasingly hide these distributions.Temperature ranges from greedy decoding as τ approaches 0, through ancestral sampling at τ = 1, toward uniform sampling as τ increases.Source: §3.3 · pp. 9–10
• Shi et al. (2024a) found no definitive best adapter for evaluated open-ended tasks, while temperature usually outperformed other adapters for code generation and translation.Which adapter to use remains an open question.Source: §3.3 · p. 10

3.4 Controlled generation

• Controlled generation modulates the language-model distribution with sequence-level criteria, using classifiers for attributes or verifiers and search heuristics for outputs such as correct solutions or desired keywords.Classifier-based methods can reweight next-token distributions or train to sample from a target distribution; verifier-based and beam-search methods address indicator criteria.Source: §3.4 · pp. 10–11
• Reward-based generation balances reward against pretrained-model probability, including human-preference alignment through reinforcement learning or reward-augmented decoding of top-k tokens.Reward-augmented decoding reweights top-k candidates using rewards assigned to partial generations.Source: §3.4 · p. 11

3.5.1 Parser-based decoding for structural constraints

• Parser-based structural decoding strictly filters next-token candidates to valid continuations; parser complexity varies by formalism, while token healing and minimally invasive designs address tokenizer-boundary and overconstraint problems.Finite-state regular-expression parsers can recognize valid continuations in constant time and space; template-heavy constraints may also skip model forward passes when only one token is valid.Source: §3.5.1 · pp. 12–13

3.5.2 Lexically constrained decoding

• Lexically constrained decoding uses search to find likely outputs containing required words, with NeuroLogic encoding constraints as conjunctive-normal-form formulas and enforcing them through modified beam search.Follow-up work adds lookahead to NeuroLogic decoding.Source: §3.5.2 · p. 13

4 Meta-generation algorithms

• Meta-generation calls interchangeable sub-generators under a strategy that may also use verifiers, retrieval models, or hyperparameters.The section identifies four strategies: chained, parallel, step-level, and refinement-based.Source: §4 · p. 13

4.1 Chained meta-generators

• Chained meta-generators compose generation calls and other operations as programs, an abstraction independent of the underlying generator model.Related formulations include DSP and DSPy (Khattab et al., 2022; 2024), language model cascades (Dohan et al., 2022), LLM programs, and scaffolding programs.Source: §4.1 · p. 14

4.2 Parallel meta-generators

• Parallel meta-generators generate multiple full-sequence trajectories, then aggregate them by reranking, transforming, or sequence-level rejection sampling.Candidate lists can come from sampling, beam search, or another sequence generator.Source: §4.2 · p. 15

4.2.1 Reranking algorithms

• Best-of-N generates N candidates and selects by a scoring function; it can use black-box generators and typically scales computational cost linearly versus top-1 decoding.In preference alignment, AlpacaFarm found Best-of-1024 with a human-preference reward model competitive with standard decoding using an RLHF-trained model; high N can also exploit reward-model errors and return undesired sequences (Gao et al., 2022).Source: §4.2.1 · pp. 15–16

4.2.2 Transformation algorithms

• Transformation methods turn candidate sequences into outputs that may not appear in the candidate list, using voting, minimum Bayes risk, or language-model synthesis.Weighted voting converges to accuracy after marginalizing intermediate sequences and outperforms unweighted voting when v · g has more total mass on correct answers than g; MBR performance can vary with sampling strategy and inflate the metric it uses (Freitag et al., 2023).Source: §4.2.2 · pp. 16–18

4.2.3 Sequence-level rejection sampling

• Sequence-level rejection sampling draws from a known upper-bound distribution and accepts with probability q*(y)/Mg(y), enabling sampling from a target with unknown normalization.Pseudo-rejection and importance-resampling variants are used when rejection sampling prerequisites, such as a known upper bound, are unavailable; best-of-N with a stochastic generator is also related to rejection sampling.Source: §4.2.3 · pp. 18–19

4.3 Step-level search algorithms

• Step-level search models generation as state transitions: in reasoning tasks, partial solutions are states, next steps are actions, and value functions estimate eventual correctness or reward.Algorithms can vary the states, actions, environment, or generator, including environments that execute code or provide visual observations (Zhou et al., 2023b).Source: §4.3 · p. 19
• Partial-sequence expansion lets stepwise beam search and Tree-of-Thoughts search over generated steps, potentially reducing value-function calls and avoiding access to all next-token probabilities.Examples include mathematical problem or proof steps and additional “thought” sequences.Source: §4.3 · p. 20
• MCTS and other search strategies extend step-level generation beyond beam search, but large simulation costs and the lack of reliable terminal rewards limit direct transfer from Go.Best-first search has been used in theorem proving, while MCTS has been adapted to LLM tasks; AlphaGo Zero used 1,600 simulations per move. Related approaches include HyperTree Proof Search, Reasoning via Planning, and ThoughtSculpt.Source: §4.3 · p. 20
• Step-level search can use designed or learned value functions, prompted language-model evaluators, and process-based verifiers to score states and guide exploration.Examples include n-gram preferences, predictions of style or correctness, proof success or length, and Rebase’s allocation of exploration budget by process-verifier scores.Source: §4.3 · pp. 20–21

4.4 Refinement algorithms

• Refinement alternates between receiving information and revising prior outputs; learned refiners include Self-Correction, while prompted refiners include Self-Refine and Reflexion.GLoRe trains a verifier to decide whether to refine and localize per-step errors; Self-Refine shares one model across feedback, refinement, and initial generation.Source: §4.4 · p. 21
• Refinement works best when feedback adds useful information, such as environment results, while intrinsic prompted self-correction has mixed results and can fail when evaluation is unreliable.Compiler feedback can assess correctness, localize errors, and convey error semantics; unlike Best-of-N, a refiner can transform the output using that information. Self-correction often fails on reasoning tasks, and verifiers can trigger spurious refinements; overall, rich environment feedback or reliable evaluation supports effectiveness.Source: §4.4 · pp. 22–23
• Training intrinsic refiners remains challenging: self-corrective learning can collapse by ignoring the intermediate output, while reinforcement learning alleviates this behavior and enables some self-correction.Learning intrinsic self-correction remains an active research direction.Source: §4.4 · pp. 22–23

5.1 Multiple models

• Small models can adjust or contrast a larger model’s token scores, while speculative decoding uses draft proposals that the larger model verifies in parallel.Lu et al. (2023) train a small model to adjust the larger model’s next-token probabilities; contrastive decoding (Li et al., 2023a) compares likelihoods and truncates some token scores. Speculative decoding (Leviathan et al., 2022) can speed generation when the rejection rate is not too high.Source: §5.1 · p. 23
• Scalar verifiers score correctness to select or vote over outputs, and process-based verifiers can outperform outcome-based verifiers.Verifiers are especially suitable for mathematics and code, where correctness is well-defined; weighted majority voting with a verifier can improve generalization to harder problems.Source: §5.1 · pp. 23–24
• Prompts can provide new information by eliciting feedback or by perturbing an input prompt to adjust token-generation logits.Kim et al. (2024b) use logits from a perturbed input prompt to adjust the logits used for token-level generation.Source: §5.1 · p. 24

5.2 External environment information

• External routines can perform tasks that are unreliable or inefficient for a language model, either during decoding or after a sequence is generated.A special token can trigger a calculator call, with its result inserted into the prefix; proof assistants can verify generated proofs, and code can be checked by executing tests.Source: §5.2 · p. 24
• Generation can incorporate environment observations, such as execution results or error messages, and digital-agent observations from diverse spaces such as web-page images.Lever (Ni et al., 2023) feeds execution results into a reward model for best-of-N, while Self-Debugging uses error messages in refinement.Source: §5.2 · p. 24

6.1 Token budget

• When total solution length is fixed, step-level search uses fewer output tokens than sequence-level search if Nb * Ne < N; with Nb = 16, Ne = 64 matches best-of-1024, while Ne = 32 halves its output cost.The comparison assumes Ts * S = T; Table 5 summarizes token budgets for representative meta-generation classes.Source: §6.1 · p. 25, Table 5 · p. 25
• When Nb * Ne = N, step-level beam search calls the scoring model N * S times versus N times for reranking, so external-information costs also matter (Table 5).Scoring costs may include sequence scores, and the table defines costs for reranking, transformation, step-level search, and refinement.Source: §6.1 · p. 25, Table 5 · p. 25
• Refinement has lower output cost than best-of-N when Nr < N; with self-feedback, three refinements cost 7T output tokens, less than best-of-8 (Madaan et al., 2023).The passage notes that Madaan et al. (2023) use Nr = 3 in many experiments, while N in the literature typically ranges from 8 to 1024; external-information costs must also be considered.Source: Table 5 · p. 25, §6.1 · p. 26

6.2 Scaling the token budget to improve performance

• On MATH500, sequence-level methods improved monotonically as sample budgets rose, and weighted voting outperformed majority voting and best-of-N at 1,024 sequences, although some models show non-monotonic voting performance.AlphaCode generated up to a million programs for filtering (Li et al., 2022), while Draft-Sketch-Prove increased the percentage of proven theorems monotonically with budget (Jiang et al., 2023).Source: §6.2 · p. 26, Figure 6 · p. 26

6.3 Minimizing the token budget

• FrugalGPT routes requests from a cheap model to a more expensive one when a learned score indicates another generation is needed, reducing costs versus GPT-4 in its experiments; majority voting can stop when a majority converges (Aggarwal et al., 2023).Both are approaches to minimizing the generation budget for a target performance level.Source: §6.3 · p. 27

6.4 Compute optimal inference

• At a fixed compute budget, sampling more tokens from a smaller model often offered better cost-performance tradeoffs than using a larger model, while Monte Carlo tree search often fared worse than other meta-generators.Compute-optimal inference chooses model size, generated tokens, and meta-generator to minimize error under a compute constraint.Source: §6.4 · p. 27

6.5 Dependence on the underlying generator(s)

• Best-of-N’s optimal temperature depends on N in Codex code generation, with higher temperatures performing better at higher N (Chen et al., 2021).Many studies use sampling parameters that are unexplained or ad hoc; Minerva’s temperature 0.6 and nucleus sampling p = 0.95 were adopted by subsequent studies (Lewkowycz et al., 2022; Azerbayev et al., 2024).Source: §6.5 · p. 27
• In minimum Bayes risk translation, performance varies by underlying sampling strategy, with epsilon sampling performing best (Freitag et al., 2023).Source: §6.5 · p. 27

7.1 Background

• Speed requires balancing latency, throughput, and quality, while hardware-aware co-design matters because reducing theoretical operations may not yield proportional real-world gains.GPU bottlenecks depend on compute and memory bandwidth, and current accelerators favor parallel, high-arithmetic-intensity workloads; algorithmic and architectural co-design has produced major speed gains.Source: §7.1 · p. 28

7.2 Speeding up the generator

• Single-call speedups use architectural changes, compression, hardware-aware implementations, or parallelized autoregressive decoding.Multi-query and grouped-query attention reduce KV Cache size; quantization can speed memory-bound generation but compression may reduce quality. Flash Attention and Flash Decoding change hardware mapping, while speculative sampling drafts tokens and verifies them in parallel, speeding memory-bound decoding when rejection is limited without changing the output distribution. (Shazeer, 2019; Ainslie et al., 2023a; Dao et al., 2022; Dao, 2023; Dao et al., 2023; Leviathan et al., 2022; Chen et al., 2023a)Source: §7.2 · pp. 29–30

7.3 Speeding up meta-generation algorithms

• Meta-generation offers additional optimization opportunities because its repeated calls to the same model often follow predictable usage patterns.The survey distinguishes these optimizations from methods that accelerate a single autoregressive generation call.Source: §7.3 · p. 31

7.3.1 Leveraging shared prefixes.

• Reusing the prefilled state for a shared prefix avoids repeating input processing across candidates, reducing input-token work by a factor of N in Best-of-N.Shared KV Cache state can also ease GPU memory demands and increase throughput; state sharing can extend to branching input trees, though compression of reused states may lose quality. (Mu et al., 2023)Source: §7.3.1 · p. 31

7.3.2 Optimizing computational graphs

• Meta-generator programs can be accelerated through caching repeated or backtracked calls, rewriting computational graphs, and algorithm-specific early stopping or pruning.Examples include SGLang reordering graph nodes and voting methods stopping once a majority converges. (Aggarwal et al., 2023; Cheng & Vlachos, 2023)Source: §7.3.2 · p. 32

7.4 Libraries and tools for fast generation

• Fast-generation tools range from vLLM and TensorRT-LLM to SGLang for meta-generation, GPT-Fast for low-latency prototyping, and CPU-oriented libraries for users without powerful GPUs.CPU and offloading approaches face distinct systems challenges beyond the homogeneous accelerator setting discussed in the survey.Source: §7.4 · p. 32

Takeaway 1: iron out degeneracies in the learned distribution

• Generation algorithms can mitigate model-distribution degeneracies, including incoherent sampled sequences, repetitive or empty MAP outputs, and excess probability on implausible sequences.Future models may remove some imperfections, but subtle design choices such as softmax (Finlayson et al., 2024a) may sustain the need to identify and mitigate degeneracies.Source: §8 · pp. 32–33

Takeaway 2: align the generation distribution with a new objective

• Generation algorithms can shift the model’s learned distribution toward a desired one, for example by reweighting with another model or selecting rewarded samples.This control may remain useful when distributions do not align, including for black-box APIs where scoring or filtering is accessible; application-specific finetuning to a reward-induced distribution could reduce the need for algorithms such as rejection sampling.Source: §8 · p. 33

Takeaway 3: dynamic computation

• Inference-time search can spend more compute exploring hypotheses and improve the chance of correct outputs in reasoning tasks.Its usefulness may persist for challenging problems that benefit from backtracking or revision, though dynamic computation could instead be built into architectures or learning algorithms, or the search algorithm could be learned. Meta-generators themselves may also be optimized; test-time compute trade-offs need further study.Source: §8 · pp. 33–34

Takeaway 4: leveraging external information

• Generation algorithms can incorporate model predictions, prompts, tools, verifiers, or environmental inputs and outputs that the language model lacks or uses inefficiently.Some tasks may require cascading generations and interaction with an environment; discrete sequence generators may also serve as agents taking actions in stochastic environments, where planning and external information are inherent.Source: §8 · p. 34

Takeaway 5: speed up generation

• Generation algorithms can speed up sampling, while diverse meta-generation configurations create additional demands and opportunities for faster generation.The authors expect continued value in speeding generation as models, architectures, applications, and compute environments evolve, particularly for methods involving multiple models, external information, or cascaded generation.Source: §8 · p. 34

• The survey motivates generation algorithms and formalizes their goals.Source: §9 · p. 34
• It provides a unified treatment of token-level generation, meta-generation, and efficient generation.Source: §9 · p. 34
• The survey brings together research from decoding, LLM reasoning, and machine learning systems, and identifies directions for future work.Source: §9 · p. 34