TL;DR
SALA (Semantic-Aware Logical Alignment) is a novel framework that improves in-context learning for complex reasoning tasks by selecting few-shot demonstrations based on their underlying problem-solving logic rather than surface text similarity. By dynamically discovering task-specific reasoning operations and using Dynamic Time Warping (DTW) to softly align operation sequences, SALA achieves state-of-the-art performance across multiple language models and reasoning benchmarks.
What Problem Does This Paper Address?
When prompting Large Language Models (LLMs) using In-Context Learning (ICL), performance heavily depends on the choice of few-shot examples (demonstrations). Traditional retrieval methods select examples based on surface-level semantic similarity (e.g., BM25 or raw embedding similarity). However, these methods are easily fooled by irrelevant topics or entities while completely missing the actual logical steps required to solve a problem.
Recent "logic-based" selection methods attempt to fix this by mapping problems to a fixed set of symbolic reasoning steps. Unfortunately, these methods rely on rigid exact-matching rules. They break down when different problems use slightly different phrasing, vary in their level of detail (decomposition granularity), or follow diverse but logically equivalent reasoning paths.
Methods
SALA addresses these limitations through a four-stage pipeline that combines explicit logical representation with soft semantic alignment:
- Adaptive Operation Construction: Rather than relying solely on a rigid, predefined set of operations (like the 13 base QDMR operations), SALA uses an LLM to automatically discover new, task-specific operations (e.g.,
ModuloorAlgebra) directly from the training data. It then applies a two-stage deduplication process—combining heuristic name normalization with LLM-based functional overlap checks—to keep the operation space clean and expressive. - Reasoning Sequence Parsing: Queries and candidate demonstrations are parsed into ordered sequences of these learned operations.
- Semantic Logical Alignment: Instead of exact symbolic matching, operation descriptions are converted into continuous semantic vectors using a pretrained text encoder (
bert-base-uncased). SALA then applies Dynamic Time Warping (DTW) to compute sequence-level similarity. DTW finds the optimal alignment between two sequences, elegantly handling variations in sequence length and granularity. - Demonstration Selection & Prompting: Examples are ranked by their DTW similarity score and arranged in an easy-to-hard curriculum based on sequence length before being formatted into the final prompt.
Datasets
The authors evaluated SALA on four diverse reasoning benchmarks:
- GSM8K: High-quality grade-school math word problems requiring multi-step reasoning.
- SVAMP: An arithmetic word problem dataset specifically designed to challenge surface-level text matching.
- CommonsenseQA (CMSQA): A multiple-choice commonsense reasoning benchmark.
- StrategyQA (StrQA): An open-domain question-answering benchmark requiring implicit, multi-step reasoning strategies.
Key Insights and Ideas
- Logic Trumps Surface Semantics: Matching examples based on how a problem is solved (the sequence of operations) is far more effective for complex reasoning than matching based on what the problem is about (the words used).
- Predefined Operations are Too Rigid: Fixed operation sets often inflate sequence lengths because they lack specialized terms. For instance, introducing a task-specific operation like
Algebracondenses long chains of basic arithmetic steps into a single, compact unit. This compaction prevents the retriever from getting confused by long, repetitive sequences. - The Power of Soft Alignment: Using DTW over continuous embeddings solves the brittleness of exact symbolic matching. It allows the system to recognize that two reasoning paths are logically similar even if they have minor structural variations or different granularities.
Key Results
- State-of-the-Art Performance: SALA consistently outperformed seven baselines—including standard embedding retrieval (TopK-BERT), diversity-aware methods (DPP-BERT), and state-of-the-art reasoning-aware selectors (PSL, LMS3)—across three different LLMs (Llama3-8B-Instruct, Qwen2.5-7B-Instruct, and DeepSeek-V4-Pro).
- Superior Average Accuracy: On the advanced DeepSeek-V4-Pro model, SALA achieved the highest average accuracy of 91.42% across all four benchmarks.
- Crucial Components: Ablation studies confirmed that removing either the task-specific operations or the DTW alignment led to a significant drop in performance (up to 2.9 points on Qwen2.5), proving that both components are vital to SALA's success.
Limitations and Future Work
- LLM Dependency: The framework relies on an LLM to induce task-specific operations and parse questions into sequences. Consequently, the quality of the operation space can vary depending on the induction model and prompting strategy used.
- Linear Sequence Assumption: SALA currently models problem-solving logic as a linear sequence of operations. While this works well for the tested benchmarks, more complex or multi-threaded tasks might benefit from richer, non-linear structures, such as hierarchical or graph-based reasoning representations. The authors plan to explore these structures in future work.
Summary updated