📄 other

Retrieval-Assisted Instantiation of Natural-Language Optimization Problems

This paper presents a transparent, retrieval-assisted framework that grounds natural-language numeric evidence into structured optimization schemas, demonstrating that while schema retrieval is highly effective, the primary bottleneck for automating optimization problem instantiation lies in the downstream task of accurately matching extracted numbers to their corresponding slots.

Original authors: Soroush Vahidi

Published 2026-07-27

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Soroush Vahidi

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a complex machine, like a robot or a video game level, but you only have a messy, handwritten note describing what you want it to do. You can't just hand that note to a robot and expect it to build the perfect thing; the robot needs a specific blueprint, a set of rules, and exact numbers to get started. This is the world of optimization, a branch of math and engineering where we try to find the "best" way to do something, whether it's delivering packages in the shortest time or mixing ingredients for the cheapest cost.

The tricky part is that humans speak in stories and paragraphs, while math speaks in strict equations and variables. Bridging this gap is like trying to translate a poem into a spreadsheet. For a long time, computers have struggled to read a human's messy description and automatically turn it into a perfect, working math model. They often get lost in the details or guess the wrong blueprint entirely. This paper dives into a specific, middle-ground step of that translation process. Instead of trying to build the whole robot at once, it asks: "Can we first figure out which blueprint the human is talking about, and then grab the specific numbers they mentioned to fill in the blanks?" It's a test of whether a computer can act like a helpful librarian who finds the right instruction manual and highlights the right numbers, even if it can't yet assemble the final machine on its own.

The Search for the Right Blueprint

Think of a massive library filled with thousands of different instruction manuals for building things. Some manuals are for building bridges, some for baking cakes, and some for organizing a school bus schedule. Each manual is a "schema"—a pre-made template with empty slots waiting for numbers like "how many buses," "how much fuel," or "how many students."

The problem is that when a person says, "I need to get 50 students to school using the fewest buses possible," a computer doesn't automatically know if they are talking about a "bus scheduling" manual or a "delivery route" manual. If the computer picks the wrong manual, it will try to fill in the blanks with the wrong kind of numbers, leading to a mess.

This paper tests a system that acts like a super-fast librarian. Its job is twofold:

Find the Manual: Look at the messy sentence and pick the single best matching blueprint from the library.
Fill the Blanks: Take the numbers mentioned in the sentence (like "50 students") and slot them into the correct empty spots in that specific blueprint.

The researchers built a system that doesn't use fancy, brain-like AI that guesses and learns. Instead, it uses strict, transparent rules. It's like a robot that follows a checklist: "If the word 'cost' appears, look for a dollar amount. If the word 'limit' appears, look for a maximum number." The goal was to see if this simple, rule-based robot could do a good job without needing to be a genius.

The Big Surprise: Finding the Manual is Easy, Filling the Blanks is Hard

The team tested their robot librarian on a collection of 331 real-world math problems written in plain English. They wanted to see how well the robot could pick the right blueprint and fill in the numbers.

Here is the most interesting part of their discovery: The robot was actually really good at finding the right manual.

When the robot had to choose the correct blueprint from a library of 335 options, it got it right about 91% of the time (specifically, 0.9094 accuracy) using a standard text-matching method called TF-IDF. Even when the text was messy or shortened, it still did a great job. This suggests that computers are already quite good at understanding the general shape of a problem just by looking at the words.

However, the real trouble started when the robot tried to fill in the blanks.

Even when the robot picked the perfect blueprint (which the researchers tested by forcing it to use the correct one), it still struggled to decide which number went into which slot. The researchers found that the "InstantiationReady" score—a measure of how many problems were fully ready to be solved—only jumped from 0.5287 (about 53%) to 0.5680 (about 57%) when they gave the robot the perfect blueprint to start with.

This tiny jump tells a huge story. It means the main problem isn't finding the right instruction manual; the problem is understanding the meaning of the numbers once the manual is found. Is "50" a total count, a limit, a cost, or a percentage? The robot, following its strict rules, often got confused. It's like having the right recipe for a cake but not knowing if "2" means two eggs, two cups of sugar, or two minutes of baking time.

Trying to Make it Smarter (and Failing)

The researchers wondered if they could fix this by making the robot "smarter." They tried adding more complex rules, like checking if numbers were related to each other or looking for hidden clues in the sentence structure. They tested three new, more complicated families of rules:

