File size: 16,159 Bytes
1a3c3b3
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
"""BRAG - Bayesian RAG.

Closed-form Bayesian orchestration for retrieval-augmented QA. The orchestrator itself makes no
LLM calls: every decision is a few arithmetic operations on conjugate (Beta) posteriors.

Actions (each is an LLM call made by the *executor*, never by the policy):
  R1 : read top-k retrieved passages -> answer or NONE, plus a follow-up search query
  R2 : retrieve with the follow-up query, read old + new passages -> answer or NONE   (needs R1)
  CB : m parallel closed-book samples -> ONE vote (their mode), reliability by agreement level

Relaxations
  R1' self-samples of one LLM are one source (vote = mode, reliability kappa_g by agreement g)
  R2' concentrated distractors: a wrong vote lands on a given rival w.p. eta (K_eff = 1/eta)
  R3' reliability hyperpriors are population-level, calibrated offline on labelled data, frozen
  R4' separate reliabilities per action type
  R5' control by information rate: a* = argmax_a D_a / c_a,  stop when  P_err * D_a* / c_a* <= lambda
Posterior (per-query reliabilities integrated out in closed form):
  log w_i = sum_t [lnB(a_t+n_ti, b_t+N_t-n_ti) - lnB(a_t, b_t+N_t)] - n_i ln eta ;  log w_residual = -ln eta
"""
from __future__ import annotations
import json, math, re, string, threading, time
from collections import Counter
from concurrent.futures import ThreadPoolExecutor
from dataclasses import dataclass, field
from typing import Callable

import numpy as np
from scipy.special import betaln
from rank_bm25 import BM25Okapi

# ----------------------------------------------------------------- text utilities
_PUNCT = set(string.punctuation)
_STOP = set('a an the of in on at to for by with from and or is was were are be been who what which when '
            'where whose how did does do that this as its it his her their'.split())

def norm(s: str) -> str:
    s = (s or '').lower()
    s = ''.join(ch for ch in s if ch not in _PUNCT)
    s = re.sub(r'\b(a|an|the)\b', ' ', s)
    return ' '.join(s.split())

def is_none(a) -> bool:
    return a is None or norm(str(a)) in ('none', '', 'unknown', 'not stated', 'not mentioned')

def tokenize(s: str) -> list[str]:
    return [w for w in re.findall(r'\w+', s.lower()) if w not in _STOP]

