Source-linked AI summary
Beam Search, Self-Consistency, and the Limits of Inference-Time Scaling for Grammar-Constrained Text-to-SQL in Small Language Models
Ty Chermsirivatana, John MacCormick
TL;DR
This paper examines whether increased inference-time computation can offset smaller models when grammar constraints enforce valid text-to-SQL outputs. Using beam search and sample+vote with Qwen2.5-Instruct models on Spider, it finds that both improve accuracy, but beam search outperforms sample+vote at matched budgets and larger models typically remain better than more inference compute.
Problem
The paper investigates whether reducing model size while increasing inference-time computation remains an effective trade-off under strict grammar-constrained decoding.
Method
The study compares variable-width constrained beam search and constrained sample+vote across 0.5B–7B Qwen2.5-Instruct models on the 1,034-example Spider development set.
Results
Beam search outperforms sample+vote at matched budgets, while inference-time computation improves accuracy especially for smaller models but typically does not compensate for reduced model size.
Takeaways & Limitations
In this grammar-constrained text-to-SQL setting, increasing model size generally provides more benefit than increasing inference compute, and beam search is the stronger compute-allocation strategy.
Takeaways & Limitations
The experiments cover one model family, one benchmark, and a single decoding run per configuration, so broader conclusions require more diverse experiments.
Abstract
from arXiv · showhide
One common trade-off in the use of large language models involves reducing the size of the model while increasing the amount of computation at inference time, for example by using a wider beam search. In this paper, we examine the constrained case of this "model size vs. inference compute" trade-off, in which the model outputs are constrained by a strict grammar at inference time. Our results demonstrate that the constrained trade-off behaves differently from the unconstrained trade-off. We investigate the task of converting a prose query into an equivalent SQL query (text-to-SQL). Performance is evaluated on the Spider text-to-SQL benchmark, using the Qwen2.5-Instruct model family ranging in size from 0.5B to 7B parameters, all at 4-bit precision. We experiment with two approaches to varying inference compute: (i) beam search with a variable number of beams; and (ii) sample+vote, i.e., sampling several constrained outputs and then voting on their execution results, where the number of samples is varied. On the 1034-example development set, we find that: (a) both beam search and sample+vote improve accuracy, especially on smaller model sizes; (b) the "model size vs.\ inference compute" trade-off is not advantageous in this experiment, because moving to a larger model size typically results in higher accuracy than increasing inference compute on the same model size; (c) beam search outperforms sample+vote at a matched inference budget. This latter result is of particular interest since it contrasts with the findings of the unconstrained trade-off.
1 Introduction
The paper studies whether inference-time computation can offset smaller models when grammar constraints enforce valid structured outputs. On grammar-constrained text-to-SQL, it compares beam search and sample+vote across model sizes and finds that larger models generally remain preferable.
- Grammar-constrained decoding guarantees syntactic validity and can prevent references to nonexistent database objects.It masks tokens inconsistent with a formal grammar at each generation step.
- Inference-time scaling increases generation computation through methods such as wider beam search or aggregating sampled candidates.Self-consistency, also called sample+vote, returns the most frequent final answer among sampled solutions.
- The paper evaluates whether extra decoding computation can help a smaller constrained model approach the accuracy of a larger one.This trade-off may matter when larger models exceed local hardware memory or require more expensive accelerators.
- Beam search outperforms sample+vote at matched budgets, while additional inference computation generally does not substitute for parameters.At eight beams, it closes 50%–76% of the gap to the next larger model, and only the 1.5B-to-3B step is fully bridged.
2 Related Work
Related work covers grammar-constrained decoding, execution-based sample+vote for text-to-SQL, and methods for addressing beam search length bias.
- Grammar-constrained decoding uses a context-free grammar and incremental parser to mask invalid continuations.For text-to-SQL, incremental parsing rejects invalid partial queries during beam search.
- Self-consistency samples several outputs and selects the most consistent answer, while constrained text-to-SQL can define consistency by identical execution results.Structurally different queries count as consistent when they return the same result.
- Prior work addresses beam search length bias using length normalization, length penalties, and tuned per-token rewards.
3 Problem Formulation
The problem formulation defines grammar-constrained generation and compares beam search with execution-voted sampling under a matched computational budget. Correctness is measured by execution accuracy on the target database.
- Grammar-constrained decoding admits only tokens that keep the generated prefix extendable to a string in the grammar’s valid language.The end-of-sequence token is allowed only at an accepting state, and schema-aware grammars restrict identifiers to the target database.
- Beam search maintains B partial hypotheses, retains the highest-scoring continuations, and returns the best finished candidate under a length penalty.Decoding halts when B finished candidates have been collected.
- Sample+vote draws B constrained samples, executes them against D, discards failures, and returns a query producing the modal result.Both methods are compared at matched budgets B ∈ {1, 2, 4, 8}.
- At budget B = 1, beam search is greedy decoding and sampling is a single draw.
- A prediction is correct when it and the gold query return the same result set, with ordering relevant only when the gold query contains ORDER BY.Execution accuracy is the fraction of correct predictions.
4 Experimental Setup
The evaluation uses quantized Qwen2.5-Instruct models on the full Spider development set, with controlled decoding settings and uncertainty reporting. Sample+vote is evaluated in a single random-seed run, unlike deterministic beam search.
- The study evaluates 0.5B, 1.5B, 3B, and 7B Qwen2.5-Instruct models at 4-bit precision on all 1,034 Spider development examples.Sample+vote uses τ = 0.7 and top-p = 0.9; beam search uses a length penalty of −2.0.
- Generation is capped at 160 new tokens for every configuration.
- Each configuration is evaluated in a single decoding run; beam search is deterministic, while sample+vote depends on the random seed.Variability across repeated sampling runs is left for future work.
- Reported error bars are 95% Wilson score intervals over the 1,034 test examples rather than variability across repeated sampling runs.The configurations are paired because they use the same examples, motivating McNemar’s exact test for comparisons.
5 Results
Inference-time compute improves grammar-constrained text-to-SQL accuracy, but its benefits shrink with model size and generally do not replace additional parameters. Beam search is stronger than sample+vote at matched budgets, while grammar incompleteness can itself reduce accuracy.
- Grammar effects: Grammar constraints can reduce accuracy because incomplete grammar coverage rejects valid SQL constructs and forces unlikely continuations.Reported uncovered cases include IN value lists, IS NOT NULL, outer joins, and free-form or abbreviated aliases.
- Inference-time scaling: Wider-beam benefits decrease with model size and saturate by beam width 4.Figure 1 reports execution accuracy over 1,034 examples with 95% Wilson score intervals.
- Inference-time scaling: Inference-time compute improves execution accuracy most for smaller models, with beam-search gains saturating around B = 4 to 8.The 0.5B- and 1.5B-parameter models receive larger boosts than the 3B and 7B models.
- Beam search versus sample+vote: Beam search is significantly more accurate than sample+vote in 11 of 16 matched-budget cells and significantly behind in none.The remaining five cells are statistical ties under exact McNemar tests.
- Beam search versus sample+vote: Sample+vote improves over greedy decoding at every model size, but beam search is superior at matched inference budgets.This contrasts with prior unconstrained reasoning-task results in which sampling beat beam search.
- Model size versus inference compute: In two of three tested downgrades, an 8× inference-compute increase fails to compensate for fewer parameters.A 2× increase does compensate for the downgrade from 3B to 1.5B in the remaining case.
6 Discussion
The discussion argues that beam search’s advantage over sample+vote is not explained by over-generation, while proposing constrained diversity and biased errors as plausible mechanisms. It also warns that subset evaluations can reverse the method ranking.
- Mechanisms: Beam search over-generates no more than sample+vote above width 1, so over-generation does not explain its superior performance.With a −2.0 length penalty, beam truncation decreases with width, while sample+vote truncates at every model size.
- Mechanisms: A hard grammar may remove the surface diversity that self-consistency exploits because every candidate is a valid query over the same schema.The paper presents this as a plausible hypothesis rather than a directly verified mechanism.
- Mechanisms: Weak constrained models may generate samples that agree confidently on the same wrong result, causing sample+vote to concentrate errors.The paper notes that directly testing this would require measures such as sample diversity and per-example vote entropy.
- Evaluation sensitivity: Subset evaluations generally favored sample+vote, but this effect disappeared on the full n = 1034 development set.The authors therefore caution that small text-to-SQL datasets could produce misleading method comparisons.
7 Limitations
The study’s conclusions are limited to one model family, one benchmark, and one decoding run per configuration, preventing broad generalization.
- Scope: The experiments cover only Qwen2.5-Instruct, Spider, and a single decoding run per configuration.The authors describe broader conclusions about constrained LLMs as plausible conjectures requiring more diverse experiments.
8 Conclusion
In grammar-constrained text-to-SQL, beam search outperformed sample+vote, and additional inference-time compute improved accuracy without typically compensating for smaller model size.
- Conclusion: Beam search was superior to sample+vote in the grammar-constrained text-to-SQL setting, contrasting with prior unconstrained findings.The comparison used Qwen2.5-Instruct models from 0.5B to 7B parameters on Spider.
- Conclusion: Inference-time compute significantly improved accuracy, especially for smaller models.The paper reports this pattern for both beam search and sample+vote.
- Conclusion: Inference-time compute typically did not compensate for reduced model size.The authors identify testing this result across other models, constraints, benchmarks, and repeated sampling runs as the main future direction.