Global Compatibility: Checking if all the numbers fit together like a puzzle.
Relation-Aware Linking: Looking at how words connect to each other.
Ambiguity-Aware Grounding: Being careful when a sentence has multiple meanings.

The result? None of these fancy upgrades worked better than the simple robot. In fact, the simple "typed-greedy" robot (which just matched numbers to slots based on basic types like "money" or "count") was still the champion, scoring 0.5287. The fancy new methods actually scored lower, with some dropping as low as 0.4230.

This suggests that the problem isn't that the robot needs more complex search strategies. The problem is that the meaning of numbers in natural language is just really, really tricky to pin down with simple rules. The robot needs to understand the context much better, not just the surface-level words.

A Glimmer of Hope: Real-World Testing

To see if this robot was actually useful, the researchers tried to use its output to run real math problems on a computer solver. They couldn't test every single problem, so they picked a few special groups:

60 problems: They checked if the robot's output looked like a valid math problem. It worked about 75% of the time.
269 problems: They tried to run the code, but hit a technical wall (a missing software tool), so they couldn't get results here.
20 problems: They used a different, simpler tool to actually solve the problems. Here, the simple robot did surprisingly well, successfully solving 80% of the problems it attempted.

Even with the perfect blueprint (the "Oracle" version), the robot only solved 75% of these 20 problems. This confirms the main finding again: even if you give the robot the right instructions, getting the numbers right is the hard part.

The Takeaway

This paper doesn't claim to have solved the mystery of turning human stories into perfect math models. Instead, it offers a very clear, honest map of where we stand.

It suggests that we don't need to worry as much about teaching computers to find the right "blueprint" from a library; they are already pretty good at that. The real challenge, the "bottleneck," is teaching computers to understand what the numbers actually mean in the context of that blueprint.

The authors conclude that while we can't yet build a fully automatic "story-to-solution" machine, this retrieval-assisted system is a valuable tool. It can act as a helpful assistant that narrows down the possibilities and grabs the right numbers, leaving the human expert to double-check the tricky parts. It's not a replacement for the engineer, but a transparent, reliable helper that makes the job of building the machine a little less lonely and a lot more organized.

Technical Summary: Retrieval-Assisted Instantiation of Natural-Language Optimization Problems

Problem Formulation
The paper addresses the challenge of translating natural-language descriptions of engineering and operations research problems into formal optimization models. Rather than attempting full end-to-end generation of solver-ready code or complete mathematical programs—a task that remains difficult to automate reliably—the study focuses on a narrower, intermediate task: retrieval-assisted optimization problem instantiation.

The core problem is defined as a two-stage process:

Schema Retrieval: Given a natural-language query, the system must identify the most compatible optimization template (schema) from a fixed catalog of 335 candidate schema documents.
Scalar Parameter Instantiation: Conditioned on the retrieved schema, the system must extract numeric evidence from the text and deterministically assign these values to the scalar parameter slots defined by the schema.

The scope is deliberately restricted to scalar numeric parameters (integers, floats, percentages, currency) within a fixed schema catalog. The pipeline is fully deterministic, utilizing no large language models (LLMs), learned retrievers, or learned extractors. The evaluation framework is designed such that downstream parameter eligibility depends on the predicted schema, not the gold schema, ensuring that retrieval errors propagate structurally to downstream performance metrics.

Methodology
The proposed framework operates as a transparent, deterministic pipeline:

Schema Identification (Retrieval): The system ranks a fixed catalog of schema documents against the input query. Three deterministic lexical retrieval baselines are evaluated:
- BM25: Probabilistic lexical weighting.
- TF–IDF: Weighted bag-of-words cosine similarity (identified as the primary backbone).
- Latent Semantic Analysis (LSA): Latent projection of TF–IDF features.
  The system selects the top-ranked schema ( $\hat{s}$ ) to serve as the structural anchor for the next stage.
