When using Large Language Models (LLMs) to translate natural language into structured outputs like SQL queries, code, or logical forms, we heavily rely on retrieval-augmented generation (RAG) to provide relevant few-shot examples. Traditional retrieval systems select these examples based on surface-level lexical or semantic textual similarity. For instance, if a user asks a question about "flight departures from Boston," a standard dense retriever will search the training set for other questions containing words like "flight," "departure," or "Boston."
However, this thematic matching introduces a fundamental mismatch in structured generation tasks. A retrieved example might share the same domain (flights) but possess a completely different grammatical or logical architecture (a simple SELECT statement versus a complex nested JOIN). Conversely, an example from an entirely different domain (such as school enrollments) might share the exact logical complexity and structural patterns required to solve the user's request.
To bridge this gap, researchers have developed structural similarity retrieval. This paradigm shifts the focus of example selection from what the query is talking about (domain vocabulary) to how the query is organized (logical and syntactic structure).
The Compositional Gap in Semantic Parsing
The necessity of structural retrieval stems from a core limitation in how language models generalize. As demonstrated by Linlu Qiu et al., simply scaling up the parameter count of an LLM does not inherently solve the "compositional gap"—the difficulty models face when they must combine known structural elements into novel configurations. When fine-tuned or prompted with standard lexically similar examples, models often fail to grasp the underlying execution logic required for complex, multi-step tasks.
Providing examples that match the target structure rather than the input text gives the model an explicit architectural blueprint. By prioritizing the structural skeleton of a query over keyword similarity, as argued by Tonghui Ren et al., the prompt ensures that the model observes the precise compositional patterns necessary to generate valid formal syntax.
Mechanisms for Isolating Structure
To retrieve examples based on structure, the system must first strip away the distracting domain-specific vocabulary and isolate the underlying logic. Researchers achieve this through several distinct representation mechanisms:
- Domain Masking and Skeletons: A direct way to expose structure is to replace specific entities, column names, and values with generic placeholders. The work of Dawei Gao et al. and Chunxi Guo et al. utilizes this strategy to isolate the underlying SQL "skeleton" or logical intent of a query. Similarly, Jinxin Liu et al. abstract formal logical forms into simplified templates, using a greedy search to find the closest structural matches in the training pool.
- Abstract Syntax Trees (ASTs): For code-related tasks, the hierarchy of the output can be explicitly evaluated. Zhili Shen et al. and Ali Al-Lawati et al. demonstrate that clustering and ranking examples using normalized Abstract Syntax Trees provides a significantly stronger signal for few-shot learning than surface text. The AST explicitly captures the nested loops, conditions, and functional relationships independent of variable names.
- Semantic Pattern Spaces: Rather than relying on text embeddings, early foundations by Yassine Benajiba et al. mapped natural language into a specialized "semantic pattern space." Here, training labels are generated by comparing structural components—such as aggregators, clause counts, and operators—to create an objective distance metric based entirely on logical requirements.
Why It Works: Enabling Abstract Copying
The reason structural similarity retrieval drastically improves model performance boils down to a core strength of in-context learning: abstract copying.
As explained by Jonathan Herzig et al., LLMs are highly proficient at recognizing structural patterns in a prompt, maintaining that abstract framework, and substituting new entities into the template. When a few-shot prompt contains demonstrations that share the exact functional logic and complexity of the target task, the model's cognitive burden shifts. It no longer needs to invent a complex program structure from scratch; it merely needs to adapt the retrieved structural blueprint to the new domain's vocabulary.
This mechanism proves effective across a wide array of structured workflows:
- Code Generation: Gabriel Poesia et al. show that aligning natural language descriptions with their underlying program structures ensures the model is prompted with logic patterns that closely match the required output, preventing execution errors.
- Decoupled Pipelines: By separating the generation process into distinct tracks, Zhenhe Wu et al. demonstrate that selecting examples based on query complexity and functional logic provides a more effective architectural blueprint than simple linguistic similarity.
- Grammatical Heuristics: Even in text generation tasks like question formulation, Lizi Liao et al. show that retrieving examples based on grammatical skeletons rather than keyword overlap provides the most effective structural patterns for the model to emulate.
Overcoming the Catch-22: Generate-and-Retrieve
An obvious paradox arises when implementing this strategy: How can we retrieve examples based on the structure of the target code before the model has actually generated it?
To resolve this Catch-22, modern frameworks adopt an iterative, two-stage workflow often referred to as Generate-and-Retrieve.
[User Query] ──> (Zero-Shot LLM) ──> [Rough Draft Output]
│
▼
[Final Output] <── (Few-Shot LLM) <── [Structurally Similar Exemplars]
First, the model processes the input query in a zero-shot manner to generate a preliminary "rough draft" of the target output. While this draft may contain minor semantic errors (such as incorrect table names or missing filters), its overall syntactic structure is usually highly accurate.
The framework then uses the structure of this draft as the retrieval key. Yury Zemlyanskiy et al. pioneered this approach by breaking down predicted logical forms into sets of structural components (intents and slots) to perform efficient frequency-based retrieval. Similarly, Linyong Nan et al. use the keywords and operators of a draft query to pull structurally analogous demonstrations from an annotated pool, proving that draft-based structural retrieval far outperforms input-based semantic similarity.
This paradigm is equally powerful for self-correction and debugging. When a generated program fails or hits an execution error, Prerna Agarwal et al. show that retrieving demonstrations based on the structural similarity of the failing code provides a much cleaner signal for resolving logical or syntactic bugs than re-evaluating the original natural language question. By observing how a similar structural pattern was correctly implemented or fixed in the past, the model can rapidly resolve its own multi-step reasoning failures.
Key Foundational Work
Synchromesh: Reliable Code Generation from Pre-trained Language Models (2022) — contributed 2 concept elements to this direction.
Evaluating the Impact of Model Scale for Compositional Generalization in Semantic Parsing (2022) — contributed 1 concept elements to this direction.
Learning To Retrieve Prompts for In-Context Learning (2022) — contributed 1 concept elements to this direction.