def est_tokens(s: str) -> int:
    return max(1, len(s) // 4)

class Clusters:
    """Answer strings -> clusters (equal after normalisation, or token containment)."""
    def __init__(self):
        self.reps: list[str] = []
    def id(self, a: str) -> int:
        n = norm(a); nt = set(n.split())
        for i, r in enumerate(self.reps):
            rt = set(r.split())
            if n == r or (nt and rt and (nt <= rt or rt <= nt)):
                return i
        self.reps.append(n)
        return len(self.reps) - 1

# ----------------------------------------------------------------- retrieval
class Corpus:
    def __init__(self, passages: list[str]):
        if not passages:
            raise ValueError('corpus is empty')
        self.passages = passages
        self.bm25 = BM25Okapi([tokenize(p) or ['_'] for p in passages])

    @classmethod
    def from_json(cls, path: str) -> 'Corpus':
        rows = json.load(open(path))
        return cls([f"{r['title']}: {r['text']}" for r in rows])

    def search(self, query: str, k: int, exclude: set[int] = frozenset()) -> list[int]:
        sc = self.bm25.get_scores(tokenize(query) or ['_'])
        order = np.argsort(-sc)
        return [int(j) for j in order[:k + len(exclude)] if int(j) not in exclude][:k]

# ----------------------------------------------------------------- LLM executor
LLM = Callable[[list[dict], float, int], tuple[str, int, int]]   # messages, temperature, max_tokens

SYS = 'You are a precise question-answering component. Follow the output format exactly.'

def p_cb(q):
    return [{'role': 'system', 'content': SYS},
            {'role': 'user', 'content': f'Answer from your own knowledge. Give only a short answer (1-6 words), '
                                         f'always a best guess.\nQuestion: {q}\nAnswer:'}]

def _ctx(ps):
    return '\n'.join(f'[{i + 1}] {p}' for i, p in enumerate(ps))

def p_r1(q, ps):
    return [{'role': 'system', 'content': SYS},
            {'role': 'user', 'content':
             'Use ONLY the passages. Return JSON {"answer": "...", "followup": "..."} where answer is a short '
             'answer (1-6 words) if the passages TOGETHER answer the question, else "NONE"; followup is the single '
             'most useful next search query for the missing information (name the bridge entity if known). '
             f'Always give a followup.\n\nPassages:\n{_ctx(ps)}\n\nQuestion: {q}\nJSON:'}]

def p_r2(q, ps):
    return [{'role': 'system', 'content': SYS},
            {'role': 'user', 'content':
             'Use ONLY the passages; combine facts across passages for multi-hop questions. Give only a short '
             'answer (1-6 words), or NONE if the passages do not contain the answer.'
             f'\n\nPassages:\n{_ctx(ps)}\n\nQuestion: {q}\nAnswer:'}]

def clean_answer(t: str) -> str:
    t = (t or '').strip().strip('"').strip()
    t = re.sub(r'^(final\s+)?answer\s*:\s*', '', t, flags=re.I)
    return t.split('\n')[0].strip().strip('."')

def parse_r1(t: str) -> tuple[str, str]:
    m = re.search(r'\{.*\}', t or '', flags=re.S)
    if m:
        try:
            d = json.loads(m.group(0))
            return clean_answer(str(d.get('answer', 'NONE'))), str(d.get('followup', '')).strip()
        except json.JSONDecodeError:
            pass
    a = re.search(r'"?answer"?\s*[:=]\s*"([^"]*)"', t or '', flags=re.I)
    f = re.search(r'"?followup"?\s*[:=]\s*"([^"]*)"', t or '', flags=re.I)
    return (clean_answer(a.group(1)) if a else 'NONE'), (f.group(1).strip() if f else '')

def hf_llm(model: str, token: str | None, provider: str = 'auto', timeout: float = 60.0) -> LLM:
    """model: a Hugging Face model id (served by HF Inference Providers) or the URL of an
    OpenAI-compatible endpoint (e.g. a dedicated HF Inference Endpoint, TGI or vLLM server)."""
    from huggingface_hub import InferenceClient
    if model.startswith(('http://', 'https://')):
        client = InferenceClient(base_url=model, api_key=token, timeout=timeout)
    else:
        client = InferenceClient(model=model, token=token, provider=provider, timeout=timeout)
    def call(messages, temperature, max_tokens):
        r = client.chat_completion(messages, max_tokens=max_tokens, temperature=max(temperature, 0.01))
        text = r.choices[0].message.content or ''
        u = getattr(r, 'usage', None)
        tin = getattr(u, 'prompt_tokens', None) or sum(est_tokens(m['content']) for m in messages)
        tout = getattr(u, 'completion_tokens', None) or est_tokens(text)
        return text, int(tin), int(tout)
    return call

# ----------------------------------------------------------------- calibration
DEFAULT_CAL = {  # overwritten by data/calibration.json when present
    'rel': {'R1': [29, 6], 'R2': [54, 11]}, 'ans': {'R1': [34, 58], 'R2': [64, 28]},
    'kap': {'1': [2, 30], '2': [15, 24], '3': [14, 11]}, 'pg': {'1': 0.333, '2': 0.409, '3': 0.258},
    'eta': 0.591}

def _kl(rho, eta, q=1.0):
    rho = min(max(rho, 1e-6), 1 - 1e-6)
    return q * (rho - (1 - rho) * eta) * math.log(rho / ((1 - rho) * eta))

def gold_match(pred, gold: list[str]) -> int:
    if is_none(pred):
        return 0
    p = norm(pred)
    return int(any(norm(g) and (norm(g) in p or (len(p) > 3 and p in norm(g))) for g in gold))

# ----------------------------------------------------------------- the orchestrator
@dataclass
class Result:
    answer: str | None
    trace: list = field(default_factory=list)
    llm_calls: int = 0
    tokens_in: int = 0
    tokens_out: int = 0
    rounds: int = 0
    llm_seconds: float = 0.0
    policy_microseconds: float = 0.0
    stopped_because: str = ''
    def to_dict(self):
        return dict(answer=self.answer, stopped_because=self.stopped_because, llm_calls=self.llm_calls,
                    tokens_in=self.tokens_in, tokens_out=self.tokens_out, rounds=self.rounds,
                    llm_wall_seconds=round(self.llm_seconds, 3),
                    policy_microseconds_total=round(self.policy_microseconds, 1), trace=self.trace)

class BRAG:
    def __init__(self, llm: LLM, calibration: dict | None = None, lam: float = 0.05,
                 k: int = 5, cb_samples: int = 3, cb_temperature: float = 0.7):
        c = json.loads(json.dumps(calibration or DEFAULT_CAL))
        c['kap'] = {int(g): v for g, v in c['kap'].items()}; c['pg'] = {int(g): v for g, v in c['pg'].items()}
        self.P, self.llm, self.lam, self.k = c, llm, lam, k
        self.m, self.temp = cb_samples, cb_temperature

    # closed-form posterior over observed answer clusters + residual
    def posterior(self, votes):
        eta = self.P['eta']; cl = sorted({i for _, i in votes}); lw = {i: 0.0 for i in cl}
        by = {}
        for t, i in votes:
            by.setdefault(t, Counter())[i] += 1
        for t, cnt in by.items():
            a, b = self.P['kap'][t] if isinstance(t, int) else self.P['rel'][t]; N = sum(cnt.values())
            for i in cl:
                n = cnt.get(i, 0)
                lw[i] += betaln(a + n, b + N - n) - betaln(a, b + N) - n * math.log(eta)
        v = np.array([lw[i] for i in cl] + [-math.log(eta)]); v -= v.max(); p = np.exp(v); p /= p.sum()
        return cl, p

    def rates(self, done):
        eta = self.P['eta']; out = {}
        for t in ('R1', 'R2'):
            if t in done or (t == 'R2' and 'R1' not in done):
                continue
            a, b = self.P['ans'][t]; ra, rb = self.P['rel'][t]
            out[t] = _kl(ra / (ra + rb), eta, a / (a + b)) / 1.0
        if 'CB' not in done:
            d = sum(self.P['pg'][g] * _kl(self.P['kap'][g][0] / sum(self.P['kap'][g]), eta) for g in (1, 2, 3))
            out['CB'] = d / self.m
        return out

    _lock = threading.Lock()

    def _call(self, res, messages, temperature, max_tokens):
        t0 = time.perf_counter(); text, ti, to = self.llm(messages, temperature, max_tokens)
        with self._lock:
            res.llm_calls += 1
            res.tokens_in += ti; res.tokens_out += to
        return text

    def run(self, question: str, corpus: Corpus) -> Result:
        res = Result(answer=None); C = Clusters(); votes = []; raw = {}; done = set(); st = {}
        while True:
            t0 = time.perf_counter()
            cl, p = self.posterior(votes)
            pbest = float(p[:-1].max()) if cl else 0.0; perr = 1 - pbest
            rates = self.rates(done); act = None; why = ''
            if not rates:
                why = 'no actions left'
            else:
                a_star = max(rates, key=rates.get)
                if perr * rates[a_star] > self.lam:
                    act = a_star
                else:
                    why = f'P_err*D/c = {perr * rates[a_star]:.4f} <= lambda = {self.lam}'
            dt = 1e6 * (time.perf_counter() - t0); res.policy_microseconds += dt
            step = dict(posterior={(C.reps[i] if i < len(C.reps) else str(i)): round(float(pp), 4)
                                   for i, pp in zip(cl, p[:-1])},
                        residual=round(float(p[-1]), 4), p_error=round(perr, 4),
                        info_rate_per_call={k_: round(v, 4) for k_, v in rates.items()},
                        action=act or 'STOP', policy_us=round(dt, 1))
            if act is None:
                res.stopped_because = why; res.trace.append(step); break
            done.add(act); res.rounds += 1; tw = time.perf_counter()
            if act == 'CB':
                with ThreadPoolExecutor(self.m) as ex:
                    outs = list(ex.map(lambda _: self._call(res, p_cb(question), self.temp, 24), range(self.m)))
                samples = [clean_answer(o) for o in outs]; good = [s for s in samples if not is_none(s)]
                step['observation'] = {'samples': samples}
                if good:
                    ids = [C.id(s) for s in good]; mo, g = Counter(ids).most_common(1)[0]
                    votes.append((g, mo)); raw.setdefault(mo, good[ids.index(mo)])
                    step['observation']['vote'] = good[ids.index(mo)]; step['observation']['agreement'] = g
            elif act == 'R1':
                idx = corpus.search(question, self.k); st['idx1'] = idx
                ps = [corpus.passages[j][:600] for j in idx]
                ans, fu = parse_r1(self._call(res, p_r1(question, ps), 0.0, 96)); st['followup'] = fu or question
                step['observation'] = {'answer': ans, 'followup': fu, 'passages': [x[:80] for x in ps]}
                if not is_none(ans):
                    cid = C.id(ans); votes.append(('R1', cid)); raw.setdefault(cid, ans)
            else:  # R2
                idx2 = corpus.search(st['followup'], self.k, exclude=set(st['idx1']))
                ps = [corpus.passages[j][:600] for j in st['idx1'] + idx2]
                ans = clean_answer(self._call(res, p_r2(question, ps), 0.0, 32))
                step['observation'] = {'answer': ans, 'new_passages': [corpus.passages[j][:80] for j in idx2]}
                if not is_none(ans):
                    cid = C.id(ans); votes.append(('R2', cid)); raw.setdefault(cid, ans)
            step['wall_seconds'] = round(time.perf_counter() - tw, 3); res.llm_seconds += step['wall_seconds']
            res.trace.append(step)
        cl, p = self.posterior(votes)
        if cl:
            res.answer = raw[cl[int(np.argmax(p[:-1]))]]
        else:   # nothing usable observed: forced closed-book answer (charged)
            tw = time.perf_counter()
            res.answer = clean_answer(self._call(res, p_cb(question), 0.0, 24)); res.rounds += 1
            res.llm_seconds += time.perf_counter() - tw
            res.stopped_because += ' | forced closed-book answer'
        return res

    # ------------------------------------------------------------ calibration with a new LLM
    def calibrate(self, labelled: list[dict], corpus: Corpus) -> dict:
        """labelled: [{question, gold:[aliases]}]. Runs every action once per question and returns
        calibration pseudo-counts (+1 smoothing) for this LLM, retriever and corpus."""
        rel = {'R1': [1, 1], 'R2': [1, 1]}; ans = {'R1': [1, 1], 'R2': [1, 1]}
        kap = {g: [1, 1] for g in (1, 2, 3)}; pg = Counter({1: 1, 2: 1, 3: 1}); pairs = coll = 0
        dummy = Result(answer=None)
        for ex_ in labelled:
            q, gold = ex_['question'], ex_['gold'] if isinstance(ex_['gold'], list) else [ex_['gold']]
            idx = corpus.search(q, self.k); ps = [corpus.passages[j][:600] for j in idx]
            a1, fu = parse_r1(self._call(dummy, p_r1(q, ps), 0.0, 96))
            idx2 = corpus.search(fu or q, self.k, exclude=set(idx))
            a2 = clean_answer(self._call(dummy, p_r2(q, ps + [corpus.passages[j][:600] for j in idx2]), 0.0, 32))
            for t, a in (('R1', a1), ('R2', a2)):
                if is_none(a): ans[t][1] += 1
                else: ans[t][0] += 1; c = gold_match(a, gold); rel[t][0] += c; rel[t][1] += 1 - c
            with ThreadPoolExecutor(self.m) as ex:
                outs = [clean_answer(o) for o in ex.map(lambda _: self._call(dummy, p_cb(q), self.temp, 24), range(self.m))]
            good = [s for s in outs if not is_none(s)]
            if good:
                C = Clusters(); ids = [C.id(s) for s in good]; mo, g = Counter(ids).most_common(1)[0]
                ok = gold_match(good[ids.index(mo)], gold); kap[g][0] += ok; kap[g][1] += 1 - ok; pg[g] += 1
            wrong = [x for x in (a1, a2, outs[0] if outs else None) if not is_none(x) and not gold_match(x, gold)]
            C = Clusters(); ids = [C.id(x) for x in wrong]
            for i in range(len(ids)):
                for j in range(i + 1, len(ids)): pairs += 1; coll += ids[i] == ids[j]
        tot = sum(pg.values())
        return dict(rel=rel, ans=ans, kap={str(g): v for g, v in kap.items()},
                    pg={str(g): pg[g] / tot for g in pg}, eta=(1 + coll) / (2 + pairs),
                    n_questions=len(labelled), llm_calls=dummy.llm_calls)