Deterministic Parameter Instantiation:
1. Extraction: Numeric mentions are extracted from the query using rule-based pattern matching (recognizing integers, decimals, percentages, currency, etc.).
2. Typing: Mentions are assigned coarse types (percent, integer, currency, float) based on surface cues.
3. Slot Eligibility: The predicted schema $\hat{s}$ determines the set of eligible scalar parameter slots.
4. Assignment: A deterministic, no-reuse assignment rule maps extracted mentions to slots. The primary method is typed greedy matching, which prioritizes type agreement between the slot and the mention.
5. Refinement: The framework includes a lexicon-based optimization-role compatibility layer. This refines the basic type-matching signal by scoring slot–mention pairs based on domain-specific role cues (e.g., "capacity," "cost," "cardinality") found in the slot name and local context.
Evaluation Metrics:
- Schema R@1: The fraction of queries where the top-ranked schema matches the gold schema.
- Coverage: The fraction of eligible gold scalar slots that receive an assignment.
- TypeMatch: The fraction of assigned slots where the predicted numeric type matches the expected type.
- InstantiationReady: A diagnostic threshold metric (requiring both Coverage $\ge$ 0.8 and TypeMatch $\ge$ 0.8) measuring query-level usability.
- Exact20 on Hits: A conditional value-accuracy metric (within 20% relative error) computed only on schema-hit cases with comparable numeric values.

Key Contributions

Problem Decomposition: The paper proposes a framework that explicitly separates schema retrieval from scalar parameter grounding, using a retrieval-dependent evaluation design where eligible slots are derived from the predicted schema.
Transparent Methodology: It introduces a fully deterministic pipeline that maps numeric text to typed schema parameters without LLMs, making every intermediate decision (schema selection, slot eligibility, numeric extraction, assignment) inspectable and reproducible.
Empirical Diagnosis: Through extensive ablation studies, oracle controls, and comparisons with richer deterministic grounding families (global-compatibility, relation-aware, ambiguity-aware), the paper identifies the primary bottleneck in the pipeline.
Downstream Validation: It provides restricted structural and solver-backed validation (using SciPy HiGHS) on specific subsets to assess the practical utility of the recovered structures, distinguishing between benchmark-scale reproducibility and restricted executable success.

Results

Schema Retrieval: Retrieval performance is strong within the fixed-catalog setting. TF–IDF achieves the best average top-1 accuracy (Schema R@1 = 0.9094 on original queries), significantly outperforming random chance (~0.003) and demonstrating robustness to lexical degradation (noisy and short queries).
Downstream Instantiation: The strongest non-oracle method (TF–IDF typed greedy) achieves an InstantiationReady score of 0.5287.
Oracle Analysis: An oracle control (using the gold schema) improves InstantiationReady only to 0.5680. This modest gain (approx. 4 percentage points) indicates that even with perfect schema retrieval, the system struggles with number-to-slot grounding (assigning the correct extracted number to the correct semantic role).
Ablation Studies:
- Numeric-Type Compatibility: Correcting how float-valued slots are matched to numeric mentions yields massive improvements in TypeMatch and InstantiationReady, confirming that type-handling errors were a major source of failure.
- Richer Grounding Families: Three additional deterministic grounding families (Global Compatibility, Relation-Aware, Ambiguity-Aware) failed to surpass the simple typed-greedy baseline, suggesting that the bottleneck is not a lack of search complexity but a fundamental semantic ambiguity in quantity-to-role mapping.
Solver Validation: On a restricted 20-instance subset compatible with the SciPy HiGHS shim, the TF–IDF pipeline achieved 0.80 solver-success and feasible rates, slightly outperforming the Oracle (0.75), reinforcing that downstream grounding, not schema selection, is the binding constraint.

Significance and Claims
The paper modestly positions its contribution not as a complete natural-language-to-optimization compiler or a replacement for human modelers, but as a transparent intermediate layer for intelligent decision support.

Primary Finding: In the context of the NLP4LP benchmark, schema retrieval is not the dominant bottleneck; it is already strong. The primary remaining challenge is semantic quantity-to-role grounding—determining which extracted number corresponds to which parameter role (e.g., distinguishing a total cost from a unit cost, or a lower bound from an upper bound) once the schema is known.
Practical Value: The system demonstrates that a deterministic, retrieval-assisted pipeline can recover a substantial fraction of usable scalar structure (approx. 53% of queries meet the readiness threshold) without opaque LLMs. This provides a measurable, inspectable step toward formalizing optimization problems, allowing human experts to verify, correct, or extend the recovered parameters.
Limitations: The authors acknowledge that the results are specific to the NLP4LP benchmark and a fixed schema catalog. The system does not handle structured parameters (vectors, lists) and relies on heuristic, rule-based type inference. The study does not claim general solver-readiness across all optimization problems but offers evidence of utility on compatible cases.

In summary, the paper argues that while full automation remains difficult, a transparent, deterministic approach to schema retrieval and scalar grounding offers a viable, interpretable, and practically useful component for engineering decision support systems.