121 lines
10 KiB
Markdown
121 lines
10 KiB
Markdown
# IOL-AI 2026 Solver — Implementation Seed
|
|
|
|
Seed context and build plan for implementing a solver for International Linguistics Olympiad (IOL) style problems. Read this fully before writing code. Design principle: the structure of language does the reasoning; the LLM proposes hypotheses that a deterministic engine executes and a symbolic verifier selects. Do not outsource rule application to the LLM.
|
|
|
|
## 1. The task
|
|
|
|
Solve self-contained linguistic-reasoning puzzles over unseen, mostly low-resource languages. Each puzzle gives a small amount of bilingual/parallel data plus hints, and asks the solver to translate, fill blanks, match forms to meanings, or convert numerals. No prior knowledge of the language is needed or expected; everything must be induced from the given data.
|
|
|
|
### Data (Linguini-style CSV)
|
|
Columns: `id`, `context`, `query`, `work_lang`, `task_lang`, `task_type`, `eval_type`.
|
|
- One row = one complete problem. `context` holds the parallel data + hints. `query` holds numbered items sharing that context.
|
|
- Read test set from `/tmp/data/test.csv`. Write `submission.csv` with a `pred` column: one **JSON list** of answers per row, one entry per numbered item, in order.
|
|
|
|
### Task types (route on `task_type`)
|
|
- `translation` (work->task and task->work): analysis one way, generation the other.
|
|
- `fill_blanks`: complete a paradigm cell.
|
|
- `match_letters`: match forms to meanings (assignment problem).
|
|
- `text_to_num` / `num_to_text`: recover and apply a numeral system.
|
|
- Others may appear (transliteration, glossing, error-correction, phonological rule application) — handle gracefully, fall back rather than crash.
|
|
|
|
### Scoring (design to this)
|
|
Final score = geometric mean `sqrt(EMw * chrFw)`, both **points-weighted** by official IOL point values.
|
|
- Geometric mean => neither factor can be near zero. **Never emit an empty or wildly-off answer**; always produce a plausible string (chrF floor).
|
|
- Need genuine exact hits (symbolic core) AND fuzzy overlap (fallback).
|
|
- Generation *into* the unknown language is the hardest direction; invest there.
|
|
|
|
### Submission and runtime constraints (hard)
|
|
- Submit a public Hugging Face repo containing `script.py` + model weights. Load models from `.` (repo root). **No internet in the eval sandbox** — vendor every dependency and weight.
|
|
- **30 minutes per run for the entire test set.** Throughput is the real budget. Symbolic-first; batch all LLM calls; spend sampling on hard/high-point items only.
|
|
- Greedy decoding for reproducibility. Up to 3 submissions/day; 2 count for the private leaderboard.
|
|
- Compute at inference: single **T4, 16 GB** (Turing: fp16 yes, bf16 no). Use 4-bit AWQ/GPTQ + LoRA via vLLM.
|
|
- Full repo is allowed: ship YAML configs, prompt libraries, DSL grammar files, multiple LoRA adapters, finetuned weights.
|
|
- Finetuning (SFT or RL) is allowed; train **offline** on other hardware and upload weights. Only inference is T4-bound.
|
|
|
|
## 2. Core insight (why this architecture)
|
|
|
|
1. LLMs (small ones especially) can *propose* linguistic rules but reliably fail to *apply* them consistently. => LLM proposes a grammar; a **deterministic interpreter applies it**.
|
|
2. The given attested pairs are a **free, exact verifier**. Leave-one-out fit on them (points-weighted EM + chrF = the competition metric) selects among candidate grammars. No LLM judge needed for correctness. This makes the domain verifiable, which is what makes test-time scaling and RL-with-verifiable-rewards work.
|
|
3. Explicit morpheme segmentation before anything else is a large, cheap win.
|
|
4. Analogical exemplars (from a multilingual model) help the LLM *propose* better grammars, never to deduce.
|
|
|
|
## 3. Architecture
|
|
|
|
```
|
|
Router/typology scan -> Preprocess (normalize, segment, align, paradigm table)
|
|
-> Symbolic-first solvers: numeral CSP | matching (Hungarian) | concatenative morphology
|
|
-> Program-synthesis subagent: LLM proposes grammar in DSL -> interpreter runs it
|
|
-> CEGIS refine <= R rounds (feed failing pairs back)
|
|
-> Verifier: leave-one-out EM+chrF on attested pairs + MDL penalty; self-consistency on ties
|
|
-> Select grammar (never empty; chrF-floor fallback = closest attested form / analogy)
|
|
-> Apply selected grammar deterministically to query items -> answers
|
|
-> (phase 5) Verbalizer LoRA: execution trace -> human explanation
|
|
```
|
|
|
|
Principles: segment first; symbolic-solved items cost ~0 LLM tokens; adaptive compute; guard against repetition loops (token cap + repetition penalty + loop detection).
|
|
|
|
### The DSL (small, executable, verifiable)
|
|
Primitives for a puzzle grammar. Programs are tiny so execution/verification is effectively free.
|
|
- `LEXICON`: morpheme -> gloss/feature
|
|
- `AFFIX(position, form, trigger)`
|
|
- `REWRITE(pattern -> repl / context)` (morphophonology: harmony, sandhi, elision)
|
|
- `ORDER(slot permutation)` (source constituent order -> target)
|
|
- `AGREE(feature copy)`
|
|
- `REDUP(template)`
|
|
- `NUMERAL(base, digitmap, combine_op)`
|
|
Interpreter must run **both directions** (analyze and generate). Generation uses the grammar + proportional analogy for unseen stems; round-trip verify generated forms.
|
|
|
|
### Verifier (single object, reused everywhere)
|
|
`score(grammar, held_out_pairs) -> points_weighted_EM, chrF`. Used as: test-time selector, CEGIS signal, and (later) RL reward. Add MDL penalty `L(grammar)+L(data|grammar)` to prefer the simplest adequate grammar.
|
|
|
|
## 4. Suggested repo layout
|
|
|
|
```
|
|
script.py # entrypoint: read /tmp/data/test.csv -> write submission.csv
|
|
solver/
|
|
router.py # task typing + typology scan + budget tier
|
|
preprocess.py # unicode NFC (keep tone/diacritics), tokenize, align, segment
|
|
align.py # minimal-pair set-difference aligner (pure python)
|
|
segment.py # MDL-guided segmentation conditioned on alignment
|
|
analogy.py # proportional analogy (a:b::c:d), analogical grids
|
|
numerals.py # base detection + CSP/algebraic solve
|
|
matching.py # scipy Hungarian over alignment-consistency scores
|
|
dsl/
|
|
grammar.py # DSL datatypes
|
|
interpreter.py # analyze() and generate(), both directions
|
|
synth.py # program-synthesis subagent + CEGIS loop
|
|
verifier.py # leave-one-out EM+chrF + MDL; selection + self-consistency
|
|
llm.py # vLLM wrapper, 4-bit base + LoRA adapter swap, batching, guards
|
|
fallback.py # chrF-floor: never return empty
|
|
budget.py # adaptive compute allocation under 30-min cap
|
|
prompts/ # YAML prompt library (proposer, analogical generator, critic)
|
|
weights/ # 4-bit base + LoRA adapters (proposer/deducer/verbalizer/critic)
|
|
eval/
|
|
scorer.py # reimplement official geomean scorer
|
|
dev_harness.py # run + score on public dev puzzles
|
|
data/dev/ # public IOL/Linguini/PuzzLing/modeLing/LINGOLY (validation ONLY)
|
|
```
|
|
|
|
## 5. Build order (do in this sequence; each has a gate)
|
|
|
|
0. **Harness first.** `eval/scorer.py` (points-weighted EM + chrF geomean) and `verifier.py` leave-one-out. Assemble `data/dev/` from public puzzles (respect CC-BY-SA / IOL copyright; validation only). Baselines: analogy-only floor, small-LLM few-shot. Gate: scorer matches hand-computed values.
|
|
1. **Cheap symbolic points.** `numerals.py`, `matching.py`, `align.py`, `segment.py`, `analogy.py`. Gate: numerals/matching beat LLM baseline; segmentation shows a positive downstream delta (replicate the known morpheme-boundary gain). If segmentation does not help, the aligner is mis-conditioned.
|
|
2. **Synthesis core.** DSL + interpreter + `synth.py` CEGIS with proposer LLM. Ablate: direct-LLM vs synthesis+verifier vs +segmentation vs +analogical exemplars; vary CEGIS rounds. Gate: synthesis+verifier clearly beats direct-LLM on translation/fill_blanks at fixed budget.
|
|
3. **Verifier-gated test-time scaling.** Best-of-N grammar sampling ranked by verifier; self-consistency; adaptive budget. Gate: monotone accuracy gain that still fits 30 min; pick operating N from the compute-accuracy curve.
|
|
4. **Finetuning (offline, highest ceiling).** Procedurally generate synthetic puzzles with gold grammar/segmentation/derivation. SFT the proposer/deducer for DSL emission + reliable rule application; then GRPO/RLVR with the verifier as reward. Validate on **real** public puzzles (guard the synthetic-real gap). Gate: finetuned small model >= best prompt-only config on real held-out puzzles at equal/lower cost.
|
|
5. **Explanation track (later).** Verbalizer LoRA: execution trace -> prose; narrow LLM critic checks faithfulness to the trace. The automated solver's trace is the explanation substrate.
|
|
|
|
## 6. Stack and risks
|
|
|
|
Models (T4, 4-bit + LoRA, vLLM): base = Qwen2.5-7B-Instruct; try a Coder variant for DSL emission; optional Aya-Expanse-8B as multilingual analogical generator. Role specialization via hot-swapped LoRA adapters over one base (stay in 16 GB).
|
|
|
|
Libraries (vendor all, offline): `unicodedata`/`regex`; pure-python aligner + MDL segmenter (avoid native `pynini`/`hfst`; implement rewrite-rule + analogy engine in python); `scipy` (Hungarian); hand-rolled CSP for numerals (spaces are tiny) or `z3-solver` if redistributable; `sacrebleu` (chrF); `vllm`; `peft`.
|
|
|
|
Risks: throughput vs 30 min (symbolic-first, batch, adaptive budget, cap N); small-model deduction leakage (always execute rules deterministically); DSL coverage of hard phenomena — tone, reduplication, circumfixes, harmony, ergativity, suppletion (grow primitives from failure analysis; keep an LLM fallback so nothing is empty); synthetic-real gap (validate on real puzzles only); repetition collapse (token caps + penalties); quantization hurting multilingual quality (compare AWQ/GPTQ/fp16 on dev before committing).
|
|
|
|
## 7. Non-negotiables
|
|
|
|
- Read `/tmp/data/test.csv`; write `submission.csv` with `pred` as a JSON list per row. Load all models/deps from repo root; assume no network.
|
|
- Never return empty for any item. Stay within 30 minutes for the whole set. Greedy decoding.
|
|
- LLM proposes; symbolic engine applies and verifies. Segment before reasoning. Keep tone/diacritics.
|